Why a Join Moves Data

Concepts covered: Distributed Primitives

Matching rows that live on different machines

A join pairs each row of one table with the rows of another that share a key. orders.join(products, "product_id") pairs order 1, which carries product 4017, with the one products row whose product_id is 4017. To build that pair, the 2 rows have to be in the same place at the same moment: inside one task, on one executor, in memory together.

Before the join, nothing has put them there. Spark read orders as 2 partitions by cutting its file at a byte offset, and read products as 2 partitions the same way. Which partition holds order 1 depends on where that row sat in the orders file, and which partition holds product 4017 depends on where it sat in the products file. The 2 rows land on whichever executors picked up those partitions, and the placement of one says nothing about the placement of the other.

A join is therefore a wide transformation on both of its inputs. Spark hashes the join key of every orders row and sends the row to the shuffle partition that hash selects, then does the same to every products row with the same hash function and the same number of partitions. Afterwards every row carrying product_id 4017, whichever table it came from, sits in one partition, and a single task can walk through that partition and emit each match.

product_idorders rows that carry itproducts rowmatches emitted
4017order_id 1, 3, 6Desk lamp3
2210order_id 2, 5Notebook2
3305order_id 4Headphones1
total6 rows3 rows6

The first line of the program below turns off Spark's automatic broadcasting, so that the join you watch is the shuffle version. Section 1 explains what that setting does when it is left alone. Watch for 2 shuffles, one per table, before any output row appears, and notice that each output row is built inside the task that received both of its halves.

spark.conf.set("spark.sql.autoBroadcastJoinThreshold", -1)
orders.join(products, "product_id").collect()
orders
order_idproduct_id
14017
22210
34017
43305
52210
64017
products
product_idproduct_name
4017Desk lamp
2210Notebook
3305Headphones

What the shuffle costs

Both tables cross the network. The tasks that read orders write every row to local disk, grouped by destination partition; the tasks that read products do the same; then the join tasks pull their partition's rows from every one of those writers. A join of a 200GB table to a 50GB table writes 250GB of shuffle data and reads 250GB back, and the reading side waits for the slowest writer to finish before it starts.

Inside each shuffle partition, Spark sorts both sides by the key and then merges them, advancing through 2 sorted lists the way you would merge 2 sorted decks of cards. That strategy is called sort-merge join, and it is what Spark falls back to whenever it has no reason to choose anything cheaper. It handles tables of any size, because no table ever has to fit in one executor's memory, and that generality is what the 2 shuffles pay for.

A job joins clicks, 400GB, to sessions, 100GB, on session_id, and neither side is small enough to broadcast. How much shuffle data does the job write before the join tasks run?

The cell below joins the seed's order_items fact table to its products dimension on product_id. Spark picks a strategy on its own here; the next section shows which and why. Run it and read the first row: its item_id and quantity came from order_items, its product_name came from products, and the join put them side by side because both carry the same product_id. Each item appears once, as each of orders 1 to 6 did in the table above, because every product_id matches a single products row.

About this lesson

This section is part of the Joins: Beginner lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.