RAG · Module 5 of 14 · 9 concepts · about 15 min

Vector Databases and Nearest-Neighbour Search

Where the vectors live and how the closest ones are found in milliseconds among millions: exact search, approximate search, the two main index types, compression, filtering and how to choose a database.

At work: The infrastructure decision in a RAG project: what stores the vectors, how much memory it needs, and how it stays fast as the collection grows from thousands to hundreds of millions.

Exact search and why it stops scaling

What it is

The simplest way to find the nearest vectors is to compare the query with every stored vector and keep the best.

This is exact or brute-force search (also called a flat index).
It always returns the true nearest neighbours.

Why it matters

Its cost grows in a straight line with the collection.

Each comparison touches every number in the vector, so one query costs chunks × dimensions multiplications. At 10,000 chunks that is instant.
At 10 million chunks of 768 numbers it is about 7.7 billion multiplications per query, which is too slow for a live system serving many users.
Exact search is the right choice for small collections and the baseline that everything faster is measured against.

In the real world: A small firm's assistant over 3,000 internal documents runs exact search inside its application with a NumPy array, and has no vector database to operate at all.

import numpy as np

def exact_search(query, vectors, k=5):
    """vectors: (n, d), all normalised. Returns the indices of the k closest."""
    scores = vectors @ query           # n dot products
    return np.argsort(-scores)[:k]

Reaching for a vector database for 5,000 chunks. Below roughly a hundred thousand vectors, exact search in memory is fast, perfectly accurate and has nothing to tune. Adding infrastructure there only adds things that can break.

Approximate nearest neighbour search (ANN)

What it is

Approximate nearest neighbour (ANN) search gives up the guarantee of finding the true nearest vectors in exchange for speed.

It organises the vectors ahead of time so that a query only looks at a small, promising fraction of them.
It finds most of the true nearest neighbours, not always all.

Why it matters

The trade is measured by recall: of the true top 10, how many did the approximate search return?

A recall of 0.95 means it found, on average, 9.5 of the 10.
Every ANN index has a setting that trades recall for speed, and you choose the point on that curve.
Typical systems run at 0.95 to 0.99 recall and answer in a few milliseconds over millions of vectors.

In the real world: A music service searches 80 million track embeddings in under 10 milliseconds by accepting that about one result in fifty differs from what an exact search would give.

Visual example

Trade-off

ANN trades a small, measurable loss of recall for a very large gain in speed.

Exact search versus approximate search

	exact (flat)	approximate (ANN)
Vectors compared per query	All of them	A small fraction
Finds the true nearest?	Always	Usually (recall 0.95 to 0.99)
Query time as data grows	Grows in step with it	Grows very slowly
Build step	None	Index must be built first
Good up to	About 100,000 vectors	Billions

Confusing this recall with retrieval quality. ANN recall only says how well the index copies what exact search would have returned. If the embeddings themselves are poor, a perfect index faithfully returns poor results.

HNSW: a graph you walk towards the answer

What it is

HNSW (Hierarchical Navigable Small World) is the most widely used ANN index.

It links each vector to a handful of its nearest neighbours, forming a graph.
A search starts at an entry point and repeatedly steps to whichever neighbour is closer to the query, until no neighbour is closer.
Extra upper layers with long-distance links let the search cross the space in a few big jumps first, like taking a motorway before local roads.

Why it matters

It is fast and reaches high recall, and it supports adding vectors without a full rebuild, which is why it is the default in most vector databases. Three settings matter.

M: links per vector; more links mean better recall and more memory.
efConstruction: how carefully the graph is built; higher is slower to build and better in quality.
efSearch: how many candidates a query keeps in play; this is the recall-versus-speed dial you tune at query time.

In the real world: A support platform raises efSearch during quiet hours for better recall and lowers it at peak traffic to hold response times, without rebuilding anything.

Visual example

HNSW settings

Two are fixed when the index is built. efSearch can be changed per query.

The three HNSW settings and what they trade

setting	what it controls	raising it gives	raising it costs	set at
M	Links per vector	Higher recall	More memory, slower build	Build time
efConstruction	Care taken while building	A better graph	Slower build	Build time
efSearch	Candidates kept during a search	Higher recall	Slower queries	Query time

import faiss

d = 768
index = faiss.IndexHNSWFlat(d, 32)        # M = 32 links per vector
index.hnsw.efConstruction = 200           # build quality
index.add(chunk_vecs)                     # float32 array, shape (n, d)

index.hnsw.efSearch = 64                  # raise for recall, lower for speed
distances, ids = index.search(query_vecs, 10)

Forgetting that HNSW lives in memory. The vectors plus the graph links must fit in RAM for it to be fast. At hundreds of millions of vectors that becomes the main cost of the system, which is what quantisation is for.

IVF: search only the nearest clusters

What it is

IVF (inverted file index) first groups all vectors into clusters, using k-means; each cluster has a centre point.

A query is compared with the cluster centres, and then only the vectors inside the few closest clusters are searched.
Two settings: nlist, the number of clusters, and nprobe, how many clusters each query searches.

Why it matters

It uses less memory than HNSW and pairs well with compression, so it suits very large collections. nprobe is the recall-versus-speed dial: searching 1 cluster of 1,000 is fast and misses neighbours that sit just across a cluster boundary; searching 20 finds most of them and is 20 times the work.

In the real world: An image-search company with two billion vectors uses IVF with compression because a pure HNSW graph of that size would need more memory than it can afford.

import faiss

d, nlist = 768, 4096                      # 4,096 clusters
quantizer = faiss.IndexFlatIP(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_INNER_PRODUCT)

index.train(sample_vecs)                  # learn the cluster centres
index.add(chunk_vecs)

index.nprobe = 16                         # clusters searched per query
distances, ids = index.search(query_vecs, 10)

Training the clusters once and never again. If new documents are about new topics, the old cluster centres no longer fit the data, clusters become lopsided and recall slowly decays. IVF needs occasional retraining; HNSW does not.

Quantisation: smaller vectors, less memory

What it is

Quantisation compresses vectors by storing each number less precisely. Three kinds:

Scalar quantisation stores each number in 1 byte instead of 4.
Binary quantisation keeps only the sign of each number, 1 bit.
Product quantisation (PQ) splits the vector into parts and replaces each part with the ID of the nearest entry in a small learned codebook, reaching very high compression.

Why it matters

Memory is the main cost of vector search at scale, and compression cuts it by 4 to 32 times or more.

The price is accuracy, and the standard remedy is rescoring: use the compressed vectors to find, say, the top 200 quickly, then re-rank those 200 with the full-precision vectors kept on disk.
This recovers most of the lost recall for little extra time.

In the real world: A search company moves from float32 to 1-byte vectors with rescoring, cuts its memory bill by about three quarters, and measures a recall drop of under one percent.

Visual example

Computed

Memory for 10 million vectors of 768 numbers, in three storage formats.

Vector memory by storage format (index overhead not included)

format	precision	bytes per vector	total (GB)	quality
float32 (original)	4 bytes per number	3072	30.7	Exact values
int8 (scalar quantisation)	1 byte per number	768	7.7	Very small quality loss
binary	1 bit per number	96	1	Larger loss; rescore the top results

The arithmetic

float32: 768 × 4 bytes × 10M = 30.7 GB

int8: 768 × 1 byte × 10M = 7.7 GB (4× smaller)

binary: 768 ÷ 8 bytes × 10M = 1 GB (32× smaller)

Turning on aggressive compression without rescoring and without measuring recall afterwards. Binary quantisation in particular can drop recall sharply on some embedding models and barely at all on others.

Metadata filtering: pre-filter versus post-filter

What it is

Real searches come with conditions: only this customer's documents, only English, only this year.

Post-filtering runs the vector search first and then throws away results that fail the condition.
Pre-filtering applies the condition first and searches only among the vectors that pass.

Modern vector databases do a combined version, checking the condition while walking the index.

Why it matters

Post-filtering has a silent failure.

Ask for the top 10, and if 9 of them fail the filter, the user gets 1 result, or none, even though thousands of matching chunks exist further down the ranking.
Pre-filtering always returns the best matches among the allowed set.
For access control this is not only a quality issue but a safety one: restricted chunks should never be candidates at all.

In the real world: A multi-company help-desk product finds small customers getting empty answers; their chunks never made the global top 50, and moving to filtered search fixes it.

# Post-filter: can return too few results
hits = index.search(q_vec, k=10)
hits = [h for h in hits if h.metadata["tenant"] == user.tenant]   # maybe 1 left

# Pre-filter (the database applies the condition during the search)
hits = index.search(
    q_vec,
    k=10,
    filter={"tenant": user.tenant, "language": "en"},
)                                                                # always up to 10

Fetching 'a few extra' and post-filtering as a workaround. With a selective filter (one tenant out of ten thousand) no reasonable over-fetch is enough, and the search returns nothing for users who have plenty of matching documents.

Practise it: Design a Semantic Search System

Choosing a vector database

What it is

Four kinds of home for vectors:

A library such as FAISS: fast, runs inside your program, but you handle storage, updates and filtering yourself.
An extension to a database you already run, such as pgvector for PostgreSQL: vectors beside your ordinary data, one system to operate.
A dedicated vector database such as Qdrant, Milvus, Weaviate or Pinecone: built for scale, filtering and high query volume.
A search engine with vector support such as Elasticsearch or OpenSearch: keyword and vector search in one place.

Why it matters

The choice is mostly about operations, not algorithms, since most of them use HNSW underneath. Ask:

How many vectors, now and in two years?
Do I need filtering and per-customer isolation?
Do I need keyword search in the same system?
Does the team already run PostgreSQL or Elasticsearch?
Managed service or self-hosted?

For up to a few million vectors, the database you already have is usually the right answer.

In the real world: A SaaS company already on PostgreSQL adds pgvector and ships in a week; two years later, at 300 million vectors, it moves to a dedicated vector database with a planned migration.

Visual example

Options

Pick by scale and by what your team already operates.

Four places to keep vectors

option	examples	choose it when
Library	FAISS, hnswlib	Small or static data; research; you manage storage yourself
Extension to your database	pgvector	Up to a few million vectors; you already run PostgreSQL
Dedicated vector database	Qdrant, Milvus, Weaviate, Pinecone	Large scale, heavy filtering, many tenants
Search engine with vectors	Elasticsearch, OpenSearch	You need strong keyword search alongside vectors

Choosing by benchmark speed. A difference of 3 milliseconds between two databases is invisible beside a language model that takes 2 seconds to answer. Filtering, updates, backups and how well your team can run it matter far more.

Practise it: Design a Production RAG System

Updates, deletes and re-indexing

What it is

Documents change, so the index must too.

Adding a vector is cheap in HNSW.
Deleting is usually a soft delete: the vector is marked as removed and skipped in results, and its space is reclaimed later by a background clean-up.
Updating is a delete plus an add.

A full re-index is needed when the embedding model or chunking changes.

Why it matters

Two production concerns come from this:

Deleted content must stop appearing immediately, especially when it was removed for legal or privacy reasons, so check that deletes take effect at once and not only after clean-up.
A full re-index must not take the system down: build the new index beside the old one, test it, then switch traffic over in one step (often with an alias that points to whichever index is live).

In the real world: After a customer asks for their data to be erased, a company's deletion job removes the chunks from the vector index within minutes, and an audit query proves they no longer come back.

Re-indexing in place. Halfway through, the index holds a mix of old-model and new-model vectors that cannot be compared with each other, and search quality collapses until the job finishes.

Practise it: Design a Production RAG System

Sizing an index

What it is

A quick estimate that interviewers like to see.

Number of chunks = documents × average chunks per document.
Raw vector memory = chunks × dimensions × 4 bytes.

Add roughly a half again for the HNSW graph and metadata. Then decide whether that fits one machine's memory or needs compression or several machines.

Why it matters

It turns 'will this scale?' into arithmetic.

One million documents of ten chunks each is 10 million chunks; at 768 dimensions that is about 31 GB of raw vectors, so a single large server holds it.
A hundred times that does not fit, and the design needs quantisation, sharding (splitting the index across machines) or both.

In the real world: In a planning meeting an engineer shows that the proposed index needs about 46 GB of memory, so the team budgets for one large machine and a replica instead of a cluster.

docs            = 1_000_000
chunks_per_doc  = 10
dims            = 768

chunks    = docs * chunks_per_doc             # 10,000,000
raw_gb    = chunks * dims * 4 / 1e9           # 30.7 GB
with_hnsw = raw_gb * 1.5                      # about 46 GB with graph + metadata
int8_gb   = chunks * dims * 1 / 1e9           # 7.7 GB if quantised

Estimating from the number of documents instead of the number of chunks. The index stores chunks, and there are usually ten to a hundred times more of them.