pgvector HNSW with a WHERE filter returns fewer rows than LIMIT

Our RAG product stores every customer's documents in one chunks table with a tenant_id column. Retrieval asks for the 10 nearest chunks for the current tenant. Large customers were happy. Small customers, the ones with a few hundred documents, complained that the assistant often said it "could not find anything relevant" for questions that were clearly answered in their docs.

Logging the retrieval result size showed the pattern:

tenant=acme       docs=48211  requested=10 returned=10
tenant=smallco    docs=312    requested=10 returned=2
tenant=tinyshop   docs=95     requested=10 returned=0

The query was simple:

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

Reproducing it

With EXPLAIN ANALYZE for a small tenant:

Limit (actual rows=2 loops=1)
  ->  Index Scan using chunks_embedding_hnsw on chunks (actual rows=2 loops=1)
        Order By: (embedding <=> '[...]'::vector)
        Filter: (tenant_id = 'b2f0...'::uuid)
        Rows Removed by Filter: 38

The index scan produced 40 candidates, the filter removed 38, and the query ended with 2 rows.

What we ruled out

• Missing data. Without the vector ordering, the tenant had 1,900 chunks.
• Embedding model mismatch between tenants. All tenants used the same model and dimension.
• A bug in our LIMIT handling. The SQL itself returned 2 rows.

Root cause

HNSW is an approximate index. A query walks the graph and keeps a candidate list whose size is hnsw.ef_search, 40 by default. Postgres then applies the WHERE clause to those candidates. When the tenant owns 0.1 percent of the table, most of the 40 global nearest neighbours belong to other tenants and are filtered out. Before pgvector 0.8, the scan did not go back for more candidates, so the query returned whatever survived.

What is happening under the hood

A B-tree can apply a filter and keep scanning until it has enough rows. HNSW search is different: it returns a bounded set of approximate neighbours. Filtering after the index scan is called post-filtering. Its recall depends on how selective the filter is. With a filter that matches 10 percent of rows and ef_search = 40, you get about 4 rows on average. With 0.1 percent you usually get none.

pgvector 0.8.0 added iterative index scans. When enabled, if the filter removes too many candidates, the scan continues through the graph to find more, until it has enough rows or reaches a limit (hnsw.max_scan_tuples). There are two modes: strict_order keeps results exactly ordered by distance, and relaxed_order allows slightly out-of-order results in exchange for better speed and recall.

Environment

Minimal reproduction

-- 1000 tenants, one of them tiny
SET hnsw.ef_search = 40;
SELECT count(*) FROM (
  SELECT id FROM chunks WHERE tenant_id = :tiny ORDER BY embedding <=> :q LIMIT 10
) s;   -- often < 10, sometimes 0

Who is affected

Multi-tenant vector search in one table, and any filtered vector search where the filter is selective: by language, product version, document type, or permissions. IVFFlat has the same problem with ivfflat.probes.

The fix

1. Upgrade to pgvector 0.8 and enable iterative scans for the retrieval role.

ALTER EXTENSION vector UPDATE TO '0.8.0';
ALTER ROLE rag_reader SET hnsw.iterative_scan = 'relaxed_order';
ALTER ROLE rag_reader SET hnsw.ef_search = 100;

With relaxed_order, results may be slightly out of order, so we wrap the query and re-sort the small result set by exact distance:

WITH candidates AS MATERIALIZED (
  SELECT id, content, embedding <=> $2 AS distance
  FROM chunks
  WHERE tenant_id = $1
  ORDER BY distance
  LIMIT 10
)
SELECT * FROM candidates ORDER BY distance;

2. Exact search for small tenants. For a tenant with a few thousand chunks, an exact scan of their rows is fast and gives perfect recall. A B-tree on tenant_id lets Postgres fetch only those rows. We route by tenant size:

def search(tenant, qvec, k=10):
    if tenant.chunk_count < 20_000:
        sql = EXACT_SQL      # filter via btree on tenant_id, sort in memory, no HNSW
    else:
        sql = HNSW_SQL       # iterative scan enabled for the role
    return db.execute(sql, {"tenant": tenant.id, "q": qvec, "k": k}).all()

In EXACT_SQL we disable the index scan for that statement with SET LOCAL enable_indexscan = off inside a transaction, so the planner does not choose HNSW and post-filter.

3. Partial indexes for the very largest tenants. The five biggest tenants got their own partial HNSW index (WHERE tenant_id = '...'), which gives full recall without iterative scanning. We stopped at five, because every index costs memory and write time.

Alternatives and trade-offs

• Raise ef_search only. Helps moderately selective filters, costs latency for everyone, does not fix 0.1 percent tenants.
• Partition by tenant. Each partition gets its own index. Clean isolation, but thousands of partitions bring their own planning overhead.
• A dedicated vector database with filtered HNSW. Some engines filter during graph traversal. Worth it at larger scale; we preferred one database for now.

How to test the fix

We built a recall test that compares approximate results with exact results for a sample of tenants of every size:

def recall_at_k(tenant, q, k=10):
    approx = {r.id for r in search(tenant, q, k)}
    exact = {r.id for r in exact_search(tenant, q, k)}
    return len(approx & exact) / max(1, len(exact))

Across 500 sampled queries, mean recall went from 0.41 for the smallest tenant decile to 0.98, and stayed above 0.97 for large tenants.

Confirming in production

• "Returned fewer than requested" log events dropped from 31 percent of queries to 0.4 percent (tenants with fewer than 10 chunks in total).
• "Could not find anything relevant" answers from small tenants fell by about 70 percent over the next two weeks.
• p95 retrieval latency rose from 18 ms to 26 ms for large tenants, which was acceptable.

Regression guard

• The recall test runs nightly against a production snapshot and alerts below 0.9 for any size bucket.
• A metric for returned < requested, broken down by tenant size bucket.

Security implications

Tenant isolation was never at risk: the filter always applied, it just removed too much. One trap to avoid while fixing this: moving the tenant filter out of SQL into application code "for performance" would turn a recall bug into a data leak. We kept the filter in the query, and the retrieval repository refuses to run a search without a tenant id.

Prevention checklist

• Know that HNSW plus WHERE means post-filtering, and measure recall per filter selectivity.
• Use iterative scans (pgvector 0.8+) for filtered queries.
• Use exact search when the filtered set is small.
• Add partial indexes or partitions for very large, frequently filtered groups.
• Log returned versus requested row counts.

References

• pgvector README, filtering and iterative index scans — https://github.com/pgvector/pgvector
• pgvector 0.8.0 release notes — https://github.com/pgvector/pgvector/blob/master/CHANGELOG.md
• PostgreSQL partial indexes — https://www.postgresql.org/docs/17/indexes-partial.html