Vector Databases and ANN Search - Complete Deep Dive

Prerequisites: Embeddings, Database Indexing, Back-of-Envelope Estimation Used in: RAG End to End, Hybrid Search and Reranking, Advanced Retrieval Build it: Lesson 14 - Vector Search and What ANN Buys You implements this as runnable, tested code you can execute offline.

What is a Vector Database?

A vector database stores high-dimensional vectors and answers one question fast: which stored vectors are closest to this one? It is a nearest-neighbour index with a storage engine, metadata filtering, and the usual operational surface bolted on.

The reason it needs to exist is that your normal index cannot do this job. A B-tree works because one dimension has a total order, so you can bisect it — see Database Indexing. There is no meaningful total order in 768 dimensions, so there is nothing to bisect.

Real-world analogy: finding a house by address is a B-tree lookup — ordered, exact, cheap. Finding the nearest coffee shop is not. You do not survey every shop in the city; you walk toward the neighbourhood you know has cafes, then look around locally. You might miss a marginally closer shop one street over. A vector index works the same way, and that last sentence is the whole design tradeoff.

Why Exact Search Dies at Scale

Exact nearest-neighbour search is brute force. Compare the query against every vector, keep the best k. Cost is O(N * d) per query, linear in corpus size and in dimensions.

Assumption for illustration - 10M vectors at 768 dimensions
  10,000,000 * 768 = 7,680,000,000 multiply-accumulate operations per query

At 10,000 vectors that is trivial and you should just do it.
At 10,000,000 vectors, served at even modest QPS, it is hopeless.

So production retrieval uses approximate nearest-neighbour search. ANN skips most of the corpus and accepts that it may miss some true neighbours.

This is the key mental shift: recall becomes a tunable SLO. Recall@10 is the fraction of the true top-10 that your index actually returned. It is not a bug to be fixed, it is a dial to be set — trade recall for latency and memory, deliberately, with a number attached.

Which means you need a ground truth to measure against. Take a few hundred representative queries, run exact search offline to get the true neighbours, then measure what your ANN configuration returns. Without that baseline you are not tuning, you are guessing. Teams that skip this step discover their recall problem months later, through complaints about answer quality that look like an LLM issue.

The Index Families

Flat - the correctness baseline

No index. Store vectors, scan them all, return the exact top k. Recall is 1.0 by definition.

Flat is not a strawman. It is the right answer below roughly the low hundreds of thousands of vectors, and it is the reference you compute recall against. Always keep a flat path available even after you build something clever.

IVF - partition then probe

Inverted File index. At build time, cluster the vectors into nlist cells and store each vector in its nearest cell. At query time, find the nprobe cells whose centroids are closest to the query and brute-force only those.

If nlist is 1,000 and nprobe is 10, you scan roughly 1% of the corpus. The failure mode is geometric: a true neighbour sitting just across a cell boundary is invisible unless you probe its cell too. Raising nprobe buys recall linearly in scan cost. IVF is cheap to build, cheap in memory, and needs a training pass over a representative sample to learn the centroids.

HNSW - navigable small-world graph

Hierarchical Navigable Small World is the default in most systems today. Build a proximity graph where each vector links to M near neighbours, then stack sparse layers above it — upper layers hold few nodes with long-range links, and layer 0 holds every vector with short local links.

Search is greedy descent. Start at an entry point in the top layer, hop to whichever neighbour is closer to the query, and when no neighbour improves, drop a layer and repeat. The upper layers cover distance fast; layer 0 does the fine-grained work.

flowchart TB
    subgraph L2["Layer 2 - few nodes and long range links"]
        A2[Entry point]
        B2[Distant hub]
    end

    subgraph L1["Layer 1 - medium density"]
        B1[Same hub one layer down]
        C1[Regional node]
    end

    subgraph L0["Layer 0 - every vector lives here"]
        C0[Same regional node at the base]
        D0[Local neighbour]
        E0[Nearest match returned]
    end

    A2 -->|greedy hop toward the query| B2
    B2 -->|descend a layer| B1
    B1 -->|greedy hop toward the query| C1
    C1 -->|descend a layer| C0
    C0 -->|expand ef search candidates| D0
    D0 -->|no neighbour improves so stop| E0

    classDef client fill:#f97316,stroke:#c2410c,color:#fff
    classDef edge fill:#6cf,stroke:#333,color:#000
    classDef service fill:#10b981,stroke:#065f46,color:#fff
    classDef async fill:#b4f,stroke:#333,color:#000
    classDef data fill:#fbbf24,stroke:#92400e,color:#000

    class A2 client
    class B2,B1 edge
    class C1,C0 service
    class D0 async
    class E0 data

HNSW gives excellent recall-per-latency and needs no training pass. It costs memory for the graph on top of the vectors, is slow to build, and — the point most teams learn late — handles heavy churn badly.

Product quantization - compression, not search

PQ is orthogonal to the above. Split each vector into subvectors, learn a small codebook per subspace, and store one byte-sized code per subvector instead of full floats. A 768-dim float32 vector at 3,072 bytes becomes a handful of dozens of bytes.

Distances computed on codes are approximate, so PQ is normally paired with rescoring: retrieve a generous candidate set using compressed vectors, then re-rank those few candidates against full-precision vectors. Simpler int8 scalar quantization gives a 4x cut with less distortion and is the sensible first step. Disk-resident variants such as DiskANN push the same idea further, keeping compressed vectors in RAM and full vectors on SSD.

The Parameters That Actually Matter

The distinction worth internalizing: ef_search and nprobe are runtime dials you can change per query, so you can serve a fast-and-loose path for autocomplete and a slow-and-thorough path for a legal search over the same index. M, ef_construction, and nlist are build-time decisions you can only revisit by rebuilding.

Metadata Filtering - The Hard Part

Real queries are never pure similarity. They are “similar chunks, from documents this user may see, in the last 90 days, excluding drafts.” Combining a filter with ANN search is where implementations genuinely diverge.

Bad — post-filter. Run ANN for k results, then drop the ones failing the filter. It is trivial to implement and it silently destroys recall the moment the filter is selective.

Assumption for illustration
  ANN fetches 100 candidates
  the filter matches 1 document in 1,000

  expected survivors = 100 * 0.001 = 0.1

You asked for 10 results and will usually get zero, with no error.

Worse, it fails non-uniformly: fine for a tenant holding 40% of the corpus, broken for the tenant holding 0.1%. That is a bug report from one customer that nobody can reproduce.

Good — pre-filter. Resolve the filter first into an allowlist of IDs, then search only those. Correct recall, but if the allowlist is large you are back toward brute force, and you have lost the index’s advantage.

Great — filter-aware search. The index evaluates the predicate during traversal, so the graph walk only ever considers matching nodes, and the engine picks a strategy based on estimated selectivity: brute-force the survivors when the filter is very selective, walk a filtered graph when it is not. Qdrant’s filterable HNSW and the filtered-search paths in Weaviate and Milvus work along these lines. Partitioning also helps: give each tenant its own index or shard so tenancy is a routing decision rather than a predicate.

Whatever you pick, measure recall with your real filters applied. Unfiltered recall numbers tell you nothing about filtered performance, and access-control predicates are exactly the selective filters that break naive post-filtering.

Hybrid Search, Updates, and Deletes

Hybrid sparse and dense. Most engines now index a sparse or lexical representation alongside the dense one and fuse the two result lists. Elasticsearch and OpenSearch come from the lexical side and added vectors; Weaviate, Qdrant, and Milvus come from the vector side and added sparse support. Either way you get two channels and a fusion step, covered in Hybrid Search and Reranking.

Updates and deletes are where graph indexes hurt. An HNSW graph’s quality comes from links built against the data present at build time. Delete a node and you cannot cheaply repair every inbound link, so engines write a tombstone and filter the node out at query time. That means:

• Deleted vectors keep consuming memory and keep being traversed, so queries get slower as tombstones pile up.
• Repeated updates — delete plus insert — degrade graph connectivity, and recall drifts down without any config changing.
• Recovery is compaction or a periodic rebuild, which is a heavyweight background job competing with your query traffic.

IVF tolerates churn better because a delete only touches one cell’s posting list, though centroids drift as the distribution shifts and eventually want retraining. If your corpus is a slowly growing document store, none of this will bother you. If it is a chat history or an event stream with constant rewrites, design for rebuilds from day one: write to a fresh index and swap behind an alias rather than mutating in place.

Memory Sizing - Back of Envelope

Memory, not QPS, is what sizes a vector cluster. Every number below is a labelled assumption chosen for clean arithmetic; the method is the point, not the total.

Assumptions
  corpus            10,000,000 chunks - one vector each
  dimensions        768
  precision         float32 - 4 bytes per dimension
  HNSW M            16
  metadata payload  200 bytes per chunk

Raw vectors
  768 * 4 = 3,072 bytes per vector
  10,000,000 * 3,072 = 30,720,000,000 bytes = 30.7 GB

HNSW graph links
  layer 0 holds up to 2M = 32 neighbour slots per node
  upper layers hold up to M = 16 and contain only a small fraction of nodes
  assume 40 slots per vector at 4 bytes per neighbour ID
  40 * 4 = 160 bytes per vector
  10,000,000 * 160 = 1,600,000,000 bytes = 1.6 GB

Metadata payload
  10,000,000 * 200 = 2,000,000,000 bytes = 2.0 GB

Subtotal   30.7 + 1.6 + 2.0 = 34.3 GB
Headroom   assume 1.5x for build and segment merges and page cache
Provision  roughly 51 GB of RAM - one large node or two shards

Now the levers, same assumptions:

int8 scalar quantization      768 * 1 = 768 B per vector    -> 7.68 GB    4x cut
product quantization at 96 B   96 B per vector              -> 0.96 GB   32x cut
Matryoshka truncation to 256   256 * 4 = 1,024 B per vector -> 10.24 GB   3x cut

Two honest caveats. Compression costs recall, and how much is corpus-specific — measure it, never assume it. And compressed indexes usually keep full-precision vectors somewhere for rescoring, so you are choosing what lives in RAM rather than eliminating the data.

Do You Even Need a Dedicated Vector Database?

Most teams start with too much infrastructure here. The progression:

Bad — a dedicated vector cluster for 50,000 chunks. You have added a system to operate, back up, monitor, secure, and keep consistent with your primary store, to solve a problem a sequential scan would have handled. The dual-write problem between your source of truth and your vector store will cost you more than the index ever saved.

Good — the database you already run. pgvector puts vectors in Postgres, so your chunks, their metadata, their permissions, and their vectors live in one transaction and one backup. You get SQL filters and joins for free, and no new operational surface. This is the correct starting point for a large fraction of RAG systems, and it stops being correct when vector memory outgrows the box you were willing to give Postgres, or when heavy ANN traffic starts competing with your transactional workload. Same argument applies if you already run Elasticsearch or OpenSearch for search or logs — you have a lexical engine and a vector field in one place, which is most of hybrid search already.

Great — a dedicated vector engine, once a specific constraint forces it. Name the constraint before you migrate: corpus beyond what one node’s RAM holds and you need real sharding; filter-aware ANN because post-filtering is wrecking recall for small tenants; quantization and disk-resident indexes to make the memory bill survivable; or per-query recall and latency tuning you cannot express through a general-purpose query planner. Any of those justifies the move. “It is what people use for RAG” does not.

Feature sets in this space move quickly, so treat the table as a shape-of-the-landscape guide as of this writing and verify specifics against current documentation. Every one of these can serve a competent RAG system; the differentiators are operational fit and filtering behaviour, not a leaderboard.

When to Use

✅ Use an ANN vector index when:

• Corpus is large enough that exact scan misses your latency budget — measure it, do not assume it
• You can state a recall target and have a ground-truth set to measure it against
• Filters are either non-selective or your engine evaluates them during traversal
• The corpus changes at a rate your rebuild strategy can absorb

❌ Don’t reach for one when:

• The corpus is small; a flat scan in Postgres or memory is faster to build, exact, and cheaper to run
• Your real problem is ingestion quality — bad chunks retrieved quickly are still bad chunks
• Queries are exact-match lookups on identifiers; that is a lexical index or a primary key
• You cannot yet measure recall, so you would be tuning parameters against vibes
• It would become a second copy of your source data with no reconciliation story

Common Interview Questions

Q1: Why not just use exact nearest-neighbour search?

Because it is O(N * d) per query, linear in corpus size. Ten million 768-dim vectors is roughly 7.7 billion multiply-accumulates per query, which no latency budget survives at scale. ANN trades recall for speed by skipping most of the corpus. The important framing is that recall becomes an explicit SLO rather than an accident: you pick a recall target, measure against exact search on a held-out query set, and tune runtime parameters to hit it. And exact search stays useful — it is the baseline you compute recall against, and it is the right answer for small corpora.

Q2: HNSW or IVF, and why?

HNSW for most workloads. It gives better recall per unit of latency, needs no training pass, and exposes ef_search as a per-query dial. The costs are graph memory on top of the vectors, slow builds, and poor behaviour under heavy churn, since deletes become tombstones that degrade both latency and recall until you compact or rebuild. IVF is cheaper in memory, much faster to build, and tolerates updates better because a delete touches one cell’s posting list, but it needs a training pass to learn centroids and its recall suffers for neighbours sitting just across a cell boundary. Write-heavy or memory-constrained pushes you toward IVF; read-heavy with a slowly growing corpus pushes you toward HNSW.

Q3: How do you combine metadata filtering with ANN search without wrecking recall?

Not by post-filtering. If you fetch 100 candidates and the filter matches 1 in 1,000 documents, you expect 0.1 survivors where you asked for 10 — and it fails non-uniformly, so it works for your largest tenant and breaks for your smallest. Options are pre-filtering into an allowlist of IDs, which is correct but degenerates toward brute force when the allowlist is large, or filter-aware traversal where the index evaluates the predicate during the graph walk and picks a strategy from estimated selectivity. Partitioning per tenant turns the most selective filter into a routing decision instead. Whichever you choose, measure recall with the real filters applied, because access-control predicates are precisely the selective filters that break the naive approach.

Q4: Size the memory for a 10 million chunk index.

Start from the vectors and state assumptions. At 768 dimensions in float32 that is 3,072 bytes each, so 10M vectors is about 30.7 GB. HNSW with M = 16 adds neighbour lists — budget roughly 40 slots at 4 bytes, about 160 bytes per vector, so 1.6 GB. Add metadata, say 200 bytes per chunk for 2 GB. That is around 34 GB, and with headroom for builds, merges, and page cache you provision roughly 50 GB, meaning one large-memory node or two shards. Then name the levers: int8 quantization cuts vectors 4x to about 7.7 GB, product quantization can reach 30x, and Matryoshka truncation to 256 dimensions gives about 10 GB. Each costs recall by an amount you must measure on your own corpus, and compressed indexes usually keep full-precision vectors for rescoring, so you are deciding what lives in RAM rather than deleting data.

Q5: When would you not use a dedicated vector database?

Whenever a system you already operate can do the job. pgvector keeps chunks, metadata, permissions, and vectors in one transaction and one backup, gives you SQL filters and joins, and adds no new operational surface — and if you already run Elasticsearch or OpenSearch, you have a lexical engine and a vector field in one place, which is most of hybrid search. Migrate when you can name the constraint: RAM exceeded so you need real sharding, post-filtering wrecking recall for selective tenants, quantization needed to make the bill survivable, or per-query recall tuning a general-purpose planner cannot express. The failure mode of skipping this reasoning is a second copy of your source data with no reconciliation story, solving a problem a sequential scan would have handled.

Build it in code: Agentic AI Course · Fundamentals: Core Concepts