Approximate nearest-neighbour 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.

-- 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 play for sorted keys. Measure recall on your own queries before and after tuning.