MEP 33 -- Support Range Search

Current state: ["Under Discussion"]

ISSUE: #17599

PRs: 

Keywords: range search, radius, query

Released: 

Summary(required)

At present, the behavior of Query() in Milvus is to return TOPK most similar results for each vector to be queried.

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

This function can be considered as a "superset" of the existing query function, because if you sort the results of range search and take the first `topk` results, they will be identical with the return result of the existing query function.

The result output of this MEP is different from the original query result. The original query result is with fixed length `nq * topk`, while the return result of range search is variable length. In addition to `IDs` / `distances`, `lims` is also returned to record the offset of the query result of each vector in the result set. Another MEP pagination will uniformly process the results of `Query` and `QueryByRange` and return them to the client, so the processing of the returned results is not within the scope of this MEP discussion.

Motivation(required)

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

Public Interfaces(optional)

• No interface change in Milvus and all SDKs

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

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

  default_index = {"index_type": "HNSW", "params":{"M": 48, "efConstruction": 500}, "metric_type": "L2"}
  collection.create_index("float_vector", default_index)
  collection.load()  
  search_params = {"metric_type": "L2", "params": {"ef": 32, "radius": 888}}
  res = collection.search(vectors[:nq], "float_vector", search_params, limit, "int64 >= 0")

• Need add new interface `QueryByRange()` in knowhere

  virtual DatasetPtr
  QueryByRange(const DatasetPtr& dataset, const Config& config, const faiss::BitsetView bitset);

There is one proposal that not to add new interface QueryByRange(), but reusing interface Query() for range search. Considering the implementation in Knowhere, we don't accept this proposal, because not all types of index support range search.

By now, Knowhere can support 13 types of index, but only 8 of them can support range search (the cell filled with BLUE):

If add new interface QueryByRange(),  we can add following code into "VecIndex.h". If QueryByRange() is called for an index type which does not support range search, a knowhere exception will be thrown out.

virtual DatasetPtr
QueryByRange(const DatasetPtr& dataset, const Config& config, const faiss::BitsetView bitset) {
    KNOWHERE_THROW_MSG("QueryByRange not supported yet");
}

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 query
    }
}

This is not a good design for knowhere.

Design Details(required)

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 parameter "param" on the SDK side.

The following figure shows the call stack diagram of vector query in segcore, and the BLACK part shows the functions that have 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 can't use knowhere IDMAP to realize the brute force search function. You can only re-realize the full set of logic of brute force search by yourself. To implement range search, you 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 query, and then call the Query() & QueryByRange() interface provided by the IDMAP, and the index will be destroyed immediately after it is used up. 

There is another MEP 34 -- IDMAP/BinaryIDMAP Enhancement describing this proposal.

查询结果的处理

Query 返回的查询结果有２种，一种为 SubSearchResult，用于存放 segment 中每个 chunk 的查询结果。

需要添加成员变量 "is_range_search_" 和 "lims_"，以及成员函数 "merge_range()" 和 "merge_range_impl()"。

class SubSearchResult {
    ... ...
    static SubSearchResult
    merge(const SubSearchResult& left, const SubSearchResult& right);

    void
    merge(const SubSearchResult& sub_result);

    static SubSearchResult
    merge_range(const SubSearchResult& left, const SubSearchResult& right);		// <==== new added

    void
    merge_range(const SubSearchResult& sub_result);								// <==== new added

 private:
    template <bool is_desc>
    void
    merge_impl(const SubSearchResult& sub_result);

    void
    merge_range_impl(const SubSearchResult& sub_result);						// <==== new added

 private:
    bool is_range_search_;				// <==== new added
    int64_t num_queries_;
    int64_t topk_;
    int64_t round_decimal_;
    MetricType metric_type_;
    std::vector<int64_t> seg_offsets_;
    std::vector<float> distances_;
    std::vector<size_t> lims_;			// <==== new added

另一种为 SearchResult，用于存放该 segment 的查询结果。

需要添加成员变量 "is_range_search_" 和 "lims_"。

struct SearchResult {
   　... ...
 public:
    int64_t total_nq_;
    int64_t unity_topK_;
    void* segment_;

    // first fill data during search, and then update data after reducing search results
	bool is_range_search_;				// <==== new added
    std::vector<float> distances_;
    std::vector<int64_t> seg_offsets_;
    std::vector<size_t> lims_;			// <==== new added
    ... ...
};

在 Query node 中还需要实现多个 segment 之间的 reduce_range()；

在 Proxy 中还需要实现多个 SearchResult 之间的 reduce_range()；

关于输出结果的处理，需要和 Pagination 的具体实现方案一起讨论。

Compatibility, Deprecation, and Migration Plan(optional)

• What impact (if any) will there be on existing users?
• If we are changing behaviors how will we phase out the older behavior?
• If we need special migration tools, describe them here.
• When will we remove the existing behavior?

Test Plan(required)

Describe in a few sentences how the MEP will be tested. We are mostly interested in system tests (since unit tests are specific to implementation details). How will we know that the implementation works as expected? How will we know nothing broke?

已为 range search 生成了基准测试数据集 sift-128-eucliean-range.hdf5 和 sift-4096-hamming-range.hdf5

Rejected Alternatives(optional)

If there are alternative ways of accomplishing the same thing, what were they? The purpose of this section is to motivate why the design is the way it is and not some other ways.

References(optional)

Briefly list all references