BlendedInfixSuggester: a repeated suggestion evicts a different one when the result set is full

BlendedInfixSuggester re-ranks the hits it fetched by a blended weight and keeps the best num in a sorted set that also merges identical suggestions (same text, same blended weight, same or no payload). When the set is full and a better hit arrives, boundedTreeAdd removes the lowest entry before it inserts the new one (BlendedInfixSuggester.java:294-306); if the new hit is a copy of a suggestion already in the set, the insert does nothing, so a different, already-collected suggestion is lost. With the default constructor and a DocumentDictionary over {the lake 1000, lake 950, lake 950, my lake 920}, lookup("lake", false, 2) returns [lake/950, my lake/828] instead of [lake/950, the lake/900], the first two of the num=3 answer; without my lake it returns [lake/950]. A dictionary with no weight field behaves the same. Nothing throws and the index is unchanged. Every release from 4.7.0 (2014, the first with this class) to 10.6.0 and main is affected (19 releases and main run, 10.6.0 by reading), and a one-line guard that skips a duplicate before evicting fixes it.

• Blending: BlendedInfixSuggester fetches num * numFactor matches (default numFactor 10) in raw-weight order, then scores each one by where the query matched: a suggestion that starts with the key keeps its weight; otherwise POSITION_LINEAR (the default) multiplies it by 1 - 0.1 * position of the first matching word (BlendedInfixSuggester.java:72-84, 259-264). Weight 0 becomes 1, and weights below 10 are multiplied by 10 (:265-270). The blended value is cut to a long (:271).
• Result set: a TreeSet ordered by LookUpComparator, bounded at the num the caller asked for (:224-227, :281). The comparator orders on the blended value, then the text, then the payload when there is one, and returns 0 when all are equal (:383-407); TreeSet.add ignores an element that compares 0 to one it holds. That is how identical suggestions are merged, which upstream tests on purpose (testBlendedInfixSuggesterDedupsOnWeightTitleAndPayload, LUCENE-6680).

boundedTreeAdd (:294-306):

if (results.size() >= num) {
  if (results.first().value < result.value) {
    results.pollFirst();      // the lowest entry is removed first
  } else {
    return;
  }
}
results.add(result);          // ... and this add does nothing for a duplicate

Step by step for lookup("lake", false, 2) over {the lake 1000, lake 950, lake 950, my lake 920} (hits in raw-weight order, set bounded at 2):

Result [lake/950, my lake/828]; the num=3 lookup returns [lake/950, the lake/900, my lake/828], so the num=2 answer is not its first two. Without the fourth document the set ends at {lake/950}.

• Two entries that compare equal: the same text, the same blended long value and equal or absent payloads. Identical entries do it, and so does the same text with raw weights that blend to the same value (1001 and 1000 at word 1 both give 900). Entries with unique payloads are told apart and are not affected.
• The later copy must blend above the lowest collected value while the set is full: an earlier, higher-weighted match was blended down because the query matched a later word of it. With the stock CUSTOM blender (coefficient 1, :373-375) only the x10 scaling of weights with |w| < 10 (:268-270, #11193) can reorder hits that way; a CUSTOM subclass that overrides calculateCoefficient, as CUSTOM's javadoc asks (:74), with a position coefficient is hit like the position blenders (executed: [lake/950, my lake/828] for the lake example with num=2).
• The copy must arrive after the set is full. Hits arrive in raw-weight order and, for equal raw weights, in the suggester index's document order (AnalyzingInfixSuggester.java:166, 739), so with tied weights the input order matters: the no-weight-field example reordered to {the apple, the apple, the big apple, a big red apple} returns the right [the apple/9, the big apple/8] (executed). A rebuild from input in another order can change whether, and which, suggestion is lost (reading). The lake example has no tie apart from the identical pair.
• Once the set holds num entries an eviction is followed by a refill from the next distinct hit, so at most one of the correct top num of the fetched hits is missing: with at least num distinct suggestions fetched, the list has num or num-1 entries, and num=1 is never affected (code reading and two small models of the method, not a Lucene run).

Default constructor, StandardAnalyzer without stop words, DocumentDictionary, on main, 10.5.2 and 9.12.3 with and without assertions: {the lake 1000, lake 950, lake 950, my lake 920} gives [lake/950, my lake/828] for num=2; without my lake, [lake/950]; with no weight field, {the apple, the big apple, the apple, a big red apple} gives [the apple/9, a big red apple/7] instead of [the apple/9, the big apple/8] for num=2 (every weight 0 becomes 10, so the blended values are 9, 8 and 7). Without the repeated entry the answer is right.

• Who. Users of BlendedInfixSuggester (@lucene.experimental, BlendedInfixSuggester.java:54). It is opt-in, but its default constructor and settings are affected, and so are all three position blenders (POSITION_LINEAR, POSITION_RECIPROCAL, POSITION_EXPONENTIAL_RECIPROCAL; the last one only in the finder's exhaustive and random scopes). The stock CUSTOM blender (no calculateCoefficient override) is hit only through the x10 scaling of weights with |w| < 10; a CUSTOM subclass with a position coefficient is hit like the position blenders (executed).
• What it takes. A suggestion text that repeats with weights that blend to the same value and with equal or no payloads: the same weight always does, and nearby weights can too (1001 and 1000 both give 900 at word 1). Repeats with equal weights are the ordinary result of a DocumentDictionary over a field whose values repeat across documents (product names, titles, places, tags), with a repeating weight field or with none: "If the weight field is not defined, the value of the weight is 0" (DocumentDictionary.java:41-42). Plus a lookup for which a higher-weighted match is blended down below the repeated one (the normal case for infix matches such as the lake for lake), with the copy arriving after the set is full.
• Scale. None: three entries suffice. Each affected lookup returns at most one suggestion too few (num-1), or a weaker suggestion in place of a stronger one it fetched. It reproduced in every recorded run (the same 3 of 4 tests failed in 20 randomized repetitions and in 12 other runs with their own root seeds), and nothing is logged or thrown; the index is not changed. With tied raw weights the input order decides whether, and which, suggestion is lost.
• Likelihood: plausible. Short prefixes with more matches than num are the normal autocomplete case, and one missing or substituted entry is easy to overlook, which fits the absence of any diagnosed report since 2014.
• Not affected: dictionaries in which no two entries share the text and the payload (or both lack one), for example entries with unique payloads; num=1; and lookups in which every copy arrives while the set still has room.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: expected:<[lake/950, [the lake/900]]> but was:<[lake/950, [my lake/828]]>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.search.suggest.analyzing.TestBlendedInfixDuplicateEviction.testDuplicateEvictsDistinctSuggestion(TestBlendedInfixDuplicateEviction.java:35)

• Contract. The class javadoc: the suggester "transforms the weight after search to take into account the position of the searched term into the indexed text ... it increases the number of elements searched and applies the ponderation after" (BlendedInfixSuggester.java:48-55); BlenderType documents the formulas, for example weight*(1 - 0.10*position) (:76). The bound is commented "we reduce the num to the one initially requested" (:226) and boundedTreeAdd is documented as "Add an element to the tree respecting a size limit" (:287-293): a bounded top-num collector.
• Tests. testRequiresMore (TestBlendedInfixSuggester.java:198) asserts top-num selection by blended weight inside the fetch window and exact sizes 2 and 3; testSuggesterCountForAllLookups (:340, from SOLR-7865) asserts size() == num on every lookup path. The dedup test (:278) looks up with num=10 and at most 2 distinct results (:465), so its set never fills. No test or javadoc describes a duplicate evicting another suggestion.
• History. Upstream fixed earlier losses or miscounts of BlendedInfix results as bugs: a LUCENE-5354 follow-up (20461c90103, 2014: a comparator that collapsed distinct results), LUCENE-6680 (#7738, "don't lose a suggestion that differs only in payload from another suggestion", 5.3.0) and SOLR-7865 (too many results). None changed boundedTreeAdd.
• Legal input. No contract forbids repeated entries (Dictionary, InputIterator, DocumentDictionary), and DocumentDictionary.java:41-42 documents weight 0 when the weight field is missing, which makes equal weights for repeated names the normal case.
• The fix keeps the intended part. With the guard, identical suggestions are still merged and the LUCENE-6680 test passes.

The strongest case for "works as designed" (the independent reproduction, the intended-behaviour check and the cross-model reviews built it; the cross-model reviews rated it moderate, the independent reproduction and the intended-behaviour check rejected it without a rating): Lookup documents num only as the "maximum number of results to return" (Lookup.java:190, 206, 219); the numFactor window already makes the blended top-num approximate (testRequiresMore shows a small numFactor missing a result); merging duplicates is intended; on #7397 (LUCENE-6336) a reply says DocumentDictionary "suggests documents, not terms" and another that whether a suggester dedups "is really up to each impl", and @mikemccand proposed deduplicating once, in a dictionary wrapper at indexing time; an order-dependent streaming collector could be called implementation-defined; the class is @lucene.experimental. For the 3-entry case there is even a consistent reading: take the blended top 2 hits (lake, lake), then merge them into one.

Why it fails: the 4-entry case fits no ranking rule. Dedup-then-top-2 gives [lake/950, the lake/900], top-2-then-dedup gives [lake/950], and the code returns [lake/950, my lake/828], a suggestion ranked below one it fetched and dropped; the answer depends on the order in which hits arrive. All 4 hits are inside the fetch window of 20, "maximum" does not cover replacing a better result with a worse one, and @lucene.experimental is about API stability. Build-time dedup is a sound workaround and maintainers may prefer it as a feature, but it does not make the collector's answer right for input the dictionaries accept. Verdict: not intended, a defect.

Options A and B were built and checked in a scratch worktree at a9779ef3c193 (removed after the runs); C is a workaround for released versions.

The finder's guard, +5 lines at the top of boundedTreeAdd. Every other path of the method is unchanged.

if (results.contains(result)) {
  // a duplicate (same weight, text and payload) is collapsed; it must not evict another result
  return;
}

Trade-offs

• Identical suggestions are still merged; a non-duplicate behaves exactly as before.
• Cost: one extra TreeSet lookup, O(log num) on a set of at most num entries, per fetched hit (up to num * numFactor hits per lookup); not benchmarked.

What the checks validated

• This doc's repro: 3 of 4 fail on stock, 4 of 4 pass with the fix (gradle with assertions on; the repro runner with -ea and -da).
• Upstream TestBlendedInfixSuggester: 9 of 9, including the LUCENE-6680 dedup test.
• All of :lucene:suggest:test: 240 tests (236 upstream + 4 new), 0 failures, 7 skipped (6 @Ignore, 1 @Nightly), with assertions off (two runs) and with -Ptests.asserts=true (one run, added in the check resolution: the first module run passed no flag, and for its seed the build picks assertions off); :lucene:suggest:checkGoogleJavaFormat and :lucene:suggest:check -x test (ecjLint, forbiddenApis) pass with the fix and the new test.
• Earlier checks: the finder's, the reproducers', the cross-model reviewers' and the audit's tests pass with the same guard (the adjudication re-ran the independent reproduction's), and the finder's exhaustive scope finds 0 mismatches.

Uses TreeSet.add's return value instead of a separate lookup.

if (results.size() >= num) {
  // add first: only a result that was really added (not a collapsed duplicate) evicts the lowest
  if (results.first().value < result.value && results.add(result)) {
    results.pollFirst();
  }
  return;
}
results.add(result);

Trade-offs

• Same results as A in every case by code reading, including the rule that an equal value does not replace an earlier hit, and no extra lookup; slightly less obvious to read.
• A plainer "add, then trim to num" (suggested by a cross-model review) also fixes the bug but changes ties: a later hit with the same blended value could evict an earlier one by text order (reading, not run).

What the checks validated

• This doc's repro 4 of 4 (gradle; the repro runner with -ea and -da); all of :lucene:suggest:test, 240 tests, 0 failures, 7 skipped (assertions on); the fact check ran the whole module again with -Ptests.asserts=false: 240 tests, 0 failures, 7 skipped.

Collapse the entries that share the text and the payload (or that both have none) into one before build, for example in a wrapping InputIterator. Removing only exact (text, weight, payload) repeats is not enough: the independent reproduction's input {the big apple 1100, x apple 1001, x apple 1000} has none, yet returns [x apple/900] for num=2, because 1001 and 1000 both blend to 900.

Trade-offs

• The merged entry needs one weight (for example the maximum, or an average as @janhoy suggested on #7397) and, if contexts are used, a rule for them (for example their union); that choice is the application's. On #7397, @mikemccand proposed such a dedup dictionary wrapper and deduplicating once at indexing time, so maintainers may also see build-time dedup as a feature to add. Giving each entry a unique payload also avoids the eviction (code reading), but then repeated texts are no longer merged and appear more than once.

What the checks validated

• The independent reproduction's input collapsed by hand to {the big apple 1100, x apple 1001} returns the right [x apple/900, the big apple/880] (main, -ea and -da), and the repro's control, the 4-document input without the repeated lake, returns the right answer. No wrapper was written or run.

Method: bounded-exhaustive translation validation (the hunt's "semi-formal" tier), a hunt unit (cross-implementation differential of the suggest lookups), 2026-10-27, main a9779ef3c193.

• The reference for this class, written from its javadoc: take the fetched num * numFactor hits, score them by the documented BlenderType formulas, collapse identical results and return the top num.
• The hypothesis came from reading boundedTreeAdd while writing that reference. The finder then added scope B2: every sequence of 1 to 4 entries over the texts {a, "b a", "c a"} and the weights {10, 100, 1000}, duplicates allowed (7,380 dictionaries). The stock jar gave 456 too-few and 288 wrong-top-N mismatches for each of the three position blenders, and 0 with the fix shadowed in. A random scope of 100,000 dictionaries also hit it in all four BlenderTypes, CUSTOM through the small-weight x10 scaling.
• A JUnit repro on the public API confirmed it on main, 10.5.2 and 9.12.3. No model checker, SMT solver or prover was used.