You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Filtered kNN: accept set built one doc at a time with deletions, cached filter bypassed, every vector scanned for small filters, off-heap lookup per accept test on sparse fields #16586
a filtered knn query on a segment with deletions builds its accept set one doc at a time instead of copying the cached filter's bitset. moreover, on a field where some docs have no vector it also ANDs a FieldExistsQuery into the filter, which turns the cached bitset into a fresh conjunction that can't be bulk copied either. both are O(docs in the segment) and sit in front of a search that's O(k log n), so on a big segment they cost more than the search itself, 1.7x and 2.5x per query in the benchmark. separately, for small filters the reader falls back to scanning every vector in the segment to score the few hundred accepted ones, and the threshold for doing that is a guess that's wrong by a factor of 2-5x on real data.
four PRs, the first two are a few lines each. all numbers below are milliseconds per query on one 200k-doc segment, k=100, and (Nx) is main divided by patched.
What happens
KnnFloatVectorQuery / KnnByteVectorQuery with a pre-filter build a per-leaf accept set in AcceptDocs.fromIteratorSupplier, then hand it to the codec. Five things go wrong on that path.
With deletions, the accept set is built one doc at a time. DocIdSetIteratorAcceptDocs.createBitSetAcceptDocsIfNecessary (AcceptDocs.java:177-182) passes iterator() to createBitSet, and with live docs iterator() is a FilteredDocIdSetIterator, which has no intoBitSet, so FixedBitSet#or falls back to nextDoc() per doc, and createBitSet then applies liveDocs a second time. One deleted doc in the segment is enough, for any accept set dense enough for the bit set branch (cost >= maxDoc >> 7). createBitSet already handles liveDocs, it should get the raw iterator.
The cached filter is never used as-is. AbstractKnnVectorQuery#rewrite (AbstractKnnVectorQuery.java:88-92) ANDs FieldExistsQuery(field) into the filter, so what reaches the accept set is a fresh ConjunctionDISI per query instead of the cached BitSetIterator, and ConjunctionDISI has no intoBitSet either. The conjunct came in with LUCENE-10382: Support filtering in KnnVectorQuery #656 for the exact search cost estimate, not for correctness: HNSW only scores graph ordinals and exactSearch intersects with the vector iterator anyway. It only survives when some leaf has a doc without a vector, otherwise FieldExistsQuery rewrites to MatchAllDocsQuery and drops out.
The filter weight itself is not cached. Same method, line 97: rewritten.createWeight(indexSearcher, ...) instead of indexSearcher.createWeight(...), so the query cache is consulted only for the clauses of a BooleanQuery filter, never for the filter. AbstractVectorSimilarityQuery (:152) goes through the searcher.
Small filters scan the whole segment. The query runs an exact search only when the filter accepts at most perLeafTopK docs (AbstractKnnVectorQuery.java:282). The reader has its own rule, HnswGraphSearcher#expectedVisitedNodes = log(graphSize) * k, and refuses the graph when the accept set is at most that (Lucene99HnswVectorsReader.java:369-372). But its fallback scans every vector of the segment testing the accept bits one by one (:382). So between perLeafTopK and log(graphSize) * k accepted docs, the query asks for an approximate search, the codec declines, and 200k vectors get tested to find 400 of them, with a DirectMonotonicReader lookup per ordinal on a field that has vectorless docs.
On a field where some docs have no vector, the filtered graph search tests acceptance through an off-heap lookup. Lucene99HnswVectorsReader#search (:365) hands the search scorer.getAcceptOrds(accepted), which for the sparse off-heap values is a lazy Bits whose get(ord) is acceptDocs.get(ordToDoc(ord)), a DirectMonotonicReader read. FilteredHnswGraphSearcher does that on every neighbour and 2-hop neighbour it looks at. At 2% selectivity that lookup is ~40% of the query on such a field (0.30 of 0.74 ms, async-profiler); the same query on a fully vectored field takes 0.40 ms.
1 and 2 compound: fixing 1 alone still walks a ConjunctionDISI per doc, fixing 2 alone still wraps the cached bit set in FilteredDocIdSetIterator on any segment with deletes.
Numbers
FilteredKnnVectorQueryBenchmark (added in PR-1): one segment, 200k docs, 128-dim random unit vectors, float HNSW with the default codec, k=100, pre-filter a TermQuery already in the LRUQueryCache. main @ 411013e, JDK 25 with --add-modules jdk.incubator.vector, AMD Genoa, each cell its own JMH process pinned to 10 vCPUs. ms per query.
Problems 1 to 3 (PR-1 fixes 1, PR-2 fixes 2 and 3), 3 forks per arm:
filter selectivity
docs without vector
deleted docs
main (ms/query)
PR-1 (ms/query)
PR-1+2 (ms/query)
95%
0%
0%
0.442
0.452
0.445
95%
0%
5%
2.046
1.227 (1.67x)
1.242 (1.65x)
95%
10%
0%
2.265
2.199
0.472 (4.79x)
95%
10%
5%
3.187
2.918 (1.09x)
1.226 (2.60x)
5%
0%
0%
0.432
0.506
0.501
5%
0%
5%
0.557
0.526
0.495 (1.13x)
5%
10%
0%
1.002
1.059
0.888 (1.13x)
5%
10%
5%
1.097
1.041
0.908 (1.21x)
Same index, 5% deleted, across selectivities:
filter selectivity
docs without vector
main (ms/query)
PR-1 (ms/query)
PR-1+2 (ms/query)
99%
0%
2.062
1.231 (1.68x)
1.232 (1.67x)
50%
0%
1.372
0.930 (1.48x)
0.899 (1.53x)
20%
0%
0.907
0.730 (1.24x)
0.675 (1.34x)
1%
0%
0.403
0.364 (1.11x)
0.376 (1.07x)
99%
10%
3.242
2.850 (1.14x)
1.291 (2.51x)
50%
10%
2.144
2.053 (1.04x)
1.133 (1.89x)
20%
10%
1.457
1.288 (1.13x)
0.937 (1.55x)
1%
10%
0.776
0.771 (1.01x)
0.716 (1.08x)
The gain scales with how many docs the filter accepts, since that is what the accept set build costs; below ~1% the graph search dominates. Rows with no deletions and no vectorless docs are the noise floor, nothing runs there (fork to fork spread is up to 13% at 0.45 ms, the 0.85x is that). PR-1 needs deletions, PR-2 needs a vectorless doc somewhere. Top-100 (doc, score) lists for 32 queries per cell are identical across the three arms.
the rows with deletions keep ~0.8 ms after both fixes: createBitSet's closing applyMask(liveDocs) runs per bit on DenseLiveDocs/SparseLiveDocs since #15413, same hole as #16282. #16593 fixes that separately, and with it these rows land on the no-deletion floor (2.07 -> 0.49 at 5% deleted)
Problem 4 (PR-3 fixes the scan, PR-4 the decision), PR-1+2 as the baseline, no deletions, 2 forks interleaved. PR-3 makes the reader's scan enumerate the accept set instead of testing every ordinal:
accepted docs
every doc has a vector (ms/query, PR-1+2 -> PR-3)
10% of docs without a vector (ms/query, PR-1+2 -> PR-3)
200
0.193 -> 0.022
1.499 -> 0.033
1000
0.276 -> 0.049
1.641 -> 0.080
Recall against brute force over the accepted docs is 1.0 before and after, the scan was exact already, it just cost 5.5 to 45 times more. Above log(graphSize) * k accepted (about 1220 here) the reader takes the graph, and that is the wrong call for a while: at 4000 accepted, scoring the accept set is cheaper than the filtered walk on this corpus, and PR-4, which weighs the two instead of comparing the accept count to log(graphSize) * k, takes that cell from 0.389 to 0.131 ms on a dense field and 0.497 to 0.205 with 10% vectorless. By 10% accepted the graph wins and PR-4 leaves it alone (within 2%, same at 95%).
I first did problem 4 on the query side, raising the query's exact search threshold to log(maxDoc) * perLeafTopK. It measured 3.5 to 26x over main in the band but it is the wrong place: once the reader's batched scan exists, the query's per-doc exactSearch pre-empts it and costs 1.15 to 2.1x more for the same answer (0.038 vs 0.021 ms at 200 accepted, 0.074 vs 0.047 at 1000, 0.879 vs 0.412 on 2-3 leaves at k=1000 and 2%). So the decision stays in the reader, which is the only layer that can see the graph.
Problem 5 (also PR-3), same index with 10% vectorless docs, the accepted ordinals materialised once per query before the filtered graph search:
filter selectivity
before (ms/query)
after (ms/query)
2%
0.795
0.513 (1.55x)
2%, 5% deleted
0.841
0.585 (1.44x)
5%
0.910
0.676 (1.35x)
10%
1.014
0.851 (1.19x)
50%
0.737
0.744
Dense field unchanged, 0.440 -> 0.441. The pass is one advance per accepted doc plus a bit set over the vectors, so it is gated on the filtered searcher being chosen and the accept set being small enough that the lookups it removes outnumber the advances (about 2sqrt(expectedVisitedNodesgraphSize), 29.5k accepted on this index); above that it does nothing.
Where this was found: elasticsearch 9.4.4 / lucene 10.4.0, a 5.8M doc index shaped like production (10.6% docs without a vector, filter accepting 99.9%, six knn clauses, k=4000), 430 -> 289 cpu-ms per request with PR-1, 182 with PR-1+2 (2.37x). That multiplier is elasticsearch's, it runs its cancellation check inside the per-doc walk (ExitableDirectoryReader.checkAndThrowWithSampling was 40% of the unpatched profile, FilteredDocIdSetIterator.nextDoc 37%). Plain lucene has no such wrapper, the JMH numbers above are the ones to expect here. PR-3 and PR-4 have not been measured at that scale.
Proposed fix
Four PRs, stacked, all against main:
PR-1, AcceptDocs: pass iteratorSupplier.get() to createBitSet. +4/-1, with a test that counts nextDoc() calls on the source iterator and fails on main when the segment has deletions. Adds the benchmark.
PR-2, AbstractKnnVectorQuery: drop the conjunct behind protected boolean requiresVectorPresenceInFilter() (default false; DiversifyingChildren*KnnVectorQuery return true since their nextParent() loop assumes the vector iterator landed on an accepted child, Seeded/Patience forward to their delegate). Create the filter weight through IndexSearcher#createWeight. exactSearch reports the docs it scored as TotalHits rather than acceptIterator.cost(), which would now count vectorless accepted docs. One consequence, AcceptDocs#cost() becomes the accepted doc count rather than accepted docs with a vector, the PR discusses what the HNSW reader does with it.
PR-3, KnnVectorValues: two overloads that work from the accept set instead of one ordinal at a time. getAcceptOrds(Bits, DocIdSetIterator), which the sparse off-heap values implement by leap-frogging the accept iterator against their IndexedDISI into a FixedBitSet over ordinals, asked for when the filtered searcher is going to run and the pass is cheaper than the lookups it removes. And acceptedOrdsIterator(Bits, DocIdSetIterator), which enumerates the accepted ordinals in order so the exhaustive scan scores the accept set rather than testing every ordinal; the scan moves to one class the two scanning readers share, values that cannot enumerate keep today's loop. On the int8 flat format, which has no graph and scans every filtered query, this is 1.7 to 17x at 0.5 to 5% accepted. Results identical.
PR-4, Lucene99HnswVectorsReader#search: weigh what the filtered graph search would cost against scoring every accepted vector, both estimated from what those loops do, instead of comparing an unfiltered visit estimate to the accept count. A reader that scored the whole accept set says so on the collector and the query does not score it again.
Not proposing: clamping AcceptDocs#cost() to the vector count (measured, no gain, the reader already clamps to graphSize), or #15592 style cost() avoidance (reverted in #15687). Can backport to 10.x if wanted.
Testing
Each PR carries its tests in BaseKnnVectorQueryTestCase (float, byte, MMap, seeded and patience variants) and ParentBlockJoinKnnVectorQueryTestCase, plus TestAcceptDocs. On the stacked branches core, join, sandbox and backward-codecs pass, and the knn query test classes pass ten iterations.
Summary
a filtered knn query on a segment with deletions builds its accept set one doc at a time instead of copying the cached filter's bitset. moreover, on a field where some docs have no vector it also ANDs a FieldExistsQuery into the filter, which turns the cached bitset into a fresh conjunction that can't be bulk copied either. both are O(docs in the segment) and sit in front of a search that's O(k log n), so on a big segment they cost more than the search itself, 1.7x and 2.5x per query in the benchmark. separately, for small filters the reader falls back to scanning every vector in the segment to score the few hundred accepted ones, and the threshold for doing that is a guess that's wrong by a factor of 2-5x on real data.
four PRs, the first two are a few lines each. all numbers below are milliseconds per query on one 200k-doc segment, k=100, and (Nx) is main divided by patched.
What happens
KnnFloatVectorQuery / KnnByteVectorQuery with a pre-filter build a per-leaf accept set in AcceptDocs.fromIteratorSupplier, then hand it to the codec. Five things go wrong on that path.
With deletions, the accept set is built one doc at a time. DocIdSetIteratorAcceptDocs.createBitSetAcceptDocsIfNecessary (AcceptDocs.java:177-182) passes iterator() to createBitSet, and with live docs iterator() is a FilteredDocIdSetIterator, which has no intoBitSet, so FixedBitSet#or falls back to nextDoc() per doc, and createBitSet then applies liveDocs a second time. One deleted doc in the segment is enough, for any accept set dense enough for the bit set branch (cost >= maxDoc >> 7). createBitSet already handles liveDocs, it should get the raw iterator.
The cached filter is never used as-is. AbstractKnnVectorQuery#rewrite (AbstractKnnVectorQuery.java:88-92) ANDs FieldExistsQuery(field) into the filter, so what reaches the accept set is a fresh ConjunctionDISI per query instead of the cached BitSetIterator, and ConjunctionDISI has no intoBitSet either. The conjunct came in with LUCENE-10382: Support filtering in KnnVectorQuery #656 for the exact search cost estimate, not for correctness: HNSW only scores graph ordinals and exactSearch intersects with the vector iterator anyway. It only survives when some leaf has a doc without a vector, otherwise FieldExistsQuery rewrites to MatchAllDocsQuery and drops out.
The filter weight itself is not cached. Same method, line 97: rewritten.createWeight(indexSearcher, ...) instead of indexSearcher.createWeight(...), so the query cache is consulted only for the clauses of a BooleanQuery filter, never for the filter. AbstractVectorSimilarityQuery (:152) goes through the searcher.
Small filters scan the whole segment. The query runs an exact search only when the filter accepts at most perLeafTopK docs (AbstractKnnVectorQuery.java:282). The reader has its own rule, HnswGraphSearcher#expectedVisitedNodes = log(graphSize) * k, and refuses the graph when the accept set is at most that (Lucene99HnswVectorsReader.java:369-372). But its fallback scans every vector of the segment testing the accept bits one by one (:382). So between perLeafTopK and log(graphSize) * k accepted docs, the query asks for an approximate search, the codec declines, and 200k vectors get tested to find 400 of them, with a DirectMonotonicReader lookup per ordinal on a field that has vectorless docs.
On a field where some docs have no vector, the filtered graph search tests acceptance through an off-heap lookup. Lucene99HnswVectorsReader#search (:365) hands the search scorer.getAcceptOrds(accepted), which for the sparse off-heap values is a lazy Bits whose get(ord) is acceptDocs.get(ordToDoc(ord)), a DirectMonotonicReader read. FilteredHnswGraphSearcher does that on every neighbour and 2-hop neighbour it looks at. At 2% selectivity that lookup is ~40% of the query on such a field (0.30 of 0.74 ms, async-profiler); the same query on a fully vectored field takes 0.40 ms.
1 and 2 compound: fixing 1 alone still walks a ConjunctionDISI per doc, fixing 2 alone still wraps the cached bit set in FilteredDocIdSetIterator on any segment with deletes.
Numbers
FilteredKnnVectorQueryBenchmark (added in PR-1): one segment, 200k docs, 128-dim random unit vectors, float HNSW with the default codec, k=100, pre-filter a TermQuery already in the LRUQueryCache. main @ 411013e, JDK 25 with --add-modules jdk.incubator.vector, AMD Genoa, each cell its own JMH process pinned to 10 vCPUs. ms per query.
Problems 1 to 3 (PR-1 fixes 1, PR-2 fixes 2 and 3), 3 forks per arm:
Same index, 5% deleted, across selectivities:
The gain scales with how many docs the filter accepts, since that is what the accept set build costs; below ~1% the graph search dominates. Rows with no deletions and no vectorless docs are the noise floor, nothing runs there (fork to fork spread is up to 13% at 0.45 ms, the 0.85x is that). PR-1 needs deletions, PR-2 needs a vectorless doc somewhere. Top-100 (doc, score) lists for 32 queries per cell are identical across the three arms.
the rows with deletions keep ~0.8 ms after both fixes: createBitSet's closing applyMask(liveDocs) runs per bit on DenseLiveDocs/SparseLiveDocs since #15413, same hole as #16282. #16593 fixes that separately, and with it these rows land on the no-deletion floor (2.07 -> 0.49 at 5% deleted)
Problem 4 (PR-3 fixes the scan, PR-4 the decision), PR-1+2 as the baseline, no deletions, 2 forks interleaved. PR-3 makes the reader's scan enumerate the accept set instead of testing every ordinal:
Recall against brute force over the accepted docs is 1.0 before and after, the scan was exact already, it just cost 5.5 to 45 times more. Above log(graphSize) * k accepted (about 1220 here) the reader takes the graph, and that is the wrong call for a while: at 4000 accepted, scoring the accept set is cheaper than the filtered walk on this corpus, and PR-4, which weighs the two instead of comparing the accept count to log(graphSize) * k, takes that cell from 0.389 to 0.131 ms on a dense field and 0.497 to 0.205 with 10% vectorless. By 10% accepted the graph wins and PR-4 leaves it alone (within 2%, same at 95%).
I first did problem 4 on the query side, raising the query's exact search threshold to log(maxDoc) * perLeafTopK. It measured 3.5 to 26x over main in the band but it is the wrong place: once the reader's batched scan exists, the query's per-doc exactSearch pre-empts it and costs 1.15 to 2.1x more for the same answer (0.038 vs 0.021 ms at 200 accepted, 0.074 vs 0.047 at 1000, 0.879 vs 0.412 on 2-3 leaves at k=1000 and 2%). So the decision stays in the reader, which is the only layer that can see the graph.
Problem 5 (also PR-3), same index with 10% vectorless docs, the accepted ordinals materialised once per query before the filtered graph search:
Dense field unchanged, 0.440 -> 0.441. The pass is one advance per accepted doc plus a bit set over the vectors, so it is gated on the filtered searcher being chosen and the accept set being small enough that the lookups it removes outnumber the advances (about 2sqrt(expectedVisitedNodesgraphSize), 29.5k accepted on this index); above that it does nothing.
Where this was found: elasticsearch 9.4.4 / lucene 10.4.0, a 5.8M doc index shaped like production (10.6% docs without a vector, filter accepting 99.9%, six knn clauses, k=4000), 430 -> 289 cpu-ms per request with PR-1, 182 with PR-1+2 (2.37x). That multiplier is elasticsearch's, it runs its cancellation check inside the per-doc walk (ExitableDirectoryReader.checkAndThrowWithSampling was 40% of the unpatched profile, FilteredDocIdSetIterator.nextDoc 37%). Plain lucene has no such wrapper, the JMH numbers above are the ones to expect here. PR-3 and PR-4 have not been measured at that scale.
Proposed fix
Four PRs, stacked, all against main:
PR-1, AcceptDocs: pass iteratorSupplier.get() to createBitSet. +4/-1, with a test that counts nextDoc() calls on the source iterator and fails on main when the segment has deletions. Adds the benchmark.
PR-2, AbstractKnnVectorQuery: drop the conjunct behind protected boolean requiresVectorPresenceInFilter() (default false; DiversifyingChildren*KnnVectorQuery return true since their nextParent() loop assumes the vector iterator landed on an accepted child, Seeded/Patience forward to their delegate). Create the filter weight through IndexSearcher#createWeight. exactSearch reports the docs it scored as TotalHits rather than acceptIterator.cost(), which would now count vectorless accepted docs. One consequence, AcceptDocs#cost() becomes the accepted doc count rather than accepted docs with a vector, the PR discusses what the HNSW reader does with it.
PR-3, KnnVectorValues: two overloads that work from the accept set instead of one ordinal at a time. getAcceptOrds(Bits, DocIdSetIterator), which the sparse off-heap values implement by leap-frogging the accept iterator against their IndexedDISI into a FixedBitSet over ordinals, asked for when the filtered searcher is going to run and the pass is cheaper than the lookups it removes. And acceptedOrdsIterator(Bits, DocIdSetIterator), which enumerates the accepted ordinals in order so the exhaustive scan scores the accept set rather than testing every ordinal; the scan moves to one class the two scanning readers share, values that cannot enumerate keep today's loop. On the int8 flat format, which has no graph and scans every filtered query, this is 1.7 to 17x at 0.5 to 5% accepted. Results identical.
PR-4, Lucene99HnswVectorsReader#search: weigh what the filtered graph search would cost against scoring every accepted vector, both estimated from what those loops do, instead of comparing an unfiltered visit estimate to the accept count. A reader that scored the whole accept set says so on the collector and the query does not score it again.
Not proposing: clamping AcceptDocs#cost() to the vector count (measured, no gain, the reader already clamps to graphSize), or #15592 style cost() avoidance (reverted in #15687). Can backport to 10.x if wanted.
Testing
Each PR carries its tests in BaseKnnVectorQueryTestCase (float, byte, MMap, seeded and patience variants) and ParentBlockJoinKnnVectorQueryTestCase, plus TestAcceptDocs. On the stacked branches core, join, sandbox and backward-codecs pass, and the knn query test classes pass ten iterations.
I'll open the PRs if the approach looks right.