Model

External sort: passes and fan-in

The merge fan-in is memory divided by the medium's efficient transfer unit.

passes = 1 + ⌈ lo g_{F} \frac{N}{M} ⌉, I/O = 2 N \times passes, F \leq \frac{M}{efficient read size}

$N$: Data; data to sort
$M$: Memory; memory for the sort
$F$: Fan-in; how many runs are merged at once

Recurring principle: Fixed cost per operation

How it behaves

One input on the horizontal axis, the others held fixed.

F = 10 (old disks)F = 100F = 8,192 (NVMe, 1 MB buffers)

Data table

Passes over the data by data-to-memory ratio
Data ÷ memory N/M	series	Passes
1	F = 10 (old disks)	1
1.26	F = 10 (old disks)	2
1.58	F = 10 (old disks)	2
2	F = 10 (old disks)	2
2.51	F = 10 (old disks)	2
3.16	F = 10 (old disks)	2
3.98	F = 10 (old disks)	2
5.01	F = 10 (old disks)	2
6.31	F = 10 (old disks)	2
7.94	F = 10 (old disks)	2
10	F = 10 (old disks)	2
12.6	F = 10 (old disks)	3
15.8	F = 10 (old disks)	3
20	F = 10 (old disks)	3
25.1	F = 10 (old disks)	3
31.6	F = 10 (old disks)	3
39.8	F = 10 (old disks)	3
50.1	F = 10 (old disks)	3
63.1	F = 10 (old disks)	3
79.4	F = 10 (old disks)	3
100	F = 10 (old disks)	3
126	F = 10 (old disks)	4
158	F = 10 (old disks)	4
200	F = 10 (old disks)	4
251	F = 10 (old disks)	4
316	F = 10 (old disks)	4
398	F = 10 (old disks)	4
501	F = 10 (old disks)	4
631	F = 10 (old disks)	4
794	F = 10 (old disks)	4
1K	F = 10 (old disks)	4
1.26K	F = 10 (old disks)	5
1.58K	F = 10 (old disks)	5
2K	F = 10 (old disks)	5
2.51K	F = 10 (old disks)	5
3.16K	F = 10 (old disks)	5
3.98K	F = 10 (old disks)	5
5.01K	F = 10 (old disks)	5
6.31K	F = 10 (old disks)	5
7.94K	F = 10 (old disks)	5
10K	F = 10 (old disks)	5
12.6K	F = 10 (old disks)	6
15.8K	F = 10 (old disks)	6
20K	F = 10 (old disks)	6
25.1K	F = 10 (old disks)	6
31.6K	F = 10 (old disks)	6
39.8K	F = 10 (old disks)	6
50.1K	F = 10 (old disks)	6
63.1K	F = 10 (old disks)	6
79.4K	F = 10 (old disks)	6
100K	F = 10 (old disks)	6
126K	F = 10 (old disks)	7
158K	F = 10 (old disks)	7
200K	F = 10 (old disks)	7
251K	F = 10 (old disks)	7
316K	F = 10 (old disks)	7
398K	F = 10 (old disks)	7
501K	F = 10 (old disks)	7
631K	F = 10 (old disks)	7
794K	F = 10 (old disks)	7
1M	F = 10 (old disks)	7
1.26M	F = 10 (old disks)	8
1.58M	F = 10 (old disks)	8
2M	F = 10 (old disks)	8
2.51M	F = 10 (old disks)	8
3.16M	F = 10 (old disks)	8
3.98M	F = 10 (old disks)	8
5.01M	F = 10 (old disks)	8
6.31M	F = 10 (old disks)	8
7.94M	F = 10 (old disks)	8
10M	F = 10 (old disks)	8
12.6M	F = 10 (old disks)	9
15.8M	F = 10 (old disks)	9
20M	F = 10 (old disks)	9
25.1M	F = 10 (old disks)	9
31.6M	F = 10 (old disks)	9
39.8M	F = 10 (old disks)	9
50.1M	F = 10 (old disks)	9
63.1M	F = 10 (old disks)	9
79.4M	F = 10 (old disks)	9
100M	F = 10 (old disks)	9
1	F = 100	1
1.26	F = 100	2
1.58	F = 100	2
2	F = 100	2
2.51	F = 100	2
3.16	F = 100	2
3.98	F = 100	2
5.01	F = 100	2
6.31	F = 100	2
7.94	F = 100	2
10	F = 100	2
12.6	F = 100	2
15.8	F = 100	2
20	F = 100	2
25.1	F = 100	2
31.6	F = 100	2
39.8	F = 100	2
50.1	F = 100	2
63.1	F = 100	2
79.4	F = 100	2
100	F = 100	2
126	F = 100	3
158	F = 100	3
200	F = 100	3
251	F = 100	3
316	F = 100	3
398	F = 100	3
501	F = 100	3
631	F = 100	3
794	F = 100	3
1K	F = 100	3
1.26K	F = 100	3
1.58K	F = 100	3
2K	F = 100	3
2.51K	F = 100	3
3.16K	F = 100	3
3.98K	F = 100	3
5.01K	F = 100	3
6.31K	F = 100	3
7.94K	F = 100	3
10K	F = 100	3
12.6K	F = 100	4
15.8K	F = 100	4
20K	F = 100	4
25.1K	F = 100	4
31.6K	F = 100	4
39.8K	F = 100	4
50.1K	F = 100	4
63.1K	F = 100	4
79.4K	F = 100	4
100K	F = 100	4
126K	F = 100	4
158K	F = 100	4
200K	F = 100	4
251K	F = 100	4
316K	F = 100	4
398K	F = 100	4
501K	F = 100	4
631K	F = 100	4
794K	F = 100	4
1M	F = 100	4
1.26M	F = 100	5
1.58M	F = 100	5
2M	F = 100	5
2.51M	F = 100	5
3.16M	F = 100	5
3.98M	F = 100	5
5.01M	F = 100	5
6.31M	F = 100	5
7.94M	F = 100	5
10M	F = 100	5
12.6M	F = 100	5
15.8M	F = 100	5
20M	F = 100	5
25.1M	F = 100	5
31.6M	F = 100	5
39.8M	F = 100	5
50.1M	F = 100	5
63.1M	F = 100	5
79.4M	F = 100	5
100M	F = 100	5
1	F = 8,192 (NVMe, 1 MB buffers)	1
1.26	F = 8,192 (NVMe, 1 MB buffers)	2
1.58	F = 8,192 (NVMe, 1 MB buffers)	2
2	F = 8,192 (NVMe, 1 MB buffers)	2
2.51	F = 8,192 (NVMe, 1 MB buffers)	2
3.16	F = 8,192 (NVMe, 1 MB buffers)	2
3.98	F = 8,192 (NVMe, 1 MB buffers)	2
5.01	F = 8,192 (NVMe, 1 MB buffers)	2
6.31	F = 8,192 (NVMe, 1 MB buffers)	2
7.94	F = 8,192 (NVMe, 1 MB buffers)	2
10	F = 8,192 (NVMe, 1 MB buffers)	2
12.6	F = 8,192 (NVMe, 1 MB buffers)	2
15.8	F = 8,192 (NVMe, 1 MB buffers)	2
20	F = 8,192 (NVMe, 1 MB buffers)	2
25.1	F = 8,192 (NVMe, 1 MB buffers)	2
31.6	F = 8,192 (NVMe, 1 MB buffers)	2
39.8	F = 8,192 (NVMe, 1 MB buffers)	2
50.1	F = 8,192 (NVMe, 1 MB buffers)	2
63.1	F = 8,192 (NVMe, 1 MB buffers)	2
79.4	F = 8,192 (NVMe, 1 MB buffers)	2
100	F = 8,192 (NVMe, 1 MB buffers)	2
126	F = 8,192 (NVMe, 1 MB buffers)	2
158	F = 8,192 (NVMe, 1 MB buffers)	2
200	F = 8,192 (NVMe, 1 MB buffers)	2
251	F = 8,192 (NVMe, 1 MB buffers)	2
316	F = 8,192 (NVMe, 1 MB buffers)	2
398	F = 8,192 (NVMe, 1 MB buffers)	2
501	F = 8,192 (NVMe, 1 MB buffers)	2
631	F = 8,192 (NVMe, 1 MB buffers)	2
794	F = 8,192 (NVMe, 1 MB buffers)	2
1K	F = 8,192 (NVMe, 1 MB buffers)	2
1.26K	F = 8,192 (NVMe, 1 MB buffers)	2
1.58K	F = 8,192 (NVMe, 1 MB buffers)	2
2K	F = 8,192 (NVMe, 1 MB buffers)	2
2.51K	F = 8,192 (NVMe, 1 MB buffers)	2
3.16K	F = 8,192 (NVMe, 1 MB buffers)	2
3.98K	F = 8,192 (NVMe, 1 MB buffers)	2
5.01K	F = 8,192 (NVMe, 1 MB buffers)	2
6.31K	F = 8,192 (NVMe, 1 MB buffers)	2
7.94K	F = 8,192 (NVMe, 1 MB buffers)	2
10K	F = 8,192 (NVMe, 1 MB buffers)	3
12.6K	F = 8,192 (NVMe, 1 MB buffers)	3
15.8K	F = 8,192 (NVMe, 1 MB buffers)	3
20K	F = 8,192 (NVMe, 1 MB buffers)	3
25.1K	F = 8,192 (NVMe, 1 MB buffers)	3
31.6K	F = 8,192 (NVMe, 1 MB buffers)	3
39.8K	F = 8,192 (NVMe, 1 MB buffers)	3
50.1K	F = 8,192 (NVMe, 1 MB buffers)	3
63.1K	F = 8,192 (NVMe, 1 MB buffers)	3
79.4K	F = 8,192 (NVMe, 1 MB buffers)	3
100K	F = 8,192 (NVMe, 1 MB buffers)	3
126K	F = 8,192 (NVMe, 1 MB buffers)	3
158K	F = 8,192 (NVMe, 1 MB buffers)	3
200K	F = 8,192 (NVMe, 1 MB buffers)	3
251K	F = 8,192 (NVMe, 1 MB buffers)	3
316K	F = 8,192 (NVMe, 1 MB buffers)	3
398K	F = 8,192 (NVMe, 1 MB buffers)	3
501K	F = 8,192 (NVMe, 1 MB buffers)	3
631K	F = 8,192 (NVMe, 1 MB buffers)	3
794K	F = 8,192 (NVMe, 1 MB buffers)	3
1M	F = 8,192 (NVMe, 1 MB buffers)	3
1.26M	F = 8,192 (NVMe, 1 MB buffers)	3
1.58M	F = 8,192 (NVMe, 1 MB buffers)	3
2M	F = 8,192 (NVMe, 1 MB buffers)	3
2.51M	F = 8,192 (NVMe, 1 MB buffers)	3
3.16M	F = 8,192 (NVMe, 1 MB buffers)	3
3.98M	F = 8,192 (NVMe, 1 MB buffers)	3
5.01M	F = 8,192 (NVMe, 1 MB buffers)	3
6.31M	F = 8,192 (NVMe, 1 MB buffers)	3
7.94M	F = 8,192 (NVMe, 1 MB buffers)	3
10M	F = 8,192 (NVMe, 1 MB buffers)	3
12.6M	F = 8,192 (NVMe, 1 MB buffers)	3
15.8M	F = 8,192 (NVMe, 1 MB buffers)	3
20M	F = 8,192 (NVMe, 1 MB buffers)	3
25.1M	F = 8,192 (NVMe, 1 MB buffers)	3
31.6M	F = 8,192 (NVMe, 1 MB buffers)	3
39.8M	F = 8,192 (NVMe, 1 MB buffers)	3
50.1M	F = 8,192 (NVMe, 1 MB buffers)	3
63.1M	F = 8,192 (NVMe, 1 MB buffers)	3
79.4M	F = 8,192 (NVMe, 1 MB buffers)	4
100M	F = 8,192 (NVMe, 1 MB buffers)	4

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Query Processing
Why can one question be answered by plans whose costs differ by a factor of ten thousand, and what does each operator force the engine to do?
$∣ build ∣ > M^{2} / B (recursion begins)$
|build| = $N$
Read it in place →
Query Processing
Why can one question be answered by plans whose costs differ by a factor of ten thousand, and what does each operator force the engine to do?
$N \leq \frac{M ^{2}}{B} (one merge pass), F = M / B$
M / B (blocks of memory) = $F$
Read it in place →
Execution Engine Runtime
Once a query plan is chosen, why does the machine still sit idle, and what does each mechanism of a query runtime pay to buy that idle time back?
$spill amplification = 1 + ⌈ lo g_{k} (S_{task} / B)⌉$
k (merge fan-in) = $F$ · S_task / B = $N / M$
Read it in place →
Memory & Resource Management
Who is allowed to hold how much memory, for how long, and what happens to the work when the answer is less than it asked for?
$N \leq M^{2} / B$
N (build side) = $N$ · M / B (partitions) = $F$
Read it in place →
Memory & Resource Management
Who is allowed to hold how much memory, for how long, and what happens to the work when the answer is less than it asked for?
$⌈ lo g_{M / B - 1} (N / M) ⌉ merge passes$
M/B − 1 = $F$
Read it in place →