One matching key holds a hundred times the records of any other - how does that change the memory each local matching strategy needs?

## Two strategies, two different bounds A lopsided distribution of records across keys - skew, meaning that one key value carries a far larger share of the records than the rest - does not affect the two local matching strategies equally, because they are not bounded by the same quantity. - The **keyed in-memory lookup** holds one entire landed side in a structure in memory. Its requirement is a function of that side's **total** footprint. Whether those records are spread evenly over a million keys or piled onto one makes no difference: the same records are resident either way. - **Walking two ordered runs** holds only the records sharing the key currently under the cursors, on whichever side it has to revisit. Its requirement is a function of the **heaviest single key**, not of the piece. So in the ordinary case the walk's bound is dramatically smaller, which is exactly why it is the strategy that survives pieces far larger than memory. And in the one-enormous-key case, that advantage shrinks towards the lookup's, because the heaviest key's run approaches the size of the piece. ## One-to-many against many-to-many The distinction that people miss is **which sides** the heavy key is heavy on. | shape | what the walk must hold | effect | |---|---|---| | the key appears once on one side, many times on the other | one record from the single side while the long run streams past | negligible - the walk is unaffected | | the key appears many times on both sides | the run from the side it revisits, because every record of one run must meet every record of the other | this is the case that inflates the bound | A many-to-many match is the only shape that forces a run to be held. Some implementations hold it in memory; others re-read that side's run from the ordered run already on local disk for each record of the other side, turning a memory cost into repeated reads. Both are still bounded by the heaviest key rather than by the whole piece - which is the honest statement of the walk's advantage, rather than a claim that it is immune. ## Why the memory question and the speed question are different Nothing above says either strategy makes that piece **fast**, and an interviewer will usually push there next. Consider a key present ten thousand times on the left and ten thousand times on the right: the match must emit one hundred million pairs for that key alone. That output volume is the work, and it is identical under both strategies, because it is a property of the data and the match, not of how the pairing is implemented. The worker that received that key therefore keeps running long after the others have finished, whichever strategy it used. What the choice of strategy genuinely decides is narrower, and worth stating precisely: 1. whether the worker also **runs out of memory** while doing that work 2. whether the extra pressure shows up as memory, as repeated local reads, or as an outright failure 3. nothing at all about how many pairs have to be produced Diagnosing an uneven spread across keys and redistributing that key's share of the work are a separate subject, and one worth handing off cleanly in an interview rather than half-answering here. ## The variance to keep in mind Two claims sound like the mechanism and are really one product's behaviour: - **that the runtime will notice the heavy piece and deal with it.** Revising the rest of a plan after measuring what a finished step produced exists in some runtimes, for some operators only, and in a continuously running job largely not at all. Do not present it as something the class does. - **that switching strategy fixes skew.** It changes which resource runs short. The pairs still have to be produced. There is also a hard limit worth naming: the fallback that rescues an oversized lookup by cutting both landed pieces again on the same key cannot help here, because every record of one key value maps to the same sub-piece however you re-cut on that key. A single key too large to fit is the one case that no function of the key will split. ## What an interviewer is listening for That you name the two bounds correctly - whole loaded side against heaviest key's run - that you distinguish the one-to-many shape from the many-to-many one instead of treating all repeated keys alike, and that you separate the memory consequence from the output volume, which no choice between the two strategies changes.