Dense FILTER/MUST + MUST_NOT queries silently drop every match in the last 4096-doc window of a segment near MAX_DOCS (int overflow in ReqExclBulkScorer)

Since #16669 (merged 2026-09-24, released in 10.6.0), ReqExclBulkScorer scores required -excluded in windows of 4096 doc IDs and hands the required clause's bulk scorer a WindowBits mask of the documents that are not excluded. WindowBits.applyMask computes the end of the caller's 4096-bit set as Math.min(DocIdSetIterator.NO_MORE_DOCS, offset + bitSet.length()) in int (ReqExclBulkScorer.java:125 on main 645d4fe14a20). For a window that starts at 2,147,479,552 (2^31 - 4096) or later the sum wraps negative, the method sees an empty range and clears every bit. On a segment with more than 2,147,479,552 documents, a BooleanQuery that BooleanScorerSupplier routes to ReqExclBulkScorer (a MUST_NOT clause, a supplier cost above 0.3% of maxDoc, which for a single required clause is that clause's cost, and FILTER/MUST clauses with no SHOULD clause) and whose required side is bulk-scored by DenseConjunctionBulkScorer or ConstantScoreBulkScorer (for example *:*) therefore silently loses up to the last 3,967 doc IDs: end to end, +*:* -b:y on one segment of IndexWriter.MAX_DOCS documents counts 2,147,479,551 instead of 2,147,483,518, with assertions on and off. main, branch_10x and branch_10_6, including the 10.6.0 RC1 revision, are affected; 10.5.2 and every older release are correct. MathUtil.unsignedMin(DocIdSetIterator.NO_MORE_DOCS, offset + bitSet.length()) fixes it.

• ReqExclBulkScorer: the bulk scorer for "required minus excluded". Since #16669 it collects the excluded documents of each 4096-doc window into a bit set, flips it into an accept mask, and passes a WindowBits (a Bits over that mask) as acceptDocs to the required clause's bulk scorer (ReqExclBulkScorer.java:54-93, :86). Its own window end is computed in long: (int) Math.min((long) max, (long) windowMin + WINDOW_SIZE) (:61).
• Bits#applyMask(FixedBitSet bitSet, int offset): clears bit i of bitSet when document offset + i is not accepted (util/Bits.java:39-72).
• When the bulk path is used: BooleanScorerSupplier.java:203-207 returns no bulk scorer when there is a MUST_NOT clause and the supplier's cost() is at most 3L * maxDoc / 1000 (then the iterator-based ReqExclScorer runs and is correct). That cost is the supplier's estimate for the positive side (with required clauses and no minShouldMatch, the cost of the cheapest required clause, :82-101); for a single required clause it is that clause's cost. Otherwise, if the clause shape has a positive bulk scorer (FILTER/MUST clauses get requiredBulkScorer only with no SHOULD clause and minShouldMatch 0, :235-236), :265 returns new ReqExclBulkScorer(positiveScorer, prohibitedScorer). The bug then needs that bulk scorer to call applyMask on a window at 2^31 - 4096 or later; not every MUST_NOT query with a dense required side meets both conditions.
• The callers: constant-score clauses get DenseConjunctionBulkScorer when they match at least 1/32 of maxDoc, else ConstantScoreBulkScorer when scores are not needed (ConstantScoreScorerSupplier.java:78-99); MatchAllDocsQuery (MatchAllDocsQuery.java:48), TermQuery without scores (TermQuery.java:168-173), PointRangeQuery, FieldExistsQuery and the multi-term constant-score wrapper use it. Both scorers call acceptDocs.applyMask(windowMatches, windowBase) on a 4096-bit set (ConstantScoreBulkScorer.java:142, DenseConjunctionBulkScorer.java:283).

ReqExclBulkScorer.java:124-145:

1. :125 int bitSetEnd = Math.min(DocIdSetIterator.NO_MORE_DOCS, offset + bitSet.length()); With offset = 2,147,479,552 and length 4096 the sum is 2,147,483,648 = 2^31, which wraps to -2,147,483,648. Math.min with NO_MORE_DOCS (Integer.MAX_VALUE) cannot change an int, so it does not guard anything.
2. :127 from = Math.max(windowBase, offset) is about 2.1 billion; :128 to = Math.min(windowEnd, bitSetEnd) is negative.
3. :129-131 if (from >= to) { bitSet.clear(); return; } clears all 4096 bits: every match of that window is gone.

A Z3 bit-vector (32-bit) model of the bounds gives 2,147,479,552 as the smallest failing offset for a 4096-bit set. Under the model's preconditions (a set of 1 to 4096 bits, 0 <= windowBase <= offset < windowEnd <= MAX_DOCS) it proves that the upper bound to equals the exact min(windowEnd, offset + bitSet.length()) whenever offset + bitSet.length() <= Integer.MAX_VALUE, and that the overflow case takes the bitSet.clear() branch although the window is not empty. The model covers the bounds only, not the clear and andRange part of the method.

Only doc IDs 2,147,479,552 to MAX_DOCS - 1 = 2,147,483,518 can be lost: 3,967 per segment and query at most. Over *:* the windows start at multiples of 4096 (the last at 524,287 x 4,096 = 2,147,479,552), so all 3,967 are lost: the end-to-end count is 2,147,479,551 instead of 2,147,483,518. A ConstantScoreBulkScorer window starts at its first match, so it loses the matches of any window that starts at 2,147,479,552 or later; a window that starts below that is correct.

• Who is exposed. An index with one segment of more than 2,147,479,552 documents. IndexWriter.MAX_DOCS = 2,147,483,519 limits the whole index (IndexWriter.java:201-208), so such a segment leaves room for at most 3,966 documents in all other segments together.
• Which queries. A BooleanQuery that BooleanScorerSupplier routes to ReqExclBulkScorer (a MUST_NOT clause, a supplier cost() above 3L * maxDoc / 1000, which for a single required clause is that clause's cost, and a positive bulk scorer, such as FILTER/MUST clauses with no SHOULD clause), and whose FILTER or MUST side is bulk-scored by DenseConjunctionBulkScorer or ConstantScoreBulkScorer. Executed with *:* as FILTER and as MUST. By code reading also a single constant-score filter such as a term, point range or exists query (not executed).
• Default configuration. Default IndexWriterConfig, codec and IndexSearcher; assertions on or off; single thread, no race.
• What is wrong. Counting and exhaustive collection, and an exact-count top-10 search (TopScoreDocCollectorManager(10, Integer.MAX_VALUE) with MUST *:*: totalHits 2,147,479,551 instead of 2,147,483,518). Silent: no exception. The query itself never returns an excluded or deleted document; the method only clears bits.
• Not affected. A sparse required side (the iterator-based ReqExclScorer runs): a legal end-to-end run with FILTER a:x on the last 100 documents passes. Every release.
• Not tested. IndexSearcher#count, and the other applyMask callers that could receive a WindowBits (MaxScoreBulkScorer.java:246, BooleanScorer.java:149).
• How likely: contrived. The trigger needs a single segment within 3,966 documents of the limit, which is expected to be rare. The point of fixing it now is that 10.6.0 (released 2026-10-29) ships it.

TestReqExclLastWindow (51 lines with the license header, one test method). It builds the scorer pair a real +*:* -b:y search gets on such a segment, a ReqExclBulkScorer over a DenseConjunctionBulkScorer, and scores it over [0, MAX_DOCS) without building a 2-billion-document index. The test uses no randomness, and :lucene:core:checkGoogleJavaFormat passes with it in the tree. As a regression test it can go into the existing TestReqExclBulkScorer as one more method.

End to end, the finder's legal run (one default-codec segment of IndexWriter.MAX_DOCS documents, about 2.1 billion addDocument calls, 7 to 15 minutes) counted +*:* -b:y as 2,147,479,551 instead of 2,147,483,518, with -ea and -da, on main ea57360912ed, whose involved files are identical at 645d4fe14a20. The same test, repeated on 645d4fe14a20 when the diagram was made, gave the same count with -ea and -da. These are the only runs of this legal-index test (the other legal-index run is the sparse control, which passes); the independent checks used unit tests and a public-API partial check (a reader that reports maxDoc = MAX_DOCS over a one-document segment).

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

# gradle, main 645d4fe14a20, -Ptests.seed=DEADBEEF (-Ptests.asserts=true and false)
TestReqExclLastWindow > testLastDocsOfMaxDocsSegment FAILED
    java.lang.AssertionError: expected:<99> but was:<0>

# standalone runner, seed DEADBEEF (the -da run at 4ae946e5a9b is the fact check's)
main 645d4fe14a20, -ea                       tests_run=1 failures=1   expected:<99> but was:<0>
main 645d4fe14a20, -da                       tests_run=1 failures=1   expected:<99> but was:<0>
branch_10_6 4ae946e5a9b (RC1 revision), -ea  tests_run=1 failures=1   expected:<99> but was:<0>
branch_10_6 4ae946e5a9b (RC1 revision), -da  tests_run=1 failures=1   expected:<99> but was:<0>
10.5.2, -ea                                  tests_run=1 failures=0

# end to end, one segment of IndexWriter.MAX_DOCS docs, +*:* -b:y (main ea57360912ed and 645d4fe14a20, -ea and -da)
TestMatchAllMustNotInMaxDocsSegment > testCountAllButOne FAILED
    java.lang.AssertionError: expected:<2147483518> but was:<2147479551>

• Contracts. BooleanClause.java:58: MUST_NOT is for clauses that "must not appear in the matching documents"; :35: FILTER is "Like MUST except that these clauses do not participate in scoring". Bits#applyMask (Bits.java:39-63) requires a non-negative offset and that set bits map below length(), and "Apart from that, this should behave the same way as the default implementation", which clears bit i only when document offset + i is not accepted. The failing calls meet both preconditions (offset 2,147,479,552; every set bit below MAX_DOCS).
• The limit. IndexWriter.MAX_DOCS = Integer.MAX_VALUE - 128, "Hard limit on the maximum number of documents that may be added to the index" (IndexWriter.java:201-208). The end-to-end index was built with default settings inside it.
• The code appears to cap the sum. Math.min(DocIdSetIterator.NO_MORE_DOCS, x) cannot change an int x. The otherwise redundant cap at :125 is consistent with an intended overflow guard missing its long widening; this is an inference, since the #16669 discussion never mentions overflow. score() in the same class widens its own window end (:61).
• The project fixes this pattern elsewhere. #14750 (2025-06-03) added MathUtil.unsignedMin because dividing the doc-ID space into windows "is prone to integer overflows if the size of the window is greater than Integer.MAX_VALUE - windowStart". BitSetDocIdStream.java:34 uses it on the same expression, MathUtil.unsignedMin(Integer.MAX_VALUE, offset + bitSet.length()), and so do both callers here for their own window ends (ConstantScoreBulkScorer.java:132, DenseConjunctionBulkScorer.java:198, :214).
• History. #16669 ("Use intoBitSet to speed up ReqExclBulkScorer with dense exclusions", the PR title, also the title of performance issue #16668 and of its CHANGES.txt entry under 10.6.0; the commit subject drops "with dense exclusions") is a speed-up. Its 9 comments, 2 reviews and 4 review comments never mention overflow, and its test testWindowBitsApplyMask uses offsets 96 to 108 (TestReqExclBulkScorer.java:263-293). The parent commit and the seven releases run return the right result; no release before 10.6.0 contains WindowBits.

The strongest case for "not a bug": the classes are package-private, Bits is @lucene.experimental (Bits.java:24), and nobody runs a segment within 3,967 documents of 2^31, so this is an unsupported corner.

Why it fails: the observable contract is the public BooleanQuery semantics, not the internal class; the trigger is a legal index built with defaults, inside the only documented limit; and the code points to an intended cap (the otherwise no-op Math.min, the long at :61, the unsignedMin siblings; an inference). The argument limits impact, not correctness. The reviewers from another model family rated the intended-behaviour case weak; the independent reproducer, the devil's advocate and the adjudication reached the same conclusion without giving a rating.

Two fixes were built and validated with gradle in a scratch worktree at 645d4fe14a20 (JDK 25, -Ptests.seed=DEADBEEF); the third option was not built.

ReqExclBulkScorer.java:125, one file, +2/-1 (the line and the import of org.apache.lucene.util.MathUtil):

    public void applyMask(FixedBitSet bitSet, int offset) {
      int bitSetEnd = MathUtil.unsignedMin(DocIdSetIterator.NO_MORE_DOCS, offset + bitSet.length());

Trade-offs

• A wrapped sum is a large unsigned value (2^31 or more), so the unsigned minimum with NO_MORE_DOCS (2^31 - 1) is NO_MORE_DOCS, and to becomes the window end. Unchanged when the sum fits.
• The idiom #14750 introduced for this case, written like BitSetDocIdStream.java:34. The line is exactly 100 columns and passes the formatter unwrapped. One unsigned compare instead of a signed one.

What the checks validated

• The minimal test passes; it fails without the fix in the same gradle setup.
• The nine closest suites pass, 145 tests: TestReqExclBulkScorer 5, TestBooleanScorer 20, TestBooleanScorerSupplier 16, TestDenseConjunctionBulkScorer 26, TestConstantScoreBulkScorer 6, TestBooleanQuery 30, TestBoolean2 10, TestBooleanRewrites 31, the new test 1. :lucene:core:checkGoogleJavaFormat passes.
• :lucene:core:test --tests "org.apache.lucene.search.*": 215 classes, 2,340 tests, 49 skipped, 0 failures.

Same line, +2/-1, no import:

      int bitSetEnd =
          (int) Math.min(DocIdSetIterator.NO_MORE_DOCS, (long) offset + bitSet.length());

Trade-offs

Mirrors the outer window computation in the same class. Written on one line it is 101 columns and fails checkGoogleJavaFormat, so it must be wrapped as shown.

What the checks validated

• The minimal test and TestReqExclBulkScorer pass (6 tests), and checkGoogleJavaFormat passes with the wrapped form. Fix B was not run against the whole org.apache.lucene.search package.
• Earlier hunt runs of the one-line form, all passing: the finder's 4 tests and TestReqExclBulkScorer 5 of 5, the independent reproducer's 9, both reviewers' own tests, both history witnesses at c5fa32ce49f and the unit witness at the branch_10_6 head 2763db11b0a.

Make ConstantScoreBulkScorer and DenseConjunctionBulkScorer avoid sets that reach past 2^31.

Trade-offs

Fixes only those two callers and leaves WindowBits breaking the Bits#applyMask contract for any other caller (MaxScoreBulkScorer.java:246, BooleanScorer.java:149).

Method: semi-formal (the hunt's hunt unit on bit sets, live docs and acceptDocs, main ea57360912ed, 2026-10-25).

• Lead. Reading the Bits#applyMask implementations against the contract: WindowBits adds offset + bitSet.length() in int. (The intended-behaviour checker later confirmed that the other implementations cannot overflow: FixedBitSet computes length() - offset, and DenseLiveDocs and SparseLiveDocs compute maxDoc - offset.)
• Z3. A 32-bit bit-vector model of the bounds, under the preconditions of a set of 1 to 4096 bits and 0 <= windowBase <= offset < windowEnd <= MAX_DOCS: O3 is a counterexample with the smallest failing offset 2,147,479,552 for a 4096-bit set; O3s proves that the bound to equals the exact min(windowEnd, offset + n) whenever offset + n <= Integer.MAX_VALUE; O3c proves the overflow case takes the bitSet.clear() branch although the window is not empty. The model does not cover the clear and andRange part of the method.
• Execution. A same-package unit test (the required clause on the last 100 doc IDs, controls 8192 docs lower pass) and a legal end-to-end run on one segment of IndexWriter.MAX_DOCS documents, both with -ea and -da. A sparse end-to-end run that takes the ReqExclScorer path passes, as the code predicts.