Algorithms & Data Structures
the bound is a claim, and it is checkable
The other axis

The cheap tail and the expensive merge

A summary whose tolerance tightens towards the tail keeps seven times the tuples of a plain one on a single pass, and after merging sixty-four shards it keeps three and a half times as many. The error function that buys a useful tail promise is also the one that pays most for never having the values in one place.
19 min read 8 figures Space is the other axisMeasured, not assumedThe model has parameters

The tolerance a quantile summary promises is a function, not a number. Plain Greenwald–Khanna allows every tuple the same rank uncertainty, proportional to the number of items. A high-biased summary allows a tuple near the top of the distribution far less and one near the middle rather more. The two structures run the same algorithm and differ only in that function.

A promise about the rank argued that the biased version is the one worth having, because a uniform rank tolerance is nearly worthless where it is needed. This is about what it costs, and the cost has two parts that were not previously separable.

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. 1 Three error functions merged across the same shards. The two biased ones lie on top of each other; the unbiased one starts far lower and climbs at a steeper slope, and never catches up over this range.

The first cost, which was known

On a single pass at a tolerance of one per cent over twenty thousand values, plain Greenwald–Khanna keeps 77 tuples. High-biased keeps 512 and low-biased 534.

That factor of about seven is the price of the tail promise and it is not a surprise. The biased cap shrinks towards the end of the distribution it favours, so tuples up there cannot fold, so the structure keeps them. The whole design is that the resolution is spent where the questions are.

Rank error as a fraction of the tail it is aboutThe same measurements as a plate reporting error against the stream, divided by the mass the quantile is about — 1 − q, which is a half at the median and a thousandth at q = 0.999. Averaged over 8 independent streams of 40,000 Pareto values. A relative promise is a flat line on this plate and an absolute one climbs, because the numerator is constant and the denominator is shrinking. Greenwald–Khanna: 0.64% → 1.37% → 3.63% → 47% → 100%; high-biased: 0.46% → 0.42% → 0.44% → 0.56% → 0.00%; t-digest: 0.33% → 0.50% → 1.15% → 11% → 56%. The vertical axis is logarithmic.0.1%1%10%100%0.50.750.90.990.999quantile asked forrank error ÷ (1 − q)Greenwald–Khanna7,080 bitshigh-biased56,064 bitst-digest5,952 bits8 streams per point · ε = 0.01, δ = 100denominator: the tail
Fig. 2 What the seven times buys, on a single pass. Relative rank error against quantile for three structures, and the two that keep more tuples are the two that stay useful past the ninetieth percentile.

What is worth restating is that the comparison is not between a good structure and a bad one. It is between two answers to what should the tolerance be a function of, and the plain version’s answer — a constant fraction of the whole item count — is the one that makes the ninety-ninth percentile’s error two hundred ranks out of twenty thousand while there are only two hundred items above it.

The second cost, which was not

Merge them and the gap does not close. It widens in absolute terms and narrows as a ratio, and both of those come out of a fit rather than an impression.

At one per cent, high-biased, the merged tuple counts go 779, 1151, 1677, 2454, 3637, 5450 from two shards to sixty-four. The unbiased summary goes 123, 194, 340, 576, 1005, 1475. Fitted, the exponents are 0.559 and 0.737.

So the structure that starts seven times larger grows more slowly, and at sixty-four shards it is 3.7 times larger rather than seven. Both are still growing.

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.71, multiplier 37 against a single summary's 38; ε = 0.01: exponent 0.74, multiplier 73 against a single summary's 77; ε = 0.005: exponent 0.71, multiplier 161 against a single summary's 152. The multiplier is the single-pass tuple count to within 6%, 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.1001,000248163264ε = 0.02, α = 0.71ε = 0.01, α = 0.74ε = 0.005, α = 0.71tuples keptshards mergedlog-normal, σ = 1.2 — a latency distribution · 20,000 valuesα 0.71 / 0.74 / 0.71 · worst residual 13.2%
Fig. 3 The unbiased summary alone, across three tolerances. The exponent stays near 0.72 as the tolerance moves through a factor of four, and the fit is visibly looser than the biased case — the points wander from the line by up to six per cent.

The exponent is a property of the error function and not of the tolerance. Halving the tolerance multiplies the multiplier and leaves the slope where it was, in both families. That is the separation this essay exists to make: the tolerance sets the size, and the error function sets the growth.

Why the flat cap grows faster

The mechanism is visible in what a merge does to a tuple.

A tuple inherits, from the summary it was not in, the gap between the two tuples of that summary it falls between. Where the other summary is dense, that gap is small and the inheritance is cheap. Where it is sparse, the gap is large and the inherited uncertainty may exceed the cap, in which case the tuple can never fold again.

A biased summary is dense exactly where its caps are tight. So a tuple landing in the tail inherits a small gap and is compared against a small cap, and a tuple landing in the middle inherits a large gap and is compared against a large one. The two scale together.

A flat-cap summary is sparse everywhere by comparison — 77 tuples over the whole distribution — so the inherited gaps are large relative to a cap that does not grow to meet them. More tuples survive each merge, proportionally, which is the steeper exponent.

The structure that spends its budget unevenly merges better, because the unevenness is a match to the unevenness of what a merge inflicts. Nothing in either structure’s design anticipated that; the biased caps were chosen for what a reader wants from the tail.

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.59, multiplier 296 against a single summary's 309; ε = 0.01: exponent 0.56, multiplier 540 against a single summary's 534; ε = 0.005: exponent 0.54, multiplier 964 against a single summary's 953. The multiplier is the single-pass tuple count to within 4%, 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.59ε = 0.01, α = 0.56ε = 0.005, α = 0.54tuples keptshards mergedlog-normal, σ = 1.2 — a latency distribution · 20,000 valuesα 0.59 / 0.56 / 0.54 · worst residual 2.4%
Fig. 4 The low-biased summary, whose resolution is concentrated at the bottom of the distribution rather than the top. It is a mirror image of the high-biased one and its exponents are the same to two places, which says the effect is about the shape of the cap function rather than about which end it favours.

The residual is a finding too

The two families do not merely have different exponents; they have different fit quality, and the difference is consistent.

The biased summaries’ counts sit on their fitted line to within one or two per cent at every tolerance. The unbiased summary’s wander by up to six per cent at one per cent tolerance and thirteen per cent at half a per cent, and the wandering is not random — the points bow, running below the line at the small end and above it at the large.

A bow on log axes is the signature of an extra slowly-growing factor, and it is the same signature fitting a class to measurements describes for a count that is really nlog⁡nn \log n and is being offered a pure power law. So the honest reading is that the flat-cap merge probably grows as something with a logarithm in it, and that a single exponent is a worse description of it than of the biased case.

Which is itself worth having. A structure whose merged size is well described by one number is easier to provision than one whose exponent depends on where in the sweep the reading is taken, and that difference is invisible in any presentation that quotes a single shard count.

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 Greenwald–Khanna summary at ε = 0.005 over 20,000 values keeps 152 tuples; the merge of 32 of them keeps 2,029. 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: 1522512416472381,230162,02932shards mergedtuples keptε = 0.005 · none-biased · log-normal, σ = 1.2 — a latency distribution13.3× the tuples
Fig. 5 The unbiased summary at the tightest tolerance measured, where the departure from a straight line is largest. The structure is small throughout and its growth is the least regular of the three.

In bits, and against the right baseline

The tuple counts convert to bits by a fixed factor, so the picture is the same picture with a scale on it. Drawing it is still worth doing, because the comparison a deployment needs is against what the shards were holding rather than against each other.

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 550,752 bits and the answer keeps 141,600 — 3.9× smaller, and still 19.2× 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 · none-biased · 20,000 values19.2× one summary at 64 shards
Fig. 6 The unbiased summary in bits: what the shards hold at the moment of the merge against what the answer keeps. The compression ratio is worse than the biased structure’s, which is the same finding in the other currency.

At sixty-four shards the high-biased deployment holds 1.21 million bits and the answer keeps 523,000 — a compression of 2.3. The unbiased one holds far less of both and compresses by less. So the biased structure is larger everywhere and gives back more of what it was holding.

The accuracy is not what moved

It would be a cleaner story if the extra tuples were buying something at query time. They are not, in either family.

All three structures answer to well within their bounds after merging, on this stream. What differs across them is the tail behaviour they had on a single pass, which is unchanged, and the state they now occupy, which is not.

That is the shape the guarantee that is per query describes from the other direction: a bound stated per query says nothing about the aggregate cost of being able to answer, and the aggregate cost is what a deployment provisions.

What a merge does to the promise itself

There is a second reason the biased family is the awkward one, and it is not about space.

The bound a merged summary is entitled to is the sum of what its parts were entitled to, divided by the items. For a flat cap that arithmetic returns the same tolerance, because every part promised the same fraction of its own count. For a biased cap it does not, because the cap depends on rank and the ranks are being reshuffled by the merge.

The promise that does not survive the tree measured the consequence: a high-biased summary at one per cent promises two ranks at the ninety-ninth percentile and the merge of thirty-two delivers seventeen. It has not broken its own bound, which is the summed one; it has broken the one a reader was quoted.

So the biased family pays twice at the merge — in tuples, measured here, and in the distance between the printed promise and the realised one, measured there. Both are consequences of the same property, that its budget varies along the distribution, and that property is the reason to buy it.

A choice that is now two choices

Before this the decision looked like one dial with a known trade: pick an error function, pay for the tail resolution once, in tuples.

It is two dials with a coupling.

Pick the error function for the queries. If the questions are about the tail, a flat cap is not a cheaper way of answering them — it is a way of not answering them, and the digest that promises nothing sets out the third option, a structure with excellent observed tail behaviour and no bound at all.

Then price the deployment separately, because the same choice fixes a growth exponent as well as a size. Over two to sixty-four shards a biased summary is between 6.3 and 3.7 times the unbiased one, and which end of that range applies depends on how many machines the stream is spread over rather than on anything about the questions.

The shape of a quantile merge moves the bill, not the answer32 summaries of 20,000 values at ε = 0.01, none-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 80% more tuples than the fold, for an answer that differs by 69 ranks against a promise of 200. 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 time559 tuples43 ranks outcombined pairwise, in a tree1,005 tuples56 ranks outfolded in, last shard first559 tuples112 ranks outtuples kept, and worst rank error against a promise of 20032 shards · ε = 0.01 · none-biased · round1.80× the space, 69 ranks of answer
Fig. 7 And there is a third dial nobody set. The unbiased summary folded three ways at thirty-two shards keeps between 559 and 1,005 tuples — a spread of 1.8, larger than the biased structure’s 1.39 — for rank errors that differ by less than the promise.

That spread is bigger than several of the effects this essay has been careful about, and it is decided by the order a coordinator happened to receive its shards in. The shape that moves the bill takes it up.

The value distribution has nothing to do with it

One thing the sweep pins down that is easy to assume and worth confirming: none of these counts depends on the values.

Run the same measurement over lognormal, uniform, Pareto and bimodal inputs of the same length and the merged tuple counts come out identical — 842, 1248, 1852, 2725, 4065, 6116 in three of the four cases, to the tuple, and within one per cent in the fourth. The structure never looks at a value except to order it, so a monotone relabelling of the inputs changes nothing it does.

That is the property the error that is on the rank established for the single-pass structure, and its survival through merging is a useful negative: whatever governs the exponent, it is not the shape of the distribution being summarised. The remaining candidates are the error function, which does govern it, and the tolerance, which does not.

It also means a capacity plan does not need to know the distribution. It needs the item count, the tolerance, the error function and the number of shards, and the first two of those are already in the structure’s own literature.

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 284 against a single summary's 294; ε = 0.01: exponent 0.56, multiplier 528 against a single summary's 526; ε = 0.005: exponent 0.54, multiplier 956 against a single summary's 961. 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 mergedtwo clusters with a gap between them · 20,000 valuesα 0.58 / 0.56 / 0.54 · worst residual 2.4%
Fig. 8 The high-biased family on a bimodal input, where the values cluster in two places and the ranks do not. The counts are the lognormal counts to within one per cent.

The two deterministic families having been priced against each other, the third is worth placing beside them before the summary.

Where the third structure sits

There is a third quantile structure in this collection and it is worth placing on the same axes, because it makes the trade look different again.

The t-digest keeps centroids whose permitted size shrinks towards both ends of the distribution, so it has the biased structures’ concentration of resolution in the tail without stating an epsilon anywhere. What it does not have is a bound: its argument is that the centroid sizes are controlled and that the observed relative error at the tails is small, and observation is not a guarantee.

That places it awkwardly here. Its size is a parameter rather than a consequence, so its merged growth is a different question — the structure has a compression step that runs on the merged centroid list and returns it to the configured size. It does not grow with the shard count in the way either deterministic family does, and it pays for that by having nothing to say about what its answers are worth after merging.

So the three structures are three points on a trade that is not one-dimensional: a bound that survives merging and grows, a bound that survives merging and grows faster from a smaller base, and a fixed size with no bound at all. Which of those is right depends on whether the answer’s error has to be defensible or merely small, and that is a question about the consumer rather than about the stream.

The merge compresses more as the fleet grows

The essay reads the exponents as a cost — both families grow with the shard count, and the growth is what a deployment has to provision. Read them the other way and they say something reassuring that the framing has hidden.

An exponent below one means the merged summary grows more slowly than the fleet does. The shards between them hold mm summaries; the answer holds m0.56m^{0.56} of one. So the compression the merge achieves improves with every machine added:

shards biased, held on shards merged compression
2 1,024 779 1.3
8 4,096 1,677 2.4
64 32,768 5,450 6.0

At two shards the merge barely earns its name — it returns three quarters of what it was given. At sixty-four it returns a sixth. A merge is a poor summariser of two summaries and a good summariser of sixty-four, which is exactly the direction anybody deploying one would want and is not what an exponent quoted as a growth rate suggests.

The unbiased family does the same thing less well, from 1.25 at two shards to 3.3 at sixty-four, and the reason is the reason for everything else in this essay: its tuples inherit gaps too large for its caps, so fewer of them fold at every merge.

Two provisioning numbers fall out and both are more useful than the exponents themselves.

Doubling the fleet costs 47% more coordinator memory for the biased family and 65% for the unbiased one — 20.562^{0.56} and 20.722^{0.72}. A team adding machines is not adding coordinator state in proportion, and a plan that assumed it was is over-provisioned by a factor that grows with the fleet.

And the coordinator’s share of the total falls. At two shards the merged answer is three quarters of what the fleet holds; at sixty-four it is a sixth. So the coordinator stops being the memory problem as the deployment grows, and the shards — which hold their own summaries regardless — become it. That is a reversal of where the anxiety belongs, and it happens somewhere in the range of shard counts this sweep covers rather than beyond it.

Neither statement contradicts anything above. The biased summary is still larger at every shard count, still growing, and still the expensive one. What the compression column adds is that the rate it is expensive at improves, and that the single-machine ratio — the one everybody quotes — is the worst reading of it available.

What the numbers say

The claim is narrow and the sweep behind it is stated with it, in the form this collection uses for growth rather than as an assertion about limits.

Over two to sixty-four shards, twenty thousand values, three tolerances spanning a factor of four, and four value distributions: the merged tuple count is the single-pass count times the shard number to the power 0.56 for both biased families and 0.72 for the unbiased one, with worst residuals of two and six per cent respectively.

That is a description of a measured range. It refutes anything that plateaus and it refutes the two exponents being the same; it does not establish what either of them tends to, and the drift of the fitted values with the stream length says the true form probably has a slowly growing factor in it. A limit is not a prediction is the standing statement of what a finite measurement is allowed to conclude, and it binds here as much as it does on a sorting curve.

What the numbers are good for, within that, is the decision they were taken for. A team choosing between these two structures has always had a size comparison available at one machine, and the comparison changes by a factor of two across a plausible range of shard counts. Sixty-four machines is not an unusual deployment for a structure whose entire reason to exist is that the stream cannot be collected in one place, and at sixty-four machines the received figure — the biased summary costs about seven times as much — is wrong by nearly a factor of two in the direction that favours it.

So the practical statement is short. Price the error function at the shard count the system will actually run at, not at one. The single-machine ratio is the worst case for the biased family, and every machine added moves the comparison in its favour without ever making it cheap.

Where this goes next

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% 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. 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. 1101001,0000.111010010³true count of the keyrelative errorheaviest keyrarest key4×64 counters · 8,192 bits · Zipf s = 1.1 · 3,528 distinct keys at 702 positions4.11% to 34100% The guarantee that is one query wide A sketch described as accurate to within a per cent is accurate to within a per cent of the whole stream, not of the number asked about. On a skewed stream the same sketch is 4% wrong about its heaviest key and 34,100% wrong about one of its rarest, and both figures satisfy the bound.

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–KhannaGuaranteeMerge treeMergeable summaryQuantile summaryRank errorRelative errorShardSpace overheadState bitsTailTrade off