kaivalnp opened a new pull request, #12820: URL: https://github.com/apache/lucene/pull/12820
### Description In KNN queries with a pre-filter, we first perform an approximate graph search and then [fallback](https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java#L130-L137) to exact search based on the cost of the filter (if we visit more nodes than what the filter matches, it is cheaper to perform an exact search) Graph traversal performs some work (like scoring nodes, maintaining the `topK`, etc) which can be re-used from exact search - on the fact that any node which is "visited but not collected" will not be collected from exact search as well.. If we start exact search from the previous state (current `topK` vectors from graph search) - we can ignore vectors already rejected (i.e. visited) from graph traversal, and save on their similarity computations (duplicate work) plus re-use the existing min-max heap from the `KnnCollector` I performed some benchmarks using `KnnGraphTester` by indexing 100k vectors of 100 dimensions, and ran 10k queries with a `topK` of 1000 with a range of `selectivity` values (denoting what proportion of all documents are accepted by the filter): #### baseline ``` recall latency nDoc fanout maxConn beamWidth topK selectivity type 0.980 4.84 100000 0 16 100 1000 1.000 post-filter 0.988 11.94 100000 0 16 100 1000 0.300 pre-filter 0.988 14.09 100000 0 16 100 1000 0.250 pre-filter 0.995 20.01 100000 0 16 100 1000 0.200 pre-filter 1.000 18.86 100000 0 16 100 1000 0.150 pre-filter 1.000 12.94 100000 0 16 100 1000 0.100 pre-filter ``` #### candidate ``` recall latency nDoc fanout maxConn beamWidth topK selectivity type 0.980 4.86 100000 0 16 100 1000 1.000 post-filter 0.989 12.16 100000 0 16 100 1000 0.300 pre-filter 0.989 13.64 100000 0 16 100 1000 0.250 pre-filter 0.994 19.04 100000 0 16 100 1000 0.200 pre-filter 1.000 17.24 100000 0 16 100 1000 0.150 pre-filter 1.000 11.61 100000 0 16 100 1000 0.100 pre-filter ``` The gains may be beneficial only when `topK` is large and the filter is restrictive (more number of nodes visited -> more chances of falling back to exact search -> more duplicate similarity computations saved) -- 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-unsubscr...@lucene.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
