Generator

65,536 accesses, three orders, one block size

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
65,536 accesses, three orders, one block sizeEach row makes exactly 65,536 element accesses; only the order differs. In order, the 65,536 accesses cost 1,024 transfers, because each block arrives once and every element in it is used before it leaves. Striding by a whole block costs 65,536 — one transfer per access, with B−1 elements of each block thrown away. The operation count cannot tell these apart and never could.block transfersIn order, 0 to n−11,0241.0× a scan · 64.0 elements per transferEvery B-th element (B = 64)65,53664.0× a scan · 1.0 elements per transferUniformly at random61,40760.0× a scan · 1.1 elements per transfera scan of this array is 1,024 transfersB = 64, M = 4,096 (M/B = 64)64× between the cheapest order and the dearest

65,536 accesses, three orders, one block size

Each row makes exactly 65,536 element accesses; only the order differs. In order, the 65,536 accesses cost 1,024 transfers, because each block arrives once and every element in it is used before it leaves. Striding by a whole block costs 65,536 — one transfer per access, with B−1 elements of each block thrown away. The operation count cannot tell these apart and never could.

Drawn at 700 × 298, wide on the page. Everything above is what transfer-cost returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

10 essays call transfer-cost. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

block transfersIn order, 0 to n−11,0241.0× a scan · 64.0 elements per transferEvery B-th element (B = 64)65,53664.0× a scan · 1.0 elements per transferUniformly at random61,40760.0× a scan · 1.1 elements per transfera scan of this array is 1,024 transfersB = 64, M = 4,096 (M/B = 64)64× between the cheapest order and the dearest When it does not fit

One access, eight kilobytes

10³10⁴10010³n (elements)block transfersM = 256 · fan-in 7M = 1024 · fan-in 31B = 32, M as labelled4 passes against 3 When it does not fit

Sorting what will not fit

elements of block written per key insertedB-tree, in place49.3Log-structured, T = 23.0 · 16× less than the treeLog-structured, T = 42.0 · 25× less than the treeLog-structured, T = 81.0 · 49× less than the treeLog-structured, T = 161.0 · 49× less than the treeB = 64, M = 4,096 (M/B = 64)25× between the two structures at T = 4 When it does not fit

The writes nobody counted

least recently usedthe offline optimumA loop over 7 blocks35 accesses35113.18×Random over 7 blocks35 accesses971.29×A straight sweep35 accesses35351.00×B = 8, M = 48 (M/B = 6)3.2× on the loop What is taught wrongly

The block that is not a block

Sorted array (binary search)2 blocksLevel order4 blocksvan Emde Boas2 blocksmemory address, left to right · alternating outlines are blocksB = 8, M = 64 (M/B = 8)4 blocks against 2, for the same 6 comparisons What the machine does

Two searches, one comparison count

levels on the path (outline) · transfers actually paid (filled)B = 411 levels · 6.99 transfers · 16,384 blocks residentB = 166 levels · 3.23 transfers · 4,096 blocks residentB = 644 levels · 1.99 transfers · 1,024 blocks residentB = 2563 levels · 1.30 transfers · 256 blocks residentB = 10243 levels · 1.01 transfers · 64 blocks residentbinary search over the same 4,194,304 keys: 20 transfersB = 1024, M = 65,536 (M/B = 64)20× between binary search and the widest tree Structures

A tree with nodes the size of a block

11010010³10⁴1010010³rows matching the queryblock transfersn/B rows — where the arithmetic says they meetindex, rows scatteredindex, file in key orderread the whole fileB = 64, M = 4,096 (M/B = 64)plus 3 transfers to descend the index When it does not fit

The index that is not worth reading

11010010³10⁴12510rows the query actually matchescost ÷ the better plan's costrho plus the descent, 4.01estimate ÷64estimate ÷8estimate ×8estimate ×64n = 65,536, B = 64, M = 4,096 (M/B = 64), scattered read ×4dotted: the estimate switches at 512 rows When it does not fit

The estimate a plan rests on

trusts the estimateinsured ×2insured ×8always the index11.5235expected regret, logarithmic · label: worst within three standard deviationsrho 14.42.51.11.0rho 215.17.82.22.0rho 413.57.54.04.0rho 1616.016.016.016.0σ = 1.5, median error e^-1, 65,536 rowsexact over the error distribution When it does not fit

What insurance against an estimate costs

12481632641282561executed queries the fit sawexpected regrettrusting the estimatefitted from the queriesthe best divisor, 1.5ρ = 4, σ = 1.5, 120 fits a pointlower is better When it does not fit

What a planner pays to find out what to pay

The library, page 5 of 5 — where transfer-cost sits