A summary's silence is a bound, not a count

The skew a few counters cannot repair measured a planner choosing the order of a three-way join from the textbook estimate, which assumes the join column is uniform. At a Zipf exponent of two the estimate is far too low, the order it picks costs 243.9 times the better one, and two heavy-hitter counters a side repair it completely. At an exponent of a half the estimate is out by less than a factor of two and no number of counters up to 256 changes the plan.

Every column on that page is skewed the same way on both sides: the popular values of the join column are popular in $R$ and in $S$ alike, which is what makes the sum of products large and the uniform estimate too low. Real joins are not always like that. The most-ordered products are not the most-reviewed ones, and a column can be skewed in both relations towards different values — and then the sum of products is small, the uniform estimate is too high, and the heavy values each summary reports are values the other summary does not hold.

This page rotates one side’s ranking away from the other’s and measures what happens to the estimate, to the plan, and to the repair.

One dial, both marginals fixed #

The sweep changes which value sits at each rank of $S$’s distribution and nothing else. At a rotation of zero, $S$’s most popular value is $R$’s most popular; at a rotation of five it is $R$’s fifth; at 500 it is a value $R$ barely holds. Both columns keep the same shape — the same Zipf exponent, the same number of distinct values, the same row counts — so the uniform estimate, which reads only those, does not move at all.

The first line spans five orders of magnitude and the estimate behind it never changes: 160,000 rows, at every rotation. The join truly holds 63,871,022 rows at a rotation of zero and 629 at 500.

So the estimator’s error swings by a factor of 100,000 across the sweep and the estimator cannot see any of it, because it has no term the sweep touches. That is worth separating from the usual complaint about uniformity assumptions. The textbook estimate is not merely approximate here; it is measuring a quantity — row counts over distinct values — that is invariant under the thing that decides the answer.

What the plan does about it #

The planner’s decision is identical at every rotation — the same estimate produces the same comparison and the same order — so the regret line is entirely a statement about when that one fixed decision happens to be right.

It is wrong, expensively, on the left. It is right, for free, on the right: from a rotation of twenty-five onwards the order the uniform estimate picks is the better order, and the regret is one even though the estimate is between 1.1 and 254 times too high.

The join order is a guess is where that gap was first measured between an estimate’s error and a plan’s cost — an estimate out by seventy-two times producing a plan 1.49 times worse on the whole query and 43.9 times worse on the part the order actually decided. The same two numbers are reported here, and it is the second one the plates draw.

The overestimate costs nothing here and the underestimate costs 244×, and that asymmetry is not about estimation at all. An intermediate result that is truly enormous and is estimated as small makes the planner choose an order that materialises it; an intermediate result that is truly tiny and is estimated as large makes the planner avoid materialising something that would have been cheap. The first is a mistake that is paid in full; the second is a mistake that costs whatever the alternative order costs, which here is nothing. The estimate a plan rests on measured the same asymmetry for a single predicate and named its ceiling: guessing too few rows on a wide query costs at most a bounded factor, and guessing too many on a narrow one does not.

That plate and the one above it are the same experiment at two different points of the same two-dimensional space, and it is worth naming the space because neither page draws it whole. A join’s estimate is decided by how skewed each side is and by how much the two skews agree. The earlier page swept the first with the second held at perfect agreement; this page sweeps the second with the first held at an exponent of two. The corner they share — exponent two, rotation zero — is the 243.9 that appears on both.

Why the counters stop #

The repair that worked on the left is a Misra–Gries summary of each side. Values that both summaries report contribute the product of their reported counts exactly, and the rows left over are spread uniformly over the distinct values left over. At a rotation of zero both summaries hold the same eight values and the correction is nearly exact — 1.13 times the truth against the uniform estimate’s 399.

At a rotation of ten the two summaries hold eight values each and share none. The exact term is zero, every row is left over, and the corrected estimate is the uniform one to the last digit: 160,000, error 4.96, regret 3.19 — the same three numbers as with no summary at all.

That is the mechanism the earlier page’s question was about, and it is worth stating plainly. The summaries have not failed to find the heavy values; they have found them, and the estimator has no use for a heavy value the other side does not share. Eight counters a side on this data hold the eight values that matter on each side, and the estimator throws both sets away.

The rotation of five is the interesting failure, because there the summaries share some values by accident and the correction is worse than none: it estimates 20.4 times too high where the uniform estimate was 14.5 times too low, and the order it picks is the same wrong one, so the regret stays at 9.04. A summary that shares two of its eight values takes those two products as exact and spreads the rest uniformly, which double-counts the mass those two values carry on both sides.

That failure is a shortage of counters and it does go away. Sixty-four counters a side hold enough of each ranking that the two overlap again at a rotation of ten, and the corrected estimate reads 1.05 times the truth with a regret of one; at 256 counters it is exact to two decimals from a rotation of zero to twenty-five. So the middle of the sweep is a case where more summary buys the answer, exactly as the earlier page’s skew sweep was.

The far right is a different thing entirely, and it is worth taking apart because the number is surprising.

Where the overestimate actually lives #

At a rotation of 100 the join truly holds 2,066 rows and the uniform estimate says 160,000. With 256 counters a side, the corrected estimate reads 155,201, and it decomposes:

• the shared heavy values contribute 2,050, against a true total of 2,066;
• the rows left over contribute 153,151.

The summary has the answer. Eleven values are in both summaries, their products sum to within one per cent of the whole join, and the estimator then adds seventy-four times that much for the rows neither summary holds.

So the overestimate is not a failure of the heavy-value correction; it is the uniform assumption applied to the tail. The two rankings are unrelated, so a value that is moderately common in $R$ is, on average, unremarkable in $S$ — but the products of the two tails are far below the product of their averages, because the averages are pulled up by mass that sits at different values on the two sides. The uniform term is computing $\left(\sum_R \text{tail}\right)\left(\sum_S \text{tail}\right) / d$, which is an average of products replaced by a product of averages, and the two differ by exactly the correlation the sweep is about.

A summary of heavy values cannot repair that, at any size, because the mass causing it is by construction not heavy. That is the honest reading of the far right, and it is a different failure from the one at a rotation of five.

Using what a summary does not say #

A Misra–Gries summary of $k$ counters holds every value occurring more than $n/(k+1)$ times. So a value one summary reports and the other does not is not merely uncovered: the second summary’s silence is an upper bound on how often that value occurs there.

Using the bound gives a third estimator. A value held by one side and not the other contributes its reported count times $n/(k+1)$ rather than its reported count times the average, and the remainder is spread as before.

It works where the plain counters failed. At a rotation of five it takes the error from 20.4 times too high to 7 times too high and the regret from 9.04 to 1.00; at ten, from 4.96 times too low to 1.00 regret. Across rotations from zero to ten it produces the right order every time.

And it breaks the far end. At a rotation of 100 it estimates about a hundred times too high and its order costs 5.8 times the better one; at 500, 6.0. The uniform estimate, which knows nothing, costs 1.00 at both.

The reason is in the word “bound”. $n/(k+1)$ is 4,444 rows when the summary holds eight counters over 40,000 rows, and the true frequency of a value the summary does not hold is anything from 4,444 down to zero. On the left of the sweep, where the heavy values nearly coincide, the values the summaries miss really do occur thousands of times and the bound is close. On the right, where the rankings are unrelated, a value heavy in $R$ occurs in $S$ a handful of times, and the bound overstates it by three orders of magnitude.

So the answer to whether a summary can correct an overestimate as well as it corrects an underestimate is no — and the reason is not the one the question implied. A summary’s positive statements are counts and its negative ones are bounds. Counts can be multiplied together to correct in either direction, which is why more counters repair the middle of this sweep; a bound multiplied by a count gives a bound, and a bound used where an estimate is wanted errs in one direction only, which is exactly the direction that was already wrong on the right.

And underneath both is the decomposition above: the overestimate on the right is in the uniform tail, which is the one part of the estimate that no summary of heavy values addresses, by definition.

What a planner should take from this #

Ask which direction the error runs before choosing a repair. The two halves of this sweep need different things: the left needs the shared heavy values, which counters supply once there are enough of them; the right needs the tail’s correlation, which no summary of the heaviest few values holds. A planner that applies the heavy-value correction everywhere is right on the left, harmless on the right, and wrong in a narrow band in between if its summaries are too small.

And count the counters against the ranking, not against the skew. Eight counters a side repair a rotation of zero and fail at five; sixty-four repair both. The number needed is set by how far the two rankings have to overlap before a shared value appears, which is a property of the pair of columns and not of either one. A planner sizing its summaries from a single column’s skew — which is what a histogram on one table gives it — is sizing them for the wrong quantity.

And a correction that helps in the middle is not therefore safe. The silence-using estimator is the best of the three over rotations from zero to ten and the worst of the three from twenty-five on. Measuring it only where the problem was first noticed would have shipped it.

That is the same shape the skew a few counters cannot repair found in the other parameter: the easy case was the extreme one, and the moderate case was hard for a reason with a name. Here the extreme cases are easy in both directions — a rotation of zero is repaired by counters and a rotation of 500 needs no repair at all — and the middle is where every estimator on the page is at its worst.

The exponent decides how much is at stake and the rotation decides who can see it, and the two are not interchangeable. At an exponent of one the whole sweep spans a factor of sixty and the worst order costs 17.7; at two it spans 100,000 and the worst order costs 244. A planner that has measured its column’s skew knows the first number and knows nothing about the second.

What is not measured here #

Rotation, not a correlation coefficient. The sweep rotates one side’s ranking, which takes the two heavy sets from identical to disjoint through a sequence in which they partially overlap. It is one path through the space of rankings; a random permutation of $S$’s ranking would be a different one and would have no monotone parameter.

One distribution shape on both sides. Both columns are Zipf with the same exponent. A join between a heavily skewed column and a nearly uniform one is a different case and is not swept.

One summary, not a histogram. A Misra–Gries summary is the structure the items that survive k counters measured, and it is built to find heavy hitters rather than to describe a distribution. A histogram over equal-width buckets describes the tail, which is where the far right’s error lives — and the histogram that cannot see the order is the standing warning about what a histogram loses instead.

The bound is the textbook one. A Misra–Gries summary’s guarantee is that it holds every value above $n/(k+1)$; a real implementation also knows each counter’s residual error and could bound an absent value more tightly. That would move the silence-using estimator’s break-even and would not change its direction.

The rows a join produces, not the rows it reads. The estimate under test is of the intermediate result’s size, which the occurrences a join invents is about in a different setting: a join over skewed values produces far more rows than either side holds, and an estimate that cannot see the skew cannot see that either.

Three relations, one shape. The join is $R \bowtie S \bowtie T$ with $S$ in the middle, and only the $R$–$S$ column is skewed. A plan over six relations has more orders and more estimates, and the regret compounds across them rather than resting on one.

Transfers, not time, as throughout these join measurements, and the regret reported is the decided part — the whole plan’s cost with the final result’s own write removed from both orders, since both orders pay it and it swamps the part the estimate actually decided.

Still open: a summary that measures rather than bounds #

Everything that went wrong on the right of this sweep went wrong because a summary answers “how often does this value occur” with either a count or a bound, and the bound is loose when the answer is small. A structure that answers with an estimate in both cases exists and has been measured here: a Count-Min sketch returns a count for every value, never below the truth and wrong by an amount proportional to the whole stream rather than to the value.

A count that is never under is the structure to reach for, and its one-sided error is the thing to watch when two of its answers are multiplied together: two estimates that are each never below the truth give a product that is never below the truth either, and the errors compound rather than cancel.

The measurement that follows replaces the two Misra–Gries summaries with two Count-Min sketches of the same total width, estimates the join size as the sum over the heavy values of each side of the product of the two sketches’ answers, and asks three things: whether the right of the sweep is repaired, what the sketches’ one-sided error does to the estimate when both factors are overestimates, and how the accuracy at a fixed number of bits compares with the counters’ — since a sketch spends its space on every value and a summary spends it on the few that matter, and the sweep on this page is precisely about whether the few that matter on one side matter on the other.