The new public DocAndScoreQuery factory keeps repeated doc ids: a document listed twice is counted twice and can leak into the previous segment

#16686 made DocAndScoreQuery and its createDocAndScoreQuery(IndexReader, TopDocs, ...) factory public on main, for authors of their own kNN queries. The javadoc promises a query that "matches exactly the documents in topK" and lists its preconditions, but not that a document may appear only once, and the factory does not check it. It sorts the entries by doc id and copies every one, so a repeated document is counted, iterated and returned once per copy (two kNN fields that find the same 4 documents give a count of 8). Segment boundaries are found with Arrays.binarySearch, which may land on any copy of a repeated value: when the repeated document is the first document of a segment, the earlier copy stays in the previous segment and comes out there as doc id maxDoc, one past its last document. That copy is checked against the wrong segment's live docs, doc values and other clauses. With deletions there, the live-docs check reads past its end: with assertions off it throws ArrayIndexOutOfBoundsException when that segment's maxDoc is a multiple of 64 and its live docs are dense (64 documents, one deleted), drops the copy for other sizes, and lets it through with sparse live docs (128 documents, one deleted: the document is returned twice). A doc-values sort throws or uses another document's value, and when that segment has no deletions the document is returned even if it is deleted or excluded by a MUST_NOT clause. Lucene's own callers and TopDocs.rrf never pass repeats, and no release exposes the public factory (9.9.0 to 10.6.0 reach the same code through a kNN query subclass that overrides protected hooks, judged contrived). Rejecting repeats with IllegalArgumentException (or collapsing them) fixes it; both were validated.

1. The factory copies every entry. createDocAndScoreQuery (:121-143) reads the max score from scoreDocs[0] (:125), sorts topK.scoreDocs by doc id in place (:126) and copies all entries into docs[] and scores[] (:127-132). Nothing removes or rejects a repeated doc id; the only input check is assert len > 0 (:124).
2. Segment slices come from a binary search. findSegmentStarts (:145-161) places each segment's first entry with Arrays.binarySearch(docs, resultIndex, docs.length, upper), where upper is the segment's docBase (:153-154). The JDK documents that "If the range contains multiple elements with the specified value, there is no guarantee which one will be found." For docs = [1, 1, 2] and docBase 1 the search probes the middle index first and returns index 1, so segmentStarts = [0, 1, 3].
3. Each segment counts and iterates its slice entry by entry. Weight#count is segmentStarts[ord + 1] - segmentStarts[ord] (:192-195); nextDoc steps one entry at a time (:217-224) and returns docs[upTo] - context.docBase (:254-262). Segment 0 gets slice [0, 1) = doc 1 and returns 1 - 0 = 1, its maxDoc; segment 1 gets docs 1 and 2 and returns 0 and 1. In general the leaked copy comes out as docBase(next) - docBase(prev) = maxDoc(prev).
4. Why the leaked copy escapes deletions and MUST_NOT. The collector adds segment 0's docBase, so the hit has the right global id, but everything per segment is checked in segment 0: its live docs (an out-of-range bit; with assertions off: with 64 documents and a deletion, ArrayIndexOutOfBoundsException; with 3, 63 or 65 documents a clear padding bit, so the copy is dropped; with sparse live docs, 128 documents and one deletion, it passes and the document is returned twice; with no deletions, no check at all), its doc values (read past the end) and a MUST_NOT clause's iterator on segment 0, which never reaches doc id maxDoc, so the exclusion does not apply. A FILTER clause never matches it there either, so a conjunction drops it.
5. Repeats away from a boundary stay in range but are counted and returned once per copy.

• Minimal layout (segment 0 = doc 0; segment 1 = docs 1, 2), topK docs [1, 1, 2]: segment 0 iterates [1] with maxDoc 1; Weight#count 1 + 2; IndexSearcher#count 3; hits [1, 1, 2]; with MUST_NOT id:1 hits [1, 2] instead of [2].
• Two kNN fields that both find the same 4 documents, lists concatenated: IndexSearcher#count 8, totalHits 8, every hit twice, iterator 1 1 2 2 3 3 4 4.
• Segment 0 with 64 documents and a deletion, docs [64, 64, 65]: ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1 from the live docs (assertions off), AssertionError: index=64, numBits=64 (on). Other sizes, doc 0 deleted, docs [b, b, b+1] with b = segment 0's maxDoc, assertions off: 3, 63 and 65 documents give hits [b, b+1] (the copy reads a clear, unused bit and is dropped); 128 documents (sparse live docs) give [128, 128, 129], the document twice; with assertions on all five sizes throw an AssertionError.
• Segment 0 with 64 documents and no deletion, sorted by a numeric doc-values field: EOFException with the test framework's wrapped directory (newDirectory()), IndexOutOfBoundsException with a plain ByteBuffersDirectory; with a 3-document segment 0 the document is sorted with a value that is not its own (1000 instead of 1003).
• Segment 0 without deletions: the document is returned even when it is deleted, and despite a MUST_NOT clause that matches it; a FILTER clause still excludes it.

Making the binary search return the first copy alone makes the minimal test pass but keeps the doubled hits (expected:<[64, 65]> but was:<[64, 64, 65, 65]>).

• Who is exposed. Authors of their own kNN queries on main or branch_11x who build the TopDocs by hand, for example by concatenating the results of two vector fields or two query vectors without de-duplicating. #16686 opened the API for exactly such "own KNN query classes".
• Configuration and scale. Default configuration and a few documents: the minimal test uses a plain IndexWriterConfig, ByteBuffersDirectory and IndexSearcher (some consequence probes set NoMergePolicy only to keep their segment layout). The boundary shape also needs the repeated document to be the first document of a segment other than the first.
• Symptoms. Doubled counts, totalHits and hits, with no error. At a segment boundary, depending on the previous segment: an exception far from the cause (ArrayIndexOutOfBoundsException, EOFException, IndexOutOfBoundsException), a wrong sort value, a document returned twice, or a deleted or MUST_NOT-excluded document returned.
• Not exposed. Lucene's own callers (AbstractKnnVectorQuery.java:156, RescoreTopNQuery.java:90) pass lists without repeats. TopDocs.rrf (TopDocs.java:372) merges repeated documents: the same two-field inputs combined with it pass, including the boundary layout with a deletion and a doc-values sort. No release has the public factory (package-private in 10.x, private in 9.x); 9.9.0 to 10.6.0 reach the same code through a kNN query subclass that overrides protected hooks (see History).
• Likelihood: rare. It needs a hand-built list that keeps a document twice. Downstream multi-kNN code (elastic/elasticsearch#92118) shows such lists do contain repeats, and de-duplicates them before building its own query.

The class sits in org.apache.lucene.search next to the kNN tests and uses nothing package-private; a probe outside the package shows the same leak. It uses a plain IndexWriterConfig, ByteBuffersDirectory and a plain IndexSearcher, with a commit after the first document so that segment 0 holds doc 0 and segment 1 holds docs 1 and 2. It needs the public 3-argument factory, so it compiles only on main and branch_11x (10.6.0 has no createDocAndScoreQuery(IndexReader, TopDocs, int) and its factories are package-private: "incompatible types: int cannot be converted to NoMatchExplainer").

Regression test: this same test. With the collapse fix it passes as written. With the recommended reject fix the factory call throws, so the test's last five statements become a TopDocs local and one expectThrows(IllegalArgumentException.class, () -> DocAndScoreQuery.createDocAndScoreQuery(r, topDocs, 0)); that form passes with the fix and fails on stock ("Expected exception IllegalArgumentException but no exception was thrown").

cp $REPRO/TestDocAndScoreQueryRepeatedDoc.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.search.TestDocAndScoreQueryRepeatedDoc -Ptests.seed=DEADBEEF
# assertions off fails the same way: add -Ptests.asserts=false (the recorded runs added --offline --no-daemon)

# gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF, assertions on
   >     java.lang.AssertionError: first doc of segment 0 expected:<2147483647> but was:<1>
   >         at __randomizedtesting.SeedInfo.seed([DEADBEEF:E90A93E502F3C914]:0)
   >         at org.junit.Assert.fail(Assert.java:89)
   >         at org.junit.Assert.failNotEquals(Assert.java:835)
   >         at org.junit.Assert.assertEquals(Assert.java:647)
   >         at org.apache.lucene.search.TestDocAndScoreQueryRepeatedDoc.testRepeatedFirstDocOfSegment(TestDocAndScoreQueryRepeatedDoc.java:47)
:lucene:core:test (FAILURE): 1 test, 1  failure

# the same with -Ptests.asserts=false: same message, 1 of 1 failed

# public-API probe outside the package, same layout with an id field per document (assertions on and off identical)
topK docs=[1, 2]    | leaf0 Weight#count=0 iterated=[]  | leaf1 Weight#count=2 iterated=[0 1] | IndexSearcher#count=2 totalHits=2 hits=[1, 2] | with MUST_NOT id:1 hits=[2]
topK docs=[1, 1, 2] | leaf0 Weight#count=1 iterated=[1] | leaf1 Weight#count=2 iterated=[0 1] | IndexSearcher#count=3 totalHits=3 hits=[1, 1, 2] | with MUST_NOT id:1 hits=[1, 2]

• The contract describes a set of documents. "Create a query that matches exactly the documents in {@code topK}" and "@param topK the documents to match" (DocAndScoreQuery.java:104, :114). IndexSearcher#count: "Count how many documents match the given query" (IndexSearcher.java:491); Weight#count: "Counts the number of live documents that match" (Weight.java:182). A count of 3 for 2 documents contradicts all three.
• Every other precondition is listed. Global doc ids of that reader, that reader only (else IllegalStateException), descending score order, non-empty (DocAndScoreQuery.java:103-120). The class has no @lucene.internal or @lucene.experimental tag, and it already fails fast on the other documented misuse (another reader throws in createWeight, :170-171).
• The iterator contract. A leaf doc id equal to maxDoc lies outside the segment's doc-id space under any reading. Repeats away from a boundary are a weaker point: DocIdSetIterator says "a set of non-decreasing doc ids" (DocIdSetIterator.java:23), which read literally allows equal neighbours, but also "set" and, for nextDoc, "Advances to the next document in the set" (:127); the test framework asserts strictly increasing, in-range ids (AssertingScorer.java:171 "backwards nextDoc", AssertingLeafCollector.java:128-130 "Out of order", "Out of range").
• Lucene's other public set-like inputs de-duplicate or reject. TermInSetQuery.java:153 and PointInSetQuery.java:118 skip repeats ("// deduplicate"); RoaringDocIdSet.Builder throws "Doc ids must be added in-order" (RoaringDocIdSet.java:118).
• An exposure, not a design. The copy-every-entry factory and the binary search date from LUCENE-9614 (2021), when only Lucene's duplicate-free callers could reach them. #16686 changed only visibility and javadoc; its discussion covers NoMatchExplainer visibility and the backport, nothing about input requirements.

The intended-behaviour verifier and the adjudication built the strongest case for "callers must de-duplicate": topK is a TopDocs, which "Represents hits returned by IndexSearcher#search" (TopDocs.java:26), and the javadoc expects it "as produced by a nearest-neighbors search" (DocAndScoreQuery.java:109-110); a search never returns a document twice. The package-private constructor has documented docs "in ascending order" since 2021 (:52); #12152 built count on "a monotonically increasing start for each scored document"; a maintainer wrote "Lucene hits would never duplicate docid" in the #15950 review; TopDocs.rrf is the idiomatic fusion; and a downstream project de-duplicates before building its own analogous query (elastic/elasticsearch#92118).

Why it fails: the public javadoc spells out its preconditions and leaves uniqueness out (the ascending-order and monotonic notes concern the package-private constructor and internal callers); the API was opened for authors who build such lists themselves; and the failure mode is no error at the call, then an out-of-range doc id that crashes far away or lets a deleted or excluded document through. So even if maintainers rule uniqueness a precondition, a documented check is warranted. The cross-model reviews rated the intended-behaviour case "moderate"; the reproducer, the devil's advocate, the adjudication and an audit kept the bug. Verdict: not intended; at least a missing precondition check in a new public API.

Two fixes were validated through gradle in a scratch worktree of 645d4fe14a20; both act in the factory, before the segment split, so every segment's slice holds distinct, increasing doc ids. A third change was run for comparison only: it is not sufficient.

In createDocAndScoreQuery, after the sort, throw when a doc id equals the previous one, and add the precondition to the javadoc: "Each document may appear at most once in {@code topK}; {@link IllegalArgumentException} is thrown otherwise."

for (int i = 0; i < len; i++) {
  docs[i] = topK.scoreDocs[i].doc;
  scores[i] = topK.scoreDocs[i].score;
  if (i > 0 && docs[i] == docs[i - 1]) {
    throw new IllegalArgumentException("topK lists doc " + docs[i] + " more than once");
  }
}

Trade-offs

• Least opinionated. No score policy to choose; callers that combine lists keep control of fusion (for example TopDocs.rrf). It matches the class's existing fail-fast check of the reader. The devil's-advocate verifier and the adjudication call it the least opinionated choice, and an audit expects a committer to accept it with little debate.
• Cost. One comparison per entry; Lucene's own callers never trigger it. The throw comes after the documented in-place sort of topK. It also changes behaviour for released kNN query subclasses whose overridden hooks return a repeat: they get IllegalArgumentException instead of wrong results, so a CHANGES line is worth considering.
• Test. The minimal test's final statements become an expectThrows (see Minimal repro).

What the checks validated

• Repro: now stops at the factory with IllegalArgumentException: topK lists doc 1 more than once; the expectThrows form passes with the fix and fails on stock.
• :lucene:core search.*Knn*, TestPatience*, TestRescoreTopNQuery*, TestFilterReadersForwardVectorPrefetch: 297 tests, 2 skipped, 0 failures; :lucene:join kNN tests: 39, 0 failures.
• checkGoogleJavaFormat, ecjLintMain, ecjLintTest, forbiddenApisMain: pass.

After the sort, merge equal doc ids, keep the maximum of their scores and trim the arrays with ArrayUtil.copyOfSubArray; one javadoc sentence: "A document listed more than once matches once, with the highest of its scores." (+17/-3)

Trade-offs

Fulfils "matches exactly the documents in topK" literally and keeps the minimal test unchanged, but silently picks a fusion policy (max): a caller who wanted sum or first gets max without noticing, so the policy must be documented. The hunt's original version used Arrays#copyOf, which Lucene's forbidden-apis check rejects ("Prefer using ArrayUtil"); this version does not.

What the checks validated

• The minimal test passes as written, assertions on and off; 14 core classes, 298 tests (the repro and the same suites), 2 skipped, 0 failures; the assertions-off subset (91) and the join kNN tests (39) pass.
• All five lint tasks pass; the hunt's 4-test class (assertions on and off) and the independent reproducer's 5-test class pass with it.

findSegmentStarts steps back to the first index of a run of equal doc ids.

Trade-offs

Run for comparison only: the minimal test passes, but repeats are still counted and returned twice (the hunt's tests fail 3 of 4, expected:<[64, 65]> but was:<[64, 64, 65, 65]>). Useful as hardening on top of a factory fix, not instead.

Add "each document at most once" to the javadoc without a check.

Trade-offs

Keeps the out-of-range doc id, and its deletion and MUST_NOT effects, for anyone who misses the sentence.

Method: non-formal first signal (a probe; the Z3 model came after it).

• While reading the contract of the factory made public by #16686, the hunt ran a probe on main (2026-10-28): two kNN result lists concatenated, IndexSearcher#count 8 for 4 distinct documents, iterator 1 1 2 2 3 3 4 4.
• The hunt unit wrote a Z3 model of findSegmentStarts with Java's exact Arrays.binarySearch0 over unbounded 32-bit doc ids: 24 satisfiable cases with repeats, witness docs = [b, b, c], docBase = b, and none for a lower-bound search. It checked the model against the real jar on 64,659 sorted arrays.
• A bounded-exhaustive model-based test of the factory javadoc against the stock jar (every topK multiset of size 1 to 4 on 5 segment layouts and 3 score variants, 12 observables, 3,135 cases, about 307,000 checks): all 2,295 repeated-doc cases fail, none of the 840 duplicate-free cases.
• It reduced this to a public-API JUnit; an independent reproducer, a devil's-advocate verifier, cross-model reviews and an adjudication then checked it. A later step shrank the repro to one test on three documents.