A kNN filter backed by a bit set shorter than maxDoc makes the search throw instead of returning hits

Before a filtered kNN search, AbstractKnnVectorQuery turns the filter into per-segment accept bits through AcceptDocs.fromIteratorSupplier. When the segment has no deletions and the filter's iterator is a BitSetIterator, AcceptDocs.createBitSet returns that iterator's own BitSet without checking its length (AcceptDocs.java:95-97 at 5adff78bb168). Its two other branches build exactly maxDoc bits, and the class's other factory, fromLiveDocs, rejects bits whose length is not maxDoc. The HNSW reader then reads the accept bits for vector ordinals up to the segment's vector count, so a shorter set is read past its end: AssertionError with assertions on, ArrayIndexOutOfBoundsException with them off once an ordinal passes the set's last 64-bit word. No in-tree query builds such a set; a custom filter does, on a segment with no deletions where every document has the vector. It fails loudly; no wrong hit was seen. A one-line guard (reuse the set only when its length is maxDoc) fixes it.

1. The filter's own iterator reaches AcceptDocs. The filter is ANDed with FieldExistsQuery(field) and rewritten (search/AbstractKnnVectorQuery.java:88-97); when every document has the vector, FieldExistsQuery rewrites to match-all and drops out, and the filter scorer's iterator goes unwrapped into AcceptDocs.fromIteratorSupplier(.., liveDocs, reader.maxDoc()) (:257-268).
2. The shortcut reuses the set unchecked. createBitSet: if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) { // If we already have a BitSet and no deletions, reuse the BitSet; return bitSetIterator.getBitSet(); } (search/AcceptDocs.java:95-97). This is the fix site. The other branches build new FixedBitSet(maxDoc) (:102) or BitSet.of(.., maxDoc) (:109-111), and BitsAcceptDocs, behind fromLiveDocs, throws IllegalArgumentException("Bits length = .. != maxDoc = ..") (:124-128). bits() hands the reused set out as is (:187-191).
3. The reader reads every ordinal. accepted = acceptDocs.bits() (codecs/lucene99/Lucene99HnswVectorsReader.java:370); the exhaustive loop tests acceptedOrds.get(i) for every i < scorer.maxOrd() (:388-389), and the graph branch passes the same bits to HnswGraphSearcher, which tests every visited ordinal (:379-381). Ordinals equal doc ids here because every document has a vector.
4. The read runs off the set. FixedBitSet.get asserts index < numBits (util/FixedBitSet.java:286). With assertions off it reads word index >> 6 (:287-291): ordinals 10 to 63 read the set's only word and correctly return false; ordinal 64 reads word 1 of a 1-word array and throws.

• All of these are needed: a filter whose scorer iterates a BitSetIterator over a set shorter than maxDoc; no deletions in the segment (otherwise the copying branch builds maxDoc bits); every document has the vector field (otherwise the FieldExistsQuery conjunction wraps the iterator); the filter not served from the query cache, whose sets are maxDoc long.
• No in-tree query builds such a set: point, spatial and join queries, DocIdSetBuilder, LRUQueryCache and QueryBitSetProducer size theirs to maxDoc. Custom code can, with the @lucene.internal BitSetIterator, BitDocIdSet or DocIdSetBuilder, or with the public, untagged DocsWithFieldSet.iterator() (index/DocsWithFieldSet.java:101-104), which returns a BitSetIterator once its documents are not exactly 0 to n-1, over a set that grows with the documents added rather than to maxDoc; a custom filter built on it fails the same way (executed). Both are unusual custom-filter constructions.
• Sets longer than maxDoc are not read past their end here (by reading; not tested). With assertions off, a short set throws only once the reader reaches an ordinal past its last 64-bit word, and the reads below that are correct, so no wrong hit was seen.
• In the repro, the 100-vector segment gets no HNSW graph (#14963, 10.4.0: graphs are skipped for tiny segments), so the reader takes the exhaustive loop. On bigger segments, or before 10.4.0, the graph walk reads the bits for the ordinals it visits: with assertions on it fails at the first visited ordinal past the set, with them off only at one past the set's last 64-bit word (on 10.0.0 and 10.3.0 the repro's walk visits ordinal 54, so it fails with assertions on and passes with them off).

• Who. Code with its own filter Query whose scorer iterates a BitSetIterator over a set sized to its matches, or built for a smaller doc range, instead of the segment's maxDoc. A downstream vector-search plugin built such shorter-than-maxDoc BitSetIterators in 2022 (LUCENE-10674, #1068).
• Default vs opt-in. Default codec, IndexWriterConfig and searcher; the trigger is the application's filter code.
• Effect. Loud: that request throws from IndexSearcher.search and returns nothing. No corruption, and no wrong, extra or leaked hit was seen: by reading, the reads below the failing ordinal return the filter's own answer.
• Scale. None needed: 100 documents, one segment, single thread, deterministic.
• Likelihood. Rare: no in-tree query reaches it, and no public report of this crash was found since 9.3.0.

TestKnnFilterBitSetShorterThanMaxDoc (one method, extends LuceneTestCase, package org.apache.lucene.search of the lucene/core tests, no package-private member, Apache license header; it does use the @lucene.internal FixedBitSet, BitSetIterator and protected Weight.DefaultScorerSupplier). Its input is fixed; LuceneTestCase still randomizes the directory, so the command pins a seed (it also failed with three other seeds). It passes checkGoogleJavaFormat. It fails with assertions on and off on main, and passes unchanged with the recommended fix. The release-jar runs and the first gradle pass (the 89-test suite and the unpatched run with assertions off) used an earlier copy of this test that differs only in one comment line; the current copy was re-run unpatched with assertions on and patched with them on and off, and an independent fact check ran it unpatched with assertions on and off (both fail).

cp $REPRO/TestKnnFilterBitSetShorterThanMaxDoc.java $LUCENE/lucene/core/src/test/org/apache/lucene/search/
cd $LUCENE && ./gradlew :lucene:core:test --tests TestKnnFilterBitSetShorterThanMaxDoc -Ptests.seed=DEADBEEF

# gradle, scratch worktree at 5adff78bb168, -Ptests.seed=DEADBEEF, assertions on
TestKnnFilterBitSetShorterThanMaxDoc > testFilterBitSetShorterThanMaxDoc FAILED
    java.lang.AssertionError: index=10, numBits=10
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:5C2E948DDFDC87E4]:0)
        at org.apache.lucene.util.FixedBitSet.get(FixedBitSet.java:286)
        at org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsReader.search(Lucene99HnswVectorsReader.java:389)
        at org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsReader.search(Lucene99HnswVectorsReader.java:324)
        at org.apache.lucene.codecs.perfield.PerFieldKnnVectorsFormat$FieldsReader.search(PerFieldKnnVectorsFormat.java:329)
        at org.apache.lucene.index.CodecReader.searchNearestVectors(CodecReader.java:294)
        at org.apache.lucene.search.KnnFloatVectorQuery.approximateSearch(KnnFloatVectorQuery.java:118)
        at org.apache.lucene.search.AbstractKnnVectorQuery.getLeafResults(AbstractKnnVectorQuery.java:290)
        ...
        at org.apache.lucene.search.IndexSearcher.search(IndexSearcher.java:624)

# same, -Ptests.asserts=false
TestKnnFilterBitSetShorterThanMaxDoc > testFilterBitSetShorterThanMaxDoc FAILED
    java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
        at org.apache.lucene.util.FixedBitSet.get(FixedBitSet.java:291)
        at org.apache.lucene.codecs.lucene99.Lucene99HnswVectorsReader.search(Lucene99HnswVectorsReader.java:389)
        ...

# release jars (repro harness, seed DEADBEEF)
10.6.0, assertions off: ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1 at Lucene99HnswVectorsReader.search:377
10.4.0, assertions off: same, at Lucene99HnswVectorsReader.search:365
10.3.0, assertions on: AssertionError: index=54, numBits=10 at HnswGraphSearcher.searchLevel:295 (passes with assertions off)

# with the fix: passes, assertions on and off

• The class enforces the length on its other path. fromLiveDocs rejects bits of the wrong length (AcceptDocs.java:124-128), the two copying branches of createBitSet build exactly maxDoc bits (:102, :109-111), and upstream TestAcceptDocs asserts bits().length() == maxDoc for both factories (lucene/core/src/test/org/apache/lucene/search/TestAcceptDocs.java:57-59).
• No length requirement anywhere. No javadoc, CHANGES or MIGRATE entry says a filter's BitSetIterator must cover the segment. BitSetIterator caches bits.length() and returns NO_MORE_DOCS past it (util/BitSetIterator.java:72, :94-95).
• Core accepts shorter sets elsewhere. BitSetConjunctionDISI uses the minimum length of its sets (search/ConjunctionDISI.java:244-250). LUCENE-10674 (#1068 / #11709, fixed in 9.4.0) fixed that class for exactly this input, built by a downstream plugin; a maintainer called such sets "not typical" (2022-09-09), and the fix was merged with a test.
• The same filter works everywhere else. On main, the 10-bit filter gives count 10, a plain search 10 hits, and 10 hits in a conjunction with FieldExistsQuery (independent reproducer's controls).
• History. Before #951 (9.1.0, 9.2.0) the filter was always collected into a new FixedBitSet(maxDoc); #951's description and review do not discuss the set's length.

The case for intended: BitSetIterator and FixedBitSet are @lucene.internal, so a short backing set is outside the public input domain (the executed cross-model refute review, which still reproduced the crash and agreed on the root cause and the fix). Also: Bits.get says out-of-range indexes are undefined, "just don't do it!" (util/Bits.java:30-31).

The answer (a judgement call): the tag withholds API-stability guarantees; it does not make a valid DocIdSetIterator an illegal filter, and the public, untagged DocsWithFieldSet.iterator() reaches the same crash. The Bits.get rule binds the caller, and here the caller is Lucene's own reader, fed bits that AcceptDocs built against its own invariant. #1068 shows upstream already treated this input class as a bug. On this reading, these points lower the likelihood rather than the validity, and the devil's-advocate verifier and the adjudication rejected the objection; a maintainer may still weigh the contract objection differently.

Option A was built and checked through gradle on 5adff78bb168; B and C were not built.

Add bitSetIterator.getBitSet().length() == maxDoc to the shortcut's condition in AcceptDocs.createBitSet (AcceptDocs.java:95). A short set falls through to the existing copying branches, which build a maxDoc-sized set.

-    if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
+    if (liveDocs == null
+        && iterator instanceof BitSetIterator bitSetIterator
+        && bitSetIterator.getBitSet().length() == maxDoc) {

Trade-offs

• In-tree filters, whose sets are maxDoc long, keep the zero-copy shortcut; the cost is one length comparison per segment, plus a copy for sets of any other length.
• Matches the class's own invariant (fromLiveDocs, TestAcceptDocs).
• With ==, a set longer than maxDoc is copied too. That is fine while its set bits are below maxDoc, as a filter's matches must be; a set with a bit at or past maxDoc would throw in the copy (BitSetIterator.intoBitSet, util/BitSetIterator.java:126-128), where today's shortcut never reads it. Not tested.

What the checks validated

• gradle in a scratch worktree at 5adff78bb168, seed DEADBEEF: the repro fails without the fix (assertions on and off) and passes with it (on and off).
• With the fix: the repro (1), TestAcceptDocs (5), TestKnnFloatVectorQuery (43) and TestKnnByteVectorQuery (40): 89 tests, 0 failures. :lucene:core:checkGoogleJavaFormat passes with the fix and the test in the tree. The whole core module was not run.
• The finder's earlier run of the same guard also passed its larger graph-walk probe (2000 vectors, a 1000-bit set).

Reuse the set when getBitSet().length() >= maxDoc.

Trade-offs

Also keeps the shortcut for oversized sets, which the readers do not read past their end (by reading), but bits().length() could then differ from maxDoc, unlike every other AcceptDocs. Not built.

Make the HNSW reader treat ordinals at or past acceptedOrds.length() as not accepted.

Trade-offs

Adds a check to the hot per-ordinal loop and must be repeated in every KnnVectorsReader; the public AcceptDocs.bits() would still hand short bits to outside readers. Not recommended; not built.

Method: semi-formal (a proof-obligation audit of a class's contract, witnessed by an executable repro).

• The finder stated the obligation for AcceptDocs: bits() of an AcceptDocs for a segment covers [0, maxDoc), as fromLiveDocs enforces and as the HNSW reader assumes. Two branches of createBitSet discharge it by construction; the reuse shortcut discharges it only if the filter's set is maxDoc long, which nothing checks.
• The finder then wrote a JUnit test that fails on main with assertions on and off and on 10.2.0 to 10.6.0, a larger graph-walk probe for older releases, and the one-line guard.
• An independent reproducer, an executed cross-model review, a devil's-advocate verifier and an adjudication reproduced it with their own tests ("Prior reports, history and checks").