skip to content

In a single-pass pipeline, why does putting a cheap selection before an expensive transformation reduce the work done?

level: middleimportance: should knowfreq 55%

answer

  1. one pass is not minimal work
  2. count applications, not traversals
  3. selection changes how many elements arrive
  4. n applications versus k applications
  5. fusion collapses loops, does not reorder

basics

~20 s

Because each stage's function runs once per element that reaches it. Fusion removes the collections between stages, not the per-element work, so the only way to run the expensive transformation fewer times is to let fewer elements reach it.

solid answer

~50 s

A fused chain applies the stages in the order you wrote them, one element at a time. If the expensive transformation comes first, it runs `n` times - once per row in the export - and the selection then throws most of those results away. If the selection comes first, the transformation runs `k` times, where `k` is the number of survivors, and the saving is the difference between `n` and `k` applications of the expensive function. Fusing the chain does not reorder it for you: it collapses the loops, so the order you wrote is the order the element visits. The rewrite is only safe when the selection's test reads something the transformation does not produce or rewrite - if the test looks at a field the transformation computes, moving it earlier changes the result rather than just the cost.

code

pseudocode · 15 lines
pseudocode
calls = 0
function enrich(item)
    calls = calls + 1
    return withValuation(item)          # the expensive stage

# order A: transform first
report = collect(filter(map(lazy(rows), enrich), isDiscrepant))
# calls == n   (every row is enriched, most results discarded)

# order B: select first
report = collect(map(filter(lazy(rows), isDiscrepant), enrich))
# calls == k   (only survivors are enriched)
#
# same report only because isDiscrepant reads a field
# that enrich neither produces nor rewrites

go deeper

for a junior

The takeaway to recall: a stage runs once for every element that reaches it, so filtering early means the expensive stage sees fewer elements. Being able to say which of two orders does less work is enough here.

for a middle

State the counts, not the intuition: the expensive function runs n times in one order and k times in the other, and fusion does not change either number. Then name the condition that makes the rewrite legal.

for a senior

Show the judgment: quantify the selectivity before reordering, recognise when the test depends on the transformation's output, and treat the readability loss as a cost you pay deliberately and comment on.

for a principal

The lead's angle is where this reasoning should live. Hand-ordering every chain does not scale across a codebase; deciding whether pipelines carry their own cost model, or whether the team just keeps a convention, is the real call.

The export has `n` rows. One stage tests a field already present on each row - cheap, a comparison. Another stage enriches each item by computing something substantial from it - expensive, and the dominant cost in the chain. Both orders produce the same report when the test does not depend on the enrichment, and one of them does far less work. ## Why the order changes the cost at all A fused chain is one loop with the stage functions inlined in the order you wrote them. Each function is applied **once per element that reaches it**, and a selection stage is the only kind of stage that changes how many elements reach the next one. | Order written | Applications of the cheap test | Applications of the expensive transformation | |---|---|---| | transform, then select | `n` | `n` | | select, then transform | `n` | `k` (the survivors) | With `n` of a million and `k` of ten thousand, that is ninety-nine percent of the expensive work removed - and the fusion itself removed none of it. This is the point people most often get backwards: one pass is not the same as minimal work. Both orders above are one pass; one of them does a hundred times more of the work that matters. ## Fusion collapses the chain, it does not plan it Collapsing the stages into one traversal is a mechanical rewrite of the loops, not an optimiser deciding what the cheapest plan is. Some pipeline designs do inspect the chain and push a selection down towards the source before running it, and many do not - a chain built from ordinary per-element functions has no way to know that one of them is a filter and another costs a thousand times more. Treat the order you write as the order that runs, and let any automatic reordering be a bonus you discover rather than a guarantee you lean on. ## When moving the selection earlier is not allowed The rewrite preserves the result only under conditions worth stating explicitly: 1. **The test must be computable on the earlier value.** If the selection reads a field that the transformation produces, there is nothing to test before the transformation has run. 2. **The transformation must not rewrite what the test reads.** If it normalises the field the test compares, the two orders select different elements - that is a behaviour change, not an optimisation. 3. **Neither stage may depend on being applied to everything.** A stage that logs, counts or otherwise records every element it sees will see a different set after the move, which is only acceptable if that record was not the point. When all three hold, the two orders are interchangeable in meaning and distinguishable only in cost. ## The trade-offs that survive the rewrite - **Two selections in a row are worth ordering too.** The one that rejects more, or costs less per element, belongs first, for exactly the same reason. - **The gain is proportional to selectivity.** If the selection keeps almost everything, moving it buys almost nothing, and the reordered chain may read worse for no benefit. - **Readability is a real cost.** A chain reads best in the order a human would describe the task; when the reordered version reads worse, a comment saying why the selection is first is part of the change. - **The per-element cost has to actually be lopsided.** If both stages are comparisons, you are trading clarity for nothing measurable. - **The count you should be able to state is the one that changed.** Not "it is faster" but "the enrichment now runs ten thousand times instead of a million". ## How this sits next to fusion itself Fusion and stage order answer two different questions about the same chain. Fusion decides **what is allocated between the stages** - nothing, once the loops are collapsed. Stage order decides **how many times each stage's function is applied**. A chain can be perfectly fused and still do a hundred times the necessary work, and a well-ordered eager chain can do the minimum number of expensive applications while allocating an intermediate collection at every boundary. Naming which of the two problems you are solving is most of what an interviewer is listening for.

  • Two selection stages sit next to each other in the chain. Which one should come first?
    The one that removes more elements per unit of its own cost. Each element pays the first test, so a cheap and highly rejecting test first means the second test is applied to far fewer elements. If one test is expensive and rejects little, it belongs last regardless of how it reads.
  • The selection's test reads a field the transformation computes. What are the options then?
    Moving it earlier is not available - the field does not exist yet, and forcing the move changes the result. The usable options are to split the transformation so the part the test needs runs first, or to derive a cheaper proxy test on the original element that is guaranteed never to reject a true survivor.
  • Does fusing the chain reorder the stages for you?
    Not in general. Fusion is a mechanical collapse of the stages into one traversal in the order they were written. Some pipeline designs do analyse a chain and push selections down before running it, and many do not, so the safe assumption is that the order you write is the order that runs.

saying these in an interview costs you the question

  • Believes a single-pass chain already does the minimum possible work
  • Says fusion automatically pushes selections towards the source
  • Moves a selection ahead of the stage that computes the field it tests
  • Measures the gain in traversals instead of in expensive applications
  • Reorders every chain regardless of how selective the test is
  • Thinks the ordering only matters for eager chains, not fused ones