# Designing a vector database that stays fast at a billion vectors

Source: https://www.techinterview.org/post/3233476089/designing-a-vector-database-that-stays-fast/
Updated: 2026-07-02 · techinterview.org

The interesting part of designing a vector database shows up the second you accept that exact search is off the table. If an interviewer wants the 10 nearest neighbors of a query embedding inside a corpus of 500 million vectors, and you plan to score the query against all 500 million, you have designed something correct and unshippable. Approximate nearest neighbor search (ANN) is the actual problem, and everything after it is a negotiation: how much accuracy you give up to buy latency and to fit in RAM.

Say that out loud early, because it reframes the whole session. You are not storing vectors so much as building an index that lets you skip almost all of them on every query. So the first number to pin down is recall, usually recall@10: of the true 10 nearest neighbors, how many does your approximate search actually return? A recommender might be fine at 0.9. A RAG system feeding an LLM often wants 0.95 or higher, because a missed chunk turns into a wrong answer the user reads.

## Getting the scale on the whiteboard

Before touching an index, size the thing. Ask for the corpus size, the embedding dimension, the distance metric, the query rate, and the freshness requirement, then do the memory math in front of them, because that math drives every later choice.

A 768-dimension embedding in float32 is 768 × 4, about 3 KB. A hundred million of those is roughly 300 GB of raw vectors before any index overhead. That one calculation tells the interviewer you know the punchline: at real scale, vector search is a memory problem first and a CPU problem second. You can't keep 300 GB in one machine's RAM cheaply, so you are already talking about sharding, or about compressing the vectors, or both.

Query rate sets the replica count. If one shard replica serves 800 queries per second at your target recall and you need 5,000, that's seven-ish replicas per shard for load alone, more for redundancy. Freshness decides how hard the write path has to be: a product catalog that reindexes nightly is a different system from a chat app where an uploaded document must be searchable seconds later.

## Picking the index, and paying for it

This is where the interview earns its keep. Four index types come up, and a strong answer can say when each is the right call.

Flat is brute force: no index, exact results, a linear scan of every vector. It is the correct answer for a few hundred thousand vectors, and it doubles as the ground truth you measure recall against. It stops being viable somewhere past a million vectors once latency matters.

IVF (inverted file) runs k-means to cluster the space into `nlist` partitions, then at query time probes only the `nprobe` partitions closest to the query. Set `nlist` near the square root of your vector count as a starting point; `nprobe` is the recall dial you turn per query. IVF wins on lower memory and fast builds over huge, mostly static corpora. Its weakness is the cluster boundary: a true neighbor sitting just across a partition line gets missed unless you raise `nprobe`, which costs latency.

HNSW builds a layered proximity graph and walks it greedily from the top layer down, and it's the default in most production systems for a reason: high recall at low latency on data that keeps changing. You pay for it in memory and build time. Two build parameters, `M` (links per node) and `ef_construction`, trade graph quality against build cost; at query time, `ef_search` trades recall against latency. That last curve is the detail worth knowing cold, because it's non-linear. Pushing recall from 0.80 to 0.95 might add 30% latency, but going from 0.95 to 0.99 can cost three to five times the latency, since the search has to explore far more candidates to catch the last few stragglers.

Product quantization (PQ) is the compression trick that makes the memory math survivable. Split each vector into `m` subvectors, quantize each to one of 256 centroids, and store one byte per subvector. A 768-dim float32 vector at 3 KB drops to 96 bytes with `m`=96, roughly 32x smaller, so those 300 GB become under 10 GB. Distances get approximated from a lookup table. The cost is recall, which is why PQ almost always rides on top of IVF (IVF-PQ) and gets a re-ranking pass: pull a few hundred candidates with the compressed index, then re-score the top ones against full-precision vectors kept on SSD.

| Index | Memory | Build | Recall | Best for |
| --- | --- | --- | --- | --- |
| Flat | Raw vectors | None | Exact (1.0) | Under 1M vectors, ground truth |
| IVF | Raw plus small | Fast | Tunable via nprobe | Large, mostly static corpora |
| HNSW | Raw plus graph | Slow | High, tunable via ef_search | Changing data, low latency |
| IVF-PQ | Compressed | Medium | Lower, re-rank to recover | Billions of vectors, RAM-bound |

## Sharding a graph that hates being split

Once the corpus won't fit on one node, you shard. The subtlety a lot of candidates miss: an ANN index is not a hash table you can range-partition cleanly. If you split by some metadata key, a single query still has to fan out to every shard, because a query vector's neighbors can live in any of them. So the standard move is random or hash sharding by vector id, scatter the query to all shards, take each shard's local top k, and merge. Every shard runs its own HNSW or IVF index over its slice.

That fan-out carries a tail-latency problem worth naming. Query the whole set, wait for the slowest shard, and your p99 is set by whichever replica just hit a GC pause or a cold page. Hedged requests, sending to a second replica when the first is slow, and keeping shard count sane are the usual answers. More shards buys more parallelism per query but a worse tail, since now you wait on the slowest of many.

## The filtering question, which is where interviews go deep

Almost every real query is "nearest neighbors where tenant_id = 42 and language = 'en'". Combining a metadata filter with ANN is genuinely hard, and interviewers push on it because the two obvious answers both break.

Post-filtering searches the index for the top k, then drops results that fail the predicate. That's fine when the filter keeps most of the data. It falls apart on selective filters: ask for 10 results where only 0.1% of vectors match, and your top 200 from the index might contain zero survivors, so you over-fetch blindly and still come up short. Pre-filtering computes the matching set first and searches only inside it, but that fights the index structure, because an HNSW graph pruned down to 0.1% of its nodes loses the connections that made traversal fast and decays toward a linear scan of the matched set.

The production answer is filtered search folded into the traversal itself: evaluate the predicate as you walk the graph and only expand nodes that pass, with the filter pushed into the index rather than bolted onto either end. Qdrant and others keep extra payload-aware links so the graph stays connected even under a heavy filter. Knowing that pre- and post-filtering are both traps, and being able to say why, is usually the signal the interviewer is fishing for.

The follow-ups that separate answers tend to sound like this:

- "Recall dropped from 0.97 to 0.88 in production but the index config didn't change. What happened?" (often data drift against stale IVF centroids, or a distance-metric mismatch)

- "How do you keep two replicas of the same shard returning identical results?"

- "One tenant has 40 million vectors, another has 400. Same index for both?"

- "Cosine or dot product here, and does it change anything if the embeddings aren't normalized?"

That last one is a quiet trap. If your vectors are L2-normalized, cosine similarity, dot product, and Euclidean distance all rank neighbors in the same order, so the choice is free. If they aren't normalized, dot product starts rewarding longer vectors and cosine doesn't, and the two indexes return different neighbors. Pick the metric your embedding model was trained for, and normalize at write time if you want the cheap dot-product path.

## Updates, deletes, and the rebuild you can't avoid

HNSW has an awkward secret: it has no real delete. You can add nodes, but removing one means either leaving a tombstone that search skips over or rebuilding the graph. Most systems tombstone, filter dead ids out of results, and periodically rebuild a segment once the dead fraction climbs, much like compaction in an LSM tree. IVF absorbs inserts by assigning each to the nearest existing centroid, but those centroids were trained on old data, so after enough drift the clusters go lopsided and recall sags until you retrain and reassign.

This is why real vector databases borrow the segment model from search engines like Lucene: writes land in a small, fresh in-memory index; a segment is immutable once sealed; a background process merges small segments into larger ones and rebuilds their graphs; queries scatter across all live segments and merge. You get fast writes, bounded memory per segment, and a natural place to apply deletes, at the price of querying several indexes per request.

If you want to show range in the last few minutes, name what you're deliberately not building. You're describing FAISS-grade index internals wrapped in a serving layer; you are not reimplementing the ANN math from scratch, and you'd reach for pgvector on a small deployment or Milvus, Qdrant, or Pinecone once scale and filtering justify a dedicated system. The point the interviewer is testing is whether you understand the tradeoffs those tools already made, not whether you can out-engineer them on a whiteboard in 45 minutes.