Vector databases and approximate nearest-neighbour search
A vector database stores embeddings with their metadata and an approximate nearest-neighbour (ANN) index, such as HNSW or IVF, that finds almost-the-closest vectors without comparing the query with every vector.
Why it matters
Exact search compares the query with every stored vector. With millions of vectors and many users, that is too slow and too expensive. ANN indexes search only a small, well-chosen part of the data, giving answers in milliseconds while keeping recall high. Choosing and tuning them is a core part of building retrieval at scale.
The idea
Comparing a question with every document vector is exact but slow once you have millions. Approximate nearest-neighbour (ANN) indexes, such as HNSW or IVF, find almost-the-closest vectors much faster by searching only a small part of the data. A vector database stores the vectors, the index and metadata (like source and date) together, so you can filter and search at once.
Finding a book by walking to the right section and shelf, instead of checking every book in the library.
A library's sections are exact. An ANN index can occasionally miss the true best match, so you trade a little accuracy (recall) for a lot of speed, and you should measure that trade.
How it works
- HNSW: build a graph where each vector links to its nearest neighbours, in several layers; higher layers hold fewer vectors and longer links.
- Search starts at an entry point on the top layer and greedily hops to whichever neighbour is closer to the query.
- When no neighbour is closer, drop a layer and continue. On the bottom layer, the closest vectors found are returned.
- IVF: cluster the vectors with k-means, and at query time search only the few clusters nearest the query.
- Product quantisation compresses vectors (for example to a few bytes each) to save memory, at some cost in accuracy.
- Tune the speed–recall trade-off (HNSW's ef_search, IVF's number of probed clusters) and measure recall@k against exact search.
- Store metadata (source, date, owner) with each vector, so you can filter and enforce permissions.
Key points
- Exact search: perfect recall, cost grows with the number of vectors.
- ANN: a little recall traded for a lot of speed.
- HNSW: graph-based, fast and accurate, memory-hungry.
- IVF: cluster-based; easy to understand and to scale.
- Measure recall@k against brute force on your own data.
- Metadata filters can hurt recall if applied after the search; good databases filter during it.
Common mistakes
- Assuming an ANN index returns the exact nearest neighbours.
- Never measuring recall after tuning for speed.
- Using a vector database for a few thousand vectors, where NumPy brute force is simpler and fast enough.
- Forgetting permissions, so search returns documents a user must not see.
Not true: A few thousand vectors: worth setting up a vector database.
In fact: With a few thousand vectors, comparing against all of them in NumPy takes milliseconds and is exact. An index only pays off at a much larger scale.
Not true: ANN index: the exact nearest neighbours, found faster.
In fact: ANN stands for approximate: it searches only part of the data and can miss a true neighbour. It trades a little recall for a lot of speed.
Part of Unit 5: AI engineering in the free ML Foundations course.