Notesbatch🌱 seedling
Join Strategies
Also: Distributed Join · Sort-Merge Join · Broadcast Hash Join · Broadcast Join · Shuffle Hash Join · Map-Side Join · Reduce-Side Join · Bucketed Join · Hash Join
Ways to bring matching rows of two distributed datasets together: shuffle both sides by key (sort-merge or shuffle hash), copy the small side everywhere (broadcast hash), or pre-partition both identically (bucketing). The cost that matters is what crosses the network.
Why it exists
Rows that match on a join key usually live on different machines, and moving terabytes is the most expensive thing a batch job does.
How it works
- Sort-merge (reduce-side): shuffle both sides by hash(key), sort each partition, merge like a zipper. Works for any size; shuffles both sides.
- Broadcast hash (map-side): copy the small side to every executor, build an in-memory hash table, stream the big side past it where it already sits. No shuffle of the big side.
- Shuffle hash: shuffle both sides, hash the smaller side of each partition instead of sorting.
- Bucketed: both tables were written bucketed and sorted by the join key into the same number of buckets, so matching rows are already co-located.
Trade-offs
| Strategy | Network | Memory | Best when |
|---|---|---|---|
| sort-merge | both sides | low, streams | both large |
| broadcast hash | small side × executors | small side per executor | one side small |
| shuffle hash | both sides | build side per partition | partitions fit in memory |
| bucketed | none | low | tables pre-bucketed on the key |
In practice
- Spark broadcasts automatically below spark.sql.autoBroadcastJoinThreshold (10 MB by default); hints (BROADCAST, MERGE, SHUFFLE_HASH) override the choice.
- Adaptive query execution (on by default since Spark 3.2) converts sort-merge to broadcast at runtime when a side turns out small after filtering.
Pitfalls
- Broadcasting a "small" table that grew: executors run out of memory.
- Planning from stale size estimates; the real post-filter size decides the right strategy.
Connections
- Part of
- Batch Processing
- Learn first
- Shuffle
- In real systems
- Apache Spark
Recall
These cards are also in your review deck, scheduled with spaced repetition.