Vector databases and ANN indexes
In one line
A vector database finds the stored vectors closest to a query vector; at scale it uses approximate nearest neighbour (ANN) indexes such as HNSW, IVF and DiskANN that trade a little recall for orders of magnitude less latency, and the hard parts are memory, filtering and updates.
What it is
Embedding models turn text, images or users into vectors of a few hundred to a few thousand numbers, where nearby vectors mean similar things. Similarity search asks for the k vectors nearest to a query vector under a distance such as cosine, dot product or Euclidean (L2). For normalised vectors, cosine and dot product give the same ranking.
Exact search compares the query with every vector. For 100M vectors of 768 dimensions that is about 77 billion multiply-adds per query: fine for a few thousand vectors, far too slow for hundreds of queries per second over millions. Approximate nearest neighbour (ANN) indexes search only a small, well-chosen part of the data and return most of the true nearest neighbours, measured as recall@k (for example 95% of the true top 10).
The main index families: HNSW, a multi-layer graph where search greedily walks towards the query (fast, high recall, memory-hungry, the most common choice); IVF, which clusters vectors and searches only the nearest few clusters (less memory, needs training, recall depends on how many clusters you probe); product quantization (PQ) and scalar or binary quantization, which compress vectors so more fit in memory; and disk-based graphs such as DiskANN, which keep compressed vectors in RAM and full vectors on SSD.
A 'vector database' can be a dedicated system (Pinecone, Milvus, Qdrant, Weaviate), a feature of a database you already run (Postgres with pgvector, Elasticsearch or OpenSearch, Redis, MongoDB Atlas), or an object-storage-backed service for huge, cheap, slower indexes (Amazon S3 Vectors, turbopuffer). Choosing among them is mostly about scale, filtering needs, update rate and operations, not about raw benchmark speed.
Why interviewers ask
Vector search sits under RAG, semantic search, recommendations, deduplication and semantic caching, so interviewers ask about it both directly ('design a vector similarity search service') and inside AI designs. They look for memory sizing with real numbers, understanding of the recall-latency trade-off and its knobs, the filtering problem (tenant or category filters breaking ANN results), how updates and deletes work, and a sensible build-vs-reuse choice, such as 'pgvector until about tens of millions of vectors, then a dedicated engine'.
How it works
- 1Size first: memory for raw vectors = count x dimensions x bytes per value. 10M x 1,024 x 4 bytes (float32) = 41 GB. HNSW adds the graph: roughly 2 x M neighbour ids per vector on the bottom layer, about 128 bytes per vector at M = 16.
- 2HNSW build: each new vector is inserted into layer 0 and, with decreasing probability, into higher layers; it is linked to its M nearest neighbours found by a search of width ef_construction. Higher M and ef_construction give better recall but more memory and slower builds.
- 3HNSW search: start at the top layer, greedily move to closer neighbours, drop a layer and repeat; on the bottom layer keep a candidate list of size ef_search. Raising ef_search raises recall and latency. It is the main query-time knob (pgvector's default is 40).
- 4IVF: k-means splits vectors into nlist clusters (often around the square root of the vector count); a query checks the nprobe closest clusters. More probes, more recall, more latency. IVF needs representative data before training and re-training when the data distribution shifts.
- 5Quantization: int8 scalar quantization cuts memory 4x with small recall loss; binary quantization cuts it 32x but needs rescoring the top candidates with full vectors; PQ compresses to tens of bytes per vector. A common pattern is search compressed vectors, then rescore the top 100 with full-precision vectors.
- 6Filtering: queries usually carry filters (tenant, language, in-stock). Post-filtering (ANN top k, then filter) can return too few results when the filter is selective. Pre-filtering (filter, then exact search over the subset) is exact but slow for large subsets. Good engines filter during graph traversal (filterable HNSW, iterative scans) or you partition the index by the filter key, such as one namespace or partition per large tenant.
- 7Updates and deletes: HNSW handles inserts online, but deletes are usually tombstones that still occupy the graph; heavy churn lowers recall until the index is compacted or rebuilt. Segment-based engines (Milvus, Lucene-based search) write new segments and merge them in the background, like an LSM tree.
- 8Scale out: shard vectors across nodes (by tenant, or randomly with scatter-gather to all shards and a merge of their top k), and add replicas for read QPS. Random sharding means every query hits every shard, so tail latency is the slowest shard's.
- 9Measure: keep a sample of queries with exact (brute-force) answers, and track recall@10 and p99 latency for every index or parameter change. Tune for the recall the product needs, typically 0.9 to 0.99.
Worked example · Sizing semantic search for 100M product and review chunks
- Data: 100M chunks, 768-dimensional embeddings, 300 queries per second at peak, filters by marketplace and language, p99 target 100 ms for retrieval.
- Raw float32 vectors: 100M x 768 x 4 bytes = 307 GB. HNSW graph at M = 16: about 100M x 128 bytes = 13 GB more. Holding everything in RAM needs about 320 GB plus headroom, so several large nodes per replica.
- With int8 quantization: 100M x 768 x 1 byte = 77 GB for the in-memory search copy; keep float32 vectors on SSD for rescoring the top 100. This fits on two 64 GB nodes per replica.
- Sharding: 4 shards of 25M vectors each. A query fans out to all 4 shards in parallel, each returns its top 20, and the coordinator merges to the top 20. Shard latency p99 about 25 ms, so the merged p99 is around 35 to 40 ms.
- Replicas: one replica handles about 150 QPS at ef_search = 64 in a load test, so 3 replicas give 450 QPS of capacity for a 300 QPS peak with one replica down for maintenance.
- Recall check on 2,000 sample queries with brute-force ground truth: recall@10 = 0.93 at ef_search 64 and 0.97 at 128 (latency +40%). The product team accepts 0.95, reached at ef_search 96.
- Filters: language filter matches about 30% of data, fine for in-graph filtering. A marketplace with only 0.5% of data was getting too few results with post-filtering, so it gets its own small partition.
Picture it
An HNSW index is like asking for directions in a city. You first ask someone who knows the region (top layer) and get sent to the right neighbourhood, then ask locals (lower layers) who send you street by street to the exact house. You do not knock on every door in the city, and very occasionally you end up at a house next door to the best one, which is the 'approximate' part.
Key patterns
Compress, then rescore
When: Vectors do not fit in RAM at full precision
How: Search int8, binary or PQ-compressed vectors for the top 100 to 200 candidates, then rescore them with full-precision vectors from SSD or the database.
Partition by the dominant filter
When: Most queries filter on tenant, region or language
How: Give large tenants or segments their own index or namespace; use exact search for small ones. Avoids post-filtering that starves results.
Ground-truth recall checks
When: Any index or parameter change
How: Keep sample queries with brute-force answers; track recall@k and p99 together so you never buy speed with invisible quality loss.
Start in the database you have
When: Up to tens of millions of vectors, moderate QPS
How: Use pgvector, OpenSearch or Elasticsearch to keep one system, one backup story and one access-control model; move to a dedicated engine only when numbers demand it.
Real-world use
FAISS at Meta
Meta's open-source FAISS library implements IVF, PQ, HNSW and GPU search, and it is the base of many vector databases and research systems for billion-scale similarity search.
Spotify Annoy and Voyager
Spotify built Annoy for nearest-neighbour search in music recommendations and later released Voyager, an HNSW-based library, for faster and more accurate search.
Microsoft DiskANN
DiskANN keeps compressed vectors in memory and full vectors on SSD, serving billion-scale indexes on a single machine. Microsoft has used it in Bing and in Azure database services.
pgvector in Postgres
Adds a vector type and HNSW and IVFFlat indexes to Postgres, so vectors live next to relational data with transactions, joins and Row-Level Security. Newer versions add iterative index scans to help filtered queries return enough results.
Amazon S3 Vectors
AWS added vector indexes stored directly in S3 for large, cost-sensitive workloads that accept higher query latency than an in-memory engine, an example of the object-storage-backed design.
In a project
A Mumbai fintech runs RAG over 8M chunks of customer-support history in Postgres with pgvector. After a year, filtered queries for small business customers return only 2 or 3 chunks instead of 10, and p99 search latency has grown from 40 ms to 300 ms.
- Measure first: build 1,000 queries with brute-force ground truth per tenant size; recall@10 for small tenants is 0.41, for large ones 0.94. The problem is post-filtering on a global HNSW index.
- Enable iterative index scans so the index keeps searching until enough rows pass the tenant filter, and compare recall and latency.
- Move the 20 largest tenants to their own partitions with separate HNSW indexes; small tenants (under 50,000 chunks each) use exact search over their rows with a btree index on tenant_id, which is fast at that size.
- Find the latency cause: heavy daily deletes and re-inserts have left the HNSW index bloated. Schedule a REINDEX CONCURRENTLY weekly and monitor index size.
- Switch from float32 to halfvec storage to halve memory, verify recall drop under 1 point on the eval set.
- Write down the threshold for leaving Postgres: above about 50M vectors or 2,000 QPS, evaluate Qdrant or OpenSearch.
Impact: Recall@10 for small tenants rises from 0.41 to 0.97, p99 drops back to about 45 ms, the index fits comfortably in memory again, and the team has a measured trigger instead of a premature migration.
Trade-offs
Use it when
- Search by meaning: RAG retrieval, semantic product search, similar images, duplicate detection
- Recommendations from user and item embeddings
- Semantic caching of LLM prompts
- Approximate results are acceptable and measured, typically recall 0.9 to 0.99
Avoid it when
- Exact lookups and structured filters: use a normal index (btree, inverted index)
- Small collections (under about 100,000 vectors per query scope): exact search is simple and fast enough
- Keyword-heavy queries with ids and codes: vectors alone miss them; combine with keyword search
- Adding a separate vector database creates a second copy of permissions and data you cannot keep in sync
Common mistakes
- Choosing a vector database from a benchmark without sizing memory for your vector count and dimensions.
- Ignoring filters: post-filtering a global ANN index returns too few results for small tenants or rare categories.
- Never measuring recall against exact search, so tuning for latency silently ruins quality.
- Assuming deletes are free in HNSW; tombstones accumulate and degrade recall and latency until a rebuild.
- Mixing vectors from two embedding models, or forgetting to normalise vectors when the index uses dot product as cosine.
- Building a separate vector store with its own copy of permissions that drifts from the source of truth.
Interview questions
Quick revision
- Raw memory = vectors x dimensions x bytes (float32 = 4). 1M x 1,024 dims = about 4 GB.
- HNSW: graph, high recall, memory-hungry; knobs M, ef_construction, ef_search.
- IVF: clusters, probe nprobe of nlist; needs training data; less memory.
- Quantization: int8 = 4x smaller, binary = 32x smaller (rescore needed), PQ = tens of bytes per vector.
- DiskANN-style: compressed in RAM, full vectors on SSD.
- Recall@k vs exact search is the quality metric; measure it on every change.
- Post-filtering starves selective filters; use in-graph filtering, iterative scans or partitions.
- HNSW deletes are tombstones; rebuild or compact under heavy churn.
- Scatter-gather sharding: every shard per query, tail latency = slowest shard.
- Normalised vectors: cosine and dot product rank the same.
- Start with pgvector or your search engine; move when numbers demand it.
Check yourself
1. Roughly how much RAM do 20M float32 vectors of 1,536 dimensions need, before any index overhead?
2. Which HNSW parameter can you change at query time to trade latency for recall?
3. A query filters to a tenant that owns 0.1% of the vectors in a global HNSW index, and post-filtering is used. What is the likely result?
4. What does recall@10 = 0.95 mean for an ANN index?
See it in a full design
These walkthroughs use this lesson.
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.