When it does not fit
One access, eight kilobytes
The external-memory model with its two parameters stated — the block size B and the memory size M — and why the unit of cost that every analysis on this site assumed is the wrong one as soon as the data does not fit.
Sorting what will not fit
External merge sort measured in block transfers, why the cost is a staircase in the memory available rather than a curve, and why the base of the logarithm is M/B.
The layout that is told nothing
Cache-oblivious layout measured against a B-tree tuned for one block size, across seven block sizes — what a parameterless algorithm can claim, and the constant factor it pays for the claim.
The writes nobody counted
Write amplification measured — an in-place B-tree against a log-structured merge tree — and why a read count and a write count are two resources rather than one.
One dial between two structures
The buffered tree, measured — how one exponent moves insertion cost from a whole block per key to a fraction of one, what it charges for that on every query afterwards, and where the trade stops paying.
Permuting is the harder problem here
Why moving elements one at a time costs one transfer each, why sorting by destination costs far less, where the two cross, and what a lower bound proved about both.
The index that is not worth reading
Three query plans priced in transfers, why the crossover the textbook arithmetic predicts is not the measured one, and what a clustered index changes about all of it.
Two ways to join, and the ratio that decides
Block nested loop, partitioned hash and sort–merge joins measured in transfers, why all three return identical answers, and why the choice between them is a ratio rather than a size.
The estimate a plan rests on
One planner decision priced at the truth while its row estimate is held wrong by a fixed factor. Overestimates on narrow queries grow with the file, underestimates are capped by the read-cost ratio, and that ratio decides which mistake is the dangerous one.
The permutation that moves almost nothing
Carrying out a permutation one element at a time, measured against the inversions it contains. The cost follows how far elements move relative to what fits in memory, not how many pairs are out of order, and two permutations can be ordered one way by inversions and the other way by transfers.
The join order is a guess
A three-way join ordered on an estimate that assumes a uniform join column, swept over skew. The regret over the whole plan stays under 1.5 while the regret on the part the order controls reaches 44 and then 244, because every order writes the same output and that shared cost hides the mistake.
The filter each run carries
Bloom filters on the runs of a log-structured store, with the same memory divided evenly or sized to each level. Sizing makes an absent lookup's wasted reads nearly independent of how many levels there are, while an even split pays for every level it adds.
The skew a few counters cannot repair
The uniform join-size estimate behind a three-way join order, repaired with Misra–Gries summaries of the join column, swept over skew and over the number of counters. A handful of counters removes a regret of 243.9 at high skew; at an exponent of one half 256 counters remove nothing and 512 are needed, because the sum of squared frequencies no longer has a small set of values carrying it.
What insurance against an estimate costs
Four planners choosing between an index and a scan on estimates wrong by a log-normal factor, priced exactly over the error distribution. Insurance that shifts the crossing is free and halves the tail at a small read ratio, costs a third of the expected regret at a moderate one when estimates run low, and buys nothing at a large one — and when estimates run high it lowers the expected regret too.
Runs twice as long as memory
Replacement selection measured against loading, sorting and storing memory-sized runs for an external merge sort. Runs average two memories on random input, one run on sorted input and exactly one memory on reversed input; halving the runs saves a merge pass only in narrow windows of file size, while nearly sorted input collapses the run count and with it the merge.
The keys that arrive late
A B+-tree with real node splits built from the same keys in several arrival orders, under even splits and under the rightmost-split rule, beside a tree bulk-loaded from sorted keys. Leaf fill runs from 50% to 100% and the leaf count by a factor of two; random insertion settles near ln 2; and one per cent of late keys in an ascending stream removes the whole benefit of the rightmost-split rule.
What a planner pays to find out what to pay
The insurance divisor a query planner applies to its own row estimates, fitted from executed queries rather than given, measured in expected and worst regret against the number of observations — and across a plane of read ratio and error spread where learning ranges from paying at once to never paying.
The sibling a full leaf asks first
B*-tree redistribution at the leaves of a B+-tree, measured against even splits and the rightmost-split rule on random, ascending, descending and late-arriving key orders — with the extra sibling writes it costs counted per key.
A summary's silence is a bound, not a count
A three-way join whose two sides are skewed towards different values, swept from identical rankings to unrelated ones, with the uniform estimate, a Misra–Gries summary of each side, and a summary that also uses the values it does not hold — and why only one direction of error is correctable.
The read a filter has no key for
Range queries over a log-structured store measured against the point lookups its Bloom filters were bought for, swept over the size ratio, the range's length and the filter's bits — and the size ratio a store should be tuned to once its queries are not all point lookups.
A key passed along the row
Redistribution in a B+-tree of 131,072 keys widened from the adjacent siblings to a chain across the parent's children, at reaches of 1 to 64, on random, ascending, descending and nearly ascending insertion: the leaves' fill, the pages written per key, the trade between the two, and how far a key actually travels.