Page Comparison

Current state: ["Under Discussion"]

...

If call range search API with unsupported index types or unsupported metric types, knowhere will throw out exception.

In Knowhere, only one parameter "radius" is passed in via config, and range search will return all un-sorted results with distance "better" than radius.

...

The valid scope for "radius" is defined as: -1.0 <= radius <= float_max

2. QueryByRange()

This API does range search for index, it returns all unsorted results with distance "better than radius" (for IP: > radius; for others: < radius).

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

...

This API does range search for no-index dataset, it returns all unsorted results with distance "better than radius" (for IP: > radius; for others: < radius).

static DatasetPtr
RangeSearch(const DatasetPtr base_dataset,
            const DatasetPtr query_dataset,
            const Config& config,
            const faiss::BitsetView bitset);

...

Range search completely reuses the call stack from SDK to segcore.

Compatibility, Deprecation, and Migration Plan(optional)

There is no compatibility issue.

...

With above solution, user can get maximum 16384 range search results in one call.

If user wants to get more than 16384 range search results, they can do like this: (use L2 as an example)

• NQ = 1

1st call with (radius_low_bound = 0.0, radius_high_bound = inf), get result distances like this: {d(0), d(1), d(2), ..., d(n-1)}

2nd call with (radius_low_bound = d(n-1), radius_high_bound = inf), get result distances like this: {d(n), d(n+1), d(n+2), ..., d(2n-1)}

3rd call with (radius_low_bound = d(2n-1), radius_high_bound = inf), get result distances like this: {d(2n), d(2n+1), d(2n+2), ..., d(3n-1)}

...

• NQ > 1 (suppose NQ = 2)

1st call with (radius_low_bound = 0.0, radius_high_bound = inf), get result distances like this: 

{d(0,0), d(0,1), d(0,2), ..., d(0,n-1), d(1,0), d(1,1), d(1,2), ..., d(1,n-1)}

2nd call with (radius_low_bound = min{d(0,n-1), d(1,n-1)}, radius_high_bound = inf), get result distances like this: 

{d(0,n), d(0,n+1), d(0,n+2), ..., d(0,2n-1), d(1,n), d(1,n+1), d(1,n+2), ..., d(1,2n-1)}

3rd call with (radius_low_bound = min{d(0,2n-1), d(1,2n-1)}, radius_high_bound = inf), get result distances like this:

{d(0,2n), d(0,2n+1), d(0,2n+2), ..., d(0,3n-1), d(1,2n), d(1,2n+1), d(1,2n+2), ..., d(1,3n-1)}

...

The result of 2nd call will have some duplications with the result of 1st call, use need do duplication check and remove them.

Compatibility, Deprecation, and Migration Plan(optional)

There is no compatibility issue.

Test Plan(required)

Knowhere

1. Add new unittest
2. Add benchmark using range search dataset

...

1. Need implement Merge operation for chunk, segment, query node and proxy
2. Memory explosion caused by Merge
3. Many API modification caused by invalid topk parameter

...

2. Many API modification caused by invalid topk parameter

Current proposal is better than the previous one in all respects.

Others

Because the result length of range search from knowhere is variable, knowhere plan to afford another API to return the range search result count for each NQ.

If there is user request to get all range search result in one call, query node team will afford another solution to save knowhere's output to S3 directly.

References(optional)

...