BigSort: Sorting When Nothing Fits

BigSort for Massive Data

Remember Merge Sort?

Small data (fits in RAM): Split array → Sort pieces → Merge sorted pieces
Big data (doesn't fit): Same idea! Split file → Sort runs → Merge sorted runs

BigSort (also called External Sort) scales merge sort to handle data that's way bigger than RAM.

Interactive BigSort Animation

The BigSort Algorithm

Core Idea

1. Divide: Create sorted runs that fit in memory

2. Conquer: Merge sorted runs into 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

Example Problem: Break Big Sort Into Small Sorts

Strategy: When you need to sort data that's too big to fit in memory, break it into small pieces you can sort, then merge the sorted pieces back together. This divide-and-conquer approach makes the impossible possible.

Why Sort?

-- These queries need sorted data:
SELECT * FROM Users ORDER BY last_active DESC;
SELECT DISTINCT user_id FROM Listens;
SELECT * FROM Songs ORDER BY play_count DESC LIMIT 100;

-- Sorting enables:
-- 1. ORDER BY clauses
-- 2. Efficient DISTINCT
-- 3. Sort-merge joins
-- 4. Rank/percentile calculations

Two-Phase Execution: Applying the Algorithm

-- PROBLEM: Need to sort this massive table
SELECT * FROM Listens ORDER BY user_id;
-- But 64GB data won't fit in 6.4GB RAM for sorting!

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 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.

Use Cases & Real-World Systems

ORDER BY Queries

-- BigQuery uses BigSort for massive ORDER BY
SELECT * FROM billion_row_table ORDER BY timestamp;
-- Automatically partitions and sorts across many machines

PostgreSQL

-- PostgreSQL work_mem setting controls when to use BigSort
SET work_mem = '1GB';
SELECT * FROM large_table ORDER BY created_at;
-- Uses BigSort if data > work_mem

Distributed Systems

• Spark: Sorts partitions using BigSort algorithm

• MapReduce: Shuffle phase uses BigSort to merge mapper outputs

• BigQuery: Massively parallel BigSort across thousands of machines

Key Takeaways

1. Divide and Conquer: Split large sorts into small sorts, then merge

2. Two-Phase Process: Split creates sorted runs, merge combines them

3. Scalable Cost: 2N × passes - works for any data size with fixed RAM

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

5. Memory Efficient: Sort TB of data with GB of RAM

The Punchline: When in doubt, sort it out! Sorted data enables countless optimizations downstream.