CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 5 of 7 · 4 min read

Joins and grouping at scale

The trick is to bring all records with the same key to the same place.

Think of two lists: a list of visitors with their birth years, and a list of page views with visitor names. To tell which age groups read which pages, each view needs its visitor's birth year. You could phone the registry for each view, which is slow. Better to put both lists in one big pile, sorted by name, so that each visitor's record sits right above that visitor's views.

DDIA uses this example (user activity events and a user database). Looking up each user in a remote database for each event is orders of magnitude slower than a batch job's throughput. It may overload the database, and it makes the job nondeterministic, since the database can change during the run. So the better way is to copy the user database into the same file system as the activity log and join the two there.

Sort-merge join. One set of mappers reads activity events and emits the user id as the key. Another set reads the user database and also emits the user id as the key. The shuffle brings both to the same reducer. With a secondary sort, the user's record comes first, followed by their events. The reducer remembers the date of birth and then walks through the events. It needs only one user record in memory at a time and makes no network requests. This is a reduce-side join.

Sort-merge join

A sort-merge join combines two datasets by key. Both are sorted by the key and then merged, so rows with the same key sit together and can be matched in one pass.

Example: mappers emit (user 8, birth year 1990) from the user table and (user 8, view of /a) from the log. The reducer for user 8 sees the birth year first, then the views.

The book observes that mappers act like senders of messages, and the key acts like an address. All pairs with the same key are delivered to the same call of the reducer. This separates the network work of moving data from the business logic, and it shields the code from partial failures, because the framework retries tasks.

Grouping. The same pattern gives the SQL GROUP BY: counting, summing, or picking the top k per key. A common use is sessionization: group the events of one user from many servers by user id or session cookie, to see the sequence of actions.

Skew. If one key has far more data than others, such as a celebrity with millions of followers, one reducer gets overloaded. A job is only done when all reducers are done, so the slowest holds everything up. DDIA lists fixes: a sampling job finds the hot keys, the records for a hot key are spread to several reducers at random, and the other join input is copied to all of them. Or, for grouping, aggregate in two stages: first at random reducers to shrink the data, then combine the partial results.

Map-side joins. If assumptions hold, the join can skip the sorting and reducers:

Join Condition How it works
Broadcast hash join One input is small enough for memory Every mapper loads the small input into a hash table and scans its block of the large input
Partitioned hash join Both inputs are split the same way by the same key Each mapper loads only its matching partition of the small input
Map-side merge join Both inputs are split and sorted the same way Each mapper merges the two sorted inputs

Broadcast hash join

A broadcast hash join copies a small dataset to every worker, which holds it in a hash table and looks up each record of the large dataset in it.

Example: a 50 MB table of countries is loaded by every mapper, and a 2 TB log is scanned with a lookup per line.

A worked example (made up). The user table is 200 MB. The activity log is 400 GB, in 3,200 blocks of 128 MB.

Join choice Data moved over the network Sorting needed
Reduce-side sort-merge The whole 400 GB plus 200 MB are shuffled Yes
Broadcast hash join 200 MB copied to each of 3,200 tasks, about 640 GB in the worst case if every task fetches it separately No

Look carefully at the second row: copying 200 MB to 3,200 tasks seems larger than shuffling 400 GB. In practice tasks on the same machine share one copy, and the copy is read from a nearby replica, so this is a rough upper bound, not an exact figure. The point is that the choice depends on sizes, and it should be measured. Which join is cheaper depends on the number of machines, the size of the small table, and the layout of the data.

Because the physical layout matters, knowing the encoding and the folder is not enough. You need the number of partitions and the keys by which data is partitioned and sorted. Hadoop keeps this in metadata stores such as the Hive metastore.

Check yourself:

  • Why is looking up each event's user in a remote database a poor idea in a batch job?
  • When does a broadcast hash join work?