HNSW indexes in pgvector

How HNSW finds neighbours#

HNSW (Hierarchical Navigable Small World) links every vector to its nearest neighbours, then adds sparser "express" layers on top. A search enters at the top, greedily hops towards the query on each layer, drops down, and finishes with a wider search on the bottom layer, where every vector lives. That last step keeps a list of the ef_search best candidates seen so far.

A real HNSW built in your browser over 260 random 2-D points. Real embeddings have 1,536 dimensions, but the mechanics are identical: a handful of upper-layer hops, then a bounded search at the bottom. Push ef_search up and watch recall rise along with the distance computations.

Creating the index#

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

Choose the operator class for the distance your queries use — vector_cosine_ops for <=>, vector_ip_ops for <#>, vector_l2_ops for <->. A mismatch silently falls back to a full scan (see the plans). Over 2,000 dimensions, index a halfvec cast (guide).

ef_search: the knob to turn first#

hnsw.ef_search changes per query and costs nothing to experiment with. We ran our 1,000 held-out queries at seven values against the default-built index:

What the curves say:

• The default of 40 is a sensible middle: 94.7% recall at 2.9 ms.
• Doubling ef_search roughly doubles latency (40 → 100: 2.9 ms → 5.3 ms) while recall gains shrink fast: +3.5 points from 40 → 100, +1.2 from 100 → 400.
• Exact search is not an option at scale: without an index the same query took 441 ms — 150× slower.

Set it where it applies — per transaction keeps it from leaking into other queries on a pooled connection:

demo=# SET hnsw.ef_search = 100;
SET

demo=# BEGIN;
BEGIN

demo=# SET LOCAL hnsw.ef_search = 200;
SET

demo=# SHOW hnsw.ef_search;
 hnsw.ef_search 
----------------
 200
(1 row)

demo=# COMMIT;
COMMIT

demo=# SHOW hnsw.ef_search;
 hnsw.ef_search 
----------------
 100
(1 row)

Or per role: ALTER ROLE search_api SET hnsw.ef_search = 100;. It must be at least your LIMIT; without iterative scans an HNSW scan never returns more than ef_search rows.

Build options: m and ef_construction#

These are fixed at CREATE INDEX time. m is how many links each vector keeps per layer (twice that on the bottom layer); ef_construction is the candidate-list size used while inserting. Better graphs give more recall per millisecond of search — at the cost of build time and, for m, size.

ef_construction: going from 64 to 128 bought 1.2 points of recall at ef_search = 40 for 1.7× the build time. Going on to 256 added only 0.4 points for another 1.7×. Dropping to 32 saved build time but capped recall at 0.988 even with ef_search = 400.

m: m = 32 reached 0.975 at ef_search = 40 versus 0.947 for the default, but each search step checks twice as many links, so per-millisecond the advantage is small, and the build took 1.6× longer. m = 8 built fastest but topped out at 0.987.

Index size didn't change with m at all for these vectors — 781 MB for m 8, 16 and 32 alike. A 1,536-dim element (6.2 KB) plus its neighbour list fills an 8 KB page by itself, so the extra links fit in space that would otherwise be wasted. For smaller vectors m does add size; the storage calculator models it.

Build time and memory#

Most "pgvector is slow" reports are slow builds. Same 100,000 vectors, same index, only the setup changed:

Three things decide build time, and the third one surprised us.

1. maintenance_work_mem must hold the graph#

With PostgreSQL's 64 MB default, pgvector logged hnsw graph no longer fits into maintenance_work_mem after 9753 tuples and the build took 10.4 min instead of 3.4 min — 3.1× slower. 256 MB was barely better (8.3 min). Both notices imply the same ~6,881 bytes of memory per 1,536-dim element, so budget about 6.7 KB × rows. Set it for the session only:

SET maintenance_work_mem = '4GB';

2. Your parallel workers may never start#

The standard advice is to raise max_parallel_maintenance_workers. We did — and PostgreSQL launched zero workers: 3.4 min with the setting at 3, 3.4 min with it at 0. Counting processes in pg_stat_activity during the build confirmed it.

The cause is TOAST. A 1,536-dim vector is 6 KB, so Postgres stores it out of line; our 100,000-row table had 795 MB of vectors in TOAST but a main heap of only 5.0 MB. PostgreSQL decides how many workers a CREATE INDEX gets from the size of the main heap, and below min_parallel_table_scan_size (8 MB) the answer is none. The fix is one line:

ALTER TABLE items SET (parallel_workers = 3);
SET max_parallel_maintenance_workers = 3;
SET maintenance_work_mem = '4GB';
CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops);

The heap grows with row count, so bigger tables cross the 8 MB line on their own. To check, we rebuilt at 250,000 and 500,000 rows and counted workers again: with heaps of 13 MB and 25 MB, PostgreSQL launched all 3 workers without any table option (2.6 min and 5.1 min), and setting parallel_workers = 3 changed nothing (2.6 min and 5.4 min). At 52 bytes of heap per row, the cut-off for 1,536-dim vectors is roughly 160,000 rows — so the trap catches small and medium tables, and a table that grows past it suddenly builds several times faster. Setting parallel_workers explicitly is harmless at any size. In Docker, parallel builds also need --shm-size at least as large as maintenance_work_mem (why).

3. Load first, index second#

Creating the index on an empty table and then loading is the slowest path: every row is inserted into the graph one at a time, with no parallelism. Loading 100,000 rows into an indexed table took 13.8 min; loading (65 s) then building (3.6 min) took 4.7 min. For ongoing writes the per-row cost is what matters: a single-row INSERT into the indexed 100K table took 10 ms versus 0.78 ms without the index.

Watching a build#

demo=# SELECT phase, round(100.0 * blocks_done / nullif(blocks_total, 0), 1) AS "%",
demo-#        tuples_done, tuples_total
demo-# FROM pg_stat_progress_create_index;
     phase      |  %   | tuples_done | tuples_total 
----------------+------+-------------+--------------
 building index | 39.6 |       39634 |            0
(1 row)

Run it from another session. Use CREATE INDEX CONCURRENTLY on a live table so writes aren't blocked — it takes longer, and a failure leaves an invalid index to drop.

How it scales#

We repeated the default build at 250,000 and 500,000 rows, with the same 1,000 queries:

Index size grew exactly with row count (one 8 KB page per 1,536-dim row). Build times are not comparable across sizes: the 100K build ran as a single process, while the 250K and 500K builds got 3 parallel workers automatically (see above). With 3 workers at every size, the build took 56 s, 2.6 min and 5.4 min for 100K, 250K and 500K rows — slightly worse than linear in row count. Median query latency grew far slower than the table, from 2.8 ms to 4.1 ms, while exact search went from 447 ms to 1016 ms. Recall at a fixed ef_search slips gently as the table grows (0.948 → 0.931 at 40), so re-check recall after big data growth.

Inserts, updates, deletes and vacuum#

• Inserts go into the graph immediately; no rebuild is ever required.
• Deletes and updates leave dead elements that VACUUM must repair, which for HNSW means reconnecting their neighbours — vacuum can be slow on heavily-updated tables. A REINDEX INDEX CONCURRENTLY before vacuuming can be faster than repairing in place.
• Run 0.8.3 or later. Earlier versions had a bug that could corrupt HNSW indexes during vacuum (check your version).

Checklist#

1. Load data first, then CREATE INDEX.
2. Before building: SET maintenance_work_mem to about 7 KB × rows (for 1,536 dims), and ALTER TABLE … SET (parallel_workers = N) so workers actually start.
3. Match the operator class to your query's operator.
4. Measure recall with real queries (query), then tune hnsw.ef_search.
5. Keep the index in memory: size shared_buffers and RAM for it.
6. Filtering? Turn on iterative scans.

Frequently asked questions