[C API] Add svs_index_search_range (radius search)

Aperta
  • Qualcosa non va?
#425 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 5 giorni

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
25/100
Tipo di issue
Funzionalità
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
c, cpp
Ambito
api, search

Direzione di ricerca

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.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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.
Lingua principale
C++
Stelle
241
Fork
48
Merge medio
4g 21h
PR unite (30g)
11

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di intel/ScalableVectorSearch

Tutte le issue di intel/ScalableVectorSearch

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.