Filtered vector search: build allow-bitsets from secondary indexes and stop decoding records per visited node #2688

Summary

Filtered vector search evaluates its predicate by loading and decoding the whole record for every visited HNSW node. On a document-with-sections corpus (~9 KB records, filter selectivity 5–40%) that makes a filtered top-50 query 35–50× slower than Postgres + pgvector on the same data at the same recall, while the native HNSW module's allow-bitset search path sits unused. Fix in three parts: build allow-bitsets from secondary indexes (equality and comparison operators, AND/OR), feed them to the plane's bitset search, and evaluate any remaining pushed-down predicate from index entries or lazy field access instead of a full decode.

Measured

Synthetic corpus, 20k documents / ~100k sections, 768-d, one box, recall@50 within 0.004 of pgvector (Harper efSearch 100 × filterExpansion 24; pgvector ef_search 100, iterative scan). Filter: tenantId = ? AND publishedAt >= ?, 5–40% selective.

The five non-ANN steps (hydrate, rerank, ±2-ordinal expansion, collapse) cost Harper ~1 ms in total. The rest is the filtered traversal: up to ef × filterExpansion = 2,400 node visits, each a ~130 µs record load + decode. The same program with three dependent reads and no filter (a summary-tree walk) has Harper ahead of both Postgres variants, so this is specifically the filter path.

Root cause

• HierarchicalNavigableSmallWorld.ts searchPlane (~L756–796) only ever calls plane.searchWithPredicate(...), adapting filter(primaryKey) through a TSFN batch. The plane binding's search(vector, k, ef, filter: Uint8Array, filterExpansion) (hnswPlaneBinding.ts ~L40) has no caller. The HNSW module's DESIGN.md lists the bitset path as tier 1 for "RBAC allow-lists and companion-condition candidate sets" and leaves the pk→nodeId glue to Harper; that glue does not exist.
• Every predicate Harper can hand the traversal loads the record: a caller vectorFilter(record), and the pushed-down sibling conditions composed by search.ts composeRecordFilter (~L109–121). Indexed attributes in those conditions are never consulted as indexes during traversal.
• filterExpansion = 24 exists to compensate for expensive admission; with a bit test per visit it is unnecessary.
• Postgres wins here for one reason: it checks tenant_id / published_at on fixed-width tuple slots with the text TOASTed out of line. It is cheap column access, not a smarter index.

Proposal

1. Allow-bitsets from secondary indexes. For an AND group where every sibling condition targets an indexed attribute: equality → key-only range scan of the secondary index for that value; gt/ge/lt/le/between → key-only range scan over the ordered index; map each primary key to its node id; OR → union, AND → intersection. Pass the result to plane.search(..., filter) (plain bitset over idHighWater; roaring when sparse). No record is touched before the ANN returns. Cache per (attribute, value) for low-cardinality equalities (tenant, corpus, ACL role) and invalidate from the post-commit delivery in Implement the shared transaction-log runtime for derived indexes #2489; a range condition intersects the cached equality bitset with a fresh scan.
2. Retire filterExpansion for bitset filters, keep it only for residual function predicates. Planner rule stays: when the candidate set is small (below a threshold in the low thousands) do exact cosine over the set instead of a filtered traversal, as the planner already does for selective condition filters.
3. Cheap residual predicates. Anything that cannot become a bitset (a vectorFilter function, a non-indexed attribute) is evaluated from index point-lookups or lazy field access over the raw record bytes, not a full decode. Reading two scalar fields from a 9 KB record should cost ~1 µs, not 130 µs.
4. Full-text conditions (Expose full-text conditions and $score through Table.search and REST #2511) are a bitset lane of the same shape: a matches group produces a doc-id set from Tantivy that maps to node ids and intersects with the vector traversal, which gives "must contain these terms AND be near" without a second ranked list.

Acceptance

• The benchmark above at the same recall gate: Harper filtered ANN top-50 within 2× of pgvector's at concurrency 1, and the full six-step program at or below the single-CTE Postgres variant at concurrency 8 and 32.
• explain reports filterEvaluations = 0 for a bitset-served filter and the bitset build cost separately.
• Equality, ge/gt/le/lt/between, and nested AND/OR over indexed attributes all take the bitset path; a mixed group with one non-indexed sibling takes the bitset for what it can and the cheap residual path for the rest.
• Recall under filter is unchanged or better than today's predicate path at the same ef (bitset admission never routes worse than predicate admission).
• Unit coverage for bitset build from each comparator, cache invalidation on write, and the small-set exact fallback.

Non-goals

• Changing the HNSW graph, distance, or quantization.
• Cross-node or sharded filtering.
• Replacing vectorFilter for callers; it keeps working, only faster.

Related

• Predicate-aware HNSW traversal: filtered vector search with user-function and RBAC participation #1241 (closed) introduced the predicate-aware traversal this replaces for indexed conditions.
• Native HNSW index: file-primary mmap graph as a backend on the shared derived-index runtime #2430 native plane; Implement the shared transaction-log runtime for derived indexes #2489 shared derived-index runtime (the invalidation source for cached bitsets).
• Expose full-text conditions and $score through Table.search and REST #2511 full-text conditions and $score — item 4.
• [Epic] Vector/HNSW roadmap (research) #1658 vector/HNSW roadmap.
• HarperFast/hnsw DESIGN.md "Filtering", tier 1 bitset fast path.
• Measurement harness: HarperFast/retrieval-plan-bench (private).

🤖 Generated with Claude Code