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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.