BigSort: Sorting TBs of Data with GBs of RAM

Concept. BigSort uses external merge-sort. It sorts a table larger than RAM by reading RAM-sized chunks, sorting each chunk in memory, writing each sorted chunk to disk, then merging the sorted chunks.

Intuition. To sort a 64 GB Listens table by rating on a 6.4 GB machine, read 6.4 GB at a time, sort each chunk in RAM, write each sorted chunk back, then merge the 10 sorted chunks. Cost: read every page once and write every page once per pass.

How External Merge Sort Uses Memory

External merge sort as a memory model: pages stream from disk (green, persistent) through a small four-page RAM box (red, volatile) and back. Phase 1 reads four pages, quicksorts them, and writes a sorted run; Phase 2 reads the head of each run and emits the smallest, merging into one sorted file. Tiles are pages shaded light to dark by sort key.

Figure 1. Phase 1 reads four pages into memory, quicksorts them in place, and writes the pages back as one sorted run, repeating until the file becomes a set of sorted runs. Phase 2 keeps the head page of each run in memory, repeatedly selects the smallest remaining value, and writes it to the output to merge the runs into one sorted file. Each tile is a page shaded by its sort key, light for small and dark for large. The red box is RAM (volatile). The green is disk (persistent).

Interactive: move every page yourself

Sort 550 values across 58 pages with only a few pages of RAM. Each value is shaded by its rank, so a sorted run reads as a smooth light-to-dark gradient and the raw input reads as noise. Press Play to walk the four stages, or use the tabs to jump between the unsorted input, the Phase 1 sorted runs, and the two merge passes down to one sorted file.

Figure 2. 550 values across 58 pages, shaded by rank. Play steps through Phase 1 run generation and the merge passes that produce one sorted file.

The BigSort Algorithm (aka External Sort)

Core Idea

  1. Divide: Create sorted runs that fit in memory.

  2. Conquer: Merge those sorted runs into your final output.

Algorithm · BigSort

BigSort(file, B):                 // B = total RAM pages available

    Phase 1: Create sorted runs
    runs = []
    while not EOF:
        chunk = read(B pages)
        sort(chunk)               // quicksort in RAM
        write(chunk to run_i)
        runs.add(run_i)

    Phase 2: Merge runs
    while |runs| > 1:
        next_runs = []
        for i = 0 to |runs| step B:
            batch = runs[i : i+B]     // merge up to B runs per pass
            merged = KWayMerge(batch)
            next_runs.add(merged)
        runs = next_runs
    return runs[0]

Why Sort?

Sorting is the backbone of a database. Every ORDER BY, every range scan on a B+Tree, every sort-merge join, every LSM compaction starts here. PostgreSQL, BigQuery, Spark all run the same operation underneath. Get sort right and the rest of the engine gets fast.

Example Problem: Break Big Sort Into Small Sorts

64GB

Unsorted table

6.4GB

Available RAM

SOLUTION. Apply BigSort to this 10× mismatch: split into 10 sorted runs of 6.4 GB each (Phase 1), then a single 10-way merge combines all 10 runs into the fully sorted 64 GB file (Phase 2). Single merge pass, so cost is 4N IOs total.

Cost Analysis

Reference table of per-pass IO costs: BigSort reads and writes every page once per pass at C_r times N plus C_w times N and grows with the number of merge passes; hash partitioning is a flat 2N single pass.

Figure 3. BigSort reads and writes every page once per pass. Additional merge passes add additional read and write costs.

Each pass reads and writes every page once, so a pass costs 2N (C_r×N + C_w×N). Phase 1 builds the sorted runs in one pass; Phase 2 merges, and each merge pass folds up to B runs into one, so it takes ⌈log_B(N/B)⌉ merge passes. The total is 2N × (1 + ⌈log_B(N/B)⌉), which is two N times a logarithmic number of passes, so BigSort is O(N log N) in IO, not linear. The familiar 4N is just the single-merge-pass case (small data, where every run fits in one merge); treat it as a best-case approximation, not the general cost. Hash partitioning, by contrast, is a single shot at a flat 2N. The full side-by-side against the join algorithms is on the IO Algorithms page.

In practice: runs of ~2B

The simple version above writes one RAM-sized run per chunk, giving ⌈N/B⌉ runs. Real systems do better with replacement selection: the input streams through an in-memory heap of B pages, and each time the smallest qualifying key is written out, a new page takes its slot. Incoming keys that are still larger than the last one written keep extending the current run, so a run grows to about 2B pages on average instead of B. That roughly halves the run count to ⌈N/2B⌉ and can save a merge pass. The colab and exam cost equations use this ⌈N/2B⌉ form, so an exam cost is 2N × (1 + ⌈logB(N/2B)⌉).

Sorting is half the big-data toolkit. The other half is the join, and the first join algorithm reuses exactly these RAM-sized blocks.