john-mlika opened a new issue, #16586:
URL: https://github.com/apache/lucene/issues/16586
### 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.
1. 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.
2. 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 #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.
3. 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.
4. 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.
5. 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 @ 411013eebd, JDK 25
with --add-modules jdk.incubator.vector, AMD Genoa, each cell its own JMH
process pinned to 10 vCPUs. ms per query.
```
java --add-modules jdk.incubator.vector -jar lucene-benchmark-jmh-*.jar
FilteredKnnVectorQueryBenchmark \
-p filterSelectivity=0.95 -p vectorlessFraction=0.1 -p
deletedFraction=0.05 -f 3
```
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 | PR-1 |
PR-1+2 |
|---|---|---|---|---|---|
| 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 | PR-1 | PR-1+2 |
|---|---|---|---|---|
| 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.
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 | 10% of docs without a vector |
|---|---|---|
| 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 | after |
|---|---|---|
| 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 2*sqrt(expectedVisitedNodes*graphSize), 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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
