Transfer — the series
-
One access, eight kilobytes
Every count on this site 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.
-
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.
-
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.
-
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.
-
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 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 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 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.
-
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 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.
-
What a planner pays to find out what to pay
Insurance against a row estimate is set from the error's median and spread, and a running system knows neither — it has to fit them from executed queries. Fitted from one query the divisor costs 1.263 times the better plan against 1.215 for a planner that never insures at all, so learning is worse than not learning until about sixteen queries have run. The tail, though, is bought immediately: one observation already holds the worst case to 24.7 against 36.6.
-
The sibling a full leaf asks first
The rule databases use to fix ascending inserts fills their leaves completely and collapses to 53.4% when one key in a hundred arrives late. A leaf that offers a key to a sibling before it splits, and splits two full leaves into three when neither will take one, holds 84.2% on the same stream — and is better with a trickle of late keys than without one, because a perfectly ascending stream has no sibling with room.
-
A summary's silence is a bound, not a count
When both sides of a join are skewed towards the same values the textbook estimate is 399 times too low and the order it picks costs 244 times the better one; two counters a side repair it. Skew them towards different values and the same estimate becomes 254 times too high — and the counters have nothing to say, because no value is in both summaries. Using their silence instead repairs the middle of the sweep and makes the far end six times worse.
-
The read a filter has no key for
A Bloom filter on every run of a log-structured store turns a lookup for a missing key from a read of every level into a fraction of one — 0.72 transfers across eight levels at five bits a key, and 0.00027 at twenty. A range query over the same store reads nine transfers at five bits and nine at twenty, because a filter answers whether one named key is in a run and a range has no key to name.
-
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.