Data in pieces: partitions and mergeable summaries

Merging variances exactly

Variance looks unmergeable, since it's built from distances to the mean and each partition has a different mean. It merges exactly if each partition keeps three numbers: its count $n$, its mean $\bar x$, and $M_2$, the sum of squared distances from its own mean. For partitions $A$ and $B$, with $\delta = \bar x_B - \bar x_A$:

In plain words: add the two partitions' own spreads, then add the spread between their two means, weighted by how many values sit on each side.

The last term adds back the spread between the two partitions' means, which each partition alone can't see. The sample variance is then $M_2 / (n - 1)$.

import statistics as st

def summary(xs):
    m = sum(xs) / len(xs)
    return len(xs), m, sum((x - m) ** 2 for x in xs)

def merge(a, b):
    (na, ma, m2a), (nb, mb, m2b) = a, b
    n, d = na + nb, mb - ma
    return n, ma + d * nb / n, m2a + m2b + d * d * na * nb / n

partitions = [[12, 15, 22, 30], [41, 38, 25], [14, 9, 61, 33, 20]]
s = summary(partitions[0])
for p in partitions[1:]:
    s = merge(s, summary(p))
print("merged:", round(s[2] / (s[0] - 1), 3), "direct:", round(st.variance([x for p in partitions for x in p]), 3))

The merged variance matches the direct calculation exactly, without any partition sharing its raw values.

na, ma, m2a = 2, 10, 2
nb, mb, m2b = 2, 20, 2
n, delta = na + nb, mb - ma
print(m2a + m2b + delta ** 2 * na * nb / n)

Sketches for what won't merge

For the statistics that won't merge, there are sketches: small, mergeable structures that give approximate answers with known error.

• Distinct counts: HyperLogLog keeps a few kilobytes per partition and estimates the number of distinct values within about 2%, merging by taking element-wise maximums. Databases use it for "unique visitors".
• Quantiles such as the median and the 95th percentile: t-digest and similar sketches keep a compressed outline of the distribution that merges and answers any quantile closely, especially near the tails.
• Most frequent items: Count-Min and similar sketches track the heaviest hitters in fixed memory.

When an answer must be exact, the system has to bring related data together, called a shuffle: every row moves to the worker responsible for its key. Shuffles are the most expensive step in most big-data jobs, so good pipelines filter and pre-aggregate before them.

def overall_mean(parts):
    return sum(mean for count, mean in parts) / len(parts)


print(round(overall_mean([(4, 19.75), (3, 34.67), (5, 27.4)]), 2))

Partitioning well, and checking whether it's big at all

Choose partitions by how the data is used. Partition logs by day, and a question about last week reads only seven partitions. Partition orders by a hash of the customer ID, and everything about one customer lands in one place, so per-customer summaries need no shuffle. Watch for skew: if one customer has 40% of the rows, the worker that gets them finishes last and the whole job waits for it. Store data in a columnar format such as Parquet, so a query that needs two columns reads two columns.

And check before you build. A few gigabytes fit comfortably on a laptop: DuckDB queries Parquet and CSV files larger than memory, and pandas can read a file in chunks and merge chunk summaries exactly as above. A cluster is worth its cost and complexity only when one machine really can't keep up.

Mergeable summaries also make data that arrives late cheap to handle. When yesterday's partition gets a few extra events this morning, summarize only the new events and merge them into yesterday's summary, instead of reprocessing the whole day. Streaming systems are built on this: each window keeps a mergeable summary and folds new events in as they come.