Vector Indexing
Fast search without searching everything
Brute-force similarity over millions of vectors is too slow — indexing (HNSW, IVF, PQ) trades small recall loss for massive speed. Understanding index structure explains storage, latency and accuracy trade-offs.
What you will learn
- Explain why exact search doesn't scale
- Compare ANN index families
- Set up a basic index with trackable recall
What is this?
Exact nearest-neighbor search compares a query against every vector — correct but hopeless at millions of rows. ANN (approximate nearest neighbor) indexes organize vectors so queries examine only promising regions, trading a little recall for enormous speed. Index choice (HNSW graph, IVF partitions, PQ compression) determines your latency, memory and accuracy triangle.
Why do you need it?
- 1M vectors × 1536 dims brute-force is ~seconds per query; ANN is milliseconds.
- Recall@k is a dial: faster index ≠ necessarily bad, just calibrated.
- Index memory (RAM) often dwarfs vector storage on disk.
- Keeping the index healthy (rebuilds, inserts, deletes) is an operational skill.
Mental model
A library's index cards vs reading every shelf
Vector indexing
An exact search reads page 1 of every book (slow but 100% thorough). An index card system skips to shelves likely to contain the quote — 99% of the time the right shelf, dramatically faster. Occasionally the best match hides on an unindexed shelf (recall loss).
How it works
- HNSW builds a layered proximity graph; each level has fewer nodes, log-scale navigation.
- IVF partitions space into clusters; queries probe the nearest clusters only.
- PQ compresses vectors into short codes for cheaper distance computation.
- Indexes hold HNSW/IVF metadata in RAM; vectors may live on disk or object storage.
- Recall@k is measured by rerunning a sample against brute-force and comparing retained hits.
The ANN trade triangle.
In production
- RAG systems query HNSW indexes for near-real-time top-k retrieval.
- Massive product catalogs use IVF + PQ to stay within RAM at 100M+ vectors.
- Recall audits sample queries and quantify the index's quality gap.
Best practices
- Always measure recall@k on YOUR query distribution after index tuning.
- Keep the index in RAM or accept compressed-PQ on SSD deliberately.
- Rebuild/rebalance indexes on a schedule; deletes accumulate graph rot.
- Document index params (M, efConstruction) in config, not code comments.
Common mistakes
- Blindly 'heavier index = better' — over-indexing wastes RAM.
- Forgetting recall is configuration: a moderate graph reduces recall visibly.
- Ignoring delete-tombstone drift in cross-iteration indexes.
Common issues
Recall falls off a cliff after hundreds of thousands of insertsHNSW graph degradation from inserts/deletes
Schedule periodic graph rebuilds or re-inserts.
Index RAM high vs expectedDimension/EF parameters underestimated
Model the memory formula; tune or switch to PQ.
Debugging tips
- Query latency fine but recall collapsed → index params or embed model drift.
- RAM blew past budget → HNSW M/efConstruction high or dims bigger than expected.
- Index empty overnight → ingest/update job failed silently.
Interview checkpoint
Hands-on lab
- Run a brute-force scan over a small deterministic dataset
- Build a 4-bucket index from sign tests relative to the centroid
- Measure candidate reduction and name the recall tradeoff
Flat Scan vs Signed Projection Index
30 min · intermediate
Quick quiz
ANN stands for…
ANN indexes are lossless — same results as brute force always.