You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "Pranshu-S (via GitHub)" <gi...@apache.org> on 2026/10/19 12:57:24 UTC
[PR] Optimize KnnVectorsQuery to reuse kNN filter accept docs on optimistic re-entry and skip exactly-searched leaves [lucene]
Pranshu-S opened a new pull request, #16866:
URL: https://github.com/apache/lucene/pull/16866
### Description
<!--
If this is your first contribution to Lucene, please make sure you have reviewed the contribution guide.
https://github.com/apache/lucene/blob/main/CONTRIBUTING.md
-->
AbstractKnnVectorQuery searches a filtered KNN query in up to two passes per leaf (segment):
1. [Pass 1](https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java#L114-L118) — each leaf runs an optimistic reduced-budget search (perLeafTopK instead of full k).
2. [Pass 2 (re-entry)](https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java#L137-L140) — leaves whose pass-1 results are still competitive with the global top-K get searched again to recover the full k results for that leaf.
Before this change, both passes independently called [createAcceptDocs() ](https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java#L257-L269)for a leaf with a filter present, which:
- re-ran the filter's Weight.scorer(ctx) to get a fresh iterator,
- re-materialized it into an AcceptDocs/bitset, and
- recomputed cost().
For a leaf that re-enters, this means the filter is evaluated twice — once in pass 1, once again in pass 2 — even though the filter's result for that leaf cannot have changed. For non-trivial filters (anything more expensive than a cached bitset — e.g. compound boolean/range/geo filters), this is pure duplicated work on the query's critical path.
Separately, a leaf that fell back to exact search in pass 1 (because the filtered candidate set was too small, or the approximate search blew its visit budget) can never be improved by re-entering — its results are already exhaustive — yet it was still a candidate for re-entry consideration.
### Optimisation Results
```auto
=======================================================================
metric baseline(n=5) candidate(n=5) delta pct
------------------ ----------------- ----------------- ------ -----
ms/query 69.908±0.059 63.766±0.070 -6.143 -8.8%
hits/query 50.000±0.000 50.000±0.000 +0.000 +0.0%
leaves 10 10
num_segments 10 10
topK 50 50
queries 300 300
recall(hits==topK) 1.000 (identical)
=======================================================================
```
In practice this maps to setups where segments correlate with the vector-space neighborhoods being searched such as -
- Time-ordered / append-only indexes where queries skew toward recent data (news, feeds, logs, trending catalogs) — segments are roughly chronological, so a query's neighbors cluster in the newest segment(s).
- Multi-tenant / partitioned indexes where one tenant's documents land together in the same ingest-time segments.
- Index-sorted or vector-clustered layouts (e.g. indexSort, BP/vector reordering, or data already grouped by topic/category) that physically co-locate similar vectors into the same segment.
- Combined with expensive query-time filters — compound boolean/range/geo filters, ACL/permission filters, or any filter without a cheap cached bitset.
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Optimize KnnVectorsQuery to reuse kNN filter accept docs on optimistic re-entry and skip exactly-searched leaves [lucene]
Posted by "github-actions[bot] (via GitHub) via issues" <is...@lucene.apache.org>.
github-actions[bot] commented on PR #16866:
URL: https://github.com/apache/lucene/pull/16866#issuecomment-6591996448
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!
--
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: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org