FINDING NEEDLES · CHAPTER 08

Vector databases

Dense retrieval turns search into “find the nearest points”. Measuring every point is exact and too slow. A vector index gives up a little accuracy to skip almost all of them.

~16 min read12 starsTested Python

What you'll learn

  • Why exact nearest-neighbour search costs N times d per query
  • How IVF sorts vectors into lists and only opens a few of them
  • How a layered graph (HNSW) finds a neighbour by walking
  • Why filtering after the search can return too few results
  • What recall@k measures, and what you pay to raise it

Before you start

Find the nearest star without measuring them all

Picture a star catalogue where each entry has been turned into a point. Ask for “stars like this one” and the answer is the points closest to your query point. That is the whole job of the previous chapter’s retriever, once the vectors exist.

The slow way measures the distance to every star. The fast ways first decide which stars are worth measuring. They can pick wrong, so they sometimes miss a true neighbour. That is why they are called approximate nearest neighbour (ANN) search.

A vector index is a guess about where to look. A good guess opens a small part of the catalogue and still finds most of the true neighbours. Every knob on a vector index trades how much you open against how many neighbours you miss.

A vector database wraps that index in the parts a service needs: ids, stored metadata (here, each star’s colour), inserts and deletes, and filters. This chapter is about the index and the filters, because that is where the trade-offs live.

Measure everything, then sort

Twelve stars, each a 2-D toy vector. Real embeddings have hundreds of dimensions; two let you draw the picture. The query sits at (4, 4). Distance is squared straight-line distance, which gives the same order as the real distance without a square root.

stars · ANN · tradeoff · filters

MANIM Vector DBs approximate nearest neighbors under a latency budget.
StarVectorColourDistance² to (4, 4)
S4(4, 3)blue1
S12(5, 5)blue2
S8(6, 4)red4
S2(2, 3)blue5
S3(3, 1)red10
S1(1, 2)blue13
S9(4, 8)red16
S6(8, 3)blue17
S5(7, 1)red18
S11(7, 8)red25
S10(5, 9)blue26
S7(9, 2)red29

The true top 3 are S4, S12, S8, at distances 1, 2 and 4. Finding them took 12 distance computations, one per star. That answer is the ground truth every faster method is graded against.

every one of the N stored vectors, times d numbers in each vector.

Twelve stars in two dimensions is 24 multiply-adds. A collection of 10 million vectors with 768 dimensions is 7,680,000,000 multiply-adds for one query. Hardware can do that, but not for thousands of queries a second on one machine. So you stop measuring everything.

Sort the sky into regions, open only the nearest ones

An inverted file index (IVF) borrows the idea from chapter 1. There, a word pointed at a list of documents. Here, a centroid points at a list of vectors. Build time: pick a few centroids (k-means finds them in practice; here they are placed by hand) and file every star under its nearest centroid.

A B C S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 query
Teal stars are blue in the catalogue, pink stars are red. Yellow squares are the centroids, and the dashed lines show which list each star is filed in. The query sits near the corner where all three regions meet, which is exactly where IVF struggles.
ListCentroidStars filed hereDistance² from query to centroid
A(2, 2)S1, S2, S3, S48
C(5, 8)S9, S10, S11, S1217
B(8, 2)S5, S6, S7, S820

Query time: measure the query against the centroids (8, 17 and 20), sort them, and open the nprobe closest lists. Only the stars in those lists get measured.

nprobeLists openedWorkTop 3 foundRecall@3
1A3 centroids + 4 stars = 7 distancesS4, S2, S31/3
2A, C3 + 8 = 11 distancesS4, S12, S22/3
3A, C, B3 + 12 = 15 distancesS4, S12, S83/3

of the k neighbours exact search would return, how many did the index return too.

S8 is the third-nearest star, but it lives in list B, and B’s centroid is the farthest of the three. A centroid is a summary of its list. A star on the edge of a list is badly summarised by it. That is the miss every ANN index has to live with.

Interactive · Open more lists

How many lists do you have to open before S8 shows up? Pink chips are returned, yellow chips were measured, plain chips were never opened.

At nprobe 3 the index costs 15 distances, more than the 12 of exact search. On twelve stars IVF is a loss. It pays off at scale. Take 10 million vectors in 1,000 lists of about 10,000 each, and open 10 lists. That is 1,000 centroid distances plus 100,000 vector distances: 101,000, or 1.01% of the 10 million an exact search measures. Real systems tune nprobe on held-out queries until recall@k is high enough.

Shrinking the vectors too: product quantization

Speed is half the problem. Memory is the other half. A 768-dimension float32 vector takes 3,072 bytes. Product quantization cuts the vector into 96 short pieces, learns a small codebook for each piece, and stores one byte per piece: the id of the nearest codebook entry. That is 96 bytes, 32 times smaller. Ten million vectors drop from 30.72 GB to 0.96 GB. Distances are then computed against the codebooks, so they are approximate too. IVF with product quantization on top is a common pairing for collections that do not fit in memory.

Walk a graph toward the query

The other main family skips lists and builds a graph. Every star is linked to a few nearby stars. To search, start somewhere and keep hopping to whichever neighbour is closer to the query. Stop when no neighbour is closer. That is a greedy walk.

A walk on one flat graph takes many short hops to cross the sky. HNSW (hierarchical navigable small world) adds sparser layers on top, with long links between a few stars. The walk starts on the top layer, crosses the sky in a few long hops, then drops down a layer and continues with shorter links.

S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 entry S11 S12 query
Teal lines are layer 0 (every star). Dashed yellow lines are layer 1, which holds only S1, S7 and S10. The green path is the walk.
  1. Layer 1. Start at the entry star S10, distance 26. Its neighbours are S1 (13) and S7 (29). Hop to S1.
  2. Still layer 1. From S1, neither S7 nor S10 is closer than 13. Drop to layer 0 at S1.
  3. Layer 0. S1’s neighbours are S2 (5) and S3 (10). Hop to S2. S2’s neighbours include S4 (1). Hop to S4.
  4. S4’s neighbours are S2, S3, S12 (2) and S8 (4). None beats 1. Stop. The answer is S4, the true nearest star.

The path is S10 → S1 → S2 → S4. Along the way the walk measured 8 of the 12 stars. On twelve points that is a small saving. On millions, the layers let a walk cross the collection in a handful of long hops, so the number of hops grows roughly with the log of N rather than with N.

A real HNSW search does not keep only the single best star. It keeps a short candidate list (its size is the ef setting) and explores from all of them, which is how it returns a top k and recovers from dead ends. Each star’s link count (M) is set at build time. More links and a longer candidate list both raise recall and both cost time or memory.

“Nearest red stars” is a different question

Real queries come with conditions: this tenant, this date range, in stock. Here the condition is colour = red, and you want 3 results. Where you apply the filter changes the answer.

StrategyWhat it doesRed stars returned
Post-filterTake the top 3, then drop the blue onesS8 (1 of 3)
Oversample ×2Take the top 6, then filterS8, S3 (2 of 3)
Oversample ×3Take the top 9, then filterS8, S3, S9
Pre-filterKeep only red stars, then search themS8, S3, S9

The true top 3 has two blue stars, so post-filtering leaves one result where you asked for three. Oversampling helps, but how much is enough depends on how rare the condition is: ×2 still came up short because S1 (blue) sits closer than S9 (red). Pre-filtering always returns the right answer, but it searches a subset the index was not built for. A strict filter can leave an IVF list nearly empty or cut a graph into islands the walk cannot cross. Vector databases differ most in how they handle this middle ground, for example by checking the filter during the graph walk.

The index you can re-run

vector_index.pyrecall@3 = 1/3, 2/3, 3/3
"""Exact search, an IVF index, a two-layer graph walk, and filters.

Twelve stars from a toy catalogue, each one a 2-D vector.
Real systems use hundreds of dimensions and millions of points.
Distance is squared Euclidean: the same order as Euclidean, no square root.
"""

# Star id -> (x, y, colour). The colour is metadata, not part of the vector.
STARS = {
    "S1": (1, 2, "blue"), "S2": (2, 3, "blue"), "S3": (3, 1, "red"),
    "S4": (4, 3, "blue"), "S5": (7, 1, "red"), "S6": (8, 3, "blue"),
    "S7": (9, 2, "red"), "S8": (6, 4, "red"), "S9": (4, 8, "red"),
    "S10": (5, 9, "blue"), "S11": (7, 8, "red"), "S12": (5, 5, "blue"),
}

QUERY = (4, 4)

# IVF: three centroids, placed by hand where k-means would roughly put them.
CENTROIDS = {"A": (2, 2), "B": (8, 2), "C": (5, 8)}

# The graph, drawn by hand. Layer 1 is a sparse express layer.
LAYER1 = {"S1": ["S7", "S10"], "S7": ["S1", "S10"], "S10": ["S1", "S7"]}
LAYER0_EDGES = [
    ("S1", "S2"), ("S1", "S3"), ("S2", "S4"), ("S3", "S4"),
    ("S4", "S12"), ("S4", "S8"), ("S8", "S12"), ("S8", "S6"),
    ("S6", "S7"), ("S5", "S6"), ("S5", "S8"), ("S12", "S9"),
    ("S9", "S10"), ("S10", "S11"), ("S11", "S12"),
]
ENTRY = "S10"


def dist(a, b):
    """Squared straight-line distance between two 2-D points."""
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2


def point(star):
    x, y, _ = STARS[star]
    return (x, y)


def exact_knn(query, k, stars=None):
    """Score every star. Correct by definition, and the cost grows with N."""
    stars = list(STARS) if stars is None else stars
    ranked = sorted(stars, key=lambda s: (dist(query, point(s)), int(s[1:])))
    return ranked[:k], len(stars)


def build_lists():
    """Each star joins the list of its nearest centroid."""
    lists = {name: [] for name in CENTROIDS}
    for star in STARS:
        home = min(CENTROIDS, key=lambda c: dist(point(star), CENTROIDS[c]))
        lists[home].append(star)
    return lists


def ivf_search(query, k, nprobe):
    """Rank the centroids, open the nprobe closest lists, scan only those."""
    lists = build_lists()
    order = sorted(CENTROIDS, key=lambda c: dist(query, CENTROIDS[c]))
    probed = order[:nprobe]
    candidates = [s for c in probed for s in lists[c]]
    found, scanned = exact_knn(query, k, candidates)
    return found, probed, len(CENTROIDS) + scanned


def recall(found, truth):
    """Share of the true top-k that the approximate search returned."""
    return len(set(found) & set(truth)) / len(truth)


def layer0():
    graph = {star: [] for star in STARS}
    for a, b in LAYER0_EDGES:
        graph[a].append(b)
        graph[b].append(a)
    return graph


def greedy(graph, start, query, seen):
    """Hop to the closest neighbour while it beats the current star."""
    here, path = start, [start]
    seen.add(start)
    while True:
        seen.update(graph[here])
        best = min(graph[here], key=lambda s: dist(query, point(s)))
        if dist(query, point(best)) >= dist(query, point(here)):
            return here, path
        here = best
        path.append(here)


def graph_search(query):
    """Walk the express layer, drop down, walk again. Count every distance."""
    seen = set()
    here, top_path = greedy(LAYER1, ENTRY, query, seen)
    here, low_path = greedy(layer0(), here, query, seen)
    return here, top_path + low_path[1:], len(seen)


def filtered(query, k, colour, strategy, oversample=2):
    """pre: filter, then search. post: search k, then filter. over: search k*oversample, then filter."""
    if strategy == "pre":
        keep = [s for s in STARS if STARS[s][2] == colour]
        return exact_knn(query, k, keep)[0]
    pool = k if strategy == "post" else k * oversample
    hits = exact_knn(query, pool)[0]
    return [s for s in hits if STARS[s][2] == colour][:k]


def scale(n=10_000_000, dim=768, nlist=1000, nprobe=10):
    """Exact multiply-adds per query, and vectors IVF touches with even lists."""
    exact_ops = n * dim
    ivf_vectors = nlist + nprobe * (n // nlist)
    return exact_ops, ivf_vectors


def pq_bytes(dim=768, sub_vectors=96):
    """float32 storage versus one byte per sub-vector code."""
    return dim * 4, sub_vectors

Mistakes learners make

Reporting speed without recall. An index that opens one list is fast and wrong. Always measure recall@k against exact search on a sample of real queries, then tune nprobe or ef.

Filtering after the search and trusting the count. Post-filtering returned 1 star when you asked for 3. Check how many results came back, and oversample or pre-filter when the condition is rare.

Using an ANN index on a tiny collection. On 12 stars, IVF at full recall did 15 distances against exact search’s 12. Below a few tens of thousands of vectors, exact search is often fast enough and never misses.

Mixing the distance the model was trained for. If the encoder was trained with cosine or dot product, index with that. Squared distance gives the same order as cosine only when every vector has length 1.

What to remember

  • Exact search costs N × d per query. Here the true top 3 is S4, S12, S8; at 10 million × 768 it is 7,680,000,000 multiply-adds.
  • IVF files vectors under centroids and opens nprobe lists. Recall@3 went 1/3, 2/3, 3/3 as nprobe went 1, 2, 3.
  • HNSW walks a layered graph greedily. The walk S10 → S1 → S2 → S4 found the nearest star after 8 of the 12 distances.
  • Post-filtering can come back short. Pre-filtering gives S8, S3, S9 but strains the index.
  • Every ANN knob buys recall with time or memory. Measure both.

Check yourself

1. Why does IVF at nprobe 1 miss S12 and S8?

Only list A is opened, because centroid A is closest to the query. S12 is filed under C and S8 under B, so they are never measured.

2. Why is IVF slower than exact search on this catalogue at nprobe 3?

It measures the 3 centroids and then all 12 stars anyway. The centroid step only saves work when most lists stay closed.

3. What does the top layer of HNSW buy you?

Long hops. The walk crosses the sky in a few steps before it switches to short links, instead of crawling there one neighbour at a time.

4. You ask for 3 red stars and get 1. Which strategy did you use, and what are two fixes?

Post-filtering. Oversample enough candidates before filtering, or pre-filter so the search only sees red stars.

Go to the source

Keep going