Catalog My learning Blog
LLM System Design Course: RAG, Vector Databases, Cost · Phase 3 · Lesson 15 · 9 min read

Vector Search Metadata Filtering and Hybrid Queries

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: Selectivity-Aware Filtering With a Hard Tenant Boundary
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

Explain why combining a metadata filter with an approximate nearest neighbor search is genuinely hard, compare pre-filtering, post-filtering, and filtered graph traversal, and describe how to enforce tenant and permission boundaries in retrieval without creating a data leak.

Concept Explanation

Almost no production retrieval query is a pure nearest-neighbor search. The real query is nearest neighbors among documents this tenant owns, that this particular user is permitted to see, that are not archived, of an allowed document type, published within some date range. In a relational database, combining predicates with a ranked scan is routine work for a query planner. In an approximate vector index it is genuinely difficult, and the reason is structural: the index was built over the whole corpus, and its ability to find neighbors quickly depends on the connectivity of that whole structure. Removing an arbitrary subset of nodes damages exactly the property the search relies on.

Post-filtering is the naive approach and it fails in a specific, memorable way. Search the index for the top k, then discard the results that do not satisfy the filter. If the filter is unselective this works fine. If the filter is selective - one tenant out of ten thousand, one document type out of forty - the top fifty nearest neighbors across the entire corpus may contain zero matching documents, and the query returns nothing at all despite the corpus containing perfectly good answers. The failure mode is the worst possible one: it is silent, it is worse for smaller tenants, and it looks like a missing-data problem rather than a retrieval architecture problem, so teams spend time investigating the corpus instead of the index.

Pre-filtering is the opposite approach: evaluate the filter first to obtain the set of eligible ids, then search only within that set. It is exactly correct and it has a cost profile shaped like a cliff. If the eligible set is small, brute-force scanning it is fast and the result is exact, which is strictly better than approximate search. If the eligible set is large, you have effectively disabled the index and are scanning millions of vectors. The pragmatic implementation therefore branches on estimated selectivity: below some threshold of eligible rows, scan exactly, and above it, use the index with an approach that handles the filter natively.

That native approach is filtered graph traversal, and it is where the dedicated vector databases have invested most. Rather than filtering before or after, the predicate is evaluated during the search, so the traversal only accepts nodes satisfying the filter while still using non-matching nodes for navigation. The complication is that if too many nodes are excluded, the graph becomes disconnected from the search's perspective and recall collapses, so implementations add extra links among nodes sharing common filter values, or fall back to exact scanning when selectivity crosses a threshold. The practical guidance that follows is to design for a small number of high-cardinality filter dimensions that the index knows about in advance, rather than assuming arbitrary ad hoc predicates will be efficient.

Tenant and permission filtering deserves separate emphasis because it is a security boundary rather than a quality knob, and the shape of the failure is a cross-tenant data leak surfaced through a generated answer. Three rules follow. The tenant predicate must be applied inside the search, never after, both because post-filtering can return empty results and because any code path that fetches another tenant's content into memory is one refactor away from returning it. The predicate must come from the authenticated session, never from a request parameter, or you have rebuilt an insecure direct object reference with a semantic search in front of it. And for strong isolation requirements, physical separation by index or namespace per tenant removes the possibility of a filter bug leaking data at all, at the cost of more indexes to manage and worse memory efficiency for very small tenants. Document-level permissions are harder still, since they can change between indexing and query time, which is why permissions should be resolved against the live authorization system at query time rather than baked into metadata that can go stale.

ApproachHow It WorksFails WhenUse For
Post-filterSearch the whole index, then discard non-matching resultsThe filter is selective; returns few or zero results silentlyUnselective filters only, such as a coarse language flag
Pre-filter and exact scanResolve eligible ids first, then compute exact distances over themThe eligible set is large; the index is effectively bypassedHighly selective filters, such as a small tenant
Filtered graph traversalEvaluate the predicate during traversal, navigating through non-matching nodesSelectivity is extreme enough to disconnect the graphThe general case, with a fallback to exact scan
Physical partition per tenantA separate index or namespace per tenantTenant count is very large or tenants are tinyStrong isolation requirements

Worked Example: Selectivity-Aware Filtering With a Hard Tenant Boundary

The routing logic below picks a strategy based on estimated selectivity, and the tenant predicate is structurally incapable of being skipped, because it is taken from the authenticated principal and applied inside every branch.

Python
def search(query_vec, principal, filters, top_k=50):
    # 1. The tenant boundary comes from the SESSION. Never from the request.
    #    If this were filters.get('tenant_id'), you have built an IDOR with
    #    a semantic search in front of it.
    scope = {'tenant_id': principal.tenant_id, **sanitize(filters)}

    # 2. Estimate how much of the corpus survives the predicate.
    eligible = stats.estimate_matching_rows(scope)

    if eligible < 20_000:
        # Small enough to scan exactly. Faster AND exact - strictly better
        # than approximate search here. This is the small-tenant path.
        return exact_scan(query_vec, scope, top_k)

    if eligible < 0.30 * corpus_size:
        # Selective enough that post-filtering would return near-nothing,
        # but too large to scan. Push the predicate INTO the traversal.
        return index.search(query_vec, filter=scope, top_k=top_k,
                            ef_search=max(200, top_k * 4))   # widen: filtering
                                                             # costs recall
    # Unselective: ordinary approximate search with the filter applied
    # during traversal is fine at default width.
    return index.search(query_vec, filter=scope, top_k=top_k)

# 3. Document-level permissions are resolved LIVE, not from stale metadata.
#    An ACL copied into the index at ingest is wrong the moment it changes.
def authorized(chunks, principal):
    allowed = authz.filter_readable(principal, {c.doc_id for c in chunks})
    return [c for c in chunks if c.doc_id in allowed]

# 4. The test that must exist in CI:
#    assert search(any_vector, tenant_a_principal, {}) never returns tenant_b ids
#    including when filters is empty, malformed, or attacker-controlled.
Three filtering strategies against an approximate index: post-filtering returning an empty result set for a selective tenant predicate, pre-filtering collapsing into an exact scan, and filtered traversal evaluating the predicate inside the graph walk, with a selectivity threshold routing between them.
Three filtering strategies against an approximate index: post-filtering returning an empty result set for a selective tenant predicate, pre-filtering collapsing into an exact scan, and filtered traversal evaluating the predicate inside the graph walk, with a selectivity threshold routing between them.

Real-World Examples

  • Qdrant published its filterable HNSW design, which addresses the graph-disconnection problem by adding extra links among nodes that share common payload values so that a filtered traversal still has a navigable path, together with a threshold below which it falls back to exact scanning. It is a concrete demonstration that filtered vector search required changing the index structure rather than wrapping an unfiltered index in a predicate.
  • Elasticsearch documents that filters on an approximate k-nearest-neighbor search are applied during the search rather than afterwards, specifically so that a restrictive filter still returns the requested number of results, and it notes that the filter can be combined with an exact brute-force search when that is a better fit. The existence of that documented distinction is evidence that post-filtering returning too few results was a common enough failure to warrant designing around it explicitly.
WarningA tenant or permission predicate applied after the vector search rather than inside it is a data leak waiting for a refactor, and it also silently returns empty results for smaller tenants. Take the boundary from the authenticated session rather than from any request parameter, apply it inside every search path including the exact-scan fallback, resolve document-level permissions against the live authorization system rather than from metadata copied at ingest, and keep a cross-tenant isolation test in continuous integration.

Review Questions & Answers

Post-filtering searches the entire corpus for the top k and then discards non-matching results, so the number of surviving results is roughly k multiplied by the fraction of the corpus the filter admits. A tenant owning a thousandth of the corpus will typically see zero of the global top fifty belong to them, so the query returns nothing even though relevant documents exist. It is hard to diagnose because no error occurs, the result is simply empty, and the severity scales inversely with tenant size, so it appears as sporadic complaints from smaller customers that look like missing content rather than a retrieval architecture defect.

HNSW finds neighbors by walking a graph whose navigability depends on the connectivity of the whole structure, with each hop moving closer to the query. If nodes failing the filter are removed from the graph entirely, paths that the search depended on to cross the space disappear, and the traversal can become stranded in a region with no remaining route to the true neighbors, so results are not merely fewer but wrong. Implementations address this by traversing through non-matching nodes while only accepting matching ones as results, by adding extra links among nodes sharing common filter values, and by falling back to exact scanning when the filter is selective enough that the graph would be unusable.

Because permissions change independently of documents. Someone leaves a team, an access group is revised, a document is reclassified, and none of those events necessarily touches the document content that would trigger re-indexing. An access control list copied into the index at ingest becomes stale at the moment of that change, and the failure direction is the dangerous one: a user retains retrieval access after their permission was revoked. Resolving the permitted document set against the live authorization system at query time keeps retrieval consistent with the actual authorization state, and it also keeps the authorization logic in one place rather than duplicated into an index that cannot express it fully.

When the isolation requirement is strong enough that a filter bug would be unacceptable rather than merely bad, which is common in regulated industries and in contracts that promise physical separation. Separate indexes make cross-tenant retrieval impossible by construction rather than by correct predicate application, and they additionally give each tenant an index small enough that exact search is often viable, which removes recall uncertainty as well. The costs are real: many indexes to create, monitor, back up, and upgrade, poor memory efficiency when most tenants are small since each index carries fixed overhead, and a more complex provisioning path for onboarding. The tradeoff generally favors separation when tenants are few and large, and filtering when tenants are many and small.