MUST_NOT queries no longer skip long runs of excluded documents (ReqExclBulkScorer, since #16669)

Since #16669 ("Use intoBitSet to speed up ReqExclBulkScorer with dense exclusions", merged 2026-09-24, first released in 10.6.0 on 2026-10-29), ReqExclBulkScorer scores +R -X in windows of at most 4,096 docs, each starting where the previous call to R's bulk scorer returned: it loads the exclusion of each window into a bit mask, flips it into an accept mask and always calls R's bulk scorer for the window (ReqExclBulkScorer.java:53-93, line 86 on main 645d4fe14a20), even when the mask accepts nothing. The default bulk scorer visits every match of R before it checks the mask (Weight.java:293-315). #16669 also removed the docIDRunEnd skip that 10.3.0 to 10.5.2 used to jump runs of excluded documents without moving R (#14976), and the two-phase variant added in the same cycle (#16307).

So when X excludes a long run of doc IDs (the older documents of an append-ordered or time-sorted segment, an index-sorted range, a flag on a contiguous block, a cached dense filter) and the required side costs more than 0.3% of maxDoc, +R -X costs about as much as R alone. Hits, counts and top-k were identical in every executed case; only the work changes. In the minimal repro (one 10,000-doc segment, run [0, 9000)), a counting match-all R moves 10,001 times on main and on the 10.6.0 release jars, against 1,001 on every release from 10.0.0 to 10.5.2. At 1M documents with 99.9% excluded, a PhraseQuery as R reads 2,000,000 postings instead of 2,002. The 10.6.0 release notes still say that ReqExclBulkScorer "now skips runs of excluded docs". A 12-line change that scores R only over the accepted part of each window never steps R inside an excluded run that crosses a window boundary (any run of 4,096 documents or more), as in 10.5.2, and passes the org.apache.lucene.search tests.

1. Routing. BooleanScorerSupplier.java:203-207: with a MUST_NOT clause and a supplier cost (the cheapest MUST/FILTER clause's cost, computeCost) of at most 3L * maxDoc / 1000, the doc-at-a-time ReqExclScorer runs (not affected). Otherwise FILTER/MUST clauses without SHOULD get requiredBulkScorer() (:235-236) and :259-265 returns new ReqExclBulkScorer(positiveScorer, prohibitedScorer); several MUST_NOT clauses become one disjunction.
2. The window loop. ReqExclBulkScorer.java:53-93: each window is [windowMin, min(max, windowMin + 4096)) (:60-61), where windowMin is what the previous req.score call returned; the exclusion is advanced to the window (:63-65), loaded with intoBitSet (:67-72), flipped into an accept mask and combined with acceptDocs (:73-84); then upTo = req.score(collector, windowBits, windowMin, windowMax); (:86) runs for every window. The class has no docIDRunEnd call left.
3. Why a rejected window still costs. The default bulk scorer loops for (int doc = iterator.docID(); doc < max; doc = iterator.nextDoc()) and only then checks acceptDocs.get(doc) (Weight.java:293-301; the two-phase loop :303-315 also calls matches()). So a window that X covers completely costs one step per match of R in it.
4. What it replaced. 10.5.2 ReqExclBulkScorer.java:51-78, the leap-frog loop of LUCENE-6940 (5.5.0/6.0.0): when a non-two-phase exclusion sits on upTo, upTo = Math.min(exclApproximation.docIDRunEnd(), max); (:60-62, from #14976, 10.3.0), a two-phase one is confirmed with matches() and passed one doc at a time (:63-65), else req.score(collector, acceptDocs, upTo, Math.min(exclDoc, max)) (:69), so R is only scored on the gaps between excluded documents.

Minimal repro: 10,001 required-iterator moves on main and 10.6.0 against 1,001 on 10.0.0 to 10.5.2, 1,000 hits everywhere. At 1M documents with the run [0, 999000): 1,000,001 against 1,001 moves for five kinds of exclusion (postings run, index-sort range, cached bit set, two-phase doc-values range with a skip index, 2-term disjunction), count and top-10 alike; a stock PhraseQuery as R reads 2,000,000 postings against 2,002. Indicative wall clock on a shared host, 10.5.2 to main: term top-10 0.299 to 2.479 ms, 8-term OR top-10 2.330 to 18.506 ms, phrase count 0.711 to 11.368 ms. The claim rests on the counts, not the timings.

• Configuration. Default codec, IndexWriterConfig and IndexSearcher; assertions on or off; single thread.
• Which queries. A BooleanQuery with MUST/FILTER clauses and MUST_NOT clauses that BooleanScorerSupplier sends to ReqExclBulkScorer (the required side costs more than 0.3% of maxDoc). By code reading the same wrapping also serves a pure SHOULD disjunction with MUST_NOT (not run).
• Which data. Many of R's matches must lie inside long runs of excluded doc IDs. Doc IDs follow indexing order and index sorting, so time-based exclusions on append-ordered or time-sorted segments, index-sorted ranges, flags on contiguous blocks and cached dense filters produce such runs; all five kinds of exclusion tested regress the same way.
• How bad. About the cost of R alone: at most linear in maxDoc per segment, no hang, no extra memory beyond a 4096-bit mask. Largest when R decodes or scores postings per document (term top-k, phrase, disjunction): about 8x to 16x in the indicative timings. Probably small for MatchAllDocsQuery or another dense constant-score R whose bulk scorer applies the mask word by word (code reading, not measured).
• Not affected: required clauses at or below 0.3% of maxDoc (doc-at-a-time path). Not claimed: interleaved, non-run exclusions, the case #16669 targets: there the window path moves work from the exclusion to R (on #16669's dense shape 1,000,001 required and 3 exclusion moves on main, against 40,001 and 980,003 on 10.5.2), and #16669 reports large speed-ups.
• Versions. 10.6.0 (released 2026-10-29) and main. All releases from 10.0.0 to 10.5.2 are fine.

TestReqExclSkipsExcludedRun (123 lines with the license header, one test method). The counting clause is a plain Query whose ConstantScoreWeight wraps a counting DocIdSetIterator in a ConstantScoreScorer and Weight.DefaultScorerSupplier; these are public but marked @lucene.internal, fine for an in-tree test (for a stock-query demonstration, use the PhraseQuery postings count above). Its Weight keeps count() at the default -1, because with a stock MatchAllDocsQuery IndexSearcher#count would shortcut through BooleanWeight#count and never score. The query cache is off. The test first checks the hit count (1,000, passes everywhere), then that the required iterator moved at most 2,000 times.

The <= 2_000 bound is a judgement; the observable fact is maxDoc + 1 moves (10,001) against hits + 1 (1,001). It is every document of the run only because R matches all documents; in general R steps through every one of its matches inside the run. The comment line in the test is longer than 100 columns; wrap it before adding the test to the tree. As a regression test it can go into the existing TestReqExclBulkScorer as one more method.

cp $REPRO/TestReqExclSkipsExcludedRun.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestReqExclSkipsExcludedRun -Ptests.seed=1044B21F

# main 645d4fe14a20, gradle, -Ptests.seed=1044B21F
TestReqExclSkipsExcludedRun > testRequiredClauseSkipsExcludedRun FAILED
    java.lang.AssertionError: required iterator moved 10001 times
        at org.apache.lucene.search.TestReqExclSkipsExcludedRun.testRequiredClauseSkipsExcludedRun(TestReqExclSkipsExcludedRun.java:119)
1 test completed, 1 failed

# standalone runner
main 645d4fe14a20, -ea / -da               failures=1  required iterator moved 10001 times
10.6.0 (Maven Central jars), -ea / -da     failures=1  required iterator moved 10001 times
10.5.2, -da                                failures=0  (1,001 moves)
main + recommended fix, -ea                failures=0

• The same release notes say the opposite. The 10.6.0 section of lucene/CHANGES.txt lists "GITHUB#16669: Use intoBitSet to speed up ReqExclBulkScorer with dense exclusions." (:687 on main) and, earlier in the same Optimizations section, "GITHUB#16307: ReqExclBulkScorer now skips runs of excluded docs via TwoPhaseIterator#docIDRunEnd for two-phase excluded clauses (e.g. a doc-values not-equals filter), instead of advancing one doc at a time." (:632-634; :183-185 and :238 in the 10.6.0 release commit). The shipped class has no docIDRunEnd call (0 references in the bytecode of main and of the RC1 core jar, 1 in 10.5.2).
• The skip was built on purpose. #14976 added it (10.3.0, CHANGES.txt:1699: "Utilize docIdRunEnd on ReqExclBulkScorer."); #16142 made it cheap for several MUST_NOT clauses (10.5.0, :1158: "Optimize disjunction #docIDRunEnd to skip runs of excluded documents."; it changed DisjunctionDISIApproximation, and its PR body says "ReqExclBulkScorer uses the prohibited scorer's docIDRunEnd() to skip runs of excluded documents"); #16307 extended it to two-phase clauses in the 10.6 cycle.
• #16669 removed the old loop on purpose, but never measured runs. Its issue #16668 notes that "docIDRunEnd() only helps when the iterator can expose a consecutive run of matching document IDs". Its first commit (b3094fab914) kept the old leap-frog loop, with both docIDRunEnd branches, as a sparseScore path used only when excl.cost() < req.cost() >>> 7, so any exclusion costing at least 1/128 of R (the minimal repro's 9,000 against 10,000, for example) already took the window path. The author then wrote "I'm exploring whether we can remove the sparse path and use the dense path universally, which would simplify the implementation", and commit e0c955a58c7 ("delete spare path") removed it. The benchmarks behind that (round-robin interleaved MUST_NOT terms, luceneutil ReqExclSparse/ReqExclDense, not-equals ranges) contain no run-shaped exclusion, and the PR body, its 9 comments and 4 review comments do not mention long runs or the skip.
• Why no test caught it. #14976 and #16307 added no test; #16669's tests check results, not cost.
• Precedent. Upstream fixed comparable MUST_NOT slowdowns (#16049, fixed by #16142; #16702, addressed by #16715) and the same window-vs-leap-frog trade-off in DenseConjunctionBulkScorer (#16259).

The strongest case for "intended": Lucene documents matching semantics, not cost; #16669 chose the window path deliberately and deleted the leap-frog path on purpose, to simplify; and +R -X now costs about what R alone costs, which a maintainer may accept. The cross-model intended-lens review rated this case moderate, the intended-behaviour checker weak to moderate, and upstream may label the report an enhancement, as it did #16049.

Why it does not settle it: the release notes of the very release that ships the change advertise the skip; nothing in #16669 shows the run case was measured or the loss of the skip weighed; and, as far as measured, a fix need not undo #16669, because skipping the required clause where the mask rejects every document keeps the window path for interleaved exclusions (operation counts only, no end-to-end benchmark). Verdict: an unintended performance regression against 10.3.0 to 10.5.2, results correct; a maintainer may still label it an enhancement.

Three variants were written against 645d4fe14a20 and measured on the same shapes (required-iterator moves; hits identical everywhere):

On #16669's dense shape 10.5.2 pays on the exclusion side instead (980,003 exclusion moves).

ReqExclBulkScorer.java, replaces line 86; the 12 added lines of fix-optC.diff, verbatim:

      // Score the required clause only from the first to the last doc the mask accepts, and not at
      // all when the mask accepts nothing, e.g. when a run of excluded docs covers the window.
      int first = windowMask.nextSetBit(0, windowLength);
      if (first == DocIdSetIterator.NO_MORE_DOCS) {
        upTo = windowMax;
        continue;
      }
      int last = windowMask.prevSetBit(windowLength - 1);
      upTo = req.score(collector, windowBits, windowMin + first, windowMin + last + 1);
      // No doc after the last accepted one can match: the next window starts at windowMax at the
      // earliest, where the exclusion iterator is positioned after intoBitSet.
      upTo = Math.max(upTo, windowMax);

Trade-offs

• General: works for every exclusion, whether or not its iterator reports runs, and calls no docIDRunEnd. R is never stepped inside an excluded run that crosses a window boundary (any run of 4,096 documents or more): windows inside the run are skipped and the run's part of its first and last window is trimmed off.
• upTo must not fall below windowMax: intoBitSet has moved the exclusion iterator there, so a window starting earlier would miss excluded documents.
• Leaves: a run strictly inside a window with accepted documents on both sides is still stepped (at most that window's 4,096 documents); the exclusion is still loaded into a mask for every window inside a run, as on main; if R runs out of matches inside a long run, masks are loaded until the next window with an accepted document (code reading, not measured); the unreleased two-phase skip of #16307 stays gone; measured by operation counts only, not benchmarked end to end.

What the checks validated

• gradle in a scratch worktree at 645d4fe14a20, -Ptests.seed=1044B21F: the minimal test fails without the fix and passes with it; with it, the nine closest suites pass (TestReqExclBulkScorer, TestBooleanQuery, TestBoolean2, TestBooleanScorer, TestBooleanMinShouldMatch, TestBooleanScorerSupplier, TestBooleanOr, TestBooleanRewrites and the new test: 138 tests), and so does the whole org.apache.lucene.search package (215 classes, 2,340 tests, 49 skipped, 0 failures).
• 1,152 count identities, 0 mismatches; a randomized partition test (run, interleaved, two-phase doc-values and disjunction exclusions, MUST and FILTER, 10% deletions, random sub-ranges against brute force), 3 seeds, pass; independent verifiers' run tests pass.
• A verifier's two-phase test still fails with C (512 matches() calls where it asserts 112; that run was launched expecting a pass, so the runner marks it unexpected): C does not restore #16307's two-phase skip.

Insert after the exclusion is advanced to windowMin (:63-65), +12:

      if (exclApproximation.docID() == windowMin) {
        int runEnd =
            exclTwoPhase == null ? exclApproximation.docIDRunEnd() : exclTwoPhase.docIDRunEnd();
        if (runEnd > windowMin) {
          upTo = (int) Math.min((long) max, (long) runEnd);
          continue;
        }
      }

Trade-offs

Brings back the released mechanism: a run that reaches a window start is jumped in docIDRunEnd steps without loading masks, and a two-phase exclusion with a proven run is skipped without matches() (#16307); when no run is proven, the existing intoBitSet path still calls matches() per candidate. Limits: a run that starts inside a window is stepped up to the next window boundary (5,098 against 1,502 moves above); only exclusions whose iterator reports runs benefit.

What the checks validated

The minimal test passes with assertions on and off; 99 upstream tests of TestReqExclBulkScorer, TestBooleanQuery, TestBoolean2, TestBooleanScorer, TestBooleanMinShouldMatch and TestBooleanScorerSupplier, 30 iterations of TestReqExclBulkScorer, 1,152 count identities and 576 partitioned checks pass.

+24/-1. C's trimming plus A's run jump and two-phase skip.

Trade-offs

Equal to C on most shapes and restores the two-phase skip, but worse than C on runs of 2,000 and 4,000 (68,017 and 52,013 against 52,075 and 4,050 moves), because A's jumps end at run ends and move the window starts onto the kept documents.

What the checks validated

The minimal test, the independent verifiers' run tests including the two-phase one, the partition test (2 seeds), a mid-window-run test and the 1,152 count identities pass. Through gradle at 645d4fe14a20 it passes the minimal test and the same nine suites (138 tests).

To restore 10.5.2's cost for runs inside a window too, a window whose mask has only a few accepted stretches could score R once per stretch, as #16259 brought leap-frog back for sparse windows in DenseConjunctionBulkScorer.

Trade-offs

More code and a heuristic threshold.

What the checks validated

Not written or measured.

Method: non-formal lead, semi-formal backing. The hunt's "10.5.2 vs 10.6.0 RC1" differential lens read the #16669 diff and compared query costs on 10.5.2, RC1 and main with identical hits; MUST_NOT queries with a contiguous excluded range stood out. A skeptic re-run replaced timings with a count of the required iterator's moves (1,001 on 10.2.2 to 10.5.2 against 1,000,001 on RC1 and main at 1M documents).

The hunt then reduced it to one JUnit, measured five kinds of exclusion and stock PhraseQuery/TermQuery postings reads, and built a bounded-exhaustive model of the 10.5.2, main and fixed loops: 790,324 cases for cost and correctness plus 16.4M partitioned and chunked re-entrant correctness checks, with two mutants caught.