Document suggester: num x prefix paths overflows an int, so a ContextQuery across many contexts can silently return no suggestions

The document (NRT) suggester stores each ContextSuggestField suggestion in the segment's FST behind its context. A ContextQuery that names no context "suggest[s] across all contexts", so its automaton matches one FST prefix, a prefix path, per distinct context. To make sure every path can contribute, NRTSuggester.lookup asks its Util.TopNSearcher for up to num x prefixPaths.size() results, an upper bound by design (the collector stops at num), but computes it in int (NRTSuggester.java:142 on main 645d4fe14a20). With 100,000 contexts in one segment, suggest(query, 21474, true) returns the one distinct suggestion and suggest(query, 21475, true) returns none, with no error: the product wraps to -2,147,467,296 and while (results.size() < topN) (Util.java:310) never runs. With 10^6 contexts num 2147 returns 2147 suggestions and num 2148 none. A small positive wrap truncates instead (3000 contexts, num 1,431,656: 704 of 3000), and regex or fuzzy completion queries with many matching prefixes hit the same line. A negative wrap also removes the search queue's 5000-entry bound. Truncation since 5.3.0 (LUCENE-6459), empty lists since 5.4.0 (LUCENE-6858), through 10.5.2, 10.6.0 and main. Computing the product in long and saturating it at Integer.MAX_VALUE fixes it; the neighbouring queue-size product was already made long by #11923.

• Document (NRT) suggester: SuggestField / ContextSuggestField indexed with a completion postings format, queried with a CompletionQuery (PrefixCompletionQuery, RegexCompletionQuery, FuzzyCompletionQuery, ContextQuery) through SuggestIndexSearcher.suggest(query, num, skipDuplicates), which "Returns top n completion hits for query" (SuggestIndexSearcher.java:49) and runs one lookup per segment (:64-76).
• Contexts: ContextSuggestField prepends each context and the separator '\u001D' to the input (ContextSuggestField.java:49, :79-101). A ContextQuery with no context, or addAllContexts(), uses "any string, then the separator" (ContextQuery.java:228-233, concatenated with the inner automaton at :197-200); "When no context is added, the default behaviour is to suggest across all contexts" (:62-63). addContext(prefix, boost, false) matches every context with that prefix (:64-66).
• Prefix paths: FSTUtil.intersectPrefixPaths "Enumerates all minimal prefix paths in the automaton that also intersect the FST" (FSTUtil.java:48-52): one per distinct matching context, or one per matching prefix for regex and fuzzy completion queries.

1. NRTSuggester.lookup computes prefixPaths (NRTSuggester.java:131-132) and then final int topN = collector.getCountToCollect() * prefixPaths.size(); (:142). The comment above (:133-141, from LUCENE-6858) says the factor is there "to ensure search admissibility", that collectors "will early terminate as soon as enough suggestions have been collected", and that "This value is the maximum number of suggestions that can be collected".
2. topN goes straight into new Util.TopNSearcher<>(fst, topN, queueSize, ...) (:148-154), whose constructor does not check it (Util.java:193-206). search() loops while (results.size() < topN) (Util.java:310): for topN <= 0 it never runs, so the segment contributes nothing; a small positive wrap stops it after that many results. The lookup ignores the outcome ("search admissibility is not guaranteed", NRTSuggester.java:256-259).
3. The same wrapped value sizes the queue: getMaxTopNSearcherQueueSize(topN, ...) (:143-144) multiplies in long but from the wrapped int and returns min(5000, ...) (:292-301), here negative. The queue is pruned only when its size equals the depth (Util.java:215, :248-249), which never happens for a negative depth, so, by code reading, every prefix path stays queued instead of at most 5000.

• 100,000 contexts, skipDuplicates=true, one surface form: num 21474 -> 1 hit, num 21475 -> 0 (21,475 x 100,000 = 2,147,500,000, as an int -2,147,467,296). Without dedup: 5000 (the private queue cap) -> 0.
• 10^6 contexts, no dedup, match-all (this doc's probe on 645d4fe14a20) or addContext("store:", 1f, false) (the devil's advocate's run): num 2147 -> 2147, num 2148 -> 0. Each lookup takes about 2.4 s.
• 3000 contexts: num 715827 -> 3000, num 715828 -> 0, num 1,431,656 (wraps to 704) -> 704 of 3000. 1000 regex prefixes: num 2,147,484 -> 0 of 1000.
• First failing num for P paths: floor(Integer.MAX_VALUE / P) + 1 (2148 for 10^6, 21475 for 10^5, 214749 for 10^4). The int wraps modulo 2^32, so a large positive wrap is harmless: num 2,000,000 with 2500 paths returns all 2500.

• Per segment: the count is each segment's own. Two segments of 50,000 contexts: num 42949 -> 10000 hits, num 42950 -> 0. Segments whose own product does not wrap still contribute (one lookup per leaf into one shared collector, SuggestIndexSearcher.java:69-85), so a multi-segment index returns an empty list only when every segment with matches wraps to 0 or below; otherwise it silently lacks the wrapped segments' suggestions.
• skipDuplicates does not help; no deletions or filter are needed.
• Only results are dropped: the contexts, the filter and the live docs are applied as before, so nothing they exclude is returned.
• Side effect of a negative wrap: by code reading, every prefix path stays queued. At 10^6 contexts and a 512 MB heap, the num 2148 lookup ran out of memory (OutOfMemoryError) where num 2147 completed in 2.6 s, and with the saturating fix both lookups completed (one run each). With 3 GB, the whole suggest() call allocated about 2.1 GB at num 2148 against 1.85 GB at num 2147 (cumulative allocation; no per-phase breakdown was collected).

• Who is hit. Users of SuggestIndexSearcher.suggest with a ContextQuery across all contexts (no context, addAllContexts()) or across a shared non-exact context prefix, over many distinct contexts per segment; or with regex or fuzzy completion queries that match very many prefixes.
• Default or opt-in. The document suggester and its completion postings format are opt-in; within it, the trigger is ContextQuery's documented default.
• Effect. An empty or truncated suggestion list with no error. By code reading, a negative wrap also leaves the search queue unbounded; at 10^6 contexts and a 512 MB heap the wrapping lookup ran out of memory and the fixed one did not. Nothing the query, contexts, filter or live docs exclude is returned.
• Scale. num x (prefix paths in one segment) > 2^31. At the usual autocomplete num of 10 to 100 that is about 2 x 10^7 to 2 x 10^8 prefix paths in one segment, and a 10^6-path lookup already takes about 2.4 s. Queries over about 900 contexts are reported in practice (elasticsearch#119966, d2a-raudenaerde; its performance was fixed by Mayya Sharipova in #14169).
• Releases. Truncation from 5.3.0, empty lists from 5.4.0, through 10.5.2, 10.6.0 (released 2026-10-29; branch_10_6) and main.
• How likely: rare (registry likelihood rare, priority low).

# Lucene main 645d4fe14a20, assertions on (-ea), seed 5EED0999: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<2148> but was:<0>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:647)
       org.junit.Assert.assertEquals(Assert.java:633)
       org.apache.lucene.search.suggest.document.TestContextQueryManyContextsTopN.testAllContextsQueryOnOneMillionContexts(TestContextQueryManyContextsTopN.java:50)

• Contract. SuggestIndexSearcher.java:49: "Returns top n completion hits for query". ContextQuery.java:62-63: "When no context is added, the default behaviour is to suggest across all contexts". TopSuggestDocsCollector rejects only num <= 0 (TopSuggestDocsCollector.java:77-78); no javadoc, CHANGES or MIGRATE entry gives an upper limit.
• Design intent. The comment at NRTSuggester.java:133-141 (LUCENE-6858) calls the product the maximum number of suggestions that can be collected. Areek Zillur explained on LUCENE-6459 (#7518, 2015-05-26) that each prefix path gets n expansions and that the search "will early terminate", and on LUCENE-6858 (#7916) that the bigger topN is there "to ensure search admissibility in case of suggestions with multiple contexts". A negative bound that switches the search off contradicts their design.
• Overflow-safety was asked for here. Reviewing LUCENE-6339 (#7400, 2015-03-26), Michael McCandless asked whether the queue-size computation from the same num "could possibly overflow int? Maybe use long". Robert Muir's #11923 (2022, after Kevin Risden's error-prone run #11921) made that product long (NRTSuggester.java:294) and left :142 as it was.
• Tests. No upstream document-suggester test asserts large-num or overflow behaviour (the devil's advocate's grep of lucene/suggest/src/test).

The intended-behaviour checker built the strongest case (first raised by the finder's reviewer from another model family, OpenAI GPT-5.6, which itself rated it weak): the document suggester is @lucene.experimental; the class NOTE says the search can be "inadmissible due to over-pruning" (NRTSuggester.java:55-65); the queue is capped at MAX_TOP_N_QUEUE_SIZE = 5000 (:92), so a huge num is already approximate; the collector "Collects at most num completions" (TopSuggestDocsCollector.java:74); and a huge num is the application's business (SECURITY.md:38 leaves limits on "unbounded, unfiltered input" to the application; Michael McCandless called Integer.MAX_VALUE for search(Query, n) "a nonsense value" on LUCENE-2119, #3195).

Why it fails: the NOTE covers "too many deletions or using a very restrictive filter", and the repro has neither. The 5000 cap is private, and without deletions or a restrictive filter (the NOTE's conditions for over-pruning) it gives min(5000, available), never 0: with 10^6 contexts num 2147 returns exactly 2147 and num 2148 returns 0, both below the cap and below maxDoc. "At most num" does not license 0 when one fewer returns the full list. The threshold depends on a per-segment, data-dependent path count the caller cannot see. In the same LUCENE-2119 thread Michael McCandless also wrote "We should bounds check it", and IndexSearcher.searchAfter caps numHits at maxDoc (IndexSearcher.java:588, :597) instead of failing. Experimental allows API changes, not silent wrong results. Verdict: not intended (adjudication: confirmed, high confidence).

One fix was built and validated; two alternatives were considered and not built.

A change in NRTSuggester.lookup (1 file, +3/-1), the same as the finder's fix sketch and the independent reproducer's patch, split over two lines to stay within 100 columns. The product is meant as an upper bound that the collector undercuts anyway; the search can never return more than Integer.MAX_VALUE results, so saturating keeps that meaning exactly. The queue size then comes back to min(5000, ...), which also restores the queue bound.

// The product can exceed Integer.MAX_VALUE, so compute it in long and saturate.
final long maxTopN = (long) collector.getCountToCollect() * prefixPaths.size();
final int topN = (int) Math.min(maxTopN, Integer.MAX_VALUE);

Trade-offs

• Scope: saturation removes this overflow and restores the queue cap. It does not make the document suggester exhaustive in general: the over-pruning the class NOTE allows with deletions or a restrictive filter (NRTSuggester.java:55-65) and the private 5000-entry queue cap stay as they are.
• No change below the threshold: the value is identical there.
• With topN = Integer.MAX_VALUE, TopNSearcher's rejectCount + topN <= maxQueueDepth (Util.java:409) can itself overflow, but it only sets TopResults.isComplete, which NRTSuggester ignores (NRTSuggester.java:256-259); noted by the devil's advocate, not a blocker.
• Open PR #16847 edits the next statement, so the fix may need a trivial rebase.

What the checks validated

• Scratch worktree of 645d4fe14a20, gradle, OpenJDK 25: the repro fails on the stock tree and passes with the fix, with assertions on and off.
• With the fix and the repro test, the whole lucene/suggest module passes with assertions on and off: 32 suites (31 upstream + the test), 237 tests, 7 skipped, 0 failures; the 6 upstream suggest.document suites (58 tests) among them.
• :lucene:suggest:check -x test (checkGoogleJavaFormat, ecjLint, forbiddenApis) passes.
• Earlier, by the hunt: the finder's 4 tests and the independent reproducer's 8 pass with the same saturation; the 12 upstream suggest test classes (144 tests) pass with all of the hunt unit's fix sketches.
• Not run: nightly tests, a benchmark (one multiply per segment lookup).

Throw ArithmeticException instead of returning nothing.

Trade-offs

Honest, but it turns a legitimate request (the javadoc's default across all contexts) into an exception, where the saturating fix answers it correctly.

Cap or reject large num in TopSuggestDocsCollector or SuggestIndexSearcher, as IndexSearcher caps numHits at maxDoc.

Trade-offs

Does not fix it on its own: the overflow depends on the per-segment prefix-path count, and with 10^6 contexts num 2148 is far below maxDoc.

Method: non-formal first signal, then a small formal model (the hunt's hunt unit for suggester num sizes, 2026-10-28, main a9779ef3c193).

• Lead. A sweep over every int product of a suggest num found NRTSuggester.java:142.
• Model. A Z3 32-bit bit-vector model and an exhaustive enumeration over every int num gave the tight wrap-free bound per prefix-path count: 2148 for 10^6, 21475 for 10^5, 214749 for 10^4, 715828 for 3000, 2147484 for 1000.
• Execution. Each operating point was run on the stock main jars (3000 contexts, 1000 regex prefixes, 100,000 contexts), then reduced to a JUnit; this doc reduced it again to one method.