In an equality join, one key value has two million rows on the left and fifty on the right — what must that key's destination produce?

## What a join does within one key An equality join is, per key, a cross product. Every record on the left carrying key *k* is paired with every record on the right carrying key *k*. If the left has *L* such rows and the right has *R*, the key emits *L × R* rows. For the overwhelming majority of keys in a healthy dataset that product is tiny — 20 left rows against 3 right rows is 60 — and nobody thinks about it. The join is also a **redistributing step**: a step that cannot be computed from what one worker already holds, so every record is first sent to the worker that owns its key. Which worker that is comes from the **key-to-destination rule**, the function from a key value to the number of the destination that receives it, with the property that the same value always yields the same destination. So both sides' records for key *k* arrive at one destination, and the product for *k* is formed there, by one worker. ## The arithmetic | Key, left × right | Records arriving at the destination | Records produced there | | --- | --- | --- | | a typical key, 20 × 3 | 23 | 60 | | the heavy key, 2,000,000 × 50 | 2,000,050 | 100,000,000 | | the heavy key, 2,000,000 × 1 | 2,000,001 | 2,000,000 | | heavy on both sides, 2,000,000 × 2,000,000 | 4,000,000 | 4,000,000,000,000 | Read the first two rows together. Against a typical key the heavy key brings a hundred thousand times as much input, but produces 1.6 million times as much output. The multiplier on the right-hand side is what turns an awkward piece into one that does not finish. Row three is worth stating explicitly because it is the case people assume: when the other side's key is unique, the product collapses to *L* and the heavy key is a pure concentration problem. Row four is the one that produces a job nobody can wait for. Four trillion rows out of one worker is not slow; it is never. ## Concentration and multiplication are different problems - **Concentration** is about the input: one destination receives a large share of the records. It is set by the key's frequency in the data. - **Multiplication** is about the output: that destination emits the product of the two sides' counts. It is set by the frequencies on **both** sides together. A candidate who only counts input rows will predict a piece a hundred times too large and be confused when the job behaves far worse than that. The counts to look at before a join are the row counts per key on **each** side, not the table sizes. ## What varies between engines - How the pairs are formed at the destination differs. One common approach builds a lookup over one side's rows for the key and streams the other side against it, which means that side's rows for the heavy key must be held somewhere while the pairing runs. Another sorts both sides by key and merges them, which needs no per-key lookup at all and can stream both sides. The memory profile of the heavy key differs sharply between the two; the number of output rows does not change at all. - Whether the runtime intervenes differs too. Where an engine re-decides the part of a plan it has not run yet from the sizes a finished step actually produced, it may treat an unusually large destination specially for a join — for some join shapes. Where the input never ends, no step finishes and there is nothing measured to re-plan from. - What the destination does when it cannot hold what it needs varies as well: writing to local disk and continuing, or failing the piece. Either way, the heavy piece is the one that announces the imbalance first. ## The output does not stay put The destination that produced a hundred million rows is also the one that emits them. If the job writes at that point, it writes one enormous unit of output while its peers write small ones. If another step follows, that step inherits pieces of wildly different size — the imbalance propagates downstream unless the records are redistributed again on a key with a different frequency shape. This is why a heavy key discovered at a join is often blamed on a step several stages later: the later step is where the oversized piece finally fails. ## What an interviewer is listening for That you multiply rather than add. The strong answer states the product immediately, names the destination that will form it, and then asks for the per-key row counts on the other side — because the difference between 2,000,000 × 1 and 2,000,000 × 50 is the difference between an awkward job and one that will not complete. A candidate who says "the join output is about the size of the bigger input" has assumed uniqueness on the other side without checking it.