Vector databases,
and approximate nearest neighbors.

An embedding model maps text (or images) to a vector in a high-dimensional space where similar meanings sit close together. Semantic search, RAG, and recommendations all reduce to one operation: given a query vector, find the stored vectors nearest to it. That's a k-nearest-neighbor (kNN) query.

The naive way — brute force — compares the query against every stored vector and sorts by distance. That's exact, but it costs O(N × d) per query: with millions of vectors of hundreds or thousands of dimensions each, a single search touches billions of numbers. Far too slow for interactive use, and it only gets worse as your corpus grows. A vector database exists to make this fast.

"Nearest" needs a distance metric. Three are common, and they must match how your embedding model was trained.

For most modern text embeddings, vectors are normalized and cosine = dot product, so the choice collapses. The rule: use the metric your embedding model was trained with — mixing metrics quietly wrecks relevance.

The key idea that makes vector search fast is approximate nearest neighbor search. Instead of guaranteeing the exact top-k, an ANN index cleverly organizes the vectors so a query only has to examine a small, promising subset rather than everything — returning the true neighbors almost always.

Quality is measured by recall: of the true top-k neighbors, what fraction did the index return? An index at 0.98 recall finds 98% of the real neighbors while examining a tiny fraction of the data. Every ANN index exposes knobs that trade recall against latency (and memory): search harder for higher recall but slower, or search less for speed. This recall–latency–memory triangle is the whole game.

Why exact search doesn't scale — and ANN does

The cost is not subtle. An exact (brute-force) search compares the query against every stored vector, so it's linear in the corpus:

Double your data, double the work — forever. A graph index like HNSW instead walks a proximity graph greedily, touching a small, query-dependent neighborhood that grows only logarithmically:

That is the difference between a linear scan and a sublinear walk — and it's the entire reason vector databases exist.

This isn't hand-waving. The runnable index below builds a real navigable graph and measures it: recall vs. the exact ground truth, and how many vectors each query actually touched. You'll watch recall climb from ~0.36 to ~0.94 as you raise the search effort — and watch the cost climb with it. That's the triangle, in numbers you can change.

HNSW (Hierarchical Navigable Small World) builds a graph where each vector links to nearby ones across layers; searching greedily walks the graph toward the query, which is remarkably fast and accurate — the default for many stores, at the price of holding the graph in memory. IVF (Inverted File) clusters the space and, per query, only scans the nearest clusters (you tune how many you probe: more = higher recall, slower). Product quantization compresses each vector into a small code, so you can hold vastly more vectors in memory and compare them cheaply — often combined with IVF (IVF-PQ) for billion-scale search. Real systems mix these; the choice depends on your scale, memory budget, and recall target.

Real queries aren't pure similarity — you want "nearest chunks where tenant = X and date > last week." So vectors are stored with metadata, and search is filtered. This is subtler than it looks, because the ANN index navigates by geometry, not by your filter.

Post-filtering (retrieve top-k, then drop non-matches) is simple but can return too few results if the filter is selective — the matches might all be past the top-k. Pre-filtering (restrict the search to matching vectors) gives correct results but is harder to do efficiently inside an ANN index. Good vector databases integrate filtering into the index so it's both correct and fast; how well they do it is a key differentiator.

Corpora change: documents are added, updated, deleted. ANN indexes — especially graph-based ones — are optimized for search, not for constant mutation, so handling upserts and deletes efficiently is a real engineering concern. Vectors are typically written to a mutable buffer and periodically merged into the main index; deletes are often soft (marked, later compacted).

This introduces a freshness lag — a just-added vector may not be searchable for a moment — and the usual consistency questions. For search over a slowly-changing knowledge base this is fine; for real-time use you tune the refresh interval. And remember the embedding-consistency rule from RAG: if you change the embedding model, every vector must be re-embedded and the index rebuilt, since vectors from different models aren't comparable.

Past one machine, vector databases shard the index across nodes and scatter-gather queries: each shard returns its local top-k, and the results are merged. Replicas add read throughput and availability. Because ANN indexes are memory-hungry (especially HNSW), the memory-vs-cost math often drives the architecture — which is exactly where PQ compression earns its keep.

Most production retrieval isn't pure vector search either. Hybrid search fuses vector similarity with keyword/BM25 to catch exact terms (names, codes) that embeddings miss, and pairs with a reranker for precision. A vector database is one component of a retrieval stack, not the whole thing.

Not every project needs a dedicated vector database. At modest scale — up to a few million vectors — a Postgres extension like pgvector keeps your vectors alongside your relational data and metadata in one system you already run, which is simpler and often plenty fast. Libraries like FAISS give you the raw ANN index in-process with no server at all.

Reach for a dedicated vector database when you hit real scale (tens of millions to billions of vectors), need high query throughput, want advanced filtering and hybrid search out of the box, or require horizontal scaling and operational features you'd otherwise build yourself. Start simple; upgrade when the numbers demand it — not because vector databases are fashionable.