The summaries that add

A stream too large for one machine is split across a hundred of them. Each summarises its share. The hundred summaries are combined into one.

Whether that final summary is the same object as the one a single machine would have produced from the whole stream is a question with two different answers, and the field uses one word for both.

The three that lose nothing #

HyperLogLog merges by register-wise maximum. Register $j$ of the merged summary is the larger of the two inputs’ register $j$. The reason it is exact is that a register holds a maximum over the keys that landed there, and the maximum over a union is the maximum of the maxima. There is nothing approximate about that identity — it is the definition of a maximum.

Count-Min merges by cellwise addition. A cell holds a sum of counts, and sums add. The requirement is that both sketches used the same hash functions, which is a constraint on how they were constructed rather than on the merge, and a merge across different seeds is refused rather than silently producing a table of nonsense.

Bottom-$k$ merges by union and re-truncation. Take both sets of retained hashes, sort, keep the $k$ smallest. The $k$ smallest of a union are among the $k$ smallest of each part, so nothing that should have survived was thrown away early.

In all three the merged summary is bit-identical to the direct one. That is a strong statement and it has consequences beyond convenience.

It makes the summary a value rather than a process. Two systems that merged the same shards in different orders hold the same bytes, so they can be compared for equality, cached, checkpointed, and deduplicated. A pipeline that recomputes a summary after a failure produces the same answer as the one that did not fail.

It makes the operation associative and commutative, which is what allows a tree. A hundred summaries can be combined pairwise in any arrangement, in parallel, and the answer does not depend on the arrangement. The alternative — a fixed order — is a serialisation point in the middle of a distributed system.

It makes the whole thing idempotent when the underlying structure is. A HyperLogLog merged with itself is itself, so a shard delivered twice changes nothing. Count-Min merged with itself is not itself — the counts double, correctly — so the same protection does not extend to it, and the difference is exactly the difference between counting distinct things and counting occurrences.

The one that keeps its promise and not its state #

Misra-Gries is mergeable in a real and non-obvious sense, and the merge is not a maximum or a sum.

Add the two tables together key by key, keep the $k$ largest, and subtract the value of the $(k+1)$-th largest from everything that survives. The subtraction is what preserves the bound: it charges the surviving keys for the ones that had to be dropped, exactly as the decrement rule charges them during a single pass.

The result satisfies the same $N/(k+1)$ shortfall bound as a directly built table. Measured on two streams of forty thousand each with $k = 32$: the merged table’s worst shortfall is 1,814 and the directly built one’s is 1,815, against a bound of 2,424. As accurate, on this data, to within one count.

And it is a different object. The merged table holds thirty keys; the direct table holds thirteen. They are not the same thirteen. Both are correct, both satisfy the bound, and neither can be compared to the other for equality.

That is worth naming as a category rather than as a quirk, because the literature calls both properties mergeability and they support different things:

Exactly mergeable — the merged state equals the direct state. Supports equality, caching, deduplication, replay, and any arrangement of the merge tree.

Bound-preservingly mergeable — the merged summary satisfies the same guarantee. Supports the answer being trustworthy and nothing else.

A distributed system built on the first and specified on the second will work. One built on the second and assumed to have the first has a class of bug in it that appears only when two paths through the system are compared — a checkpoint against a recomputation, a replica against its primary — and reports a difference that is not an error.

What makes a structure mergeable #

The three that merge exactly have one thing in common: their state is a function of the set of items, not of the order they arrived in.

A register’s maximum does not care about order. A cell’s sum does not care about order. The $k$ smallest hashes do not care about order. So the state after a stream is determined by the stream’s contents, and any two ways of getting there agree.

Misra-Gries’s state depends on order, and it is easy to see how. The same multiset of items presented in different orders produces different tables — a key whose occurrences are clustered survives a competition that the same key spread thin would lose. Once the state depends on order, no merge can reconstruct the order-dependence of a hypothetical single pass, because the information about which order was never recorded.

That is a clean criterion and it holds up: every exactly-mergeable summary in this field is order-independent, and the one that is not, is not.

The hash functions have to agree #

The merges above are only defined between structures built the same way, and the constraint is sharper than it sounds.

Two HyperLogLogs with different hash seeds have registers that mean different things — key $x$ is in register 3 of one and register 900 of the other — so a register-wise maximum of the two is arithmetic performed on unrelated numbers. It produces a summary, it is not a summary of anything, and its estimate is plausible. That is the failure this field is most exposed to: a merge that runs, returns a number in the right range, and is meaningless.

So a merge across different seeds is refused, and the refusal is one of the checks the gate requires to fire. The practical form is a constraint on deployment rather than on code: every process summarising a shard of the same stream must be configured with the same hash seed, and a rolling upgrade that changes it silently invalidates every merge across the boundary.

Sampling, which does not merge at all #

The structure this field keeps being compared with is a sample, and it is worth showing that the property fails there, because the failure is instructive rather than incidental.

Reservoir sampling gives a uniform sample of $k$ items from a stream of unknown length, in one pass and $k$ slots — one pass, k slots measures it. Two reservoirs over two streams cannot simply be combined: taking $k$ of the $2k$ items at random gives a sample that is uniform over the union of the two samples, which is not the same as uniform over the union of the two streams unless the streams were the same length. Merging correctly requires knowing both lengths and sampling from the two reservoirs in proportion, so the summary is no longer self-contained.

That is not a defect of sampling; it is a consequence of the sample being a statement about a distribution over the stream rather than a function of the stream’s contents. The criterion above catches it: a reservoir’s state depends on the order and the length, so no order-blind merge can exist.

Why this is where the structures field wants it #

Mergeability is not an accuracy property, and it is not visible on any of the error plots in this phase. Two structures could have identical error curves and differ entirely here.

What it is, is an algebraic property of a data structure: the summaries form a commutative monoid under merge, with the empty summary as identity. That is the same kind of statement as “a heap maintains the heap property” or “a B-tree’s nodes are between half and completely full” — a structural invariant that makes a set of operations safe, and that has nothing to say about how fast or how accurate anything is.

It also explains why these structures displaced their predecessors in practice. Probabilistic counting, Misra-Gries and sampling all long predate HyperLogLog, and all of them answer their questions. What arrived with distributed processing was a requirement nobody had needed before — combine a thousand partial answers, in any order, with no coordination — and the structures that satisfy it are the ones now in every analytics system. The property that decided it is on this page and is not on any of the accuracy plates.

The property is checked again on a flatter stream over four times the key space, and again on a longer one with only the two cardinality structures, because bit-identical is a claim that has to be false somewhere if it is worth anything.

What a merge cannot recover #

One limitation is worth stating because it is easy to hope otherwise.

Merging combines summaries; it does not improve them. Two HyperLogLogs of a thousand registers each, over two halves of a stream, merge into a HyperLogLog of a thousand registers — not two thousand — and its accuracy is the accuracy of a thousand registers over the whole stream. The bits do not add.

That is obvious once stated and it is the opposite of what happens with samples, where two samples of size $k$ combine into a sample of size $2k$ and the estimate genuinely improves. It is another instance of the distinction the answer that is allowed to be wrong draws between a summary and a sample: a summary’s accuracy is fixed by its shape at construction time, and no amount of combining changes the shape.

The corollary is a sizing rule. A structure that will be merged across a hundred shards must be sized for the union’s cardinality, not for a shard’s, and sizing it for a shard produces a hundred summaries each perfectly adequate and one merged answer that is not.

For Count-Min the same rule bites harder, because the additive error is $\varepsilon N$ and $N$ for the merged sketch is the sum of all the shards’ streams. A width chosen so that a shard’s slack is acceptable gives a merged sketch a hundred times that slack, and the sketch will not complain — the merge is exact, the bound is satisfied, and the number returned is useless.

The property, stated once #

The three exactly-mergeable structures here share a form worth stating plainly, because it is what to look for in a structure that has not been examined yet.

The state is a function $\sigma$ of the multiset of items, and there is an operation $\oplus$ such that $\sigma(A \uplus B) = \sigma(A) \oplus \sigma(B)$. For HyperLogLog $\oplus$ is register-wise maximum; for Count-Min it is cellwise addition; for bottom-$k$ it is union followed by truncation. Each of those is associative and commutative, each has an identity, and that is the whole of the algebra.

Everything on this page follows from it. Order-independence is $\sigma$ being a function of the multiset. Reproducibility is $\sigma$ being a function at all. The merge tree is associativity. Idempotence, where it holds, is $\oplus$ being idempotent — a maximum is, a sum is not.

And the structure that fails is the one where $\sigma$ is not a function of the multiset. That is not a shortcoming to be engineered away; it is a description of what Misra-Gries is doing, which is running a competition, and a competition’s result depends on who met whom.

A monoid, and for one of them a group #

The algebra stated above stops at a commutative monoid, and it is worth asking which of these structures supports the next operation up — an inverse, so that a merged summary can have a shard’s contribution taken back out.

Count-Min can. Cells hold sums and sums subtract, so subtracting one sketch from another cellwise gives the sketch of the difference. That is the turnstile model arriving as an algebraic property rather than as a stream of negative updates, and it carries the same consequence: the one-sidedness does not survive it, so the retracted sketch’s estimates are two-sided even though every input sketch’s were not.

HyperLogLog cannot. A register holds a maximum, and a maximum has no inverse — knowing that the larger of two numbers is nine says nothing about which of them it was. Two shards that both saw a key with a long run of zeros both set the register, and removing one shard’s contribution requires knowing whether the other shard would have set it anyway.

Bottom-$k$ cannot, for the same reason at one remove: the retained set is a truncation, and the hashes that were dropped because they were too large are gone. Removing a shard might mean a previously-dropped hash should now be retained, and it is not there to be retained.

Misra-Gries cannot, and it could not even if it merged exactly.

That gives a sharper reason to prefer the sketch than accuracy ever does. A system that must retract — a shard discovered to be corrupt, a tenant whose data has to be removed from an aggregate, a late correction to a batch already merged — needs a group rather than a monoid, and exactly one of these four is one. Every other structure’s answer to “remove this shard” is to rebuild the aggregate from the remaining shards, which requires that the shards still exist.

So the algebra is not an abstraction over the engineering; it is the engineering. Whether a summary can be un-merged decides whether the raw data has to be kept, and keeping the raw data is the cost these structures exist to avoid.

Idempotence decides what the delivery guarantee has to be #

The idempotence remark above deserves following through, because it changes a requirement on the infrastructure rather than on the summary.

A HyperLogLog merged with itself is itself. So a shard’s summary delivered twice — by a retry, a redelivery after a timeout, a replayed log segment — changes nothing, and the aggregate is correct whether it arrived once or five times.

A Count-Min sketch merged with itself is not itself. Its counts double, correctly, because it is counting occurrences and the same occurrences have been counted twice. So a duplicate delivery is a wrong answer, silently.

That is the difference between a pipeline that can run on at-least-once delivery and one that needs exactly-once, and the second is dramatically more expensive: it requires deduplication keys, a store of what has been seen, and a coordination protocol that at-least-once does without. A great deal of distributed-systems machinery exists to provide exactly-once semantics, and a structure whose merge is idempotent does not need any of it.

A one-line algebraic property therefore decides which half of a distributed system has to be built. That is worth more than the accuracy difference between any two structures on this page, it is invisible on every plot in this field, and it follows immediately from whether $\oplus$ is a maximum or a sum.

The measurement, and what it had to be careful about #

Checking that a merge is exact sounds like it needs no care, and there is one way to get it wrong that would have made every result on this page vacuous.

The two input summaries have to be built with the same hash functions, and the natural way to construct two of anything is to construct them twice — which, with a seeded generator, gives two different sets of hashes. Two Count-Min sketches built that way merge into a table of numbers with no meaning, and the merged estimate for a heavy key comes out in roughly the right range, because a heavy key is heavy in both tables wherever it landed. The check would pass on a comparison of estimates and fail on a comparison of cells.

So the comparison here is cellwise and registerwise rather than answerwise: 1,024 registers, 256 cells, 128 retained hashes, each compared individually. An assertion on the estimates alone would have been satisfied by a merge that was wrong, which is the shape of mistake this whole site is arranged against — and the library builds its sketch pairs through a constructor that shares the hashes explicitly, so that the careless version is not the convenient one.

The same care applies in the other direction for Misra-Gries. The claim that it is not exactly mergeable is asserted by requiring the key sets to differ, and if they ever agreed the assertion would fire. A check that only verified the bound would pass whether or not the distinction this essay is about exists.