Sorted runs and merge structures
Why is distributed sort a sampling problem?
An external sort sorts data bigger than memory: it writes sorted runs as big as memory, then merges them, F runs at a time. The operator and its pass arithmetic belong to query processing; on modern hardware F is so large that one merge pass suffices. What this group adds is the structure underneath: what sets F, and why the same merge loop runs half the stack.
What actually binds is the merge's I/O pattern
Raising F cuts passes, but it shrinks each stream's buffer. A buffer below the medium's efficient transfer size turns one sequential stream into random I/O. So F is pinned by buffer ≥ efficient read size, that is F ≤ M ÷ efficient_read_size. On a spinning disk with a 1 MB efficient read this gave F in the dozens. On NVMe with deep queues and 128 KB reads it gives F in the thousands.
There is also a Little's Law reading of the same thing. Little's Law says: the amount of work in flight equals throughput multiplied by latency. To keep a device busy with F concurrent streams you need F × buffer ≥ bandwidth × latency. The bandwidth-delay product and the merge buffer budget are the same quantity. In words: you need as many bytes in flight as the device can move during one wait.
Distributed sort is a partitioning problem
A global merge would send all data through one coordinator, so nobody does that. The universal pattern (the TeraSort benchmark, Spark's RangePartitioner, every shuffle-based ORDER BY) is to range-partition first, sort each partition independently, and define the global order as the concatenation of the partitions (the operator). The cost moved rather than vanished: range partitioning needs boundaries, and boundaries need a sample of the key distribution.
The failure mode is skew. Boundaries drawn from an unrepresentative sample hand one task ten times the work, and because a sort's runtime is the maximum over its tasks, one bad boundary sets the duration of the whole stage. Spark draws the boundaries by reservoir sampling per partition: randomization stands in for a coordinated global histogram.
The merge is data engineering's universal primitive
| Operation | What it merges |
|---|---|
| External sort | sorted runs |
| LSM compaction | SSTables |
| Iceberg / Delta compaction | data files |
| Merge-on-read | a delta applied to a base |
| CDC apply (change data capture) | a change stream into a snapshot |
| "Latest wins" deduplication | versions, with a tiebreak |
Every one is the same loop with a loser tree at the top, and the cost of every one is N log k. If you internalize one thing from this group, it should be that these are not analogous operations. They are the same operation with different retention policies for the losing record.
The merge join is this loop over two inputs: O(n + m) time, O(1) memory, and no "fits" condition, so it degrades gracefully where a hash join falls off a cliff.
Interesting orders: order as an asset
One established order can satisfy a merge join, a GROUP BY, a DISTINCT, a window function and a top-n at the same time (sort avoidance is the optimizer's search for it). A bucketed-and-sorted table is that idea made physical: pay the sort once at write time and share its cost over all later queries. The break-even is simple:
- sort_cost
- — paid once: a sort, a compilation, a plan
- saving_per_query
- — what each later query, row or execution saves
Example. If sorting costs 600 seconds once, and each query saves 40 seconds, then after 600 / 40 = 15 queries the sorted layout has paid for itself.
The constraint nobody escapes
A table can be physically sorted exactly one way. Every extra order you want is either a secondary structure (with its own write amplification) or a sort at query time. This is the hardest constraint in physical design, and the reason Z-ordering exists: it buys mediocre clustering in several dimensions by giving up good clustering in any one.