Modern AI applications represent text, images, and audio as embedding vectors — dense arrays of floating-point numbers (typically 256 to 1536 dimensions). Finding the most similar items means finding the nearest neighbors in this high-dimensional space. The naive approach — computing the distance from the query vector to every stored vector — is O(n * d) where n is the number of vectors and d is the dimensionality. For a database of 10 million 1536-dimensional vectors, that is 15 billion floating-point operations per query. This is far too slow for real-time applications.

ANN: Trading Accuracy for Speed

Approximate Nearest Neighbor (ANN) indexes solve this by accepting a small accuracy loss in exchange for orders-of-magnitude speedup. Instead of guaranteeing the exact top-k nearest vectors, they return a set that is correct with high probability (measured by recall@k — the fraction of true top-k results that appear in the ANN result).

Distance Metrics

The choice of distance metric depends on the embedding model:

Metric	Formula	Use case
L2 (Euclidean)	sqrt(sum((a_i - b_i)^2))	General purpose, raw magnitude matters
Cosine similarity	dot(a,b) / (norm(a) * norm(b))	Text embeddings (direction matters, not magnitude)
Inner product	dot(a,b)	When vectors are already normalized (equivalent to cosine)

HNSW (Hierarchical Navigable Small World)

HNSW builds a multi-layer graph where each layer is a "small world" network — most nodes have short-range connections, but a few have long-range connections that enable fast traversal. Search starts at the top (sparsest) layer, greedily navigates to the region nearest the query, then descends to denser layers for refinement.

• Pros: best recall@k among ANN methods, no training phase, supports incremental inserts.
• Cons: high memory usage (stores the graph in RAM), slow to build for very large datasets.
• Typical performance: 95–99% recall@10 with sub-millisecond latency on millions of vectors.

IVF (Inverted File Index) + PQ (Product Quantization)

IVF partitions the vector space into clusters using k-means. At query time, only the nprobe nearest clusters are searched instead of the entire dataset.

Product Quantization compresses each vector by splitting it into subvectors and encoding each with a small codebook. A 1536-dim float32 vector (6 KB) can be compressed to ~48 bytes — a 128x reduction.

• Pros: low memory (compressed vectors), tunable recall via nprobe.
• Cons: requires a training phase on representative data, lower recall than HNSW at equal latency.

Scalar Quantization

A simpler compression: convert each float32 component to int8 (or float16), reducing memory 4x (or 2x) with minimal recall loss. Often combined with HNSW.

pgvector for PostgreSQL

The pgvector extension adds vector storage and ANN search directly to PostgreSQL. It supports two index types:

• ivfflat: IVF-based, requires training via CREATE INDEX ... USING ivfflat
• hnsw: graph-based, no training needed, higher recall

This lets you combine vector search with standard SQL filters in a single query — for example, find the 10 most similar products that are also in stock and under $50.

Recall@k

The standard quality metric for ANN indexes: run the same query with exact kNN and with the ANN index, then compute the overlap. Recall@10 = 0.95 means 9.5 out of 10 results are the true nearest neighbors.