[C API] Add svs_index_search_range (radius search)

Abierto
  • ¿Algo no está bien?
#425 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 5 días

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
25/100
Tipo de issue
Nueva funcionalidad
Claridad
Bastante claro
Estado de actividad
Activo
Stack tecnológico
c, cpp
Área
api, search

Línea de trabajo

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.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.
Lenguaje dominante
C++
Estrellas
241
Forks
48
Merge medio
4 d 21 h
PR fusionados (30 d)
11

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de intel/ScalableVectorSearch

Todos los issues de intel/ScalableVectorSearch

Issues similares

Más issues de C++

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.