A landed piece is twice the memory a worker can give the match - what does each of the two local matching strategies do then?

## What is actually running out A worker has some amount of memory available to this match. One of the two landed pieces, once decoded into whatever the runtime holds records as, is larger than that. Nothing about the movement has gone wrong: the records are on the right worker and the keys are co-located. It is the **local matching step** that cannot proceed as planned. Note that how a worker's memory is divided among the operators running inside it, and writing a working set to local disk as a general design response to memory pressure, are separate subjects; what follows is specifically what each of the two matching strategies does. ## The lookup's three possible responses Building a keyed structure over a landed piece is all-or-nothing: you cannot look a key up in the half of the side that fitted. So a runtime has exactly three moves. 1. **Cut both landed pieces again, on the same key.** Apply a further function of the matching key value to split each landed piece into sub-pieces, write them to local disk, and then match sub-pair by sub-pair, loading one side of each sub-pair at a time. Because the same key value still routes both sides to the same sub-piece, correctness is preserved. 2. **Abandon the strategy.** Order both sides and walk them instead, paying for an ordering in exchange for a resident set that no longer depends on the size of a side. 3. **Fail.** Some runtimes, and most hand-written per-record matches, simply run out of memory and the unit of work dies. A candidate who assumes a graceful fallback always exists has generalised from one product. The important claim here is the one about **variance**: the strategy does not define the response, the runtime does. Saying so is not a hedge - it is the answer. ## Why cutting again on the key works It is the same idea as the movement itself, applied twice and at a smaller scale: - the first application used a routing function over the matching key to put equal keys on one worker - the second applies another function of the same key to put equal keys in one sub-pair on that worker - matching records therefore still meet, and no pair is lost - the price is real: each sub-piece is written to local disk and read back, so the data is passed over more than once - and it is not unbounded - a key value that is itself too large to fit will not be split by any function of that key value, because every one of its records maps to the same sub-piece That last bullet is the honest limit of the technique and the bridge to the heavy-key case. ## What the walk does instead The ordered walk's resident set was never a whole side, so the piece exceeding memory does not threaten the match - it threatens the **ordering**. Ordering more records than fit in memory is a solved, ordinary operation: order as many as fit, write that ordered chunk to local disk, repeat, then merge the chunks by reading a little of each. The result is an ordered run the walk can advance through with two cursors. So the cost lands as extra reads and writes on local disk and extra processor time, not as a decision about whether the match can run. | | lookup | walk | |---|---|---| | nature of the limit | hard: resident or not | soft: pay in passes | | where the extra work goes | a re-cut, a switch, or nothing | producing the ordering | | can it be resolved on this worker alone | yes, if the runtime implements a re-cut | yes | | what defeats it entirely | one key value too large to split | the same, for the run it must hold | ## Judging the fit before it bites The most common way to get this wrong is to compare the wrong numbers. A landed piece of 400 MB in storage is not a 400 MB working set. It may be encoded and compressed on the way in; it is decoded on the way out; and what it is decoded **into** varies a great deal between runtimes in this class - some hold records in a compact managed binary layout, others as ordinary language objects with per-object overhead, and the gap between those two is several-fold for the same data. Always attach the unit and the place: 400 MB encoded in storage, perhaps well over a gigabyte once resident. Whether a given side fits is a statement about the second number. ## What an interviewer is listening for That you distinguish a **hard** requirement from a **payable** one; that you can describe the re-cut and say why it preserves correctness; that you know the ordering for the walk survives a piece larger than memory; and above all that you attribute the fallback to the runtime rather than asserting that every engine rescues you.