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

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

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

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

評価

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

調査の方向性

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.

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

説明

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.
主要言語
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 を短くまとめたダイジェスト。