7.2 External Sorting, Multi-Way Merge, and Merge Join

The ledger to be sorted has grown so large it no longer fits in memory. The archivist splits the problem into batches of sorted segments stored on disk.

When the data to be sorted exceeds the operator's memory budget, the executor writes portions of sorted runs to temporary storage and performs a multi-way merge. The core of external sorting isn't switching to a different sorting algorithm; it's ensuring that each pass reads and writes data in a sequential manner, and using a limited number of buffers to control the merge fan-in.

Learning Objectives

• Derive the run generation and merge passes;
• Understand the relationship between memory, fan-in, and temporary I/O;
• Distinguish between full sort, top-N, and incremental sort;
• Explain sort-based distinct and aggregation operations in relation to merge join;
• Write a bounded, duplicate-aware k-way merge.

Phase 1: Generate sorted runs

Given input N pages, the sort memory can hold approximately M pages:

Read up to M pages
Sort records in memory
Write one sorted run
Repeat

Initial run count ≈ ceil(N / M)

Actual memory is divided among tuples, pointers/keys, comparison state, and the allocator, so you can't precisely derive M by dividing configured bytes by row width. Variable-length rows and abbreviated keys also affect capacity.

Replacement selection may produce sorted runs longer than memory under random input, but modern engines employ strategies such as quicksort, radix sort, replacement selection, or others, depending on implementation specifics.

Phase 2: k-way merge

With B buffer pages, a typical configuration uses B-1 input buffers plus one output buffer, yielding a fan-in of approximately B-1. In practice, this is further constrained by file descriptors, prefetching, parallelism, and per-run metadata overhead.

pass 0: R initial runs
pass 1: ceil(R / k) runs
pass 2: ceil(previous / k) runs
...

The number of merge passes is approximately ceil(log_k R). Each complete materialized pass reads N pages and writes N pages, resulting in about 2N page I/O operations. If the final result is directly pipelined to the parent operator, the full write operation can be avoided, this decision is ultimately determined by the execution plan.

External sorting is not O(1) space: it consumes O(memory budget) of RAM and requires temporary disk space that may approach the input or output volume. Multi-pass processing and compression can alter the peak memory usage.

A Correct k-way Merge Skeleton

The following program assumes that each input file contains one integer per line, and that the integers are sorted in ascending order:

from __future__ import annotations

from contextlib import ExitStack
import heapq
from pathlib import Path
from typing import TextIO


def read_integer(handle: TextIO) -> int | None:
    line = handle.readline()
    if line == "":
        return None
    return int(line.strip())


def merge_integer_runs(inputs: list[Path], output: Path) -> None:
    if output in inputs:
        raise ValueError("output must not overwrite an input run")

    with ExitStack() as stack:
        handles = [
            stack.enter_context(path.open("r", encoding="utf-8"))
            for path in inputs
        ]
        destination = stack.enter_context(output.open("x", encoding="utf-8"))

        heap: list[tuple[int, int]] = []
        for run_id, handle in enumerate(handles):
            value = read_integer(handle)
            if value is not None:
                heapq.heappush(heap, (value, run_id))

        while heap:
            value, run_id = heapq.heappop(heap)
            destination.write(f"{value}\n")

            next_value = read_integer(handles[run_id])
            if next_value is not None:
                heapq.heappush(heap, (next_value, run_id))

The heap uses (value, run_id), which allows comparison even when values are equal, ensuring that duplicates are preserved. A production implementation would also require buffered binary I/O, record serialization, checksums, temporary file cleanup, disk full handling, a stable tie-breaker, and a multi-pass fan-in limit.

Double buffering and asynchronous prefetch

Each run can prepare an active buffer and a next buffer: while the CPU merges the current block, the I/O system prefetches the next block. This hides some latency, but is still constrained by storage bandwidth, queue depth, memory availability, and the scheduler.

When there are many input runs, allocating two large buffers per run can squeeze sort memory and reduce fan-in, requiring a careful overall trade-off.

Full sort is not always necessary

Top-N

SELECT item_id, value_cents
FROM vault_items
ORDER BY value_cents DESC, item_id DESC
LIMIT 100;

If no index provides direct ordering, the executor can maintain a bounded heap, retaining only the top N rows. Memory usage scales approximately with N, rather than sorting all rows. Still, the executor must scan the candidate input unless other access paths or partition pruning reduce the input size.

When the offset is large, the bounded heap might need to retain N + offset, increasing cost. Keyset pagination is better suited for stable deep pagination.

Incremental sort

If the input is already sorted by (a) and the goal is (a, b), the executor can sort the b values within each group of identical a values, without needing to store the entire input. The benefit depends on the prefix order and the sizes of the groups.

Index order

When the B+ tree index order aligns with the query order, the executor can output results directly from the index scan, avoiding an explicit sort. However, random heap fetches, index coverage, and the number of matching rows may still cause the optimizer to choose a scan followed by a sort.

DISTINCT and GROUP BY

On a sorted input, adjacent equal keys can be deduplicated or aggregated:

sort by group key
scan once
accumulate current group
emit when key changes

Hash aggregation can also achieve the same logical result and, when memory is insufficient, can partition and spill data. Which approach is better depends on group cardinality, input order, available memory, parallelism, and whether a subsequent ordered output is required.

"The larger the DISTINCT dataset, the more it must be externally sorted" is incorrect; the planner can use hash, sort, index uniqueness, or other operators to handle this.

Merge join

When both sides of a join are ordered by the join key, a merge join progresses linearly:

left.key < right.key  -> advance left
left.key > right.key  -> advance right
equal                 -> output Cartesian matches of both equal-key groups

This final point is crucial. If the left key equals 7 has 3 rows and the right key equals 7 has 4 rows, an inner join must produce 12 pairs. Simply advancing both pointers one step at a time would miss duplicate matches.

The inputs to a merge join can come from:

• an index or order-preserving scan;
• an explicit sort;
• an upstream operator that already maintains order.

If sorting both large tables before the join is required, the total cost may exceed that of a hash join. Conversely, if the output also needs to be ordered, the sort cost may be reused.

NULL equality, collation, outer join unmatched rows, and inequality joins all must be handled according to SQL semantics.

Observing Spill in PostgreSQL

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT item_id, value_cents
FROM vault_items
ORDER BY value_cents, item_id;

The planned Sort Method and Memory/Disk usage indicate whether a sort node will spill. work_mem represents the initial budget for each sort or hash operation, and it can be shared among parallel workers and multiple nodes within the same query. Therefore, it should not be directly set to "available server memory." The default value also depends on current configuration and should not be hardcoded to 4 MB.

Database-level temporary file counters can provide trend data, but they aggregate across multiple sessions and queries, making it impossible to attribute spilling to a specific execution plan. Combine this with log_temp_files, query statistics, and EXPLAIN analysis for more accurate insights.

I/O and Stability Boundaries

Insufficient temporary filesystem space can cause queries to fail. Multiple concurrent spills may compete for the same device. Sort comparisons are influenced by collation, data type, and operator behavior. ORDER BY key does not guarantee stable ordering within duplicate keys; pagination must include a unique tie-breaker. Whether a sort algorithm is stable is an implementation detail, and SQL does not guarantee the order of rows not explicitly included in ORDER BY. When output rows are large, sorting on a key plus a row reference allows for deferred materialization of the payload.

Acceptance Checklist

• [ ] Can estimate runs and passes based on N, M, and fan-in;
• [ ] Does not describe external sort disk space as O(1);
• [ ] Can explain why a top-N query might still scan the entire input;
• [ ] Merge join correctly handles duplicate groups;
• [ ] ORDER BY includes a unique tie-breaker;
• [ ] Spill testing simultaneously logs temp bytes, latency, concurrency, and device;
• [ ] Before modifying memory budget, computes per-node/per-worker scaling factors.

Chapter Summary

A hash index sacrifices key ordering to optimize equality lookups, while external sort uses runs and multi-way merging to construct order within limited memory. In the next chapter, we will integrate scan, join, sort, and aggregate operations into a single iterator/vectorized execution model, and explain how the optimizer selects operators and allocates resources.