Hash Partitioning: Divide and Conquer

Concept. Hash partitioning splits a too-big-for-RAM table into N partitions by hashing a key. Each partition fits in RAM and supports independent processing.

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 listen from Mickey maps to the same partition regardless of input order.

The Hash Partitioning Algorithm

Core Idea

Break the data into B smaller partitions, each chunk holding rows for a subset of keys.

Hash partitioning shown as DISK input on the left, a small fixed RAM buffer 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.

Figure 1. Hash partitioning makes one pass over a too-big-for-RAM file using a small, fixed RAM buffer: one input slot plus one output buffer per partition. A page streams into the input slot, each row hashes by h(user_id) % B and routes to one of ~B output buffers. The instant any buffer fills, it flushes to its partition file on disk and is cleared, so RAM never holds more than that fixed set of buffers no matter how large the input. Partitions are stored on disk, not in memory: the full partitions live on disk, while only the small fixed RAM buffer is resident at any point in time. Rows with the same key always land in the same partition, so later stages can sort, join, or group one partition at a time. See the IO Cost Summary for the cost breakdown.

Algorithm · Hash Partitioning

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

    Phase 1: Stream rows into per-bucket buffers
    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)   // flush a full buffer
            output_buffers[p].clear()

    Phase 2: Flush whatever is left
    flush_all(output_buffers)

Cost

One read of every page and one write of every page: C_r×N + C_w×N, which is 2N IOs for C_r = C_w = 1. The key point: the cost is linear in N.