Sort spill, and choosing the operator by its tail

Why does the slower sort survive a bad estimate where hash fails?

Sort spill, and the comparison that decides operator choice

External sort: generate runs of size M, write them sequentially, and merge them with fan-in F = M/B. The number of passes is ⌈log_F(N/M)⌉ (see the table in Memory grants and reservations per operator).

One structural difference from hash is decisive:

	Hash	Sort
Fitting requirement	each partition must fit	none, only one buffer per merge input
Skew sensitivity	structural failure on a hot key	affects comparison cost, not structure
Degradation shape	cliff, then non-convergence	logarithmic, monotone
One-pass capacity	`M²/B`	`M²/B` (same arithmetic)
Byproduct	none	output is ordered, which downstream may need anyway

Hash is faster in memory and structurally fragile outside it. Sort is slower in memory and cannot fail. So choosing an operator under uncertainty is not a question of which is faster. It is a question of which one degrades well. And Rationing established that the size estimate is log-normal with a heavy right tail.

With a heavy-tailed input-size estimate, choose the algorithm with the better tail, not the better mean.

This is "the tail matters more than the average" applied to algorithm selection instead of load. It is the real reason sort-merge join survives in every mature engine despite losing the in-memory benchmark. It also means the optimizer's choice of join algorithm is really a bet on its own cardinality estimate. That is a coupling between the optimizer and the memory manager that neither one's documentation usually admits.

One-line compression: sort never requires anything to fit, which is why the slower algorithm is the one that survives a bad estimate.