# DDIA Ch. 4: the same rows cost 4× more in random order ## Concept A B-tree keeps keys sorted in fixed-size pages, so *where* a new key lands depends on its value. Feed it keys in ascending order and every insert appends to the same rightmost leaf — fast and tightly packed. Feed it the *same keys* scattered across the key space and each insert lands in a different page all over the disk — the "random writes" the book warns about. You will load 10 million rows two ways, differing only in key order, and watch the random order take **4× longer** and leave an index **31% bigger** and a third emptier. This is why LSM-trees, which only ever write sequentially, sustain higher write throughput. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 4 — *Storage and Retrieval*, §"Sequential versus random writes": > With a B-tree, if the application writes keys that are scattered all over the > key space, the resulting disk operations are also scattered randomly … Disks > generally have higher sequential write throughput than random write > throughput. The book contrasts the B-tree's scattered small writes with the LSM's large sequential ones. Here you produce the B-tree penalty and measure it. ## Prerequisites The surprise is about how a B-tree places keys on pages. These help; each line notes where it shows up. 1. **B-tree layout** — keys are held in sorted order across fixed-size pages (8 KB in Postgres); a lookup walks from the root down to a leaf. 2. **Insertion and page splits** — a new key goes into the leaf that owns its value; if that leaf is full, it *splits* into two half-full pages. Where the key lands is set by its value, not by when it arrives. 3. **Sequential vs. random insertion** — always-increasing keys land in the current rightmost leaf (append); scattered keys land in leaves all over the tree (random). 4. **Page fill factor** — how full leaf pages are on average. Append-heavy loads pack pages tight; split-heavy loads leave them partly empty, so the index takes more space. ### Where to learn them - **B-tree inserts and splits (#1–#2):** DDIA §"B-Trees"; any DB-internals reference on B-tree page splits. - **The random-fill result (#4):** the average fill of a randomly-built B-tree tends to **ln 2 ≈ 69%** — a classic result (Knuth, *TAOCP* Vol. 3); you'll see it land almost exactly. - **Why LSM avoids it:** DDIA §"Sequential versus random writes" and §"Comparing B-Trees and LSM-Trees." If only one is new, make it #2 — page splits are why random order costs more. ## Environment Timings depend on your hardware and will differ; the index sizes and fill factors are structural and reproduce closely: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Docker 29.6.2 running the official `postgres:16` image → PostgreSQL 16.14 - Two tables of 10,000,000 rows, each with a B-tree index present during load ## Mental model Two tables, each with a B-tree index on column `k`, built *before* the rows are inserted so the index is maintained on every insert: - **Sequential** — `k = 1, 2, 3, …, 10,000,000`, inserted in order. Each new key is the largest so far, so it always goes into the current rightmost leaf. - **Random** — the *same count* of rows, but `k` is scattered across the key space (a hash of the row number). Consecutive inserts land in unrelated leaves all over the tree. Same table shape, same number of rows, same index — only the order the keys arrive in differs. We measure load time, index size, and how full the leaf pages end up. The whole exercise is one script, `code/random_vs_sequential_writes.sql`. ## Setup ``` docker run -d --name ddia-ch4 -e POSTGRES_PASSWORD=study -e POSTGRES_DB=study postgres:16 sleep 3 docker exec ddia-ch4 psql -U postgres -d study -c "CREATE EXTENSION pgstattuple;" docker cp random_vs_sequential_writes.sql ddia-ch4:/tmp/ docker exec ddia-ch4 psql -U postgres -d study -f /tmp/random_vs_sequential_writes.sql ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — load time (the surprise) **Predict.** Both loads insert exactly 10,000,000 rows into an identical table with an identical index. The only difference is the order the keys arrive in. How different can the load times be? (The instinct: "same rows, same work — maybe a little slower for random.") **Observe.** ``` === sequential insert: keys 1..10,000,000 in ascending order === INSERT 0 10000000 Time: 9979.232 ms (00:09.979) === random insert: same 10,000,000 rows, keys scattered across the key space === INSERT 0 10000000 Time: 39840.081 ms (00:39.840) ``` **~4× slower** for random order — ~10 s vs ~40 s — for the identical set of rows. Every scattered insert dirties a different, cold index page; the sequential load keeps hammering the same hot rightmost page. ### Step 2 — the index is bigger, too **Predict.** The two indexes hold the same 10M keys. Are they the same size? **Observe.** ``` === index sizes: same key count, different insertion order === seq_index | rnd_index | ratio -----------+-----------+------- 214 MB | 282 MB | 1.31 ``` The randomly-built index is **31% larger** — for the same keys. Random inserts split pages in the middle and leave the halves partly empty; the extra space is real bytes on disk (and in the cache) forever. ### Step 3 — why: page fill **Predict.** What is the average leaf-page fill of each index? (Sequential append should pack pages nearly full.) **Observe.** ``` === avg leaf fill (%): how densely packed the B-tree leaves are === insert_order | avg_leaf_density_pct --------------+---------------------- sequential | 90.1 random | 68.6 ``` Sequential fills leaves to **90%**; random settles at **68.6%** — essentially **ln 2 ≈ 69%**, the textbook average fill of a B-tree built from random keys. That 90-vs-69 gap is exactly the 31% size difference from Step 2. ## What you should see - Random-order load is **~4×** slower than sequential (~40 s vs ~10 s) for the same rows. - The random index is **~31%** larger (282 vs 214 MB). - Leaf fill: **~90%** sequential vs **~69%** random (the classic `ln 2`). ## Why A B-tree stores keys in sorted order across fixed-size pages, so a key's *value* decides which leaf it belongs in. Ascending keys are always the new maximum, so they land in the current rightmost leaf: the load touches one hot page until it fills, splits it once, and moves on. That page is already in memory, the writes coalesce, and each leaf ends up ~90% full. The disk sees, in effect, a sequential append. Scattered keys defeat all of that. Each insert targets a different leaf somewhere in the tree — very likely a *cold* page that must be read in, modified, and written back, with a write-ahead log entry each time. That is the pattern of "many small, scattered writes" the book names, and disks (even SSDs) do it slower than sequential writes: ~4× here. Worse, an insert into a full interior leaf splits it into two ~half-full pages, and with random arrivals that keeps happening everywhere at once, so the average fill converges to **ln 2 ≈ 69%** — which is both the wasted space (a 31% bigger index) and *more* pages to write, compounding the slowdown. **The boundary — sequential keys are the happy path; that's the whole point of LSM.** A B-tree loves monotonic keys: auto-increment IDs, timestamps, ULIDs. It suffers on random keys: UUIDv4, hashes, natural keys spread across a domain — which is exactly why time-ordered UUIDs (UUIDv7) were designed, to turn random inserts back into appends. An LSM-tree sidesteps the question entirely: it buffers writes in memory and flushes whole sorted segments at once, and compaction rewrites whole segments — so *every* write to disk is sequential regardless of key order. That is the write-throughput advantage the book attributes to log-structured storage, and this exercise is the B-tree cost it is measured against. ### Go deeper 1. **Rebuild and re-measure.** `REINDEX` the random index and check its size and fill. Predict whether a clean rebuild recovers the 90% packing — it sorts the keys first, so it should. (This is why periodic index maintenance exists.) 2. **`fillfactor`.** Create the sequential index with `WITH (fillfactor=70)` and compare. Predict how leaving room in each page changes size now vs. how it would help a later *update*-heavy workload. 3. **Count the WAL.** Wrap each load in a check of `pg_current_wal_lsn()` before and after. Predict which order generates more write-ahead log, and by roughly how much.