Similarity search with vector databases

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

A vector database stores embeddings (arrays of a few hundred to a few thousand floats) and answers "which stored vectors are closest to this one" by cosine, dot product, or Euclidean distance.
Exact search compares the query with every vector, which is too slow at tens of millions of vectors, so systems use approximate nearest neighbour (ANN) indexes and trade a little recall for orders of magnitude in speed.
The main index families are graph-based (HNSW), cluster-based (IVF), and compressed (product quantization), often combined. Each has a different memory, build-time, and update profile.
Metadata filters ("only this tenant's documents"), hybrid keyword plus vector ranking, and freshness under updates are where most production difficulty lies.
Options range from extensions (pgvector, OpenSearch k-NN) to libraries (FAISS) to dedicated services (Milvus, Qdrant, Weaviate, Pinecone).

How it works

Embeddings and distance

A model maps text, images, or users into a vector space where similar items land near each other. A 768-dimension float32 vector is 3 KB. For normalized vectors, cosine similarity equals dot product, and ranking by either is equivalent to ranking by Euclidean distance. The database does not understand meaning; quality depends entirely on the embedding model, and changing the model means re-embedding everything.

Why exact search does not scale

Brute force over 10 million 768-dimension vectors is 7.7 billion multiply-adds per query, around 30 GB of memory traffic. Even with SIMD that is tens of milliseconds per query on one core, and it grows linearly. Classic spatial trees (k-d trees) do not help above roughly 20 dimensions because almost every branch must be visited.

IVF: cluster then probe

Run k-means to pick, say, 4,096 centroids. Each vector is stored in the list of its nearest centroid. A query finds the nprobe nearest centroids and scans only those lists. With nprobe = 32, the query scans under 1% of the data. Recall falls when a true neighbour sits just across a cluster boundary, so nprobe is the recall versus latency dial. FAISS's guidance grows the list count with the data: 4√N to 16√N lists below a million vectors, 65,536 for 1 to 10 million and 262,144 for 10 to 100 million, each trained on 30 to 256 sample vectors per list, so 4,096 lists suit only a small collection (FAISS wiki). IVF builds fast and handles appends well, but centroids drift as the data distribution changes.

HNSW: navigable graphs

Hierarchical Navigable Small World builds a multi-layer proximity graph (Malkov and Yashunin). Each vector connects to about M (often 16 to 32) near neighbours. Upper layers are sparse and allow long jumps; the bottom layer contains everything. A search starts at the top, greedily moves toward the query, drops a layer, and repeats, keeping a candidate list of size ef_search. HNSW gives excellent recall at low latency, but the graph links cost memory (roughly M × 2 × 4 bytes per vector per layer), builds are slow, and deletes are awkward, usually handled with tombstones and periodic rebuilds.

Product quantization: compress the vectors

PQ splits each vector into, for example, 96 subvectors of 8 dimensions and replaces each with the id of the nearest of 256 sub-centroids: 96 bytes instead of 3 KB, a 32x reduction. Distances are approximated with lookup tables (Jégou et al., TPAMI 2011). IVF-PQ lets a billion vectors fit in RAM on one large machine; a re-ranking step with full vectors on the top few hundred candidates restores precision.

Filtering and hybrid search

"Nearest vectors where tenant_id = 7 and lang = 'de'" is hard. Post-filtering ANN results can return nothing if the filter is selective. pgvector applies WHERE after the index scan, so with the default ef_search of 40 a filter matching 10% of rows returns only about 4 rows. Since version 0.8.0 it can keep scanning (hnsw.iterative_scan) until enough rows pass or 20,000 tuples have been visited (pgvector). Pre-filtering to a candidate set and then brute forcing works for small sets. Modern engines integrate filters into graph traversal: Qdrant adds extra graph edges per indexed payload value and switches to a plain scan when its planner estimates few matches (Qdrant docs), and ACORN traverses a predicate subgraph, reporting 2 to 1,000 times the throughput of earlier filtered methods at the same recall (Patel et al., 2024). Partitioning by tenant avoids the problem for the commonest filter. Hybrid search runs keyword (BM25) and vector retrieval in parallel and merges, often with reciprocal rank fusion.

Down the stack

Layer 1The contract

A vector index promises approximate top-k nearest neighbours under a chosen metric (L2, inner product, or cosine), not exact results. The quality guarantee is statistical: recall@k measured on a sample of queries against brute-force ground truth, usually targeted at 0.9 to 0.99. Recall depends on tuning parameters (ef_search, nprobe), on the data distribution, and on filters, and it can drift as data is inserted and deleted. Results can shift after unrelated updates, and a restrictive filter can silently return fewer than k results.

Layer 2The mechanism

In HNSW (hnswlib, FAISS IndexHNSWFlat, pgvector), each inserted vector draws a top layer from an exponential distribution, so each layer holds roughly 1/M as many nodes as the one below. Insertion searches greedily down from the entry point, then on each layer at or below its top runs a beam search of width ef_construction and keeps up to M neighbours (2M on the bottom layer), chosen by a heuristic that prefers neighbours in different directions over a cluster of near-duplicates. pgvector stores the graph in ordinary 8 KB Postgres pages as element tuples (the vector plus metadata) and neighbour tuples, with defaults of m = 16, ef_construction = 64, and hnsw.ef_search = 40. Its IVFFlat index uses lists centroids and searches ivfflat.probes of them, 1 by default, which is why untuned IVFFlat recall is often poor. Its indexes take vector columns of up to 2,000 dimensions; larger embeddings need halfvec (16-bit floats, up to 4,000) or binary quantization (pgvector).

FAISS's IndexIVFPQ stores, in each inverted list, the PQ code of each vector's residual (the vector minus its centroid), which quantises far more accurately than coding raw vectors. At query time it builds a lookup table per probed list: for each of the m subspaces, the distance from the query's subvector to all 256 sub-centroids. The distance to a database vector is then m table lookups and additions, called asymmetric distance computation because the query stays exact while the database side is compressed.

Layer 3The machine

A 768-dimension float32 vector is 3,072 bytes, which is 48 cache lines. An AVX2 fused multiply-add handles 8 floats per instruction and AVX-512 handles 16, so the arithmetic is cheap; the real cost is pulling 3 KB from memory. HNSW visits a few hundred to a few thousand vectors per query, and each is a random access, so search is memory-latency bound and implementations prefetch the next neighbours while computing the current distance. The bottom-layer links add about 2M × 4 bytes per vector, 128 bytes at M = 16.

PQ changes the bottleneck. A 96-byte code fits in two cache lines, and FAISS's fast-scan variants use 4-bit codes so that a whole lookup table fits in SIMD registers and a single shuffle instruction (pshufb and its AVX2 form) performs 16 or 32 table lookups at once. When an index outgrows RAM, every HNSW hop becomes a random disk read. Disk-oriented designs such as DiskANN keep compressed codes in memory and lay out each node's full vector with its neighbour list in one 4 KiB sector, so each hop costs exactly one SSD read. The DiskANN paper served a billion-point dataset from one 64 GB workstation at over 5,000 queries per second, under 3 ms mean latency and above 95% recall@1 (Subramanya et al., NeurIPS 2019). pgvector without enough memory degrades the same way, one random 8 KB page read per visited element.

Why it's built this way

Exact search scans every vector and high dimensions defeat spatial trees, so indexes give up exactness for speed.
Search cost is dominated by memory traffic per vector, so graphs minimise how many vectors are touched and PQ shrinks each one.
Compression loses precision, so systems re-rank a short candidate list with full vectors.
Random hops are cheap in RAM and expensive on disk, so disk-based indexes pack each hop into one sector-sized read.
Quality is statistical, so recall must be measured continuously, not assumed.

Diagram

flowchart TD
    Q["Query embedding"] --> C["Find nprobe nearest centroids"]
    C --> L1["Inverted list 17"]
    C --> L2["Inverted list 942"]
    C --> L3["Inverted list 3051"]
    L1 --> S["Score candidates (PQ distances)"]
    L2 --> S
    L3 --> S
    S --> F{"Metadata filter"}
    F --> RR["Re-rank top 200 with full vectors"]
    RR --> K["Top k results"]

Worked example

A support-search product embeds 40 million help-centre chunks with a 1,024-dimension model. Raw float32 vectors are 4 KB each: 160 GB.

HNSW, full precision: 160 GB of vectors plus about 10 GB of graph links with M = 32. That needs several memory-optimized nodes per replica, and recall@10 of 0.98 at around 5 ms. Building the index takes hours, and with two replicas the RAM bill is the dominant cost.

IVF-PQ with re-ranking: 65,536 lists and 128-byte PQ codes give 5 GB of codes in RAM. Full vectors move to SSD for re-ranking the top 100 candidates per query, which costs 100 random 4 KB reads, about 1 ms on NVMe. Recall@10 lands around 0.95 at 8 ms, on one modest node per replica.

The team measures recall against exact search on a 10,000-query sample and finds that answer quality in the product does not change between 0.95 and 0.98. They pick IVF-PQ and spend the savings on a better embedding model, which moved quality far more than index tuning did.

In the wild

Instacart, 2025: moving vector retrieval into Postgres to get filters right. Instacart had run semantic search as a separate FAISS service with an HNSW index per retailer, hundreds in all. FAISS could not filter on document attributes during retrieval, so the service over-fetched and filtered afterwards, and keeping two systems in sync caused inconsistencies. Moving to pgvector next to the existing Postgres full-text search, with indexes grouped by retailer characteristics instead of one per retailer, cut zero-result searches by 6% in an A/B test (Instacart).
Spotify, 2023: replacing Annoy with an HNSW library. Spotify had used Annoy, its own open-source nearest-neighbour library, in production, but it had fallen to the middle of public benchmarks. Its replacement, Voyager, is built on hnswlib and reports more than 10 times the speed at the same recall, up to 50% more accuracy at the same speed, and up to 4 times less memory by storing vectors as 8-bit floats (E4M3) (Spotify).

Trade-offs

Option	Strengths	Weaknesses	Choose when
Brute force (flat)	Exact, simple, easy updates	Linear cost per query	Under about 1 million vectors, or after a selective filter
HNSW	High recall, low latency	High memory, slow builds, awkward deletes	Latency-critical, data fits in RAM
IVF (flat or PQ)	Fast build, tunable, compact with PQ	Lower recall at the same latency, centroid drift	Very large collections, cost-sensitive
DiskANN-style SSD graph	Billions of vectors with little RAM	SSD latency, more complex	Huge corpora, moderate QPS
pgvector in an existing database	Transactions, joins, one system	Lower ceiling at scale	Small to medium corpora, strong filtering needs

Pitfalls in production

No recall measurement. Teams tune for latency and silently lose relevance. Keep a labelled or exact-search baseline and track recall@k per release.
Mixing embedding models. Vectors from different models or versions are not comparable. Version the model in metadata and re-embed in a new index, then switch with an alias.
Selective filters returning empty results. Post-filtering top 100 for a tenant with 0.1% of data returns nothing. Use filter-aware search or per-tenant partitions.
Deletes and updates degrading HNSW. Tombstones accumulate and the graph gets worse. Schedule rebuilds or compaction.
Unnormalized vectors with cosine. Mixing normalized and raw vectors gives inconsistent rankings. Normalize at write time.

Leadership lens

Ask whether a dedicated vector database is needed at all; under a few million vectors, an extension in your existing database is often enough.
Demand an evaluation harness before tuning: recall@k against exact search and an end-to-end quality metric.
Plan re-embedding as a routine migration, with cost and time estimated per model change.
Size by memory per vector (raw, compressed, graph links) times replicas; that drives the bill.

Check yourself

Why does raising nprobe in IVF improve recall and cost latency?
Show answer
More clusters are scanned, so true neighbours just across a cluster boundary are found, but the query compares against more vectors.
Why can post-filtering ANN results return too few hits?
Show answer
The ANN step returns the top candidates regardless of the filter, and a selective filter may remove almost all of them.
What does product quantization trade for its 30x memory saving?
Show answer
Distance precision, because vectors are approximated by sub-centroid codes; re-ranking with full vectors recovers most of it.
Why is changing the embedding model a migration, not a config change?
Show answer
Vectors from different models live in different spaces, so every stored vector must be re-embedded and the index rebuilt.

Sources and further study

Primary

Jégou, Douze and Schmid, Product Quantization for Nearest Neighbor Search (TPAMI 2011): sub-vector codebooks, asymmetric distance and IVFADC.
Subramanya et al., DiskANN (NeurIPS 2019): a graph index laid out for SSDs that searches a billion points on one machine.
Patel et al., ACORN (2024): filtered vector search that works for arbitrary predicates.
Cormack, Clarke and Büttcher, Reciprocal Rank Fusion (SIGIR 2009): the merge rule most hybrid search uses.

Systems docs

pgvector: index options, defaults, iterative scans for filtered queries and the dimension limits.
Qdrant: indexing: payload indexes, filterable HNSW and the full-scan threshold.
FAISS: guidelines to choose an index: picking Flat, HNSW, IVF and PQ by dataset size and memory budget.

Books

AI Engineering, Chip Huyen, chapter 6 "RAG and Agents" (section "RAG"): retrieval as one stage of an application, including embedding-based and term-based retrievers.
Designing Data-Intensive Applications (2nd ed.), Martin Kleppmann and Chris Riccomini, chapter 4 "Storage and Retrieval" (section "Multidimensional and Full-Text Indexes"): indexes beyond B-trees and LSM trees.

Other curricula

Azure Architecture Center: choose a vector search service: starts from whether vectors change often and need near-real-time search, favours an existing database when it can do the job, and treats filtering and embedding refresh as design questions.

Watch

Vector Database Search: HNSW Algorithm Explained (Redis): layer construction and greedy search in HNSW.
Qdrant: Open Source Vector Search Engine (CMU Database Group): a database-systems view of a production vector engine.

Free resources

HNSW paper (Malkov and Yashunin): the original description of hierarchical navigable small world graphs.
Billion-scale similarity search with GPUs (FAISS): IVF and product quantization at very large scale.
FAISS documentation: the reference library for ANN index types and their trade-offs.
ANN Benchmarks: recall versus throughput curves for many algorithms on public datasets.
Pinecone: HNSW explained: a clear walkthrough with parameter guidance.

Open in the interactive app: practice, quiz, mock interview →