Pre-Filtering

Pre-filtering applies hard metadata constraints—like user_id = 'abc' or date > '2024-01-01'—first, creating a drastically smaller candidate set. This is a Boolean operation on indexed fields, not a similarity search. For example, filtering a 10-million-item catalog by category = 'electronics' might reduce the candidate pool to 50,000 items before any vector math occurs. This step is 100% recall for the filter condition; any item not matching the metadata is excluded irrevocably.

The efficiency of a pre-filtering strategy hinges on filter selectivity, the estimated fraction of the total dataset that passes the filter. A highly selective filter (e.g., sku = 'XYZ123') returns a tiny candidate set, making pre-filtering ideal. A low-selectivity filter (e.g., status = 'active' where 95% of items are active) offers little reduction, potentially making post-filtering or ANN with filters more efficient. The database's query planner analyzes predicate selectivity and index availability to choose the optimal execution path.

For pre-filtering to be fast, metadata fields must be indexed. Common structures include:

• B-tree indexes: For efficient range (>, <) and equality queries on scalar fields.
• Bitmap indexes: For extremely fast set operations on low-cardinality fields (e.g., category, status). They represent each value as a bit array, enabling rapid AND/OR operations.
• Bloom filters: Probabilistic data structures used for fast membership tests (e.g., "is this ID in the allowed list?") with a configurable false-positive rate. Without proper indexing, the pre-filtering step becomes a full table scan, negating its performance benefit.

Pre-filtering guarantees perfect precision for the metadata constraint—no result will violate the filter. However, it can negatively impact overall recall for the semantic query. If the single most semantically relevant item in the database fails the metadata filter, it is excluded and cannot be retrieved. This trade-off is intentional: pre-filtering prioritizes business rule enforcement (e.g., "only show user's own documents") over pure semantic relevance. The alternative, post-filtering, risks returning semantically relevant results that must then be discarded for violating constraints.

Pre-filtering is often the first stage in a multi-stage retrieval pipeline. Its role is to use cheap, deterministic rules to prune the search space before handing off to more expensive stages:

1. Stage 1 (Pre-Filter): Apply hard metadata filters via indexed lookup.
2. Stage 2 (ANN Search): Perform approximate nearest neighbor search (e.g., using HNSW) on the filtered candidate set.
3. Stage 3 (Reranking): Optionally apply a slow, precise cross-encoder model to the top-K ANN results. This architecture optimizes cost and latency by ensuring expensive operations run on the smallest possible dataset.

• vs. Post-Filtering: Post-filtering runs the vector search first on the full dataset, then applies metadata filters. It preserves semantic recall but may waste compute on results that are later filtered out. Pre-filtering is more efficient when filter selectivity is high.
• vs. ANN with Filters (Single-Stage): Advanced indices like HNSW with filters interweave filtering and graph traversal, checking constraints during the search. This can be more efficient than a strict two-step pre-filter/ANN process but is algorithmically more complex. Pre-filtering remains simpler to implement and reason about when using standard ANN indices.

Post-filtering is the inverse strategy to pre-filtering. A broad vector similarity or keyword search is executed first, returning a large candidate set. Metadata filters are then applied after the similarity search to prune irrelevant results.

• Trade-off: Can be inefficient if the initial search returns many candidates that are later filtered out, wasting compute on irrelevant vector comparisons.
• Use Case: Effective when filter selectivity is low (filters exclude few items) or when the primary goal is maximizing semantic recall before applying soft constraints.

Filtered search is the overarching process of applying metadata constraints—such as user_id, timestamp, or category—to narrow a result set. It encompasses both pre-filtering and post-filtering strategies.

• Core Function: Enables precise, context-aware retrieval (e.g., "find similar products available in my region").
• Implementation: Filters are typically expressed as Boolean expressions (AND, OR, NOT) on structured fields. The database's query planner decides whether to apply them pre- or post-similarity search based on filter selectivity.

ANN with Filters refers to specialized Approximate Nearest Neighbor search algorithms engineered to respect hard metadata constraints during the graph or tree traversal, not before or after. This integrates filtering into the core index structure.

• Key Challenge: Maintaining search speed and recall while skipping invalid nodes. Algorithms like HNSW with Filters modify the graph traversal logic to only explore paths that satisfy the filter predicates.
• Advantage: Often more performant than a separate pre-filtering step, as it avoids constructing a large intermediate candidate set.

Filter selectivity is a critical metric, expressed as a fraction or percentage, that estimates the proportion of records in a dataset that will satisfy a given filter predicate (e.g., category = 'electronics').

• High Selectivity: A filter that excludes most records (e.g., user_id = 'abc123'). Favors a pre-filtering strategy.
• Low Selectivity: A filter that excludes few records (e.g., language = 'en' in an English corpus). May favor post-filtering.
• Query Optimization: Database optimizers use selectivity estimates to choose the most efficient execution plan, deciding whether to push filters down early.

A bitmap index is a specialized database index that enables extremely fast pre-filtering operations. It represents each distinct value of a field as a bit array (bitmap), where each bit corresponds to a record ID and indicates membership.

• Efficiency: Set operations (AND, OR, NOT) for conjunctive/disjunctive filters are performed via fast bitwise logic on these arrays.
• Use Case: Ideal for medium-cardinality fields (e.g., status, region) where pre-filtering needs to be executed in milliseconds. It is a foundational structure for implementing high-performance filtered search.

Query planning is the process where a database system's optimizer analyzes a search query—including its vector similarity component and filter predicates—to generate an efficient sequence of operations, known as an execution plan.

• Key Decision: The planner evaluates filter selectivity, index availability, and data distribution to decide between pre-filtering, post-filtering, or integrated ANN with Filters.
• Goal: Minimize total latency and computational cost by reducing the number of expensive vector comparisons and unnecessary data scans.