Vector Search Indexes: Why ANN Exists

Why this matters

The first vector search bridge introduced the basic idea:

embed content -> store vectors -> embed query -> find nearby vectors

That works as a mental model, but it hides a systems problem.

If a database stores ten vectors, comparing the query with every vector is fine. If it stores ten million vectors, checking everything can be too slow.

This page explains why vector databases use Approximate Nearest Neighbor search:

slightly less exact -> much faster

Mental model

Imagine searching for the closest note in a huge library.

Exact search means:

walk to every shelf
compare every note
return the closest one

Approximate search means:

use shortcuts
inspect the most promising area
return a very close note quickly

The approximate result might not always be the single mathematically closest note. But for many AI applications, a very relevant result returned quickly is better than a perfect result returned too late.

Core ideas

• Exact nearest-neighbor search compares the query with every stored vector.
• Exact search becomes expensive when the database has many vectors.
• Approximate Nearest Neighbor search is usually shortened to ANN.
• ANN trades guaranteed exactness for speed.
• Recall means how often the search finds the truly relevant nearest results.
• HNSW reduces search by navigating a graph of nearby vectors.
• IVF reduces search by looking inside selected clusters.
• PQ compresses vectors so storage and distance estimates become cheaper.
• HNSW, IVF, and PQ are not the same kind of trick.

Walkthrough

Exact search checks everything

Suppose a vector database contains five study-guide passages.

Exact search can compare the query with all five:

query -> compare with A
      -> compare with B
      -> compare with C
      -> compare with D
      -> compare with E
      -> rank all results

That is easy to understand and gives the exact nearest result.

Now scale the same idea:

query -> compare with 10,000,000 stored vectors

The logic is still simple, but the cost is no longer small.

ANN searches fewer candidates

Approximate Nearest Neighbor search tries not to compare against everything.

The promise is:

inspect fewer vectors -> return close matches faster

The trade-off is:

may miss the exact best neighbor -> usually still finds useful neighbors

That trade-off is often acceptable in semantic search, recommendations, and RAG because the top result is rarely the only useful result. Several nearby passages may be good enough to help the system answer.

HNSW: navigate a neighbor graph

HNSW stands for Hierarchical Navigable Small World.

Friendly meaning:

move through a shortcut graph toward closer and closer vectors

Imagine every passage is connected to some nearby passages.

A -- B -- C
     |    |
     D -- E

Search does not scan every point from left to right. It starts somewhere, follows links that seem to move closer to the query, and refines the search as it goes.

HNSW also uses layers:

upper layers -> fewer points, long jumps
lower layers -> more points, careful local search

Plain version:

use shortcuts first, then refine near the target

IVF: search promising clusters

IVF stands for Inverted File Index.

Friendly meaning:

split the vector space into neighborhoods, then search only likely neighborhoods

The database first groups vectors around centroids.

cluster 1: SQL, MySQL, query safety
cluster 2: embeddings, vector search, HNSW
cluster 3: PCA, LDA, dimensionality reduction

For a query about approximate search, the system first finds the closest clusters. It might search cluster 2 heavily and ignore cluster 1 or 3.

Plain version:

find the right neighborhood before checking individual houses

IVF can be efficient, especially when the vector collection is relatively stable and cluster assignment can be prepared ahead of time.

PQ: compress vectors

PQ stands for Product Quantization.

Friendly meaning:

store smaller codes instead of full-size vectors

Vectors can be large. If every vector has hundreds or thousands of numbers, storing and comparing millions of them uses a lot of memory.

PQ reduces that burden by splitting vectors into parts and replacing those parts with compact codes.

The goal is not mainly:

choose which area to search

The goal is:

make vectors cheaper to store and compare

That is why PQ should be read differently from HNSW and IVF.

Three ideas, three roles

Idea	Main role	Friendly picture
HNSW	navigate through a graph	shortcuts between nearby points
IVF	narrow the search area	search selected neighborhoods
PQ	compress vectors	store compact codes

They can also be combined in real systems. For study purposes, keep their roles separate first.

Where RAG fits

RAG often uses vector search as its retrieval step.

question -> query embedding -> ANN search -> relevant passages -> LLM prompt

The ANN index does not write the answer. It helps retrieve candidate context quickly enough that the application can use it.

Term Decoder

Term	Friendly meaning
nearest neighbor	stored vector closest to the query vector
exact search	compare the query with every stored vector
ANN	approximate search for nearby vectors
recall	how often search finds the truly relevant close results
candidate	vector selected for closer inspection
index	helper structure that speeds up search
HNSW	graph-based shortcut search
IVF	cluster-based narrowing
centroid	center point representing a cluster
PQ	vector compression technique

Common traps

Approximate does not mean random

ANN uses organized shortcuts, clusters, or compressed representations. It is approximate because it may skip some comparisons, not because it guesses blindly.

Exact is not always better in practice

Exact search can be too slow at large scale. A fast, high-recall result can be more useful than a perfect result that arrives too late.

HNSW, IVF, and PQ are not interchangeable

HNSW navigates a graph. IVF searches selected clusters. PQ compresses vectors.

PQ is not just another graph or cluster index

PQ mainly reduces memory and distance-computation cost by using compact codes.

ANN does not fix bad embeddings

ANN speeds up search over the vectors you already have. It does not make poor representations meaningful.

Check yourself

Why is exact nearest-neighbor search expensive at scale?

It compares the query vector with every stored vector, which becomes costly when there are millions or billions of vectors.

What trade-off does ANN make?

It gives up a guarantee of always finding the exact nearest neighbors in exchange for much faster search.

What is the rough idea of HNSW?

Search through a layered graph, using shortcut links to move toward closer vectors and then refining locally.

What is the rough idea of IVF?

Cluster the vector space and search only the most promising clusters for a query.

What is the rough idea of PQ?

Compress vectors into compact codes so they are cheaper to store and compare.

Why should PQ be described differently from HNSW and IVF?

HNSW and IVF mainly reduce where the system searches. PQ mainly reduces the cost of storing and comparing vector representations.

Now Read the Full Lesson

The full Modern Data Management 2 lesson uses these same ideas in the broader database-and-AI story:

embeddings -> vector database -> similarity search -> ANN index -> retrieved context -> LLM answer

Next: Modern Data Management 2

Source anchors

• Supports: study-guide/docs/lessons/04-modern-data-management-2.md
• Source file: notebooks/Module2/04-Modern Data Management 2.pdf
• Key source concepts prepared here: exact nearest-neighbor search, Approximate Nearest Neighbor search, recall trade-off, HNSW, NSW, skip-list intuition, IVF, centroids, PQ, vector search for RAG