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.

Figure 1. Hash partitioning makes one pass over a too-big-for-RAM file through a small RAM workspace. A page streams into the input slot, each row is hashed by h(user_id) % B and routed to one of ~B output buffers, and a full buffer flushes to its partition file on disk. The same key always lands in the same partition no matter when it appears, so each partition fits in RAM and the next stage can sort, join, or group them one 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.

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.