Explain how a relational engine sorts a data set that does not fit in the memory available to the sort operator. Describe the algorithm and what determines its I/O cost.

## The problem Sorting is a *blocking* operator: it cannot emit its first output row until it has consumed all input, because any not-yet-seen row could belong first. If the whole input fits inside the sort operator's memory budget, the engine does an ordinary in-memory sort (typically quicksort, or an insertion sort for tiny inputs) and streams the result out. The interesting case is when it does not fit — the engine must sort correctly using bounded memory plus temporary disk space. The standard answer, essentially unchanged since the 1970s, is **external merge sort**. ## Phase 1 — run generation The operator reads input rows until its memory is full. It sorts that in-memory chunk and writes the sorted chunk to a temporary file. That sorted chunk is called a **run**. Then it clears memory and repeats. When the input ends, disk holds a set of sorted runs whose concatenation is the whole input. If the input is N pages and memory is M pages, this yields about `N/M` runs, each about M pages long. Some engines use **replacement selection** instead of sort-then-dump: maintain a heap of M pages of rows and continuously emit the smallest row that is still ≥ the last emitted one, refilling from input. On random input this produces runs averaging **2M** — half as many runs — and on already-nearly-sorted input it can produce one giant run. The trade-off is worse cache behaviour and more complex code, so several modern engines prefer simple quicksorted runs. A detail that matters in practice: what is written is not the base table rows but the **tuples the plan carries** — the sort key plus whatever columns downstream operators need, plus per-row overhead. Projecting away unused wide columns before the sort directly shrinks N. ## Phase 2 — merging Merging takes K sorted runs and produces one sorted stream. Memory is divided into one input buffer per run plus one output buffer, so the **fan-in** F is roughly `M / buffer_size - 1`. The operator reads the first block of each run, puts each run's current head row into a small heap (a *tournament tree* / loser tree of size K), and repeatedly pops the global minimum, refilling from whichever run it came from. Each output row costs one heap operation, O(log K) comparisons. If `K <= F`, one merge pass suffices and the merged output can be **pipelined** straight into the parent operator — no extra write. If `K > F`, the operator merges F runs at a time, writing longer intermediate runs, and repeats. The number of merge passes is `ceil(log_F(N/M))`. ## The cost formula Total page I/O is approximately: `2 * N * (1 + ceil(log_F(N/M)))` The leading `2 * N` is the run-generation write plus the first read; each further pass costs another read and write of the whole data. CPU cost is `O(N log N)` comparisons overall, and comparison cost is not free — sorting on a long text column with a locale-aware collation can cost more than the I/O. The practical shape of this: with even a modest budget and a fan-in in the tens or hundreds, `log_F(N/M)` is 1 for almost any realistic data size. So the honest rule of thumb is that a spilling sort writes and reads the data roughly **twice**, and only truly enormous sorts with tiny memory reach three or more passes. This also explains a counter-intuitive tuning fact: doubling the memory budget of a spilling sort rarely halves its time, because you were already at one merge pass. The big win is either avoiding the spill entirely or avoiding the sort entirely. ## Ways to avoid the sort - **Ordered access path.** Scanning an index whose key matches the required order supplies sorted rows directly; the sort operator disappears from the plan. This is the single biggest lever for ORDER BY on hot paths, at the cost of maintaining the index and, for non-covering indexes, random I/O to fetch the rest of the row. - **Order already established upstream.** A merge join or a sort-based aggregate leaves its output ordered on the join/group key; a later operator needing that same order can reuse it. - **Top-N.** If only the first few rows are wanted, the engine keeps a bounded heap instead of sorting everything. - **Partial sort / incremental sort.** If input is already sorted on a prefix of the required key, the engine sorts only within each group of equal prefix values, which bounds memory and starts producing rows early. ## Interview signals A strong answer names both phases, says what determines the number of runs (memory) and the number of passes (fan-in), gives the ~2N-per-pass cost intuition, and finishes with the observation that the fastest external sort is the one that never runs, because an index or an upstream operator already delivered the order.