How Hash Join Chooses Build and Probe Sides: A Deep Dive
This article explains how Hash Join assigns build and probe sides, why the smaller table typically becomes the build side, how outer joins affect side selection, and the differences from Sort-Merge Join, with a concrete SQL example.
1. Typical Hash Join Workflow
In a Hash Join physical plan, the build side is the input that is read first and used to construct an in-memory hash table. The probe side is read afterward; each row's join key is hashed and looked up in that hash table to find matches.
For a query like A JOIN B ON A.id = B.id, the optimizer usually picks the smaller filtered table (e.g., B) as the build side.
Build Phase
Scan the build-side table (B), compute hash(B.id) for each row, and insert the mapping B.id → B row (or required columns) into the hash table. The hash table is organized into buckets; within each bucket an equality comparison of the actual key is still required because different keys can hash to the same bucket (hash collisions).
Probe Phase
Scan the probe-side table (A), compute hash(A.id), locate the corresponding bucket, compare keys, and output joined rows for each match. If one probe row matches multiple build rows, multiple result rows are produced.
Outer Join Handling
Left, right, and full outer joins need extra bookkeeping: they must record which build-side rows were matched, or emit NULL-extended rows for probe-side rows that find no match.
2. Build/Probe Roles Are Not Fixed to Left/Right
For inner joins the two inputs can be swapped; the optimizer decides based on statistics. Common patterns:
Small table build, large table probe – the most frequent choice.
Broadcast Hash Join – the small build-side table is broadcast to all nodes; each node probes its local partition of the large table.
Shuffle Hash Join – both sides are shuffled (repartitioned) on the join key; within each partition the smaller side becomes the build side and the other the probe side.
With outer joins, making the preserved side the probe side often simplifies streaming unmatched rows; if the preserved side is the build side, additional match-state flags are required.
3. Why the Build Side Is Usually Small
The build side must be materialized as a hash table in memory. An oversized build side can cause:
Memory exhaustion / OOM errors.
Hash table spilling to disk, degrading performance.
Increased garbage-collection pressure.
Excessive network and memory overhead in broadcast joins.
Therefore the optimizer evaluates: table size, post-filter row count, column width, join-key cardinality, broadcast hints, and memory limits when choosing the build side.
4. Difference from Sort-Merge Join
The terms build and probe are specific to Hash Join. Sort-Merge Join is described as “sort then merge”; it does not build a hash table but instead merges two sorted streams on the join key. Occasionally the outer input is called the probe side, but the core mechanism is a merge of ordered streams, not hash-table probing.
5. Concrete Example
SELECT *
FROM orders o
JOIN users u ON o.user_id = u.id
WHERE u.country = 'CN';If the filtered users table (Chinese users) is small:
Build side = users – build an id → user hash table.
Probe side = orders – scan orders, look up each o.user_id in the hash table.
Matches emit combined order and user rows.
If users is large and orders is small, the optimizer may reverse the roles, depending on statistics and join type.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
