[Latency Improvement Oppurtunity] Improve filter search performance when filter results is matching all the documents in the segment

[navneet1v]

Description

Currently when filtered vector search is run, we run the filters to find out the relevant filter ids and see if we can do ANN search or exact search for each segment. The identified filterIds are passed to ANN search so that we can do filter while searching.

But in case when lets say filter matched all the docIds in the segment, we can avoid few things:

1. Converting the filterIds bitmap to filterIds array.
2. Validating should we do ANN search or Exact search.

2, is very very cheap(as it has bunch of if else check) but 1 can add latency(exact latency is not identified as of now) if the segment is large enough because we need to iterate over the bitmap to find the docids and pass it till the C++ layer. There are some conversion that happen in c++ layer ref: https://github.com/opensearch-project/k-NN/blob/main/jni/src/faiss_wrapper.cpp#L465-L490.

Solution

We can avoid all this computation by adding a simple check to see if max doc and filter bitmap size is same. If both of them are same, we can just to simple ANN search.

[luyuncheng]

We meet the same situation. and in some scenarios filters cause OOM error. we are happy to optimize this issue

[luyuncheng]

@navneet1v
hi, in #1402 i propose some ideas to optimize the latency and avoid some OOM scenarios.

[navneet1v]

@luyuncheng Its pretty interesting that you guys are getting OOM. My main idea of optimization here was if at a segment level no docs are getting filtered its better to do ANN search without filters.

I will try to look into the PR which you have raised. But on a high level can you add what is the optimization you are thinking in the PR you raised.

[weiwang118]

This issue is assigned to me and I will complete it by Christmas.