Sort-Merge Join: When Order Matters

Concept. Sort-merge join sorts both tables on the join key, then scans them in lockstep and emits matching rows for equal keys.

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 scans the two sorted runs with two pointers. Equal keys form a matching key group, and the operator emits every pair in the group. Unequal keys advance the smaller side. The example advances through user_id 7 → 2, 13 → 2, 42 → 3, 99 → 1, total 8 rows. A key that appears on only one side emits nothing under inner join semantics. A key with m matches on one side and n on the other emits the m × n cross-product for that key. The output stream stays sorted on the join key, so a downstream operator that requires that order does not add a sort. Best case is P(R) + P(S) + OUT for one linear scan per run, plus the two Phase-1 BigSort costs. Worst case is O(P(R) × P(S)) + OUT when one key dominates and the merge performs a per-key cross-product. OUT 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