Vector Databases & ANN Search

ANN trades a little recall for orders-of-magnitude speed

Level 2's "Vector Databases & Embeddings" lesson introduced embeddings and similarity search; this lesson credits that first pass and goes deep on the ANN index families and the operational surface. A vector database stores high-dimensional embeddings (typically 384 to 3072 floats) and answers "find the k vectors most similar to this query vector" fast. Exact nearest-neighbor search compares the query against every stored vector, which is O(N) per query. At 1B vectors that is billions of distance computations per query, hopelessly slow. So production uses Approximate Nearest Neighbor (ANN) search, which trades a small amount of recall for orders-of-magnitude speedup. The entire discipline is choosing where on the recall / latency / memory / cost surface you want to sit.

The ANN index families

• HNSW (Hierarchical Navigable Small World). A multi-layer graph you greedily walk from a coarse top layer down to dense lower layers. Highest recall and lowest latency of the common indexes, but it lives in RAM and RAM is the cost driver: 1B vectors of 768 float32 dims is roughly 3TB of raw vectors before graph overhead. Knobs: M (graph degree), ef_construction (build quality), ef_search (candidates explored at query time, the main recall/latency dial).
• IVF and IVF-PQ. IVF clusters vectors into nlist partitions; a query probes only nprobe nearest partitions instead of all of them. PQ (Product Quantization) then compresses each vector into a few bytes, cutting memory 10 to 50x at some recall cost. IVF-PQ is how you fit a billion vectors in memory affordably. Knob: nprobe trades recall for latency.
• DiskANN. A graph index designed to live on NVMe SSD, not RAM, so you serve billion-scale from a single node cheaply at the cost of SSD read latency. The pick when RAM cost dominates and you can tolerate a few extra ms.

Exact (flat) search is fine only up to maybe a few hundred thousand vectors, or as a re-ranking step over a small ANN candidate set.

Laid out side by side, the choice is really one question, and it is a budget question:

Table

Recall and latency differ modestly across the three production families. Where the index lives differs by orders of magnitude in cost, which is why that column, not the recall column, usually decides the answer.

Index	Where it lives	Recall	Query latency	Cost at 1B vectors	Main dial
Flat (exact)	RAM	perfect	O(N), unusable at scale	prohibitive	none
HNSW	RAM	highest	lowest	~3 TB raw, plus graph overhead	ef_search
IVF-PQ	RAM, quantized	good	low	10 to 50x cheaper than HNSW	nprobe
DiskANN	NVMe SSD	good	a few ms more	cheapest per vector	beam width

Filtered and hybrid search

Real queries are "similar vectors WHERE category = docs AND updated_at > X." There are three strategies. Post-filter: run ANN, then drop results failing the predicate. Cheap but broken when the filter is selective, because your top-k might all get filtered out, returning too few results. Pre-filter: compute the allowed id set first, then search only within it. Correct but expensive if the allowed set is huge and the index cannot restrict its walk. Modern stores use filtered-HNSW that pushes the predicate into the graph traversal so it only visits allowed nodes. Interview nuance: the right answer names the pre vs post filter tradeoff and says selective filters need the predicate inside the index, not bolted on after.

Operations and build-vs-buy

Vectors stream in and get deleted. HNSW handles inserts but deletes leave tombstones that degrade the graph, so you periodically rebuild. Sharding splits the index across nodes (scatter-gather query, merge top-k); replication gives read throughput and HA. Index builds are CPU and memory heavy, so you build offline and hot-swap. And re-embedding is the migration nobody plans for: switching embedding models invalidates every stored vector, forcing a full re-embed and reindex, which for a billion vectors is a multi-day, expensive job. Version your embeddings.

For under a few million vectors with existing Postgres, pgvector is genuinely enough and saves a system. Dedicated stores (Pinecone, Weaviate, Qdrant, Milvus) earn their keep at scale, with filtered search, hybrid, and sharding built in. OpenSearch adds vectors to an existing search cluster.

Recap: ANN trades recall for speed via HNSW (RAM, high recall), IVF-PQ (quantized, memory-cheap), or DiskANN (SSD-scale); tune ef_search / nprobe; handle filtered search as a pre-filter pushed into the index; and plan for rebuilds and re-embedding migrations.