Plan a sort

Grouping (all rows with the same key together, in any order) is strictly cheaper than order, and the two are routinely confused. If only grouping is needed: use hashing, not a sort.

A clustered layout, an index scan, an earlier merge join, an LSM-tree's read order, a bucketed table. If the data already arrives in the needed order: use it. Check before buying.

One sort order can serve several operators: an order by (a, b) also satisfies a requirement on a alone, and a column fixed to a constant can be ignored. If one candidate order satisfies two or more requirements: sort. If exactly one: compare it directly with the hash alternative.

With N bytes of data and M of memory: if N fits, sort in memory. Otherwise passes = 1 + ⌈log_F(N ÷ M)⌉, where the fan-in F = M ÷ buffer size B; a third pass is needed only when N > M²/B, and a normal two-pass sort does about 4N of I/O. With 16 GB of memory and 8 MB buffers, a third pass starts only past 32 TB. Choose the fan-in on purpose: a larger one means fewer passes but more comparisons per record.

If rows are wide or keys are strings with language-aware collation: convert each key once into bytes that compare correctly with a plain byte comparison, and sort compact (key prefix, pointer) pairs instead of whole rows, unless gathering the rows afterwards would be random I/O.

Sample the data to choose the boundaries between machines, never by taking the first records of input that is already ordered. Size the sample for the imbalance you can accept. Check for one key appearing more than N ÷ machines times: it defeats range partitioning exactly as it defeats hashing.

If data is already ordered by a prefix of the key (sorted by day, needing day then customer): sort each segment separately instead of the whole input.