ANN Indexes (HNSW & IVF)
Scenario
You have 10 million document chunks. A user submits a question. Predict: if the database calculates cosine similarity between the query and every one of the 10 million stored vectors, how long does that take — milliseconds or seconds?
Think about the scale problem, then read on to see how ANN indexes solve it.
Mental model
ANN trades a tiny bit of accuracy for a massive speed gain by building a map that lets you skip checking 99% of the vectors.
A brute-force scan (called exact kNN) calculates the precise distance to every stored vector. That is too slow at scale. Approximate Nearest Neighbor (ANN) indexes build a shortcut map — like a multi-layer highway system (HNSW) or clustered neighborhoods (IVF) — so the search jumps straight to the right area. You might occasionally miss the absolute best match, but you will find 99% of the best matches in milliseconds instead of seconds.
Deep dive
A brute-force search (exact kNN) compares your query vector to every single stored vector. It guarantees the absolute best match, but it scales badly. With 10 million vectors, it does 10 million cosine calculations per query. That is too slow for production — a single query could take seconds.
Exact kNN scans everything. Perfect accuracy, terrible speed at scale.
To fix this, vector databases use ANN (Approximate Nearest Neighbor) indexes. They pre-organize the vectors into a structure so you do not have to scan them all. The trade-off: you might occasionally miss the mathematically closest vector. But you will find matches that are close enough in milliseconds instead of seconds.
ANN skips most distance calculations, trading perfect accuracy for massive speed.
**HNSW (Hierarchical Navigable Small World)** is the most popular ANN algorithm. It builds a multi-layer graph. The top layer has long 'highway' connections to jump far across the space quickly. Lower layers are denser, letting the search fine-tune its way to the nearest neighbors. HNSW is the default in pgvector and Pinecone.
HNSW navigates a multi-layer graph to zoom in on the nearest neighbors quickly.
**IVF (Inverted File Index)** uses a different approach. It groups vectors into clusters around a center point. When you query, the database compares your query to the cluster centers first, picks the closest cluster, then only searches inside that cluster. It ignores every other cluster entirely.
IVF groups vectors into clusters and searches only the most relevant one.
Because these algorithms are approximate, you control the accuracy-speed trade-off. You can tell the database to search a wider area (more accurate, slightly slower) or a narrower area (less accurate, much faster). For RAG, 'approximate' retrieval is perfectly acceptable — finding the 4th-best chunk instead of the 3rd-best rarely matters.
Pipeline recap: the ANN index is the engine inside your vector database making the Embed → Retrieve step fast at scale.
Code examples
Build an HNSW index in pgvector
CREATE INDEX ON documents
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);You must explicitly create the index. Without it, pgvector falls back to a slow exact scan. `m` and `ef_construction` control how dense and accurate the graph is when built — more detail on tuning is in the pgvector docs.
Tune query-time accuracy vs speed with ef_search
-- Increase ef_search to search a wider area (more accurate, slightly slower)
SET hnsw.ef_search = 100;
SELECT chunk_text
FROM documents
ORDER BY embedding <=> :query_vec
LIMIT 5;At query time, `ef_search` is the accuracy dial. A higher value evaluates more nodes, catching edge cases at the cost of a few extra milliseconds of latency.
Common mistakes
- Forgetting to build the index: If you insert vectors into pgvector without creating a vector index, every query silently runs a brute-force scan. In development with small data it is fast enough to hide the problem. In production with millions of rows, it will use 100% of your database CPU.
- Assuming ANN guarantees the absolute best matches: ANN is approximate. It uses shortcuts to skip parts of the vector space. Very rarely, the mathematically closest vector might be skipped. Do not write tests that assert the exact same ranked list every time — minor ordering differences are expected.
Glossary
- ANN
- Approximate Nearest Neighbor — a fast search method that skips most vectors by trading a tiny bit of accuracy for a massive speed gain.
- HNSW
- Hierarchical Navigable Small World — a popular ANN algorithm that builds a multi-layer map so the search engine can jump quickly to the right area.
- IVF
- Inverted File Index — an ANN method that groups similar vectors into clusters, so the search only looks inside the most relevant cluster.
Recall questions
- Explain the ANN trade-off to a classmate in plain words.
- At a high level, how does HNSW navigate a vector space quickly?
- If you query a pgvector table with 1 million rows and no vector index, what happens?
- What happens if you double ef_search in an HNSW index?
Questions & answers
Your RAG application works well with 1,000 documents at 50ms per query. After uploading 5 million documents, queries take 3 seconds and max out the database CPU. The code has not changed. What is the problem and how do you fix it?
The database is doing a full sequential exact kNN scan because no vector index was created. With 1,000 documents, brute force is fast enough to hide the problem. With 5 million, it is too slow. The fix is to create an ANN index (such as HNSW or IVF) on the vector column so the database skips most of the distance calculations.
Approach: Recognize the performance cliff that appears at scale. Sequential scan vs index is the classic database scaling problem, applied here to vector distance math.
You are tuning an HNSW index in production. You need faster query times and are willing to accept slightly less accurate retrieval. Which query-time parameter do you adjust and how?
Decrease `ef_search`. A smaller value means fewer candidate nodes are evaluated during the search, which makes queries faster but increases the chance of missing the true nearest neighbor. This is the main query-time accuracy vs speed dial for HNSW.
Approach: Know the core HNSW levers. `ef_search` controls query-time accuracy vs speed. `ef_construction` controls index build quality and cannot be changed after index creation.
Continue learning
Previous: Similarity Metrics