Vector databases

Story

Hide story

Forty thousand parcels sit in the Sorting Depot, and a passenger at the counter wants the three most like hers. Merrow taps the counter. “One minute,” he says, wearily, as he says most things.

You could walk every row and compare each parcel with hers. You could split the depot into zones and walk only the nearest ones. You could ask a clerk who thinks he remembers where such things went.

Which would you try first?

Concept#

A vector databaseVector databaseA store built to hold embeddings and find the nearest ones quickly, usually with metadata filters. Start with what you already run and move when a measured limit forces it.Open the glossary entryClose stores embedding vectors and answers one question quickly: “which stored vectors are nearest to this query vector?” To do that at scale it uses an approximate nearest-neighbor (ANN)Approximate nearest neighbor (ANN) searchFinding very close, though not always the closest, vectors with an index. You trade some recall for lower latency and memory.Open the glossary entryClose index. ANN returns almost the true nearest neighbors, much faster than checking all of them.

The index internals and tuning below go deeper than the rest of this module. If you only need to choose a store, read the mental model, the exact-search section and the store comparison first.

Why It Matters#

Every RAG system needs retrieval that is both fast and relevant at scale. Interviewers probe the “approximate” part, not whether you know a vector database “stores vectors”. You are expected to say what is traded away, which knob buys it back, and how you would check.

Mental Model#

Picture a library of millions of books. Exact search walks every shelf with the query in hand. An ANN index is a floor plan that lets you walk straight to the right area and check only the shelves around it. You may miss the single best book, but you finish in a fraction of the time. You pay for the map in memory and build time.

Why exact search stops working#

Exact (brute-force) search compares the query with every stored vector. The work grows with the number of vectors times the number of dimensions. For an illustrative 10 million vectors of 1,536 dimensions, one query needs about 10,000,000 x 1,536 = 15.4 billion multiply-adds. That is feasible offline and too much for a request with a latency budget of tens of milliseconds, especially at many queries per second.

Brute force does have a place. It is exact and needs no index. As a rough guide (measure on your own hardware), a few thousand to tens of thousands of vectors is often fast enough. It is also your ground truth for measuring ANN recall, below.

Recall: what “approximate” costs#

Recall@kRecall@kThe share of the relevant or true top-k items that appear in the top k results. For an ANN index it measures the recall lost to approximation.Open the glossary entryClose is the share of the true top-k neighbors that the ANN search actually returned. If the exact top 10 contains 10 vectors and ANN returns 9 of them, recall@10 is 0.9. Every ANN index has settings that trade recall against latency and memory. Higher recall costs more time or more memory. You choose a point on that curve, you do not get both.

Two index families#

HNSW: a layered graph#

HNSWHNSWHierarchical Navigable Small World, a layered graph index. Search starts in a sparse top layer and descends to a dense bottom layer. High recall, memory-heavy.Open the glossary entryClose (Hierarchical Navigable Small World, Malkov and Yashunin) links each vector to nearby vectors in a graph, and stacks several layers of it. The top layer is sparse with long links. The lower layers are denser. A search enters at the top, hops greedily toward the query, drops a layer, and repeats until the bottom layer. Think of a motorway, then a main road, then a street map.

• Strengths: high recall at low latency, and new vectors can be inserted one at a time.
• Costs: the graph is large and is usually held in memory next to the vectors. Building is slower than for simpler indexes.
• Knobs: M is how many links each node keeps. ef_construction is how wide the search is while building (it affects build time). ef_search is how many candidates a query tracks. Higher values raise recall at the cost of memory, build time or latency. M and ef_construction are fixed at build time, so changing them means rebuilding. ef_search can be changed per query. In pgvector the defaults are m = 16, ef_construction = 64 and hnsw.ef_search = 40 (checked 2026-10-09).

IVF: clusters and probes#

IVFIVFInverted file index: vectors are grouped into clusters around learned centres, and a query scans only the nearest clusters. Lighter on memory than HNSW, and needs training on representative data.Open the glossary entryClose (inverted file) splits the vectors into clusters, each with a center point. A query is compared with the centers first, and only vectors in the closest few clusters are scanned. Think of postal districts: you search the districts nearest the address, not the whole country.

• Strengths: less memory and faster builds than HNSW. The trade-off, per the pgvector README, is that at the same recall its queries are usually slower (checked 2026-10-09).
• Costs: it needs a training step to find the cluster centers from a sample of your data, so the table should hold representative data before you build the index. If the data later changes a lot, the clusters may fit it less well. A true neighbor sitting in an unprobed cluster is missed.
• Knobs: nlist or lists is how many clusters. nprobe or probes is how many clusters each query scans. Search time grows roughly in step with probes, and probing all clusters equals brute force. FAISS documents this and defaults nprobe to 1. pgvector defaults ivfflat.probes to 1 and suggests starting lists at rows / 1,000 for up to 1 million rows, and probes near the square root of lists (both checked 2026-10-09). Treat those as starting points to measure, not answers. Raising nlist while nprobe stays fixed means each query scans a smaller share of the data. That is faster but usually lowers recall, and it needs a rebuild.

Quantization shrinks vectors#

Product quantization (PQ)Product quantization (PQ)A vector compression method that splits each vector into sub-vectors and stores, for each, the id of its nearest entry in a small learned codebook. It saves memory and speeds up distance checks, at some loss of recall.Open the glossary entryClose and other compression schemes store a compressed approximation of each vector, so more fit in memory and distance checks are faster. The price is lower recall. A common pattern is to search the compressed vectors, then re-rank a short list with the original vectors.

Diagram#

Diagram: Both indexes avoid scanning every vector.

How to measure recall#

Never ship an ANN index without measuring it. A simple method:

1. Sample a few hundred real queries, ideally from your logs or a realistic test set.
2. For each, get the exact top-k with brute force. This is the ground truth.
3. Get the ANN top-k with your index and settings.
4. Compute recall@k as the overlap, and record latency.
5. Change one knob at a time (ef_search, nprobe) and re-measure. Pick the cheapest setting that meets your recall target.

pgvector’s documentation describes the same check: compare approximate results with exact search, which you can force by disabling index scans in a transaction (checked 2026-10-09). Also check whether retrieval recall is what really limits your product. Sometimes the embeddings or the chunking matter more than the last point of ANN recall.

Choosing a store#

Pick by your scale, your team and your other requirements, not by popularity.

On hosting: do not equate “dedicated” with “managed only”. Qdrant is open source under the Apache 2.0 license, can be run yourself with Docker, and also has a managed cloud. Weaviate describes itself as open source, with Docker, Kubernetes and embedded options, plus a managed Weaviate Cloud. Pinecone’s documentation describes a managed database and mentions a bring-your-own-cloud option, where it runs in your cloud account. Check its current docs for deployment options (all checked 2026-10-09). Products and plans change, so confirm before you decide.

One concrete limit to know: pgvector’s vector type can be indexed up to 2,000 dimensions, and halfvec up to 4,000 (checked 2026-10-09). A 3,072-dimension embedding therefore needs half-precision storage or a shorter vector. Details like this can decide the choice, so read the current docs.

A rule of thumb (judgment, not a measured law): start with what you already run (often pgvector), measure, and move when a measured limit (latency, memory, ops burden, filtering) forces you.

Metadata filters and freshness#

Real queries are rarely pure similarity. They say “similar to this, and department = legal, and the user may read it”. Two things to design, not discover in production:

• Filtering. With an approximate index, a filter may be applied after the index returns its candidates. pgvector’s documentation gives the example of a condition matching 10% of rows with ef_search = 40: only about 4 rows survive on average, so you can get fewer than k results. Remedies include iterative index scans (pgvector 0.8.0 and later), a larger candidate list, partitioning by the filter field, or an engine that filters during the graph search. Test filtered queries for recall too. Permission filters are a security boundary, so a missed filter is a data leak, not a ranking quirk.
• Freshness. Documents change. Update the stored vector when the text changes, and delete the old chunks. Use deterministic chunk IDs (for example document ID plus chunk number) so an update overwrites its old chunk instead of leaving a stale copy. Some indexes need periodic rebuilds or compaction after many deletes.

Real-World Application#

A support-search team indexes 50,000 help articles. At that size, pgvector with an HNSW index, one WHERE filter for product and language, and a nightly recall check against brute force on 300 logged queries is a defensible design. A product catalogue of hundreds of millions of items, with per-second updates and several teams querying it, is where a dedicated, sharded system earns its cost. In both cases the discipline is the same: measure recall and latency, then change one knob.

Interview Perspective#

Expect: “how does HNSW work at a high level”, “when would you not need a dedicated vector database”, “how do you keep an index fresh” and “how do you know your ANN index is good enough”. Common mistakes are treating ANN output as exact, never measuring recall, and ignoring filtering.

Provenance: Common industry pattern. These are standard topics for GenAI roles, not a verified list for any named company.

Practice Questions#

These are generated practice questions, not reported from any company.

• Basic: Why can you not just brute-force compare against every vector at scale?
• Intermediate: Which knob raises recall in HNSW, which in IVF, and what does each cost?
• Advanced: Your recall@10 is 0.95 on average but only 0.6 on queries with a tight metadata filter. What could explain the gap, and what would you test?
• Product-Company: A document was just updated, but search still returns the stale version. What is happening and how do you fix it?

Activity#

Decide in writing between pgvector and a dedicated vector database for two cases: a 50,000-document internal wiki, and a 500-million-item product catalogue. For each, state the numbers you would measure first (vector count, dimensions, queries per second, update rate, filter selectivity) and the result that would make you change your mind.

Homework#

Using any library with an ANN index (FAISS, or pgvector if you have Postgres), build an index over a few thousand embeddings. Compute exact top-10 with brute force for 50 queries. Then vary ef_search or nprobe over at least four values, and record recall@10 and time per query. Write three sentences on where you would set the knob, and why.

Quick Revision#

• Exact search is accurate but costs vectors x dimensions per query; ANN trades a little recall for much lower latency.
• HNSW: layered graph, high recall, memory-heavy, inserts incrementally; knobs M, ef_construction, ef_search.
• IVF: clusters probed per query, smaller memory, needs training; knobs nlist and nprobe.
• Measure recall@k against brute force on real queries; change one knob at a time.
• Start with what you run (often pgvector); move when a measured limit forces it. Open-source dedicated databases can be self-hosted.
• Design filters and updates explicitly; post-filtering can return too few results.

Check yourself#

• Walk-through: Compare HNSW and IVF for a 50M-vector index with frequent updates. Which knobs trade recall for latency, and how do you verify recall?
• Variation: Your HNSW index is 2x over the memory budget. Name three options (quantization, shorter vectors, switching to IVF) and the likely recall cost of each.
• Common misconception: Treating ANN as exact, never measuring recall, or ignoring the cost of metadata filtering.

Related#

• Embeddings and similarity search
• RAG architecture and chunking
• Better retrieval