Vector Databases: Embeddings, ANN Indexes, and the Retrieval Layer for AI

TL;DR: Vector databases answer “which stored items are most similar to this query?” by indexing high-dimensional embeddings under approximate nearest-neighbor (ANN) algorithms. HNSW dominates for in-memory workloads (logarithmic search, 95%+ recall), IVF-PQ trades recall for 64x compression¹, and DiskANN serves a billion vectors from a single node at under 3 ms mean latency². For most teams: use pgvector under 10M vectors, Pinecone for zero-ops, and Milvus or Qdrant at scale. Hybrid retrieval (BM25 + vector + reranking) is non-negotiable for production RAG.

Learning Objectives

After this module, you will be able to:

• Explain what an embedding is and why cosine similarity is the default metric
• Describe HNSW and IVF indexes and their recall/latency trade-offs
• Design a retrieval pipeline combining BM25 and vector search
• Choose between Pinecone, pgvector, Weaviate, Milvus, and Qdrant
• Estimate memory, disk, and query cost for a vector workload

Intuition

You walk into a library and ask the librarian for “books about staying healthy during the holidays.” There is no shelf labeled with that exact phrase. A keyword catalog would find “healthy” and “holidays” separately but miss books titled “Wellness Tips for the Festive Season” because no words overlap.

Now imagine the librarian has a magical map where every book is a dot, and books about similar topics cluster together. Your question also becomes a dot on the same map. The librarian walks to your dot and grabs the five nearest books. One is “Festive Season Wellness,” another is “Holiday Nutrition Guide.” Neither shares your exact words, but they are close in meaning.

That map is an embedding space. Each dot is a vector of 768 or 1,536 floating-point numbers produced by a neural network. “Close” means small cosine distance. The librarian’s walk is a nearest-neighbor search. And the reason the library needs a special index (not just a linear scan of every dot) is that with 50 million books, checking every single one takes too long.

This is the core problem vector databases solve: find the k nearest vectors to a query vector, fast, at scale, without scanning everything. The rest of this chapter explains how.

Theory

Embeddings and distance metrics

A transformer encoder converts text (or images, audio, code) into a fixed-length vector of d floating-point numbers. Semantically similar inputs land near each other in this d-dimensional space. OpenAI’s text-embedding-3-large produces 3,072 dimensions and scores 64.6% on the MTEB benchmark; text-embedding-3-small uses 1,536 dimensions at 62.3%³. Alternatives like Cohere embed-v3 (1,024d, commercial API) and the open-source BGE-M3 (1,024d) offer competitive quality without per-token API costs.

Three distance metrics dominate:

• Cosine similarity measures the angle between vectors, ignoring magnitude. It is the default for normalized embeddings.
• Inner product (dot product) is equivalent to cosine when vectors are unit-normalized, and is the fastest operator in pgvector for that case⁴.
• Euclidean (L2) measures straight-line distance. Airbnb chose L2 specifically because it produces more uniform IVF cluster sizes than dot product⁵.

Why approximate, not exact

Exact nearest-neighbor search costs O(N * d) per query. At d=1,536 and N=10M, that is roughly 60 billion floating-point operations per query. Even with SIMD, a single core takes hundreds of milliseconds. This is the “curse of dimensionality”: in high dimensions, distance ratios concentrate, and no partitioning scheme can prune efficiently without accepting some error.

ANN indexes accept a small recall loss (typically 95-99% of the true top-k) in exchange for 100x or greater speedup. The key insight: you do not need the exact nearest neighbor. You need results good enough that a downstream reranker or LLM cannot tell the difference.

flowchart LR
    subgraph Exact["Exact kNN"]
        E1[Scan all N vectors]
        E1 --> E2[Sort by distance]
        E2 --> E3[Return top-k]
    end
    subgraph ANN["Approximate NN"]
        A1[Navigate index structure]
        A1 --> A2[Visit ~log N candidates]
        A2 --> A3[Return top-k approx]
    end
    Q[Query vector] --> Exact
    Q --> ANN
    Exact -.->|"O(N*d), 100% recall"| R1[Results]
    ANN -.->|"O(log N * d), ~95% recall"| R2[Results]

HNSW: hierarchical navigable small world

HNSW is the dominant ANN algorithm in production today. It builds a multi-layer proximity graph inspired by skip lists. Data Structures for Distributed Systems introduced skip lists as a probabilistic alternative to balanced trees; HNSW applies the same layering idea to graph search.

How it works: Each vector is a node. On insert, the node draws a random layer from an exponential distribution. It is connected to its M nearest neighbors in each layer from 0 up to its drawn layer. The top layers are sparse (long-range jumps); the bottom layer contains all nodes (local refinement)⁶.

Search: Start at the entry point in the top layer. Greedily walk toward the query. Descend one layer. Repeat. At layer 0, expand the search beam to ef_search candidates and return the top-k.

Key parameters (pgvector defaults):

Memory cost: HNSW stores each vector plus its adjacency list. In practice, indexes typically consume 1.5-2x the raw vector storage due to adjacency lists and graph metadata. For 1M vectors at 1,536 dimensions (6 GB raw float32), expect 9-12 GB resident memory.

graph TD
    subgraph L2["Layer 2 - sparse, long jumps"]
        EP((Entry)) --- N1((A))
    end
    subgraph L1["Layer 1 - medium density"]
        A1((A)) --- B1((B))
        B1 --- C1((C))
        A1 --- D1((D))
    end
    subgraph L0["Layer 0 - all nodes, local refinement"]
        A0((A)) --- B0((B))
        B0 --- C0((C))
        C0 --- T((target))
        D0((D)) --- B0
        D0 --- E0((E))
        E0 --- T
    end
    EP -.->|descend| A1
    C1 -.->|descend| C0
    C0 -.->|greedy hop| T

IVF and product quantization

IVF (Inverted File Index) clusters the corpus into nlist Voronoi cells via k-means. At query time, compute the nprobe nearest centroids and scan only vectors in those cells. This is cheaper in memory than HNSW but requires a training step and delivers lower recall at equal speed on standard benchmarks⁷.

Product Quantization (PQ) compresses vectors dramatically. Split each d-dimensional vector into m sub-vectors, run k-means on each sub-space with 256 centers, and store only the m codebook indices (1 byte each). For d=1,536 with m=96 sub-vectors: 96 bytes per vector instead of 6,144 raw bytes. That is a 64x compression¹.

IVF-PQ combines both: cluster into cells, then PQ-compress vectors within each cell. This enables billion-scale search on a single machine. The trade-off is lossy distances: PQ collapses small differences between top candidates, so production systems re-rank a shortlist with exact distances.

ScaNN (Google, ICML 2020) improved PQ by penalizing quantization error parallel to the data vector more heavily than orthogonal error, achieving roughly 2x QPS at equal recall versus the next-best library on the glove-100-angular benchmark⁸.

DiskANN: billion-scale on one node

Microsoft’s DiskANN (NeurIPS 2019) keeps compressed (PQ) vectors in RAM for routing but stores full-precision vectors and graph adjacency lists on SSD. A careful graph layout minimizes random reads. The result on the billion-point SIFT1B dataset: over 5,000 queries per second at under 3 ms mean latency and 95%+ 1-recall@1, served from 64 GB RAM plus an SSD, where in-DRAM algorithms peak at 100-200M points for the same accuracy².

One independent report documents replacing a 3 TB RAM sharded-HNSW cluster with a single 96 GB DiskANN node at 40x lower cost for the same workload⁹. DiskANN is the right answer when your vector count exceeds what fits in RAM but you need single-digit millisecond latency.

Hybrid retrieval and RAG pipelines

Pure vector search misses exact matches, proper nouns, product codes, and rare entities. Pure BM25 misses semantic similarity. Production systems combine both.

Reciprocal Rank Fusion (RRF) merges two ranked lists by scoring each document as sum(1 / (k + rank_i)) across lists (k=60 is standard). It ignores raw scores and uses only ranks, making it robust across heterogeneous retrieval systems. Weaviate’s relativeScoreFusion (normalize scores to [0,1] and take a weighted sum) showed a ~6% recall improvement over rankedFusion on the FIQA benchmark¹⁰.

A complete RAG pipeline has these stages:

flowchart LR
    subgraph Offline["Offline indexing"]
        D[Documents] --> CH[Chunker<br/>200-800 tokens]
        CH --> EM1[Embedding model]
        EM1 --> VDB[(Vector DB<br/>HNSW index)]
        D --> INV[Inverted index<br/>BM25]
    end
    subgraph Online["Online query path"]
        Q[User query] --> EM2[Embedding model]
        EM2 --> VDB
        Q --> INV
        VDB -->|top-50| FUS[Fusion<br/>RRF]
        INV -->|top-50| FUS
        FUS --> RR[Reranker<br/>cross-encoder]
        RR -->|top-5| PA[Prompt assembly]
        PA --> LLM[LLM]
        LLM --> ANS[Answer + citations]
    end

Evaluation: RAGAs defines four metrics scored 0-1: faithfulness (every claim grounded in context), answer relevance, context precision, and context recall¹¹. Measure these before deploying; low context recall means your chunking or retrieval is broken.

Metadata filtering strategies

Real queries combine semantic similarity with hard filters: tenant_id = 7 AND created > 2024-01-01 ORDER BY embedding <-> query LIMIT 10. Three strategies exist:

pgvector’s HNSW with post-filter and ef_search=40 returns only ~4 rows on average when the filter matches 10% of data. Version 0.8.0 introduced iterative_scan to address this⁴. Qdrant’s filterable HNSW builds per-payload subgraphs that preserve graph connectivity under filters¹². Milvus uses pre-filter bitmasks before vector search¹³.

Real-World Example

Airbnb: embedding-based retrieval for search

Airbnb deployed a two-tower neural network for listing retrieval. The listing tower processes home features (amenities, capacity, historical engagement) offline in a daily batch, pre-computing all listing embeddings. The query tower processes search features (location, guests, dates) online per request⁵.

The key architectural decision: Airbnb chose IVF over HNSW. HNSW’s memory grew too large under frequent listing updates (pricing and availability change constantly), and HNSW retrieval combined with mandatory geographic and availability filters produced poor latency. IVF cluster IDs are stored in the existing search index and treated as just another filter alongside price and availability, making integration “quite straightforward”⁵.

They chose Euclidean distance over dot product because dot product produced imbalanced clusters that “greatly reduce the discriminative power” of IVF retrieval. Training used hard negatives from actual user journeys (homes seen but not booked) rather than random negatives.

The result: an A/B test showed bookings lift “on par with some of the largest machine learning improvements to our search ranking in the past two years”⁵.

This is a critical counterexample to the “HNSW is always better” default. When your vectors update frequently and your queries always carry hard filters, IVF integrated into an existing search stack can outperform a standalone HNSW index.

Trade-offs

Common Pitfalls

Exercise

Design the retrieval layer for a RAG chatbot over 50M support documents. Pick an embedding model, choose an ANN index, size memory and storage, define the hybrid retrieval strategy, and specify how you handle document updates and deletions.

Key Takeaways

• Vector search is approximate by design. Tune recall vs latency with ef_search (HNSW) or nprobe (IVF); do not expect exactness.
• HNSW is the default ANN algorithm today: logarithmic search, incremental inserts, tunable recall. But it costs 1.5-2x raw vector size in RAM.
• IVF-PQ compresses vectors 64x and wins when memory is scarce or vectors update frequently (Airbnb’s choice).
• DiskANN serves billion-scale from SSD at under 3 ms mean latency, 40x cheaper than sharded HNSW in RAM.
• Hybrid retrieval (BM25 + vector + reranking) beats either approach alone on real benchmarks. It is non-negotiable for production RAG.
• pgvector is good enough for most teams under 10M vectors. Do not over-engineer with a separate vector database until you outgrow it.
• Embedding API cost, not storage cost, dominates at large scale. Budget $0.02-$0.13 per million tokens and plan for re-embedding on model upgrades.

Further Reading

• Efficient and robust approximate nearest neighbor search using HNSW (Malkov and Yashunin, 2018) - The canonical HNSW paper; the only must-read if you read one thing on ANN graph indexes.
• DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node (NeurIPS 2019) - How to serve 1B vectors from 64 GB RAM plus SSD; the architecture behind Microsoft’s billion-scale search.
• Embedding-Based Retrieval for Airbnb Search - Why Airbnb chose IVF over HNSW; the best production trade-off story in the vector search space.
• ANN-Benchmarks - Standardized recall-vs-QPS plots across algorithms and datasets; check here before trusting any vendor’s benchmark.
• pgvector README - The Postgres extension’s full documentation: HNSW/IVF knobs, iterative scan, hybrid search patterns, and distance operators.
• Weaviate Hybrid Search Fusion Algorithms - Deep dive into rankedFusion vs relativeScoreFusion with worked examples and benchmark results.
• New embedding models and API updates (OpenAI, 2024) - Benchmarks, pricing, and Matryoshka dimension reduction for text-embedding-3.
• Search Systems - The lexical counterpart; Search Systems covers inverted indexes and BM25, which form the other half of hybrid retrieval.

Flashcards

References