Latency in a modern data center spans eight orders of magnitude, from a nanosecond on-chip to a hundred milliseconds across the planet.
Latency Tiers
One data center: seven orders of magnitude of latency
Figure: One data center: seven orders of magnitude of latency
Seven latency tiers on one axis, ordered fastest to slowest left to right: L1 cache 1 ns on-chip, RAM 100 ns on-board, SSD 100 microseconds same rack, network within the data center 500 microseconds an aisle away, spinning disk 10 milliseconds same rack, cross-region 50 milliseconds a continent away, cross-continent 100 milliseconds the other side of Earth. The span from end to end is 100 million times. An algorithm that reads from the wrong tier pays up to 10,000,000 times more. Color key: orange is a latency tier, grey is the fast-to-slow axis.
Seven tiers in one data center, fastest to slowest, from L1 cache at 1 ns to a cross-continent round trip at 100 ms. End to end is 100,000,000x.
A system is components chosen to work with each other.
What Is a System?
Pick one from each bin
Figure: Pick one from each bin
Three bins of parts, then three cars built from them. Engines: E1 a motorbike good for 130 mph at five thousand dollars, E2 a turbo four good for 150 at twelve thousand, E3 a jet good for 400 at two million. Chassis: C1 Lego good for 2 mph at fifty dollars, C2 steel good for 150 at ten thousand, C3 carbon good for 250 at five million. Wheels: W1 road tyres good for 150 at six hundred, W2 sport at 200 for two thousand, W3 slicks at 250 for fifty thousand. The builds: E3 plus C1 plus W3 is mismatched and does 2 mph for two million and fifty thousand dollars; E3 plus C3 plus W3 is oversized and does 250 mph for seven million; E2 plus C2 plus W1 is right-sized and does 150 mph for twenty-two thousand six hundred.
Engines, 3 parts. Each lists the top speed it supports and its cost. The goal is a car that will do 150 mph on a public road.
Engine
E1
Motorbike
130 mph
$5,000
E2
Turbo four
150 mph
$12,000
E3
Jet
400 mph
$2M
Chassis, 3 parts, drawn beside the engines on the same rows.
Chassis
C1
Lego
2 mph
$50
C2
Steel
150 mph
$10,000
C3
Carbon
250 mph
$5M
Wheels, 3 parts, drawn beside the chassis on the same rows.
Wheels
W1
Road
150 mph
$600
W2
Sport
200 mph
$2,000
W3
Slick
250 mph
$50,000
What you can build from them, 3 builds. A build runs at its slowest part and costs all of them: the mismatched build is held to 2 mph by its Lego chassis, the oversized one overshoots the 150 mph goal by 100 mph for $7.05M, and the right-sized one hits the goal exactly for $22,600. Read each column down: the parts, then the speed, then the cost.
Mismatched
Oversized
Right-sized
E3 + C1 + W3
E3 + C3 + W3
E2 + C2 + W1
2 mph
250 mph
150 mph
$2.05M · C1 is the bottleneck
$7.05M · 100 mph past the goal
$22,600 · hits the goal exactly
The goal is a car that will do 150 mph on a road. Pick one row from each bin; the car then runs at its slowest part and costs every part in it. E3+C1+W3 spends $2.05M and travels at walking pace: C1 is the bottleneck. E3+C3+W3 has no bottleneck, but it is oversized: it runs 100 mph past the goal, at $7.05M. E2+C2+W1 hits 150 on all three parts at once for $22,600.
The CPU works through cache and RAM, never the SSD, and data moves one page at a time
Figure: The CPU works through cache and RAM, never the SSD, and data moves one page at a time
Three tiers left to right. The CPU on the left works only out of its registers and L1, L2, L3 cache, which the hardware fills from RAM in 64-byte cache lines, in nanoseconds. RAM in the middle holds 16 GB divided by 64 MB, which is 256 fixed-size page slots, drawn as a small grid. The SSD on the right holds 128 GB divided by 64 MB, which is 2048 pages, drawn as a larger grid of the same-size cells; one is highlighted orange as it is paged into a free RAM slot, labelled one page, 64 MB, one IO, transfer-bound at about 5 GB per second so about 13 milliseconds. When RAM fills, a page is evicted and the next is paged in, so all 2048 SSD pages stream through the 256 RAM slots one page at a time. Color key: orange is a page in motion (the unit of one IO), grey is structure.
The CPU computes only out of its registers and cache; it does not operate on the SSD directly. The SSD gives RAM a 64 MB page per IO, and RAM feeds the CPU 64-byte cache lines in nanoseconds. That page costs the same whether the query wants one row or the whole block, and at ~5 GB/s a 64 MB transfer takes ~13 ms, so cost is page count. **Paging** refers to the overall steps in moving the needed subset of pages in-n-out of RAM.
Why paging matters: the speed gap scaled to human time
Figure: Why paging matters: the speed gap scaled to human time
Four storage tiers left to right, each access time rescaled as if one L1 cache hit took 1 second. L1 cache is 1 second, RAM is 1.5 minutes (100 times slower), SSD is 3 hours (another 100 times), and a hard disk is 4 months (another 1000 times). The point: a disk read feels like a season when a RAM read feels like a short pause, which is why paging keeps the working set in the fast tiers. Color key: orange is a storage tier and its human-scaled wait, grey is the slowdown factor between tiers.
Rescale latency so an L1 cache hit takes one second. RAM becomes 1.5 minutes, an SSD read becomes 3 hours, and a hard disk read becomes 4 months. Paging keeps the working set in RAM. A query that reads from disk on every page pays the hard disk or SSD cost once per page.
The IO cost formula and the symbols it uses. IO cost equals C_r times the pages read plus C_w times the pages written. C_r is the time to read one page and C_w the time to write one page, both shown in orange. P(R) is the number of pages in table R and T(R) = n is the number of rows (tuples) in R. Color key: orange marks the two per-page costs C_r and C_w.
Cost counts page I/Os, not CPU work. Cr and Cw are the time to read or write one page; P(R) is the pages in table R and T(R) = n its row count. Every algorithm's cost is Cr × pages read + Cw × pages written.
Three algorithms and their IO cost, revealed one at a time. Example 1, basic: read and write every page once, cost C_r times P(R) plus C_w times P(R). Example 2, multi-pass: read every page seven times and write three times, cost C_r times seven P(R) plus C_w times three P(R). Example 3, logarithmic: read log P(R) passes and write a tenth of the pages per row, cost C_r times log P(R) times P(R) plus C_w times 0.1 P(R) times T(R). Color key: orange is the cost formula.
Example 1 reads and writes every page once; Example 2 makes seven read passes and three write passes; Example 3 reads log P(R) passes and writes a tenth of the pages per row. The cost is the page count; the CPU work is negligible.
Notes ↗IO Cost Model: Algorithmic Complexity for Big Data
Calculating Read and Write Costs
The cost of reading one page, and of an algorithm:
Page size is 64 MB unless a problem says otherwise; units are decimal (1 MB = 1,000,000 bytes, 1 GB = 1,000,000,000 bytes). In practice a write can cost more than a read; unless a problem says otherwise, CS145 uses Cw = Cr.
Notes ↗IO Cost Model: Algorithmic Complexity for Big Data
Read 200 pages through a cache. RAM holds 90% of them. Of the pages RAM misses, 75% are on SSD and 25% on HDD. What is the total read time?
Show Solution
Figure: How a cached read works: 200 page readsHow a cached read works, for 200 page reads. Step 1: every read checks RAM first, hit or miss, 200 times 0.00064 s, 0.128 s. Step 2: 180 reads (90%) hit and are served from RAM; 20 (10%) miss and go to the next tier. Step 3: of the misses, 15 come from SSD at 0.01281 s each, 0.192 s, and 5 from HDD at 0.65 s each, 3.25 s, shown in orange. Total 3.57 s: the 5 HDD reads are 2.5% of the requests and 91% of the time.
Figure 1. Every read pays the RAM check (0.128 s); 180 stop there. The 20 misses split into 15 SSD fetches (0.192 s) and 5 HDD fetches (3.25 s), for 3.57 s in total. The 5 HDD reads are 2.5% of the requests and 91% of the time (3.25 / 3.57).
Total time: 3.57 s. The RAM check is paid on every read, and the few reads that fall to HDD dominate.
Figure: Network RAM: fetching a 64 MB page from another machineA Network RAM read of one 64 MB page. The page sits in RAM on a remote machine. You request it, the remote machine reads it from its RAM (0.00064 s), it travels back over a 10 GB/s network (0.0064 s, the orange arrow and the dominant cost), and you write it into your own RAM (0.00064 s), for 0.0077 s total, which still beats a local SSD read at 0.0128 s. Color key: orange the network hop, grey the machines and RAM.
Figure 2. A Network RAM read. The page sits in RAM on a remote machine; you request it, read it from remote RAM, send it back, and write it into your RAM. The network hop (0.0064 s) dwarfs the two RAM touches (0.00064 s each). Total 0.0077 s, still under a local SSD read (0.0128 s).
Show Solution
Network RAM
Remote read 0.00064 s + network hop 0.0064 s + local write 0.00064 s = 0.0077 s. The network hop (64 MB ÷ 10 GB/s) dominates.
Versus local storage
The single-page costs on the local devices are the same ones from Problem 2: RAM 0.00064 s, SSD 0.0128 s, HDD 0.65 s.
Ranked: Local RAM < Network RAM (0.0077 s) < Local SSD (0.0128 s) < Local HDD (0.65 s).
A hash function maps a key to a fixed-size bucket id, so you can find or insert in expected O(1) by reading the page where the bucket lives.
Integer hashing with h(x) = x % 10
Figure: Integer hashing with h(x) = x % 10
Inputs 42, 157, 1042, 89 are hashed by x mod 10 into ten buckets. 42 and 1042 both land in bucket 2, a collision (shown in orange); 157 lands in bucket 7 and 89 in bucket 9. Color key: orange is the colliding bucket in focus, grey is the other buckets.
h(x) = x % 10 maps four integers into ten buckets numbered 0 through 9. 42 and 1042 both land in bucket 2 (orange) because both end in 2, while 157 and 89 fall in distinct grey buckets. The collision is the point: an index must handle two or more keys landing in the same bucket. Chaining stores a list per bucket.
Case Study 2.1: How Uber and Google Maps index locations
Uber's H3 and Google's S2 map 2-D coordinates to 1-D cell IDs.
Why hexagons, not squares: a hexagon's neighbours are all the same distance
Figure: Why hexagons, not squares: a hexagon's neighbours are all the same distance
Two grids compared. On the left a square cell has eight neighbours at two different distances: its four edge neighbours are one cell away, its four corner neighbours are farther by a factor of root two, so the ring a radius query must read is uneven. On the right a hexagon has six neighbours, every one exactly the same distance from the centre, so the ring is even in all directions. That uniform neighbour distance is why map systems grid the world into hexagons. Color key: orange is the query cell and, for the hexagon, its single even neighbour ring; grey is the grid; dashed circles are neighbour distances.
Cell shape determines the neighbor ring. A square has eight neighbors at two distances: four edge-neighbors one cell away, four corner-neighbors farther by a factor of root two. A hexagon has six neighbors, each at the same distance from the center, which yields a symmetric ring for a radius query. Hexagons approximate a circle better than squares.
Figure: Nearby points share a cell, far points do not
The three Stanford campus buildings versus SF Mission, computed with H3. At resolution 8 (zoomed out) the three campus buildings get the identical code 8828347417fffff, one shared cell, while SF Mission, 29 miles away, gets a different code. At resolution 12 (zoomed in) the three campus codes split into three cells, differing in the fine digits at the end (orange), and SF stays different. Color key: orange is where the campus codes differ at resolution 12, black is shared.
H3 codes for three Stanford campus buildings and SF Mission. At resolution 8 the three campus buildings map to 8828347417fffff and SF Mission, 29 miles away, maps to a different cell. At resolution 12 the three campus buildings split into three cells, differing in the trailing digits (orange), and SF Mission remains in a different cell.
Figure: Geo-hashing: a location becomes a cell code
Order pins start as raw latitude and longitude. Lay H3's hexagons over the map and every pin falls in one hexagon, which has a cell code. Pins in the same hexagon, three Stanford buildings here, share one code; a far pin in San Francisco gets a different code. The hash is just which hexagon a point lands in. Color key: orange is a shared cell and the pins in it, grey is the hex grid, dark dots are orders.
H3 maps each food-delivery order's latitude and longitude to a cell ID. The system stores 10 million orders by that ID, so nearby orders share one and distant orders fall under different ones.
Geo-hashing lookup: a radius query is a bounded handful of cell reads
Figure: Geo-hashing lookup: a radius query is a bounded handful of cell reads
At a resolution where one neighboring ring covers two kilometers, the query reads the driver's cell and its six neighbors. Those seven cell identifiers may occupy seven pages. The system then checks exact distances for the candidate food delivery orders. Other radius and resolution combinations may require more rings.
At a resolution where one neighboring ring covers 2 km, the query reads the driver's cell and its six adjacent cells. Those seven cell IDs can map to seven different pages, yielding up to seven reads. The system then checks exact distances for the candidate food-delivery orders. The number of cell lookups stays constant as the table grows from ten thousand orders to ten million; a larger search radius just reads a few more rings.
Columnar compression (run-length, dictionary, delta) exploits repetition inside one column, typically shrinking on-disk size 10× thereby cutting IO by the same factor.
When to Use What?
Four columnar compression techniques at a glance
Figure: Four columnar compression techniques at a glance
Four panels side by side, one per technique. RLE turns a run like Mickey times three, Daffy times four into one value plus a count, 10 to 100 times smaller, very fast, best for sorted repeated values. Dictionary replaces low-cardinality strings with small integer codes, 5 to 20 times, fast, best for low-cardinality strings. Delta stores the difference between sorted numbers, 5 to 10 times, fast, best for sorted numbers and timestamps. Bit packing stores small integers in the minimum bits, 4 to 8 times, very fast, best for small integers and flags. In each panel the raw input is grey and the encoded result is orange. Color key: orange is the encoded result, grey is the raw input.
We can compress a column by removing repeated structure. RLE stores each run as a value plus a count (i.e., length of a run of Mickeys). Dictionary encoding maps each distinct value to a small integer code. Delta encoding stores differences between adjacent sorted numbers. Bit packing stores small integers in the minimum number of bits. The raw input is grey, the encoded result orange. Ratios run from about 4x (bit packing) to 100x (RLE on sorted data); choose based on the column's value distribution.
One user_id column of 1 million values, 4 MB raw, sorted by user_id with about 25,000 active users, shrunk in three stacked steps, drawn as a descending staircase of orange boxes whose height tracks the size. RLE collapses the sorted runs to 200 KB. Dictionary shrinks each value because 25,000 ids need only a 2-byte code, not a 4-byte int, to 100 KB. zstd is a general-purpose codec that entropy-codes the leftover byte patterns, to 50 KB. The end result is 98.75 percent smaller. Color key: orange is the column shrinking, grey is the step applied.
A 1M-row user_id column sorted by user_id with ~25,000 active users compresses by chaining encodings. RLE collapses the sorted runs (4 MB to 200 KB). Dictionary encoding then replaces ids with codes; 25,000 ids fit in a 2-byte code rather than a 4-byte int (to 100 KB). zstd entropy-codes the remaining byte patterns (to 50 KB), a 98.75% reduction. Unsorted data or high cardinality is less compressible.
A Bloom filter stores a set in a bit array and uses k hash functions to map each item to k bit positions.
Visual: How Bloom Filters Work
Bloom filter: insert alice, look up alice, look up bob
Figure: Bloom filter: insert alice, look up alice, look up bob
A 16-bit Bloom filter with k = 3 hash functions; bits 9 and 11 were set by earlier inserts. 1, INSERT "alice" hashes to bits 3, 7 and 14 and sets them. 2, LOOKUP "alice" checks bits 3, 7 and 14; all are 1, so alice is probably in the set, which could be a false positive because other items set bits too. 3, LOOKUP "bob" checks bits 3, 9 and 2; bit 2 is 0, so bob is definitely not in the set: one 0 is proof, so there are no false negatives. Color key: orange is a set bit, grey an unset bit, green is a guaranteed answer.
The 16-bit array after the insert, each index with its bit: bits 3, 7 and 14 were just set by inserting "alice", and bits 9 and 11 came from earlier inserts. Every other bit is 0. Real filters use millions of bits.
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
0
0
0
1
0
0
0
1
0
1
0
1
0
0
1
0
INSERT "alice": k = 3 hash functions, each picking a bit and setting it to 1.
INSERT "alice"
hash1("alice") % 16 = 3 → bit[3] = 1
hash2("alice") % 16 = 7 → bit[7] = 1
hash3("alice") % 16 = 14 → bit[14] = 1
LOOKUP "bob": the same 3 hashes. Bits 3 and 9 are already 1, but bit 2 is 0, and one zero is enough: "bob" is definitely not in the set. That answer is guaranteed, which is why a Bloom filter never gives a false negative.
LOOKUP "bob"
hash1("bob") % 16 = 3 → bit[3] = 1
hash2("bob") % 16 = 9 → bit[9] = 1
hash3("bob") % 16 = 2 → bit[2] = 0
A Bloom filter stores a 16-bit array and k = 3 hash functions; earlier inserts set bits 9 and 11. (1) INSERT "alice" hashes to bits 3, 7, and 14 and sets them. (2) LOOKUP "alice" checks the same three bits: all are 1, so "alice" is probably in the set. All 1s can also be a false positive, because other items set bits too. (3) LOOKUP "bob" checks bits 3, 9, and 2: bit[2] = 0 guarantees "bob" is not in the set (green). Any 0 means "definitely not in the set", so false negatives never occur. A bigger bit array lowers the false-positive rate at the cost of space; k is tuned to the array size and item count. In general, a Bloom filter checks membership in RAM before paying an expensive IO.
Case Study 2.2: How early Chrome Safe Browsing used a Bloom filter
Chrome Safe Browsing checks if a user is visiting a phishing site.
Early Chrome Safe Browsing: a local Bloom filter and a prefix check
Figure: Early Chrome Safe Browsing: a local Bloom filter and a prefix check
A worked early Safe Browsing design. A dashed boundary separates the device from Google. The device holds a 125 MB Bloom filter estimated from an 8 GB raw list, a 64-times reduction. A definite miss ends locally. A possible match sends a 32-bit hash prefix to Google, which returns the full hashes sharing that prefix so the device can finish the check.
This example starts with 100 million URLs averaging 80 bytes, or 8 GB. At 10 bits per item, a Bloom filter occupies about 125 MB, 64 times less space. A definite miss ends locally. A possible match sends a 32-bit hash prefix to Google, which returns the matching full hashes so the device can finish the check. The server receives a prefix instead of the full URL.
An ordinary hash spreads similar inputs across different buckets.
An ordinary hash scatters similar items
Figure: An ordinary hash scatters similar items
Two near-identical cat vectors feed an ordinary hash, which is built to spread inputs out, so they land in unrelated buckets, bucket 7 and bucket 3, far apart in the bucket row. A red bar states the consequence: similar inputs land in unrelated buckets, so finding similar items would have to scan every bucket. This is the problem locality-sensitive hashing fixes. Color key: orange marks the two similar items, grey the hash and buckets, red the two scattered destinations and the verdict.
An ordinary hash spreads inputs across buckets. Two near-identical vectors (cat A and cat B) land in unrelated buckets, 7 and 3. The bucket index carries no information about distance, so a similarity query still scans every bucket. Locality-sensitive hashing groups near vectors instead.
Figure: LSH: similar items hash to the same bucket
Four items become feature vectors, then k random hyperplanes turn each vector into a sign-bit code, then a bucket. Cat 1 and Cat 2 are similar so both get code 1011 and bucket 11 (orange, the focus pair); Dog gets bucket 9 and Car bucket 4 (grey). A query for items similar to Cat scans only bucket 11. Color key: orange is the similar pair in focus, grey is the other items.
Each item becomes a feature vector, an embedding, then a short LSH code, then a bucket. The two similar cats receive code 1011 and share a bucket, while the dog and car map to different buckets. A query for items like the cat reads that one bucket instead of comparing against every stored vector. Code bits come from random cuts of the space.
A space crossed by three dashed cuts. Above a cut implies 0, below implies 1, so three cuts give each point a three-bit code. The two cat photos read 111 because no cut falls between them, and share a bucket. The dog reads 011 and the car reads 110. The dog differs on cut 1, the car on cut 3. A table on the left fills in above or below for each point as every cut lands.
Which side of each cut, 4 items. Above a cut implies 0, below implies 1, so the three answers in each row spell that item's three-bit code: Cat 1 and Cat 2 both read 111, the dog reads 011 and the car reads 110. The two cats match on all three cuts and share a bucket; the dog differs on cut 1 and the car on cut 3. Equal codes go in the same bucket, and no distance is ever computed.
cut 1
cut 2
cut 3
Cat 1
below
below
below
Cat 2
below
below
below
Dog
above
below
below
Car
below
below
above
Each cut asks one yes-or-no question: above the line is 0, below is 1, and the code assembles one bit at a time. The same four items as Figure 2. The two cats end on 111 because no cut fell between them, so they share a bucket; the dog differs on cut 1 and the car on cut 3, so each lands elsewhere. Nothing measures a distance, so a nearness lookup becomes an ordinary hash-table lookup: cost O(N) drops to about O(N / 2k). Misses happen when a cut does fall between a close pair.
The cut is always one dimension less than the space
Figure: The cut is always one dimension less than the space
A cloud of 200 unit vectors in three dimensions, holding the two near-duplicate cats and the unrelated dog. Planes through the origin arrive one at a time and orange marks every vector still on Cat 1’s side of all of them. After the first plane the dog is still in Cat 1’s bucket, because one cut only halves the space; the second plane separates it, and Cat 2 stays throughout. The candidate set falls from 200 to 94, then 43, then 19. A ladder along the bottom names the same object in each dimension: in two dimensions the cut is a line, in three a plane, and in 256 a hyperplane, always one dimension less than the space it cuts.
In 2D that is a line, which is what Figure 3 drew; in 3D it is an ordinary plane, drawn here; in an embedding’s few hundred dimensions it is a hyperplane (hard to picture). Nothing else changes: above or below is still the only question. One cut is insufficient. After the first plane the dog is still in the cat’s bucket, because one cut halves the space and a coin flip put it on that side. The second ejects it, and the near-duplicate survives all three. Each plane roughly halves the candidates: 200, then 94, then 43, then 19.
Case Study 2.3: How OpenAI and Meta's FAISS Speed Up Vector Search
OpenAI's embeddings are vectors.
The problem: a distance calculation against every row
The exact scan: one query against every vector
Figure: The exact scan: one query against every vector
Exact L2 search computes one distance from the query, a 1,536-D vector, to each of N = 1,000,000 stored vectors, every one to the last. One query costs 1,000,000 L2 distances, about 1.5 billion coordinates and 6.1 GB of vector data, repeated for every query: exact search performs O(N) distance evaluations per query. Color key: orange is the query, grey the stored vectors and the scan.
Exact scan against all N vectors. At one million vectors, a query computes one million 1,536-dimensional L2 distances, covering about 1.5 billion coordinate values and 6.1 GB of vector data. In FAISS, IndexFlatL2 performs this exact search.
Notes ↗The fix: an approximate nearest-neighbour index
HNSW is built in layers
Figure: HNSW is built in layers
A hierarchical proximity graph. Layer 0 holds every point with selected nearby links. Random level assignment places fewer points in each upper layer, where links span longer distances. Dashed verticals mark the same point across layers. Color key: orange is points and graph links, grey dashed is the same point across layers.
Each vector is assigned a random height, so only a few rise to the upper layers. At the bottom, nearly all of them connect to their neighbors like local streets. The few promoted higher become the sparse freeway stops the search starts from.
Notes ↗The fix: an approximate nearest-neighbour index
HNSW search narrows candidates layer by layer
Figure: HNSW search narrows candidates layer by layer
The search starts at an upper-layer entry point, greedily moves toward the query, and descends through the layers. At layer 0, HNSW checks a handful of nearby candidates and returns the best. Color key: orange is the illustrated descent path, the grey ring is a considered neighbour, and the black dashed line is the query.
Top layers are freeways: long links jump you near the query. The bottom layer is local streets: short hops close in. It checks only a handful of candidates, so it is fast but can miss the true nearest.
Notes ↗The fix: an approximate nearest-neighbour index
Brute-force scan vs an ANN index
Figure: Brute-force scan vs an ANN index
One query over a million 1,536-D embeddings. Exact search with IndexFlatL2 compares the query to every vector: one million 1,536-D L2 distances, about 6.1 GB read, an exact answer, O(N) work per query. An ANN index (IVF or HNSW) looks at a small fraction: IVF probes a few clusters, HNSW walks a graph to the neighbourhood. It examines fewer candidates and may miss a neighbour. Color key: orange is the ANN index.
Exact search compares the query with all one million vectors. An ANN index checks only a slice of them, so it answers far faster but can skip the true closest. Check more candidates and you trade speed for accuracy.
A float32 vector index stores more precision than search needs.
A 100,000-document demo becomes a 60 GB index
The demo fit in RAM; production does not
Figure: The demo fit in RAM; production does not
The index has to sit in RAM to search fast. The raw float32 index, about 60 GB for 10 million 1,536-D vectors at 4 bytes each (about 6 KB per vector), does not fit in the machine's RAM. Quantizing, 8 to 32 times smaller, gives the same index at a few bits per number, which fits with room to spare. Color key: grey is the machine's RAM, red is float32 that does not fit, green is quantized and fits.
A full-precision embedding is big. Most have about a thousand dimensions or more. OpenAI's smaller embedding model is 1,536-D and the large one is 3,072-D. At 1,536-D float32 that is about 6 KB per vector, so 10 million vectors take ~60 GB in RAM for fast search. The large model uses double. Quantizing each coordinate to a few bits shrinks the index 8 to 32 times and brings it under the RAM limit.
Notes ↗Most of the information hides in a few directions
A random spin turns the grid, not the points
Figure: A random spin turns the grid, not the points
One panel. San Francisco, Berkeley and Stanford stay at the same coordinates in every frame while the grid behind them rotates. SF and Berkeley begin in one cell and end in different cells after a spin of 58 degrees; Stanford, much further away, is unaffected. A read-out lists the cell each city falls in.
Eight frames from 0° to 58°. The three cities sit at identical coordinates in every frame, so you can check for yourself that only the grid moved. San Francisco and Berkeley begin in one cell and end in different ones. Stanford, much further off, is untouched.
Notes ↗Most of the information hides in a few directions
Four bits buys 16 levels. Before the rotation, 5 get used.
Figure: Four bits buys 16 levels. Before the rotation, 5 get used.
256 embedding coordinates drawn as bars, beside a histogram of how many fall into each of the 16 levels a 4-bit quantiser offers. Before the rotation the coordinates are dominated by a few large ones, so only 5 of the 16 levels are ever used and one level holds most of them. After a random rotation the coordinates are evenly spread and 15 of the 16 levels are in use. Storage is 4 bits per coordinate in both cases.
The same idea at 256 dimensions. A 4-bit budget is 16 levels. Before the rotation the coordinates are so uneven that only 5 levels are ever used, which is 2.3 bits of information in the 4 bits you are paying to store. After it, 15 levels are in play at 3.9 bits. Storage is 4 bits per coordinate either way; only the useful fraction changes.
A coordinate stored today as 0.4327 uses 32 bits per number, the exact coordinate. After quantizing it is stored as 10: 2 bits, bucket 2 of 4, which decodes back to about 0.4. The distance between two vectors barely moves, because after the spin no single coordinate carries the answer. Sixteen times smaller, and no codebook to train. Color key: orange is the quantized value.
Scalar quantization of one coordinate. 0.4327 stored in 32 bits maps to a 2-bit bucket 10 and decodes to about 0.4. One coordinate is now rough, but a distance adds up hundreds of them, and the rounding errors mostly cancel out. The rotation first spreads the values evenly, so one simple quantizer fits every coordinate and every dataset, with no training. Two bits gives 16× compression, and one bit gives 32×.
Two levers for a too-big problem: partition the lookup, or shrink each item
Figure: Two levers for a too-big problem: partition the lookup, or shrink each item
Every structure here turns a big problem into a small one. Lever 1, don't scan all N: partition the lookup so a query touches one slice; exactly by hashing to one bucket (Basic Hashing), or approximately by bucketing similar items or pruning what is definitely absent (Bloom, LSH, IVF, HNSW). Lever 2, don't store all N bytes: shrink each item so the index fits; losslessly by dropping redundancy (RLE, dictionary, delta, bit-pack), or lossily by dropping precision while keeping the order (PQ, TurboQuant). Stack both and you get, for example, IVF-PQ, the vector database. Color key: orange is the lever.
Two levers for a too-big problem. Lever 1 partitions the lookup so a query examines one slice instead of all N: exactly, by hashing to a bucket; approximately, by pruning what is definitely absent (Bloom) or bucketing by similarity (LSH, IVF, HNSW) and checking only the candidates near the query. Lever 2 shrinks each item: losslessly by dropping the redundancy the data already has (only if it has structure), or lossily by dropping precision while keeping the rank order (a random rotation reframes the data so one coarse quantizer fits any of it). Each lever has an exact form and an approximate one. Real systems pull both at once: a vector database like IVF-PQ partitions the data and then compresses what is left.
Figure: How a cached read works: 200 page readsHow a cached read works, for 200 page reads. Step 1: every read checks RAM first, hit or miss, 200 times 0.00064 s, 0.128 s. Step 2: 180 reads (90%) hit and are served from RAM; 20 (10%) miss and go to the next tier. Step 3: of the misses, 15 come from SSD at 0.01281 s each, 0.192 s, and 5 from HDD at 0.65 s each, 3.25 s, shown in orange. Total 3.57 s: the 5 HDD reads are 2.5% of the requests and 91% of the time.
Figure: Network RAM: fetching a 64 MB page from another machineA Network RAM read of one 64 MB page. The page sits in RAM on a remote machine. You request it, the remote machine reads it from its RAM (0.00064 s), it travels back over a 10 GB/s network (0.0064 s, the orange arrow and the dominant cost), and you write it into your own RAM (0.00064 s), for 0.0077 s total, which still beats a local SSD read at 0.0128 s. Color key: orange the network hop, grey the machines and RAM.