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

  1. HNSW: build a graph where each vector links to its nearest neighbours, in several layers; higher layers hold fewer vectors and longer links.
  2. Search starts at an entry point on the top layer and greedily hops to whichever neighbour is closer to the query.
  3. When no neighbour is closer, drop a layer and continue. On the bottom layer, the closest vectors found are returned.
  4. IVF: cluster the vectors with k-means, and at query time search only the few clusters nearest the query.
  5. Product quantisation compresses vectors (for example to a few bytes each) to save memory, at some cost in accuracy.
  6. Tune the speed–recall trade-off (HNSW's ef_search, IVF's number of probed clusters) and measure recall@k against exact search.
  7. Store metadata (source, date, owner) with each vector, so you can filter and enforce permissions.

Key points

Common mistakes

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.