Which grouped computations finish with one fixed-size running value per group, and which need the group's values available at once?
answer
- is there an update rule?
- fixed-size state, or growing state
- one more record, same room
- distribution-shaped answers hold the group
basics
~20 sA computation folds when a fixed-size state plus one more record yields the new state — a group's total, its row count, an extreme. It cannot fold when the answer turns on the group's whole distribution, like an exact middle value.
solid answer
~50 sThe test is whether an **update rule** exists: some state, plus one more record, gives the new state, in room that does not grow. A group's total, the number of rows in it, its largest or smallest value all pass — and so do an average and a spread, because a few running numbers carry them. Answers defined by where a value sits among all the others fail: the exact middle value, or the exact value below which nine in ten fall, need every value of that group available together, so the state grows with the size of the group. A third shape sits between them: an exact tally of how many different values a group contains grows with the group's *variety* rather than its length. The result looks identical in all three cases — one row per group — which is why the cost is easy to miss.
code
pseudocode · 11 lines# folding: the state stays one fixed-size thing
state <- initial_state()
for each record in the rows sharing a key:
state <- update(state, record)
answer <- finish(state)
# holding: what is kept grows until the whole group is present
kept <- empty collection
for each record in the rows sharing a key:
kept <- kept with record.value added
answer <- middle_value_of(kept)go deeper
Know that a group's total and its largest value can be worked out as the records go past, one running number each, without keeping the records themselves.
State the folding test — initial state, an update taking state plus one record, a finish step — and place an average, a distinct-value tally and an exact middle value correctly against it.
Show that the result's shape hides all of this, and that classifying the computation before it runs is the only way to predict what a grouped step will cost.
Worth arguing about as a team rule: which per-group computations an unattended job may use, and whether an approximate answer that folds is preferable to an exact one that does not.
## The question behind the question In a **grouped operation** — split, apply, combine: one pass that gives every row a key, runs a computation once per key, and reassembles the answers — the per-key computations all look alike from the outside. Each one turns many rows into a single value, and **collapsing to one row per group** returns exactly as many rows as there are groups whichever computation you chose. From the shape of the result you cannot tell the difference between a computation that cost one number per group and one that needed every row of the biggest group in memory at the same instant. That difference is the whole subject. ## The folding test A per-group computation **folds** when three things exist: 1. an initial state, of a size fixed before the data is seen; 2. an update rule taking the state so far plus one more record and giving the new state, in that same fixed room; 3. a finish step turning the final state into the answer. If you can write those three, the rows sharing a key are consumed one at a time and discarded. If you cannot, something about the group has to survive until the answer is produced, and that something is what you end up paying for. ## Three tiers, not two | What you want per group | What is carried | Room per group | |---|---|---| | the group's total; the number of rows in it | one or two running numbers | fixed | | the largest or smallest value in it | one running value | fixed | | the average; a spread measure | a few running numbers together | fixed | | the best few under an ordering you fix in advance | as many entries as you asked for | fixed by your own choice | | an exact tally of how many different values appeared | one entry per distinct value seen | grows with the group's variety | | the exact middle value; the exact value below which nine in ten fall | every value of the group | grows with the size of the group | | a hand-written per-group body handed the group as a whole | whatever the body is given | grows with the size of the group | The middle tier is the one people forget. A tally of distinct values is not free and not unbounded either: it costs one entry per value actually encountered, so a group of ten million rows drawn from six status codes stays cheap, and the same group with ten million distinct identifiers does not. ## Why an average folds and a middle value does not An average is a quotient of two running numbers — keep the group's total, keep the number of rows folded in, divide at the end. Each record touches both numbers once and is then irrelevant. A spread measure behaves the same way with one more running number. So a computation producing a single number is not thereby cheap, and a computation that keeps several running numbers is not thereby expensive. An exact middle value is different in kind. Which value sits in the middle depends on where every other value of that group sits relative to it, and the next record read can move it. There is no fixed-size state that survives that, so the values have to be available together when the answer is formed. The consequence is not that the computation is impossible — it is that its room follows the group. ## A hand-written body is a fourth case, and it varies When the per-key work is a **hand-written per-group body** — a function you supply that the library cannot look inside — what it costs depends on what the surface hands it. Some surfaces pass one record at a time, some pass the group's values for one column together, some pass a table of that group's rows. Only the first keeps a folding shape, and the choice is a property of the tool and the surface rather than of your function. So the useful thing to establish is not "is it hand-written" but "what does it receive". ## Two execution models, one invariant Whether the input's rows are in memory at all depends on the execution model: under **eager evaluation** each step runs as written and the input is resident before the split begins; under **deferred evaluation** the steps are recorded as a plan and run only when an answer is demanded, and a folding reduction can then be carried out from the accumulators alone. Under both models the accumulators are resident, and under both models a computation that needs its group at once will hold that group. That is the claim worth carrying: what must be resident, rather than what happens to be loaded. ## What to say in an interview Give the test, then one example on each side, then the middle tier to show the two-bucket answer is a simplification. Finish with the practical consequence: because the result's shape is identical either way, the only way to predict a grouped run's memory is to classify the computation before running it.
- Where does an exact tally of distinct values per group sit against that test?Between the two. It carries one entry per distinct value actually seen, so it is not fixed-size, but it does not grow with the group's length either — only with its variety. Ten million rows drawn from six codes stay cheap; ten million distinct identifiers do not. Treating it as free because it returns one number is the common error.
- Does a computation that returns one number per group always cost the same as another that does?No, and the result gives no clue. A total and an exact middle value both collapse a group to one number, but one carries a running figure and the other needs the group's values together. Cost follows the state the computation must carry, not the shape of what it returns.
- If you need a middle value and the groups are large, what is the honest framing of the choice?You are choosing between an exact answer whose room follows the largest group and an answer of a different kind whose room does not. That is a decision about what the number is for, not a tuning knob — so it belongs in the conversation before the pipeline is written, not after a run has failed.
Counting a crowd with a tally counter in your pocket costs one number no matter how many people file past. Finding the crowd's middle height costs having everybody standing there at once — the same single number comes out, and the two cost nothing alike.
saying these in an interview costs you the question
- Assumes every single-number answer costs the same room per group.
- Says an average needs the group's values kept together.
- Thinks an exact middle value can be found with one running number.
- Treats a distinct-value tally as carrying fixed-size state.
- Reads a grouped run's memory cost off the result's row count.
- Judges a hand-written body by who wrote it rather than what it receives.