Algorithms & Data Structures
the bound is a claim, and it is checkable
One pass, and no room

The tuples a merge does not give back

A merge of thirty-two quantile summaries keeps seven times the tuples of one summary over the same values, and sixty-four keeps ten and a half. Fitted across the sweep the count goes as the shard number to the power 0.56, which answers what it converges to — it does not.
20 min read 7 figures Measured, not assumedSpace is the other axisA guarantee is not a result

A quantile summary is bought for its size. It answers rank queries to a stated tolerance while holding a few hundred tuples instead of twenty thousand values, and everything interesting about it is a statement about how few tuples that is.

The promise that does not survive the tree measured what a merge does to its accuracy and noted, in passing, that the merged summary also kept about seven times the tuples. Seven times what, at what shard count, tending to what — none of that was answered, and it is the half of the result a deployment pays for continuously rather than at query time.

The tuple count of a merged summary, fittedTuples kept by the merge of m summaries of 20,000 values, on log axes, so a power law is a straight line and the exponent is the slope. ε = 0.02: exponent 0.58, multiplier 283 against a single summary's 277; ε = 0.01: exponent 0.56, multiplier 527 against a single summary's 512; ε = 0.005: exponent 0.54, multiplier 942 against a single summary's 958. The multiplier is the single-pass tuple count to within 3%, so the shape is tuples(m) ≈ tuples(1)·m^α. Halving ε moves the multiplier and leaves the exponent where it was, so ε buys resolution and the shard count buys nothing but tuples.1,00010,000248163264ε = 0.02, α = 0.58ε = 0.01, α = 0.56ε = 0.005, α = 0.54tuples keptshards mergedlog-normal, σ = 1.2 — a latency distribution · 20,000 valuesα 0.58 / 0.56 / 0.54 · worst residual 2.0%
Fig. 1 Tuples kept by the merge of m summaries, on log axes so a power law is a straight line and its exponent is the slope. Three tolerances, twenty thousand values, and three lines that are parallel.

Why a merge cannot compress back

The structure keeps a sorted list of tuples, each carrying a value, the number of items it stands for, and how uncertain its rank is. A compression pass walks the list and folds a tuple into its neighbour whenever the combined weight and uncertainty stay inside the cap the tolerance allows at that rank. That is what keeps a single pass at a few hundred tuples over any number of values.

A merge interleaves two such lists. A tuple from one summary knows its rank among that summary’s items exactly as well as it did before, and knows nothing about its rank among the other summary’s items beyond which two of its tuples it falls between. So it inherits that gap as extra uncertainty, and the merged list is compressed with the merged cap.

Both halves of that move the wrong way at once. The uncertainties go up, which makes each tuple harder to fold; and the caps go up too, since the cap is proportional to the item count and the merged summary has twice as many items. If the second effect dominated, compression would recover everything. It does not.

The reason is that a tuple’s inherited uncertainty is charged against it, while the enlarged cap is shared with everything else in the neighbourhood. Two tuples that would have folded now carry two inherited gaps between them, and the cap has to cover both. The arithmetic works out to a merged list that is longer than either input relative to its own item count, every time, and the excess accumulates as the tree deepens.

What a merged quantile summary keeps, against the number of shardsA merged summary does not compress back to the size of an unmerged one. One high-biased summary at ε = 0.01 over 20,000 values keeps 512 tuples; the merge of 32 of them keeps 3,637. The tuples arrive from the shards already compressed to their own caps, and the merged cap is not tight enough to take them out again — so the space a query answers from grows with the number of machines that contributed to it.one summary: 51277921,15141,67782,454163,63732shards mergedtuples keptε = 0.01 · high-biased · log-normal, σ = 1.2 — a latency distribution7.1× the tuples
Fig. 2 The same growth read at the structure rather than at the fit. A single summary over the union stays where it is however the stream is divided; the merged one climbs.

The shape, fitted

Seven times at thirty-two shards is a point. The sweep is the shape, and the shape is fitted here rather than described, for the reason fitting a class to measurements gives: a growth claim read off the code is a guess about the code, and a growth claim read off measurements is a claim about the measurements.

At a tolerance of one per cent, high-biased, the counts are 779, 1151, 1677, 2454, 3637 and 5450 tuples at 2, 4, 8, 16, 32 and 64 shards, against a single summary’s 512. The fitted power law has an exponent of 0.559 and a multiplier of 527, and the worst departure of any point from the fitted line is 1.2 per cent.

The multiplier is the thing to notice. 527 against a single summary’s 512 — within three per cent, and the same coincidence holds at every tolerance measured: 283 against 277, and 942 against 958. So the shape is

tuples(m)  ≈  tuples(1)⋅mα\text{tuples}(m)\;\approx\;\text{tuples}(1)\cdot m^{\alpha}

with α\alpha near 0.56 and the constant supplied by the un-merged structure. A merged summary is the single-pass summary, multiplied by a power of the shard count.

It does not converge. There is no shard count past which the growth flattens, over the range measured, and the fit is close enough that a flattening would be visible. Doubling the machines multiplies the answer’s size by about 1.47, indefinitely as far as these measurements can see.

The honest limit applies here in its usual form and is worth restating rather than assumed. A fit across a measured range refutes and measures a constant; it does not establish a limit. What is claimed is that the counts follow this shape from two shards to sixty-four at three tolerances, and that anything with a plateau in it is refuted over that range.

The exponent belongs to the bias functionTuples kept by the merge of m summaries of 20,000 values, on log axes, so a power law is a straight line and the exponent is the slope. high-biased: exponent 0.56, multiplier 527 against a single summary's 512; low-biased: exponent 0.56, multiplier 540 against a single summary's 534; none-biased: exponent 0.74, multiplier 73 against a single summary's 77. The multiplier is the single-pass tuple count to within 5%, so the shape is tuples(m) ≈ tuples(1)·m^α. α is a property of the bias function — near 0.56 for the biased summaries and 0.74 for plain Greenwald–Khanna — and the answer to what it converges to is that it does not.1,000248163264high-biased, α = 0.56low-biased, α = 0.56none-biased, α = 0.74tuples keptshards mergedlog-normal, σ = 1.2 — a latency distribution · 20,000 valuesα 0.56 / 0.56 / 0.74 · worst residual 6.5%
Fig. 3 Three error functions. The two biased ones sit on top of each other with an exponent near 0.56; the unbiased summary starts at a seventh of their size and climbs at 0.74. The exponent belongs to the error function and not to the tolerance.

What the exponent depends on

Two dials were available and only one of them moves it.

Halving the tolerance moves the multiplier and leaves the exponent alone: 0.582, 0.559 and 0.541 at tolerances of two, one and half a per cent, against multipliers of 283, 527 and 942. The multipliers double as the tolerance halves, which is the usual 1/ε1/\varepsilon behaviour of the un-merged structure, unchanged by merging.

Changing the error function moves the exponent. High-biased and low-biased summaries both sit at 0.56; plain Greenwald–Khanna, whose cap does not depend on where in the distribution the tuple sits, is at 0.737 with a worse fit residual of 6.5 per cent.

That inversion is worth a moment. The biased summaries exist because a uniform tolerance is the wrong promise for a tail — a promise about the rank sets out why an absolute rank error of two hundred is useless at the ninety-ninth percentile — and they buy the tail’s resolution by keeping more tuples up there. So they start large. Under merging they then grow more slowly than the structure they were bought to replace, and the crossing never happens over this range: at sixty-four shards the unbiased summary holds 1,475 tuples and the biased one 5,450.

The structure with the better promise is the one whose merge is expensive, in absolute terms throughout, and by a smaller factor at large shard counts than at small ones. Neither of those is stated anywhere in either structure’s guarantee, which is a guarantee about ranks.

The compression that runs at the wrong moment

There is a tempting repair, and following it to where it fails explains the growth better than the arithmetic does.

A single-pass summary compresses on a schedule — once every 1/2ε1/2\varepsilon arrivals — and the schedule is what keeps its size flat. A merged summary compresses once, at the merge. So the obvious question is whether compressing harder afterwards would recover the size, and the answer is that there is nothing left to compress: the pass has already folded everything the caps permit, and running it again is a no-op.

The tuples that remain are not lazily kept. Each of them is a tuple whose uncertainty, after inheriting a gap from the other side, is too large to fold into its neighbour without breaking the promise. Folding them anyway is available and is a different structure with a different guarantee.

That is the same structural point the summary that has to forget makes about expiry — the state a structure holds is the state its guarantee requires it to hold, and reducing it means changing the guarantee rather than being cleverer. What the merge has done is push the uncertainty budget into a shape where fewer folds are legal, and no amount of re-running the same rule reverses that.

In bits, which is what is bought

Tuples are the structure’s own unit. The unit a deployment is billed in is bits, and the conversion is fixed — a value and two counters per tuple — so the growth is the same growth with a constant on it. It is worth drawing anyway, because the comparison that matters is not against one summary.

What the shards held, and what the answer costsThe same merge in bits. The pale bar is the state the m shards hold at the moment of the merge and the dark bar is the merged summary. At 64 shards the deployment holds 1,212,480 bits and the answer keeps 523,200 — 2.3× smaller, and still 10.6× a single summary over the union. The merge is a compression that does not get back to where one pass would have been, and the gap grows with the shard count.one summary248163264state, in bitsshards mergedε = 0.01 · high-biased · 20,000 values10.6× one summary at 64 shards
Fig. 4 What the shards hold at the moment of the merge, against what the answer keeps. The deployment’s state is larger than the answer at every shard count, and both are larger than one summary over the union.

At sixty-four shards the deployment is holding 1.2 million bits across its summaries and the merged answer keeps 523,000. So the merge is a compression, by a factor of 2.3 — and the thing it compresses to is 10.6 times what a single summary over the same values would have needed.

Both numbers are true and they support opposite sentences. The merge more than halves the state is true. The merge costs ten times the state is true. The first compares against the shards and the second against the summary the shards are standing in for, and the second is the comparison the state a merge is standing in for argued is the only honest one — for exactly the same reason, one level along.

The accuracy, so that the trade is a trade

None of this would matter if the extra tuples bought accuracy. They do not buy much.

The merged summary’s realised errors are small — a handful of ranks at the quantiles that matter, against a promise of a hundred at the median. What has grown is the state, not the error, and the state has grown by a factor of ten while the error has stayed inside a bound that itself moved.

So the trade is: pay ten times the space to get an answer whose accuracy is roughly what the single-pass summary would have given, having never had the values in one place. That is a defensible bargain for a system that genuinely cannot collect the stream, and it is not the bargain the structure’s specification describes. It is also the second time this collection has found a merge whose cost is in a currency its guarantee does not mention: the state a merge is standing in for found the counter tables giving up accuracy at constant space, and the quantile summaries give up space at nearly constant accuracy. Same operation, opposite axis, and in both cases the axis that moves is the one nobody was watching.

The reason the two structures differ that way is structural rather than incidental. A counter table has a fixed width, so a merge that cannot represent what it holds must lose accuracy; a tuple list grows, so a merge that cannot represent what it holds keeps more tuples. A structure with a fixed allocation converts merge damage into error, and a structure that grows converts it into space — which is a sentence about allocation policy rather than about quantiles, and it is the kind of thing space is the other axis exists to collect.

The shape of a quantile merge moves the bill, not the answer32 summaries of 20,000 values at ε = 0.01, high-biased, folded three ways. The upper bar is the tuples the merged summary keeps and the lower is its worst rank error over q = 0.5, 0.9, 0.99 and 0.999. The tree keeps 39% more tuples than the fold, for an answer that differs by 0 ranks against a promise of 100. The counter tables measured elsewhere in this collection do the opposite: their order moves the answer and not the space. A balanced tree merges equals, and a linear fold merges a large accumulator with a small arrival whose tuples inherit the accumulator's gaps and compress away.folded in one at a time2,616 tuples17 ranks outcombined pairwise, in a tree3,637 tuples17 ranks outfolded in, last shard first2,615 tuples17 ranks outtuples kept, and worst rank error against a promise of 10032 shards · ε = 0.01 · high-biased · round1.39× the space, 0 ranks of answer
Fig. 5 And the number is not even determined by the shard count. Folding the same thirty-two summaries in a different order changes the tuple count by nearly forty per cent, for an answer that moves by nothing.

That last plate opens the question the shape that moves the bill takes up: the tuple counts above were all measured with the shards combined pairwise in a tree, which is one of three orders a deployment might use, and the choice is worth more than a doubling of the shard count.

Where the tuples sit

One more property, because it decides whether the extra state is doing anything.

The merged summary’s extra tuples are not spread evenly along the distribution. They cluster where the caps are tightest, which for a high-biased summary is the upper tail — precisely the region the biased error function was chosen to resolve. So the growth is concentrated in the part of the structure a deployment cares most about, and it is not obviously waste.

It is also not obviously value. The realised rank errors up there are already far inside the promise, so the extra tuples are resolving a region that was not short of resolution. What has happened is that the merge’s inherited uncertainties are largest where the caps are smallest, so the fold fails most often exactly where the structure is densest.

The exponent belongs to the bias functionTuples kept by the merge of m summaries of 20,000 values, on log axes, so a power law is a straight line and the exponent is the slope. high-biased: exponent 0.58, multiplier 280 against a single summary's 293; low-biased: exponent 0.59, multiplier 293 against a single summary's 293; none-biased: exponent 0.72, multiplier 36 against a single summary's 38. The multiplier is the single-pass tuple count to within 6%, so the shape is tuples(m) ≈ tuples(1)·m^α. α is a property of the bias function — near 0.58 for the biased summaries and 0.72 for plain Greenwald–Khanna — and the answer to what it converges to is that it does not.1001,000248163264high-biased, α = 0.58low-biased, α = 0.59none-biased, α = 0.72tuples keptshards mergedPareto, α = 1.2 — a heavy tail · 20,000 valuesα 0.58 / 0.59 / 0.72 · worst residual 3.9%
Fig. 6 The same three error functions on a heavy-tailed input at a looser tolerance. The counts differ and the exponents do not, which is the separation this essay rests on.

The merge is not the only thing that grew

One more quantity moves with the shard count and it is easy to miss because it is not the structure’s own.

Every shard holds a summary while the merge is being computed. At sixty-four shards that is sixty-four summaries of a sixty-fourth of the values each, and a summary of n/64n/64 items is not a sixty-fourth the size of a summary of nn — it is a good deal more than that, because the tuple count of one of these structures grows slowly with the item count rather than proportionally.

Measured here, sixty-four shards hold 12,630 tuples between them against a single summary’s 512. So the deployment’s total state at the moment of the merge is twenty-five times what one machine would have held, before any merging has happened at all.

That is the same accounting that makes the merged answer’s ten times look modest, and it is the reason the comparison is drawn against the shards rather than against the single summary alone. A distributed summary is expensive in three places — the shards, the merge, and the answer — and only the third of them is what anybody calls the structure’s size.

The exponent sits halfway between the two things it could have been

An exponent of 0.56 is a measurement without a scale until it is set against the two exponents the merge could conceivably have had, and both of those are known.

A merge that lost nothing would keep what the shards keep. A Greenwald–Khanna summary’s tuple count is Θ(1/ε)\Theta(1/\varepsilon) — governed by the tolerance, nearly independent of how many items it has seen — so mm shards hold about mm times one shard’s list however the stream is divided. That is an exponent of 1.

A merge that lost nothing worth keeping would produce the summary a single machine would have built over the union, whose size does not move with mm at all. That is an exponent of 0.

Measured: 0.56, which sits almost exactly between them.

That is the quantitative form of the sentence this essay has been circling. The merge is neither a concatenation nor a re-summarisation; it recovers about half of what having the values in one place would have recovered, measured on the exponent, at every tolerance and both biased error functions.

The three-way comparison also settles the two true sentences that support opposite readings. At sixty-four shards the deployment holds 12,630 tuples, the merged answer keeps 5,450, and one summary over the same values would have kept 512. The merge more than halves the state and the merge costs ten times the state are both readings of that row — and the exponents say they will keep diverging: the first comparison improves with mm, because 1 exceeds 0.56, and the second worsens, because 0.56 exceeds 0.

So a deployment scaling out sees its merge look better and its answer look worse, from the same measurement. Which of the two a capacity plan should quote is the state a merge is standing in for’s question and its answer is the second: the merge is standing in for the single summary, and the single summary is what its specification describes.

The framing also says what a better merge rule would have to achieve, which is more useful than saying it does not exist. Anything that folds more aggressively moves the exponent towards zero and gives up promise; anything that folds less moves it towards one and gives up nothing but space. The exponent is the dial, it is currently at 0.56 for the biased structures and 0.74 for the unbiased one, and the difference between those two is the clearest evidence in this essay that the number belongs to the cap function rather than to the merge.

And it puts the fold shape in proportion. The shape that moves the bill measures a chain against a tree at thirty-nine per cent, which on this scale is a change to the constant and not to the exponent — worth taking, worth once, and not a way out of a growth that doubles the answer’s size every three doublings of the fleet.

What a capacity plan can now say

Before this, the available statement was the merge keeps more tuples than one summary would. What is available now:

A shape. Tuples go as the single-pass count times the shard number to a power near 0.56, over two to sixty-four shards, at three tolerances, with a worst residual of two per cent.

A constant that is already known. The multiplier is the un-merged structure’s own tuple count, which is the quantity every published account of these summaries gives. So a deployment that knows what one summary costs knows what the merge of mm costs, without running the merge.

A dependence on the value distribution that is not there at all. The counts come out identical on lognormal, uniform, Pareto and bimodal inputs, to the tuple, because the structure is rank-based and never looks at a value except to order it. That is the property the error that is on the rank established for the un-merged summary, and it survives merging intact.

A dependence that is the wrong way round. Tightening the tolerance buys resolution and leaves the growth exponent alone; changing the error function changes the exponent, and the function with the better tail promise is the one that starts larger and stays larger.

A rank promise of ±2% at q = 0.99 on log-normal, σ = 1.2 — a latency distributionThe curve is the empirical distribution of 20,000 values: the horizontal axis is the value, logarithmic and the vertical axis is the fraction of the stream at or below it. A promise about the RANK is the shaded horizontal band, whose height is fixed at ±2% wherever it is drawn. What it permits in the ANSWER is the vertical band it cuts from the curve, and that runs from 187 to 2,170 — a range of 623% of the true value at this quantile. The summary answered 2,170 against a true 318: a rank error of 1.00%, inside the promise, and a value error of 581.7%, about which the promise says nothing. The two errors are the same number exactly when the distribution is flat, and the gap between them is the slope of this curve.answered 2,1700%25%50%75%100%0.36420.52,170value, logarithmicfraction of the stream at or belowrank ±2%value 187–2,170answered 581.7% out20,000 values · log-normal, σ = 1.2 — a latency distribution · Greenwald–Khanna, ε = 0.02rank 1.00% · value 581.7%
Fig. 7 The quantity all of this is spent on. A rank error is not a value error, and the same rank tolerance is worth wildly different amounts at different points of the distribution — which is the reason the biased summaries exist and therefore the reason their merge is the expensive one.

The remaining question this leaves is what the exponent is, as opposed to what it measures at. The residuals drift slightly with the number of values — the fitted exponent moves from 0.52 to 0.57 as the stream grows from four to thirty-two thousand — which on this site’s own reading is the signature of a power law that is not quite one, in the way the constant the notation drops describes for the sorts. Whatever the true form has in it, it is a slowly growing factor and not a plateau, and none of these measurements is consistent with the merge settling down.

Where this goes next

quantilepromisedone summarymerge of 8q = 0.5100.01418q = 0.920.0183q = 0.992.005overq = 0.9990.214overrank error, in items out of 20,000ε = 0.01 · high-biased · 8 shards, round2 of 4 quantiles over the single summary's promise The promise that does not survive the tree A high-biased quantile summary at ε = 1% answers the 99th percentile of twenty thousand values to within two ranks. Merge thirty-two of them and the answer is seventeen ranks out — inside the merged bound, eight times outside the one anybody was quoted. answered 4,1900%25%50%75%100%11.794,190value, logarithmicfraction of the stream at or belowrank ±2%value 24.9–4,190answered 1553.5% out20,000 values · Pareto, α = 1.2 — a heavy tail · Greenwald–Khanna, ε = 0.02rank 0.10% · value 1553.5% A promise about the rank is not a promise about the value A quantile summary asked for the 99th percentile of a log-normal stream returns the largest value it ever saw — 2,169 against a true 318, six times too high — and its rank error is 1.00% against a promised 2%. The guarantee held. It was never about the number. folded in one at a time2,616 tuples17 ranks outcombined pairwise, in a tree3,637 tuples17 ranks outfolded in, last shard first2,615 tuples17 ranks outtuples kept, and worst rank error against a promise of 10032 shards · ε = 0.01 · high-biased · round1.39× the space, 0 ranks of answer The shape that moves the bill Thirty-two quantile summaries combined pairwise keep 3,637 tuples and the same thirty-two folded in one at a time keep 2,616, for answers that differ by nothing at all. The counter tables measured for the same thing do the opposite — their order moves the answer and leaves the space alone.

What this makes readable

Essays that name this one as a prerequisite.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

Every essay whose body links to this one.

The objects this essay names

Each one links to every other essay that touches it.

Curve fittingGreenwald–KhannaGuaranteeHonest limitMerge treeMergeable summaryPartitionQuantile summaryRank errorShardSpace overheadState bitsSummary