The skew a few counters cannot repair

The join order is a guess priced a three-way join in two orders and let a planner choose between them on the textbook estimate of the first intermediate result — the product of the two relations’ sizes divided by the number of distinct values in the join column. When that column followed a Zipf distribution the estimate fell behind the truth by a factor of 72 at an exponent of 1.2 and 399 at two, and the part of the plan the order decided cost 43.9 and then 243.9 times what the better order would have.

The same essay pointed at the repair. A join’s size is a sum, over the values of the join column, of the product of their counts in the two relations, and a sum of products is carried by the values frequent in both. An estimator that knew the counts of those few values exactly, and assumed uniformity only for everything else, should capture most of the sum. The items that survive k counters measured the summary that finds such values in one pass: Misra–Gries, which keeps $k$ counters, never reports a count above the truth, and reports every value whose count exceeds $N/(k+1)$.

That essay made a prediction specific enough to be wrong. A few dozen counters should remove nearly all of the damage at high skew. And somewhere at a moderate exponent the repair should fail, because the heavy values are not heavy enough to dominate and the summary’s error is comparable to their counts. This page measures both halves, and the second turns out to have a sharper location than the prediction gave it.

The estimate, with counters #

The instance is the one the join-order essay used. $R$ has 4,000 rows, $S$ 40,000 and $T$ 2,000; column $a$, joining $R$ to $S$, has 1,000 distinct values drawn from a Zipf distribution with exponent $s$; column $b$, joining $S$ to $T$, is uniform over 500 values. Every plan is priced in block transfers, with blocks of 64 records and 4,096 records of memory, and each plan’s cost is split into the output every order must write and the part the order decides.

The corrected estimate is built like this. Keep a Misra–Gries summary with $k$ counters for column $a$ in $R$, and another for column $a$ in $S$. For every value both summaries report, multiply the two reported counts. Take away the reported rows from each relation, spread what is left uniformly over the distinct values not reported, and add that product in. With $k = 0$ nothing is reported and the result is the textbook estimate; if the summaries could hold every value the result would be exact. The number of counters is a dial between the two.

The first half of the prediction holds, and more strongly than predicted. At an exponent of two the uniform estimate chooses an order whose decided part costs 243.9 times the better one; four counters a side choose correctly. At 1.25, where the uniform estimate’s choice costs 52.9 times the better, four counters are again enough. The counters do not need to be “a few dozen”. They need to be a few.

The second half holds too, and it holds at a single point with unusual stubbornness. At an exponent of one half the uniform estimate’s choice costs 1.37 times the better order, and so does the choice made with 4, 16, 64 and 256 counters. Every line on the plate passes through the same point.

What a repaired plan looks like #

The repaired estimate is not accurate. At an exponent of 1.2 it is out by a factor of 1.9, which in most settings would be called a poor estimate. It is accurate enough, which is a different property, and the difference is the whole of what an estimate is for in a planner. The planner compares two costs; the estimate has to put the right one lower. The estimate a plan rests on found the same asymmetry for a single access path, where a bounded error in one direction could be named in advance and an error in the other could not.

How far each estimate is from the truth #

Read beside the first plate, this one makes a point about the relation between an estimate’s error and a plan’s regret that neither plate makes alone.

At an exponent of two, four counters leave the estimate out by 1.41 and the order right. At an exponent of one, sixteen counters leave it out by 3.94 and the order right. At an exponent of one half, the uniform estimate is out by 1.98 — the smallest error at which any order on these plates goes wrong — and the order is wrong. And 256 counters, which bring that error down to 1.55, leave the order wrong.

So a smaller error is not a better choice. What decides the choice is the error measured against the margin between the two orders, and at this instance the margin is small: the join order is a guess found the planner’s two estimated costs within about eleven per cent of each other. At high skew the true costs are far apart, so a large error can still leave them in the right order; at low skew they are close, so a small error can swap them. The skew at which an estimate is nearly right is the skew at which being nearly right is not enough.

Which way the corrected estimate errs #

The error plate draws each estimate’s distance from the truth as a factor either way, which hides a direction worth knowing. At every skew from a quarter upwards, with every number of counters, the corrected estimate is below the true size — by a factor of 1.55 at an exponent of one half with 256 counters, 1.07 at one, 1.00 only once the reported values carry the whole sum. It is above the truth in exactly one place: on a column with no skew at all, where hundreds of counters report values that happen to be slightly commoner than average and the uniform remainder is spread over too few values.

The direction is built into the summary. Misra–Gries never reports a count higher than the true one; every decrement it applies to make room for a new value is charged against the values it keeps. So each exact product in the corrected estimate is a product of two undercounts, and is low. The reported rows subtracted from each relation are too few, which pushes the uniform remainder up — but a uniform remainder is an average of the very products the skew makes large, so it cannot make up the difference. The corrected estimate therefore inherits the uniform estimate’s direction of error and shrinks its size, and on these columns it approaches the truth from below as the counters grow.

That matters for the order the planner picks, because an estimate that is always low always leans the same way. In this query a low estimate of the first join favours joining $R$ with $S$ first. Every wrong choice on the plates is that choice, and the step in the counters plate below is the point at which the estimate rises far enough towards the truth to stop favouring it: between 256 counters, where the estimate is out by 1.55, and 512, where it is out by 1.29.

What the reported values carry #

The explanation of why counters work at high skew and not at low is in how much of the join the reported values account for.

At high skew a handful of values carry nearly the whole join. At an exponent of two, the values two four-counter summaries share account for 99.3% of the true size, so the uniform part of the corrected estimate is pricing a sliver and cannot be far wrong. At an exponent of one half, the values 256-counter summaries share account for 51.9%, and the other half is priced by the uniform assumption that was the problem to begin with.

There are two limits in this, and they compound. The first is the summary’s: Misra–Gries only guarantees to report a value whose count exceeds $N/(k+1)$, which with $N = 4{,}000$ rows in $R$ and 256 counters is about sixteen rows. At an exponent of one half the value of rank $i$ has about $4{,}000 \cdot i^{-1/2}/\sum_{j \le 1000} j^{-1/2} \approx 65\, i^{-1/2}$ rows, which is above sixteen only for the first sixteen or so values. The second limit is the distribution’s, and it is the one that makes one half special.

Why one half #

When both sides of a join follow the same Zipf distribution with exponent $s$, the expected size of the join is proportional to $\sum_i i^{-2s}$ — the value of rank $i$ contributes the product of two counts each proportional to $i^{-s}$. The share of that sum carried by the top $m$ values is

$$\frac{\sum_{i \le m} i^{-2s}}{\sum_{i \le d} i^{-2s}}.$$

If $2s > 1$ the series in the denominator converges as $d$ grows, so a fixed number of top values carries a fixed share of it however many distinct values there are. At $s = 1$ the top four carry $\bigl(1 + \tfrac14 + \tfrac19 + \tfrac1{16}\bigr) / \sum_{i \le 1000} i^{-2} \approx 1.42/1.64$, about 87%. At $2s = 1$ the series is the harmonic series, which diverges: the share carried by the top $m$ of 1,000 values is $H_m/H_{1000}$, the ratio of two harmonic numbers, which grows only like $\log m / \log 1000$. The top sixteen carry about 45%, and the top 256 about 82% — and no summary with far fewer counters than there are distinct values can report 256 values from 4,000 rows at that skew.

So $s = 1/2$ is not a moderate exponent that happens to be awkward. It is the boundary at which the quantity a join estimate needs stops being concentrated in any small set of values. Below it the join’s size is spread across the whole column, and a summary of heavy values has nothing heavy to summarise; above it, a fixed handful of values carries most of the sum and a fixed handful of counters finds them.

The estimate that squares the stream measured a different summary — the tug-of-war sketch, which estimates $\sum_v f(v)^2$ with a relative error that does not depend on how the frequencies are spread. That is the complementary tool. A heavy-value summary is exact where the sum is concentrated and helpless where it is spread; a second-moment sketch is equally good at both and exact at neither. A planner wanting to be safe at every skew needs either the second kind or a very large amount of the first.

The counters each skew needs #

Each line is a step: nothing, and then a complete repair. At an exponent of 1.5 the step is at two counters; at 1 it is at eight; at one half it is at 512.

A step is what the argument above predicts. An order is either right or wrong, and the estimate either crosses the point where the two orders’ costs are equal or it does not. Counters move the estimate towards the truth continuously, as the error plate shows, and the regret waits until the movement is enough and then drops all at once.

The position of the steps is the practical result, and it can be priced in memory. A counter holds a value and a count, which at 32 bits each is 64 bits. Eight counters a side for a join column is 512 bits, 64 bytes per relation; two is sixteen bytes. Numbers that small can be kept for every join column of every table without anyone noticing, and they repair the order at every exponent from one upwards on these plates.

Five hundred and twelve counters a side is 32,768 bits — four kilobytes per relation — and over a column with a thousand distinct values it is not a summary of the column. It is half of the column’s frequency table, and a system that kept it would be better off keeping all of it, since an exact table of a thousand counts costs twice as much and is never wrong.

The plan that stays wrong #

The corrected estimate did move. It went from 160,000 to 203,662 against a truth of 316,373, closing about a quarter of the gap, and that quarter was not enough to cross the point where the orders swap. A regret of 1.37 on the decided part — 1.11 on the whole plan — is not a disaster. It is a steady, invisible tax on every query over a moderately skewed column, and it is exactly the regime a planner with a heavy-value summary would believe it had handled.

A sixth of what, exactly is the site’s warning about reporting a ratio without its denominator, and the pair of numbers above repeats it: the whole-plan regret of 1.11 sounds like noise, and the decided regret of 1.37 is the planner’s actual error rate at choosing orders on this query.

What a planner can take from the measurement #

Heavy-value summaries are worth keeping and nearly free where they work. At exponents above one, a few counters per join column turn a planner that is wrong by two orders of magnitude into one that is right. An error measured against the answer explains why the additive error Misra–Gries promises is the right kind for this use: it is small relative to the heavy values, which are the ones the sum of products depends on.

They cannot be trusted near an exponent of one half, and more counters are the wrong remedy. The share of the join carried by any small set of values is logarithmic there, so the counters needed grow with the number of distinct values rather than with the accuracy wanted. The honest alternatives are a sketch of the second moment, which does not care how the frequencies are spread, or a planner that treats a small estimated margin between orders as no information at all.

And a planner should report the margin as well as the choice. The uniform estimate put the two orders within about eleven per cent of each other at every skew, because nothing it reads changes as the skew does. A choice made on a ten per cent margin with an estimate whose error is a factor of 1.5 is a coin flip, and a planner that knew that could run the cheaper safeguard — observing the first intermediate result and re-planning — exactly where it is needed. Two ways to join, and the ratio that decides is the two-table version of the same decision, where every quantity is known exactly and no margin needs reporting.

Still open: a join whose heavy values differ between its sides #

Every column on this page was skewed the same way on both sides of the join: the popular values of $a$ were 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. A column can be skewed in both relations towards different values — the most-ordered products are not the most-reviewed ones — 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.

The corrected estimate on this page would then report almost nothing in common and fall back on the uniform part, which is now the wrong direction. The measurement that follows sweeps the correlation between the two sides’ rankings, from the same heavy values to disjoint ones, and asks how the error and the regret behave as the heavy values stop coinciding — and whether a summary of each side’s heavy values, which knows those values are absent from the other side, can correct an overestimate as well as it corrects an underestimate.