The floor a merge does not settle at

The account is exact and it needs a run. That is the position the last two essays leave, and it is a step backwards from where the arithmetic stood before them.

The floor charged at every level established what a fold charges: the floor of the summary on the other side of every merge a surviving key passes through. Read those floors off an actual fold and they sum to the measured damage to the unit, at every shard count. But reading them off a fold means building the fold, and the whole value of the arithmetic was that it prices a deployment before anything is allocated.

The obvious repair is to predict the level floors the same way the floor a histogram already knows predicts the leaf ones: merge the shard histograms pairwise and run the same fixed point on each merged one. It is three lines, it needs no structure, and it over-predicts by up to 1.73.

Why the histogram over-predicts #

The fixed point answers a specific question: what floor would a summary of $k$ counters settle at, if it were run over these arrivals?

A merged summary was not run over them. It was assembled from two summaries that were, and assembly is a different process from arrival.

Watch what each does to a heavy key. A fresh run over the union puts the key in, evicts it whenever it falls to the smallest counter, reinstates it at the floor, and repeats — every one of those eviction cycles pushing the table’s smallest counter up. A merge takes two tables that already hold the key with large counts, adds them, and the key sits near the top of the merged table without ever having been part of an eviction cascade at the merged scale.

So the merged table’s $k$ largest entries are, in effect, the two tables’ heavy keys carried across intact, and the $k$-th of them — which is the floor — is lower than the value an eviction cascade would have driven it to.

Measured at thirty-two shards the shares are 0.825, 0.752, 0.707, 0.749 and 0.717 over five levels. A merged summary’s floor is around three quarters of a fresh one’s.

The same fact, seen from the guarantee #

There is a second reading of the deficit that is worth having beside the mechanical one, because it says the merged summary is better rather than merely different.

A summary’s floor is the whole of its overestimate: a key held with count $c$ has a true count somewhere in $[c - \varphi, c]$. So a merged table with a floor of 241 and a fresh table with a floor of 345 over the same arrivals are making different promises about the same data, and the merged one’s is tighter.

That should be surprising and is not, once the state is counted. A merged summary of thirty-two shards was assembled from thirty-two tables of thirty-two counters — 1,024 counters’ worth of observation — and compressed to thirty-two. A fresh summary saw the same arrivals with thirty-two counters throughout. More state was in play, so a better answer comes out. The state a merge is standing in for is where this site established that a merge has to be scored against a matched single summary given $m \cdot k$ counters rather than $k$, for exactly this reason, and the merged-floor deficit is that same effect measured on the floor rather than on the error.

Which reframes the prediction problem usefully. The fixed point is not wrong about the merged summary; it is answering a question about a different structure — the one that saw the same arrivals with less state — and the law is the exchange rate between them.

It is not one constant #

The tidy version of this essay ends there, with a constant of 0.75 and a corrected prediction. It is not what the measurements say.

Across shard counts the share moves: 0.903 at four shards, 0.827 at eight, 0.797 at sixteen, 0.750 at thirty-two, 0.696 at sixty-four. That is a smooth decline and it is straight in $\log_2 m$:

$$\text{share}(m) \;\approx\; 1.007 \;-\; 0.0518 \log_2 m$$

with a worst residual of 3% over the range.

And it should be. The deficit is incurred once per level — each merge is an assembly rather than a run — so a fold of $m$ shards accumulates $\log_2 m$ of them. The intercept lands at 1.007, which is the statement that a fold of a single shard is a fresh summary, and the fitted law finding that on its own is the strongest evidence that the mechanism is the right one.

A constant would have been a fudge factor. A law with an intercept at one is an account.

What the correction recovers, and what it does not #

Apply the law and the three predictions read, against the measurement, at 4, 8, 16, 32 and 64 shards:

• Leaf floors: 1.01, 1.00, 0.90, 0.78, 0.54
• Level floors, uncorrected: 1.13, 1.27, 1.51, 1.57, 1.73
• Level floors, corrected: 1.05, 1.10, 1.22, 1.18, 1.20

The first two walk away and the third does not. Above sixteen shards the corrected ratios span 0.04 — 1.22, 1.18, 1.20 — while the other two are still moving at the right-hand edge with no sign of settling.

The correction removes the growth and leaves a bias. That is the honest summary and it is deliberately not dressed up: the prediction is about a fifth too high above sixteen shards, consistently, and this essay does not explain the fifth.

It is worth noting which direction the correction goes, because it is the counter-intuitive one. The uncorrected model predicts too much damage, and the correction makes the predicted damage smaller. A reader expecting a correction to a merge model to add a cost that was being missed has it backwards: what was being missed is that merging is gentler on the floor than running is, so the model was charging for evictions that never happened.

Why a trend and a bias are different failures #

It is tempting to read 20% as worse than it is, or better, and the distinction that matters is not the size.

A trend means the model is missing a term that depends on the sweep variable — which is what a floor with two variables in it found the missing term to be. It will be wrong by more at ninety-six shards than at sixty-four, and by an amount nobody can bound without extending the measurement. The leaf model’s 0.54 is that: it is not 46% wrong, it is 46% wrong here and worse elsewhere.

A bias means the model has the right shape and a wrong constant. It will be 20% high at ninety-six shards too. That is a number a deployment can carry — multiply by 0.83 and stop worrying — in a way that a trend never is.

So the value of the correction is not that it turns 73% into 20%. It is that it turns an unbounded error into a bounded one, and the fact that the residual is flat is the evidence that the remaining term does not depend on the shard count.

How close anything gets to the floor makes the general case for this site’s attention to constants; this is the case where the constant is the whole of what is left.

Three more readings of the same law, because a correction fitted at one width and one shard count is a correction that has been fitted to nothing.

That law is fitted on one width, so the next question is whether the width is in it. It is the obvious place for a missing term to hide: a wider table has more counters for the eviction cascade to run through, and a merged summary skips that cascade at every level.

So the answer is that the width is not in it, and the way to show that is to run the whole comparison again at twice the counters and see whether any of the three curves moves.

What the remaining fifth might be #

Three candidates, none of them measured here, listed so that the gap has a shape rather than being a shrug.

The fold is balanced and the histogram merge is too, but the pairings may differ. The level account pairs the summaries in the order the fold does; the histogram version pairs the histograms in the same order, and both are index order. That should be identical and a difference here would be a bug rather than a finding. It was checked and it is not the gap.

The share is a mean over the level and the charge is a specific summary’s floor. The law gives the mean share at a level; a particular key is merged against a particular sibling, whose floor may sit either side of that mean. Averaging a nonlinear charge over a distribution biases it, and the direction is plausibly the observed one. This is the candidate with the most behind it and it is testable — charge the sibling’s own predicted floor rather than the level mean — and it was not tested.

The fixed point’s own accuracy degrades on merged histograms. It lands within 1% of a fresh summary’s floor on a stationary shard, and a merged histogram at the top of a fold is a union of thirty-two shards’ key spaces with a different shape. The validation behind that number swept streams and widths and not this.

The residual has a shape, and it names a candidate #

A flat twenty per cent is how the leftover is described, and the five corrected ratios do not quite say that. They read 1.05, 1.10, 1.22, 1.18, 1.20, which is a rise of seventeen points between four and sixteen shards and then four points of movement across the next two doublings.

So the residual is not a constant bias. It is a term that rises and saturates, and the distinction matters twice.

It matters for the advice. Multiply by 0.83 and stop worrying is right above sixteen shards and wrong below: applied at four shards it turns a five-per-cent overshoot into a twelve-per-cent undershoot, which is a larger error than leaving the correction alone. The usable form is narrower — apply it above sixteen shards, and below eight leave the corrected prediction as it stands, since it is already within five per cent there.

And it matters for the diagnosis, because a saturating term rules things in and out. The correction is per level and the level count goes 2, 3, 4, 5, 6 across the sweep, so a per-level error that was uniform would give a residual growing at every step. This one grows while the fold is shallow and stops once it is deep, which is what an error concentrated in one level looks like once that level’s share of the total stops changing.

The exact account at sixty-four shards says which level. Its charges are 2, 8, 20, 43, 88 and 248, so the top level is 61% of the 409, and every level below it together is 39%. The corrected model predicts 493 — an excess of 84, which is 34% of the top level’s charge and would be 100% of the fourth level’s. A model wrong by a third on the last merge and right on the rest reproduces the whole discrepancy; no distribution of the same error over all six levels does, because the shallow levels are too small to carry it.

That points at the third candidate rather than the second. The top level is exactly where the fixed point is asked about a union of thirty-two shards’ key spaces, and the validation behind its one-per-cent accuracy swept streams and widths on single shards — never a union of that shape. A floor with two variables in it is the reason to expect trouble there specifically: the table’s share of the key space is what the fixed point is sensitive to, and it is at its smallest and moving fastest at the top of a deep fold.

The second candidate, averaging a nonlinear charge over the level’s distribution, would spread its error across every level in proportion to how many merges each holds — which is the shape the residual does not have. It is not ruled out, since the top level holds one merge and the widest spread of sibling floors, and those two effects work in the same direction. But the arithmetic above says the cheap test is the other one: run the fixed point on a single merged histogram at the top of a deep fold and compare against that summary’s actual floor. One merge, one comparison, and it either finds a third or it does not.

None of that is measured here either, and saying which candidate the shape favours is a smaller claim than testing it. What it does is replace a flat twenty per cent nothing explains with a residual that is concentrated, localised to one merge, and checkable in one run — which is the state the floor a histogram already knows left the leaf model in before it was settled.

The cost this puts back into the arithmetic #

There is a price to the law and it should be stated in the same breath as the recovery.

The original claim was that a merge can be priced from the histograms and nothing else — no summary allocated, no arrival replayed. That claim is now false above eight shards, and it is false in a specific way: the arithmetic needs one number that is not in any histogram, namely what a merge does to a floor.

The law makes that number cheap. It is $1.007 - 0.0518\log_2 m$, it takes the shard count as its only input, and a deployment knows its shard count. But it was fitted from runs, and a fitted constant is a different kind of object from a computed one. If a deployment’s stream, width or partition put it somewhere the fit was not measured, the law is a guess wearing a residual.

That is the honest limit here, and it is the shape this site’s limits usually take: an arithmetic that ran entirely before the run now has one number in it that only a run produces, and the number is small, stable, and derived from a mechanism that predicts its own intercept.

What this says about the other structure #

Misra-Gries’s merge takes a cut rather than charging a floor, and the same question can be asked of it: is a merged table’s cut what a fresh run’s decrement rounds would have produced?

Almost certainly not, for the same reason. Two structures that are one established that the floor and the decrement count are the same quantity under a stream, so a mechanism that lowers one lowers the other. But the merge rules differ — one adds an absent side’s floor, the other subtracts the $(k+1)$-th largest from every survivor — so the size of the deficit is a separate measurement and nothing here makes it.

What a fold charges per level measures the cuts a fold takes and compares them against the damage, and the agreement there is good enough that a 25% systematic bias would have shown. Which suggests the Misra-Gries side does not have this problem, or has a smaller one, and neither of those is established here.

Where the law does not apply #

Under round-robin the correction is unnecessary and the reason is worth stating, because it explains why this went unnoticed for so long.

A heavy key under round-robin is present in every shard. Space-Saving’s merge charges only for a key absent from a side, so the key is charged nothing at any level, whatever the floors are. The whole apparatus — leaf floors, level floors, merged-floor shares — multiplies out to zero.

That is why a parameter that waits for another applies here as much as to the fold shape. Every quantity in this essay is gated on the partition making the shards hold different things, and a deployment on round-robin can ignore all of it.

Why the fit was believable before it was checked #

A fitted law with a residual of 3% is easy to accept and worth being suspicious of, because five points fitted with two free parameters is not much evidence.

Three things make it more than a curve through five dots.

The intercept was not fitted to be one. It came out at 1.007 from a least-squares line that had no reason to land there, and it is exactly what the mechanism predicts: a fold of a single shard performs no merges, so its floor is a fresh summary’s floor, so the share at $m = 1$ must be one. A fit that lands on a prediction it was not given is evidence in a way that a fit landing anywhere is not.

The slope has a unit that makes sense. It is per doubling of the shard count, which is per level of the fold, which is the granularity at which the deficit is incurred. A slope in $m$ rather than $\log_2 m$ would have needed explaining; this one is what the account already said.

And the within-fold spread is smaller than the across-fold movement. At thirty-two shards the five levels span 0.12 and the mean across shard counts moves by 0.21 over the range. If the share were noise rather than a function of $m$, those would be the other way round.

None of that makes it a derivation. It makes it a law that predicts its own boundary condition, which is the most a fit gets to claim on this site.

The check #

Two clauses, and the second is the one that took the longest to get right.

The share must be stable enough within one fold for a single number to stand for it — the levels of a thirty-two-shard fold span 0.12, which is inside the allowance — and the law must reproduce the measured share at that shard count to within 0.06.

Then the corrected prediction must beat both others, must land inside 28%, and — this is the clause the essay’s actual claim needs — the corrected ratios above sixteen shards must span less than 0.12. A check that only required the corrected model to be closest would pass on a model that was closest and still walking away, which is the failure the leaf model already demonstrates and which is invisible in any single-point comparison.

The honest limit, stated once more because it is the one that matters: the level floors are computable from histograms, the correction that makes them usable is a fitted law rather than a derivation, the intercept the law lands on is the strongest argument that the mechanism behind it is right, and what remains is a flat 20% that nothing here explains.