skip to content

Which aggregates fold into one mergeable value per group, which force keeping every record, and where does mean sit?

level: middleimportance: must knowfreq 58%

answer

  1. ask what value you would carry
  2. combine two partials, then check its size
  3. mean folds as a pair
  4. distinct and median keep the records

basics

~20 s

Sum, count, smallest, largest and mean fold into a fixed-size value per group. Exact median, exact distinct count and exact top-k do not. Mean folds only as a total-and-count pair, never as a running average.

solid answer

~40 s

The test is not the list, it is the question: what value would you carry for the group, and do two such values — built over different halves of the group — combine into the value for the whole, without that combined value getting bigger? Count and sum pass (add), smallest and largest pass (take the smaller or larger), and mean passes once you carry the pair `(total, count)` and divide only at the end. Exact median fails because the middle value depends on records not yet seen. Exact distinct count fails on the *size* half of the test: a set of identifiers merges by union, but it grows with distinct values. Exact top-k by frequency fails for the same reason — you need a count per distinct key, not per ranked key.

code

python · 18 lines
python
def empty():
    return (0.0, 0)


def fold(acc, value):
    total, count = acc
    return (total + value, count + 1)


def combine(left, right):
    return (left[0] + right[0], left[1] + right[1])


def finish(acc):
    total, count = acc
    if count == 0:
        return None
    return total / count

go deeper

for a junior

Know the short list by heart: total, count, smallest, largest and mean fold into a fixed-size value; exact median, exact distinct count and exact top-k do not.

for a middle

Derive the list rather than recite it — name the carried value, combine two partials, check whether the result grew — and explain the total-and-count pair for a mean.

for a senior

Judge what to do when an aggregate does not fold: shrink what each group sees, coarsen the key, or change the question to an approximate one with an agreed error.

for a principal

Own the trade across a platform: decide which numbers must be exact because somebody is billed or audited on them, and which are estimates nobody should try to reconcile.

## Foldability is a test, not a list An open group — one whose records are still arriving and whose answer cannot yet be handed downstream — costs whatever it is holding. It can hold a **foldable accumulator**: a per-group value with two properties, that any two of them merge into a single value covering both sets of records, and that its size does not grow with how many records have been folded in. Or it can hold a **retained record set**: the records themselves, kept until the group is declared finished so the answer can be computed from all of them at once. Which one an aggregate needs is decided by a test you can run in your head: 1. Name the value you would carry for a group after one record, after two, after a thousand. 2. Take two such values, built over disjoint halves of the same group, and combine them into the value for the whole group. 3. Ask two things about that combination: did it need something one side had already discarded, and did the combined value grow? A yes to either means the aggregate does not fold in the sense that saves memory. ## The ones that fold - **Count** — carry one integer; combining adds. - **Sum** — carry one number; combining adds. - **Smallest and largest** — carry one value; combining takes the smaller or the larger. - **Mean** — carry a total and a count; combining adds each, and the division happens once at the end. - **Variance and standard deviation** — carry count, sum and sum of squares; all three add. - **Flag rollups such as "did any record match"** — carry one flag; combining applies the same operation again. What these share is that the carried value has the same shape after a million records as after one. ## The ones that do not - **Exact median, and every exact percentile.** The middle value is a property of the whole set's shape, and which record occupies it depends on records that have not arrived. Every value stays. - **Exact distinct count.** To recognise a repeat you must have kept the identifiers. The carried thing is a set, and sets do combine — the union of two is the answer for both — but the union grows with distinct values. - **Exact top-k by frequency.** A key that is second in every half can beat a key that is first in one half, so a correct ranking needs a count for every distinct key, not only for the k that survive. | Aggregate | Carried value | Combines? | Fixed size? | |---|---|---|---| | count, sum | one number | yes, by adding | yes | | smallest, largest | one value | yes, by comparison | yes | | mean | total and count | yes, by adding each | yes | | exact median | every value | yes, by concatenation | no | | exact distinct count | set of identifiers | yes, by union | no | | exact top-k | count per identifier | yes, by adding counts | no | The last column is the one candidates skip. "Does it combine" is not the whole test, because concatenating two retained sets combines perfectly well and costs everything. ## Mean is the instructive near-miss Interviewers reach for mean because the naive answer is wrong in an interesting way. Averaging two averages is correct only when both covered the same number of records, so a candidate who carries the average itself has built a value that cannot be combined. Carrying a total and a count fixes it outright, at the price of one extra number per group. The same move rescues neighbours of the mean: variance needs a third number, and a weighted mean needs the weighted total and the total weight. ## What to do when an aggregate genuinely does not fold Three moves, roughly in the order they are worth trying: 1. **Make the group hold less.** A shorter interval or a finer grouping key means fewer records retained per group. This does not change the aggregate's nature; it changes how much of the input each group sees. 2. **Change the question.** A constant-size summary that answers "how many distinct, within a stated error" or "approximately the ninety-fifth percentile" combines the way an accumulator does and restores the constant per-group cost. What has to be agreed before that swap is its own subject. 3. **Accept the retained set** where groups are genuinely small. A per-user group over five minutes may hold a handful of records, and exactness is then free. ## Where engines of this class differ Whether the runtime *exploits* foldability is not universal, even though the property of the aggregate is. A declarative aggregate expression is generally compiled into a fold. A hand-written function that receives each record and appends it to a collection is generally executed exactly as written and folds nothing, even where the mathematics allows it. Some runtimes let you declare an accumulator with its own combine step explicitly; others infer it from the expression; the oldest model in this family expresses it as a separate local combining phase. So "this aggregate folds" is a statement about the mathematics, and "my job folds it" is a statement about how the job was written and which runtime is reading it.

  • How do you make a top-k by frequency affordable when the distinct key count is large?
    Either make each group hold fewer distinct keys, or change the question. A constant-size summary that tracks frequent items answers "which are the heavy ones, within a stated error" instead of "the exact ranking". An exact top-k needs a count per distinct key and has no cheap exact form.
  • A set of identifiers held for an exact distinct count merges by union. Does that make it foldable?
    It satisfies half the test. Two such sets do combine into the answer for both, but the result grows with distinct values, so the group's cost is not constant. Foldability in the sense that saves memory means combinable and fixed-size, and the second half is the one that decides whether the job fits.

saying these in an interview costs you the question

  • Says a mean cannot be folded because averages of averages are wrong.
  • Assumes any aggregate can be turned into one running number.
  • Thinks an exact distinct count folds because counting folds.
  • Claims a median folds if you carry a running average.
  • Treats top-k as cheap because only k results are emitted.