skip to content

A lazy pipeline over a stock-take export still peaks at full-dataset memory - which kind of stage explains that?

level: seniorimportance: should knowfreq 38%

answer

  1. one stage refuses to answer early
  2. what must it hold per demand
  3. data dependency, not an implementation choice
  4. one traversal per fused segment
  5. ordering cannot emit before the last element

basics

~20 s

A barrier stage: one that cannot emit its first output until it has consumed every input element, such as ordering or grouping. It buffers the whole stream, splitting the chain into two fused segments with a materialised collection between them.

solid answer

~50 s

Fusion only holds across stages that can answer a demand from one element at a time. A stage that orders the elements, or groups them by key before emitting groups, has no first output to give until the last input has arrived, so it must buffer everything. The chain therefore runs as **two fused segments** - the stages feeding the barrier, then the stages draining it - with a full materialisation in between, and peak memory tracks the data reaching that point rather than the result. Worth separating from a third case: a stage that emits as it goes but retains state, such as one that suppresses elements it has seen before, streams perfectly well while still growing its memory with the number of distinct elements. The diagnosis is the same in practice - find the stage whose memory is not bounded by one element - but the mechanism differs.

code

pseudocode · 10 lines
pseudocode
p = lazy(rows)
p = filter(p, isCounted)        # streams: one element in flight
p = sortBy(p, location)         # barrier: holds every element it is given
p = map(p, format)              # streams again, once sorting is done
report = collect(p)

# the chain runs as two fused segments:
#   1. read -> isCounted -> buffer inside sortBy   (whole input consumed)
#   2. drain sorted buffer -> format -> report
# peak memory tracks the survivors of isCounted, not the report

go deeper

for a junior

The idea to hold is that some stages cannot produce anything until they have seen every element - ordering is the obvious one - so a chain containing one is not the single clean pass the rest of the chain suggests.

for a middle

Explain why it is a data dependency: the smallest element under an ordering may be the last one read, so the stage has no honest first output. Then describe the chain as two fused segments with a materialisation between them.

for a senior

Demonstrate the diagnosis on a real profile: identify the stage whose retained state is not one element, move selections ahead of it, separate a true barrier from a stage that merely retains state, and state the new memory ceiling you expect.

for a principal

The trade-off a lead owns is whether the barrier belongs in the pipeline at all - pushing an ordering or a grouping to whatever produced the data, or accepting an approximate result, are architectural answers that a stage reordering cannot reach.

A team rewrites a report as a lazy chain over the stock-take export, expecting peak memory to fall to roughly the size of the report. It does not move. The chain is still lazy and the stages still fuse; the fusion simply cannot cross one of them. ## Three kinds of stage, by what they retain | Kind of stage | Can emit before input ends? | What it retains | Effect on the pass | |---|---|---|---| | Element-wise (transform, select) | yes, immediately | one element in flight | fuses freely | | Stateful but streaming (suppress repeats, running total) | yes | state that grows with distinct elements or is constant | fuses, but memory is not bounded by one element | | Barrier (order, group before emitting, reverse) | no | every element it has been given | splits the chain into two segments | A **barrier** is defined by a data dependency, not by an implementation choice. The smallest element under an ordering may be the very last row read, so no ordering stage can honestly emit a first element earlier. The same is true of a stage that emits complete groups: until the input ends, any group may still receive another member. ## What the barrier does to the pass 1. The collecting step demands a value from the end of the chain. 2. The demand reaches the barrier, which has nothing to give and pulls its own upstream to exhaustion - the whole first segment runs, fused, into the barrier's buffer. 3. The barrier does its work over the completed buffer. 4. Only then does it begin answering demands, and the second segment - fused again - drains it element by element. So "a lazy chain walks the data once" is precisely true **per fused segment**. A chain with one barrier has two segments and one materialisation; a chain with two barriers has three and two. ## Diagnosing it - **Find the stage whose retained state is not one element.** Ask each stage what it must hold to answer a single demand; the barrier is the one that answers "all of it". - **Check where the barrier sits relative to the selection stages.** A barrier after a selection buffers only the survivors; the same barrier before it buffers everything. This is the single highest-value move available, and it is often legal, because ordering a set and then discarding members gives the same result as discarding first and then ordering. - **Check whether the barrier is needed at the position it occupies.** A stage that orders elements only so that a later stage can group adjacent equals is doing the grouping stage's job at full-dataset cost. - **Check whether the whole barrier is needed at all.** A barrier that exists to take a bounded slice of an ordering can often be replaced by a bounded retention that holds only as many elements as the slice needs. - **Distinguish retention from a barrier.** A stage suppressing repeats is streaming; its memory grows with the number of distinct elements. Treating it as a barrier leads you to look for a buffering bug that is not there, and treating a barrier as mere retention leads you to expect a first output that will never arrive early. ## The claim to state carefully It is tempting to summarise this as "a lazy pipeline avoids materialising the data". The defensible version is narrower: a lazy chain avoids a collection **at every boundary its fusion spans**, and a barrier stage is a boundary its fusion cannot span. That is not a defect in laziness - the work genuinely cannot be done element-wise - but it is the difference between a pipeline whose memory ceiling is its output and one whose ceiling is its input, and it is almost always where a disappointing rewrite went.

  • The chain orders the elements and then discards most of them. What change would you make first?
    Move the selection ahead of the ordering, so the barrier buffers only the survivors. The two orders agree whenever the test does not read something the ordering changes - and an ordering changes position, not content - so it is usually a safe move, and it converts a full-input buffer into a result-sized one.
  • How is a stage that suppresses elements it has already seen different from a barrier?
    It emits each first occurrence immediately, so it streams and fuses with its neighbours; what it retains is a set that grows with the number of distinct elements. Its memory can still reach full-dataset size when nearly everything is distinct, but the first output arrives after the first element, not after the last.
  • Is it still honest to say the chain makes one pass over the data?
    Only per fused segment. A chain with one barrier has two segments: the first consumes the source to exhaustion into the barrier, the second drains the barrier. The source itself is read once, but the pipeline holds a complete materialisation at the barrier, which is exactly the cost fusion was supposed to remove.
  • Which property of the data would let you replace an ordering barrier with a streaming stage?
    Knowing the input already arrives in that order, in which case the stage can be dropped; or needing only a bounded slice of the ordering, in which case a retention of that bounded size does the job and emits when the input ends, holding a fixed number of elements rather than all of them.

A sorting office can forward most letters as they arrive, but a stage that must dispatch them in postcode order cannot send the first one until the last van has unloaded.

saying these in an interview costs you the question

  • Claims every lazy chain walks the data exactly once regardless of its stages
  • Says a stage suppressing repeats cannot emit until the input ends
  • Treats the full buffer as a library defect rather than a data dependency
  • Puts the ordering stage before the selection and expects the same memory
  • Thinks adding more element-wise stages after a barrier reintroduces buffering
  • Believes laziness removes the result collection as well as the boundary ones