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

Figure 1. Hash partitioning makes one pass over a too-big-for-RAM file using a small RAM workspace. A page streams into the input slot, each row hashes by h(user_id) % B and routes to one of ~B output buffers, and a full buffer flushes to its partition file on disk. Rows with the same key always land in the same partition, so later stages can sort, join, or group one partition at a time. Cost is below; see also the IO Cost Summary.

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)   // spill a full buffer
            output_buffers[p].clear()

    Phase 2: Flush whatever is left
    flush_all(output_buffers)

Example Problem: Break Big Problem Into Small Problems

The Spotify Listens table is ten times the size of RAM, so brute force is out. Slice it into RAM-sized pieces and process each one independently.

64GB

Spotify Listens table

6.4GB

Available RAM

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. That is the whole point: the cost is linear in N. A RAM-blind join of two big tables is quadratic, O(N²); one partitioning pass makes every downstream sort, join, and group-by linear instead, because each partition now fits in RAM and is processed once. The full cost comparison against the join algorithms is on the IO Algorithms page.