Skip to content
How Hash Join Chooses Build and Probe Sides: A Deep Dive
Databases 6 min read

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.

Big Data Technology Tribe
Big Data Technology Tribe
Big Data Technology Tribe

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.

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

SQL OptimizationHash JoinDatabase InternalsJoin AlgorithmsQuery Execution PlanBuild SideProbe Side
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.