HNSW with Filters

The core innovation of HNSW with filters is the integration of metadata predicate evaluation into the greedy search algorithm. During traversal from the entry point, the algorithm only explores graph neighbors that satisfy the provided Boolean filter. This prevents wasted computation on irrelevant vectors and ensures the search path remains within the filtered candidate set. The traversal logic dynamically prunes branches, making it fundamentally more efficient than naive post-filtering.

This architecture is a sophisticated form of pre-filtering. By applying constraints during the graph walk, it avoids the costly scenario of performing a full, unrestricted vector search only to discard most results afterward. The system's efficiency is heavily dependent on filter selectivity—the proportion of the total dataset that passes the filter. High-selectivity filters (e.g., category = 'news' AND date > yesterday) yield the greatest performance gains over post-filtering approaches.

The system natively supports complex filtering logic, including:

• Conjunctive queries (AND): user_id = 123 AND status = 'active'
• Disjunctive queries (OR): category = 'sports' OR category = 'politics'
• Range queries: price >= 10.0 AND price <= 50.0
• Negation (NOT): language != 'fr' These predicates are typically evaluated using fast auxiliary index structures like bitmap indexes or B-trees on the metadata fields, allowing for near-instant set membership checks during graph traversal.

Unlike post-filtering, which can return fewer results than requested (k) if many top candidates are filtered out, HNSW with filters is designed to find the k nearest neighbors within the filtered subset. This provides deterministic result set size. The search scope is precisely controlled, which is critical for applications like personalized recommendations (user_segment = 'premium') or multi-tenant retrieval where data must be strictly isolated by tenant_id.

The database's query planner analyzes the filter's selectivity and available indexes to choose an optimal execution strategy. For a highly selective filter (e.g., targeting <1% of vectors), it may use a filter-first approach, retrieving a list of valid vector IDs via the metadata index before performing a targeted search within that small set. For less selective filters, the default traversal-time filtering is used. This adaptive planning is key to maintaining low latency (<10ms) across diverse query patterns.

The trade-off for filtered accuracy is a predictable increase in search latency and potential impact on recall compared to an unfiltered HNSW search. The graph must explore alternative paths when optimal neighbors are filtered out, which can increase the number of distance computations. However, this cost is almost always significantly lower than the alternative: a full ANN search followed by filtering, which scales with the total dataset size rather than the relevant subset.

Users search for items using natural language (e.g., "comfortable running shoes for trail") while applying hard filters for price range, brand, and size. HNSW with filters executes a single, efficient traversal of the product embedding graph, only visiting nodes that satisfy all metadata constraints. This prevents the system from wasting compute on scoring irrelevant items, crucial for sub-100ms latency in high-traffic catalogs.

In secure environments, search results must respect user permissions. Each document has metadata tags for department, clearance level, and project ID. A query for "Q3 financial projections" combines semantic similarity with a conjunctive filter (e.g., department = Finance AND clearance >= user_clearance). The HNSW graph traversal skips entire branches of documents that fail the permission check, ensuring compliance and privacy without a costly post-filtering step that could return zero results.

A media platform recommends articles or videos based on a user's current session embedding. To ensure freshness and relevance, the system applies filters for content language, publish date (last 7 days), and content rating. HNSW with filters navigates the graph of content embeddings, prioritizing recent, appropriately-rated items in the correct language. This maintains high recall of relevant candidates while enforcing business rules within the ANN search itself.

A B2B SaaS platform stores all customer embeddings in a single large index for operational efficiency. Each vector is tagged with a tenant_id. During search, the system injects a tenant_id = X filter into the HNSW traversal. This design provides strong multi-tenancy isolation at the index level, preventing one customer's query from accessing another's data, while leveraging the performance and density of a unified graph index.

DevOps engineers search application logs semantically (e.g., "authentication timeout error") but must scope the search to a specific time window (e.g., last 1 hour) and service name. Using HNSW with filters, the graph is structured with timestamps, allowing the search to prune exploration of log embeddings outside the required timeframe immediately. This is far more efficient than scanning all logs and then filtering, enabling fast root cause analysis during incidents.

This card contrasts HNSW with filters against two common alternatives:

• Pre-Filtering: Apply metadata filters first to get a candidate ID list, then search this subset with vanilla HNSW. Risk: high-selectivity filters may produce a tiny, non-representative subset, harming recall.
• Post-Filtering: Run a broad HNSW search, then filter the top-K results. Risk: may discard all top-K items if they don't match filters, forcing inefficient pagination.
• Integrated Filtering (HNSW with Filters): The filter logic guides the graph traversal. The algorithm evaluates a node's metadata before adding it to the candidate priority queue, balancing similarity and constraint satisfaction in a single pass. This provides optimal trade-offs for complex Boolean filters with medium selectivity.

The foundational problem that HNSW solves. ANN search refers to algorithms that find vectors approximately closest to a query vector in sub-linear time, trading perfect accuracy for massive speed and scalability. Key trade-offs are between recall (fraction of true nearest neighbors found), latency, and index build time. HNSW is a leading graph-based ANN algorithm.

The core constraint paradigm. Filtered search is a retrieval process where metadata-based constraints (e.g., user_id = 123, date > 2024-01-01) are applied to narrow the candidate set. In vector databases, this is combined with similarity search. The primary engineering challenge is filter selectivity—applying a highly selective filter early drastically reduces the search space and cost.

The two fundamental strategies for applying filters with ANN search, representing a critical performance trade-off.

• Pre-Filtering: Filters are applied first to create a reduced candidate set, then ANN search runs on this subset. Efficient for highly selective filters but can degrade graph connectivity.
• Post-Filtering: Broad ANN search runs first, and results are filtered afterward. Simple but can cause recall collapse if the true nearest neighbors are filtered out after the search.

HNSW with Filters often uses a modified traversal to blend these approaches.

A core data structure for fast filtering. A bitmap index represents the membership of records for specific attribute values using arrays of bits (bitmaps). For a filter like category = 'news', a bitmap with a 1 for every 'news' document enables extremely fast set intersection (AND) and union (OR) operations. This is crucial for evaluating conjunctive and disjunctive queries efficiently during HNSW graph traversal.

The optimizer's role. Query planning is the process where the database analyzer evaluates a query containing both vector similarity and metadata filters to choose an efficient execution sequence. For HNSW with Filters, the planner must estimate filter selectivity to decide:

• The order of filter evaluation.
• Whether to use a modified HNSW traversal or a separate pre/post-filter step.
• How to leverage indexes like bitmaps.

The Boolean logic of filtering. These define how multiple filter predicates are combined.

• Conjunctive Query (AND): category = 'news' AND date > 2024-01-01. All conditions must be true. Efficiently executed via bitmap intersection.
• Disjunctive Query (OR): category = 'news' OR category = 'sports'. At least one condition must be true. Executed via bitmap union.

HNSW with Filters must correctly respect this Boolean logic during graph traversal to ensure correct results.