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.
A planner that knows how sure it is
An insurance divisor set from a one-sided upper confidence bound on the fitted error spread, swept from no bound to 99%: expected regret and worst regret against the queries seen, the trade between them at a fixed sample, the divisor each spread justifies at three read ratios, nine settings where the bound helps or hurts, and how slowly the inflation switches itself off.
The runs a range query can skip
A levelled store of 2^20 uniform keys in four levels, each carrying a real Bloom filter over b-bit key prefixes at five bits a key, measured against an oracle that skips exactly the empty levels: the share of the oracle each prefix length recovers for ranges of 0.1 to 100 keys, the transfers saved across range lengths, which levels are skippable, the same filter asked a point question, and one filter against two on a mixed workload.
A reach that follows the stream
A B+-tree of 131,072 keys whose redistribution reach doubles or halves every 64 overflows on the mean walk they made: its leaves and pages written against every fixed reach on random, ascending, descending and nearly ascending insertion; its position against the fixed frontier at six targets; two streams that change order halfway; how many insertions it takes to notice each change; and the target below which an ordered stream makes it thrash.
The small levels' share of a range filter
Range queries on a built log-structured store of 2^20 keys in four levels, with a Bloom filter over key prefixes on each: the best prefix length for each level alone and for each range length, where the gap between one shared length and a perfect range filter goes, what each level's transfers do as its filter gets more bits a key, the best division of a fixed memory among levels with a length chosen for each, and what that division does to lookups for absent keys.
The resolution a range filter can afford
Prefix filters at every length from 16 to 24 bits sharing each level's memory in a four-level store of 2^20 keys, a range asked at the longest length covering it with two prefixes and refined below every yes, or asked at every length from the coarsest, against one length a level: transfers a range query against filter memory, transfers and reads of empty levels by range length at five bits a key, the occupancy of each level's prefixes, and filter probes a query.
One length for the gaps and the clusters
A four-level store of 2²⁰ keys drawn uniformly or from 65,536 down to 16 windows of key space covering a sixteenth of it, with range queries starting anywhere in key space, centred on stored keys, or half of each; one prefix length a level chosen for each store, workload and memory against a Bloom filter at every length from 12 to 24 bits asked from the coarsest down, every skip checked against the keys: how many coarse prefixes are empty, which design wins in each cell, the lengths each workload wants, what one length for a mixed workload gives up on each kind of range, and the crossing against memory.
Two lengths that do the work of eleven
A four-level store of 2²⁰ keys in 16 clusters, in 4 large and 64 small ones, or in 16 groups of 16, asked half with ranges anywhere in key space and half with ranges at stored keys, at 4, 10 and 24 bits a key: one prefix length a level, the multi-resolution filter at every length from 12 to 24 bits, and the best pair of lengths a level asked coarse first, each chosen for its store, workload and memory — the saving against memory, the cost by range length, where the memory goes, the three stores, the saving charged again on fresh queries, and the filter probes each design asks.
The filter rebuilt with every write
The 2²⁰ keys of a sixteen-cluster store inserted one at a time into a levelled store with a 4,096-key buffer and size ratio four, shuffled or a cluster at a time, stopped at six points of the fill and charged on range queries half in the gaps and half at stored keys: a coarse-and-fine prefix pair chosen for each level at its last write against one pair chosen once, the transfers through the fill, where they fall level by level, every candidate pair on the smallest level, the pairs the levels chose, the gap between the two policies at two and ten bits a key, and the share of a perfect filter's saving captured at three memories.
One bit a key, divided
A levelled store of 2^20 keys in sixteen clusters, filled by insertion shuffled or a cluster at a time, each level's range filter a pair of prefix lengths chosen from its keys when it is written, given a total of 0.5 to 4 bits a key either evenly or by the division that makes the store cheapest on one seed of queries, charged on another: the share of a perfect filter's saving captured through the fill; each level's cost on the full store; the bits a key each level is given against its size; each level's cost against its filter's bits; the share captured against the budget; and where the memory goes.