Area 02 · RAG · Concept 06 of 20

HNSW Indexes

A graph-based index for approximate nearest-neighbour search. Fast even over millions of vectors.

01–10 · The basePhase 2 · Weeks 7–10≈ 1 hour

The idea

HNSW (Hierarchical Navigable Small World) links each vector to a few of its neighbours, in several layers. The top layers are sparse highways; the bottom layer has every vector. A search starts at the top, hops greedily toward the query, and drops down layer by layer until it finds close neighbours.

It is approximate: it may occasionally miss a true nearest neighbour. Settings trade speed for recall: m (links per node) and ef_construction at build time, ef_search at query time. Higher values mean better recall, more memory and slower builds or queries.

In pgvector you create it with CREATE INDEX ... USING hnsw (embedding vector_cosine_ops). Build it after bulk loading for speed. IVFFlat is the other option: faster to build, usually lower recall.

Why it matters

Without an index, search time grows linearly with your data. With HNSW it stays in milliseconds.

Picture it

Words to know

  • Recall (ANN)Share of true nearest neighbours the index actually returns.
  • ef_searchHow many candidates to explore per query.

Try it without code

Read a query plan

  1. In psql, run EXPLAIN ANALYZE on a vector search before and after creating the index.
  2. Compare execution times.

Use it in code

Create and tune an HNSW index in pgvector.

sql
CREATE INDEX IF NOT EXISTS chunks_embedding_hnsw
  ON chunks USING hnsw (embedding vector_cosine_ops)
  WITH (m = 16, ef_construction = 64);

SET hnsw.ef_search = 100;   -- higher = better recall, slower

EXPLAIN ANALYZE
SELECT id, body FROM chunks
ORDER BY embedding <=> (SELECT embedding FROM chunks WHERE id = 1)
LIMIT 5;
PRACTICE · TICK IT AFTER THIS

Insert 100,000 random vectors, time a query without an index, with HNSW, and with ef_search at 40 and 200.

Common mistakes

  • Building the index row by row during a huge import.
  • Using the wrong operator class (cosine vs L2) for your query operator.

Go deeper