Hash Partitioning: Divide and Conquer

Concept. Hash partitioning splits a too-big-for-RAM table into N partitions by hashing a key, so that each partition fits in RAM and can be processed independently.

Intuition. When your Listens table is 64 GB but your machine has 6.4 GB of RAM, hash user_id % 16 to split Listens into 16 partitions of 4 GB each. Each partition fits, and Mickey's listens always land in the same partition no matter which one you read first.

The Hash Partitioning Algorithm

Core Idea

Break the data into B smaller chunks, each chunk holding rows for a subset of keys. This is not elegance, it is necessity when the table dwarfs RAM.

Hash partitioning shown as DISK input on the left, a small RAM workspace in the middle, and DISK partitions on the right. The source file is read one page at a time into a RAM input-buffer slot. Each row is hashed and routed to one of three colored output buffers. When a buffer fills, it flushes to its partition file on disk.

📋 ALGORITHM: Hash Partitioning

HashPartition(file, B, key):
    output_buffers[B]    // B output buffers + 1 input buffer

    for row in file:
        p = hash(row.key) % B
        output_buffers[p].add(row)
        if output_buffers[p].full:
            write(output_buffers[p] to dbfile_p)
            output_buffers[p].clear()

    flush_all(output_buffers)

    Result: B partitions, each ≈ N/B pages
    Cost: 2N IOs (read + write)
    Key Property: Same key always goes to same partition

Example Problem: Break Big Problem Into Small Problems

Strategy: Tackle oversized problems by slicing them into digestible segments. Hash partitioning exemplifies this divide-and-conquer tactic.

64GB

Spotify Listens Table

6.4GB

Available RAM

10×

Size Mismatch

Solution

Hash Partition!

Why Can't We Just Process It All?

When your data is ten times the size of your RAM, brute force isn't an option. You need a plan that respects your hardware's limits.

Two-Phase Execution: Applying the Algorithm

Here's how hash partitioning addresses our oversized data dilemma:

SOLUTION: Two-Phase Approach

Phase 1: Partition → Hash data into 100 manageable files

  • Apply hash(user_id) % 100 to each row

  • Result: 100 DBFiles, each ~640MB (fits in RAM!)

  • All data for each user stays in the same partition

Phase 2: Process → Each file independently

Cost Analysis

Hash Partitioning Cost: C_r×N + C_w×N

  • Read N pages from original file → C_r×N cost

  • Write N pages to B partitioned DBFiles → C_w×N cost

  • Total: C_r×N + C_w×N IOs for partitioning step

  • For C_r = C_w = 1: 2N IOs (typical case)

Additional Processing on Partitioned Files

After partitioning, each smaller file can be processed independently:

  • GROUP BY aggregation: Read each DBFile once → +C_r×N cost

  • Sorting within partitions: Read + write each DBFile → +(C_r×N + C_w×N) cost

  • Hash joins: Build hash tables from each DBFile → +C_r×N cost

Key Takeaways

  1. Divide and Conquer: Split big problems into small ones. Process TB of data with GB of RAM.

  2. Linear IO Cost: O(N) is much better than N²

  3. Foundation of Big Data: This is how Postgres, BigQuery, Spark, Hadoop work.

Next

BigSort → Sorting a table that doesn't fit in RAM uses the same divide-and-conquer trick, just on sorted runs instead of hash partitions.