How vector databases work: indexing and compression

Meera has a new idea, and it is a big one.

Crumb has taken orders over WhatsApp for five years. That is 3.2 million messages: orders, complaints, compliments, questions about eggless cakes, photos of birthday cakes with the wrong name iced on them. “Everything our customers have ever told us is in there,” she says. “I want the team to be able to search it the way you made the menu searchable. ‘Complaints about packaging at the Baner store in 2023.’ ‘Every time someone asked for a sugar-free Diwali hamper.’ Can you do it?”

Arjun has done this before, with 120 menu items and 3,100 tickets. He says yes before he has done the arithmetic.

The night Arjun’s laptop ran out of memory

Arjun’s plan is the one that worked before: embed every message, keep the vectors in a NumPy array, and for each search, compare the query with every single vector. He starts with OpenAI’s text-embedding-3-small, which gives 1,536 numbers per text.

The embedding finishes overnight. Loading the vectors does not. His script dies with MemoryError. He does the sum he should have done first:

$$3,200,000\times 1,536\times 4\text{ bytes}\approx 19.7\text{ GB}$$

Each number is a 4-byte float (a decimal number), and his laptop has 16 GB of memory in total.

So he switches to the smaller local model, all-MiniLM-L6-v2, with 384 numbers per text. Now the array is about 4.9 GB, and it loads. He times one search:

import time
import numpy as np

vecs = np.load("whatsapp_384.npy")            # shape (3_200_000, 384), all length 1
q = embed(["packaging was damaged, box crushed"])[0]

start = time.perf_counter()
scores = vecs @ q                             # 3.2 million dot products
top10 = np.argpartition(-scores, 10)[:10]
print(f"{(time.perf_counter() - start) * 1000:.0f} ms")

240 ms

A quarter of a second. That sounds acceptable, until Priya asks how many searches they expect. The support team of eight will use it all day, and Meera wants the same search behind the website’s help page. At peak, maybe 40 searches a second. At 240 ms each, one laptop processor handles about 4.

“Comparing the query with every vector is called a flat search, or brute force,” Priya says. “It is exact. It is also hopeless past a few million. You need to stop reading every shelf in the library.”

How a library finds a book

Priya draws a library. “Suppose you want a book about sourdough. Option one: walk every shelf and read every spine. That’s your flat search. What do real libraries do?”

“They have sections,” Arjun says. “You go to ‘Food and Drink’, then ‘Baking’.”

“Right. You only search the shelves near what you want. That’s one family of index. Now, what’s the risk?”

He thinks. “A sourdough book shelved under ‘Science’, because it’s about fermentation microbes. I’d never find it.”

“Exactly the risk. And there’s a second family. Suppose you ask a friend who knows a lot of people. She sends you to someone who knows bread, who sends you to someone who knows sourdough, who hands you the book. A few hops instead of thousands of shelves.”

“And the memory problem?”

“Instead of storing a full description of every book, store a short code. ‘Shelf 14, section 3.’ You lose a little detail and save a lot of space.”

She writes three words on the board: sections, friends of friends, short codes. “That’s an IVF index, an HNSW index, and quantisation. Every vector database you’ll ever use is built from some mix of those three ideas.”

Following one query through a sectioned index

Trace one query through the “sections” idea with numbers small enough to check by hand. Twelve vectors with two dimensions each, measured with ordinary straight-line distance.

Step 1: build the sections, once. An algorithm called k-means groups the twelve points into three clusters and records each cluster’s centre point, its centroid.

Cluster	Points	Centroid
A	(0.8, 1.2), (1.3, 0.9), (1.0, 0.6), (0.6, 0.9)	(0.93, 0.90)
B	(4.6, 1.3), (5.4, 0.8), (5.0, 1.5), (3.4, 1.0)	(4.60, 1.15)
C	(2.8, 3.6), (3.3, 4.2), (2.5, 4.4), (3.6, 3.7)	(3.05, 3.98)

Each point is stored in the list belonging to its cluster. This is an inverted file index, or IVF: instead of one long list of vectors, you have one short list per cluster.

Step 2: a query arrives. $q=(2.5,1.4)$.

Step 3: compare the query with the centroids only. Three comparisons instead of twelve:

• To A: $\sqrt{(2.5-0.93{)}^2+(1.4-0.90{)}^2}=\sqrt{2.46+0.25}\approx 1.65$
• To B: $\sqrt{(2.5-4.60{)}^2+(1.4-1.15{)}^2}=\sqrt{4.41+0.06}\approx 2.11$
• To C: $\sqrt{(2.5-3.05{)}^2+(1.4-3.98{)}^2}=\sqrt{0.30+6.66}\approx 2.63$

Cluster A’s centre is closest.

Step 4: search inside the closest cluster. The setting that says how many clusters to open is called nprobe. With nprobe = 1, we search only cluster A’s four points. The nearest is $(1.3,0.9)$, at a distance of $\sqrt{1.44+0.25}=1.30$.

Total work: 3 centroid comparisons plus 4 point comparisons, 7 instead of 12.

Step 5: check against the truth. The real nearest point is $(3.4,1.0)$, at $\sqrt{0.81+0.16}\approx 0.99$. It sits in cluster B, near the border, like the sourdough book shelved under Science. The index missed it, and it gave no error. It returned a perfectly reasonable-looking answer that was not the best one.

Step 6: open more sections. With nprobe = 2, we search clusters A and B: 3 + 8 = 11 comparisons. Now we find $(3.4,1.0)$. Correct, but nearly as much work as searching everything.

That is the trade-off of every fast index, in miniature. At Crumb’s scale it looks like this: split 3.2 million vectors into 4,000 clusters of about 800 each. With nprobe = 16, a query makes 4,000 centroid comparisons plus about 12,800 vector comparisons: around 17,000 instead of 3.2 million, roughly 190 times less work. And sometimes, the best match sits a little way over a border you did not open.

Show the answer

A flat search with extra steps. You open every cluster, so you compare the query with every vector (plus all the centroids). The result is exact, and slower than plain brute force. nprobe is a dial between “fast and occasionally wrong” and “exact and slow”, and it can be changed per query without rebuilding the index.

Measuring “occasionally wrong”: recall

You need a number for how often an index misses. That number is recall at k: run the same query through an exact flat search and through the fast index, and see what share of the true top k the fast index found.

If the exact top 10 and the index’s top 10 share 9 items, recall at 10 is 0.9. Average it over a few hundred queries and you have your index’s recall.

Fast indexes are called approximate nearest neighbour (ANN) indexes, because they trade a little recall for a lot of speed. Most production systems tune for recall around 0.95 to 0.99. For finding similar customer complaints, missing the 10th-best match occasionally does not matter. For other jobs it might, and only you can decide that.

Friends of friends: HNSW

The second idea from Priya’s whiteboard is the one most vector databases use by default. HNSW stands for hierarchical navigable small world, which is a mouthful for “a graph with motorways”.

Picture Pune’s roads. To get from Hinjewadi to a particular lane in Camp, you do not drive down every street. You take the motorway to the right area, switch to main roads, then to local lanes. HNSW builds the same thing for vectors.

• The bottom layer contains every vector. Each one is linked to a handful of its nearest neighbours, like houses connected by lanes.
• Each layer above contains a random, smaller sample of vectors with longer links, like main roads, then motorways. The top layer might hold only a few dozen points.

To search, you start at an entry point in the top layer and repeatedly hop to whichever linked neighbour is closer to the query. When no neighbour is closer, you drop down a layer and keep hopping. On the bottom layer, you explore a little more carefully and keep a shortlist of the best points you have seen.

Three settings control it:

• M: how many links each vector keeps. More links mean better recall and more memory.
• ef_construction: how hard the builder searches for good links when inserting each vector. Higher means a better graph and slower building.
• ef_search (often shortened to ef): the size of the shortlist kept while searching. This is HNSW’s nprobe: raise it for recall, lower it for speed, per query.

HNSW is fast and accurate, which is why it is the default in Chroma, pgvector, Milvus and many others. Its cost is memory. It keeps the full vectors plus the links: with M = 16, roughly 32 links per vector on the bottom layer at 4 bytes each, which adds about 128 bytes per vector on top of the vector itself. And because the graph is designed to be walked in memory, the whole index usually needs to fit in memory.

Short codes: compressing vectors

That still leaves Arjun’s first problem: 19.7 GB of vectors on a 16 GB machine. The answer is quantisation: storing each vector in fewer bytes, accepting slightly blurrier numbers.

Scalar quantisation: fewer bytes per number

Each number in a vector is a 4-byte float, but embedding numbers mostly sit in a narrow range, say between −0.2 and 0.2. Divide that range into 256 even steps and store each number as a single byte, the step it falls on.

Take the number 0.0734 in a dimension whose range is −0.2 to 0.2:

• Its position in the range: $(0.0734+0.2)/0.4=0.6835$.
• Times 255 steps: $0.6835\times 255=174.3$, so store 174: one byte.
• To read it back: $174/255\times 0.4-0.2=0.0729$. The error is 0.0005.

Every number shrinks from 4 bytes to 1. Four times smaller. Similarity scores shift very slightly, and rankings barely change. This is scalar quantisation, often called SQ8 or int8.

Product quantisation: one byte per chunk

Product quantisation (PQ) goes further. Take a vector, cut it into equal pieces, and replace each piece with the ID of the nearest entry in a small, learned list of typical pieces, called a codebook.

A tiny example with a 4-number vector, $v=(0.12,-0.40,0.33,0.05)$, cut into two halves:

Piece	Values	Codebook entries (learned beforehand)	Nearest
First half	(0.12, −0.40)	0: (0.1, −0.4), 1: (−0.3, 0.2), 2: (0.5, 0.1), 3: (0, 0)	entry 0, distance 0.02
Second half	(0.33, 0.05)	0: (−0.2, −0.3), 1: (0, 0.4), 2: (0.3, 0.1), 3: (0.4, −0.2)	entry 2, distance 0.06

The vector is stored as the code (0, 2). When needed, it is rebuilt as $(0.1,-0.4,0.3,0.1)$, close to the original. Four floats (16 bytes) became two small integers.

At real scale, a 1,536-number vector is typically cut into 96 pieces of 16 numbers each, with a codebook of 256 entries per piece. Each piece becomes one byte. 6,144 bytes become 96 bytes: 64 times smaller. The price is precision: distances computed from codes are approximate, so recall drops unless you take a careful second look at the best candidates.

There is also binary quantisation, which keeps only whether each number is positive or negative: one bit per number, 32 times smaller. It is crude, but surprisingly usable as a first pass for some models.

What that means for Crumb

For 3.2 million vectors from text-embedding-3-small:

Storage	Bytes per vector	Total
Full floats	6,144	about 19.7 GB
Scalar quantisation (1 byte per number)	1,536	about 4.9 GB
Binary (1 bit per number)	192	about 614 MB
Product quantisation (96 pieces)	96	about 307 MB

Show the answer

Compressed distances are approximate, so the ordering among close candidates is a bit noisy: the true 3rd-best might be ranked 14th. Searching compressed codes is cheap enough to find a good shortlist. Re-scoring only that shortlist with exact vectors is cheap too (100 comparisons, not millions) and puts the order right. You get most of the memory saving and most of the accuracy. The full vectors can live on disk, since only a few are read per query. This pattern is called rescoring or reranking with full precision.

Opening the hood: what a vector database actually is

Indexes and compression are the clever core. A vector database wraps them in everything you need to use them in production:

• Storage. Vectors, plus the original text or an ID pointing to it, plus metadata: structured fields such as store, date, customer ID or language.
• An index. Flat, IVF, HNSW or a mix, often with quantisation, built and maintained as data changes.
• CRUD. Create, read, update and delete records by ID, without rebuilding everything. Upsert means “insert, or replace if this ID already exists”.
• Filtered search. “Nearest to this query, where store = Baner and year = 2023”. Combining filters with an ANN index is harder than it sounds: if the filter removes most vectors, a graph walk can run out of eligible neighbours.
• Persistence and scale. Saving to disk safely, recovering after a crash, splitting data across machines.

How a record is constructed, in most systems: your write lands in a log first (so it survives a crash), then in a small in-memory buffer that is searched exactly. Every so often, the buffer is sealed into a segment with its own index. Queries search all segments and merge the results. Deletes are usually recorded as markers, called tombstones, and cleaned up later. You do not need to manage any of this, but it explains why freshly written data is searchable immediately and why heavy delete workloads can slow things down.

The experiment: recall against speed

Theory is cheap. Arjun runs the trade-off on real numbers using FAISS, an open-source library from Meta that contains every index in this lesson (uv add faiss-cpu numpy). To keep it runnable on any laptop, the code builds 200,000 clustered fake vectors. Swap in your real embeddings if you have them.

import time
import faiss
import numpy as np

rng = np.random.default_rng(0)
d, n = 384, 200_000
centres = rng.normal(size=(1_000, d))                       # 1,000 "topics"
xb = centres[rng.integers(0, 1_000, n)] + 0.6 * rng.normal(size=(n, d))
xb = (xb / np.linalg.norm(xb, axis=1, keepdims=True)).astype("float32")
xq = xb[rng.integers(0, n, 200)] + 0.05 * rng.normal(size=(200, d)).astype("float32")
xq = (xq / np.linalg.norm(xq, axis=1, keepdims=True)).astype("float32")

def timed(index, k=10):
    start = time.perf_counter()
    _, ids = index.search(xq, k)
    return ids, (time.perf_counter() - start) * 1000 / len(xq)   # ms per query

flat = faiss.IndexFlatIP(d)              # exact; inner product = cosine on unit vectors
flat.add(xb)
truth, flat_ms = timed(flat)

def recall(ids):
    return np.mean([len(set(a) & set(b)) / 10 for a, b in zip(ids, truth)])

print(f"flat           recall 1.000  {flat_ms:.2f} ms")

Now an IVF index and an HNSW index, each tried at several settings:

quantiser = faiss.IndexFlatIP(d)
ivf = faiss.IndexIVFFlat(quantiser, d, 1_000, faiss.METRIC_INNER_PRODUCT)
ivf.train(xb)                            # k-means: learn 1,000 centroids
ivf.add(xb)
for nprobe in (1, 4, 16, 64):
    ivf.nprobe = nprobe
    ids, ms = timed(ivf)
    print(f"ivf nprobe={nprobe:<3} recall {recall(ids):.3f}  {ms:.2f} ms")

hnsw = faiss.IndexHNSWFlat(d, 32, faiss.METRIC_INNER_PRODUCT)   # M = 32 links
hnsw.add(xb)
for ef in (16, 64, 256):
    hnsw.hnsw.efSearch = ef
    ids, ms = timed(hnsw)
    print(f"hnsw ef={ef:<4}   recall {recall(ids):.3f}  {ms:.2f} ms")

On Arjun’s laptop the output looks like this. Your numbers will differ, but the shape will not:

flat           recall 1.000  14.80 ms
ivf nprobe=1   recall 0.612  0.09 ms
ivf nprobe=4   recall 0.874  0.25 ms
ivf nprobe=16  recall 0.978  0.88 ms
ivf nprobe=64  recall 0.998  3.40 ms
hnsw ef=16     recall 0.851  0.11 ms
hnsw ef=64     recall 0.972  0.30 ms
hnsw ef=256    recall 0.996  1.05 ms

Read it as a menu of trade-offs. nprobe=16 gives 97.8% recall at about one-seventeenth of the flat search time. HNSW reaches similar recall faster at this size. At nprobe=1, four in ten true neighbours are missed, and nothing in the output warns you. Only the comparison with the flat search reveals it.

FAISS’s core classes (IndexFlatIP, IndexIVFFlat, IndexHNSWFlat) have been stable for years, but library APIs change quickly. If a name has moved, check the FAISS documentation.

Where it breaks

Arjun builds an HNSW index over the WhatsApp messages with a low ef_search to make it fast, and demos it. Searching for “cake arrived melted” returns good results. Sunita then searches for something she knows is there, a very specific complaint from a customer in Aundh about a melted ice-cream cake in May 2023. It is not in the top 10. Flat search finds it at position 3.

Other things experienced engineers watch for:

• Filtering that starves the index. “Nearest to this, but only Aundh, only May 2023” may leave very few eligible vectors. Some indexes then return fewer than k results or miss good ones. Databases handle this differently, and it is worth testing with your real filters.
• Memory that grows quietly. HNSW keeps vectors and links in memory. Budget for vectors plus roughly 100 to 200 bytes of links per vector, plus headroom.
• Unrepresentative training. IVF and PQ learn centroids and codebooks from your data. Train them on last month’s menu queries, then load five years of WhatsApp chatter, and the clusters fit badly.
• Heavy updates and deletes. Graph indexes are built incrementally; lots of deletes leave tombstones and can degrade quality until the database compacts or rebuilds.
• Model changes. New embedding model means every vector and every index is rebuilt. Plan for it.
• Metric mismatch. Building an index with Euclidean distance on vectors you expected to compare by cosine, without normalising them, quietly changes the ranking.

Arjun explains it to Meera

Meera asks the question she always asks. “In plain words. What changes, and what does it cost?”

“Searching 3.2 million messages the simple way means reading every one, every time,” Arjun says. “A quarter of a second per search, and we need forty a second. So we organise them first, like a library with sections, or like a road network with motorways. A search only looks at a small part of the data. It’s about fifty times faster.”

“What’s the catch?”

“Occasionally it misses something. We measured it: with our settings it finds about 97 or 98 out of every 100 messages that a full search would find. For searching complaints, that’s fine. We test it regularly so we know if it gets worse.”

“And the memory problem?”

“We store a compressed version of each message’s numbers. Like keeping a postcode instead of a full address. Twenty gigabytes becomes five, or even under one, and we use the full numbers only to double-check the final shortlist.”

“Do we have to build all of this?”

Priya laughs. “No. That’s what vector databases are. They’ve built the sections, the motorways and the compression for us. Arjun’s job is choosing one and setting the dials. We’ll start with the easiest one to run on a laptop.”

Try it yourself

1. Run the FAISS experiment as written.
2. Change the IVF index to use 200 clusters instead of 1,000, retrain, and rerun the nprobe loop.
3. Add a PQ index and compare its recall and memory: faiss.IndexIVFPQ(quantiser, d, 1_000, 48, 8) (48 pieces of 8 dimensions, 8 bits per code).

Expected result: with fewer, larger clusters, each nprobe setting gives higher recall but slower queries. The PQ index gives noticeably lower recall at the same nprobe than IndexIVFFlat, in exchange for storing each vector in 48 bytes instead of 1,536.

Show why fewer clusters behave that way

200 clusters of 200,000 vectors means about 1,000 vectors per cluster. Opening one cluster now covers more ground (higher recall), but you compare against 1,000 vectors instead of 200 (slower). The number of clusters and nprobe together decide what fraction of the data you scan. A common starting point is a number of clusters around the square root of the number of vectors, then tune nprobe by measuring recall.

Common mistakes

• Never measuring recall. Without a flat-search comparison, you cannot tell a fast index from a broken one.
• Copying index settings from a blog post. Good nprobe, ef_search and M depend on your data size, dimensions and recall target. Measure.
• Using an ANN index for 10,000 vectors. Flat search over tens of thousands of vectors takes a few milliseconds. An index adds complexity for no gain.
• Forgetting memory for the index itself. HNSW links and IVF centroids cost memory on top of the vectors.
• Compressing without rescoring. PQ alone can drop recall noticeably; re-score a shortlist with full vectors when accuracy matters.

Recap

• Flat (brute-force) search is exact but checks every vector; it stops scaling somewhere past a few million.
• IVF groups vectors into clusters and searches only the nearest few (nprobe); HNSW walks a layered graph of neighbours (M, ef_search).
• Approximate indexes trade recall for speed, and recall at k (the share of true top-k results found) is the number that tells you how much you traded.
• Scalar quantisation stores each number in one byte (4 times smaller); product quantisation stores chunks as codebook IDs (often 64 times smaller); rescoring with full vectors restores accuracy.
• A vector database adds storage, metadata, CRUD, filtering and persistence around these indexes, and its failures are silent, so measure.

That evening, Priya sends Arjun a one-line message: “Tomorrow: Chroma. A whole vector database that installs with one command and runs on your laptop. Bring the store handbook.”

Go deeper

• FAISS on GitHub
• Milvus documentation (its index explanations cover IVF, HNSW and quantisation clearly)
• Pinecone documentation
• pgvector on GitHub (the README explains HNSW and IVFFlat settings)