Sort-Merge Join: When Order Matters

Concept. Sort-merge join sorts both tables on the join key, then walks them in lockstep, emitting matching rows wherever the keys agree.

Intuition. When you need to join Users to Listens by user_id and one or both is already sorted (or you have to sort anyway), sort both, then walk them like merging two sorted lists. Mickey's Users row meets Mickey's Listens rows at the same point in the walk.

The Sort-Merge Join Algorithm

Sort both tables on the join key with BigSort, then walk them in lockstep with two pointers, matching as you go.

Sort-Merge Join: after Phase 1 BigSort, both R and S are sorted on the join key. Phase 2 walks both tables in one pass with two pointers, emitting matched groups as it goes.

Figure 1. Sort-Merge Join, R ⋈ S on user_id (Phase 2 shown). Phase 1 (not shown) BigSorts both R and S on the join key (see the big sort page); Phase 2 walks the two sorted runs with two pointers, emitting every pair in a matching key group and advancing the smaller side otherwise, here user_id 7 → 2, 13 → 2, 42 → 3, 99 → 1, total 8 rows. A key on one side only emits nothing (inner join); a key with m matches on one side and n on the other emits the m × n cross-product for that group. The output comes out already sorted on the join key, so a following operator that wants order pays no extra sort. Best case is P(R) + P(S) + OUT for a single linear pass per run (plus the two Phase-1 BigSort costs); the worst case is O(P(R) × P(S)) + OUT when one key dominates and the merge degenerates into a per-key cross-product, and OUT itself can dominate when match rates are high.

Algorithm · Sort-Merge Join

SortMergeJoin(T1, T2, key):           // assume |T1| < |T2|

    Phase 1: Sort both tables on the join key
    S1 = BigSort(T1, key)
    S2 = BigSort(T2, key)

    Phase 2: Walk both runs in lockstep
    i = 0, j = 0
    while i < |S1| and j < |S2|:
        if S1[i].key < S2[j].key: i++
        elif S1[i].key > S2[j].key: j++
        else:                          // keys match
            output all pairs (S1[i..i'], S2[j..j'])
            where S1[i..i'].key = S2[j..j'].key
            i = i'+1, j = j'+1

Multi-Table Sort-Merge Joins

Three-Way Join: Users, Listens, Songs

Sequential Approach

Algorithm · Three-Way Join

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

Next

IO Cost Summary → The reference equations for every algorithm in this module, applied to concrete Spotify-scale scenarios.