Vector Databases and Indexing

Every retrieval-augmented system eventually has to answer one question millions of times a day: "which of my stored vectors are closest to this one?" Answering it exactly is easy for ten thousand vectors and ruinously slow for a billion. Vector indexes are the data structures that make the question cheap, and vector databases wrap them with storage, filtering, updates and replication. This lesson takes you from the geometry of embeddings to the internals of HNSW and product quantization, and ends with how to size and choose a system.

The picture: a library with no catalogue

Imagine a library where every book has been placed in a vast room according to its meaning: cookbooks cluster in one corner, tax law in another, and books about Italian tax law on cooking equipment sit somewhere in between. A question is also placed in the room, and your job is to find the nearest books. The exact method is to walk to every book and measure the distance. An index is a shortcut: you might divide the room into neighbourhoods and only search the few nearest your question (IVF), or you might follow signposts from book to book, always stepping toward the question, starting with long-distance express routes and switching to local streets as you get close (HNSW). Both shortcuts occasionally miss a book that was in fact the closest. That miss rate, traded against speed and memory, is the central engineering trade-off of this lesson.

Embeddings: models and dimensions

An embedding model maps a piece of content (a sentence, a passage, an image) to a fixed-length vector $\mathbf{x} \in \mathbb{R}^d$, where $d$ is the dimension. Retrieval embedding models are usually transformer encoders trained with a contrastive objective so that a query and a passage that answers it end up close, and unrelated pairs end up far apart (see the prerequisite lesson on embeddings and RAG).

Practical facts that matter for indexing:

• Dimensions for text embedding models commonly range from a few hundred to a few thousand. The widely used open model all-MiniLM-L6-v2 produces 384-dimensional vectors; many larger models use 768, 1024 or more. Memory and search cost grow linearly with $d$.
• Precision. Vectors are produced as 32-bit floats (4 bytes per dimension). Many systems store them as 16-bit floats, 8-bit integers, or even 1 bit per dimension (binary quantization), usually with a recall cost that should be measured, not assumed.
• Truncatable embeddings. Models trained with Matryoshka Representation Learning (Kusupati et al., 2022) put the most important information in the leading dimensions, so you can keep, say, the first 256 of 1,024 dimensions and re-normalize, trading a little quality for a 4x smaller index.
• Query and document must use the same model (and often a model-specific prefix or instruction for queries versus passages). Changing the model means re-embedding the entire corpus: vectors from different models live in unrelated spaces.

Similarity metrics and when they are equivalent

Three scores dominate. For vectors $\mathbf{q}$ (query) and $\mathbf{x}$ (stored item):

Higher dot and cosine mean more similar; lower L2 distance means more similar. Expanding the squared distance gives the key identity:

If every vector is unit-normalized ($\lVert\mathbf{x}\rVert = 1$), this becomes $\lVert\mathbf{q}-\mathbf{x}\rVert^2 = 2 - 2\,\mathbf{q}\cdot\mathbf{x}$, and the dot product equals the cosine. So for normalized vectors, all three metrics produce the same ranking. That is why the standard practice is: normalize once at ingestion and at query time, then use inner product (often the fastest kernel).

Check with numbers: $\mathbf{a} = (0.6, 0.8)$ and $\mathbf{b} = (0.8, 0.6)$ are both unit length. Their dot product is $0.48 + 0.48 = 0.96$. Squared L2 distance is $(-0.2)^2 + (0.2)^2 = 0.08$, and indeed $2 - 2(0.96) = 0.08$.

When vectors are not normalized, the metrics disagree. Take $\mathbf{q} = (3,4)$, $\mathbf{x}_1 = (6,8)$, $\mathbf{x}_2 = (4,3)$:

$\mathbf{x}_1$ points in exactly the same direction as $\mathbf{q}$ but is twice as long; L2 penalizes that length difference, cosine ignores it, and the dot product rewards it. Use the metric the embedding model was trained with (its model card says so). Some models deliberately encode information in the norm, in which case unnormalized inner product is correct.

Exact versus approximate nearest neighbour

Exact k-nearest-neighbour (kNN) search computes the score against all $N$ vectors and keeps the top $k$. Cost per query is $O(Nd)$ multiply-adds. With $N = 10^6$ and $d = 768$ that is about $7.7 \times 10^8$ multiply-adds per query, which a modern CPU does in tens of milliseconds and a GPU much faster. Exact search is perfectly reasonable up to roughly a few million vectors, or for any corpus where queries are batched, and it is the ground truth you measure everything else against.

Approximate nearest neighbour (ANN) search uses an index to examine only a small fraction of vectors. Quality is measured by recall@k: the fraction of the true top-$k$ (from exact search) that the ANN search returns,

Note this is index recall (did the index find the true nearest vectors), not end-to-end retrieval recall (did we find the documents a human judges relevant). Both matter; they are covered in the advanced retrieval lesson.

Index types

Flat (brute force)

Store vectors in a contiguous array and scan them all. No training, no build time, 100% recall, trivially supports deletes. Memory is exactly $N \times d \times$ bytes per value.

IVF: inverted file with coarse clustering

Run k-means on (a sample of) the data to get $n_\text{list}$ centroids. Each vector is assigned to its nearest centroid and stored in that centroid's inverted list. At query time, compare the query to all centroids, pick the $n_\text{probe}$ closest, and scan only those lists.

• Work per query is about $n_\text{list} + n_\text{probe} \cdot N / n_\text{list}$ vector comparisons. With $N = 10^6$, $n_\text{list} = 1024$ and $n_\text{probe} = 16$, that is roughly $1{,}024 + 16 \times 977 \approx 16{,}700$ comparisons instead of $10^6$, about 60 times less work.
• A common starting point is $n_\text{list}$ on the order of $\sqrt{N}$ (more for large corpora), then tune $n_\text{probe}$ for the recall you need.
• Failure mode: a true neighbour sitting just across a cluster boundary is missed unless its cluster is probed. Raising $n_\text{probe}$ fixes this at the cost of speed.
• IVF needs a training step, and if the data distribution drifts far from the training sample, the clusters become unbalanced and recall or latency degrade. Periodic retraining is part of operating it.

HNSW: hierarchical navigable small-world graphs

HNSW (Malkov and Yashunin, arXiv 2016) is the most widely deployed in-memory ANN index. It is a proximity graph: each vector is a node linked to some of its near neighbours. Search is greedy graph traversal: start at an entry node, look at its neighbours, move to whichever is closest to the query, and repeat until no neighbour is closer.

A single flat graph has two problems: greedy search can get stuck in a local minimum, and reaching a far-away region takes many hops. HNSW fixes both with a hierarchy, much like a skip list:

1. Layers. Each inserted node draws a maximum layer $\ell$ from an exponentially decaying distribution, so every node is in layer 0, a fraction is also in layer 1, a smaller fraction in layer 2, and so on. Upper layers are sparse "express routes"; layer 0 contains everything.
2. Search. Start at the single entry point in the top layer. Greedily descend: in each upper layer, walk to the closest node you can reach, then drop to the next layer starting from there. In layer 0, run a beam search that keeps a dynamic candidate list of size $ef_\text{search}$: repeatedly expand the closest unexpanded candidate, add its unseen neighbours, and keep the best $ef_\text{search}$ found so far. Stop when the closest unexpanded candidate is worse than the worst kept result. Return the top $k$ (so $ef_\text{search} \ge k$).
3. Insertion. A new node runs the same search to find its neighbourhood (using a candidate list of size $ef_\text{construction}$) on each layer it belongs to, then links to up to $M$ neighbours, chosen with a heuristic that prefers diverse directions rather than $M$ near-duplicates. Neighbours whose link lists overflow are pruned.

The three parameters you will tune:

HNSW gives excellent recall-latency curves and supports incremental inserts without retraining. Its costs are memory (the vectors stay uncompressed in RAM, plus the links), slow builds for large corpora, and awkward deletes (most implementations mark deleted nodes as tombstones and rebuild or repair periodically).

Product quantization (PQ)

PQ (Jégou, Douze and Schmid, 2011) compresses vectors so that far more fit in memory. Split each $d$-dimensional vector into $m$ sub-vectors of $d/m$ dimensions. For each sub-space, run k-means to learn a codebook of $2^{b}$ centroids (usually $b = 8$, so 256 centroids). Each sub-vector is replaced by the index of its nearest centroid, so a vector becomes $m$ codes of $b$ bits: with $d = 768$, $m = 96$, $b = 8$, a vector shrinks from $3{,}072$ bytes to $96$ bytes, a 32x reduction.

Distances are computed asymmetrically: the query stays at full precision. For each sub-space, precompute a lookup table of the distance from the query's sub-vector to all 256 centroids; the approximate distance to any stored vector is then the sum of $m$ table lookups. PQ is lossy, so it is usually combined with IVF (FAISS's IndexIVFPQ) and followed by re-ranking: fetch a few hundred candidates by PQ distance, then rescore them with the exact vectors (kept on disk or in cheaper memory).

Other families worth knowing

• Scalar quantization (float32 to int8 per dimension): 4x compression, often small recall loss, simple.
• Binary quantization: 1 bit per dimension, 32x compression, Hamming distance is extremely fast; typically used as a first stage with full-precision rescoring.
• Disk-based graph indexes (for example the DiskANN family) keep compressed vectors in RAM and the graph plus full vectors on SSD, serving billion-scale corpora from a single machine.

The recall versus latency trade-off

Every ANN index exposes a knob ($n_\text{probe}$, $ef_\text{search}$, number of rescored candidates) that moves you along a curve: more work per query buys higher recall. The professional workflow is:

1. Build a held-out set of real queries and compute exact top-$k$ with a flat index.
2. Sweep the knob and plot recall@$k$ against p50 and p99 latency (and throughput, queries per second, under realistic concurrency).
3. Pick the cheapest setting that meets your recall target, often 0.95 to 0.99 for RAG, and re-check whenever data volume or distribution changes.

The code below makes this concrete with a toy IVF index written in numpy on clustered synthetic data.

import numpy as np

rng = np.random.default_rng(0)
N, d, k = 20_000, 64, 10
# Clustered synthetic data (real embeddings are clustered, not uniform noise)
centers = rng.standard_normal((200, d))
X = centers[rng.integers(0, 200, N)] + 1.5 * rng.standard_normal((N, d))
X = (X / np.linalg.norm(X, axis=1, keepdims=True)).astype(np.float32)
Q = centers[rng.integers(0, 200, 100)] + 1.5 * rng.standard_normal((100, d))
Q = (Q / np.linalg.norm(Q, axis=1, keepdims=True)).astype(np.float32)

def exact_search(Q, X, k):
    S = Q @ X.T                                    # (nq, N) cosine similarities
    idx = np.argpartition(-S, k, axis=1)[:, :k]    # unordered top-k per row
    order = np.argsort(-np.take_along_axis(S, idx, 1), axis=1)
    return np.take_along_axis(idx, order, 1)

truth = exact_search(Q, X, k)                      # ground truth for recall

Because all vectors are unit length, the matrix product Q @ X.T gives cosine similarities directly. argpartition finds the top $k$ in linear time, and only those $k$ are sorted. Now the IVF index:

def kmeans(X, nlist, iters=10):
    C = X[rng.choice(len(X), nlist, replace=False)].copy()
    for _ in range(iters):
        assign = np.argmax(X @ C.T, axis=1)        # nearest centroid by dot
        for c in range(nlist):
            m = X[assign == c]
            if len(m):
                C[c] = m.mean(0) / np.linalg.norm(m.mean(0))
    return C, np.argmax(X @ C.T, axis=1)

nlist = 128
C, assign = kmeans(X, nlist)
lists = [np.where(assign == c)[0] for c in range(nlist)]

def ivf_search(q, k, nprobe):
    probe = np.argsort(-(C @ q))[:nprobe]          # nprobe closest centroids
    cand = np.concatenate([lists[c] for c in probe])
    return cand[np.argsort(-(X[cand] @ q))[:k]], len(cand)

for nprobe in (1, 4, 16, 64):
    hits = scanned = 0
    for i, q in enumerate(Q):
        found, n = ivf_search(q, k, nprobe)
        hits += len(set(found) & set(truth[i])); scanned += n
    print(f"nprobe={nprobe:3d}  recall@10={hits / (k * len(Q)):.3f}  "
          f"scanned={scanned / (len(Q) * N):.1%}")

On one run this printed recall@10 of about 0.59 when scanning under 1% of the vectors, 0.86 at about 12.5%, and 0.985 at 50%: exactly the shape of the trade-off curve. Real embeddings are usually more clustered than this deliberately noisy data, so production indexes reach high recall while scanning far less. The same experiment with FAISS, which you would use in practice:

import faiss  # pip install faiss-cpu

d = X.shape[1]
flat = faiss.IndexFlatIP(d); flat.add(X)                  # exact, inner product
hnsw = faiss.IndexHNSWFlat(d, 32, faiss.METRIC_INNER_PRODUCT)  # M = 32
hnsw.hnsw.efConstruction = 200
hnsw.add(X)
hnsw.hnsw.efSearch = 64                                   # query-time knob
_, I_exact = flat.search(Q, 10)
_, I_hnsw = hnsw.search(Q, 10)
recall = np.mean([len(set(a) & set(b)) / 10 for a, b in zip(I_exact, I_hnsw)])
print(f"HNSW recall@10 = {recall:.3f}")

FAISS expects contiguous float32 arrays; call faiss.normalize_L2(X) in place if your vectors are not already normalized and you want cosine similarity.

Worked example: sizing memory

You must index $N = 10$ million chunks with a 768-dimensional model.

Raw float32 vectors: $N \times d \times 4 = 10^7 \times 768 \times 4 = 3.072 \times 10^{10}$ bytes $= 30.72$ GB (about 28.6 GiB).

HNSW overhead with $M = 32$: layer 0 holds up to $2M = 64$ neighbour IDs per node at 4 bytes each, so $256$ bytes per vector, or $2.56$ GB. Upper layers add only a few percent more because few nodes reach them. Total roughly $30.72 + 2.56 \approx 33.3$ GB, before IDs, metadata and the database's own overhead. Plan for a machine with comfortably more than that, since build time needs headroom too. (Exact overhead is implementation-dependent; measure it.)

Cheaper alternatives:

The PQ codebooks are tiny: $96$ sub-spaces $\times$ $256$ centroids $\times$ $8$ dims $\times$ 4 bytes $= 786{,}432$ bytes, under 1 MB. That table is the core of capacity planning: pick the cheapest row whose measured recall (after rescoring) meets your target.

Metadata filtering

Real queries come with constraints: "only documents this user may see", "only 2025 contracts", "language = de". Three strategies:

• Post-filtering: run ANN for top $k$, then drop items failing the filter. Simple, but if the filter is selective (say 1% of the corpus passes), most of your $k$ results are discarded and you may return nothing. Over-fetching ($k' \gg k$) helps only partially.
• Pre-filtering: compute the set of allowed IDs first, then search only among them. Exact for selective filters (brute force over the allowed subset is cheap), but naive graph search over a sparse allowed subset breaks connectivity.
• Filter-aware search: the index checks the filter during traversal, skipping disallowed nodes while still using them for navigation, or maintains per-value partitions. Most mature vector databases implement some form of this; behaviour with highly selective filters is exactly what to benchmark.

For access control, never rely on post-filtering by the LLM: enforce permissions in the retrieval query itself, so unauthorized text never enters the prompt.

Hybrid indexes

Dense vectors capture meaning but are weak on exact tokens: part numbers, error codes, rare names. Sparse lexical indexes (BM25 over an inverted index, or learned sparse vectors) excel there. Hybrid search runs both and fuses the results; many systems now store dense and sparse representations side by side and fuse in one query. The fusion methods are covered in the advanced retrieval lesson.

Choosing a vector store

The options fall into three groups (feature sets change quickly, so verify against current documentation before committing):

• Libraries such as FAISS (Meta) and hnswlib: in-process index implementations with no server, persistence layer or access control. Ideal for research, batch jobs and as the engine inside other systems.
• Extensions to databases you already run, such as pgvector for PostgreSQL, which adds a vector column type, distance operators, and HNSW and IVFFlat index types. Elasticsearch, OpenSearch and several other databases offer comparable vector search. Big advantage: vectors live next to your relational data, with transactions, joins, backups and row-level security you already understand.
• Dedicated vector databases (for example Milvus, Qdrant, Weaviate, Pinecone and Chroma): purpose-built for vector workloads, with features such as filtered ANN, multi-tenancy, quantization options, hybrid search and horizontal scaling.

A practical rule: if your corpus is in the low millions of vectors and you already operate PostgreSQL, start with pgvector; move to a dedicated system when measured scale, filtering performance or operational needs demand it.

Common pitfalls

• Mixing metrics. Building an index with L2 on unnormalized vectors from a model trained for cosine silently degrades ranking.
• Forgetting to normalize the query after normalizing the corpus.
• Mixing embedding models or versions in one index. Re-embed everything when the model changes, and record the model ID with each vector.
• Tuning on random queries instead of real ones. Recall on synthetic queries says little about production.
• Measuring average latency only. Users feel p99, and p99 grows under concurrency and with filters.
• Selective filters with post-filtering, returning empty or poor results.
• Unbounded HNSW deletes. Tombstones accumulate, recall and memory degrade; schedule compaction or rebuilds.
• Undersized RAM. An HNSW index that spills to swap is orders of magnitude slower.

In practice

• Start with exact search as the baseline and ground truth; only add ANN when latency or cost demands it.
• Normalize vectors and use inner product unless the model says otherwise.
• For HNSW, a sensible start is $M = 16$ to $32$, $ef_\text{construction} = 200$, then sweep $ef_\text{search}$ against your recall target.
• Store the full-precision vectors somewhere so you can rescore after quantization and re-index without re-embedding.
• Version your index: embedding model, chunking settings and index parameters together, so you can roll back.
• Benchmark with your real filters, real query mix and realistic concurrency before choosing a product.