HNSW and IVFFlat indexes

conceptThe concept

HNSW (hierarchical navigable small world) builds a layered graph in which each vector links to its nearest neighbours. Search starts at the top layer and greedily walks toward the query. Parameters: m (links per node, default 16) and ef_construction (candidate list size while building, default 64) at build time; hnsw.ef_search (candidate list while searching, default 40) at query time. Higher values mean better recall, more memory and slower builds.

IVFFlat clusters vectors into lists with k-means at build time, then searches only the ivfflat.probes nearest clusters. It builds faster and uses less memory than HNSW, but must be built after the table has representative data, and recall drops as data drifts from the original clusters.

The operator class must match the query operator: vector_cosine_ops for <=>, vector_l2_ops for <->, vector_ip_ops for <#>.

Recall is the share of the true nearest neighbours that the index returns. Measure it by running the same query with the index disabled and comparing.

whyWhy it matters

An exact scan of 10 million 1536-dimension vectors reads about 60 GB. An HNSW index answers in milliseconds. Without measuring recall, though, you do not know how many of the right answers you are silently missing.

Use caseReal-world scenario

A team indexes 8 million product embeddings with HNSW (m = 16, ef_construction = 128). An offline job samples 1,000 queries each night, compares index results with exact results at ef_search 40 and 100, and alerts when recall at 10 drops below 0.95.

Try itExamples

Run and edit these in the interactive lesson.

BEGIN;
CREATE TABLE items AS
SELECT g AS id, ARRAY(SELECT random() FROM generate_series(1, 16) WHERE g > 0)::real[]::vector(16) AS v
FROM generate_series(1, 3000) g;
CREATE INDEX items_v_hnsw ON items USING hnsw (v vector_cosine_ops) WITH (m = 16, ef_construction = 64);
ANALYZE items;
EXPLAIN (COSTS OFF)
SELECT id FROM items ORDER BY v <=> (SELECT v FROM items WHERE id = 1) LIMIT 10;
ROLLBACK;

BEGIN;
CREATE TABLE items AS
SELECT g AS id, ARRAY(SELECT random() FROM generate_series(1, 16) WHERE g > 0)::real[]::vector(16) AS v
FROM generate_series(1, 3000) g;
CREATE TEMP TABLE exact AS
SELECT id FROM items ORDER BY v <=> (SELECT v FROM items WHERE id = 1) LIMIT 10;
CREATE INDEX ON items USING hnsw (v vector_cosine_ops);
ANALYZE items;
SET LOCAL hnsw.ef_search = 10;
CREATE TEMP TABLE approx AS
SELECT id FROM items ORDER BY v <=> (SELECT v FROM items WHERE id = 1) LIMIT 10;
SELECT count(*) AS found_of_10 FROM approx JOIN exact USING (id);
ROLLBACK;

BEGIN;
CREATE TABLE items AS
SELECT g AS id, ARRAY(SELECT random() FROM generate_series(1, 16) WHERE g > 0)::real[]::vector(16) AS v
FROM generate_series(1, 3000) g;
CREATE INDEX items_v_ivf ON items USING ivfflat (v vector_l2_ops) WITH (lists = 50);
ANALYZE items;
SET LOCAL ivfflat.probes = 5;
EXPLAIN (COSTS OFF)
SELECT id FROM items ORDER BY v <-> (SELECT v FROM items WHERE id = 1) LIMIT 10;
ROLLBACK;

SET maintenance_work_mem = '8GB';          -- keep the graph in memory while building
SET max_parallel_maintenance_workers = 7;   -- parallel HNSW build
CREATE INDEX CONCURRENTLY kb_chunks_embedding_hnsw
  ON kb_chunks USING hnsw (embedding vector_cosine_ops)
  WITH (m = 16, ef_construction = 128);

-- per query or per transaction
SET LOCAL hnsw.ef_search = 100;

internalsUnder the hood

HNSW search returns at most ef_search candidates, so a LIMIT larger than ef_search cannot be filled from the index alone. A WHERE filter applied after the index scan can discard most of those candidates; pgvector 0.8 added iterative scans (hnsw.iterative_scan) that keep searching until enough rows pass the filter. HNSW builds are much faster when the graph fits in maintenance_work_mem.

Avoid / preferDo this, not that

CREATE INDEX ON kb_chunks USING hnsw (embedding vector_l2_ops);
SELECT id FROM kb_chunks ORDER BY embedding <=> $1 LIMIT 5;

CREATE INDEX ON kb_chunks USING hnsw (embedding vector_cosine_ops);
SELECT id FROM kb_chunks ORDER BY embedding <=> $1 LIMIT 5;

CREATE TABLE docs (...);
CREATE INDEX ON docs USING ivfflat (embedding vector_cosine_ops) WITH (lists = 1000);
-- then load 5 million rows

-- load the data first, then
CREATE INDEX ON docs USING ivfflat (embedding vector_cosine_ops) WITH (lists = 1000);

PitfallsCommon mistakes

• Never measuring recall, so a tuning change silently returns worse results.
• Asking for LIMIT 100 with hnsw.ef_search at its default of 40.
• Building HNSW with a tiny maintenance_work_mem and waiting hours instead of minutes.

LimitsWhen not to use it

Below roughly tens of thousands of vectors, or when queries always filter down to a few thousand rows first (one tenant, one category), an exact scan is fast enough, gives perfect recall and needs no tuning. Add an approximate index when exact search no longer meets latency targets.

SecuritySecurity notes

Index builds on large tables are heavy: run them with CREATE INDEX CONCURRENTLY and resource limits, and do not let application roles create indexes freely. A role that can set maintenance_work_mem very high can exhaust server memory.

ChallengeTry it yourself

BEGIN;
CREATE TABLE items AS
SELECT g AS id, ARRAY(SELECT random() FROM generate_series(1, 16) WHERE g > 0)::real[]::vector(16) AS v
FROM generate_series(1, 3000) g;
CREATE TEMP TABLE exact AS
SELECT id FROM items ORDER BY v <=> (SELECT v FROM items WHERE id = 1) LIMIT 20;
CREATE INDEX ON items USING hnsw (v vector_cosine_ops);
ANALYZE items;
DO $$
DECLARE ef integer; hits integer;
BEGIN
  FOREACH ef IN ARRAY ARRAY[10, 40, 100] LOOP
    PERFORM set_config('hnsw.ef_search', ef::text, true);
    SELECT count(*) INTO hits
    FROM (SELECT id FROM items ORDER BY v <=> (SELECT v FROM items WHERE id = 1) LIMIT 20) a
    JOIN exact USING (id);
    RAISE NOTICE 'ef_search % found %/20', ef, hits;
  END LOOP;
END $$;
ROLLBACK;

InterviewQuestions you should be able to answer

QuizCheck your understanding

4 questions with instant feedback in the interactive lesson; a wrong answer goes into your review deck.

Go deeperOfficial documentation

• pgvector README
• Index types