A parameter that waits for another

Here are four fold shapes measured on thirty-two Misra-Gries summaries under round-robin partitioning, where every shard gets exactly 1,250 arrivals.

Chain: 918. Balanced tree: 917. Size-ordered: 917. Largest-first: 919.

That is a spread of two counts in nine hundred — a fifth of a per cent — across four constructions that build trees of height 31, 5, 5 and 31 and that any reasonable person would expect to differ. An essay that measured this and moved on would have been right to.

Here are the same four shapes on the same stream sharded by hashing instead, where the loads run from 402 to 7,087.

Chain: 323. Balanced tree: 148. Size-ordered: 183. Largest-first: 403.

Why the even case is exactly flat #

Two of the four collapses are identities rather than coincidences, and it is worth separating them from the third.

Size-ordered is the balanced tree. Huffman’s construction on equal weights builds a complete tree — the two smallest are any two, their union is heavier than the remaining singletons, and the pool works through a full level before starting the next. So the two shapes are the same tree, and their weighted path lengths agree exactly: 200,000 and 200,000. Not close; equal.

Largest-first is the chain. Its first merge takes the two largest, whose union is now larger than any singleton, so it takes the union and the next singleton, and so on. Height 31, same as the plain chain. The two differ only in which shard enters when, and under equal loads there is no “which”.

So under an even partition there are not four shapes. There are two, and the remaining question is why those two agree to a fifth of a per cent when a chain applies thirty-one cuts and a tree applies five.

The answer is that under round-robin every shard is a uniform sample of the same stream, so every shard holds the same keys. A Misra-Gries merge cuts by the $(k+1)$-th largest count in the union of the two tables — and if the two tables hold the same thirty-two keys, their union holds thirty-two keys, there is no thirty-third, and the cut is zero.

A fold of identical tables takes no cuts at all, at any depth, in any order. Thirty-one zeroes and five zeroes are the same sum. The shape parameter is multiplied by a quantity that the partition has set to nothing.

What the uneven case supplies #

Hashing sends each key to exactly one shard. So two shards hold disjoint key sets, their union holds up to sixty-four keys against a table of thirty-two, and there is a thirty-third largest to cut by.

Now the fold has cuts in it, the cuts are sized by the mass at each node, and the shape decides how many of each size a survivor passes through. The measured cut totals are 309, 254, 259 and 388, and the damages track them.

This is the same structural fact the partition the analysis did not mention priced from the other direction. There, the partition was shown to change which structure pays; here it is shown to change whether a third parameter is connected to anything at all.

The number that says which regime a deployment is in #

If the shape’s leverage depends on whether the shards hold different things, then the quantity to look at is how different they are — and there is one already computed.

The load spread is the crude version: 1.00 under round-robin and blocked, 17.6 under hashing. It is crude because it is about mass and the mechanism is about keys; two shards could hold equal masses of entirely disjoint keys and the spread would report nothing while the cuts were large.

The sharper version is the distinct load — how many keys the $m$ tables hold between them, against the $m \cdot k$ slots the deployment allocated. Under round-robin at thirty-two shards that is a little over thirty keys against 1,024 slots, because every table holds the same ones. Under hashing it approaches 1,024, because they hold disjoint ones. That ratio is what decides whether a merge has anything to discard, and it is computed from the shard histograms before any structure is allocated.

The bill a partition only divides is where that quantity was introduced, for a different purpose. It turns out to be the gate on this parameter too, which is the kind of reuse that suggests it is the right quantity rather than a convenient one.

The shape of the measurement failure #

The generalisation is worth stating carefully, because “vary two parameters instead of one” is both correct and useless as advice — the number of pairs is quadratic and most of them are independent.

The useful version is narrower. When one parameter multiplies a quantity that another parameter can set to zero, measuring the first at the second’s zero measures nothing, and the result is not “small effect” but “no information”. Those are different findings and a table of numbers reports them identically.

What distinguishes them is available before the measurement and costs nothing: look at the mechanism and ask what the parameter acts on. The fold shape acts on the sequence of cuts. If there are no cuts, it acts on an empty list. That question is answerable by reading the merge rule, and it would have flagged round-robin as the wrong partition to measure the shape under without a single run.

It is the same trap as a benchmark run on an input the code has a special case for, and it fails the same way: quietly, in the direction of “no difference found”, which is the direction a tired reader accepts. A limit is not a prediction is this site’s standing warning about believing an asymptotic statement at a size nobody ran; this is the version where the statement is fine and the input has switched the phenomenon off.

The reason it is worth a whole essay rather than a caveat is that the flat result is genuinely informative once it is understood. “The four shapes agree to a fifth of a per cent under round-robin” is not a null result — it is a prediction of the mechanism, and a strong one, because the mechanism says the agreement should be exact for two of the pairs and near-exact for the third. Getting 917, 917, 918 and 919 is the mechanism passing a test, not the measurement failing to find anything.

It needs depth as well #

The partition is necessary and it is not sufficient, which the shard sweep makes plain.

At two shards there is one merge and every shape is the same shape. At four there are three merges and a chain of four differs from a tree of four by two levels. At thirty-two the chain applies thirty-one cuts and the tree five, and that is where the 2.7 appears.

So the shape’s effect is a product of two conditions — an uneven partition and a deep fold — and a deployment satisfying only one of them can fold however it likes. That is most small deployments, and it is another reason this has stayed unmeasured.

Space-Saving, which has no cuts at all #

The other counter structure gives the same answer through a different mechanism, and the agreement is worth having.

Space-Saving’s merge takes no cut. For a key absent from one side it adds that side’s floor, and nothing is subtracted from anybody. So the quantity the shape acts on is not a list of cuts but a list of floors — the floor of whatever summary the key was merged against, at each level.

Under round-robin the heavy key is present in every shard, so it is never absent from either side of any merge, and it is charged nothing at all whatever the shape. Under hashing it lives in one shard and is absent from every other, and now the floors on its path are what it pays. The measured damages are 634, 457, 469 and 501 against a flat 665-to-667 under round-robin.

Two structures, two unrelated merge rules, and the same conditional: the shape matters when and only when the partition makes the shards hold different things.

That the two agree is worth more than either result. The structures are the same structure under a stream — two structures that are one is where this site established that — and they stop being the same structure under a merge, which is the whole of the reversal those essays measured. So an agreement between them about a third parameter, arrived at through two different mechanisms, is evidence that the conditional is about the partition rather than about either merge rule.

Where this leaves the two folds built for it #

The size-ordered fold was built for these essays, to test whether the construction that provably minimises a weighted path length also minimises a merge’s bill. The fold that minimises the wrong thing is the answer — it does not — and the identity above is what makes that a finding rather than a coding error.

Under round-robin the size-ordered fold’s path length is exactly the balanced tree’s, to the arrival, because equal weights make the two constructions the same tree. That equality is the strongest available check that the builder is doing what it claims: an approximate agreement could be luck, and an exact one across every even partition cannot be. Under hashing it is 123,134 against the tree’s 147,365, which is a genuine 16% improvement in the thing Huffman minimises.

So the two partitions do two different jobs for that essay. The even one certifies the construction; the uneven one is where the construction has something to be optimal about, and where it loses on the quantity that is actually being paid.

The shape one structure will not fold then depends on the same condition from the other side. The trade it describes — a shape that saves a quantile summary a fifth of its space and costs a counter table 2.7 times its error — exists only under hashing. A deployment on round-robin holds two structures that both do not care, and has no decision to make.

What else has been measured at a zero #

The uncomfortable question this raises is what else on this site was measured with a second parameter parked where it switches the first one off, and it deserves an honest answer rather than a reassuring one.

The audit is not hard for this strand, because there are only a few parameters. The bias function was swept under a fixed partition, and the bias acts on the cap rather than on the merge, so the partition does not gate it. The window length was swept under a fixed arrival process, and the boundary that hides the burst is precisely the finding that the arrival process gates it — that one was caught, and it was caught by building the process that made it non-zero.

The one that is genuinely open is the tolerance. Everything about $\varepsilon$ in this collection is measured under a stationary stream, and a stationary stream is the one where the summary’s realised error is furthest below its promise. Whether $\varepsilon$’s effects look different where the promise binds is not something measured here.

A third parameter that behaves the same way #

The pattern is not unique to the fold shape, and one more instance is worth putting beside it because it was found the same way and in the same strand.

The merge’s bias function — whether a quantile summary’s cap is uniform, tail-weighted or head-weighted — is worth a large factor in state, and it is worth nothing at all in the counter tables, which have no cap. That is trivially true and nobody would measure it. The non-trivial version is that the bias’s effect on a merge depends on the shard count: the cheap tail and the expensive merge measures the biased family at 6.3 times the unbiased one at two shards and 3.7 at sixty-four, which is a factor of 1.7 in the ratio itself across the sweep. Measured at one shard count it is one number; measured at two it is a trend.

And the counter width $k$ is a fourth. It gates the fold shape as surely as the partition does, from the other side: at $k$ large enough to hold the union of every table, no merge ever discards, and the shape is again multiplied by zero. That is the same identity as the round-robin case reached by making the table bigger rather than the shards more alike, and it means a deployment can switch this whole phenomenon off by over-provisioning $k$ — which is worth knowing, and is not free, and is measured nowhere here.

Switching it off with $k$ costs more than the structure is for #

The fourth gating parameter named above — a table wide enough that no merge ever discards — deserves a price, because it is the one a deployment might reach for without noticing what it has bought.

Under hashing at thirty-two shards the tables hold nearly disjoint key sets, so their union approaches $m \cdot k$: about a thousand keys against a table of thirty-two. To make the final merge discard nothing, $k$ has to hold that union, which means raising $k$ by a factor of thirty-two — and $k$ is per shard, so the deployment’s total state goes from $32 \times 32 = 1{,}024$ counters to $32 \times 1{,}024 = 32{,}768$.

Now compare that against the thing a summary is an approximation of. The universe here is 2,048 keys, so an exact count of every key in the stream is 2,048 counters. The over-provisioned sharded deployment is sixteen times larger than counting everything exactly, and it is still approximate.

The crossing arrives long before the switch-off does. A sharded deployment costs $m \cdot k$ counters and an exact one costs $U$, so the summaries stop being a saving at

$$k \;=\; \frac{U}{m} \;=\; 64$$

— one doubling of the current width. Past sixty-four counters a shard, thirty-two summaries of this stream cost more than counting every key exactly, and the merge damage they are still paying is a cost the exact count does not have.

So the $k$ route is not a way of switching the phenomenon off; it is a way of leaving the regime where approximate counting is the right tool, and arriving there by a parameter that looks like a quality dial. The honest form of the option is: if $k$ can be raised to $U/m$, do not shard summaries at all.

Against which the fold shape is free. Choosing a balanced tree rather than largest-first takes the measured damage from 403 to 148 — a factor of 2.7 — at no cost in memory, no change to any structure, and one line in whichever code arranges the reduction. Two levers on the same quantity, one of them costing thirty-two times the memory and the other costing nothing, and only the expensive one is a parameter anybody thinks of as tunable.

That is worth stating as the practical reading of this whole essay. The fold shape is invisible under an even partition and worth a factor of 2.7 under an uneven one; the width is visible everywhere and is the wrong lever for this particular damage; and which of the two a deployment reaches for is decided by which one has a name in the configuration file.

The items that survive $k$ counters is where the width’s real job is measured — deciding which keys a single table holds, which is a question about a stream rather than about a merge. The fold that minimises the wrong thing is where the free lever turns out not to be free of subtleties either: the construction that provably minimises the path length is not the one that minimises the bill.

The same four shapes over the other counter structure say that the conditional is about the merge rule and not only about the loads.

And the two structures want opposite shapes, which is the thing a deployment folding both of them cannot arrange.

Halving the shard count halves the depth and leaves the finding where it was, which is the check that the effect is about the loads rather than about how many levels there are to accumulate over.

The check this leaves behind #

The claim here is a conditional and it is checked as one, in both directions: on the even partitions the four shapes must agree to within a fifth of a per cent, and on the uneven one they must differ by at least a factor of two.

Either clause alone passes on something useless. A check that only required the flat result would pass on a fold implementation that had quietly stopped varying its shape — which is the exact failure a green gate is most likely to be hiding, since a broken shape parameter produces four identical numbers everywhere and looks like a clean negative result. A check that only required the large result would pass on a measurement with no control in it.

The honest limit is that “even” here means two partitions that are even by construction — round-robin and blocked, both of which give exactly 1,250 arrivals per shard. Nothing between the two extremes is measured. Where the crossover sits, and whether the shape’s leverage rises smoothly with the load spread or turns on at some threshold of disjointness, is a sweep nobody has run and the machinery now supports.