IndexSearcher#count on a two-term OR can return more than maxDoc when the searcher timeout fires

Since 9.10.0 (GITHUB#13036), IndexSearcher#count counts a pure OR of two TermQuery clauses as count(a) + count(b) - count(a AND b) when the reader has no deletions, both term counts are non-zero and one is under a tenth of the other. The two term counts come from index statistics and are always exact; the intersection has to be collected, and a searcher timeout (IndexSearcher#setTimeout) can cut that collection short.

Subtracting a cut-short intersection over-counts. With an already-expired timeout the 22-document repro returns 23 for 21 matching documents, above maxDoc 22, with timedOut() true; collecting the same query under the same timeout gives 0, and 9.9.2 returns 0 too. The result is never below the true count and too high by at most the intersection, which the shortcut's 0.1 ratio keeps under 10% of the true count. Callers that discard timed-out results are unaffected; a cached intersection hides the bug on later calls.

• Searcher timeout. IndexSearcher#setTimeout(QueryTimeout) applies to all searches of that searcher (no timeout by default). When it fires, collection stops early, the search keeps what it found so far and timedOut() becomes true; the flag is the field partialResult (IndexSearcher.java:89, :94, :613, :647-650, :845-858).
• count(Query). "Count how many documents match the given query. May be faster than counting number of hits by collecting all matches, as the number of hits is retrieved from the index statistics when possible." (IndexSearcher.java:490-494). Without deletions, the count of a TermQuery is the term's docFreq (TermQuery.java:255-260).
• The two-term shortcut (GITHUB#13036, 9.10.0). For a OR b made of exactly two TermQuery SHOULD clauses (minimumNumberShouldMatch <= 1), on a reader without deletions, when both term counts are non-zero and the smaller is under a tenth of the larger, count() returns count(a) + count(b) - count(a AND b) (inclusion-exclusion, IndexSearcher.java:506-518).

1. The shortcut's guard checks the query shape and reader.hasDeletions() == false (IndexSearcher.java:507-509), never the timeout.
2. count(a) and count(b) are docFreq values. TotalHitCountCollector#getLeafCollector reads them before any scorer exists (TotalHitCountCollector.java:47-52), so they are exact under any timeout.
3. count(a AND b) cannot be read from statistics: BooleanWeight's reqCount returns -1 for two clauses whose counts are in [1, numDocs) (BooleanWeight.java:225-227). So it is collected with a TotalHitCountCollectorManager (IndexSearcher.java:525-528) through searchLeaf, which wraps the scorer in a TimeLimitingBulkScorer (:846-847). That scorer checks shouldExit() before each window and throws (TimeLimitingBulkScorer.java:80-81); searchLeaf catches it, sets partialResult and keeps the count so far (IndexSearcher.java:856-857).
4. :518 subtracts that cut-short intersection, so the result is the true count plus the part of the intersection that was not counted. It is never below the true count. It equals the true count exactly when the whole intersection was counted before the timeout fired (always, if the two terms share no document: executed, 23 for 23 matching documents with timedOut() true). Otherwise it is too high by at most the intersection, which the 0.1 ratio keeps under 10% of the true count.

• Repro: 22 documents, a in 21, b in 2 (both also have a), already-expired timeout: count() = 21 + 2 - 0 = 23 > maxDoc 22 (true count 21), timedOut() true. Collecting the same query under the same timeout gives 0; 9.9.2 gives 0.
• Timeout firing later (single thread): on 2,000 documents (a in 1,960, b in 100, 80 in both, true count 1,980), a timeout that lets its first n checks pass, n = 0..5: count() = 2060, 2056, 2050, 2040, 2027, 2006; collecting gives 0, 99, 248, 471, 805, 1305; the intersection was cut to 0, 4, 10, 20, 33, 54 of 80. At n = 6 the search completes and both give 1980. With the fix, count() equals the collected value at every n.
• Same 23 for the OR under BoostQuery or ConstantScoreQuery, for the classic QueryParser's parse of a b, and with the stock QueryTimeoutImpl and a passed deadline.
• Bound (executed): 2,247 over-counts among 7,398 timed count() calls (4 runs of 80 random indexes each; 3 seeds, one of them run with assertions on and off, so 1,690 over-counts in 5,492 distinct calls), every one with timedOut() true and an excess under 10% (largest 7.9%; a constructed ratio of 0.099 gives 1099 for 1000), none on an index with deletions. From code reading only: the sum is int arithmetic, so near the 2^31-document limit it could wrap negative instead.

• Who is hit. Applications that set IndexSearcher#setTimeout (no timeout by default, IndexSearcher.java:89) and use the value of a timed-out count(), for example as "at least N results", for a query of exactly two TermQuery SHOULD clauses (plain, or under BoostQuery or ConstantScoreQuery) whose document counts are both non-zero and differ more than tenfold, where the larger term is not in every document, on a reader without deletions. A two-word user query parsed by the classic QueryParser with its default OR operator (QueryParserBase.java:78-81) has that shape when each word is one term (executed: 23).
• When. The timeout fires while the intersection is collected, or has already expired when count() starts, for example when one searcher and one deadline serve several calls and earlier calls used the time.
• Who is not. Callers that discard or retry a result once timedOut() is true (it is true in every over-count; the flag is sticky and searcher-wide, so a true flag says that some search on this searcher timed out, not that this count() was cut short, IndexSearcher.java:647-650); readers with any deletion (the shortcut is off); queries with a third clause, a FILTER, MUST or MUST_NOT clause, minimumNumberShouldMatch > 1 or a non-term clause; term counts within 10x of each other.
• A cached intersection hides it, on later calls. A cached intersection is counted exactly. On main the default query cache is off (GITHUB#14187, 11.0.0). In 9.x and 10.x releases the default LRUQueryCache caches only on segments with at least 10,000 documents that also hold more than half of the index's average documents per segment, skips clauses that cost much more than the top-level query, and caches a BooleanQuery only after a few uses: with that cache installed on a 20,000-document segment, the first 4 timed-out counts gave 19200 (true 18200), later ones 18200. The call that fills the cache is not hidden: the cache is filled from the unwrapped scorer while the timeout still applies. Once the intersection is cached, by any earlier call, timed or not, later timed calls are exact (executed: after an untimed count() on a shared cache, the first timed call returned the exact 21 with timedOut() false).
• Effect. One number, too high by under 10% of the true count, possibly above maxDoc, on a result flagged as timed out. No documents are returned, nothing extra matches, nothing is cached wrong or written.
• How likely. Rare (registry): each condition is ordinary, together they are narrow, and the flag is set.

The test indexes 22 documents into a ByteBuffersDirectory with the default IndexWriterConfig: term a in docs 0-20, term b in docs 0-1, doc 21 with neither. So the ratio 2/21 is under 0.1, a is not in every document (otherwise the intersection would be counted exactly from statistics) and maxDoc is 22, the smallest index that can exceed maxDoc this way. It asserts only that the timed-out count() is at most maxDoc, the bound no reading of the contract can break; the message also gives the true count.

setQueryCache(null) mirrors main's default (no query cache) and keeps the test independent of caching. It is not required: with LuceneTestCase's randomly caching default cache left on, the test still fails (40 of 40 iterations with one seed, 20 of 20 with each of two more, and 30 of 30 with a fourth), because a query cache is filled from the unwrapped scorer and can hide the bug only on later calls. Dropping the line is fine.

Nothing in the test uses random(); it also failed 10 of 10 times with seed 5EED1234. It compiles unchanged against 9.3.0 and later; 9.2.0 has no setTimeout.

# gradle, stock main 645d4fe14a20, seed DEADBEEF (the same with -Ptests.asserts=false)
TestTimedOutCountTwoTermDisjunction > testTimedOutCountExceedsMaxDoc FAILED
    java.lang.AssertionError: expected a timed-out count() <= maxDoc 22 (21 docs match), got 23
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:E7A55C79C5E0BE33]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.search.TestTimedOutCountTwoTermDisjunction.testTimedOutCountExceedsMaxDoc(TestTimedOutCountTwoTermDisjunction.java:53)

1 test completed, 1 failed

# value probe on the same index and query (not the repro), main 645d4fe14a20
stock:  PROBE A EXPIRED TRACE depth=1 count(f:a)=21 timedOut()=false
stock:  PROBE A EXPIRED TRACE depth=1 count(f:b)=2 timedOut()=false
stock:  PROBE A EXPIRED TRACE depth=1 count(+f:a +f:b)=0 timedOut()=true
stock:  PROBE A EXPIRED RESULT count(f:a f:b)=23 timedOut()=true shouldExitCalls=1 maxDoc=22
stock:  PROBE A EXPIRED COLLECT TotalHitCountCollectorManager(f:a f:b)=0 timedOut()=true
fix A:  PROBE A EXPIRED RESULT count(f:a f:b)=0 timedOut()=true shouldExitCalls=1 maxDoc=22

• count() counts matching documents (IndexSearcher.java:490-494). A value above maxDoc cannot be such a count under any reading.
• Timed-out results are partial results. The flag behind timedOut() ("Returns true if any search hit the timeout", :647-650) is the field partialResult (:94). The timeout design issue #11188 (LUCENE-10151) says: 'If the search "times out", partial results would be available.' In a review comment on #927 (2022-06-01), jpountz proposed the design that shipped: the timeout "applies to all search/count methods", the methods "never propagate the exception, otherwise we're preventing users to retrieve partial results", and the flag lets users know "that some matches were skipped".
• Lucene's own tests treat timed-out values as partial. For counts, BaseExplicitVectorSimilarityQueryTestCase.java:518 expects count() == 0 under setTimeout(() -> true) ("Expect no results with the timeout") and :524 expects 0 < count < numDocs ("Expect partial results"); BaseVectorSimilarityQueryTestCase.java:637, :643 do the same. For hits, TestTimeLimitingBulkScorer.java:62: "Partial result and is aborted is true". These test particular queries, not a general javadoc contract, but they show what a timeout is expected to produce.
• The other paths we ran, and older releases, stay at or below the true count. Under the same expired timeout, TotalHitCountCollectorManager and a three-clause OR give 0; 9.3.0 to 9.9.2 pass the repro (value 0 probed on 9.3.0 and 9.9.2).
• Never tested with a firing timeout. #13036's test uses a searcher without a timeout, an IndexSearcher subclass that counts its count() calls (TestBooleanQuery.java:961-1097, the subclass at :991-998); the test framework only installs a never-firing timeout, setTimeout(() -> false) (LuceneTestCaseParent.java:2690); #13036's body, comments and reviews and #12644 never mention timeouts.

The strongest case for "works as designed" (from the cross-model reviews, the intended-behaviour checker and the adjudication): no javadoc defines the value of a timed-out count(); timedOut() is sticky and searcher-wide, so a careful caller discards every number once it is true; and timed-out counts follow no single rule anyway, because without deletions count(TermQuery) returns the exact docFreq without consulting the timeout.

Why it fails: an exact count is a valid partial count, a count above maxDoc is not; the design record, the field name and Lucene's own tests treat timed-out values as partial results that callers may use; count() presents itself as a faster way to get what collecting gives, and collecting the same query stays at or below the true count; and 9.9.2 returned 0 here. These points lower the impact (flag set, excess under 10%); none makes the value intended. Declaring timed-out counts unspecified would be a contract change that nothing in the code or tests states today. Verdict: a defect.

One fix was built and validated with gradle on 645d4fe14a20; the alternative comes from the study's notes and code reading. The defect is the value above the true count; which fallback a timed searcher gets is the maintainers' choice.

Add queryTimeout == null to the shortcut's guard in IndexSearcher#count (IndexSearcher.java:507-509): one condition plus a 2-line comment. A searcher with a timeout then takes the ordinary count path (BooleanWeight#count where statistics suffice, else collecting the OR), which under a timeout gives a partial count (0 in the repro) like the other paths; searchers without a timeout keep the GITHUB#13036 speed-up unchanged.

      // Check if two clause disjunction optimization applies
+      // Inclusion-exclusion needs an exact intersection count: with a timeout, a partial
+      // intersection count would make the result exceed the true count.
       if (innerQuery instanceof BooleanQuery booleanQuery
           && this.reader.hasDeletions() == false
+          && queryTimeout == null
           && booleanQuery.isTwoClausePureDisjunctionWithTerms()) {

Trade-offs

A searcher with any timeout, even one that never fires, loses the shortcut and collects the union instead of only the small intersection. It is a containment fix; whether it is the preferred design is the maintainers' call.

What the checks validated

• Built in a fresh scratch worktree of 645d4fe14a20 with gradle (removed after the runs). Stock, the repro fails with assertions on and off (23 > maxDoc 22).
• With A, the repro plus TestBooleanQuery (30 tests, including the shortcut's own testTwoClauseTermDisjunctionCountOptimization), TestTimeLimitingBulkScorer (2), TestIndexSearcher (11) and TestFloatVectorSimilarityQuery / TestByteVectorSimilarityQuery (18 and 18, whose testTimeout checks timed-out count() values): 6 classes, 80 tests, 0 failures, 3 skipped, with assertions on and with -Ptests.asserts=false; :lucene:core:checkGoogleJavaFormat passes with the fix and the repro file in place.
• A value probe on the same index shows the fixed timed-out count: 0 with an expired timeout, and on 2,000 documents exactly the collected partial count at every timeout point (0, 99, 248, 471, 805, 1305).
• The same validation ran earlier the same day in another scratch worktree and in the independent fact check, with the same counts; the executed cross-model review's own test also passes with the guard.

Count the intersection as today; if that count timed out, collect the OR instead, or return max(count(a), count(b)): both term counts are exact from index statistics, and their maximum is a lower bound of the union, so it never exceeds the true count (code reading; the shortcut already returns this maximum when one term count is 0, IndexSearcher.java:511-514).

Trade-offs

Keeps the speed-up for timed searchers whose count completes. It needs a per-call "this count timed out" signal: partialResult is one sticky flag for the whole searcher ("Returns true if any search hit the timeout", :647-650) and may already be true from an earlier search, so it is more code than A.

Method: semi-formal (bounded-exhaustive translation validation on the real classes, then an SMT model).

• A finder ran every search of a grid (69 query shapes x 9 collectors x 4 slicing modes x 3 reader modes on 4 index shapes) with a QueryTimeout that fires from its n-th shouldExit() call on, for every n below the call count of the full search: 1,228,664 searches, each compared with a reference written from the javadoc.
• Its count upper-bound and count-monotonicity checks fired only for IndexSearcher#count on the skewed two-term SHOULD disjunctions (also under BoostQuery) on indexes without deletions, in every slicing mode.
• A Z3 bit-vector model of the count path showed the untimed shortcut exact (UNSAT) and an over-count with a truncated intersection reachable (SAT); with the guard, the lower bound holds (UNSAT).
• The case was minimised to a deterministic JUnit on the stock jars, later reduced to the 22-document test.