[C API] `svs_index_search_topk`: document the filtered-search contract for `filter_rate() <= 0`

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

I maintainer di solito rispondono entro 5 giorni

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
3/5
Tempo stimato
1-2 giorni
Idoneità per principianti
65/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
cpp
Ambito
backend-api-design

Direzione di ricerca

Start with bindings/c/src/filtered_search.hpp and the filter_rate contract in svs_c.h; trace both early-exit sites described in the issue. Then inspect bindings/c/tests/ for the relevant search tests. Done means the tests cover both early exits and verify partial results, while the header documents the contract and the TODO is resolved.

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

Descrizione

Summary

Please document what svs_index_search_topk does with an ID filter whose filter_rate() is <= 0 (or NULL). valkey-search relies on this behaviour, and the header doesn't state it.

The contract text in svs_c.h (lines 1297-1303 at 8285340) only covers filter_rate > 0.0: "If the actual observed filter hit rate is less than the provided filter_rate value, the function returns an empty result set." It says nothing about 0.0.

Current behaviour for filter_rate() <= 0

Code references are to main at 8285340.

  • estimate_initial_batch_size (bindings/c/src/filtered_search.hpp:92-97) skips the ID sampling and returns the batch hint, so the pre-search early exit (:185-190) cannot trigger.
  • hit_rate_sufficient (:65-69) returns true for filter_rate <= 0, so the in-loop exit that resets found = 0 (:218-222) cannot trigger either.
  • The search therefore runs until k filter-passing hits are found or the batch iterator is exhausted, and returns the hits found. That can be fewer than k, and is reported per query through offsets / total_results.

Ask

  1. Document the above in svs_c.h next to the existing filter_rate > 0.0 text, so it becomes part of the contract:
    • no sampling, and no early exit on the observed hit rate;
    • the hits found are returned, possibly fewer than k.
  2. Resolve the TODO at filtered_search.hpp:216-217 for the <= 0 case. A short comment stating the guarantee is enough.
  3. Add a test in bindings/c/tests/ asserting that, with filter_rate() returning 0.0 and a selective filter, a query returns a non-zero number of hits, all of which pass the filter.

No behaviour change is requested. Whether the positive-hint path should return partial results, or drop the ID sampling, is SVS's call. If it does change, an opt-in parameter that keeps today's default would avoid surprising other integrations.

Consumer context

valkey-search (ALGORITHM SVS_VAMANA) passes an ID filter built from query predicates and returns 0.0 from filter_rate. Its query planner already knows how many keys qualify before it calls SVS:

  • very selective filters (below roughly 0.001 * N qualifying keys) go to an exact brute-force path and never reach SVS;
  • for the rest, valkey-search sizes the first batch itself through the per-query search window (batch_hint = max(k, search_window_size) in bindings/c/src/index_vamana.cpp).

So valkey-search needs SVS to do no sampling or selectivity estimation, only to keep the <= 0 behaviour stable.

Scope change

This issue originally asked for partial results when the observed hit rate falls below a positive filter_rate. After the discussion below, valkey-search will handle selectivity on its own side, so the ask is narrowed to documenting the <= 0 contract. The ID sampler referenced in the original text has moved to bindings/c/src/index_vamana.cpp (around lines 78 and 140).

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.