Sorting Algorithms

Sorting is arguably the most fundamental operation in database systems. It appears everywhere: ORDER BY clauses, merge joins, sort-based aggregation, duplicate elimination, index construction, and B-tree maintenance. Understanding sorting in the database context is essential because database sorting has unique characteristics that distinguish it from general-purpose sorting.

The Database Sorting Challenge:

Unlike in-memory algorithm courses where we sort arrays of integers, database sorting faces distinct challenges:

1. Scale: Datasets often exceed available memory by orders of magnitude
2. I/O Cost: Disk access is millions of times slower than memory access
3. Variable-Length Records: Tuples aren't uniform sized integers
4. Key Extraction: Comparison keys must be extracted from tuples
5. Stability: Sometimes the original order of equal elements must be preserved

When data fits in memory, databases use efficient in-memory sorting algorithms. The choice of algorithm depends on data characteristics and hardware.

Common In-Memory Algorithms:

Quicksort: The default choice for many systems

• Average O(n log n), worst case O(n²)
• Excellent cache performance due to sequential access
• In-place (minimal extra memory)
• Not stable (equal elements may reorder)

Merge Sort: Used when stability is required

• Guaranteed O(n log n) time
• Stable (preserves order of equal elements)
• Requires O(n) extra space
• Good for linked structures

Radix Sort: For integer or fixed-width keys

• O(n × k) where k is key length in digits/bytes
• Can outperform comparison-based sorts for suitable data
• Not comparison-based—exploits key structure

Database-Specific Optimizations:

Key Normalization: Transform complex keys (variable-length strings, multiple columns) into fixed-length binary format that supports direct byte comparison. This enables:

• SIMD comparisons (compare 16-32 bytes at once)
• Radix-based sorting on normalized keys
• Elimination of expensive comparison functions

Pointer Sorting: For wide tuples, sort pointers rather than tuples:

• Keep tuples stationary in memory
• Sort array of (key, pointer) pairs
• Final pass reorders tuples according to sorted pointers
• Reduces data movement during swaps

Prefix Sorting: Store key prefix with pointer:

• Many comparisons resolved by prefix alone
• Only dereference pointer when prefixes are equal
• Trades memory for comparison speed

When data exceeds available memory, external merge sort is the dominant algorithm. It's elegant, predictable, and optimized for disk I/O patterns.

High-Level Algorithm:

External merge sort proceeds in two main phases:

Phase 1: Run Generation (Create Sorted Runs)

• Read as much data as fits in memory
• Sort it using an in-memory algorithm
• Write the sorted data as a "run" to disk
• Repeat until all input is processed
• Result: Multiple sorted runs on disk

Phase 2: Merge Runs

• Read portions of multiple runs simultaneously
• Merge them to produce larger sorted runs
• Repeat until only one run remains
• That final run is the sorted output

Understanding the I/O cost of external merge sort is crucial for query optimization. The cost depends on input size, memory, and data distribution.

Phase 1 (Run Generation):

• Read all N pages: N reads
• Write all N pages as runs: N writes
• Total: 2N I/O operations

Phase 2 (Merging):

• Each merge pass reads all data and writes merged runs
• Each pass: 2N I/O operations
• Number of passes: ⌈log_{M-1}(N/M)⌉

Total I/O Cost:

Total = 2N × (1 + ⌈log_{M-1}(N/M)⌉)
      = 2N × (1 + number_of_merge_passes)

Key Observations:

1. Memory matters dramatically: Doubling memory from M to 2M potentially eliminates an entire merge pass, halving I/O for large datasets.

2. The logarithm is forgiving: Even for huge datasets, merge passes remain small. Sorting 1TB with 1GB memory: log₁₀₀₀(1000000) ≈ 2 passes.

3. Base-case optimization helps: If data nearly fits in memory (N ≈ M), total cost approaches 4N (one run, one merge).

4. Read:Write ratio: External merge sort has 1:1 read:write ratio. SSDs with asymmetric read/write performance may prefer read-heavy algorithms.

The basic external merge sort generates runs of exactly M pages. Replacement selection is a technique that can produce runs of 2M pages on average for random data—potentially eliminating a merge pass entirely.

The Idea:

Instead of filling memory, sorting, and writing, we use a priority queue (min-heap) in memory:

1. Fill heap with initial tuples from input
2. Repeatedly:
   • Extract minimum tuple from heap, write to current run
   • Read next tuple from input
   • If new tuple ≥ last written: add to heap (extends current run)
   • If new tuple < last written: mark for next run (can't go in current run)
3. When heap empties of current-run tuples, start new run with marked tuples

Tuples that can extend the current run do so immediately; tuples that would break sort order are "saved" for the next run.

Why 2M on Average?

For uniformly random input, approximately half the new tuples read will be larger than the last written tuple and can extend the current run. This cascade effect produces runs averaging 2M tuples—double the basic algorithm.

When Replacement Selection Excels:

1. Partially sorted input: If input has runs of ascending values, replacement selection produces extremely long runs—potentially the entire file in one run!

2. Large memory: More heap capacity means longer average runs.

When It Underperforms:

1. Reverse sorted input: Worst case—each new tuple is smaller than all heap elements, producing runs of exactly M.

2. Modern SSD storage: The CPU overhead of heap operations may not be worth it when I/O is fast.

The merge phase offers numerous optimization opportunities beyond the basic algorithm.

1. Double Buffering (Prefetching):

While processing one buffer page, prefetch the next:

For each input run:
    Page A: currently being read by merge logic
    Page B: being prefetched from disk in background
    When A exhausted, swap A and B, start prefetching new B

This hides I/O latency by overlapping disk and CPU operations. Requires 2× memory for input buffers but dramatically improves throughput.

2. Read-Ahead for Sequential Runs:

Operating systems and disk controllers optimize sequential reads. Reading larger chunks (e.g., 64 pages instead of 1) reduces seek overhead and leverages disk prefetching.

3. Cascade Merge (Polyphase Merge):

For very large sorts with many initial runs, clever scheduling of merges can reduce total I/O. Instead of merging all runs at once (which limits merge order to M-1), cascade strategies merge subsets strategically.

4. Avoiding Final Write:

If the sorted output is consumed by a streaming operator (like merge join), we can avoid writing the final sorted run:

Pipeline: Sort → Merge Join

Optimization:
    - Perform sort, creating runs on disk
    - During final merge pass, pipe directly to merge join
    - No disk write for final sorted output
    - Saves N page writes

5. External Quick Sort:

An alternative to merge sort for external sorting:

1. Sample input to find good pivot
2. Partition into "smaller" and "larger" files
3. Recursively sort partitions

Can be faster when memory is very limited (fewer passes), but less predictable I/O patterns.

Modern systems exploit parallelism at multiple levels to accelerate sorting.

Intra-Operator Parallelism:

Parallelize within a single sort operation:

1. Parallel Run Generation:

• Partition input into P chunks
• Each thread sorts its chunk using in-memory sort
• Result: P sorted runs created in parallel

2. Parallel Merge:

• Multiple merge operations can run simultaneously
• Example: With 8 runs and 4 threads:
  • Thread 1: Merge runs 1-2 → run A
  • Thread 2: Merge runs 3-4 → run B
  • Thread 3: Merge runs 5-6 → run C
  • Thread 4: Merge runs 7-8 → run D
  • Then merge A, B, C, D

Distributed Sorting:

In distributed systems, sorting involves network shuffling:

1. Local Sort: Each node sorts its local data
2. Sample Exchange: Nodes exchange samples to determine global partition boundaries
3. Shuffle by Range: Tuples redistributed based on key ranges
4. Final Local Sort: Each node sorts received data
5. Concatenation: Range-ordered results form global sorted output

Challenges:

• Data Skew: If one range has much more data, that node becomes a bottleneck
• Network Bandwidth: Shuffling may transfer significant data across network
• Coordination Overhead: Barrier synchronization between phases

Many queries don't need a fully sorted result—they need only the top K elements (ORDER BY with LIMIT). This enables significant optimization.

Heap-Based Top-K:

For finding the K smallest (or largest) elements:

TOP_K(input, K):
    heap = MaxHeap(capacity=K)  // For finding K smallest
    
    for each tuple t in input:
        if heap.size() < K:
            heap.insert(t)
        elif t < heap.peek():  // t smaller than largest in heap
            heap.replace_max(t)  // remove max, insert t
    
    return heap.contents_sorted()

Complexity: O(n log K) instead of O(n log n) for full sort. When K << n, this is dramatically faster.

Memory: O(K) instead of O(n). For LIMIT 10 on a billion rows, we need space for only 10 tuples!

External Top-K:

For very large K that doesn't fit in memory, hybrid approaches work:

1. Two-pass algorithm:

   • First pass: Sample to estimate the K-th largest value threshold
   • Second pass: Collect all tuples above threshold, sort them, take top K

2. Priority queue with spillover:

   • Similar to replacement selection but maintaining top-K invariant

ORDER BY with OFFSET:

SELECT * FROM table ORDER BY col LIMIT 20 OFFSET 1000;

Unfortunately, OFFSET doesn't optimize well—we must find the top 1020 elements to discard 1000. For deep pagination, consider keyset pagination (WHERE col > last_seen_value) which can use indexes.