Block transfer — where it appears
Named by 39 essays across 6 fields — each of them below, with the objects they name alongside it.
One access, eight kilobytes
An operation count charges one for an array access. A machine charges for a block. The same 65,536 accesses cost 1,024 transfers in one order and 65,536 in another, with nothing about the algorithm's work changed — a factor of 64, which is exactly the number of elements in a block, and which no counter here could see until now.
Sorting what will not fit
Merge sort's Θ(n log n) is a statement about comparisons and says nothing about a file larger than memory. Counted in transfers the answer is (n/B)·log_{M/B}(n/B), and the base of that logarithm is the number of blocks that fit in memory — so doubling the memory does not halve the work, it moves a staircase. The measured cost jumps by 32,768 transfers at one step and by nothing for the next four.
The layout that is told nothing
A B-tree is built around a block size somebody looked up. The van Emde Boas layout is given neither the block size nor the memory size, and across seven block sizes spanning a factor of 64 it tracks the best structure that was told them. An algorithm with no parameters making a claim at every level of the hierarchy at once is a strange thing to be able to measure, and this is what it costs.
The writes nobody counted
Sixteen thousand keys inserted into a B-tree write 49.3 elements' worth of blocks for every key stored. The same keys into a log-structured store write 2.0. Every operation counter reports the two as the same work — the same insertions, the same comparisons, the same number of updates — and the factor of 24 decides which structure a storage engine is built from.
The block that is not a block
This field's model has one memory, one block size, one processor, no prefetcher, no queue and no clock, and every number in it is a count of transfers rather than a duration. A real machine has five levels, reads ahead, issues a hundred requests at once, and charges four orders of magnitude more for one kind of transfer than another. What survives the difference is worth stating exactly, and so is what does not.
The floor under moving data
The information-theoretic floor for comparison sorting is log₂(n!) and it says nothing about a file on a disk. In the external model the floor is (n/B)·log_{M/B}(n/B), it is a bound on every algorithm rather than on merge sorts, and a measured external sort sits 2.40 to 2.97 times above it. Both numbers are computable, and the gap between them is what a real implementation costs.
Two searches, one comparison count
Three arrangements of the same binary search tree over the same million keys, walking the same path, making the same twenty comparisons. One costs 15 block transfers, one costs 13, and one costs 3. Nothing about the algorithm differs between them — only where the nodes were put — and no counter this site had before this phase could tell them apart.
One dial between two structures
A B-tree writes 226 elements of block for every key stored and a log-structured store writes two. They are presented as rival designs. They are one design at two settings of an exponent that nothing in either description mentions, and every setting between them is available.
Permuting is the harder problem here
Rearranging 65,536 elements into a stated order costs 63,601 transfers one at a time and 4,096 by sorting them into place. In the model every other field on this site uses, the first is the cheap method and beats the second by a factor of eight. The two models disagree about which problem is easy, and they disagree by about the same factor in opposite directions.
A tree with nodes the size of a block
A B-tree is a binary search tree that has read the hardware manual. Its node holds as many keys as fit in one transfer, so the height falls from log₂ n to log_B n — and the measured cost falls further still, to 1.01 transfers over four million keys, because the top of the tree is small enough to stay in memory. The comparison count goes up.
The index that is not worth reading
An index turns a query over 65,536 rows from 1,024 transfers into four. At a thousand matching rows it costs 654 and still wins; at sixteen thousand it costs 1,027 and has lost. Where it turns is decided by the block size — a number the query does not contain, the schema does not mention, and nobody writing either has seen.
Two ways to join, and the ratio that decides
The same join costs 260 transfers one way and 1,040 the other; at eight times the memory the same two costs are 2,880 and 1,280, the other way round. Neither number is a property of how large the tables are. The quantity that decides is how the smaller of them compares to memory, and a rule of thumb phrased in rows is a rule about somebody's machine.
The estimate a plan rests on
A planner chooses between an index and a scan on how many rows it thinks will match, and the number it has is wrong by a factor. Guess sixty-four times too many on a narrow query and the scan it picks costs 13.5 times the index. Guess sixty-four times too few on a wide one and the index costs at most 4.01 times the scan — a ceiling that can be named before any query runs.
What a pass costs when it is a file
The streaming model trades passes for memory along n to the power one over p, and it never says what a pass costs. On a file a pass is a read of every block, and it cannot run in less than one block of memory. Charge both and the trade nearly disappears: the median of four million keys takes three passes at two blocks of memory and two passes at four, and writing the surviving interval out makes the third pass cost sixteen blocks instead of four thousand. On a heavy tail the same habit nearly doubles the bill.
The permutation that moves almost nothing
Two ways to scramble sixteen thousand elements. Shuffling them inside windows of five hundred and twelve puts two million pairs out of order and costs 3,095 block transfers to carry out. Swapping a thousand pairs across the whole array puts seven million out of order and costs 1,189. Inversions are the textbook measure of disorder, and on a disk they rank these two backwards.
The join order is a guess
Three tables, two orders, and an estimate of the first intermediate result that assumes the join column is uniform. When the column is skewed the estimate is out by seventy-two times, and the plan chosen on it costs 1.49 times the better one — which sounds tolerable until the shared output is taken away, and the part of the cost the order actually decided turns out to be 43.9 times worse.
The filter each run carries
A log-structured store turns every lookup for a missing key into a read of every level, and a Bloom filter on each run buys those reads back with memory. Spread five bits a key evenly across three levels and a missing key still wastes 0.279 reads. Give the small levels more bits and the large one fewer — the same memory — and it wastes 0.201. At four levels the gap is 0.382 against 0.209, because sized filters stop the waste growing with the number of levels.
The skew a few counters cannot repair
A join order chosen on the textbook estimate costs 243.9 times the better order at a Zipf exponent of two, and two counters a side are enough to fix it. At an exponent of one half the estimate is out by less than a factor of two, the plan it picks costs 1.37 times the better one, and no number of counters up to 256 changes that. The easy case is the extreme one, and the reason the moderate one is hard is a series that stops converging at exactly one half.
What insurance against an estimate costs
A planner that trusts its row estimate expects to pay 1.057 times the better plan and risks 7.76. One that insures itself by halving its estimate before it decides expects 1.057 and risks 4.10 — the insurance is free. At a read ratio of sixteen the same insurance costs six per cent in expectation and makes the worst case worse. Whether a conservative planner is paying a sensible premium depends on two numbers the planner can measure and usually does not — its device's read ratio and the direction its own errors run.
Runs twice as long as memory
Feed 262,144 random records through a heap that holds 4,096 and the sorted runs that come out average 1.94 memories — the snowplow's famous factor of two. At a fan-in of 63 that saves a merge pass at 262,144 records, and at two of fourteen sizes in all. Feed the same heap a sorted file with one record in a thousand out of place and it writes two runs instead of sixty-four. And it spends 19 comparisons a record doing so, on every input, where sorting the chunks spends five on sorted data. The factor of two is the least of what the method does.
The keys that arrive late
Insert 131,072 keys into a B+-tree in random order and its leaves end up 70.5% full; in ascending order, 51.6%; in descending order, 50.0%. The rule databases use to fix ascending inserts — split a full leaf at its right-hand end — fills them completely, and it does nothing for descending keys. Let one key in a hundred arrive late in an otherwise ascending stream and the rule's leaves fall from 100% to 53.4% full. How much of an index is empty is decided by the order its keys arrived in, and a trickle of disorder undoes the fix.
A key passed along the row
A full B+-tree leaf that offers a key to its immediate neighbours before splitting leaves an ascending stream 67.2% full. Let it look one sibling further and the same stream fills its leaves completely, 2,048 leaves where there were 3,048, for about the same key moves. On random keys each doubling of the reach adds a few points of fill and more writes than it saves, and at the whole parent a key travels sixteen leaves on average. On a stream that is mostly in order the same reach costs almost nothing.
The runs a range query can skip
A Bloom filter over key prefixes can tell a range query that a run holds nothing it wants, which a filter over keys cannot. On a four-level store of a million keys, a range expected to hold one key costs 4.76 transfers with no such filter and 2.41 with one built on 20-bit prefixes. The best length moves two bits for every tenfold longer range. By a hundred keys the most any range filter could save is a fifth of a transfer, because only the smallest level is ever empty. And the same memory spent on 20-bit prefixes makes a lookup for an absent key three times dearer.
A reach that follows the stream
A full B+-tree leaf that passes keys along its siblings wants a short reach on random insertion and the whole parent on a nearly ordered stream, and a tree is never told which it is receiving. Let the reach double after every 64 overflows whose walks averaged two siblings or less and halve otherwise, and it finds the whole parent on every ordered stream. On random keys it lands on the fixed reaches' own frontier. On a stream that turns from random to ordered halfway it beats every fixed reach, by 57 leaves at the same writes. It notices a turn to random in 62 insertions and a turn to order in 779. Below a target of 1.75 siblings it thrashes on ordered keys.
The small levels' share of a range filter
Prefix filters on a four-level store were proposed a prefix length each, on the reasoning that one length is a compromise between levels whose densities differ 43-fold. Each level does want its own length, 18 to 22 bits, and that recovers a quarter of the gap to a perfect range filter. The gap is mostly not about length. Three fifths of it is false positives. Moving filter bits from the largest level to the small ones — 12, 12, 8 and 3 bits a key instead of 5 each — recovers more than half of it at the same memory, and matches one shared length given twice the memory.
The resolution a range filter can afford
A prefix filter on each level of a log-structured store answers a range by asking one question for every prefix the range touches, and each can be wrong. A filter holding prefixes at every length from 16 to 24 bits could ask each range at the resolution it needs, and was proposed as the repair. At the store's five bits a key it costs 5.69 transfers a range query where one length a level costs 4.32, because a short range is asked only at the finest length, and that filter now holds a fraction of the memory. Asked at every length it recovers most of that, and seems to overtake the single length at twelve bits a key — but only a single length chosen for five bits. Chosen again for each memory, one length a level beats every multi-resolution design at every memory measured, because the resolution a level can afford is itself set by its memory.
One length for the gaps and the clusters
On uniform keys one prefix length a level, chosen for its memory, beat a filter holding every length from 12 to 24 bits. Clustering the keys was predicted to reverse that, because coarse prefixes between clusters are empty and a coarse filter can then say no to a long range in one question. Clustering alone does not: whether ranges fall in the gaps or at the keys, one length re-chosen for that workload still wins, since it moves coarse for the gaps and fine for the keys. The multi-resolution filter wins only where a clustered store is asked both — by 0.17 transfers a query at ten bits a key on sixteen clusters — and it wins on short ranges inside the clusters, not on long ones between them.
Two lengths that do the work of eleven
On keys that cluster, asked both between the clusters and at them, a prefix filter holding every length from 12 to 24 bits beat one length a level by 0.17 transfers a range query, and a pair of lengths — one coarse, one fine — was proposed to recover nearly all of that. It recovers more than all of it: 0.23 transfers at ten bits a key, and at four bits, where the eleven lengths lose to one, the pair still saves 0.18. The coarse filter takes under 2% of a level's memory, and the eleven-length filter was leaving its finest length as little as 14% and cannot give it more without starving the lengths its descent passes through. The store predicted to defeat a pair, with gaps at two scales, does not. The saving is bought in questions: the pair asks its filters more often than the eleven lengths do.
The filter rebuilt with every write
A log-structured store chooses a range filter's two prefix lengths when it writes a level, and a filling store's small levels hold only the keys that arrived last. Choosing at every write was predicted to keep the lead a pair chosen once on the full store has, except where keys arrive a cluster at a time and a small level's choice goes stale when the next batch lands elsewhere. It cannot go stale: a levelled store changes a level's keys only by rewriting it, and rewriting it rebuilds the filter. Choosing at every write and choosing once then differ by at most 2.3% of what a perfect filter saves, on both arrival orders, at two bits a key and at ten, and choosing costs twenty-eight times the hashing. What the order of arrival changes is the store: filled a cluster at a time, its small levels hold one cluster each, and at two bits a key the same filter captures 94% of a perfect filter's saving against 68% shuffled.
A file written once for the queries after
An exact selection against a file of four million keys counts the whole file into a thousand or more pieces on its first pass, keeps the one piece holding its rank, and throws the rest away. Kept, those counts save every later query one full read of the file, from the second query on. Written out as parts, the file makes each later query read a fraction of it — but a pass that counts 3,582 pieces can write only seven, because each part needs a buffer. On a heavy tail, parts of equal width never pay; parts cut where the counts say the keys are pay by the second query and bring twenty-three selections from 69 reads of the file to 9.
A product paid for in blocks
The published floor under sorting puts a bound on time times space, and a read-only family that scans its input over and over meets it, while every in-place sort sits far above it. Counted in block transfers rather than reads, the floor itself moves to n²/B: the family meets it at every block size, and so does every sort once memory holds the whole array. With a memory of 512 cells, quicksort sits a fixed eight times above the family at every block size, because partitioning is itself a scan. Only heapsort's distance grows with the block, from ten times at a line of one to 285 times at 64. The prediction that the family's lead would widen towards B holds against heapsort and nothing else.
Parts cut where the questions are
A file of four million keys, written once as seven parts so that each later selection reads only its own part, can be cut where the keys are or where the questions are. When nine queries in ten ask about the top 2% of ranks, parts balanced by keys cost 1,170 block transfers a query. Parts that each serve an equal share of past queries cost about as much, and a little calculus says they must, on average. Parts cut so that each one's size times its share of queries is equal cost 290, which is the optimum's square-root law, measured to within a third at every concentration tried. The saving lasts exactly as long as the questions stay where they were counted: moved a percentile and a half, the fitted parts cost more than the plain ones.
A recut the law decides
Parts of a file cut by the square-root law where selection queries fall lost their advantage once the queries moved a percentile and a half. A partition that recuts itself when the law says the saving pays for the rewrite was predicted to stay within 20% of the best fixed recut interval at every drift speed, and to fail on traffic that jumps. With recent queries decayed at a half-life of 250, it stays within 7% up to a drift of 0.1 percentiles every hundred queries and within 22% at five times that. On jumping traffic it beats every interval fixed in advance, rewriting 13 times a stream where the best interval rewrites 80. The law does not remove a setting: it trades the interval, which has to move fourfold with the speed, for a half-life that does not.
Every cut the law moves
A file cut into seven parts by the square-root law, and recut when the law says the saving pays, was charged a full rewrite for every recut. Charging only the parts whose boundaries change was predicted to cut a recut's cost to a tenth on slow drift. It cuts it by 2%. When the band of hot queries moves, the law moves 98% of its cuts, a median of nineteen thousand ranks each, because the parts on either side of the band have to share out what the band left. Holding small moves back keeps a quarter of the file and costs more a query; recutting only the parts around the band costs up to three times as much.
The two parts the law was not given
The square-root law moves almost every cut of a seven-part file whenever its band of hot queries moves. A background cut once by keys, with only the part holding the band cut again, was proposed instead: a recut would rewrite a seventh of the file. It does, and it beats the law at every drift speed — 365 transfers a query against 417 at a moderate drift — but it wins with nine parts to the law's seven. Given nine, the law costs 322. Held to seven, the fixed background loses to the law at every speed. What survives the fair comparison is narrower and still useful: six parts by keys, with the band's part cut in four, ties the nine-part law on drift for a quarter of its rewriting. It loses on jumps, because a fixed background waits about three hundred queries to believe the band has left before it moves, and it pays double wherever a background cut runs through the band.
A background that holds two bands
A file kept in six fixed parts by keys, with the part holding the band of hot queries cut in four, ties the nine-part square-root law on drifting traffic and loses to it by 10% to 16% when the band jumps, because after a jump it pays for a whole background part for three hundred queries before moving its split. Asking every part whether a split would pay, instead of asking which part holds the most queries, was proposed to end the wait. It changes nothing: 363 transfers a query against 365. What ends the wait is the second half of the proposal, letting two parts be split at once in three and two pieces: on jumps the background comes within 2% to 4% of the law, and on fast drift, which nobody expected it to touch, it beats the law by 6% to 10%, because a band lying across a background cut is held by two split parts rather than by one split and one whole.
The memory a product does not charge
Time times space charges a sort for the cells it writes and not for the fast memory it needs to write them cheaply. Counted three ways, on random keys in lines of eight, a read-only family stays within a factor of eight of the floor with 32 to 256 cells of fast memory at every length, while heapsort needs all of n and quicksort an eighth of it. Quicksort's need falls far faster than predicted as the factor loosens. And the product the floor leaves out, transfers times fast memory, separates the two kinds of sort completely: no read-only sort can push it far below n²/B, and quicksort reaches a twentieth of it.
The lines a sort writes back
A replay that charges a transfer for every line brought into fast memory and none for a line sent back flatters every sort that writes in place. Charged for its write-backs, quicksort's transfers rise by 1.9 at every memory short of n, as predicted, and heapsort's by 1.8, not the predicted three, because no line can go back more often than it came in. The cost that changes the account is the last one: at n itself every in-place sort pays two reads of its array, so none of them can come within a factor of two of the floor, while the read-only family reaches 1.07.
A buffer that does not shift its tail
The read-only family of sorts scans its input once for each batch of the smallest values not yet output, keeping them in a buffer; charged for the dirty lines it sends back to slow memory, its least transfers × fast memory rose from 1.29 of n²/B to 1.87, because a sorted buffer takes each value by shifting every larger entry one place. Kept as a max-heap instead, the buffer was predicted to write back about a third of the lines it reads below its own size and to bring the product back towards 1.29. At a buffer of 64 cells it writes back 33% at its best memory, against 45%, and its least product falls to 1.71: right about the share, wrong about the product, since a third written back is still a third more transfers. At 256 cells the heap does more than predicted — 1.47 million accesses against 6.94 million, a third of the misses — and its least product, 1.62, is under any buffer's on the earlier charge. At 16 cells it does nothing.
Named alongside it
The objects these essays reach for when they reach for this one.
Trade offExternal-memory modelCost modelHonest limitExternal-memoryLocalityLsm treeB-treeDesign parameterWorkloadBloom filterRegime