SpanContainingQuery and SpanWithinQuery miss matches when the little query's spans end out of order

SpanContainingQuery(big, little) should return every big span that contains at least one little span, and SpanWithinQuery(big, little) every little span inside a big span. Spans are enumerated by start and then by end, so when the little query is a SpanOrQuery of a longer clause and a shorter one that starts inside it, the little spans' ends go down: [1,6), then [2,3). Both queries merge big and little in one forward pass that assumes the ends go up: containing tests each big span against only the first little span that starts at or after it, and within advances the big iterator past big spans that a later, shorter little span would fit in, and never goes back. Whole documents and individual spans are missed, IndexSearcher.count is wrong too, SpanWithinQuery(A, B) and SpanContainingQuery(A, B) can disagree, and adding a word to a document or an OR alternative to the little query can remove a hit; the queries never return an extra match. It happens with the default codec and settings; the merge is per document, so index size does not matter; and every release since the classes were added (5.2.0) is affected. A local fix buffers each document's spans instead of skipping them and keeps collect() working.

• Span: a match of a span query in one document, written [start, end) in token positions. In bos apple cake eos bos pie eos the tokens are at positions 0 to 6, and cake is the span [2,3).
• Order of spans: a Spans iterator returns a document's spans "by increasing start position and finally by increasing end position" (Spans.java:25-28). The ends may go down across starts.
• Big and little: SpanContainingQuery "matching spans from big that contain at least one spans from little" (SpanContainingQuery.java:33-35); SpanWithinQuery "matching spans from little that are inside of big" (SpanWithinQuery.java:32-34).
• Out-of-order ends: a SpanOrQuery ("the union of its clauses") of a longer clause and a shorter one that starts inside it. spanOr(spanNear([apple, pie], 5), cake) on the document above gives [1,6), then [2,3).

1. Containing (SpanContainingQuery.java:94-132): for each big span, advance little while little.start < big.start, then test only that one little span (big.end >= little.end). Sentence [0,4) is tested against [1,6) only (6 > 4); for sentence [4,7) the little iterator runs past [2,3) and is exhausted. cake is never tested against the sentence that contains it.
2. Within (SpanWithinQuery.java:93-131): for each little span, advance big while big.end < little.end, then test big.start <= little.start. Little [1,6) pushes the big iterator past sentence [0,4) to [4,7); little [2,3) is then tested only against [4,7) (4 > 2). A Spans cannot be rewound, so [0,4) is gone.
3. Only out-of-order ends trigger it. If the little ends rise, skipping is safe: a big span that ends before the current little span ends before every later one. A TLA+ model of both loops (TLC, every pair of span lists of up to 3 spans over 4 and 5 positions) shows them sound and complete whenever the little ends rise, whatever the big spans are.
4. Trigger detail. For containing, the long little span that hides the match must be the first little span that starts at or after big.start. Within fails whenever an earlier, longer little span pushes the big iterator past the big span that contains a later, shorter one.

The last row is the 6-state minimal counterexample TLC produced. Adding an OR alternative removes a hit, and within disagrees with containing on the same pair.

Exhaustive check of the stock jar (every document of 1 to 6 tokens over 4 letters, 5,460 documents; 18 span queries as big and as little; both query types: 648 queries; expected results built from the spans Lucene itself returns for big and little): 68 queries miss documents, 10,762 missed document hits and 20,016 missed spans, 0 extra hits or spans, IndexSearcher.count wrong on the same 68 queries, 28 big/little pairs where within and containing disagree, and no failure when the little ends rise.

• Who is exposed. Code that builds SpanContainingQuery or SpanWithinQuery (public API in lucene-queries) with such a little clause: a sentence- or paragraph-scoped "X OR (Y NEAR Z)" search, or a nested containment query as the little clause. The registry also lists downstream query languages with span_containing / span_within queries as a route (not checked here).
• What happens. Documents are missed, so counts, top-k and facets built on the query are too low. Documents that still match can lose spans and so score lower (sloppy frequency): 76 queries in the exhaustive check return a wrong span set against 68 with a wrong hit set; for example SpanWithin(b, spanOr(spanNear([a, b], 3, unordered), b)) on b b a returns [0,1) but not [1,2).
• Inside an exclusion (MUST_NOT), a missed match lets a document through: +*:* -SpanContaining(sentence, little) returns bos apple cake eos bos pie eos (1 hit, expected 0); with the fix, 0.
• Within and containing disagree. SpanWithinQuery(A, B) and SpanContainingQuery(A, B) match different documents for 28 big/little pairs, which an upstream test asserts cannot happen.
• Scale. Deterministic and per document (seen from one-document indexes to 100,000 documents); the default codec, IndexWriterConfig and IndexSearcher in the plain main() probes, randomized codecs in the JUnits; assertions on and off. On 100,000 random 40-word documents, SpanContainingQuery(near(w1, w2, 10), spanOr(near(w3, w4, 5), w5)) returns 1,122 hits on main and 1,124 with the fix: rare on random text; real phrasing patterns decide.
• How likely. Rare: span queries are a legacy API (intervals are the replacement), the shape is specific, and nobody has reported it since 2015. Not a 10.6.0 regression.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: expected:<containing=[1 within=1]> but was:<containing=[0 within=0]>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.queries.spans.TestSpanContainUnorderedLittleEnds.testShortLittleSpanAfterLongerOne(TestSpanContainUnorderedLittleEnds.java:53)

• Exact containment is documented (SpanContainingQuery.java:33-35, :76-79; SpanWithinQuery.java:32-34, :75-78; package-info.java:35-38). No javadoc, package doc, CHANGES or MIGRATE entry says the result is approximate or lazy. The only "minimum slop matches" caveat in the package is on NearSpansOrdered (NearSpansOrdered.java:26), which is not involved: the expected results are built from the spans Lucene itself returns for big and little.
• The input is legal. Spans.java:25-28 allows falling ends; the module's test wrapper AssertingSpans checks that starts never go backwards and that start <= end, not the order of ends (every query of the union-law test was wrapped in AssertingSpanQuery; no assertion fired).
• Upstream asserts the broken property. TestSpanSearchEquivalence.testSpanWithinVsContaining (:452-465): "SpanWithinQuery(A, B) = SpanContainingQuery(A, B)", with a single-term little clause.
• Tests never covered it. Every upstream little clause in TestSpanContainQuery, TestSpanSearchEquivalence, TestSpanWithinQuery and the nightly payload test is a term, an OR of single terms or a two-term near: all have rising ends.
• History. The loops came with the classes (LUCENE-6083, 2015) and are unchanged; the discussion covered containment semantics, two-phase iteration and naming, not completeness.

The strongest case for "works as designed": span queries are forward-only and lazy, and upstream accepts the consequences. In #8451 the author of ContainSpans defined lazy as "all subspans are only moved forward" and wrote "To allow collecting/payloads easily, I'd rather accept the limitations/bugs of the current lazy implementation"; #10247 stopped QueryBuilder from building span graph queries because of #8451; #16820 says that span queries "have some basically unfixable correctness bugs".

Why it fails here: #8451's statements are about SpanNearQuery and #10247 about the span graph queries QueryBuilder used to build, where a complete answer needs backtracking over child spans; #16820's remark names no class and no specific bug. Here the child spans are correct, the miss is in the two containment loops, the fix needs no rewinding of any child Spans, and the javadocs of these two classes promise exact containment. Every verifier judged it real, and the two that built the works-as-designed case rejected it; expect upstream to raise it anyway and to suggest intervals.

Option A was applied in a scratch worktree of main a9779ef3c193 and run through gradle with assertions on and off; it was validated on main only, not ported to or run on any release branch. Options B to D were not run. A user-side workaround is the Intervals API: Intervals.containing / Intervals.containedBy return the expected documents on the inputs checked.

• SpanWithinQuery: keep the big spans of the current document that start at or before the current little span, with the maximum of their ends; the little span matches iff that maximum is >= little.end. Nothing is rewound.
• SpanContainingQuery: buffer the document's little spans with the suffix minima of their ends; a big span matches iff the minimum end over the little spans that start at or after big.start is <= big.end.
• collect() still reports a partner (ContainSpans.java:55-58 collects big and little, and payload scoring relies on it). A new package-private SpanLeafRecorder records the buffered spans' leaves (term, position, doc, freq, offsets, payload copy) and replays the partner's: for containing the first buffered little span inside the big span, for within the first buffered big span that contains the little span.
• What this doc changed in the hunt's sketch: the replayed PostingsEnum returns the recorded freq() and docID() of the original postings. The sketch returned freq() == 1, and the UnifiedHighlighter (which sizes its offset arrays by postings.freq(), PhraseHelper.java:355, :377-378) and a freq-sized SpanCollector threw ArrayIndexOutOfBoundsException, also on queries that work today.

3 files, +261/-38 (google-java-format applied). The within loop:

private boolean littleInsideBig() throws IOException {
  final int littleStart = littleSpans.startPosition();
  while (bigSpans.startPosition() <= littleStart) { // NO_MORE_POSITIONS ends the loop
    if (bigSpans.startPosition() != -1) {
      bigEnds = ArrayUtil.grow(bigEnds, numBig + 1);
      bigEnds[numBig++] = bigSpans.endPosition();
      bigLeaves.record(bigSpans);
      maxBigEnd = Math.max(maxBigEnd, bigSpans.endPosition());
    }
    bigSpans.nextStartPosition();
  }
  return maxBigEnd >= littleSpans.endPosition();
}

Trade-offs

• Cost. Each candidate document's little spans (containing) or big spans (within) are drained and their leaves recorded, with a payload copy when payloads exist; memory grows with the spans and the recorded leaves (term, position, doc, freq, offsets, payload copy) per document, and high-frequency leaves, deep span trees and large payloads were not measured. A rough probe on a shared, loaded machine (100,000 random documents, count(), 7 alternating runs each; not a benchmark), median main vs fix: containing with an OR little clause 9.1 vs 10.7 ms, within with the OR 7.2 vs 7.9 ms, with a term little clause 5.5 vs 5.7 ms and 4.3 vs 4.7 ms. The run-to-run spread is about as large: probably a modest slowdown; benchmark properly before quoting numbers.
• Partner reported to collect(). Where main already matches, containing reports the same little span as today. Within can report another big span when ends are out of order: on a b c d e, big spanOr(phrase a b c, phrase a b c d e), little spanOr(phrase a b c d, b), the little span [1,2) is collected with big [0,5) on main and with big [0,3) with the fix (both contain it). Payload scores and highlights of such spans can change; keep today's partner if the PR must not change them.
• Review nits. Containing's collect() ends with throw new AssertionError(...); upstream is replacing such errors with proper exceptions (#16919), so use IllegalStateException. The recorder allocates one small PostingsEnum per replayed leaf.
• Scope. Local to the two classes plus one package-private helper; no API change.

What the checks validated

• Gradle in a scratch worktree of main a9779ef3c193 (removed afterwards), seed DEADBEEF, assertions on and off: the finder's, the independent reproducer's and the devil's advocate's JUnits and the freq-sized collector test (4 classes, 14 tests) pass, where main fails 9 of them with assertions on and 9 off; the two UnifiedHighlighter tests pass on main and with the fix.
• This doc's JUnit: 3 of 3 pass with the fix and 3 of 3 fail on main, assertions on and off.
• All span and payload tests with -Ptests.nightly=true: 32 classes, 280 tests, 0 failures (the copied tests included).
• All of :lucene:queries:test: 55 classes, 526 tests, 0 failures; all of :lucene:highlighter:test: 36 classes, 724 tests, 0 failures. :lucene:queries:check -x test (google-java-format, ecjLint, forbiddenApis, license headers) passes with the patch and this doc's JUnit.
• Through the repro harness with the three files shadowed (assertions on and off): the finder's JUnit 4 of 4, the reproducer's 6 of 6, the root-cause test, the two highlighter tests and the freq-sized collector test pass; the exhaustive check gives 0 mismatches over 839,056 checks.
• UnifiedHighlighter snippets are identical to main's on every case main already matches, with offsets from postings and from weight matches; the missed cases now highlight, for example <b>new</b> <b>york</b> city.
• Earlier, for the position logic: TLC shows the fixed loops sound and complete within its bounds (mutants of the fix are caught), and 264 upstream span and payload tests pass with -Dtests.nightly=true.

Keep today's fast path (test the current span first) and buffer only the spans the loop advances past while it looks further, with a sliding minimum (containing) or maximum (within).

Trade-offs

Avoids draining whole documents when the first candidate matches, at the price of more complex state; needs its own model check or exhaustive run.

SpanContaining(big, spanOr(a, b)) becomes spanOr(SpanContaining(big, a), SpanContaining(big, b)), and the same for within, as #9523 did for intervals.

Trade-offs

Partial: fixes only a top-level OR whose clauses each have rising ends, changes scoring and span duplication, and leaves nested shapes broken.

State in both javadocs that the little query's spans must end in start order.

Trade-offs

Cheapest; fixes nothing.

• Method (semi-formal): bounded-exhaustive checking of the stock jars against the set semantics in the javadoc. An earlier hunt unit's spans checker met the SpanWithin leg and set it aside as the #8451 class; a later planning probe (5,460 documents x 392 queries) found both legs and isolated the containment step.
• Then TLA+ model checking (TLC; the logs say "TLC2 Version 2026.10.20.183001") of the per-document loops, transcribed line by line: every pair of sorted span lists of up to 3 spans over 4 and 5 positions. TLC found the 6-state counterexample big [0,2), little [0,3), [1,2) and, within those bounds, showed both loops sound and complete whenever the little ends rise, and showed the fix's position logic sound and complete (its mutants are caught).
• The exhaustive check of the jar was then widened to 857,111 checks, and the finder reduced it to a public-API JUnit; independent checkers followed (see "Independent checks").