Filtered Vector Search Is a Recall Budget

Sep 2

By

ai infrastructurepostgresqlpgvectorvector searchdatabase engineering

An approximate vector index can make a query fast while making the product wrong. The risk becomes sharp when semantic search is combined with tenant, permission, language, freshness, or product filters.

The invariant is:

Retrieval quality must be measured after every eligibility filter, because the application cannot use a relevant result it is not allowed to return.

Approximate nearest-neighbor indexes search a bounded candidate set. In pgvector, filtering is commonly applied after that approximate scan. If only 10% of scanned candidates satisfy the filter, an HNSW search that examines 40 candidates yields roughly four eligible candidates on average—not the requested ten.

Why LIMIT 10 may return three rows

Consider a shared embedding table:

SELECT id, content
FROM document_chunk
WHERE tenant_id = $1
  AND deleted_at IS NULL
ORDER BY embedding <=> $2
LIMIT 10;

The SQL contract appears to request ten rows. The approximate index has a different internal budget: visit a bounded neighborhood, then discard rows that fail the relational filter. The executor cannot return disallowed candidates, so the result can be short.

This is not merely a tuning bug. It is an interaction between two correct mechanisms:

ANN candidate generation -> relational eligibility filter -> LIMIT

The smaller or more selective a tenant is within a shared graph, the more its recall and latency can differ from a large tenant’s. Aggregate benchmarks conceal that unfairness.

Choose the search shape by selectivity

There is no universal index plan.

For highly selective filters, a B-tree can find a small eligible set first and exact distance can rank it:

CREATE INDEX CONCURRENTLY document_chunk_tenant_idx
ON document_chunk (tenant_id)
WHERE deleted_at IS NULL;

Exact search over 500 eligible vectors may be cheaper and more accurate than traversing a global HNSW graph.

For a few large, stable segments, partial vector indexes can isolate search spaces:

CREATE INDEX CONCURRENTLY document_chunk_en_hnsw
ON document_chunk USING hnsw (embedding vector_cosine_ops)
WHERE language = 'en' AND deleted_at IS NULL;

For many tenants, one index per tenant creates operational debt. Partitioning by a bounded grouping, dedicated tables for the largest tenants, or shared indexes with iterative scans may be better.

Iterative scans turn recall into bounded work

pgvector supports iterative scans that continue searching when filtering leaves too few results:

BEGIN;
SET LOCAL hnsw.iterative_scan = strict_order;
SET LOCAL hnsw.ef_search = 80;
SET LOCAL hnsw.max_scan_tuples = 20000;

SELECT id, content, embedding <=> $2 AS distance
FROM document_chunk
WHERE tenant_id = $1 AND deleted_at IS NULL
ORDER BY embedding <=> $2
LIMIT 10;
COMMIT;

Strict ordering preserves exact distance order among returned candidates. Relaxed ordering can improve recall-performance trade-offs; a materialized CTE can then re-sort the expanded result.

The controls are budgets, not magic. Increasing ef_search, scan tuples, IVFFlat probes, or scan memory spends CPU, memory, and latency to recover candidates. Put ceilings around interactive traffic and separate policies for offline retrieval jobs.

Benchmark against exact truth

Latency-only benchmarks reward empty results. Build an evaluation set of real query embeddings and eligibility filters. For each query, compute an exact top-k baseline by disabling approximate index scans in a controlled environment, then compare the approximate result.

Useful metrics include:

recall@k = relevant exact top-k IDs found / k
fill@k   = returned eligible rows / requested k

Also record p50, p95, and p99 latency; candidates visited; filter selectivity; tenant size; index size; model version; embedding dimension; and corpus freshness.

Report distributions by tenant and filter class. A global recall of 0.95 can coexist with a recall of 0.30 for small tenants—the exact customers isolation is supposed to protect.

Retrieval correctness extends beyond ANN

Even perfect nearest-neighbor recall does not prove a correct AI answer. Retrieval can fail because:

  • the source was chunked across the required context;
  • embeddings changed without a complete reindex;
  • permission metadata is stale;
  • deleted content remains in a secondary index;
  • the distance operator does not match how embeddings were normalized;
  • a reranker optimizes a different relevance definition;
  • the model cites a chunk it did not actually use.

Version embeddings and chunking policy. Store source revision and authorization metadata with each chunk. Make deletion and permission change propagation measurable. Never use semantic similarity as authorization.

Index lifecycle is product lifecycle

HNSW generally offers a better query speed-recall trade-off but costs more memory and build time than IVFFlat. IVFFlat depends strongly on list count, training data, and probes. Both need evaluation after corpus growth or embedding-model changes.

Build production indexes concurrently where write availability matters. Observe EXPLAIN (ANALYZE, BUFFERS), index size, build progress, vacuum behavior, and replica impact. A new embedding model often requires dual-writing and shadow evaluation before traffic moves—not overwriting vectors in place and hoping ranking remains stable.

The CTO decision

Define retrieval quality as a service objective: minimum recall and fill rate for each important eligibility class, within a latency and resource budget. Make an exact baseline reproducible. Choose exact search, partial indexes, partitioning, HNSW, or IVFFlat from measured selectivity rather than fashion.

Vector search is not “working” because the query is fast. It is working when eligible evidence is found reliably enough for the product decision built on top of it.

References

>