Chapter 6: Billion Scale

Time: 40 minutes. Cost: $0. This lab reuses the shared dataset from Chapter 4 and makes no API calls.

The short version

• A billion embeddings take about 3 terabytes of memory as they come out of the model. Big search systems shrink each vector, keep most of the data on disk, or both.
• Shrinking works far better than you might expect if you rescore: search the small copies for extra candidates, then check only those against the full vectors.
• Try the cheapest fix first. Storing half the digits halved memory in the lab with no measurable loss.

Here is the number that decides your hardware bill. One vector from nomic-embed-text is 768 numbers. Each number is a 4-byte float. That is 3,072 bytes. Multiply by a billion and you need 3,072 GB, about 3 terabytes, just to hold the vectors, before a single HNSW link and before a second copy for reliability. With a 1,536-dimension model, double it.

Machines with that much memory exist. They are rare and expensive. So everyone who searches billions of vectors ends up pulling one of two levers, usually both: make each vector smaller, and stop keeping all of them in memory. This chapter measures both.

The memory math

The lab starts with a calculator. Change CALC_COUNT or CALC_DIMENSIONS in the script and it redoes the math for your case:

PART 1: 1,000,000,000 vectors with 768 dimensions
  stored as                          bytes each     total
  float32 (what you have now)             3,072  3,072 GB
  float32 + HNSW links (M=32)             3,344  3,344 GB
  float16                                 1,536  1,536 GB
  int8 (scalar quantization)                768    768 GB
  product quantization, 96 parts             96     96 GB
  binary (1 bit per dimension)               96     96 GB

The HNSW links come from Chapter 5's measurement, 272 bytes per vector at M=32. Next to 3,072-byte vectors, the links look small. Keep an eye on them anyway. Once the vectors shrink to 96 bytes, the links are almost three times bigger than the vectors they connect.

Every compressed row is an approximation, and approximations cost recall. The question is how much, and whether you can win it back.

Fewer digits: float16 and int8

The cheapest trick is to store each number with less precision, the way you would write a price of $19.98731 as $19.99. Nobody misses the extra digits. float16 keeps about three decimal digits instead of about seven. int8, or scalar quantization, goes further. For each of the 768 dimensions, take the smallest and largest value in the collection and map that range onto 256 whole numbers, like marking a ruler with 256 ticks and recording only the nearest tick. One byte per number instead of four.

Searching with only the compressed vectors, against the same exact top 10 as before:

method                         bytes each  smaller by  recall@10
float32 (no compression)            3,072          1x       1.00
float16                             1,536          2x       1.00
int8 (scalar)                         768          4x       0.99

Half the memory for nothing. A quarter of the memory for 1% of recall. If your index does not fit, this is where I would start, because it is close to free. pgvector has a half-precision halfvec type for exactly this reason. It has no int8 type, but many dedicated vector databases do.

One bit per number: binary quantization

Now the aggressive version. Imagine describing people only with yes-or-no answers: taller than average? Older than average? Lives north of the river? Two people are similar if they gave the same answers to most questions.

Binary quantization does that to vectors. Keep only one fact about each number: is it above or below the average for its dimension? That is one bit. 768 dimensions become 96 bytes, 32 times smaller. Comparing two codes means counting the answers that differ, called the Hamming distance, which processors do extremely fast.

The lab compares bits against the average, not against zero, for the reason Chapter 4 found: these embeddings all lean one way, so against zero most bits would come out the same for every paragraph.

binary (1 bit per dimension)           96         32x       0.56

On its own, binary search finds just over half of the true top 10. That sounds bad. It is less bad than it sounds, and the reason is the most useful idea in this chapter.

Search small, then rescore

Think of choosing 10 photos for an album out of thousands. You scroll through the small thumbnails and pick 100 that look promising, then open only those 100 at full size to choose the final 10. Thumbnails are bad at telling two similar shots apart and good at ruling out everything else.

A compressed vector works the same way. It is good at finding the right neighborhood and bad at the exact order inside it. The true 10th result is probably in binary's top 100. It just is not in binary's top 10.

So split the search in two. Ask the compressed index for more candidates than you need, then rescore only those candidates with the full float32 vectors and keep the best 10:

method                           fetch 10   fetch 50  fetch 100
binary                               0.56       0.89       0.95
product quantization, 96             0.66       0.97       0.99

Binary goes from 0.56 to 0.95 by fetching 100 candidates and rescoring them. You searched 96-byte codes and touched only 100 full vectors per query. Vendors recommend the same pattern: Qdrant's documentation, for example, recommends using binary quantization only with rescoring turned on, and notes it works best on high-dimensional embeddings. The name you will see in settings is oversampling: how many extra candidates to fetch before rescoring.

There is a catch, and it sets up the rest of the chapter. Rescoring needs the full vectors. If they have to sit in memory anyway, you saved nothing. They need to live somewhere cheaper.

Smarter codes: product quantization

Before getting to "somewhere cheaper," look at the second row of that table. Same 96 bytes as binary, and better recall at every fetch size. That is product quantization (PQ), from the same research that paired compression with the inverted file in Chapter 4.

Think of a paint store's color fan deck. Instead of writing down the exact mix of a color, you write the number of the closest swatch. A deck of 256 well-chosen swatches covers most colors people want.

PQ does that for pieces of a vector. Cut each 768-number vector into 96 pieces of 8 numbers. For piece position 1, run k-means on all 18,896 first pieces and keep 256 typical pieces, a codebook. Do the same for position 2, and so on. Now store each piece as the number, 0 to 255, of its closest typical piece. That is one byte per piece and 96 bytes per vector. The codebook is the fan deck, built from your own data so the swatches sit where your vectors actually are.

Search does not even rebuild the vectors. The query stays at full precision. For each of the 96 positions, score the query's piece against all 256 typical pieces once. That gives a small lookup table. A paragraph's score is then just 96 table lookups added together.

Why does it beat binary at the same size? Binary's cut points are fixed: above or below average. PQ's codebooks are learned from your data, the same reason IVF beat LSH in Chapter 4. The price is training. The two quantizers in the lab took about 20 seconds to train, and at a billion vectors you train on a sample.

Push it further and it breaks down. With 48 pieces of 16 numbers, 64 times smaller:

product quantization, 48 parts         48         64x       0.49

There is also a different way to shrink vectors that does not touch the numbers at all: keep fewer of them. Matryoshka representation learning, named after Russian nesting dolls, trains a model so the first few hundred dimensions still work on their own. OpenAI's text-embedding-3 models accept a dimensions setting for this. If your model supports it, it stacks with everything above.

DiskANN: a billion vectors on one machine

Now the second lever: stop keeping everything in memory.

Think of a big library with a card catalog. The cards are small, so you can flip through thousands of them at the desk. The books are in the stacks, and every trip to fetch one is slow. A good researcher uses the cards to decide which few books are worth the trip.

That is the design of DiskANN, from a team that included researchers at Microsoft Research India. On a billion-point benchmark dataset, on a single machine with 64 GB of RAM and an SSD, it reported more than 5,000 queries per second with under 3 milliseconds of mean latency, while finding the true nearest neighbor at least 95% of the time.

Sixty-four gigabytes, for a billion vectors. Here is how the pieces from this chapter fit together:

PQ codes for every vector stay in memory, and they are what steer the walk. The graph and the full vectors live on the SSD, stored side by side, so each hop is one read that brings back both the node's links and its full vector. The full vectors read along the way are then used for rescoring. It is search small, rescore with full vectors, with the full vectors on a disk.

The graph is not HNSW. DiskANN builds its own, called Vamana, with no layers. Every hop is an SSD read, so the graph is tuned to reach the answer in as few hops as possible, keeping some longer links that let a walk cover more ground per read.

The idea spread from there. The code is open source, follow-up work added inserts, deletes, and filters, Azure Cosmos DB uses it for its vector index, and the pgvectorscale extension for PostgreSQL has an index inspired by it.

Where this came from: DiskANN and what followed

Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri published DiskANN at NeurIPS in 2019. The code is open source on Microsoft's GitHub.

Follow-up papers added FreshDiskANN in 2021 to support inserts and deletes, and Filtered-DiskANN in 2023 for filters. Azure Cosmos DB for NoSQL made its DiskANN-based vector index generally available in November 2024. Timescale's pgvectorscale extension for PostgreSQL, announced in June 2024, has an index called StreamingDiskANN, which it describes as inspired by DiskANN rather than a copy of it.

Product quantization comes from a 2011 paper by Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Matryoshka representation learning is from Aditya Kusupati and colleagues in 2022. pgvector added halfvec in version 0.7.0, in April 2024.

The lab builds this storage split in miniature. It writes the full float32 vectors to a plain file, keeps only PQ codes in memory, scores the codes, and then reads back just 50 full vectors per question to rescore. Brute force over the codes stands in for the Vamana walk.

PART 4: product-quantized codes in memory, full vectors on disk, fetch 50
  In memory: 2.6 MB of codes and codebooks (the full vectors take 58 MB)
  On disk:   58 MB in vectors_on_disk.f32
  Read from disk per question: 50 vectors, 154 KB
  recall@10: 0.97

A 22-times smaller memory footprint, 154 KB read per question, and 0.97 recall. One honest caveat: a 58 MB file is small enough that your operating system will quietly keep it in memory, so this lab does not test SSD speed. It shows how little each query needs to read, which is the part that scales.

How I would choose

Here is the order I would try things in, cheapest first. At each step, measure recall against brute-force ground truth on a sample of your own queries, the way these labs do.

1. It fits in memory as float32 with room to spare. Use HNSW and stop. Compression has a cost in recall and complexity, and you do not need it.
2. It almost fits. Switch to float16 or int8. In this lab that cost at most 1% recall for 2 to 4 times less memory.
3. It does not come close. Use binary or product quantization with rescoring, and tune the oversampling until recall is where you need it.
4. It is billions of vectors, or memory is your biggest cost. Look at a DiskANN-style index that keeps codes in memory and full vectors on SSD.

A useful sanity check before any of it: if you can use a smaller embedding, or fewer dimensions, without hurting your search quality, every number in the calculator shrinks with it.

Hands-on lab: compress, rescore, and split

You will run the memory calculator, compress the 18,896 paragraph vectors four ways and measure recall for each, rescore compressed results with full vectors, and build the codes-in-memory, vectors-on-disk split.

Full instructions: download the Vector Databases labs ZIP. If you have not built the shared dataset yet, follow labs/vector-databases/dataset/README.md first. Then open labs/vector-databases/06-billion-scale and follow its README.

The output is the tables in this chapter. The lab runs for about a minute, mostly training the product quantizers.

Checkpoint

Binary quantization alone found 56% of the true top 10, but fetching 100 candidates and rescoring reached 95%. Why does rescoring recover so much?

Binary codes are good at finding the right neighborhood and poor at ordering within it. Most of the true top 10 are somewhere in binary's top 100, just not in its top 10. Rescoring those 100 with the full float32 vectors puts them back in the right order.

You have 50 million vectors with 1,536 dimensions. How much memory do they take as float32, int8, and binary?

float32: 50 million × 1,536 × 4 bytes = about 307 GB. int8: one byte per number, about 77 GB. Binary: one bit per number, 1,536 ÷ 8 = 192 bytes each, about 9.6 GB. Add graph links on top of each.

In DiskANN, what stays in memory, what goes on the SSD, and why that split?

PQ codes for every vector stay in memory, because they are small and the walk scores them at every hop. The graph links and full vectors go on the SSD, stored together so one read per hop returns both. The full vectors read during the walk are used to rescore the final results.

Check Your Knowledge

Click to start the quiz

1. Your HNSW index is about 30% too big for the server's memory, and you need a fix this week with as little risk to search quality as possible. Based on the lab, what would you try first?

Binary quantization, because it is 32 times smallerProduct quantization with 48 parts, because it is 64 times smallerDelete the oldest 30% of the vectorsStore the vectors as float16: half the memory, and recall stayed at 1.00 in the lab

2. Your product-quantized index uses 96 parts per vector. To halve memory again, a teammate proposes 48 parts. Based on the lab, what should you expect?

The same recall, because the codebooks still hold 256 typical pieces per positionRecall without rescoring drops from 0.66 to 0.49, because each one-byte code now has to describe 16 numbers instead of 8, so plan on fetching and rescoring more candidatesHigher recall, because fewer pieces mean fewer lookup-table errors to add upAn error, because product quantization requires pieces of exactly 8 numbers

3. Binary quantization and product quantization with 96 parts both store 96 bytes per vector. Why did PQ get higher recall in the lab?

PQ learns its codebooks from the data with k-means, while binary uses a fixed rule, above or below the average, for every dimensionPQ keeps the full vectors as a backupPQ uses more bytes per vector than binaryBinary quantization only works on images, not text

4. You compress a billion 768-dimension vectors to 96-byte PQ codes but keep an HNSW graph with M=32 in memory. What now takes the most memory?

The PQ codes, because there is one per vectorThe codebooks, because there is one per piece positionThe graph links: about 272 bytes per vector against 96 bytes of codes, roughly 272 GB against 96 GBNothing changes, because links are stored on disk by default

What's next

So far, every index in this track has been a library: you load vectors, build an index, and query it from Python. A real application also needs to add and delete documents while people are searching, filter by date or customer, survive a restart, and back everything up. Chapter 7 moves from library to database. You will run pgvector in Docker, create the HNSW index from Chapter 5 with one SQL statement, and see how filters interact with approximate search.