Use Lucene's MultiLeafCollector to speed up concurrent-segment exact search

[shatejas]

Lucene introduced MultiLeafCollector to optimize concurrent segment search. While this cannot be used for faiss due to JNI layer, this can possibly be leveraged for exact search.

This can further reduce multiple iterations to reduce to topK in NativeEngineQuery

• https://github.com/opensearch-project/k-NN/blob/main/src/main/java/org/opensearch/knn/index/query/nativelib/NativeEngineKnnVectorQuery.java#L71
• https://github.com/opensearch-project/k-NN/blob/main/src/main/java/org/opensearch/knn/index/query/nativelib/NativeEngineKnnVectorQuery.java#L79

To do this correctly, involves refactoring the code and also possible collecting ANN results in the collector. A POC os recommended to start with to assess the possibility/challenges and latency benefits of this should be benchmarked.

[navneet1v]

@shatejas multi-leaf collector helps in identifying the min competitive scores across different segments and helps to identify if a neighborhood in the HNSW graph should be explored or not.

can you please add some more details/your thoughts how multi-leaf collector will be useful with exact search? Since in exact search we need to do the full scan and to even know the score to be a min competitive score we have to do the vector distance calculation. Hence I am little confuse on the usage of Multi-leaf collector with exact search.

[shatejas]

@navneet1v I see your point, Multileaf collector does not hold docIds in global queue.

The idea here is to use a global max heap queue of size k, and pass the queue to each segment. As we add data in the local minheap queue we also update global queue, that way at the end of it we have k results without again iterating on those segment results. But I realize this might need a custom collector here. But it will be similar to what MultiLeafCollector does, i.e maintaining a global queue and relying on subcollector to maintain a minheap if required.

There is no intention to use min competitive similarity here. Its just leveraging the global queue to cut out a few loops and see if we can shave off some time for Exact search

This definitely needs a POC to see possibilities

[navneet1v]

There is no intention to use min competitive similarity here. Its just leveraging the global queue to cut out a few loops and see if we can shave off some time for Exact search

This looks like something. Would like to know in exact search how you are thinking? because saving some loops might help, but at the same the time for exact search latency comes from reading vectors and then computing the scores. can you share more details on what loops and things you are thinking will be cut off.