Filtering and iterative index scans

The problem: filters run after the index#

An HNSW scan collects ef_search candidates (40 by default), and Postgres then applies your WHERE clause. If only 1% of rows match, about 1% of 40 candidates survive. Here it is on a 20,000-row table where category = 7 matches 1% of rows, with the HNSW index forced:

demo=# RESET hnsw.ef_search;
RESET

demo=# SET enable_seqscan = off;
SET

demo=# SET enable_bitmapscan = off;
SET

demo=# SELECT count(*) FROM (SELECT id FROM items WHERE category = 7 ORDER BY embedding <=> (SELECT embedding FROM items WHERE id = 1) LIMIT 10) t;
 count 
-------
     0
(1 row)

demo=# SET hnsw.iterative_scan = relaxed_order;
SET

demo=# SELECT count(*) FROM (SELECT id FROM items WHERE category = 7 ORDER BY embedding <=> (SELECT embedding FROM items WHERE id = 1) LIMIT 10) t;
 count 
-------
    10
(1 row)

demo=# RESET hnsw.iterative_scan;
RESET

demo=# RESET enable_bitmapscan;
RESET

demo=# RESET enable_seqscan;
RESET

Measured: four selectivities, four strategies#

Setup: 100,000 DBpedia × OpenAI text-embedding-3-large (1,536-dim) vectors, HNSW m 16 / ef_construction 64, ef_search = 40, LIMIT 10, and a tenant_id filter keeping 50%, 10%, 1% or 0.1% of rows. Ground truth is the exact top-10 among the matching rows. First, the HNSW index on its own (no B-tree on the filter column):

Without iterative scans the index runs dry as soon as filters get selective: 4.0 rows instead of 10 at 10%, 0.39 at 1%, 0.03 at 0.1%. With relaxed_order the scan keeps walking the graph until LIMIT is met (bounded by hnsw.max_scan_tuples, 20,000 by default).

Now recall and latency, adding the realistic case where a B-tree on tenant_id exists and the planner chooses:

What we learned:

• Broad filters (50%) are a non-issue: every strategy used the HNSW index and returned 0.939 recall in about 2.9 ms.
• At 10%, iterative scans are the big win. Plain HNSW returned 4.0 rows (recall 0.398); relaxed_order returned all 10 at 0.946 recall in 6.3 ms. Given a B-tree, the planner instead chose an exact sort of the 10,000 matching rows — perfect recall, but 58 ms, 9.2× slower.
• At 1% and below, the B-tree wins. Exact search over a few hundred rows took 6.3 ms at 1% and 0.82 ms at 0.1% with recall 1.0, while relaxed_order had to walk far through the graph (37 ms at 1%).
• strict_order cost recall here — 0.899 vs 0.946 for relaxed_order at 10%. Use relaxed_order and re-sort in SQL if you need exact ordering (below).

Iterative scan settings#

If a relaxed scan's slight disorder matters, re-sort in a materialised CTE:

demo=# SET hnsw.iterative_scan = relaxed_order;
SET

demo=# WITH relaxed AS MATERIALIZED (
demo-#   SELECT id, embedding <=> (SELECT embedding FROM items WHERE id = 1) AS distance
demo-#   FROM items WHERE category = 7
demo-#   ORDER BY distance LIMIT 10
demo-# )
demo-# SELECT id, round(distance::numeric, 4) AS distance FROM relaxed ORDER BY distance;
  id   | distance 
-------+----------
  9007 |   0.1632
  3407 |   0.1720
 10107 |   0.1762
  1907 |   0.1766
  6707 |   0.1779
  9807 |   0.1898
 15307 |   0.1943
  1007 |   0.1947
 17207 |   0.1963
 17807 |   0.1980
(10 rows)

demo=# RESET hnsw.iterative_scan;
RESET

Partial indexes for hot values#

When a few filter values dominate traffic — one big tenant, one language — give each its own index. The planner uses it automatically when the query's WHERE matches:

demo=# CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops) WHERE (category = 7);
CREATE INDEX

demo=# EXPLAIN (COSTS OFF) SELECT id FROM items WHERE category = 7 ORDER BY embedding <=> (SELECT embedding FROM items WHERE id = 1) LIMIT 10;
                      QUERY PLAN                      
------------------------------------------------------
 Limit
   InitPlan 1
     ->  Index Scan using items_pkey on items items_1
           Index Cond: (id = 1)
   ->  Index Scan using items_embedding_idx1 on items
         Order By: (embedding <=> (InitPlan 1).col1)
(6 rows)

For many values, consider partitioning the table by the filter column (PARTITION BY LIST (tenant_id)): each partition gets its own HNSW index and Postgres prunes the rest.

Recipe#

1. Index the filter columns with ordinary B-trees.
2. Enable iterative scans where filtered vector queries run: SET hnsw.iterative_scan = relaxed_order;
3. Check the plan with EXPLAIN for each common filter shape.
4. Measure rows returned and recall for your most selective real filter.
5. Hot values get partial indexes; many tenants get partitions.

Frequently asked questions