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: [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]
