The Fundamental Conflict: Ordering vs. Filtering
Integrating traditional database filtering with vector search, a cornerstone of modern AI applications, presents a significant technical challenge. When developers attempt to add a simple `WHERE tenant_id = 42` clause to an existing vector query, they often encounter one of two undesirable outcomes: either the query becomes unexpectedly slow, or it returns fewer results than requested. This isn't a bug; it's a direct consequence of how approximate nearest neighbor (ANN) indexes, like Hierarchical Navigable Small Worlds (HNSW), operate compared to traditional B-tree or GIN indexes.
Traditional databases excel at filtering data using indexes like B-trees or GIN. These indexes allow the query planner to efficiently identify and retrieve subsets of data that match specific criteria. When combining multiple traditional indexes, a database like PostgreSQL can construct bitmaps from each index and logically AND them together. This process is efficient because each index provides a direct set of matching row identifiers.
Vector indexes, such as HNSW, operate on a fundamentally different principle. Their primary value lies in producing an *ordered stream* of results, ranked by proximity to a query vector. They don't produce a static set of matching rows in the same way a B-tree does. Instead, they navigate a graph structure, prioritizing neighbors that are closest in the vector space. This inherent ordering is the index's core strength.
The problem arises when you try to apply a filter to this ordered stream. A traditional filter, represented as a bitmap of matching rows, cannot be directly intersected with an ordered stream without losing the ordering property. Trying to AND an ordered stream with a bitmap is like trying to sort a deck of cards while simultaneously only considering cards of a specific color – the sorting logic breaks. The query planner is forced to make a difficult choice:
1. Post-filtering: The planner can execute the vector search first, retrieving an ordered stream of nearest neighbors. Then, it discards any results that do not satisfy the filter condition. This approach suffers from inefficiency because the vector index might explore many nodes and compute many distances only to discard the results later. If the filter is highly selective (i.e., it eliminates most of the data), this becomes extremely wasteful.
2. Pre-filtering: Alternatively, the planner can first apply the filter to identify a smaller subset of rows that satisfy the condition. Then, it performs the vector search only on this filtered subset. This requires a traditional index (like a B-tree on `tenant_id`) to efficiently find the rows that pass the filter. However, the vector search is then computed on a potentially much smaller set of vectors, which can also be suboptimal if the filter is not very selective. Furthermore, it means the vector index cannot participate in the initial filtering step.
The selectivity at which one of these methods becomes critically detrimental is mathematically calculable. It depends on the size of the dataset, the nature of the vector index, and the selectivity of the filter. This inherent conflict means that a single query cannot simultaneously leverage the exactness of a filter and the approximate, ordered nature of a vector search without compromise.
The Calculation of Selectivity
The point at which the performance of combined filtering and vector search degrades to an unacceptable level is not arbitrary. It can be estimated by analyzing the cost of both post-filtering and pre-filtering strategies. Consider a dataset with $N$ total items. A vector search might involve examining $k$ neighbors, with each examination costing $C_v$ (e.g., distance calculation). A traditional filter might involve a lookup in a B-tree index, costing $C_f$ per probe, and retrieving $m$ matching rows.
In a post-filtering scenario, the cost is roughly $C_{vector} + (m imes C_{filter})$. The $C_{vector}$ here represents the cost of the full vector search, which might explore a large portion of the index. The $(m imes C_{filter})$ is the cost of applying the filter to the $m$ results returned by the vector search. If $m$ is large and the filter is expensive, this becomes slow.
In a pre-filtering scenario, the cost is $C_{filter} + (m' imes C_{vector}')$. Here, $C_{filter}$ is the cost to find the $m'$ rows that satisfy the filter using a traditional index. Then, $C_{vector}'$ is the cost to perform the vector search on this reduced set of $m'$ vectors. If $m'$ is very small, the vector search might be fast, but the initial filtering might still be costly if the index isn't perfectly selective. If $m'$ is still large, the vector search on this subset can still be slow.
The critical point is where the cost of one strategy exceeds the cost of the other, or where the number of results returned ($m$ or $m'$) is significantly less than the user's requested limit (e.g., `k`). This happens when the filter is either too broad (leading to post-filtering inefficiency) or too narrow and the vector index cannot efficiently narrow down the search space *before* filtering.
Think of it like trying to find the 10 closest friends to your house (vector search) but also needing to ensure they all live in a specific ZIP code (filter). If you first find the 10 closest friends and then check their ZIP codes, you might end up with only 2 or 3 who qualify, and you have to go find more. If you first find everyone in that ZIP code and then calculate distances, you might have to calculate distances for thousands of people if that ZIP code is huge. The problem is that the ordering property of