The fold that minimises the wrong thing

There is already an account here of what a merge fold costs, and it has an obvious consequence nobody took.

What a fold charges per level established that a Misra-Gries merge takes a cut — the $(k+1)$-th largest count in the union of the two tables, subtracted from every survivor — and that a surviving key therefore pays the cuts on its own path from leaf to root. A chain of thirty-two applies thirty-one of them to a key that was present from the start; a balanced tree applies five.

Write that as a sum. If each shard’s keys are worth its load $w_i$, and a key in shard $i$ passes through $d_i$ merges, the total charge across the fold looks like

$$\sum_i w_i \, d_i$$

which is a weighted external path length — and there is a classical construction that minimises exactly that quantity. Huffman’s: repeatedly combine the two smallest.

So build it, and see whether the fold that minimises the path length is the fold that minimises the bill.

It does minimise the path length #

The first thing to check is that the construction is doing what it is famous for, because a result about an optimal fold that turns out not to be optimal is a bug rather than a finding.

Under hashing, where the shard loads run from 402 to 7,087, the four folds give weighted path lengths of 542,649 for the chain, 200,000 for the balanced tree, 123,134 for the size-ordered fold, and 738,384 for its mirror. The size-ordered fold is least, as Huffman’s exchange argument requires it to be.

And there is a control that pins down what “weighted” is doing. Flatten every weight to one and re-run: the size-ordered fold ties the balanced tree exactly, because on equal weights Huffman’s construction is a complete tree. If the quantity being minimised had nothing in it, the size-ordered fold would have come out least in both cases, and the optimality would have been an artefact of tree shape rather than of weights.

And it does not minimise the damage #

The worst error left on the sixteen heaviest keys runs: chain 323, balanced tree 148, size-ordered fold 183, largest-first 403.

The size-ordered fold is second. It lands between the chain and the tree, which is exactly where the note left behind by that essay guessed it would land — and the guess and the arithmetic disagreed, because the arithmetic said it should land below both.

On Space-Saving the same ordering holds with a smaller gap: 634, 457, 469, 501. The tree wins; the size-ordered fold is close behind; the path length says the size-ordered fold should be ahead.

Ruling out the easy explanations first #

Before accepting that an optimal construction is losing, three cheaper explanations have to go.

The weights could be the wrong ones. The fold compares summaries, so its weight is the summary’s own total rather than the shard’s arrival count — a deployment folding summaries has the summaries and not the shards, and using a quantity it could not know would make the construction unbuildable. Those two numbers differ: a Misra-Gries table’s total is the arrivals minus every decrement, so it is below the shard load by the decrements the shard ran. Re-running with the shard loads as weights gives the same tree here, because the decrement is a small and nearly proportional deduction on a stationary stream. On a stream where it were not, the two weightings would build different trees and the construction would be optimal for whichever one it was given.

The damage could be measured on the wrong keys. It is the worst error over the sixteen heaviest, which is the statistic the whole strand has used since the state a merge is standing in for. Taking the mean instead moves the numbers and not the ordering; taking the single heaviest key moves neither.

The tie-breaking could be doing it. Huffman’s construction is under-specified when weights tie, and a different tie rule builds a different tree of the same path length. The pool here breaks ties by shard index, deterministically. Under hashing there are no ties to break — the loads are all distinct — so the tree is unique and the question does not arise.

None of those is the explanation, and what is left is the account itself.

A level is not a fixed charge #

The error in the account is in one word. “A fold charges per level” is true, and it was read as “a fold charges a fixed amount per level”, which is not.

The cut at a merge is the $(k+1)$-th largest count in the union of the two tables. Two small tables merged give a small cut; two large ones give a large one. So the charge at a node scales with the mass under that node, and a fold that gives a heavy key a short path does it by making the merges on that path bigger.

Huffman’s construction does exactly that, deliberately. It puts the heavy leaves near the root — that is what minimising $\sum w_i d_i$ means — and a leaf near the root is a leaf whose one or two merges are against everything else that has already been accumulated.

The two effects nearly cancel, and the residue has the wrong sign. Which means the quantity to look at is not the depth but the cuts themselves.

The quantity that does track #

Sum the cuts the fold actually took, over every merge, and the ordering comes out right.

Chain 309, balanced tree 254, size-ordered fold 259, largest-first 388 — against damages of 323, 148, 183 and 403. The least cut total and the least damage are the same shape, and the ordering agrees across all four.

That is not a coincidence and it is not a proof either. The cut total counts every cut once, while a survivor pays only the cuts on its own path, so the two quantities are the same only up to how the cuts are distributed. They agree here because the fold shapes that take many cuts also take them where survivors are, and a fold could in principle be constructed where they came apart. Nothing here builds one.

The maximum cut is a third statistic and it is instructive because it orders the shapes differently again: 25, 75, 59, 24. The balanced tree takes the largest single cut of the four and leaves the least damage, and largest-first takes the smallest single cut and leaves the most. A deployment reasoning about worst-case single events would have picked the wrong fold twice.

What the shapes actually look like #

The heights are worth writing down, because they explain both structures at once. The chain and largest-first both have height 31, the balanced tree has height 5, and the size-ordered fold has height 8.

Eight rather than five is the price of the uneven loads. Huffman’s tree is unbalanced by construction — small leaves go deep, big ones stay shallow — and with a seventeen-fold spread the smallest shards end up three levels below the deepest a balanced tree would have put them. The heavy key, meanwhile, sits at depth two or three rather than five, which is where the path-length saving comes from and where the larger cuts come from as well.

The same question, asked of the other structure #

Space-Saving’s merge takes no cut. For a key absent from one side it adds that side’s floor; nothing is subtracted from the survivors. So the middle column above is empty and the ordering has to come from somewhere else.

It comes from the floors, and the floors have the same property the cuts do: the floor of a merged summary grows with the mass under it. A key travelling a short path through a Huffman tree is charged two or three large floors rather than five moderate ones, and the arithmetic comes out the same way. The floor charged at every level is that account written out, and it is exact — the floors on a survivor’s path sum to the measured damage to the unit, at every shard count.

Which means the two structures fail the path-length prediction for the same reason in two different currencies, and that is a stronger result than either alone. A cut and a floor are unrelated quantities computed by unrelated rules, and both of them scale with the mass at the node, so both of them punish a shallow path.

Why the reasoning was worth doing anyway #

It would be easy to file this as a wrong guess corrected by a measurement, and that undersells what the exercise produced.

The path-length framing is what made the control obvious. Once the bill is written as $\sum w_i d_i$, the question “what happens when all the $w_i$ are equal?” answers itself — Huffman becomes a complete tree — and that predicts the four shapes should collapse under round-robin. They do, to a fifth of a per cent. The framing was wrong about the optimum and right about the condition, and the condition is the finding that a parameter that waits for another is built on.

It also produced the mirror fold, which nobody would have thought to build otherwise. Largest-first is a bad idea for a counter table by every measure here — 403 against the tree’s 148 — and it is the best of the four for a quantile summary’s space. That contrast is the shape one structure will not fold, and it exists because a construction was built to be an adversary and turned out to be somebody’s optimum.

The construction, and what it was designed for #

It is worth saying plainly what Huffman’s construction is optimal for, because the mismatch is instructive rather than embarrassing.

It minimises $\sum w_i d_i$ over all binary trees with the given leaves, and it does so because of one exchange argument: in an optimal tree the two smallest weights are siblings at the maximum depth, so combining them first is safe, and the argument recurses. That is the whole proof and it makes no reference to what $d_i$ is being paid for. It is a statement about a sum, and any cost that is genuinely $\sum w_i d_i$ is minimised by it.

A prefix code is such a cost. The expected code length is $\sum p_i \ell_i$ with $\ell_i$ the depth, and a bit at depth three costs exactly what a bit at depth one costs — one bit. That is the property this fold does not have. The optimal code that is beaten is where this site meets the construction in the setting it was built for, and the difference between the two settings is the whole of this essay: there, a level is a bit; here, a level is whatever the mass at that node makes it.

Which suggests a repair rather than an abandonment. If the charge at a node is roughly proportional to the node’s mass, the right objective is not $\sum w_i d_i$ but $\sum_{\text{nodes}} \text{mass}(\text{node})$ — except those are the same quantity, since summing a leaf’s weight once per ancestor is summing each node’s mass once. So the two objectives coincide and the measurement still disagrees with both, which means the charge is not proportional to the mass. The cut is the $(k+1)$-th largest count, and how that grows with mass depends on the distribution’s shape at that node, which is not a linear function of anything.

That is the sentence the whole strand comes down to. A fold’s bill is not a function of its shape and its weights; it is a function of its shape and the distributions the shape brings together, and no tree-building construction gets to see the second.

Two more readings of the same four shapes, because the finding is a conditional and a conditional needs its other side drawn.

What a deployment should take from it #

If the shards are even, the shape does not matter and any of the four will do. That is most map-reduce arrangements and it is the reason this has stayed invisible.

If the shards are uneven — which is what hashing on a skewed key distribution produces, and hashing on a skewed key distribution is what a heavy-hitter deployment is for — fold in a balanced tree. Not the chain, which costs 2.2 times; not size-ordered, which is 24% worse than the tree despite being provably optimal for a quantity that turns out not to be the bill; and certainly not largest-first.

And the general form, which is the part that outlives these particular structures: a construction that is optimal for a stated objective is optimal for that objective. Checking that the objective is the bill is a separate step, it takes one measurement, and the case where the objective is nearly right is the case where skipping the step is most expensive — because a nearly-right objective produces a fold that is nearly best, and a fold that is nearly best is indistinguishable from a fold that is best until somebody draws the third column.

One more reading, and it is the one to carry away from the whole strand. Three quantities were computed for four folds — path length, cut total, damage — and no two of them agree on which fold is best. The path length says size-ordered, the cut total and the damage say the tree, and the maximum single cut says largest-first. Four shapes, four statistics, three different winners. One run, two counts is a standing theme on this site and it usually means two ways of counting the same cost; here it means something sharper, which is that “what a fold costs” was never one number and the shape it is best in depends on which number somebody is paying.

What is now buildable that was not #

The tree builder this essay needed reads the fold back rather than just folding it — the cut at every node, the mass at every node, the depth every leaf ended at — and that machinery is worth more than the four shapes it was built for.

It is what makes the floor charged at every level possible at all, because that account needs the floor of the summary on the other side of every merge, which no reducer exposes. It is what turns a fold from a function into an object with statistics on it.

And it makes a family of folds buildable that nobody has reason to want yet but somebody will: fold by arrival time, fold by geography, fold to minimise the maximum single cut rather than their sum. The first two are what a real deployment does by accident. The third is a genuine optimisation problem with a different answer from any of the four here, and this essay’s numbers say it would produce the worst damage of the lot.

The honest limit is the range. All of this is at thirty-two shards, thirty-two counters, a stationary Zipf stream and a seventeen-fold load spread. The size-ordered fold’s deficit against the tree is 24% on Misra-Gries and 3% on Space-Saving — the second of those is small enough that a different stream could reverse it, and nothing here sweeps the spread to find where the two cross. What is robust across everything measured is the negative: the fold that minimises the weighted path length is never the fold that minimises the damage, on either structure, under any uneven partition tried.

Why one structure cares about the shape and the other nearly does not #

The 24% and the 3% are treated as two samples of one quantity, with the second flagged as fragile. They are not two samples. They are a shape-sensitive structure and a nearly shape-blind one, and the merge rules say which is which before any stream is chosen.

Space-Saving charges per absent key. A key pays one floor for every side of every merge it is missing from, and under a hashed partition it is missing from all but one — so the bill is very nearly $m-1$ floors whatever order the merges happen in. The shape moves which floors, not how many, and the floors differ only by the mass under them.

Misra-Gries charges per merge. One cut, taken from the summed table and subtracted from every survivor, at each of the $m-1$ nodes. The cut’s size depends entirely on how much mass has accumulated under that node — so where a heavy shard sits in the fold decides what its merge costs, and the shape decides that directly.

So a shape-blind bill and a shape-determined bill, and the measurements land where the rules predict: 3% against 24%, a factor of eight.

Which makes the fragility warning the wrong worry. The 3% is not a small number that a different stream might reverse; it is the residue of a quantity the shape barely reaches, and a stream would have to make the shard floors differ wildly before it could grow — which is the same condition the floor charged at every level needs, and which a seventeen-fold load spread does not supply.

The recommendation survives either way and gets a rider. Fold in a balanced tree, and on Space-Saving expect it to be worth almost nothing — which is one run, two counts again, with the two counts belonging to two structures rather than to two currencies.