What a fold charges per level

A merge of $m$ summaries is $m-1$ applications of a two-argument rule, and the two shapes anybody builds differ in how those applications are arranged. A chain applies them in sequence, so a value entering at the first shard passes through all $m-1$. A balanced tree applies them in levels, so a value passes through $\lceil \log_2 m \rceil$.

That difference is the whole of what follows. Where a merge rule charges something per application on a value’s path, the chain costs $m-1$ of it and the tree costs $\log_2 m$; where it charges per shard, the arrangement is irrelevant. Both kinds occur, in the same family of structures, and one of them has been measured here with the shape fixed all along.

The measurement #

Thirty-two shards, thirty-two counters each, arrivals routed by a hash of the key. Worst error over the eight heaviest keys.

Misra-Gries: 148 under a balanced tree, 323 under a chain, 323 under the chain reversed.

Space-Saving: 455 under the tree, 571 under the chain, 603 reversed.

The same thirty-two summaries. The same rule. A factor of 2.2 on one structure and 1.3 on the other, decided by an association nobody writes down.

Where the charge is #

The Misra-Gries merge adds two tables, keeps the $k$ largest and subtracts the $(k+1)$-th largest from every survivor. The subtraction is the charge, and it is charged once per merge on the value’s path.

So a key that enters at the first shard of a chain and survives to the end pays thirty-one cuts. The same key in a balanced tree pays five. The cuts are individually smaller in the chain — the accumulator is only ever being asked to absorb one shard’s worth of new keys — but not thirty-one fifths smaller.

The arithmetic that prices this from the histograms alone is available, and it folds predicted tables in whichever shape the deployment uses. Along a chain at thirty-two shards it puts the cuts on a survivor’s path at 299 arrivals; along a tree at 178. Measured, the two folds differ by 175. The model is not exact and it gets the ordering, the scale and the mechanism.

The depth is the multiplier, and $m-1$ against $\log_2 m$ is a factor of six at thirty-two shards and a factor of sixteen at two hundred and fifty-six. Nothing in the structure’s description mentions the depth of a fold, because the structure’s description is about one merge.

Where the charge is not #

Under round-robin the three shapes give 927, 927 and 928 at eight shards, 924 three times at sixteen, and 918, 917 and 918 at thirty-two. There is no effect, at any shard count, on either structure.

The reason is in the plate above. Round-robin puts every heavy key on every shard, so the tables hold the same six keys above their floors, so the union of any two of them fits inside thirty-two slots, so no merge ever has to discard anything. A merge with nothing to discard is exact, and an exact merge is associative.

That is the useful general statement, and it is sharper than this operation happens not to be associative: exactness and order-blindness travel together. A merge is associative when it either discards nothing or can show at the moment of discarding that what went could not have mattered. The cardinality structures merge exactly and are associative for that reason — the summaries that add is the measurement — and these do not and are not.

So the shape’s cost is not a property of the structure. It is a property of the structure, the partition and the stream together — and the same deployment that makes Misra-Gries the good choice at merge time is the one that makes its fold shape irrelevant.

A cut is not a constant #

It is tempting to read thirty-one cuts against five as six times the damage and stop. The measurement says 2.2 times, and the gap between those two numbers is where the interesting behaviour is.

A cut is the $(k+1)$-th largest entry of the summed table, so its size depends on what is being summed. Along a chain the accumulator is large and the incoming shard is small, so the summed table is barely wider than the accumulator and the $(k+1)$-th entry is small: the cuts run at three to seventeen arrivals apiece, thirty-one times. In a tree the two sides are equals and the summed table is nearly twice as wide, so the cut is large: the deepest levels cut by sixteen, seventeen and more, five times.

So depth and cut size move in opposite directions, and the chain wins on the second while losing badly on the first. The product is 2.2 rather than 6.

That is the same cancellation, one structure along, that makes the bill a partition only divides come out flat against the shard count: a sum whose length and whose terms move oppositely is a sum whose total is hard to guess and easy to measure. Counting the applications is not pricing them, and a rule of thumb built on the depth alone would be wrong by a factor of three here.

The other family, charged the other way #

The quantile summaries are folded by the same two shapes and they prefer the opposite one.

At thirty-two shards a chain keeps 2,616 tuples and a tree keeps 3,637, for answers that agree exactly. The shape that moves the bill works through why: a chain merges a large accumulator with a small arrival, and the arrival’s tuples are absorbed into the accumulator’s grid; a tree merges equals, and neither side has a grid to absorb the other into.

Put the two families side by side and the pattern is not that one shape is better. It is that each structure is charged on a different quantity:

• Counter tables are charged per merge on the path. Depth is the cost, so the tree wins.
• Quantile summaries are charged per merge on the imbalance. Lopsidedness is a discount, so the chain wins.

A system merging both kinds of summary — which is an ordinary thing for a monitoring pipeline to do — cannot pick a fold that suits both. That is a real and small consequence, and it is the sort of thing that is invisible until the two costs are written in the same currency.

What this does to the numbers already published #

Every merged counter figure in this collection was measured with a balanced fold, which was chosen because a parallel reduction is what a reduction is and not because anything had been compared.

That choice turns out to have been the favourable one for the counter tables and the unfavourable one for the quantile summaries. So the counter-table damage reported elsewhere — 536 for Space-Saving and 152 for Misra-Gries at eight shards under hashing — is a best case, and a coordinator folding those same eight shards in sequence would see 577 and 171. At thirty-two shards the gap is much wider: 455 and 148 against 571 and 323.

None of the conclusions move. The reversal between the two structures under the two partitions holds under every shape measured; so does the flatness of the error against the shard count under hashing; so does the observation that a merge is never better than one summary holding the same total state. What changes is that each of those statements now has a fold attached to it, in the way the model a bound was quoted in argues every bound needs a machine attached to it.

It is a small correction and it is the kind worth making explicitly, because the alternative is a set of numbers that are right under an assumption nobody stated and that nobody can check.

Why the reversed chain is not the forward one #

One asymmetry worth noting, because it says the effect is about sizes rather than about order.

For the quantile summaries the forward and reversed chains agree to a tuple — 2,616 and 2,615 — because reversing changes which shard is absorbed first and not the fact that every merge is lopsided.

For the counter tables they do not always agree. At sixteen shards Misra-Gries gives 218 forward and 258 reversed, and Space-Saving 592 and 627. The cuts along the two chains differ because the tables being folded in are different tables, holding different keys with different masses, and the order they arrive in decides which of them is present when a cut is taken.

So the counter merge is sensitive to the sequence and the quantile merge is sensitive only to the shape. The first is the stronger failure and the one the order nobody fixed reported at thirty-two shards, where fifty-two keys move by up to 950 arrivals between associations. Both are failures of associativity; they are failures of different strength.

What the depth is worth against what the width is worth #

The two dials a deployment has are the number of shards and the shape of the fold, and it is now possible to compare them.

Going from eight shards to thirty-two under hashing moves the Misra-Gries error from 152 to 148 under a tree — nothing — and from 171 to 323 under a chain. So at fixed shape the shard count barely matters in one case and matters a great deal in the other, and the reason is that the chain’s depth grows with the shard count while the tree’s grows with its logarithm.

That is the finding the bill a partition only divides could not reach, because the bill is a sum over shards and has no depth in it. The bill accounts for everything under round-robin, where the cuts are zero. Under hashing the cuts are the difference between the bill and the measurement, and the cuts are where the tree enters.

Where the shape stops mattering #

There is a third regime, and it is the one a deployment would most like to be in.

The cuts are zero whenever the two tables being merged hold at most $k$ keys between them. That is guaranteed when each table holds at most $k/2$ keys above its own floor, and it is a condition on the stream and the partition rather than on the width alone: it says the shards’ key sets overlap enough that their union fits.

Under round-robin on a stationary stream the tables hold six keys above their floors between all thirty-two of them, so the condition holds with enormous margin and the fold is free. Under hashing at thirty-two shards the union is 327 keys against a width of thirty-two, so it fails everywhere.

Between those there is a boundary, and the quantity that locates it is the count drawn two plates above — the distinct keys the tables hold between them. It is computable from a histogram, before any structure exists, in the way the floor a histogram already knows computes the floors. So a deployment can ask, in advance, whether its fold shape is going to matter, and the answer is a comparison between one number and its table width.

Depth is a resource the model already counts #

The pattern here is not new to this collection, which is worth saying because it suggests where to look next.

A pass over a stream is a resource: a bound stated for one pass is a different bound from the same result at two, and making the pass count a parameter and sweeping it produced a field’s worth of results. A direction is a resource in the same way — every streaming lower bound is stated for some number of passes and every one of those passes runs forwards, and the direction turns out to be worth a factor of the window length on a windowed question.

The depth of a merge tree is the third quantity of that kind. It is counted by the machinery — a fold of $m$ shards performs $m-1$ merges whatever its shape, and each of them is charged to some subset of the values — and it appears in no statement of what a merge costs.

What the three have in common is that each is a property of the schedule rather than of the algorithm. The rule is the same rule; what changes is how many times it runs against a given value and in what order. Every result in this collection about a summary has now met at least one of them, and the merge tree is the one that was hardest to see because a reduction is such an ordinary thing to write.

The two factors, separated, and how each scales #

The essay’s own numbers are enough to split the damage into its two parts, and the split says how the fold’s value moves as a deployment grows.

Damage is depth times the mean cut. For Misra-Gries at thirty-two shards: the chain’s 323 over thirty-one cuts is 10.4 arrivals a cut; the tree’s 148 over five is 29.6. So the tree’s cuts are 2.8 times the chain’s, the chain’s depth is 6.2 times the tree’s, and the product is $6.2 \times 0.36 = 2.2$ — the measured ratio, recovered from the two totals.

Both factors were described qualitatively above and the numbers pin them: the chain’s cuts run around ten arrivals because its accumulator is only ever absorbing one shard’s worth of new keys, and the tree’s run around thirty because it merges equals and the summed table is nearly twice as wide.

Now scale. At eight shards the chain gives 171 against the tree’s 152 — a ratio of 1.13. At thirty-two it is 323 against 148 — a ratio of 2.18. So the fold’s value grew by 1.9 while the depth ratio grew by 2.66, from 2.33 to 6.2. The cut sizes absorbed the difference: the chain’s cuts get relatively smaller as the chain gets longer, because its accumulator grows while the arrivals do not.

Two things follow that a depth-only rule of thumb would get wrong.

The fold matters more at scale, and by less than the depth suggests. Anyone reasoning from $m-1$ against $\log_2 m$ alone would predict a factor of six at thirty-two shards; the measurement is 2.2, and the over-prediction is the cut sizes moving the other way. That is the same cancellation this essay already names, quantified — and it is the reason the account has to price the cuts rather than count the merges.

And the choice becomes worth making at exactly the scale where it stops being made deliberately. At eight shards the fold is worth thirteen per cent and no reasonable person would design around it. At thirty-two it is worth a factor of two. A deployment small enough to fold by hand is small enough not to care; one large enough to care is one where a coordinator is folding reports as they arrive, which is a chain, chosen by network timing.

So the practical form of this essay’s finding is not use a tree. It is that the default shape is a chain, the default gets worse as the fleet grows, and it gets worse in the currency the structure’s guarantee does not mention. The order nobody fixed measures the strong version of that — an association decided by which shard reported first, moving fifty-two keys by up to 950 arrivals — and this is the weaker and more predictable half of it: not which chain, but that it is a chain at all.

The quantile family inverts the whole paragraph and is worth reading beside it. There the chain is the cheap fold, by thirty-nine per cent at the same shard count, and the default is therefore the good one — so a deployment folding both kinds of summary at one coordinator has one structure benefiting from the arrangement and one paying for it, with no shape that serves both. The shape that moves the bill is that measurement, and the two together are why a fold deserves recording rather than deciding once.

What to record with a merged number #

Three things, none of which is currently recorded anywhere.

The fold. A merged counter table is not determined by its inputs, and the association is decided by network timing as often as by design. A number reported without it is one of several legal numbers.

The partition, because it decides whether the fold matters at all. Under a routing that puts every key on every shard, the association is irrelevant and any of them may be used freely.

The depth, which is the actual quantity in the arithmetic — the thing the pass that was never a parameter is about, one structure along: a count the model contains and the statement of the result does not. A reduction over a hundred shards in a tree has a depth of seven; the same hundred folded at a coordinator has a depth of ninety-nine, and the second is fourteen times the first on a quantity that shows up directly in the error.

The last of those is the one worth carrying out of all four of these essays. A merge’s damage separates into a term that depends on the shards and a term that depends on the tree, and only the first is what anybody means by the cost of merging. A guarantee is not a result applies to both terms equally: every table drawn in this essay is inside its bound, and the bound is wide enough to contain a factor of two that a deployment chose without knowing it had.