Transfer — the series
-
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.
-
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.
-
A planner that knows how sure it is
A planner that fits its insurance divisor from a handful of executed queries under-insures, because a spread fitted to a small sample is biased low. The textbook repair is to use the upper end of a confidence interval on the spread instead of its centre. At a read ratio of four it makes the planner worse than trusting its estimate for longer — until sixty-four queries rather than sixteen — and it buys the worst case immediately, from 22.4 times the better plan to 6.2 after two queries. The bound is not a correction towards the truth. It is a dial between two different planners.
-
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.
-
One bit a key, divided
A levelled store of a million clustered keys, each level's range filter a pair of prefix lengths chosen when the level is written, captures 68% of a perfect filter's saving at two bits a key spread evenly when its keys arrive shuffled, and 94% when they arrive a cluster at a time. The proposal was to divide the memory by what each level's filter saves per bit, and it predicted the memory would leave the small levels, whose keys the arrival order had already sorted out. It goes the other way, as it did for single prefix lengths, and much further: the small levels take twelve to sixteen bits a key, the deepest level one, and the store captures 99% of a perfect filter's saving on both orders while leaving part of the budget unspent. Divided, one bit a key on average does what four bits spread evenly cannot.