[C API] Add svs_index_search_range (radius search)

オープン
  • 何か問題がありますか？
#425 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 5 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
25/100
issue の種類
機能追加
明瞭さ
おおむね明確
活発さ
活発
技術スタック
c, cpp
領域
api, search

調査の方向性

Start with the existing svs_index_search_topk declaration in svs_c.h (around line 1316) and the CSR svs_search_results_t layout, then compare with DynamicVamanaIndexImpl::range_search in bindings/cpp/src/dynamic_vamana_index_impl.h. The new entry point must follow the same buffer-reuse and threadpool rules, add the max_results cap signal, and honour the per-metric radius contract. Done means a declared and implemented svs_index_search_range with tests for L2, dot product and cosine, including the cap-reached case.

索引モデルが issue の本文から書いたものです。

説明

Summary

Please add a radius search to the C API: given a query and a threshold, return every vector within that threshold. Today the only C API search is svs_index_search_topk (svs_c.h:1316). C_API_Design.md (line 300) lists range search as a future extension, and the CSR layout of svs_search_results_t was designed to carry variable per-query result counts for it (svs_c.h:365-368).

Why now

valkey-search added range queries in valkey-io/valkey-search#985, FT.SEARCH ... @v:[VECTOR_RANGE <radius> $blob], merged 2026-10-02. Every vector index now has to implement VectorBase::SearchRange(query, radius, filter).

valkey-search's SVS_VAMANA index uses only the C API. Without a radius search there, it approximates one:

  1. Run svs_index_search_topk with k up to the configured cap, search.max-nonvector-search-results-fetched (100,000 by default).
  2. Keep the results within the radius.
  3. When the cap is reached with its farthest result still in range, scan every stored vector exactly.

This works, but it sizes the search by the cap rather than by how many vectors are actually in range, and the exhaustive scan is O(N).

Ask

A C API entry point alongside svs_index_search_topk, for example:

SVS_API bool svs_index_search_range(
    svs_index_h index,
    const float* queries,
    size_t num_queries,
    float radius,
    size_t max_results,              /* per query; 0 = no limit */
    svs_search_results_t* out_results,
    svs_search_params_h search_params /*=NULL*/,
    svs_id_filter_i id_filter /*=NULL*/,
    svs_error_h out_err /*=NULL*/
);

with this contract:

  1. Results. Per-query counts vary, written in the existing CSR layout (offsets, total_results). Ordering within a row doesn't matter to us.
  2. Radius is in the index metric's own units, and documented per metric. For L2, results have distance <= radius. For dot product and cosine, results have similarity >= radius. A non-positive threshold must be accepted for dot product and cosine: valkey-search's distance radius r maps to the similarity threshold 1 - r, which is <= 0 whenever r >= 1.
  3. max_results cap. When a query has more than max_results vectors in range, return max_results of them and report that the cap was reached, for example through a flag or a per-query count. valkey-search then falls back to an exact scan, so it needs to know the result is incomplete rather than get a silently truncated one.
  4. Threading. Run on the threadpool installed with svs_index_builder_set_threadpool_custom, as svs_index_search_topk does. valkey-search installs a pool that runs on the calling thread so SVS starts no threads of its own.
  5. Filtering. Same svs_id_filter_i contract as svs_index_search_topk with filter_rate() <= 0 (intel/ScalableVectorSearch#415): no sampling, no early exit on hit rate, and return the matches found.

How this differs from the C++ range search

The C++ runtime bindings already provide range search: DynamicVamanaIndex::range_search (bindings/cpp/include/svs/runtime/vamana_index.h:88), implemented in DynamicVamanaIndexImpl::range_search (bindings/cpp/src/dynamic_vamana_index_impl.h:216). It walks batch_iterator in distance order, in batches of the search window size, and stops at the first result outside the radius. That traversal suits this request too. What differs is the contract around it:

C++ range_search This request (C API)
Interface C++ virtual method; results through a ResultsAllocator callback C function; results in svs_search_results_t CSR, with the buffer-reuse and struct_size rules svs_index_search_topk already follows
Radius validation Rejects radius <= 0 for every metric (line 226) Accepts any finite threshold for dot product and cosine (similarity can be <= 0); keeps > 0 for L2
Radius units Not documented per metric Documented per metric: distance <= for L2, similarity >= for dot product and cosine
Threading Runs on default_threadpool() (line 297) Runs on the threadpool installed on the index, like svs_index_search_topk
Result size Unbounded; reserves the search buffer's capacity per query and grows from there Capped by max_results, with a signal when the cap was reached
Filter IDFilter::is_member only svs_id_filter_i, with the filter_rate() <= 0 contract from #415
Errors Status / StatusException svs_error_h, like the other C API calls

Consumer context

  • valkey-search (ALGORITHM SVS_VAMANA) is built on the C API submodule, pinned at 8285340.
  • The current SearchRange fallback is in eshenayo/valkey-search (src/indexes/vector_svs.cc), part of the upstream draft valkey-io/valkey-search#1577.
  • With a native call, VectorSVS::SearchRange would become a single svs_index_search_range call. It would fall back to the exact scan only when SVS reports the cap was reached.
主要言語
C++
スター
241
フォーク
48
平均マージ
4日 21時間
マージ済み PR（30日）
11

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

intel/ScalableVectorSearch のほかの issue

intel/ScalableVectorSearch の issue をすべて見る

似ている issue

C++ の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。