Vector Databases and ANN: IVF, HNSW and Product Quantization

Topic 09 taught us why brute-force vector search becomes expensive. Topic 10 answers the next question:

How can we search millions of vectors quickly without checking every vector?

Imagine a library with 10 million books. To find 10 books similar to one you like, you could inspect every book, or go to the most promising shelves first. The second approach is faster, although you might miss a great book on a shelf you skipped.

That is the idea behind Approximate Nearest Neighbour (ANN) search.

We'll learn five main concepts:

1. ANN and Recall@K: Search fewer vectors and measure how many of the true best matches you find.
2. IVF (Inverted File Index): Group nearby vectors into neighbourhoods and search only selected groups.
3. HNSW: Connect nearby vectors in a graph and navigate toward the query.
4. Quantization and Product Quantization (PQ): Compress vectors to reduce memory usage.
5. Metadata filters and pgvector: Combine similarity search with ordinary database conditions.

1. Quick revision: what problem are we solving?

Suppose a streaming app has 10 million titles, and each title has a 1,536-dimensional embedding.

A user searches for:

Movies about humans exploring deep space.

The query becomes a vector, and we want the 10 closest stored vectors.

With exact search, we measure the query against every title:

N × D = 10,000,000 × 1,536

That's approximately 15.36 billion multiply-adds for one query. At 1,000 searches per second, the workload becomes enormous.

The problem is not that the distance calculation is wrong. It's that we're doing work on millions of vectors that are unlikely to be useful.

Exact search vs ANN

The key difference is:

• Exact search: measure every vector.
• ANN: choose promising candidates first, then measure those candidates properly.

ANN usually does not approximate the distance calculation itself. It approximates the selection of vectors to inspect. If the best vector is skipped, the algorithm cannot return it.

2. Recall@K: how do we measure ANN quality?

Speed alone isn't enough. We need to know whether the search still finds good results.

Suppose exact search returns these 10 films:

A B C D E F G H I J

ANN returns:

A B C D E F G H X Y

Eight of the true top 10 were found.

Recall@K = (number of true top-K items found) / K

So:

Recall@10 = 8 / 10 = 0.8

Example: Recall@10

True top 10:  A B C D E F G H I J
8 found, 2 missed

Recall@10 = 0.8 (80%)

The order of the items doesn't matter for recall@K. We only check how many items overlap with the true top K. The denominator stays K, even if the search returns fewer results.

Try calculating recall

True neighbours found: 7 / 10, so 70% recall. 7 true neighbours were found; 3 were missed.

ANN has a tuning dial

More candidates usually means better recall but more work.

For a casual recommendation app, a few missed results may be acceptable. For finding duplicate invoices before payment, missing a match can be expensive.

Remember: ANN is a trade-off between speed and recall, not automatically a bad version of exact search.

3. IVF: Inverted File Index

IVF is short for Inverted File Index. Its main idea is:

Divide the vector space into groups, find the closest groups, and search only those groups.

Think of a supermarket. If you need rice, you go to the rice aisle rather than checking every item in the store.

Step 1: Group similar vectors

Embeddings often form clusters. Space films may sit near each other, romance films may form another group, and superhero films another.

Each group has a centroid: the average position of the vectors in that group.

Illustration of three clusters; real embeddings have hundreds or thousands of dimensions.

Step 2: Use k-means to create the groups

The course explains k-means as a repeated two-step process:

1. Assign each vector to its closest centroid.
2. Move each centroid to the average position of the vectors assigned to it.

Repeat these steps until the centroids stop moving much.

This clustering work is done when building the index, not from scratch for every search. The index stores the centroids and a list of vector IDs for each centroid.

Step 3: Search only the nearest lists

The course gives this toy example with three clusters:

A query for astronauts travelling through space becomes:

Q = [7.8, 7.6]

First, compare Q against the three centroids.

The space centroid is closest. We open its list and compare the query with the three films in that group.

We searched 3 centroids and 3 films: 6 measurements instead of 9 in this tiny example. With millions of vectors, the savings can be much larger.

The IVF setting: nlist vs nprobe

These two terms are easy to confuse.

Suppose we have one million vectors divided into 1,000 lists, with roughly 1,000 vectors per list.

These figures assume roughly even lists. Real clusters are not always evenly sized.

The boundary problem

What if the closest vector is just across a cluster boundary?

If we search only one list, we might miss that vector even though it is closer than every candidate in the selected list.

The solution is to search several nearby lists.

• nprobe = 1: fewer candidates, faster, potentially more misses.
• nprobe = 5: more candidates, more work, typically better recall.
• nprobe = nlist: search every list, returning to exact search over the vectors.

For the same fixed IVF index and candidate scoring rule, increasing nprobe cannot reduce recall because the candidate set only grows.

Memory trick: nlist = how many lists exist; nprobe = how many lists you open.

4. HNSW: Hierarchical Navigable Small World

IVF divides the space into groups. HNSW takes a different approach: it connects nearby vectors in a graph, then searches by navigating the links.

A graph has:

• Nodes: vectors
• Edges: links between vectors that are close to each other

Imagine finding a good plumber. Instead of calling every plumber in a city, you ask a friend, who asks a neighbour, who knows someone nearby.

That is the intuition behind graph navigation.

How does HNSW search?

A simple greedy graph search works like this:

1. Start at a node.
2. Measure the query's distance to its neighbours.
3. Move toward a closer neighbour.
4. Stop when no neighbour offers a closer position.

But a flat graph can force a search to take many small steps. HNSW solves this by building multiple layers, like a road network.

A node that exists on an upper layer also exists on the layers below it. Layer 0 contains every vector.

The search starts at the top, makes large jumps, drops down a layer, and gradually narrows the search. This is similar to using highways for most of a journey and local roads to reach the destination.

How are nodes assigned to layers?

The course's simplified lab uses a random weighted choice: a node has a chance of roughly 1/M to move up one layer, then flips again to see whether it moves higher.

With M = 8, for 10,000 nodes, the expected counts are approximately:

Most nodes stay on the bottom layer; only a few reach the top. This gives the graph its hierarchy.

The HNSW settings: M, ef, and efConstruction

ef is important because greedy search can get stuck in a local dead end. Instead of keeping only one option, HNSW keeps several candidates open during the bottom-layer search. This is called beam search.

For example:

• ef = 1: very narrow search, like greedy walking.
• ef = 10: keep 10 candidate options.
• ef = 100: consider a wider set; typically more work and higher recall.

The course notes that ef must be at least K when returning K results. In pgvector, the query-time setting is hnsw.ef_search.

IVF vs HNSW

The course describes HNSW as often achieving better recall at the same speed, while requiring more memory. The right choice still depends on the dataset and workload.

Memory trick:

• IVF = divide into lists
• HNSW = navigate a graph
• nprobe = lists to open
• ef = candidates to keep exploring
• M = graph links per node

5. Quantization: reduce the memory bill

So far, we've focused on how to search vectors quickly. But vectors themselves take a lot of memory.

A 1,536-dimensional vector stored as float32 uses:

1,536 × 4 = 6,144 bytes

For 100 million vectors, that's about 614.4 GB just for the raw numbers, before IDs, metadata, index structures, and copies.

Quantization stores numbers at lower precision to reduce the amount of space they take.

Scalar quantization

The course compares these representations:

For example, if values are between -1 and 1, a simple int8 encoding multiplies a value by 127 and rounds it.

Original float32:  0.183742
Multiply by 127:   23.34
Round to int8:     23
Reconstructed:     23 / 127 = 0.1811

The reconstructed value is close to the original, but not identical. That's the trade-off: smaller storage, with some precision lost.

6. Product Quantization (PQ)

Product Quantization takes compression further by dividing a vector into slices and replacing each slice with a small code.

Imagine a vector with eight numbers:

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

Divide it into four slices, each containing two numbers:

Illustrative code numbers from the course example. The compressed vector stores four codes instead of eight original numbers.

What is a codebook?

A codebook is a collection of common patterns for a particular slice position.

For each slice position:

1. Collect that slice from many vectors.
2. Use clustering to find common patterns.
3. Store the representative patterns in a codebook.
4. Replace each slice with the ID of its closest pattern.

The ID is the code. Instead of storing the exact decimal values, we store which common pattern they most closely resemble.

The analogy from the course is a paint shop: rather than recording every exact pigment mixture, write down a shade number from a colour chart. The shade is close enough, but not necessarily identical.

Why 256 codebook entries?

The course uses 256 entries per codebook because 256 possible values fit in one byte.

For a 1,536-dimensional vector:

• Divide it into 96 slices.
• Each slice contains 16 dimensions.
• Store one byte per slice.

So the compressed vector needs only 96 bytes instead of 6,144 bytes.

These estimates exclude metadata, IDs, index overhead, and other storage costs. PQ's codebooks also take some memory, but are small compared with the full collection.

How can we search compressed vectors?

The query remains a normal vector. For each slice position, the system calculates distances from the query slice to the entries in that slice's codebook, then stores those distances in a lookup table.

When scoring a compressed stored vector, it reads the table entry corresponding to each code and adds the distances together.

This avoids repeatedly calculating a full high-dimensional distance against every compressed vector.

PQ is lossy: use re-ranking

PQ replaces exact values with representative patterns. The original values cannot be recovered exactly, so the calculated distances are approximate.

A common strategy is:

1. Use the compressed vectors to find, for example, the best 100 candidates.
2. Retrieve those candidates' full vectors.
3. Recalculate their distances exactly.
4. Return the final top K.

This is called re-ranking. It helps recover accuracy while retaining much of the memory saving.

Remember the difference:

• ANN reduces the number of vectors you inspect.
• Quantization reduces the memory needed to store and compare vector representations.
• PQ is a form of lossy compression that replaces slices with codebook IDs.

They solve different problems and can be combined.

7. Metadata filtering: meaning plus ordinary conditions

Real searches often combine semantic similarity with structured filters.

For example:

Find recent Hindi comedies similar to this movie.

The semantic condition is “similar to this movie.” The metadata conditions are:

WHERE language = 'Hindi'
  AND genre = 'Comedy'
  AND year >= 2020

The order of filtering and vector search matters.

Post-filtering

1. Run vector search for the top K.
2. Remove results that don't satisfy the metadata conditions.

This can be fast, but it may return fewer than K results.

Pre-filtering

1. Restrict the dataset to records that satisfy the metadata conditions.
2. Search for the nearest vectors within that set.

This can fill the requested number of results when enough matching records exist, but filtering can make index traversal harder.

Consider the course's example: K = 3, with a year filter of 2014 or later.

Post-filtering first picks Apollo 13, The Martian, and Gravity, then removes the two older films. Only The Martian remains.

Pre-filtering removes older films before searching, so the top three are The Martian, Ad Astra, and Interstellar.

A real vector database may use larger candidate sets, integrate filters into the index walk, or continue scanning until enough eligible results are found.

8. What is pgvector?

A vector database needs more than an array of numbers. The course describes five layers:

pgvector is a PostgreSQL extension that adds a vector column type, distance operators, and vector indexes. This lets an application store normal relational data and embeddings together.

For example, the course shows how to create a table and an HNSW index:

CREATE EXTENSION IF NOT EXISTS vector;

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

CREATE INDEX movies_embedding_hnsw ON movies
    USING hnsw (embedding vector_cosine_ops)
    WITH (m = 16, ef_construction = 64);

Then search for similar films, while filtering by year:

SET hnsw.ef_search = 100;

SELECT title, year, embedding <=> $1 AS distance
FROM movies
WHERE year >= 2014
ORDER BY embedding <=> $1
LIMIT 10;

Here:

• VECTOR(1536) stores a 1,536-dimensional vector.
• vector_cosine_ops configures the index for cosine distance.
• <=> is the cosine-distance operator in pgvector.
• $1 is the query embedding supplied by the application.
• hnsw.ef_search controls the query-time search width.

For IVF, the course uses an ivfflat index with lists as the build setting and ivfflat.probes as the query-time setting. The IVFFlat index should be built after the table contains data, because its lists are learned from the existing rows.

pgvector or a dedicated vector database?

Dedicated vector databases mentioned in the course include Pinecone, Qdrant, Weaviate, and Milvus. They offer vector-focused indexing, filtering, sharding, and replication capabilities.

These are starting points, not universal rules. The course recommends testing recall and speed against real queries before committing to a design.

9. Put everything together

Here is the complete semantic-search pipeline from Topic 10:

The embedding model creates the representation of meaning. The index makes finding similar representations faster. Quantization reduces storage costs. Metadata filters enforce the user's other requirements.

10. Interview revision questions

"What is ANN?"

Approximate Nearest Neighbour search finds similar vectors by inspecting a promising subset instead of every stored vector.

"What is recall@K?"

The fraction of the true top K neighbours that the search actually returns.

"What is the difference between IVF and HNSW?"

IVF groups vectors into clusters and searches selected lists. HNSW connects vectors in a layered graph and navigates the links.

"What are nlist and nprobe?"

nlist is the total number of IVF lists. nprobe is how many lists are searched per query.

"What are M and ef in HNSW?"

M controls how many links nodes keep. ef controls the width of the search candidates and affects recall and query cost.

"What is efConstruction?"

It controls the search width used while building the HNSW graph, trading construction time for graph quality.

"What is Product Quantization?"

PQ splits vectors into slices and replaces each slice with the ID of a representative codebook entry.

"Why is PQ lossy?"

It replaces original numeric values with approximate representative patterns, so the original vector cannot be reconstructed exactly.

"What is re-ranking?"

First find candidates quickly, then calculate more accurate distances using their full vectors and reorder the results.

"What is the difference between pre-filtering and post-filtering?"

Pre-filtering applies metadata conditions before vector search. Post-filtering searches first and removes ineligible results afterward.

"What is pgvector?"

A PostgreSQL extension that adds vector storage, distance operators, and vector indexes such as HNSW and IVFFlat.

"How do you choose an ANN index?"

Test it against representative queries. Measure latency, recall, memory usage, and the effect of metadata filters on your own data.

11. Quick quiz

1. What does ANN primarily approximate?
   • The arithmetic for every distance
   • Which vectors should be examined
   • The embedding model's output
2. Exact search finds 10 true neighbours. ANN finds 9 of them. What is recall@10?
   • 0.09
   • 0.9
   • 1.0
3. What does IVF's nprobe control?
   • Number of dimensions
   • Number of lists searched
   • Number of graph links
4. Which index uses a hierarchical graph?
   • IVF
   • B-tree
   • HNSW
5. What does a higher HNSW ef generally do?
   • Searches more candidates and can improve recall
   • Compresses the vectors
   • Reduces the number of stored dimensions
6. What does PQ store for each slice?
   • The entire original vector
   • An ID for a representative codebook entry
   • A database primary key only
7. Why can post-filtering return fewer than K results?
   • It removes ineligible items from the already selected top K
   • It always scans every vector
   • It changes the embedding model
8. Which PostgreSQL extension supports vector columns and indexes?
   • pgvector
   • Redis
   • Express

Final memory sheet

The central idea of Topic 10 is that fast vector search depends on choosing good candidates, not on calculating every distance faster. IVF chooses promising clusters; HNSW navigates a graph; PQ reduces memory; and recall@K helps measure the accuracy you retain.