# What is approximate nearest neighbour (ANN) search, and how do you choose an index?

Finding the stored vectors closest to a query without comparing it with every one, by using an index that may now and then miss the true closest in exchange for far faster searches.

- Page: https://tecyfy.com/concepts/approximate-nearest-neighbor-search
- Subject: Data engineering in the AI era (https://tecyfy.com/concepts)
- Level: intermediate
- Also called: ANN search, Approximate nearest neighbour search

Approximate nearest neighbour (ANN) search finds the stored vectors closest to a query without comparing the query with every one of them. It is what makes search by meaning fast enough for large collections, and it is why a [vector database](https://tecyfy.com/concepts/vector-database) can answer in milliseconds.

## Exact first

The plain way is exact search: compare the query with every stored [Embedding](https://tecyfy.com/concepts/embedding) and keep the closest. It always finds the true nearest. pgvector does this by default, and the Faiss library calls these indexes *flat*. For thousands of vectors, or even a few hundred thousand, exact search is often fast enough. Start there.

The trouble is that the work grows with the collection. Every query does one long sum per stored vector, and an embedding can hold a thousand numbers or more.

## Approximate: trade a little recall for a lot of speed

An ANN index organises the vectors so a search only visits a small part of them. The price, as pgvector puts it, is some recall: now and then the true closest match is skipped, and results can change once the index is added. Recall is the share of the true nearest neighbours a search returns. 95% recall at 10 results means that, on average, 9.5 of the 10 true nearest are found.

## The main kinds of index

| Index | How it narrows the search | Memory | Good for |
|---|---|---|---|
| Flat (exact) | Doesn't: checks every vector | The full vectors | Small collections, and the yardstick for recall |
| IVF (inverted file) | Groups vectors into lists around centres, then searches only the lists nearest the query | Full vectors plus an id | Fast builds and lower memory |
| [HNSW](https://tecyfy.com/concepts/hnsw) | Hops through layers of graphs linking near neighbours | Full vectors plus links | The best speed for a given recall, in pgvector's comparison |
| Quantised (SQ, PQ) | Stores compressed vectors and compares those | A fraction of the full size | Very large collections that would not fit in memory |

The Faiss documentation gives the sizes: a flat index stores 4 bytes for each number of each vector, an 8-bit scalar quantizer 1 byte, and product quantization only a few bytes for the whole vector. IVF and quantization combine, as in Faiss's IVF-PQ.

pgvector offers HNSW and IVFFlat. It describes HNSW as having better query performance for the recall, but slower builds and more memory. IVFFlat builds faster and uses less memory, but has to be built after the table has data, because it learns its lists from the vectors.

## Settings you will meet

- **IVF:** the number of lists, and how many lists to search, the *probes*. pgvector suggests starting with rows ÷ 1,000 lists up to a million rows, the square root of the rows above that, and the square root of the lists as probes. More probes: better recall, slower search.
- **HNSW:** links per point and the length of the candidate list, `ef_search`. Try the [HNSW demo](https://tecyfy.com/concepts/hnsw) to see the candidate list at work.

## How to choose and tune

1. Measure first. Run your real queries with exact search to get the true answers.
2. Add the index and run the same queries. Compare: recall at the number of results you use, and latency at the 95th percentile.
3. Raise the search setting (probes or `ef_search`) until recall is where you need it, then check latency again.
4. Re-check when the collection grows a lot, or when you change the embedding model.

## Why it matters for AI answers

In [RAG](https://tecyfy.com/concepts/rag), the passages a search misses never reach the model. An index tuned only for speed can lower answer quality with no error anywhere. Treat recall as part of the answer's quality, and measure it the same way.

## Related

- [HNSW](https://tecyfy.com/concepts/hnsw): Hierarchical Navigable Small World: a vector index that links each vector to its near neighbours in layers of graphs, so a search hops from coarse to fine and checks only a small share of the vectors.
- [Vector Database](https://tecyfy.com/concepts/vector-database): A database built to store embeddings and quickly find the ones closest to a query, which is how AI apps search by meaning.
- [Cosine Similarity](https://tecyfy.com/concepts/cosine-similarity): A measure of how closely 2 vectors point the same way, from 1 for the same direction to −1 for opposite; with embeddings, a higher score means closer in meaning.
- [Embedding](https://tecyfy.com/concepts/embedding): A list of numbers that stands for the meaning of a piece of text, an image or other data. Things with similar meaning get similar numbers, so a computer can find them.
- [pgvector](https://tecyfy.com/concepts#pgvector): A PostgreSQL extension that adds vector similarity search.
- [FAISS](https://tecyfy.com/concepts#faiss): Facebook AI Similarity Search library for fast vector similarity.
- [RAG](https://tecyfy.com/concepts/rag): A way to answer from your own documents. A search finds the passages that match the question, and they are added to the prompt before the model writes.

## Sources

- [pgvector](https://github.com/pgvector/pgvector)
- [Faiss indexes](https://github.com/facebookresearch/faiss/wiki/Faiss-indexes)
- [The Faiss library](https://arxiv.org/abs/2401.08281)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://arxiv.org/abs/1603.09320)