Filtering and Vector Search in One Query

Add WHERE tenant_id = 42 to a working vector query and one of two things happens: it gets slow, or it returns fewer rows than you asked for. Both are the same underlying fact — an approximate index and a filter cannot be applied at the same time — and the selectivity at which it becomes fatal is calculable in advance.

Why the two do not compose

A B-tree index and a GIN index can be combined: Postgres builds a bitmap from each and ANDs them. An HNSW index cannot participate in that, because it does not produce a set of matching rows — it produces an ordered stream, nearest first, and the ordering is the entire value of it. You cannot intersect an ordering with a bitmap and still have an ordering.

So the planner must choose. Either it walks the graph and discards rows that fail the filter afterwards (post-filter), or it finds the rows that pass the filter and computes distances for all of them (pre-filter). These have different costs and, critically, different answers.

Postgres chooses between them with its cost model, and its cost model for an approximate nearest-neighbour scan is close to a guess. It has no statistics describing how many rows the graph will examine before finding ten that pass your filter, because that quantity depends on where in vector space your query landed. So the planner picks using an estimate that is structurally uninformed, and it will sometimes pick the plan that cannot answer your query. This is the one situation in Postgres where overriding the planner from the application is normal rather than a smell.

The post-filter, and its arithmetic

This is what you get by default from the obvious query:

SELECT id, content
FROM chunks
WHERE tenant_id = 42
ORDER BY embedding <=> $1
LIMIT 10;

The HNSW scan keeps hnsw.ef_search candidates alive and returns them in distance order; the filter is applied to that stream. Let s be the selectivity of the filter — the fraction of the table it passes. If the filter is independent of position in vector space, the expected number of survivors is:

survivors ≈ ef_search × s

To get k results:   ef_search ≥ k / s

Assumptions: the filter is uncorrelated with the embedding
distribution; ef_search candidates are the only rows examined;
hnsw.ef_search has a hard maximum of 1000.

At the default ef_search = 40 and a filter that passes half the table, you expect twenty survivors and you asked for ten. Fine. At a filter that passes one row in a thousand you expect 40 × 0.001 = 0.04 survivors, which in practice means the query returns nothing at all, from an index that is working exactly as designed.

Before pgvector 0.8.0 there was no recourse inside the scan: you got however many rows survived, silently, with no indication that the answer was short. 0.8.0 added iterative scans, which rescan with a larger candidate set until the limit is met or a budget is exhausted:

SET LOCAL hnsw.iterative_scan = strict_order;   -- pgvector 0.8.0+
SET LOCAL hnsw.max_scan_tuples = 20000;        -- the budget it stops at

strict_order guarantees results come back in true distance order; relaxed_order is faster and may return them slightly out of order, which is usually acceptable if a reranker runs afterwards anyway. Neither makes the underlying cost go away — an iterative scan on a highly selective filter is doing a lot of work to find a few rows.

The cliff, in numbers

Put the formula in a table and the shape of the problem is immediate. For k = 10:

That is the cliff: it is not a gradual degradation, it is a hard wall at one per cent selectivity for a top-10 query, sitting at s = k / 1000 in general. Below it, the index is not slow — it is incapable, and iterative scan converts the incapability from wrong answers into slow ones.

One assumption in that derivation is worth naming, because it is frequently false. It assumes the filter is uncorrelated with vector position. Filters on tenant are usually roughly uncorrelated. Filters on language, document type or date are strongly correlated — all the German chunks are near each other in embedding space — and then the survivors either cluster in the candidate set (better than the formula) or are absent from it entirely (much worse). The formula is the right planning tool; your own measurement is the right decision tool.

The pre-filter, and when it is faster

The other plan ignores the vector index entirely: use a B-tree to find the matching rows, compute the distance to each, sort, take ten. Recall is exactly 100 per cent, because nothing is approximated.

-- Force it, to see what it costs:
SET LOCAL enable_indexscan = off;   -- disables the HNSW ordered scan
SET LOCAL enable_bitmapscan = on;

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM chunks WHERE tenant_id = 42
ORDER BY embedding <=> $1 LIMIT 10;

 Limit
   ->  Sort
         Sort Key: ((embedding <=> '[...]'::vector))
         Sort Method: top-N heapsort  Memory: 27kB
         ->  Bitmap Heap Scan on chunks
               Recheck Cond: (tenant_id = 42)
               ->  Bitmap Index Scan on chunks_tenant_idx
                     Index Cond: (tenant_id = 42)

The cost of this plan is s × N distance computations of d dimensions each, plus the heap fetches. At N = 10,000,000, s = 0.001 and d = 1536: ten thousand rows, fifteen million multiply-adds, single-digit milliseconds of arithmetic. The heap fetches for ten thousand scattered rows are the real cost, and they are still likely under a hundred milliseconds warm.

So the plan that the post-filter cannot answer at all is a plan the pre-filter answers exactly, quickly. The cliff and the crossover are the same place, which is a convenient coincidence and the most useful thing on this page.

Where the crossover sits

Set the two costs equal and solve. The exact plan costs about sNd. The post-filter plan needs ef_search ≈ k/s and each candidate expands about m neighbours, so it costs about (k/s)md:

s N d  =  (k / s) m d

s²     =  k m / N

s*     =  sqrt(k m / N)

k = 10, m = 16, N = 10,000,000:
  s* = sqrt(160 / 10,000,000) = sqrt(1.6e-5) = 0.0040  →  0.40%

k = 10, m = 16, N = 1,000,000:
  s* = sqrt(160 / 1,000,000)  = 0.0126        →  1.26%

Assumptions: distance computation dominates both plans; heap access
costs are ignored, which flatters the exact plan; graph traversal
cost is linear in ef_search and m.

Below s*, do not use the vector index. Above it, do. The number moves with your table size, and the square root means it moves slowly — growing from one million rows to ten million only shifts it from about 1.3 per cent to about 0.4 per cent.

Which means the practical rule is: filters that select more than a few per cent of the table should go through the vector index with a raised ef_search; filters that select less than one per cent should skip it. The planner will not reliably make this choice for you, because its cost model for an ANN scan is a placeholder, so you should make it explicitly.

Four ways out

1. Raise ef_search and measure. For selectivities above a few per cent this is the whole answer. Set it per query from the expected selectivity — you usually know roughly how many rows a tenant has — rather than globally.
2. Partition by the filter column. If your filter is almost always the same column, make it the partition key and build one HNSW index per partition. Each partition’s index then contains only matching rows, so a scan of it is unfiltered and the arithmetic above does not apply at all. This is the cleanest fix and the one with real operational cost, since it multiplies your index count.

   CREATE TABLE chunks (
     id bigint GENERATED ALWAYS AS IDENTITY,
     tenant_id int NOT NULL,
     embedding vector(1536) NOT NULL,
     content text NOT NULL
   ) PARTITION BY LIST (tenant_id);
   
   CREATE TABLE chunks_t42 PARTITION OF chunks FOR VALUES IN (42);
   CREATE INDEX ON chunks_t42 USING hnsw (embedding vector_cosine_ops);

3. Partial indexes, for a handful of hot values. A WHERE clause on the index itself. Excellent for two or three large tenants or a single status = 'active' predicate; unworkable past a few dozen, because each one is a full HNSW build.

   CREATE INDEX chunks_active_hnsw ON chunks
     USING hnsw (embedding vector_cosine_ops)
     WHERE deleted_at IS NULL;

4. Force the exact plan below the crossover. A composite B-tree on (tenant_id), and either disable the index scan for that query or write the query so the ANN index cannot apply — for instance by ordering on a computed expression. Exact search over a small filtered set is not a fallback; below s* it is the correct plan.

One thing that is not on the list: adding the filter column to the HNSW index. pgvector does not support multicolumn HNSW indexes, and there is no operator class that would make it meaningful. If a tutorial suggests it, that tutorial is describing a different engine.

Whichever route you take, the number you need first is your actual selectivity, and it is a query rather than an assumption. Filters are rarely uniform: a handful of tenants hold most of the corpus and the long tail holds almost none, so an average selectivity of five per cent can hide a thousand customers sitting at 0.01 per cent who see empty results while everybody else is fine.

-- The distribution of selectivity across the filter values you
-- actually use. Look at the bottom decile, not the mean.
WITH n AS (SELECT count(*)::numeric AS total FROM chunks)
SELECT tenant_id,
       count(*) AS rows,
       round(100.0 * count(*) / (SELECT total FROM n), 4) AS pct_of_table,
       -- ef_search needed for a top-10 query, from k/s:
       ceil(10.0 * (SELECT total FROM n) / count(*)) AS ef_search_needed
FROM chunks
GROUP BY tenant_id
ORDER BY ef_search_needed DESC
LIMIT 20;

Anything in that output with ef_search_needed above 1000 is a filter value the post-filter plan cannot serve, and the count of such rows tells you whether the answer is a per-query ef_search, a partition strategy, or a routing rule that sends small tenants down the exact path and large ones through the index. That last option is worth considering: the two plans are both correct, so choosing between them per request is a legitimate optimisation rather than a hack.

Finally, the interaction that catches teams by surprise: Postgres row-level security policies become WHERE clauses, which means enabling RLS turns every vector query in your application into a post-filtered one overnight, with the selectivity of a single tenant. That is covered, with the leak test, in row-level security for multi-tenant retrieval.