Vector Databases and ANN: IVF, HNSW and Product Quantization

Think of a huge library with ten million books and no catalogue. A reader asks for "books like this one". The only sure way to answer is to pull every book off the shelf, read the back cover, and compare. That gives the perfect answer, and it takes all day. A real librarian walks to the right section, checks a few shelves, and hands over ten good books in a minute. They might miss one great book on a shelf they skipped. Nobody minds.

Note 9 showed that exact vector search is the first librarian: always right, and far too slow at millions of vectors. This note is about the second librarian. We look at approximate nearest neighbour search (ANN), how to measure what it misses (recall), and the two ideas most vector databases use: IVF, which splits the space into neighbourhoods, and HNSW, which turns search into walking a graph. Then we shrink the vectors themselves with quantization, add metadata filters, and see how pgvector puts all of it inside Postgres. The code is a small lab in plain Java, Node.js and Python under code/10-ann-index/. No API key is needed.

Core Path

Do not try to learn every acronym at once. Follow one problem through five stages:

1. Exact search: compare the query with every vector. This is the correct answer key, but the work grows as the collection grows.
2. Approximate nearest-neighbour search (ANN): check only a promising few vectors, and score the result with recall@K (how many true neighbours it found).
3. Inverted-file index (IVF): group nearby vectors, then open only the nearest groups. nprobe controls how many groups are searched.
4. Hierarchical navigable small-world graph (HNSW): link nearby vectors and walk through layers of links. ef is how many routes you keep open at once; M is how many links each vector has.
5. Product quantization (PQ): once search is fast enough, save memory by cutting each vector into slices and storing each slice as a short code.

Read sections 1–9 for the exact-versus-approximate trade-off, 10–19 for IVF, 20–32 for HNSW, and 33–40 for quantization and PQ. Sections 41–48 are deeper production detail: filtering, pgvector, selection, tuning, and the runnable three-language lab. The order matters: first learn why vectors can be skipped, then how each index skips them, and only then how to compress.

Reference: terms used in this chapter

Use this table when a term reappears; you do not need to memorize it before starting.

1. Where Note 9 Left Us

Note 9 built the simplest vector database there is. Store an id, a vector and some metadata for every item. Embed the query with the same model. Measure the query against every stored vector and keep the best K.

Every box after the model is a loop and some arithmetic. The loop is the problem.

It also left us some numbers. One vector of 1,536 float32 numbers is 6,144 bytes. One million of them is about 6.14 GB. One query over that million takes about 1.54 billion multiply-adds (the small steps of comparing two vectors). And normal database indexes, like a B-tree or a k-d tree, stop helping once there are hundreds of dimensions (numbers per vector).

So note 9 ended with a question: can we look at only a small share of the vectors and still find answers that are very close to the true best ones? The rest of this note says yes, and shows how.

2. The Basic Search Problem

Say a streaming app has 10,000,000 titles. Each one has an embedding.

Title 1          -> [0.12, 0.87, -0.34, ...]
Title 2          -> [0.78, 0.11,  0.49, ...]
...
Title 10,000,000 -> [...]

A user types "movies about humans exploring deep space". The embedding model turns that into a query vector, maybe [0.19, 0.71, -0.29, ...]. Our job is to find the 10 stored vectors closest to it.

The obvious plan is the one from note 9.

Ten million measurements, one after the other, for one search.

This is exact nearest neighbour search. It has one big strength: it does not guess. With the same vectors and the same distance rule, it always returns the true top 10. There is nothing wrong with its maths. The trouble is the bill.

3. Why Exact Search Gets Expensive

Comparing two vectors of D numbers takes about D multiply-adds. With N vectors, one search costs about N x D.

Now multiply by traffic. A thousand searches a second means fifteen trillion multiply-adds every second.

Two everyday pictures of the same waste:

• A shop till that, to find which items are on offer today, reads every product in the warehouse instead of just the offers shelf.
• A cricket stats site that, to show "batters similar to this one", reads every player who has ever played, in every format, for every request.

Both give the right answer. Both throw away most of their work.

4. Do We Have to Look at Everything?

Say you are standing in Delhi and want the nearest coffee shop. You do not measure the distance to every coffee shop in India. You already know that shops in Mumbai, Bengaluru and Chennai are not going to win. You throw out huge areas before you measure anything.

A few more:

• You lost your phone at home. You search the rooms you were in today, not the loft.
• In a library you walk to the science shelves first. You do not check cookery.

The right side measures one thousandth of the vectors. Its job is to pick the candidates well.

That idea is called approximate nearest neighbour search, or ANN. It changes the question.

Exact search asks how to measure every vector faster. ANN asks how to avoid measuring most of them at all.

5. Exact vs Approximate Results

Here is what "approximate" looks like in practice. Say exact search returns:

1. Interstellar
2. The Martian
3. Gravity

and an ANN search returns:

1. Interstellar
2. The Martian
3. Apollo 13

It missed Gravity and returned Apollo 13 instead.

Two of three match. The third is a different film, and still a good one.

For film suggestions this is fine. Apollo 13 is a very reasonable pick for someone who likes space survival. For other jobs it may not be. If you are looking for duplicate invoices before paying them, a missed match costs real money. The right amount of "approximate" depends on the job.

6. What ANN Actually Approximates

A common mix-up: people think ANN measures distances roughly. Usually it does not. Every distance it works out is exact. The guess happens earlier, when it decides which vectors to measure.

The candidates get exact distances. The skipped vectors get no distance at all.

So when ANN returns the wrong neighbour, the reason is almost always "the right vector was never looked at", not "its distance was worked out wrong". Think of a talent scout who visits three cities. They time every runner in those cities with a perfect stopwatch. They still miss the fastest runner in the country if she lives in a fourth city.

7. Why ANN Can Miss the True Nearest

Here is a small picture of that miss. Q is the query. The index decides Q belongs to one region and only measures the points inside it.

If B is a little closer to Q than A is, the search returns A and never knows B was there.

This is where the word approximate comes from. The index draws lines through the space to save work. Every so often the best answer sits just on the other side of a line.

8. Recall@K: Measuring What We Missed

We need a number that says how good an approximate search is. The usual one is recall@K.

Run exact search to get the true top K. Run the approximate search. Count how many of the true top K it found, and divide by K.

Exact top 10: A B C D E F G H I J
ANN top 10:   A B C D E F G H X Y

Found 8 of the true 10, so recall@10 = 8 / 10 = 0.8

The same count as a picture:

Order inside the top 10 does not matter for this number. Only who made it in.

Two more ways to picture it:

• A music app shows "10 songs like this one". If 9 of them are in the true closest 10, recall is 0.9.
• A food app shows 5 restaurants for "spicy noodles". If only 3 of the true closest 5 appear, recall@5 is 0.6, and the user probably still finds dinner.

In code it is a few lines:

def recall_at_k(truth, found, k):
    expected = set(truth[:k])
    hits = sum(1 for item in found[:k] if item in expected)
    return hits / k   # divide by k, so returning fewer results costs you

Dividing by K, not by how many came back, matters. A search that returns only 3 results when you asked for 10 cannot score better than 0.3.

9. A Dial, Not a Defect

It is tempting to think of ANN as "exact search, but worse". A better picture is a dial. Turn it one way and the index looks at more candidates. Turn it the other way and it looks at fewer.

Every ANN method has some setting that moves you along this line. You pick the point that suits the job.

A food app showing "restaurants near you" can sit far left. Nobody checks whether it missed the eleventh closest. A tool that checks a new patent against old ones should sit far right. Most apps sit in the middle, where recall is something like 0.95 and the search touches a tiny share of the data.

ANN is a trade: speed for recall. Every index gives you a dial for it.

10. Two Big Ideas

Different ANN methods pick candidates in different ways. Two ideas cover most of what you will meet in real vector databases.

IVF is like a city split into postal zones. HNSW is like asking friends of friends until you reach the right person.

11. IVF: Split the Space Into Neighbourhoods

Embeddings clump. Space films sit near each other. Love stories sit near each other. Superhero films form their own group.

Real embeddings have 1,536 or more dimensions, so we cannot draw them. The idea of groups still holds.

So instead of one giant list, IVF keeps many smaller lists, one per group. A search finds the group that looks closest and only looks inside it.

You already use this idea every day:

• A supermarket has aisles. You want rice, so you walk to the rice aisle and skip the other twenty.
• Postal PIN codes split a country into zones. A letter for one zone is never sorted against every street in the country.

12. Centroids, and k-means in Plain Words

Each group needs a rough address, so a search can tell which groups are close. That address is the centroid: the average of all the points in the group. Add up every point's first number and divide by how many there are. Do the same for the second number, and so on.

How do we find good groups in the first place? The usual answer is k-means. It is simpler than it sounds.

Two steps, repeated. Assign, then move. After a few rounds the centroids stop moving much.

A picture that helps: a village wants to place 3 water tanks so nobody walks far. Put the tanks anywhere. Every house picks its nearest tank. Move each tank to the middle of the houses that picked it. Some houses now have a closer tank, so they switch. Move the tanks again. After a few rounds nothing changes much, and the tanks sit in sensible places.

13. Building an IVF Index

All that grouping is done once, when the index is built. Not once per search.

The build is the slow part, and it is paid once. Every search after that reuses the same lists.

Two practical details. Real systems usually learn the centroids from a sample, say a few hundred thousand vectors, because k-means over every vector is slow and gives almost the same result. And the lists are never perfectly even. Some topics are popular and their lists are long.

14. A Tiny IVF Example

Here are nine films with made up 2D vectors, so we can do the maths by hand.

k-means with K = 3 lands on the three obvious groups. Each centroid is the average of its three films:

• C1, love stories: [(2+2+3)/3, (2+3+2)/3] = [2.33, 2.33]
• C2, space: [(8+8+7)/3, (8+7+8)/3] = [7.67, 7.67]
• C3, superhero: [(8+7+8)/3, (2+2+3)/3] = [7.67, 2.33]

That is the whole index: three centroids and three short lists.

Now someone searches "astronauts travelling through space", and the model gives Q = [7.8, 7.6]. First, measure Q against the three centroids only:

C2 is by far the closest, so open list 2 and measure the films inside:

The answer is Interstellar, Gravity, The Martian. We did 3 centroid measurements and 3 film measurements, 6 in total, instead of 9. With nine films that saving is tiny. With a million it is the whole point.

15. IVF Search, Step by Step

Here is the same search as a conversation between the parts.

Only two kinds of measurement happen: against centroids, and against the vectors in the chosen lists.

The heart of the lab's version fits in a few lines:

search(query, k, nprobe) {
  // 1. Rank the centroids. This costs nlist distances, small next to N.
  const closestLists = this.centroids
    .map((centroid, id) => ({ id, distance: distance(query, centroid) }))
    .sort(closestFirst);

  // 2. Open only the nprobe closest lists and measure what is inside.
  const candidates = [];
  for (const { id: listId } of closestLists.slice(0, nprobe)) {
    for (const id of this.lists[listId]) {
      candidates.push({ id, distance: distance(query, this.vectors[id]) });
    }
  }

  // 3. These distances are real, so this ranking is exact.
  //    Only the choice of candidates was a guess.
  return { neighbors: topK(candidates, k), scanned: candidates.length };
}

Step 3 is the same top K as exact search. All the speed comes from step 2 skipping most lists. scanned counts the vectors measured, and the demo prints it next to recall.

16. Why Is It Called an Inverted File?

IVF stands for inverted file index. The name comes from search engines, and from the index at the back of a book.

A book's index does not list pages and say what is on them. It flips that around. It lists words and says which pages have them. "Photosynthesis: pages 12, 48, 210."

Same shape: a short key, then a list of where to look.

The mental model for IVF is three words: divide, locate, search. Divide the space into lists once. Locate the promising lists for each query. Search only inside them.

17. The Boundary Problem

Searching only one list has a catch. The lines between lists are not real walls. The index drew them to save work. A query near a line can have its true nearest neighbour on the other side.

Q sits slightly on the A side, so only list A is opened. b1 is closer, and it is missed.

You have probably met this in real life:

• Your home sits on the edge of two delivery zones. The app only shows restaurants from your zone, and misses the one 300 metres away across the line.
• A school admits children by catchment area. A family on the boundary road may live closer to the other school than half the children who go there.

18. nprobe: Open More Than One List

The fix is simple. Do not open only the single closest list. Open the closest few. The number of lists opened is called nprobe. In pgvector the same setting is called ivfflat.probes.

With nprobe = 3 in the example above, list B is very likely one of the three, and b1 is found. It is the dial from section 9 again: more lists means more candidates, fewer misses and a slower search, so there is no single right value.

A useful fact the lab tests: a bigger nprobe can never lower recall. The closest 4 lists always include the closest 3. Any true neighbour found with 3 lists is still found with 4. If you open every list (nprobe = nlist), you are back to exact search, with a little extra work for the centroids.

nprobe is the IVF dial. Open more lists for recall, fewer for speed.

19. IVF at Larger Scale

Now the numbers that make IVF worth it. Say we have 1,000,000 vectors in 1,000 lists, about 1,000 vectors in each.

With nprobe = 5 that is about 6,000 measurements instead of a million, about 0.6% of the work. Even with nprobe = 20, the work is about 2% of exact search.

A common starting point is nlist near the square root of N (1,000 for a million vectors), so there are about as many lists as vectors per list. Then raise nprobe until recall is good enough for the app. Real lists are uneven, so the "about" in the table matters.

20. HNSW: Start With a Graph

IVF splits space into regions. HNSW takes a different road. It asks: what if every vector simply knew a few vectors close to it? Then search would be like asking for directions.

A graph is a set of points joined by links. In HNSW every vector is a point (a node), and the links (edges) join vectors that are close.

A knows B and C. B knows A, C and D. D knows B, C and E. Nobody knows everybody.

The same idea works with people. You need a good plumber. You do not phone every plumber in the city. You ask a friend, who asks a neighbour, who knows one. Each person only knows a few others, and you still get there in a few steps.

21. Searching by Walking the Graph

Say the query Q sits near F. We start at some node, say A, and keep moving to whichever neighbour is closer to Q.

At every step we only measure the current node's neighbours. We never look at the rest of the graph.

The loop is short:

1. Start somewhere.
2. Measure the current node's neighbours.
3. Move to the one closest to the query.
4. Stop when no neighbour is closer than where you stand.

This is called greedy search, because each step grabs the best move in sight. Search has turned into walking.

22. The Problem With a Flat Graph

Greedy walking works, but on a big graph it can take a lot of steps. If every node only links to its close neighbours, the graph looks like a long chain, and a far away query means walking the whole chain.

Every arrow is one step. With millions of nodes, this could be thousands of steps for one search.

We want some long links too, to cross the graph quickly. But not so many that every node has to keep a huge list. HNSW gets both with layers.

23. The Road Analogy

Think about driving from one city to another. You do not take tiny lanes the whole way.

Highways cover distance fast. Lanes give you the exact door. You need both.

Trains work the same way. An express train stops only at big stations and covers the long distance. At the right big station you change to a local train that stops everywhere, and get off at the right small station.

That is the H in HNSW, hierarchical: a few layers, from highway to lane.

24. Layers

Instead of one graph, HNSW builds a stack of them.

A node that lives on layer 3 also lives on layers 2, 1 and 0. The bottom layer holds every vector.

The pattern:

25. A Query Walk, Top to Bottom

Say the query sits near X. The search starts at a fixed entry node on the top layer and walks down.

Each layer starts where the layer above finished. The walk gets shorter and more careful as it goes down.

In short: start high, take big jumps, drop a layer, take smaller jumps, and finish with a careful search at the bottom. On a large graph, a search measures only a tiny share of the nodes (typically a few hundred or a few thousand, a rough figure that depends on ef and the data).

Here is the same walk as a set of states:

The upper layers use plain greedy steps. Layer 0 uses a wider search, which section 29 explains.

26. Which Nodes Reach the Upper Layers?

Nobody chooses which nodes go up. Each new node flips a weighted coin.

Most nodes stop at layer 0. A few go one layer up. Very few go higher.

The lab uses a coin that says "go up" one time in M. With M = 8 and 10,000 nodes you expect roughly:

Random choice sounds careless, but it works well. It spreads the upper layer nodes across the whole space without anyone planning it, the way picking every eighth person at random from a crowd gives you people from every corner of the room.

27. What a Node Stores

An HNSW node is more than a vector. It also keeps its links, one list per layer it lives on.

The links on higher layers point further away, because there are fewer nodes up there to choose from.

So an HNSW index stores two things: the vectors, and the graph between them. That second part costs memory, which section 32 adds up.

28. HNSW Knows Distance, Not Meaning

This is easy to forget. HNSW has no idea what a film is. It sees vectors and the distance between them. Nothing else.

The embedding model creates the meaning. HNSW only finds its way around what the model built.

A sat-nav is a good comparison. It knows every road and how long each one takes. It has no idea why you are going to the hospital or the cinema. If the map is wrong, it will guide you perfectly to the wrong place. The same goes for HNSW: a weak embedding model gives fast, confident, unhelpful results.

29. Beam Search: Keeping Several Options Open

Pure greedy search keeps only one current node and always takes the best step in sight. That can trap it.

Greedy picks C because it is closer at that moment, and gets stuck. The better path went through D.

A hiker in fog who only ever walks downhill ends up in the first dip, not the valley floor. To avoid that, HNSW keeps a short list of the best candidates so far, not just one. This is called beam search, and the length of the list is ef.

The upper layers only need one node, because they are just getting close. Layer 0 is where ef matters. ef can never be smaller than K, since you cannot return 10 results from a list of 5. In pgvector this setting is hnsw.ef_search.

ef is the HNSW dial. A wider beam measures more nodes and finds more true neighbours.

30. Why Not Link Everything? The M Setting

If every node linked to every other node, the first step of any search would find the answer. It would also be absurd. With 1,000,000 nodes, each one would keep about 1,000,000 links. That is a trillion links.

Too few links and searches wander. Too many and memory and build time explode.

In the lab, M is the number of links a new node makes on each layer. Upper layers hold at most M links per node, and layer 0 holds at most 2M. When a list gets too long, the node keeps its closest links and drops the rest. Real HNSW is smarter here. It prefers links that point in different directions, so a node does not spend all its links on one tight cluster. The lab skips that rule to stay short, and says so in the code.

31. The Build Has a Cost Too

IVF pays its cost in k-means before any search. HNSW pays as it adds each vector.

Every insert is a small search. A million inserts is a million small searches.

The width of that build search is efConstruction (in pgvector, ef_construction). A wider build search finds better neighbours and makes a better graph, so later searches need less work. It also makes the build slower. So HNSW has two dials: one at build time, one at query time.

32. Why HNSW Is Memory Hungry

Add it up for 10,000,000 vectors of 1,536 float32 numbers, with M = 16.

Here is what each index keeps in memory next to the vectors:

Both keep the vectors. HNSW adds a much bigger structure on top than IVF does.

The links are small next to the vectors (about 1.3 GB against 61.4 GB), but they are far bigger than IVF's lists, and they add up. An HNSW search also jumps from node to node in no fixed order. That only runs fast if the whole graph sits in memory. IVF reads each list in one long run, which suits disk, because disks read long runs much faster than random jumps. HNSW buys its speed partly by spending memory.

Here is IVF and HNSW side by side:

Both avoid checking every vector. They just avoid it in different ways.

33. A Different Problem: Storage

ANN answers "how do we search a huge set of vectors fast?". There is a second question: how do we store them without going broke?

Take 100,000,000 vectors of 1,536 numbers. Each number is a float32, 4 bytes.

That 614.4 GB is only the raw numbers. The real bill is bigger.

On top of the vectors there are ids, metadata, the IVF lists or HNSW links, database overhead, and usually two or three copies for safety. And HNSW wants all of it in memory, which costs far more than disk. So vectors are expensive twice: to search and to keep.

34. Do We Need All That Precision?

An embedding looks like this:

[0.183742, -0.729182, 0.029117, 0.441827, ...]

Do we really need six decimal places to tell that two films are close? Usually not. This leads to quantization: storing numbers with less precision so they take less space.

You already accept this trade all the time:

• A weather app shows 31.4 degrees, not 31.41729.
• A shop rounds a bill of 499.62 rupees to 500.
• A photo saved as JPEG drops detail your eye will not miss, and is ten times smaller.

The simplest version is scalar quantization: keep one number per dimension, just a smaller one.

Going to int8 means fitting each number into one of 256 whole numbers, -128 to 127. If the values sit between -1 and 1, multiply by 127 and round.

A quarter of the space, and the number came back almost the same.

-0.729182 becomes -93, which reads back as -0.7323. Small errors in every dimension, but distances between vectors barely move. Product quantization goes much further than 4x.

35. Product Quantization: Cut the Vector Into Slices

Take a tiny vector of 8 numbers. As float32 it takes 8 x 4 = 32 bytes.

V = [0.2, 0.8, -0.4, 0.1, 0.7, -0.2, 0.9, 0.3]

Product quantization, or PQ, starts by cutting it into equal slices. With 4 slices, each slice is 2 numbers. Each slice is called a sub-vector.

8 numbers become 4 slices of 2. The number of slices is usually called m.

Each slice position is handled on its own from now on. All the first slices of every vector go together. All the second slices go together. And so on.

36. Codebooks: Common Shapes for Each Slice

Look at the first slice of a million vectors. Many of them look alike:

[0.20, 0.80]   [0.22, 0.79]   [0.18, 0.84]   [0.21, 0.77]

Instead of storing each one exactly, run k-means on all the first slices. Similar slices fall in the same group, and each group gets a centroid. In PQ a centroid is also called a codeword, and the list of all centroids for one slice position is the codebook.

The slice is replaced by the position of its closest codebook entry. A small whole number replaces two decimals.

A paint shop works like this. Nobody writes down the exact mix of pigments in your wall colour. They write "shade 17" from the colour chart. Anyone with the same chart can mix it again, close enough that you cannot tell.

37. Encoding a Whole Vector

Do the same for every slice, each with its own codebook. Say the four slices of V match entries 0, 203, 81 and 6. Slice 1 is [0.2, 0.8], which is closest to entry 0 from section 36.

Eight decimals became four small numbers.

The lab's encode step is the same loop:

public byte[] encode(double[] vector) {
    byte[] result = new byte[m];
    for (int part = 0; part < m; part++) {
        // The numbers of this slice, for example positions 0 to 3, then 4 to 7.
        double[] slice = slice(vector, part);
        // Which entry in this slice's codebook is closest?
        int code = KMeans.nearest(codebooks[part], slice);
        // One byte per slice. Java bytes are signed, so read back with code & 0xFF.
        result[part] = (byte) code;
    }
    return result;
}

KMeans.nearest returns the position of the closest codebook entry, and that position is the code. To go back, look each code up in its codebook and glue the pieces together. You get a vector that is close to the original, not equal to it.

38. Why 256 Entries Fit in One Byte

Real systems almost always use 256 entries per codebook. The reason is simple: 256 = 2 to the power 8, so a code from 0 to 255 fits in exactly 8 bits, which is one byte.

Now a real embedding. D = 1,536. Cut it into 96 slices of 16 numbers.

A vector that took 6,144 bytes now takes 96.

For the 100,000,000 vectors from section 33:

The codebooks are extra, but small and paid once: 96 x 256 x 16 numbers x 4 bytes is about 1.6 MB.

39. Comparing a Query With Codes

There is a neat trick at search time. The query stays a normal vector. For each slice position, measure the query's slice against all 256 entries of that codebook, once, and keep the answers in a table.

After the table is built, each stored vector costs 96 table reads and 96 additions, and no multiplying of the vector's own numbers.

This works because squared distance adds up slice by slice. The squared distance to the whole vector is the sum of the squared distances of its slices. The lab tests exactly this: the table answer equals the distance to the rebuilt vector.

Real systems combine PQ with IVF, often called IVF-PQ. IVF picks which lists to open, and PQ makes each list small and quick to scan.

40. PQ Is Lossy

Say a slice was [0.217, 0.794] and its codebook entry is [0.200, 0.810]. Close, not equal. After encoding, the original numbers are gone. This is lossy compression: some detail is lost for good, like in the JPEG photo.

The rebuilt vector is an approximation. Distances computed from it are approximations too.

So PQ adds a second kind of approximation on top of ANN. The usual fix is re-ranking: use the small codes to find, say, the best 100 candidates quickly, then fetch the full vectors for just those 100 and measure them exactly. You get most of the memory saving and most of the accuracy.

Quantization trades a little precision for a lot of memory. PQ can make vectors 64 times smaller.

41. What Makes a Vector Database

A vector database is more than a pile of arrays. A useful one has five layers.

Each layer adds one thing the one above it cannot do alone.

One stored record looks like this:

id:        101
title:     Interstellar
genre:     Sci-Fi
year:      2014
language:  English
embedding: [0.21, -0.45, 0.81, ...]

The distance rule must match how the embedding model was trained. Most text embedding models are meant for cosine similarity. Some are meant for dot product. For vectors scaled to length 1, cosine, dot product and straight line (L2) distance all rank results in the same order. The lab uses L2.

42. Metadata and Filtering

Real searches almost never use meaning alone. A user asks for "recent Hindi comedies like this one". That is two kinds of condition at once:

nearest vectors to the query
WHERE language = 'Hindi'
  AND genre    = 'Comedy'
  AND year    >= 2020

This is metadata filtering. Some systems call it scalar filtering or payload filtering. There are two simple ways to do it, and both have a weak spot.

Post filter is quick but can come back short. Pre filter always fills the list, but the index cannot help much, because it was built over every row, not just the rows that pass.

Here is the lab's example with toy [space, crime, love] vectors. The query is "a lost astronaut trying to get home", [0.9, 0.2, 0.1]. The rule is "2014 or later", and K = 3.

Post filter takes the top 3 (Apollo 13, The Martian, Gravity), then drops the two older films. Only The Martian is left. One result instead of three.

Pre filter drops every film before 2014 first, then searches what is left: The Martian, Ad Astra, Interstellar. Three results.

Same data, same rule, different answers. The order of the two steps matters.

The problem gets worse when the rule is strict. If only 1 film in 1,000 passes, a post filter on the top 10 usually returns nothing. A pre filter with an HNSW index has a different problem: most of the graph's links now lead to nodes you are not allowed to return. Real vector databases spend a lot of effort here. Some search a bigger top K and filter it. Some build the filter into the graph walk. pgvector 0.8 added iterative index scans, which keep reading the index until enough rows pass the filter.

A second example: a job site searching CVs "like this one" but only in Pune. Without care, the top 50 matches might all be in Bengaluru, and a post filter returns zero candidates.

43. Dedicated Vector Databases and pgvector

There are two broad ways to get all of this in production.

The first is a database built only for vectors: Pinecone, Qdrant, Weaviate, Milvus and others. They are designed around storing, indexing, filtering and scaling vectors, and they handle sharding (splitting data across machines) and replication (keeping copies) for you.

The second is to add vectors to a database you already run. pgvector does this for Postgres. It adds a vector column type, distance operators and both index types from this note.

CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE movies (
    id        BIGSERIAL PRIMARY KEY,
    title     TEXT NOT NULL,
    year      INT,
    genre     TEXT,
    embedding VECTOR(1536)
);

-- HNSW over cosine distance. m and ef_construction are the build dials.
CREATE INDEX movies_embedding_hnsw ON movies
    USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64);

-- The search dial for this session (40 is the default).
SET hnsw.ef_search = 100;

-- <=> is cosine distance, so smaller is closer.
SELECT title, year, embedding <=> $1 AS distance
FROM movies
WHERE year >= 2014
ORDER BY embedding <=> $1
LIMIT 10;

The WHERE year >= 2014 line is the metadata filter from section 42, in plain SQL. $1 is the query embedding the app passes in, and vector_cosine_ops tells the index to use cosine distance.

For IVF, the index line changes to USING ivfflat (embedding vector_cosine_ops) WITH (lists = 1000), and the search dial is SET ivfflat.probes = 10. Build an IVFFlat index after the table has data in it, because the lists are learned from the rows that exist at build time.

This is a starting point, not a rule. Many teams begin on pgvector and move only when they hit a real limit.

44. How to Choose

A few situations and a sensible first pick for each:

Whatever you pick, measure recall@K on your own data. Take a few hundred real queries, run exact search once to get the answer key, then tune the dial until recall and speed are both acceptable. The lab's demo does this in miniature.

45. The Whole Picture

Here is every layer from this note in one pipeline.

The embedding model makes the meaning. Everything after it is about storing that meaning and searching it cheaply.

Two mental models to keep. IVF: divide the world, then search the most promising neighbourhoods. HNSW: navigate the space instead of scanning it. And one for PQ: instead of storing every number exactly, store which common shape each slice looks most like.

46. Speed, Recall and Memory

Every choice in this note moves you around a triangle.

You can have any two quite easily. Getting all three takes tuning on real data.

Vector databases do not understand meaning. The model makes the map; the database stores it and searches it fast.

47. Building It: the ANN Lab

The lab is a command line program, written three times. There is no server and no model call. It has these parts, matching this note:

A few decisions worth copying:

48. The Code, Side by Side

The full projects are on the code page:

Browse the code for this note, or open src/FDE/code/10-ann-index/ on GitHub. The README there has the run and test commands for each version.

48.1 The HNSW search in three languages

The descent and the layer 0 beam are the same few lines everywhere. The third argument of searchLayer is the beam width: 1 on the upper layers, max(ef, k) on layer 0. The distance count before and after the search gives scanned:

int current = entryPoint;
// Upper layers: greedy, keep only the single best node.
for (int layer = topLayer; layer > 0; layer--) {
    current = searchLayer(query, current, 1, layer).get(0).id();
}
// Layer 0: a beam of ef candidates, never fewer than k.
List<Neighbor> found = searchLayer(query, current, Math.max(ef, k), 0);
return new SearchResult(ExactSearch.topK(found, k), distanceCalls - before);

let current = this.entryPoint;
// Upper layers: greedy, keep only the single best node.
for (let layer = this.topLayer; layer > 0; layer -= 1) {
  current = this.#searchLayer(query, current, 1, layer)[0].id;
}
// Layer 0: a beam of ef candidates, never fewer than k.
const found = this.#searchLayer(query, current, Math.max(ef, k), 0);
return { neighbors: topK(found, k), scanned: this.distanceCalls - before };

current = self._entry_point
# Upper layers: greedy, keep only the single best node.
for layer in range(self._top_layer, 0, -1):
    current = self._search_layer(query, current, 1, layer)[0].id
# Layer 0: a beam of ef candidates, never fewer than k.
found = self._search_layer(query, current, max(ef, k), 0)
return SearchResult(top_k(found, k), self._distance_calls - before)

48.2 Where to look in the code

The tests check the claims this note makes: exact search has recall 1.0 against itself, IVF with every list open returns exactly the exact answer, a bigger nprobe never lowers recall, k-means finds the middle of two obvious groups, no HNSW node keeps more than M links (2M on layer 0), layer 0 holds every node, a PQ vector is m one byte codes and its table distance equals the distance to the rebuilt vector, and the post filter returns fewer than K films while the pre filter returns K.

48.3 What this demo leaves out on purpose

Key Takeaways

• Exact search is always right and costs about N x D per query. At 10 million vectors of 1,536 numbers that is over 15 billion multiply-adds.
• ANN does not measure faster. It measures far fewer vectors, and it measures the ones it picks properly.
• ANN misses a neighbour when that vector was never looked at, not because its distance was worked out wrong.
• Recall@K is the share of the true top K that the search found. 8 of 10 is 0.8. Divide by K, so short answers cost you.
• Every ANN index has a dial between speed and recall. Pick the point that suits the job, and measure it on your own data.
• IVF groups vectors with k-means, keeps one list per centroid, and opens only the nprobe closest lists. A bigger nprobe never lowers recall.
• The boundary problem is why nprobe = 1 misses things: the lines between lists are not real walls.
• HNSW links close vectors into a graph with layers. A search starts high with big jumps, drops down, and ends with a beam of ef candidates on layer 0.
• M sets how many links each node keeps. More links mean easier navigation, more memory and a slower build.
• HNSW and every other index know distance, not meaning. The embedding model makes the meaning.
• Quantization stores numbers with less precision. int8 is 4 times smaller. PQ cuts a 1,536 number vector from 6,144 bytes to 96, 64 times smaller, at the cost of some accuracy.
• PQ compares a query with codes through a small lookup table, and re-ranking with full vectors wins back most of the lost accuracy.
• A vector database is five layers: data, vectors, a distance rule, an index and metadata.
• Post filtering can return fewer than K results. Pre filtering fills the list but fights the index. Real systems mix the two.
• pgvector gives Postgres a vector column, the <=> operator, and both HNSW and IVFFlat indexes. Dedicated vector databases help at very large scale or with heavy filtered search.