Vector databases

1 When do we need one?

At small scale, we don’t. For example, the similarity search on this blog uses ~2000 vectors at 1024 dimensions stored in a flat numpy .npz file; brute-force Q @ E.T takes milliseconds and the whole matrix is about 7 MB.

Things start to change around 100k vectors. The core operation in any vector search — “given a query vector, find the \(k\) most similar vectors in the corpus” — is exact nearest neighbour search, and brute-force exact search is \(\mathcal{O}(Nd)\) per query (where \(N\) is the number of vectors and \(d\) is the dimensionality). At \(N = 2000\) this is trivial for typical vectors. At \(N = 100{,}000\) I might need to worry about quitting other apps so I can search. At \(N = 1{,}000{,}000\) a naive implementation will hard crash my laptop or be too slow to be usable.

2 The approximate nearest neighbor (ANN) problem

The fix is to accept approximate nearest neighbours — results that are very likely to include the true top-\(k\), but aren’t guaranteed to. In practice the recall loss is small (often >95%) and the speed gain is dramatic: \(\mathcal{O}(\log N)\) or better per query instead of \(\mathcal{O}(N)\).

This is a well-studied problem with a surprisingly active benchmarking community. ANN Benchmarks maintains standardised comparisons of algorithms across datasets, measuring the recall-vs-queries-per-second tradeoff. It’s worth browsing to get a feel for how the algorithms compare in practice — the Pareto frontiers are instructive.

The main families of ANN algorithms:

• HNSW (Hierarchical Navigable Small Worlds) — a graph-based index where each vector is a node, and edges connect nearby vectors at multiple scales. Query traversal walks the graph greedily from coarse to fine layers. This is the most popular choice in practice, used by Qdrant, Weaviate, pgvector, and most managed vector databases. The tradeoff: excellent recall/speed, but memory-hungry since the graph structure lives in RAM alongside the vectors.
• IVF-PQ (Inverted File Index with Product Quantization) — partitions the vector space into Voronoi cells (IVF), then compresses vectors within each cell using product quantization (PQ). At query time, only a few cells are searched. Used by FAISS. Better memory efficiency through quantization, at the cost of slightly lower recall.
• DiskANN — Microsoft’s approach for datasets that don’t fit in RAM. Builds a graph index on disk with a small in-memory “entry point” structure. Good for billion-scale search on commodity hardware.

At 10M+ vectors (~40 GB in float32 for 1024d), you also need memory-mapped storage or sharding — a flat array no longer fits comfortably in RAM. This is where a heavy-duty tool like a dedicated vector database earns its keep: it combines an ANN index with persistence, filtering, and (for the server options) replication.

3 Embedded (serverless) options

For the middle ground — 10k to ~1M vectors — embedded databases that run as a library (no server process) are often the right fit.

4 Managed / server options

For production systems at scale (millions to billions of vectors), we typically need a dedicated server.