Two large inputs have been redistributed on the matching key - what two ways can a worker match the landed pieces?
answer
- the pairing is a local problem
- one side resident, or both ordered
- memory against an ordering
- runs of equal keys, not whole sides
- ordering can be inherited, not paid
basics
~10 sEither load one landed piece into a keyed in-memory lookup and stream the other past it, or have both landed pieces arrive ordered by the key and advance through the two ordered runs together.
solid answer
~50 sOnce equal keys sit on one worker the pairing is a local problem with two shapes. The first loads one of the two landed pieces into a keyed lookup structure in memory and then streams the other past it, emitting a pair for every record found under each key. It needs no ordering and touches each side once, but the loaded piece must fit in the memory the match is given. The second needs both landed pieces ordered by the matching key - paid for by ordering each side, or inherited where the runtime already delivers the records for a key grouped and in order - and then advances through both in step, matching runs of equal keys. It holds only the run currently being matched rather than a whole side. So one trades memory for skipping an ordering; the other trades an ordering for a much smaller resident set.
code
python · 30 lines# Strategy one: one landed piece becomes a keyed lookup,
# the other is streamed past it.
def match_with_lookup(landed_left, landed_right):
lookup = {} # the whole left piece must be resident
for rec in landed_left:
lookup.setdefault(rec.key, []).append(rec)
for rec in landed_right: # one pass, any order, no ordering needed
for partner in lookup.get(rec.key, ()):
yield (partner, rec)
# Strategy two: both landed pieces already ordered by the key,
# walked together.
def match_ordered(left, right): # left and right are ordered by key
l = next(left, None)
r = next(right, None)
while l is not None and r is not None:
if l.key < r.key:
l = next(left, None)
elif l.key > r.key:
r = next(right, None)
else:
k = l.key
run = [] # only this key's run is resident
while r is not None and r.key == k:
run.append(r)
r = next(right, None)
while l is not None and l.key == k:
for partner in run:
yield (l, partner)
l = next(left, None)go deeper
Know that landing the records on the right worker is not the same as matching them, and that there are two local ways to do the matching once they are there.
Explain both shapes: what the lookup holds and why it needs no ordering, and what the walk holds and where its ordering comes from. That contrast is the question.
Show judgment about which to reach for: the decoded footprint of the smaller side, whether an ordering already exists, and whether a following step wants key-ordered output.
Point out that the choice is only free where a declarative surface makes it; in per-record code it is a property of what somebody wrote, which makes it a review and standards question rather than a tuning one.
## Where this starts Both inputs have already been cut on the matching key and sent across, so each worker holds two pieces that agree on the key space: its share of the left input and its share of the right. Nothing has been matched. The records inside those pieces are not necessarily in any order, and the worker needs no further communication with anybody. From here the match is a **purely local problem**, and there are two shapes for it. ## Strategy one: one side becomes a keyed lookup - **Load.** Read one of the two landed pieces and insert each record into a keyed structure in memory, under its matching key value, so that several records with the same key sit together under one entry. - **Stream.** Read the other landed piece straight through, look each record's key up, and emit a pair for every record found under it. - **Requirement.** The loaded side must be **resident in the memory the match is given**. The streamed side is never held; it passes through. - **No ordering is needed** on either side, and each side is read once. - **Which side to load** matters: you want the smaller of the two, where smaller means its footprint once decoded into whatever the runtime holds records as, not the size it occupied in storage. - **Output order** is whatever order the streamed side happened to arrive in, so nothing downstream may assume an order. ## Strategy two: walking two ordered runs in step - **Precondition.** Both landed pieces are ordered by the matching key. - **Where the ordering comes from.** Either the worker orders each landed piece itself, or it inherits the ordering - in the older two-phase model the consuming side is handed the records for a key grouped and already in order, so the walk costs almost nothing extra there. - **Mechanics.** Two cursors, one per side. Whichever cursor sits on the smaller key advances. When the two keys are equal, the worker matches the run of records sharing that key on one side against the run on the other, then advances past both runs. - **Resident set.** Only the run of the key currently being matched, on the side the walk has to revisit - not a whole piece. - **Output order.** Pairs come out ordered by the matching key within that piece. That is not an end-to-end ordered result across the whole job, which is a different arrangement entirely, but it is reusable by a following step on the same worker. ## The comparison | | keyed in-memory lookup | walking two ordered runs | |---|---|---| | what must be resident | the loaded landed piece, in full | the run of the key currently being matched | | ordering required | none | both sides, produced or inherited | | reads over the data | one per side | one per side, after the ordering | | when a side exceeds memory | a hard stop: re-cut, switch strategy, or fail | absorbed as extra ordered passes over local disk | | one very heavy key | bound unchanged - it is the total that matters | exactly the case that inflates its bound | | output ordered by the key | no | yes, within that piece | ## Who chooses, and on what This is where assumptions about the engine you happen to know leak in. On a **declarative surface**, where the author states the match and the runtime plans it, the runtime picks a strategy from what it estimates about the two sides, and some runtimes revise that choice after measuring what a finished step actually produced - a separate subject, named here only to hand it off. In a program written as **per-record functions**, nothing is planning on your behalf: the match executes the shape the author wrote, and if that shape builds a lookup then a lookup is what runs. And in the **older two-phase model**, the consuming side receives grouped, ordered records, so the walk is effectively what you are given. A candidate who says the runtime always chooses the better of the two is describing one part of the market. ## The real axis Strip the names away and the choice is memory against passes. The lookup buys a single pass over each side with a hard memory requirement on one of them. The walk buys a small resident set by paying for an ordering, and that payment can itself be made in passes over local disk rather than in memory. Which is better depends on how big the smaller landed piece is once decoded, whether an ordering already exists, and whether a following step wants the output in key order. ## What an interviewer is listening for That you can state both shapes, name what each one holds, and say where the ordering for the second comes from - and that you do not present either as the way matching works, which is the tell of somebody who has only ever watched one runtime do it.
- Which of the two leaves its output ordered by the matching key, and why does that matter?The walk over two ordered runs emits pairs in key order within that piece, so a following step on the same worker that wants that order - another match on the same key, or an ordered write - can reuse it instead of ordering again. The lookup emits in whatever order the streamed side arrives, so nothing downstream may assume anything.
- If the landed pieces already arrive grouped and ordered by the key, is there still a choice to make?Barely. The walk then costs almost nothing beyond the match itself, which is why the older two-phase model effectively hands you that shape: its consuming side receives the records for a key together and in order. Where a runtime delivers unordered pieces, the walk has to produce the ordering first, and the lookup becomes the cheaper option whenever one side fits.
- Why does it matter which of the two landed pieces you load into the lookup?Because only the loaded side has to be resident. Loading the larger one makes a match that would have fitted comfortably fail or fall back. The comparison to make is between the two sides' footprints once decoded on this worker, which is not the same ranking as their sizes in storage if the two were encoded differently.
Cross-checking two long guest lists. Either copy one list onto index cards you can flick straight to by name and then read the other list out loud, which means holding all the cards at once; or put both lists in alphabetical order and run a finger down each, which means holding nothing but the two fingers and whichever block of identical names you are currently on.
saying these in an interview costs you the question
- Thinks the ordered walk needs both landed sides resident in memory.
- Assumes the lookup is always faster because it avoids an ordering.
- Believes the ordering for the walk must always be produced by a sort.
- Says the runtime always picks the better of the two for you.
- Thinks it makes no difference which landed piece is loaded.
- Confuses the local match with copying a small input to every worker.