The Filtered-Search Problem

The index finds neighbours first, the filter removes them later

Suppose an HNSW index returns the 40 nearest candidates (ef_search = 40), and the query adds WHERE tenant = 7 where tenant 7 holds only 1% of the rows. About 0.4 of those 40 candidates belong to tenant 7, so after filtering you may get fewer than LIMIT rows, or none, even though plenty of matching rows exist. This is post-filtering and it is the classic trap of approximate search. Fixes: (1) iterative scans (pgvector 0.8+): the index keeps fetching more candidates until enough rows pass the filter; (2) partial indexes or partitions per tenant, so the index only contains rows that can match; (3) a filter-aware engine that traverses the graph while checking payload conditions; (4) over-fetching then filtering; (5) an exact scan when the filter is so selective that few rows remain (PostgreSQL's planner may choose this itself).

The hard part: filters meet ANN

Selective filters can break naive approximate search; engines solve it with iterative scans or filter-aware graphs, and hybrid search adds keyword signals.

A selective filter returns nothing, then iterative scan fixes it, run

I ran this SQL on PostgreSQL 16 with the pgvector extension, version 0.8.6, in a Docker container. With 100 tenants (about 200 rows each), the plain HNSW query with WHERE tenant = 7 ... LIMIT 10 returns 0 rows, because none of the nearest candidates belong to tenant 7. After SET hnsw.iterative_scan = relaxed_order the same query returns 10 rows. The exact numbers depend on the data and settings.

SET client_min_messages = warning;
ALTER TABLE big ADD COLUMN IF NOT EXISTS tenant int;
UPDATE big SET tenant = id % 100;                                   -- 100 tenants, about 200 rows each
ANALYZE big;
SELECT embedding AS qv FROM big WHERE id = 1 \gset

SELECT 'plain HNSW + WHERE tenant = 7' AS setting, count(*) AS rows_returned
FROM (SELECT id FROM big WHERE tenant = 7 ORDER BY embedding <-> :'qv' LIMIT 10) x;

SET hnsw.iterative_scan = relaxed_order;                            -- keep scanning until enough rows pass the filter
SELECT 'iterative scan' AS setting, count(*) AS rows_returned
FROM (SELECT id FROM big WHERE tenant = 7 ORDER BY embedding <-> :'qv' LIMIT 10) x;

Output:

            setting            | rows_returned 
-------------------------------+---------------
 plain HNSW + WHERE tenant = 7 |             0
(1 row)

    setting     | rows_returned 
----------------+---------------
 iterative scan |            10
(1 row)

Always test with your most selective filter

Test the smallest tenant and the rarest filter value. That is where empty results hide.

Quick check: Why can a very selective filter with an HNSW index return too few rows?

• Filters are not allowed
• The index returns a fixed number of nearest candidates and the filter then removes most of them
• The table is empty
• Vectors cannot have tenants