Hash Partition Join

Concept. Hash partition join joins two tables that do not fit in RAM. It hashes both tables on the join key into matching partitions, then joins each partition pair independently.

Intuition. When both Users and Listens exceed RAM, hash user_id % 16 to split each table into 16 partitions. Mickey's Users row and Mickey's Listens rows map to the same partition, so a join can run on partition 1 with partition 1 in RAM, then 2 with 2, and so on. Cost: 3(N+M) IOs.

When Both Tables Don't Fit in Memory

The query we want to run:

SELECT u.name, l.song_id, l.rating
FROM Users u
JOIN Listens l ON u.user_id = l.user_id;

If Users is 100 GB and Listens is 800 GB but RAM is only 64 GB, neither side fits in memory. BNLJ would re-scan the larger side once per outer block, which would waste I/Os.

Hash Partition Join: The Solution

Core Insight

Partition both tables using the same hash function on the join key. Rows from each side with the same key land in the same partition number, so matching can happen one partition at a time, in RAM.

R (Users) on disk, 4 rows, one input to phase 1.
user_id	name
7	Mickey
13	Minnie
42	Pluto
99	Daffy

S (Listens) on disk, 8 rows, the other input to phase 1.
user_id	song_id
42	100
7	200
13	100
42	300
7	100
13	200
42	400
99	500

Phase 1 writes R's rows to disk in three partitions by h(user_id), so a user_id always lands in the same partition number. R partition 0 holds 2 rows, each written user_id then name.
R₀ · disk (h → 0)
42 · Pluto
99 · Daffy

R partition 1, 1 row.
R₁ · disk (h → 1)
7 · Mickey

R partition 2, 1 row.
R₂ · disk (h → 2)
13 · Minnie

Phase 1 hashes S with the same h, so matching keys meet in the same partition pair. S partition 0, 4 rows, each written user_id then song_id.
S₀ · disk (h → 0)
42 · 100
42 · 300
42 · 400
99 · 500

S partition 1, 2 rows.
S₁ · disk (h → 1)
7 · 200
7 · 100

S partition 2, 2 rows.
S₂ · disk (h → 2)
13 · 100
13 · 200

Phase 2 loads each partition pair into RAM and joins it there, so no row is ever compared against a partition it cannot match. Read each column down: the pair, how it is joined, how many rows it outputs, and which keys matched. The three partitions together output 8 rows, one per S row.
R₀ ⋈ S₀ · in RAM	R₁ ⋈ S₁ · in RAM	R₂ ⋈ S₂ · in RAM
build hash on R₀, probe with S₀	build hash on R₁, probe with S₁	build hash on R₂, probe with S₂
→ 4 output rows	→ 2 output rows	→ 2 output rows
user_id 42 → 3 matches · user_id 99 → 1 match	user_id 7 → 2 matches	user_id 13 → 2 matches

Figure 1. Hash Partition Join, R ⋈ S on user_id. Phase 1 hashes both tables with the same function so matching user_ids always land in the same partition number. Phase 2 joins each (Rᵢ, Sᵢ) pair independently in RAM, building a hash table on R and probing with S, three parallelizable joins that yield 4 + 2 + 2 = 8 rows. Best-case cost is 3(N+M) + OUT (read each table, write partitions, read them back, write the output). The worst case is hash skew, where a hot key overflows a partition past RAM and recursive re-partitioning or a sort-merge fallback adds another pass.

Algorithm · Hash Partition Join

HashPartitionJoin(T1, T2, key):       // assume |T1| < |T2|
    B = choose_partition_count(T1, RAM) // allow space for the build hash table

    Phase 1: Partition both tables on the same hash
    for row in T1: write to T1_p[h(row.key) % B]
    for row in T2: write to T2_p[h(row.key) % B]    // same hash!

    Phase 2: Join matching partitions in RAM
    for i in 0..B-1:
        HT = hash_table(T1_p[i])      // build on the smaller side
        for row in T2_p[i]:           // probe with the larger
            if HT[row.key]: output matches

Multi-Table Joins

Joining Three Tables: Users, Listens, Songs

Algorithm · Three-Way Join

ThreeWayJoin(U, L, S):              // assume |U| < |L| < |S|
    temp   = HPJ(U, L, "user_id")   // U ⋈ L
    result = HPJ(temp, S, "song_id")   // temp ⋈ S
    return result

Handling Skew in HPJ

Memory requirement: the build-side hash table must fit in RAM. The probe side can stream through it, even when that probe partition is large.
Many distinct keys in an oversized build partition: another hash function can split the partition further.
One repeated hot key: rehashing keeps every copy together. Process that key separately, for example by comparing memory-sized blocks with the matching probe rows. Extra passes and a large result can dominate the cost.