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

Đang mở
  • Có gì không ổn?
#420 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 5 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
15/100
Loại issue
Tính năng
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
c, cpp
Lĩnh vực
api, search

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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.
Ngôn ngữ chính
C++
Star
241
Fork
48
Merge trung bình
4 ngày 21 giờ
Pull request đã merge (30 ngày)
11

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của intel/ScalableVectorSearch

Tất cả issue của intel/ScalableVectorSearch

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.