# Approximate nearest-neighbour indexes

> HNSW and IVF trade a little recall for searching millions of vectors in milliseconds.

Concept · Embeddings & retrieval · https://levelcode.org/concepts/ann-indexes

Finding the vectors closest to a query **exactly** means comparing the query against every stored vector. For 10 million 1,536-dimension vectors, that's about 15 billion multiply-adds per query. It's fine for a few thousand vectors and far too slow beyond that. **Approximate nearest-neighbour (ANN)** indexes answer in milliseconds by examining only a small, well-chosen fraction of the vectors, and accept that they'll sometimes miss a true neighbour.

The trade-off is measured as **recall@k**: of the true top *k* results, how many did the index return? Production systems typically tune for 0.9–0.99.

## HNSW: a navigable graph

**Hierarchical Navigable Small World** links each vector to a few of its neighbours, in several layers. The top layers are sparse and act like express lanes; the bottom layer contains everything. A search starts at the top, greedily moves towards the query, drops a layer, and repeats.

- **Fast and high-recall,** and usable as soon as you insert data. It's the usual choice in pgvector and the default in Qdrant, Weaviate and many other vector stores.
- **Memory-heavy** (graph links plus vectors, ideally all in RAM), and slower to build.
- Tune it with `m` (links per node) and `ef_construction` at build time, and `ef_search` at query time. A higher `ef_search` gives better recall and slower queries.

## IVF: clusters

**Inverted file** indexes cluster the vectors (k-means into `lists` centroids). A query is compared with the centroids, and only the nearest `probes` clusters are searched in full.

- **Less memory and faster to build** than HNSW, and it combines well with compression (product quantization) for billion-scale collections.
- **Needs representative data at build time,** and recall drops if the data drifts away from the clusters. Rebuild it periodically.

```sql
-- pgvector
CREATE INDEX ON chunks USING hnsw (embedding vector_cosine_ops);
SET hnsw.ef_search = 100;
SELECT id, content FROM chunks ORDER BY embedding <=> $1 LIMIT 10;
```

## Filtering is the hard part

Most real queries add conditions like `tenant_id = 42 AND lang = 'en'`. If the index returns its top 10 and **then** the filter removes 9 of them, you get 1 result. Options:

- **Over-fetch** (ask for 100, then filter), or use engines with **filtered HNSW** that apply the condition during the graph walk. pgvector 0.8+ has iterative index scans for this.
- **Partition by the filter,** for example one index per tenant, when there are few distinct values.
- **Pre-filter with a regular index** when the filter is very selective, then search the small remainder exactly.

ANN indexes play the same role for vectors that [B-trees](https://levelcode.org/concepts/b-tree-vs-lsm-tree) play for sorted keys. Measure recall on your own queries before and after tuning.