Page History

...

The purpose of this MEP is to realize "range search" function. The user User specifies a query "radius", and Milvus queries does "range search" and returns all results with distance better than this "radius" ("< > radius" for "L2"; "> IP, "< radius" for "IP")other metric types).

This function can be regarded as a "superset" of the existing query search function, because if sort the results of range search and take the first `topk` results, we get identical results comparing with current query search function.

The result output of this MEP is different from the original query resultsearch and range search are different. The original query search result is with fixed length `nq 'nq * topk`topk', while the return result results of range search is with variable length. In addition to `IDs` / `distances`, `lims` Except 'IDs' and 'distances', 'lims' is also returned which is used to record the offset of the query range search result of each vector in the result set.

Another MEP pagination will uniformly process the results of `Query` and `QueryByRange` 'search' and 'range search' and return them to the client, so the result processing of the returned results is not within the scope of will not be discussed in this MEP discussion.

Motivation(required)

A user User (developing recommendation system) asked for ask Milvus to realize the function of querying searching by distance, that is, to return all results whose with similarity is better than a certain "radius".

...

• No interface change in Milvus and all SDKs

We reuse the interface `Query()` to realize the function of range searchSDK interface "search" to do "range search", so the interface of Milvus and all SDKs need not to be changed. We only need add "radius" information to into params. When "radius" is specified, the parameter "limit" setting is ignored.

As shown in the following figure, set "radius: 888" in search_ params.params.

...

...

But if we reuse interface Query() for range search, then the implementation of Query() for all index types will be changed like this:

virtual DatasetPtr
Query(const DatasetPtr& dataset, const Config& config, const faiss::BitsetView bitset) {
    if (radius exist in config) {
        // do range search
    } else {
        // do querysearch
    }
}

This is not a good code design for Ｋnowhere.

...

The following figure shows the complete call stack of a search request from SDK to segcore. Range search completely reuses this call stack without any changes. Range search only needs to put the parameter "radius" into the query search parameter "param" on the SDK side.

...

The following figure shows the call stack diagram of vector query search in segcore, and the BLACK part shows the functions that have already been implemented.

For sealed segment, to realize the range search function, knowhere needs to provide the interface QueryByRange();

For growing segment, because there is no index created, you we can't use knowhere IDMAP to realize the brute force search function. You We can only re-realize the full set of logic of brute force search by yourselfourselves. To implement range search, you we need to implement the function shown in the RED part.

Another solution is that Knowhere provides a new IDMAP index, which does not need to insert vector data, but only needs to specify the external memory address of vector data. Growing segment can temporarily generate this kind of index during querysearch, and then call the Query() & QueryByRange() interface provided by the IDMAP, and the index will be destroyed immediately after it is used up. 

...

It is used to store each chunk's query search result in a segment. 

Need add a new field "lims_" and a new method "merge_range()". Because the behavior of merge between Query() and QueryByRange() differs a lot. For Query(), after merging two "nq * topk" results, we still get "nq * topk" result. But for QueryByRange(), when merge A (with "n0" results) and B (with "n1" results), we get "n0 + n1" results.

...

test/milvus/ann_hdf5/sift-128-euclidean-range.hdf5

test/milvus/ann_hdf5/glove-200-angular-range.hdf5

test/milvus/ann_hdf5/binary/sift-4096-hamming-range.hdf5

...