BigSort: Sorting TBs of Data with GBs of RAM

BigSort for Massive Data

Merge Sort Revisited

When your data's small enough to fit in RAM, merge sort's a neat trick: divide the array, sort the pieces, and merge them back together. But when you're dealing with data that dwarfs your memory, you need a bigger plan. Enter BigSort, or External Sort, which scales this idea to handle data that laughs at your RAM limits.

Interactive BigSort Animation

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.

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-1:
            batch = runs[i : i+B-1]   // B-1 input buffers + 1 output buffer
            merged = KWayMerge(batch)
            next_runs.add(merged)
        runs = next_runs
    return runs[0]

Result: Fully sorted file
Cost: C_r×N + C_w×N per pass
Key Property: Handles any file size with limited RAM

Why Sort?

Sorting isn't just an academic exercise. It's the backbone of operations in databases and big data systems. Whether you're running a query in PostgreSQL, BigQuery, or Spark, sorting is how you get ordered results, and it's crucial for performance and efficiency.

Example Problem: Break Big Sort Into Small Sorts

SOLUTION: Two-Phase Approach

Phase 1: Split → Create sorted runs

• Load 6.4GB chunks, quicksort each, write to disk.

• Result: 10 sorted runs of 100 pages each.

Phase 2: Merge → Combine using priority queue

• Load the first page from each of the 10 runs.

• Output minimum values, refill buffers as needed.

• Result: Fully sorted 64GB file.

Cost Analysis

For detailed IO cost formulas, see IO Cost Reference.

BigSort vs Hash Partitioning: Cost Intuition

Hash Partitioning: Always 2N IOs

• Single pass through data—read once, write once to partitions.

• Cost stays constant regardless of data size.

BigSort: Variable cost—grows logarithmically

• Multiple passes needed as data gets bigger.

• More data → more sorted runs → more merge passes required.

• Small data (fits in few runs): ~4N IOs.

• Large data (many runs): ~6N, 8N, 10N IOs...

Why the difference? Hash Partitioning distributes data in one shot, but BigSort must repeatedly merge until everything is sorted.

Key Takeaways

1. Divide and Conquer: Split large sorts into small sorts, then merge; Sort TB of data with GB of RAM.

2. Scalable Cost: Works for any big data size with fixed RAM.

3. Foundation of Big Data: This is how PostgreSQL, BigQuery, Spark handle ORDER BY.