Vector search & ANN indexes

A second-hand clothing marketplace has 20 million listings. A shopper types "flowy summer dress". The best match is described as "light linen sundress, loose fit", which shares none of those words, so a keyword index (Search & inverted indexes) never finds it.

An embedding fixes that. An embedding model turns a piece of text, or an image, into a vector: a list of floating-point numbers, such as the 1,536 that OpenAI's text-embedding-3-small returns. The model is trained so that the distance between two vectors measures how related their inputs are. The query is embedded by the same model, and search becomes "find the listings whose vectors are nearest to this one":

"Nearest" needs a distance function, and the choice must match how the model was trained:

The exact answer is simple: compute the distance from the query to every listing and keep the closest 20. For 20 million vectors of 1,536 numbers, that's about 30.7 billion multiply-adds per query, reading 123 GB of 4-byte floats. A search box can't do that for every keystroke of every shopper. pgvector, the vector extension for PostgreSQL, does exact search by default, which gives perfect recall, and leaves adding an index to you.

An approximate nearest neighbor (ANN) index answers by looking at only a small part of the data, chosen so the true neighbors are very likely inside it. Its quality is measured by recall: of the true 20 nearest listings, how many did the index return? 19 of 20 is a recall of 95%.

Approximate indexes behave differently from the B-tree indexes developers are used to (Database indexing):

• Adding one changes the results. A B-tree makes a query faster and returns the same rows; an ANN index may return slightly different neighbors.
• Every index has dials. Each has a setting that trades speed for recall at query time, so the same index can be fast and rough or slower and closer.
• Recall must be measured. Compare the index's answers with exact search on a sample of real queries, and watch it as the data changes.

pgvector and FAISS, Meta's vector search library, both offer two families: graphs, which walk from neighbor to neighbor, and clustering, which only searches the clusters closest to the query. Both can be combined with compression.

HNSW (hierarchical navigable small world) connects each vector to its nearest neighbors in a graph, and stacks several graphs in layers. Every vector is in the bottom layer; each is also placed in higher layers with an exponentially decreasing probability, so the top layers are small and their links span long distances. A search enters at the top, greedily moves to whichever neighbor is closer to the query, and drops a layer when it can't get closer:

Three settings control it, shown here with pgvector's defaults:

• m (16): links per vector in each layer. More links, better recall, more memory.
• ef_construction (64): candidates considered while inserting. Higher builds a better graph, more slowly.
• ef_search (40): candidates kept while searching. The query-time dial: raise it for recall, lower it for speed.

HNSW gives better speed for a given recall than IVF, below, and needs no training step, so it can be built on an empty table. The price is memory and build time: it keeps every full vector plus its links, about 125 GB for the marketplace, and builds much faster when the graph fits in memory.

An IVF (inverted file) index groups the vectors into clusters, each with a center point. A search finds the few centers closest to the query and compares the query only with vectors in those clusters. pgvector's starting points are √rows lists for more than a million rows and √lists probes:

IVF builds faster and uses less memory than HNSW but gives lower recall at the same speed. It also needs training: the cluster centers are learned from data, so the index should be built after the table has representative rows.

Memory is the next limit, and quantization addresses it by storing an approximation of each vector. Product quantization (PQ) splits the 1,536 numbers into 64 slices and replaces each slice with the ID of its closest pattern from a learned codebook, one byte per slice. FAISS stores such an index at the code size plus 8 bytes for the ID:

Shoppers rarely want just "similar": they want similar, in size M, under $40, still for sale. With an ANN index the filter is usually applied after the index finds its candidates. The arithmetic: with HNSW's default 40 candidates in pgvector and a filter that matches 10% of rows, about 4 results survive, not 20.

Three fixes, depending on the filter:

• Search further until enough match. pgvector's iterative index scans keep scanning, up to a limit, until they find enough rows.
• Pre-filter with a regular index when the filter is very selective, then compare exactly: few rows match, so exact search is cheap.
• Separate indexes per common filter value, or per tenant. A shared index lets one tenant's vectors affect another's recall.

Keywords still matter: a shopper searching a brand name or "SKU 48213" wants that exact string, which is the keyword index's job. Hybrid search runs both searches and merges the lists. Reciprocal rank fusion needs no tuning: each item scores 1 ÷ (60 + its rank) in each list, summed:

An item found by both searches beats one found by only one, even if that one ranked higher there. The constant 60 is Elasticsearch's default; a larger constant gives lower-ranked items more say.

Choose by scale and by what you already run: