Which aggregates return exactly the same answer after a heavy key is spread over suffixes and recombined, and which do not?

## What the rewrite is asking of the aggregate A grouping cannot be computed from what one worker (one process on one machine) already holds, so it opens with a **redistributing step**: every record is sent to the destination that owns its key, chosen by a function of the key value alone. A **heavy key** - one value covering a large share of the records - therefore lands whole on one destination. The standard remedy is to append a small integer suffix to that key so its records reach several destinations, aggregate them there, and fold the partial results under the original key in a second pass. That is a rewrite of the job, not of the data, so it carries an obligation: the second pass must reconstruct exactly the answer the single-pass grouping would have produced. Two conditions decide whether it can. 1. **A combining operation exists.** Pass two must fold up to `W` partials into one value, so the fold has to be associative and have an identity - the general law governing any parallel reduction. 2. **The partial is small.** If a partial is as large as the group it summarises, pass two rebuilds the heavy group on one worker and the imbalance returns at the combining step. This is the condition people forget. ## The three classes | aggregate | partial per `(key, suffix)` | pass two | identical answer? | |---|---|---|---| | sum, count | partial sum, partial count | add | yes | | minimum, maximum | the partial extreme | extreme of the extremes | yes | | mean | sum and count | add both, divide once | yes | | variance, deviation | count, sum, sum of squares | add the three, finish once | yes, with a numerical caveat | | latest value per key | value plus its ordering field | keep the extreme ordering field | yes, if ties break deterministically | | exact distinct count, random suffix | the distinct values themselves | union, then size | only with a partial as big as the group | | exact distinct count, suffix from the value | a partial distinct count | add | yes | | median, percentile | no summary that combines | no combining operation | no | | collect the group's records | the partial list | concatenate | yes, but the partial is the whole group | ## The two failures worth being able to explain - **Averaging the averages.** Each suffix holds a different number of records, so the partial means carry different weights. Averaging them weights every destination equally and the answer is wrong by however unevenly the spread fell. The repair is to carry the numerator and the denominator separately and divide once, which also makes the aggregate associative in the process. - **Adding distinct counts.** If the suffix is random, one value under the heavy key can appear beneath several suffixes, so the partial counts overlap and adding them over-counts. Carrying the actual distinct values fixes the arithmetic and destroys the point of the rewrite, because the set that has to be rebuilt per key is the very thing making the key heavy. ## The distinct count has a different spread For an exact distinct count, do not suffix at random - derive the suffix from the value being counted. Each distinct value then reaches exactly one destination, the partial counts are disjoint, and they simply add. The heavy key's records still scatter, because it is the varied values beneath it that drive the spread. This carries its own condition, and it is the honest limit of the trick: it works when the heavy key covers many different values. If the key is heavy because one value repeats millions of times, spreading by value sends all those repeats to one destination again and nothing has been gained. The measurement to take before choosing is not just records per key but distinct values per key. ## Deviations, ordering, and what nothing checks A variance combines from a count, a sum and a sum of squares, which is exact in arithmetic but can lose precision when the values are large and the deviations small; pairwise combination of a running mean and a running sum of squared deviations is the sturdier form and combines just as well across suffixes. Aggregates that depend on the order records are seen in were already unreliable: a grouping makes no promise about arrival order at a destination, on any engine of this class. The rewrite does not cause that, it exposes it - if the answer changed when the key was spread, order-dependence was there before. Finally, the rewrite is a hand transformation. No runtime checks that the two-pass form still returns the original answer, so the check belongs to the author: run both forms over a slice small enough to finish quickly and compare per key, including the keys that were never spread.