[C API] Filter-aware Vamana search: evaluate the ID filter during graph traversal

Ouverte
  • Quelque chose ne va pas ?
#420 0 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 5 jours

Personne n'a encore pris cette issue.

Évaluation

Difficulté
5/5
Temps estimé
Plus d'une semaine
Accessibilité débutants
15/100
Type d'issue
Fonctionnalité
Clarté
Plutôt claire
Activité
Active
Stack technique
c, cpp
Domaine
api, search

Piste de recherche

Start with filtered_topk_search in bindings/c/src/filtered_search.hpp, which applies the filter only after batches are produced, and with the svs_id_filter_t interface and svs_index_search_topk in svs_c.h. The graph search itself, where admission and termination would need to change, lies outside the payload. Done means an opt-in mode that gates result admission inside the search, with new tests in bindings/c/tests/ for returned ids passing the filter, fewer than k results, and an exclusion filter, plus a recall benchmark against the batch path.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

Summary

Add an opt-in filtered search mode in which the ID filter decides which candidates enter the result set during the Vamana graph search, and the search's stopping rule counts only filter-passing results. Today svs_index_search_topk searches without the filter and filters the batches afterwards. The existing behaviour should stay the default.

Current behaviour

With an ID filter, filtered_topk_search (bindings/c/src/filtered_search.hpp:194-223 at 8285340) does the following:

  • opens a batch iterator on the unfiltered index;
  • requests batches of nearest candidates;
  • calls is_member() on each candidate after the batch is produced;
  • keeps going until k hits are found or the iterator is exhausted.

The graph search itself never sees the filter: its beam and its termination are driven by all candidates, whether they pass the filter or not. With a selective filter, most of the search effort goes into candidates that are then discarded. Batch sizing (estimate_batch_size) adapts to the observed hit rate, but the search beneath it stays unfiltered.

Reference: how hnswlib does it

In hnswlib's base-layer search (third_party/hnswlib/hnswalg.h:552-578 in eshenayo/valkey-search@91914c7):

  • every closer candidate still goes into the traversal frontier (candidate_set), so edge expansion is not gated by the filter;
  • the filter only decides whether a candidate is admitted to the result heap (top_candidates);
  • because the stopping rule (top_candidates.size() < ef || lowerBound > dist) is evaluated over filter-passing results only, a selective filter automatically makes the search go wider.

valkey-search's HNSW backend relies on this: a hybrid KNN query returns up to k matching results from one traversal.

Why it matters

In the valkey-search RFC for SVS_VAMANA (valkey-io/valkey-search#1256), reviewers called the lack of traversal-time filtering a significant limitation, because a high percentage of production vector queries are hybrid (vector + tag/numeric predicates). They also asked for it in time for the initial release:

The same mechanism serves a second use raised in that review: during an index rebuild, querying the old and new instances side by side and merging the results. That requires the old instance to exclude entries that have already been mutated in the new one, i.e. a predicate evaluated before an entry enters the result set (https://github.com/valkey-io/valkey-search/pull/1256#discussion_r3824932482).

Ask

  1. A filtered search mode for (dynamic) Vamana in which is_member() gates admission to the result set inside the graph search, and termination and buffer management are computed over filter-passing results, as in hnswlib.
  2. Expose it through the existing svs_id_filter_t interface, with no new callback type, selected opt-in: a new entry point, or a field in the search parameters. svs_index_search_topk's current behaviour stays the default, so other integrations are unaffected.
  3. Results are at most k per query, every returned id passes the filter, and the per-query count is reported through offsets / total_results as today.

The callback contract is unchanged: is_member() may be called from the searching thread for any candidate id and must be thread-safe, as it already is for the batch path.

Acceptance criteria

  • With the new mode and a filter admitting 1-10% of ids, recall@k against an exact filtered ground truth is at least that of the current batch path, at equal or lower latency, on a benchmark both sides agree on.
  • With a NULL filter, or with the mode not selected, results and latency are unchanged.
  • svs_c.h documents the mode and its contract.
  • bindings/c/tests/ covers: every returned id passes the filter; fewer than k results when fewer than k ids pass; and an exclusion-style filter (deny a given set of ids).

Related

  • #415: documents the filter_rate() <= 0 contract of the current batch path, which valkey-search uses today.
  • #304: the batch iterator takes its search parameters from the parent index.
Langage dominant
C++
Étoiles
241
Forks
48
Merge moyen
4 j 21 h
PR mergées (30 j)
11

Préparer son environnement

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de intel/ScalableVectorSearch

Toutes les issues de intel/ScalableVectorSearch

Issues similaires

Plus d'issues C++

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.