The document suggester returns too few or worse suggestions when a segment has only a few deleted documents

The document suggester (SuggestField or ContextSuggestField with a completion postings format, queried through SuggestIndexSearcher.suggest) searches each segment's FST with a bounded queue of candidate paths and rejects a completion of a deleted document only when its path completes. NRTSuggester.getMaxTopNSearcherQueueSize therefore enlarges the queue "to account for the filtered out suggestions", as (long) (k / liveDocsRatio) with k = topN x analyzed paths per entry; the cast rounds down, so for any segment with liveDocsRatio > k/(k+1) (under 50% deleted for n = 1, under 9.1% for n = 10, one path per entry) the queue is exactly k again, with no spare slot. A deleted completion in one of the segment's top slots is then dropped and nothing replaces it: with abc_0, the best of abc_0..abc_9, deleted, suggest("abc_", 1) returns [] instead of [abc_1], and after updateDocument lowers abc_0's weight from 100 to 1 it returns abc_0/1 instead of abc_1/99. No error is raised. The line is the same in every release since the document suggester appeared, 5.1.0 (2015), through 10.5.2, and the bug reproduces on the 13 releases run and on main. Rounding up fixes every tested case in which one deleted completion takes a result slot and passes the suggest module's 241 tests with assertions on and off; it covers one deleted completion per segment, so a deleted document with two top completions still needs a re-search while the result is incomplete.

• Document suggester: SuggestField / ContextSuggestField values indexed with a completion postings format (for example Completion104PostingsFormat) and looked up with SuggestIndexSearcher.suggest(query, n, skipDuplicates). Each segment holds its completions in an FST; NRTSuggester.lookup searches it.
• Queue: Util.TopNSearcher keeps at most maxQueueDepth candidate paths. Once full, a path that does not beat the worst one is dropped (Util.java:215-236), and an add beyond the limit evicts the worst (:246-250).
• Rejection: when a path completes, acceptResult checks the document against the live docs (NRTSuggester.java:205-209, CompletionScorer.java:89-91). A deleted document's completion is rejected and only counted (Util.java:394-398).

1. lookup computes liveDocsRatio = numDocs / maxDoc (NRTSuggester.java:126-127, :304-306) and topN = n * prefixPaths.size() (:142), and sizes the queue with getMaxTopNSearcherQueueSize (:143-144).
2. That method computes k = topN * maxAnalyzedPathsPerOutput (:294) and then maxQueueSize = (long) (maxQueueSize / liveDocsRatio); (:297). The cast rounds down: (long) (k / r) == k whenever r > k / (k + 1). Only a filter adds more (numDocs / 2, :298-300); the cap is 5000 (:92, :301).
3. With a queue of exactly k, the alternatives were already pruned while addStartPaths (Util.java:264-292) seeded the queue: each arc after the best one is added and evicted again (:246-250). A rejected completion leaves its slot empty; the search ends (when maxQueueDepth == topN it also skips the queue for the last result, Util.java:340-343, but removing that shortcut does not fix the bug).
4. search() reports the result as incomplete (isComplete = rejectCount + topN <= maxQueueDepth, Util.java:409), and lookup ignores it (NRTSuggester.java:254-259). In the merged top n the slot stays empty or goes to a lower-ranked hit of another segment.

The zero-slack range: under 50% deleted for k = 1, under 16.7% for k = 5, under 9.1% for k = 10. Which deleted completion costs a slot depends on how keys share prefixes: with keys whose top entries each have their own arc (abc_0..abc_9; the independent reproduction's s_0..s_{N-1}) a deletion anywhere in the top n was lost in every zero-slack case of a 370-case sweep; with item00..item99 a deletion in the last slot of num=5 was lost, while one at rank 3 was handled.

• Who is hit. Users of the document suggester, an opt-in per field (a completion postings format), with PrefixCompletionQuery, FuzzyCompletionQuery or ContextQuery; all three missed hits in the finder's harness. RegexCompletionQuery goes through the same lookup (by reading; not run). By code reading, the Elasticsearch and OpenSearch completion suggesters call it with the segment's live docs; nothing was run downstream.
• Ordinary operations. One deleteDocuments, or one updateDocument, the usual way to change a suggestion's weight, which leaves the old copy deleted in its segment. No other setting is needed, and a large segment does not protect: one deletion leaves no slack in any segment of at least k + 2 documents (3 for num = 1), so 1 deletion in 1,000 documents is enough.
• Silent and deterministic. No exception or warning; -ea and -da behave the same. The result is short, or a lower-ranked suggestion takes the slot (weight 1 instead of 99 in the update case).
• Wide range. Zero slack for any segment under 50% deleted at n = 1, under 16.7% at n = 5, under 9.1% at n = 10 (one prefix path, one analyzed path per entry).
• Not every lookup. A miss needs a deleted completion in one of the segment's top slots for the queried prefix, and the slot must matter in the merged top n. In the finder's harness (3,000 random indexes of at most 6 documents, about a third of them with one deleted document; 4,680,000 lookups over all of them) 798 lookups missed a hit and 96 returned a lower-scored hit from another segment (the harness labels these 96 "unexplained"; all go away with only the Math.ceil change); a run without deletions had neither kind. Merges reclaim deletions over time.
• Masked by filters. With a BitsProducer filter the queue gets numDocs / 2 extra slots; in the probe's filter cases that masked the rounding (the same results with and without the fix), though a restrictive filter can still over-prune (6 of 176 filter lookups short both ways).
• How common in production was not measured.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<[abc_1]> but was:<[]>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.search.suggest.document.TestNRTSuggesterOneDeletion.testDeletedTopCompletionIsReplaced(TestNRTSuggesterOneDeletion.java:67)

• The method's own promise. NRTSuggester.java:281-284: "Since suggestion entries can be rejected if they belong to a deleted document, the length of the TopNSearcher queue has to be increased by some factor, to account for the filtered out suggestions."
• The public contract. SuggestIndexSearcher.suggest: "Returns top <code>n</code> completion hits for <code>query</code>" (SuggestIndexSearcher.java:49).
• The caveat covers the opposite case. Class NOTE (NRTSuggester.java:58-60): "having too many deletions or using a very restrictive filter can make the search inadmissible due to over-pruning of potential paths". One deletion in 10 or in 1,000 triggers this bug; 5 of 10 deleted does not.
• Incomplete by the searcher's own test. isComplete = rejectCount + topN <= maxQueueDepth (Util.java:409): a queue of exactly topN has no room for one rejection.
• Sibling code sizes for rejections. FreeTextSuggester.java:605-608: "Must do num+seen.size() for queue depth because we may reject up to seen.size() paths in acceptResult()".
• Precedent. LUCENE-4481 / #5547 (2012), a bounded TopNSearcher queue with rejected results in another suggester, was fixed as a bug.
• Why tests missed it. TestSuggestField.testNRTDeletedDocFiltering deletes every other document and asks for all live ones; testSuggestOnAllDeletedDocuments and testSuggestOnMostlyDeletedDocuments delete all or all but one. None is in the zero-slack range.
• History. The LUCENE-6339 issue thread discussed the filter heuristic, a long overflow and nearly-all-deleted tests, not rounding or few deletions (its patch attachments were not read). No CHANGES or MIGRATE entry mentions it.

The case for "intended" (the cross-model reviews rated it moderate; the independent reproduction, the intended-behaviour check and the adjudication examined it): the class NOTE says the search can over-prune; the javadoc calls the sizing "Simple heuristics" and says "the search can still lead to over-pruning"; lookup deliberately does not assert isComplete ("search admissibility is not guaranteed"); the package is @lucene.experimental; the collector "Collects at most <code>num</code> completions".

Why it fails:

• The caveat names too many deletions or a very restrictive filter; the trigger is a single deletion, and spare room appears only once about half the segment is deleted (num = 1: 5 of 10 works, 4 of 10 still fails).
• The heuristic is not imperfect here, it is switched off: the documented increase is zero.
• @lucene.experimental means "This API is experimental and might change in incompatible ways in the next release"; it says nothing about wrong results. "At most num" is an upper bound, not permission to return fewer when more exist.

What a maintainer could still raise: best-effort admissibility is documented and the javadoc's caveat ("the search can still lead to over-pruning") is unconditional, so the change may read as an improvement to a heuristic; the 5000 cap bounds the work by design; and the one-line fix is partial: a deleted document with several top completions still empties the lookup, which is defensible as best effort. The updateDocument case (a worse hit, not just a short list) is the hardest to defend.

Option A was validated with gradle in scratch worktrees at ea57360912ed (JDK 25.0.3), with assertions off and with -Ptests.asserts=true, and through the repro runner with -ea and -da; options B and C were not run.

Change the cast in getMaxTopNSearcherQueueSize to Math.ceil. A segment with any deletion then gets at least one spare slot (while the 5000 cap does not bind): ceil(1 / 0.9) = 2 keeps abc_0 and abc_1, abc_0 is rejected and abc_1 is returned. The same code change as the finder's patch; the comment was reworded to state the rule with k.

// NRTSuggester.getMaxTopNSearcherQueueSize, line 297
-    maxQueueSize = (long) (maxQueueSize / liveDocsRatio);
+    // round up: truncating returns maxQueueSize unchanged whenever liveDocsRatio >
+    // maxQueueSize / (maxQueueSize + 1), leaving no room for a rejected (deleted) completion
+    maxQueueSize = (long) Math.ceil(maxQueueSize / liveDocsRatio);

Trade-offs

• Partial. One spare slot covers one rejected completion. A deleted document with two completions that both outrank every live one still empties a num=1 lookup (TestSuggestFewDeletionsLimit: [] instead of [abc_1/99], on stock and with the fix). The finder's harness with only this change still finds 60 of 4,680,000 lookups that miss, all where the deleted document has two or more matching completions.
• Cost. At most one extra queue entry per segment lookup when the segment has deletions; nothing changes without deletions (k / 1.0 is exact). The 5000 cap stays. Not benchmarked.
• Behaviour. Only lookups that were short or wrong change; no index format change.
• Coverage. The JUnit tests use one prefix path and one analyzed path per entry; several prefix paths (fuzzy queries) were exercised only by the randomized harness, and several analyzed paths per entry (graph analyzers, synonyms) by no test.

What the checks validated

• The repro: 4 of 5 fail on stock, 5 of 5 pass with the fix (gradle with assertions off and with -Ptests.asserts=true; the repro runner with -ea and -da).
• :lucene:suggest:test --tests 'org.apache.lucene.search.suggest.document.*': 7 suites, 63 tests (58 upstream + 5 new), 0 failed, through gradle with assertions off (seeds 1A2B3C4D and 77AA77AA) and through the repro runner with -ea (seed 5EED1234).
• All of :lucene:suggest:test: 241 tests (236 upstream + 5 new), 7 skipped, 0 failed, seed 1A2B3C4D, with assertions off and with -Ptests.asserts=true.
• :lucene:suggest:checkGoogleJavaFormat passes with the fix and the new test (re-run after the comment rewording).
• Earlier stages: the finder's, the independent reproduction's (370-case sweep: 0 misses), the cross-model review's and the intended-behaviour check's tests pass with it; 5.1.0 with the line changed passes the finder's scenario.

When search() reports isComplete == false, repeat with a larger queue (for example doubled), up to the 5000 cap and a bounded number of retries. LUCENE-4481 discussed the same idea for another suggester. Not implemented or run.

Trade-offs

acceptResult collects hits and records surface forms for skipDuplicates as side effects, so a retry must buffer a segment's hits until its search is complete, or reset that state; otherwise hits are collected twice. A heavily deleted or filtered segment can cost several searches, bounded by the cap and the retry limit. By the searcher's own completeness test it would also cover A's limit case (by reading); beyond the cap the documented over-pruning remains.

Use k + (maxDoc - numDocs), capped, instead of dividing by the ratio. Not run.

Trade-offs

Covers several deleted documents among the top results, but in A's limit case (one deleted document with two top completions) it also gives a queue of 2 and would miss the same way (by reading). Gives large queues to segments with many deletions.

Method: randomized bounded translation validation (the hunt's semi-formal tier: the harness's mismatch gave the first signal; no model checker, SMT solver or prover was involved).

• The finder's harness (NrtTV.java) compares PrefixCompletionQuery, FuzzyCompletionQuery and ContextQuery over SuggestField and ContextSuggestField, with several segments, deletions and skipDuplicates on and off, against an independent reference of the documented top-n semantics, over random indexes of at most 6 documents. Its first run reported an unexplained missing live completion in a 3-document segment with one deletion; tracing it led to the truncating line.
• At scale, 3,000 random indexes, about a third of them with one deleted document (4,680,000 lookups over all of them), gave 798 missing-hit mismatches plus 96 where a lower-scored hit from another segment took the slot, and 0 such mismatches in a run without deletions. The harness samples randomly and is not exhaustive.
• The finder wrote a public-API JUnit (fails 2 of 3 with -ea and -da). Claude verifiers wrote their own: the independent reproduction (outside the suggest package; 1 of 1,000 deleted, updateDocument, a 370-case sweep that misses exactly where the queue equals n) and an updateDocument case, num=5 in 100 documents. Reviews by an independent reviewer from another model family (OpenAI GPT-5.6) read the code only; a separate run re-ran the finder's test for each and ran a further test for the second. An adjudication re-ran the tests with fresh seeds.