Vector databases

A vector database stores embeddings, fixed-length arrays of numbers that a model produced from text, images or users, each with an ID and metadata, and answers one question fast: which stored vectors are closest to this one? It uses an approximate nearest-neighbour (ANN) index such as HNSW or IVF-PQ, giving up a little accuracy for speed-ups of a thousand times or more, and wraps it with filters, updates, replication and sharding. In an interview it is the retrieval engine behind RAG, semantic search and recommendations, provided you can say what it guarantees, what memory it needs and where it stops.

Picture it first: a spice trader in Khari Baoli

A wholesale spice trader has 50,000 sacks. A cook hands over a pinch of masala: “Find me sacks like this.” Smelling all 50,000 would take a week, so the trader has prepared.

Each sack carries a card of scores (heat, sweetness, smokiness), so “like this” means “close scores”. The godown is laid out in lanes by family, and he walks only the three lanes closest in style. Each sack also has a short chalked code, good enough to shortlist twenty; only those twenty get a proper taste test. “Organic only” rules sacks out along the way. New stock waits a day in the back room, and now and then the best match was in a fourth lane he never walked.

Map it back: the pinch is the query vector, a card is an embedding, the sack’s label is metadata, the lanes are IVF clusters and “three lanes” is nprobe, the chalked code is quantisation, the taste test is rescoring, “organic only” is a filter, the back room is indexing lag, and the missed sack is why recall is below 1.

Data model: vectors, metadata and one metric

A recap first. An embedding model turns content (a passage, a product, a photo, a user’s history) into a few hundred to a few thousand numbers, placed so that similar things land close together; the query goes through the same model, so “similar” becomes “nearby”. Models, chunking and retrieval quality belong to embeddings and semantic search; this page is about the database.

A record (a point in Qdrant, a row in pgvector) is:

• An ID, normally the source row’s key, such as doc_42#chunk_7. Writes are upserts by ID.
• A vector of fixed dimension, say 768, which every query must match. Float32 by default; most engines also take float16, int8 or bits.
• Metadata: tenant, category, price, permission groups. Used for filters, never for similarity.

A collection fixes the dimension and the distance metric at creation: L2 (straight-line distance), dot product (larger is closer, and longer vectors score higher) or cosine (the angle only). On vectors normalised to length 1 all three rank identically, since ‖a − b‖² = 2 − 2(a · b), so normalise at write time and use the dot product, which pgvector recommends for normalised vectors as the fastest.

Namespaces (Pinecone) or list partitions (pgvector) slice an index per tenant, so tenant 42’s query never touches tenant 43’s vectors. Sparse vectors, one weight per vocabulary term and mostly zeros, can sit beside dense ones for hybrid retrieval fused by rank, as search end to end shows. In pgvector the whole model is one table:

CREATE TABLE doc_chunks (
  id         bigint PRIMARY KEY,         -- same ID as the source chunk
  tenant_id  bigint NOT NULL,
  doc_id     bigint NOT NULL,
  model      text   NOT NULL,            -- embedding model that produced the vector
  embedding  vector(768) NOT NULL        -- 4 × 768 + 8 = 3,080 bytes
);
CREATE INDEX ON doc_chunks USING hnsw (embedding vector_ip_ops)
  WITH (m = 16, ef_construction = 64);   -- the defaults

SET hnsw.ef_search = 100;                -- default 40
SET hnsw.iterative_scan = relaxed_order; -- 0.8.0+: scan on until 10 rows pass the filter
SELECT id, doc_id FROM doc_chunks
WHERE tenant_id = 42
ORDER BY embedding <#> $1                -- negative inner product: ascending = most similar
LIMIT 10;

Exact search, and why it stops scaling

Exact search compares the query with every vector: N × d multiply-adds, and N × d × 4 bytes read. For 10 million 768-dimension vectors that is 7.7 billion multiply-adds and 30.7 GB read per query.

The HNSW paper’s brute-force baseline took 94 ms for 1 million 128-dimension vectors (0.128 billion multiply-adds). Ours is 7.68 ÷ 0.128 = 60 times the work: about 5.6 s per query. A GPU streaming memory at roughly 3 TB/s reads 30.7 GB in about 10 ms, and a batch of queries can share one pass. Fine for offline jobs; far too costly per query for an online service, which is why ANN indexes exist.

Exact search still wins for small sets or few queries (Redis suggests its FLAT index under 1 million vectors; FAISS, when you will run only 1,000–10,000 queries), and it is your ground truth.

Recall@k and the triangle you trade on

Recall@k is the share of the true k nearest neighbours that the index returned: 9 of exact search’s top 10 is recall@10 = 0.9. Measure it by running sampled queries both ways. Every knob trades recall, latency and memory, with build time as a hidden fourth cost: more candidates buy recall with latency; compression buys memory with recall unless you rescore. State a target: “recall@10 of at least 0.95 at a p99 under 50 ms”.

How ANN indexes find neighbours

HNSW: a layered graph you walk downhill

HNSW (Malkov and Yashunin, arXiv 2016, IEEE TPAMI 2018) is the index that pgvector, Qdrant, Weaviate, Redis and Elasticsearch all offer. Each vector is a node linked to up to M close neighbours, and draws a random top layer; each layer up holds about 1 in M of the nodes below, like a skip list. With M = 16, 100 million vectors make about 7 layers (log₁₆ 10⁸ ≈ 6.6).

Search hops greedily towards the query on each layer, drops a layer when no neighbour is closer, and on layer 0 keeps the efSearch best candidates, expanding them before returning the top k. Insertion runs the same search with efConstruction candidates and links the node to up to M neighbours per layer, 2M on layer 0.

• M (6–48 in the paper; 16 by default in pgvector, Qdrant and Elasticsearch) buys recall on hard data with memory.
• efConstruction (64 in pgvector, 100 in Qdrant) buys graph quality with build time.
• efSearch (40 in pgvector) is the query-time dial. Each expanded candidate costs up to 2M = 32 distances, so a search computes thousands of distances, not 100 million.

Memory: the FAISS guidelines put HNSW at d × 4 + M × 2 × 4 bytes per vector, so 3,072 B of float32 plus 128 B of links at d = 768 and M = 16. Elastic’s guide, used in part 4, budgets half that for links; plan for 128 B.

You gain the best recall per millisecond in RAM, with no training step. You pay with RAM (Elastic says HNSW needs most vector data in memory), slow builds (every insert is a search) and hard deletes: other nodes route through the one you remove, so the paper left removal as future work, FAISS’s HNSW cannot delete, and databases use tombstones and rebuilds.

IVF: cluster first, then search a few clusters

IVF runs k-means to find nlist centroids and files each vector under its nearest one; a query scans only the nprobe nearest lists. For 10 million vectors, pgvector’s starting rule (lists = √rows ≈ 3,162, probes = √lists ≈ 56) scans 1.8% of the data, about 177,000 vectors instead of 10 million. You gain small overhead and fast builds. You pay with a training step, misses when the true neighbour sits just across a cell boundary, and drift that needs retraining as the data changes.

Product quantisation: 32 times smaller vectors

Product quantisation (Jégou, Douze and Schmid, 2011) splits a vector into m sub-vectors, learns 256 centroids per sub-space, and stores each sub-vector as a one-byte centroid ID: m bytes per vector. At d = 768 and m = 96, 3,072 bytes become 96, 32 times smaller. With asymmetric distance computation the query stays uncompressed: it fills a 96 × 256 table of distances once, and each stored vector then costs 96 lookups. The paper’s IVFADC system, now called IVF-PQ, stores PQ codes of each vector’s residual inside IVF lists, and was tested on two billion vectors.

Scalar and binary quantisation, with rescoring

int8 stores each dimension in one byte: 4 times smaller, with a small recall loss. Binary keeps one bit per dimension and compares codes by Hamming distance: 32 times smaller and much rougher (Elastic’s BBQ format takes ⌈768 ÷ 64⌉ × 8 + 14 = 110 bytes). Elasticsearch now quantises by default; part 5 has the versions. Recover accuracy by oversampling and rescoring: fetch, say, 4k candidates by code, then re-rank them with full vectors read from disk, as pgvector’s README shows. The rule: codes in RAM, full vectors on disk.

DiskANN: a billion vectors on one machine

DiskANN (Subramanya et al., NeurIPS 2019) puts a single-layer Vamana graph, built with long-range edges so searches need few hops, and the full vectors on SSD, keeping only PQ codes (32 bytes per vector) in RAM to steer the walk. A beam search reads 2–8 nodes per round trip, since a few random SSD reads cost about as much as one, and each node’s full vector arrives with its neighbour list, so re-ranking needs no extra reads. The result: one billion vectors on a 16-core machine with 64 GB of RAM, over 5,000 queries a second at under 3 ms mean latency and 95% recall@1. Milvus (DISKANN) and Redis (SVS-VAMANA) ship Vamana-based indexes.

Libraries: FAISS and ScaNN

FAISS, from Meta, is a library of all these indexes on CPU and GPU; its 2017 paper built a nearest-neighbour graph over one billion vectors in under 12 hours on four GPUs. Google’s ScaNN is a similar library.

Filtering: where vector search gets hard

Real queries carry conditions: passages this employee may read, dishes that are vegetarian and deliverable to 560034. There are three ways to combine a filter with an ANN index.

• Post-filter: run the ANN search, then drop rows that fail. A selective filter starves the result: pgvector’s README notes that with hnsw.ef_search at 40 and a condition matching 10% of rows, about 4 rows come back. Elasticsearch treats a filter outside the knn clause the same way.
• Pre-filter, then exact search: resolve the filter with an ordinary index (B-tree or bitmap), then score the survivors exactly. Perfect recall, and fast when few rows match: 5,000 rows × 768 is about 4 million multiply-adds. At 1 million matches it is 0.77 billion, about half a second at the HNSW paper’s brute-force rate.
• Filtered traversal: walk the graph, route through non-matching nodes but count only matching ones, and stop when k match. Qdrant adds graph edges per indexed payload field and, since 1.16, offers ACORN, which looks two hops out when direct neighbours fail. Weaviate feeds an allow-list from its inverted index into the walk, with ACORN the default since 1.34. Elasticsearch filters inside the knn clause this way, with an ACORN heuristic by default on indices created in 9.1 or later. pgvector 0.8.0 added iterative index scans, which keep reading the index (up to 20,000 tuples by default) until enough rows pass.

The selectivity trap: in a relational database a stricter filter makes a query faster; in HNSW it can make it slower, because the walk must visit more nodes to collect k matches, until so few rows match that Lucene, for one, switches to brute force. The hardest case is a medium filter (1–10% of rows) unrelated to the query’s meaning. When a filter is always present and has few values, such as tenant or language, make it a partition: a namespace or partitioned table per value, so each query searches a small, unfiltered index.

Guarantees, precisely

Writes become visible after the index catches up

Most vector stores acknowledge a write once it is in a log and index it in the background, so a vector is durable before it is searchable:

• pgvector writes the index entry in the same transaction: visible on commit.
• Elasticsearch and OpenSearch show writes after the next refresh, 1 s by default (Elasticsearch).
• Milvus offers four levels per collection or request: Strong, Bounded (the default), Session (you see your own writes) and Eventually. Writes are timestamped in a write-ahead log, and a search waits until the serving node has applied everything up to its guarantee timestamp.
• Pinecone documents serverless indexes as eventually consistent; writes return a log sequence number and queries report the highest one indexed, so a client can check.
• turbopuffer is strongly consistent by default, because queries also scan the unindexed tail of its log; its eventual mode can be up to about an hour stale.
• Amazon S3 Vectors documents writes as strongly consistent.

Read-your-writes matters for chat memory (“what did I just tell you?”) and for a user who asks about a file just uploaded; for catalogue search, seconds of lag are fine.

Results are approximate, deletes are tombstones

Recall is below 1 by design, and two replicas whose graphs were built or merged differently can return slightly different top-k lists for the same query. Deep paging through ANN results is unreliable: fetch a larger k once and paginate in the application.

A graph cannot cheaply drop a node others route through, so a delete marks a tombstone that searches skip until a merge, compaction or vacuum removes it. Until then it costs memory and hops, and Qdrant’s docs note that many soft-deleted points can split the graph. An update is a delete plus an insert. For a privacy erasure request, the vector leaves results at once and the disk after compaction; say both.

Durability, and no transaction with your source of truth

Durability comes from a log: pgvector inherits Postgres’s write-ahead log and replication, Milvus appends to a WAL and seals segments into object storage, and turbopuffer and Pinecone log each write before acknowledging it.

Unless pgvector lives in the same database, there is no atomic “update the product and its embedding”. Keep the source database authoritative, use the same ID in both stores, feed the vector store from change data capture or an outbox through an embedding worker, make upserts idempotent, and store the model version with each vector. The index returns IDs; read price, stock and permissions from the database.

How it scales

Memory decides the shape

Size a vector store by RAM per copy. For 100 million 768-dimension vectors:

• float32: 100,000,000 × 768 × 4 B = 307.2 GB; float16 halves it to 153.6 GB.
• int8: 100,000,000 × 768 B = 76.8 GB.
• PQ with 96 one-byte codes, or one bit per dimension: 100,000,000 × 96 B = 9.6 GB.
• An HNSW graph at M = 16 adds 100,000,000 × 128 B = 12.8 GB.

Every replica needs it all again, plus headroom. Part 4 did the same sum for 50 million vectors in Elasticsearch: 42.4 GB per copy with int8.

Shards, scatter-gather and replicas

When one node is not enough, shard by ID hash (database sharding). Similarity gives no key to route on, so every query goes to every shard: each returns its local top k and a coordinator merges them, the scatter-gather of Elasticsearch’s query phase and web search. The slowest shard sets the latency. If every query is scoped to one tenant, shard by tenant instead: one shard per query, at the risk of hot shards for giant tenants.

Replicas add throughput. Since every query hits every shard, each shard needs peak QPS ÷ QPS per node copies. Suppose a benchmark shows one node with 45 GB of int8 vectors and graph answering 800 queries a second at recall@10 = 0.95. For 100 million vectors (89.6 GB) at a 4,000 QPS peak: 2 shards × (4,000 ÷ 800 = 5 copies) = 10 nodes.

Disk, object storage and GPUs

Three designs cut the RAM bill. Disk-based indexes such as DiskANN keep 32-byte codes in RAM (3.2 GB for 100 million vectors) and the rest on NVMe. Object-storage-first services keep every namespace in S3-like storage and cache the hot ones: turbopuffer reports cold queries at p50 874 ms and warm ones at 14 ms for 1 million documents, and Pinecone serverless builds immutable “slabs” in object storage, merging small ones into larger, better-indexed ones. Amazon S3 Vectors, generally available since December 2025, holds up to 2 billion vectors per index, answering in under a second when queried rarely and around 100 ms when queried often. You gain object-storage prices and idle namespaces that cost almost nothing; you pay with cold starts, slower writes and lower QPS ceilings.

GPUs shine at bulk work: index builds, re-embedding, batched brute force. Milvus’s GPU indexes, such as CAGRA, need the data in GPU memory and return at most 1,024 results.

Limits and numbers

Defaults and limits from current documentation (October 2026); the paper figures are from their stated year and hardware.

When to pick it, and when not

Pick a dedicated vector database when vectors are the product: hundreds of millions or more, heavy filtering, many tenants, or a need for disk and GPU indexes.

Pick something else when:

• You have under about 10 million vectors and run Postgres. pgvector needs no pipeline and commits with your rows.
• You need keyword search and facets anyway. Elasticsearch or OpenSearch keeps one index in sync (choosing a search engine).
• Exact tokens matter: SKUs, model numbers, names. Vectors blur them (types of search).
• The job is offline, like nightly “similar items”: FAISS in a batch job, results to a key-value store.

Common interview usage

Going deeper: failure modes

• Recall decays silently. Nothing reports that recall fell from 0.95 to 0.8 as data grew tenfold, tombstones piled up or IVF cells drifted. Run a nightly job: 1,000 sampled queries against exact search, an alert below target, then retune efSearch or nprobe, or rebuild.
• A new embedding model means re-embedding everything. Vectors from different models are not comparable, and the dimension often changes. Build a new index beside the old one, backfill from the source (part 7’s 50 million products take about 7 hours on one GPU), dual-write, compare, then switch, as in the blue-green rebuild. Store the model version on every vector.
• Memory blow-ups. Budget replicas × (vectors + graph) + headroom. When HNSW’s working set spills out of RAM, Elastic warns that latency “climbs sharply”, and pgvector builds far faster when the graph fits in maintenance_work_mem.
• Slow builds and merges. Every HNSW insert is a search. Bulk-load first and build the index after, and expect Lucene-based engines to rebuild graphs as segments merge.
• Noisy tenants and hot shards. In a shared index, one tenant’s vectors affect another’s recall and speed, as pgvector’s README notes. Give each tenant a partition or namespace, and giants their own shards (noisy neighbours).
• Metric and dimension mismatches. The dot product on unnormalised vectors favours long ones, and a query embedded by the wrong model returns plausible nonsense. Pin model, dimension and metric in configuration and validate on write.

Cheat sheet

How to say it in the interview

“Documents live in Postgres; the vector index is a rebuildable copy. CDC feeds an embedding worker that upserts 768-dimension vectors keyed by chunk ID, with tenant, permission groups and model version as metadata. At 100 million chunks, float32 would be 307 GB, so I’d use HNSW over int8 vectors, about 90 GB per copy with the graph, in two shards, with replicas sized from a benchmark at recall@10 of 0.95. Queries scatter to both shards with the permission filter applied during the walk, merge the top 50, rerank to 8 and hydrate from Postgres. New documents are searchable within seconds, and a nightly job measures recall against exact search.”

Why not just use pgvector? Under about 10 million vectors on Postgres, I would: transactions, joins, no pipeline. Its limits are one primary’s RAM, 2,000 indexed dimensions for vector, and vector queries competing with OLTP traffic.

How do you tune HNSW? Start at M = 16 and efConstruction 64–100, then raise efSearch until sampled queries hit the recall target against exact search. Raise M only if recall plateaus; memory grows with it.

What if a filter matches 2% of rows? Post-filtering returns almost nothing, and exact search over 2% of 100 million is 2 million vectors. Use filtered traversal (ACORN-style), or a partition if the filter is a tenant or language.

How would you hold a billion vectors? Float32 is 1,000,000,000 × 3,072 B ≈ 3 TB; 96-byte PQ codes are 96 GB. Shard IVF-PQ by ID with rescoring, or use DiskANN, which held a billion vectors on one 64 GB machine.

Where to go next

• Embeddings and semantic search: models, chunking and retrieval quality.
• Types of search and choosing a search engine: semantic beside keyword search.
• Elasticsearch in depth and search end to end: kNN in Lucene, RRF and rebuilds.
• PostgreSQL and Elasticsearch: where vectors often live first.
• Database sharding and data replication: scaling in general.
• Design RAG search over company documents and design a recommendation feed: vector stores in full designs.

References and further reading

1. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (Malkov and Yashunin, arXiv 2016; IEEE TPAMI 2018)arxiv.orgThe HNSW layers, greedy descent, M, efConstruction and ef, the 2·M limit on layer 0, graph memory of 60–450 bytes per vector, and the 94 ms brute-force baseline.
2. Product quantization for nearest neighbor search (Jégou, Douze and Schmid, IEEE TPAMI 2011)inria.hal.scienceSub-vectors with 256 centroids each, one byte per sub-vector, asymmetric distance computation, and the inverted-file IVFADC system tested on two billion vectors.
3. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node (Subramanya et al., NeurIPS 2019)proceedings.neurips.ccThe Vamana graph on SSD with PQ codes in RAM, beam search, implicit re-ranking, and the one-billion-vector, 64 GB, 5,000 queries a second result.
4. Billion-scale similarity search with GPUs (Johnson, Douze and Jégou, 2017)arxiv.orgThe FAISS GPU design: exact and IVF-PQ search on GPUs, and k-NN graphs over 95 million images in 35 minutes and one billion vectors in under 12 hours.
5. FAISS wiki: Guidelines to choose an indexgithub.comHNSW memory of d × 4 + M × 2 × 4 bytes, no removal from HNSW, every index in RAM, IVF list counts by dataset size, and when flat search is enough.
6. pgvector README (v0.8.7)github.comTypes and dimension limits, HNSW and IVFFlat options and defaults, post-filtering, iterative index scans since 0.8.0, binary quantisation with re-ranking, tenant partitioning and recall checks.
7. Elasticsearch documentation: Tune approximate kNN searchelastic.coBytes per vector for int8 and BBQ, HNSW graph memory of num_vectors × 4 × m, and why HNSW needs its working set in the page cache.
8. Qdrant documentation: Indexingqdrant.techPayload indexes, filterable HNSW with extra edges, the full-scan threshold, HNSW defaults, and the ACORN search algorithm since 1.16.
9. Milvus documentation: Consistency Level (v3.0)github.comStrong, Bounded (default), Session and Eventually, implemented with WAL timestamps, service time and guarantee timestamps.
10. Amazon S3 Vectors: Limitations and restrictionsdocs.aws.amazon.comTwo billion vectors per index, 4,096 dimensions, write and query limits, and metadata limits; with the December 2025 general-availability announcement.