PoC: Using Count-Min Sketch for join cardinality estimation

Hi,

During the recent "CMU vaccination" talk given by Robert [1], a couple 
of the attendees (some of which were engineers working on various other 
database systems) asked whether PostgreSQL optimizer uses sketches. 
Which it does not, as far as I'm aware. Perhaps some of our statistics 
could be considered sketches, but we've not using data structures like 
hyperloglog, count-min sketch, etc.

But it reminded me that I thought about using one of the common sketches 
in the past, namely the Count-Min sketch [2], which is often mentioned 
as useful to estimating join cardinalities. There's a couple papers 
explaining how it works [3], [4], [5], but the general idea is that it 
approximates frequency table, i.e. a table tracking frequencies for all 
values. Our MCV list is one way to do that, but that only keeps a 
limited number of common values - for the rest we approximate the 
frequencies as uniform distribution. When the MCV covers only a tiny 
fraction of the data, or missing entirely, this may be an issue.

We can't possibly store exact frequencies all values for tables with 
many distinct values. The Count-Min sketch works around this by tracking 
frequencies in a limited number of counters - imagine you have 128 
counters. To add a value to the sketch, we hash it and the hash says 
which counter to increment.

To estimate a join size, we simply calculate "dot product" of the two 
sketches (which need to use the same number of counters):

   S = sum(s1(i) * s2(i) for i in 1 .. 128)

The actual sketches have multiple of those arrays (e.g. 8) using 
different hash functions, and we use the minimum of the sums. That 
limits the error, but I'll ignore it here for simplicity.

The attached patch is a very simple (and perhaps naive) implementation 
adding count-min sketch to pg_statistic for all attributes with a hash 
function (as a new statistics slot kind), and considering it in 
equijoinsel_inner. There's a GUC use_count_min_sketch to make it easier 
to see how it works.

A simple example

   create table t1 (a int, b int);
   create table t2 (a int, b int);

   insert into t1 select pow(random(), 2) * 1000, i
     from generate_series(1,30000) s(i);
   insert into t2 select pow(random(), 2) * 1000, i
     from generate_series(1,30000) s(i);

   analyze t1, t2;

   explain analyze select * from t1 join t2 using (a);

                              QUERY PLAN
   ------------------------------------------------------------------
    Hash Join  (cost=808.00..115470.35 rows=8936685 width=12)
               (actual time=31.231..1083.330 rows=2177649 loops=1)


So it's about 4x over-estimated, while without the count-min sketch it's 
about 2x under-estimated:

   set use_count_min_sketch = false;

                              QUERY PLAN
   ------------------------------------------------------------------
    Merge Join  (cost=5327.96..18964.16 rows=899101 width=12)
                (actual time=60.780..2896.829 rows=2177649 loops=1)

More about this a bit later.


The nice thing on count-min sketch is that there are pretty clear 
boundaries for error:

   size(t1,t2) <= dot_product(s1,2) <= epsilon * size(t1) * size(t2)

where s1/s2 are sketches on t1/t2, and epsilon is relative error. User 
may pick epsilon, and that determines size of the necessary sketch as 
2/epsilon. So with 128 buckets, the relative error is ~1.6%.

The trouble here is that this is relative to cartesian product of the 
two relations. So with two relations, each 30k rows, the error is up to 
~14.5M. Which is not great. We can pick lower epsilon value, but that 
increases the sketch size.

Where does the error come from? Each counter combines frequencies for 
multiple distinct values. So for example with 128 counters and 1024 
distinct values, each counter is representing ~4 values on average. But 
the dot product ignores this - it treats as if all the frequency was for 
a single value. It calculates the worst case for the bucket, because if 
you split the frequency e.g. in half, the estimate is always lower

    (f/2)^2 + (f/2)^2 < f^2

So maybe this could calculate the average number of items per counter 
and correct for this, somehow. We'd lose some of the sketch guarantees, 
but maybe it's the right thing to do.

There's a bunch of commented-out code doing this in different ways, and 
with the geometric mean variant the result looks like this:

                              QUERY PLAN
   ------------------------------------------------------------------
    Merge Join  (cost=5328.34..53412.58 rows=3195688 width=12)
                (actual time=64.037..2937.818 rows=2177649 loops=1)

which is much closer, but of course that depends on how exactly is the 
data set skewed.


There's a bunch of other open questions:

1) The papers about count-min sketch seem to be written for streaming 
use cases, which implies all the inserted data pass through the sketch. 
This patch only builds the sketch on analyze sample, which makes it less 
reliable. I doubt we want to do something different (e.g. because it'd 
require handling deletes, etc.).


2) The patch considers the sketch before MCVs, simply because it makes 
it much simpler to enable/disable the sketch, and compare it to MCVs. 
That's probably not what should be done - if we have MCVs, we should 
prefer using that, simply because it determines the frequencies more 
accurately than the sketch. And only use the sketch as a fallback, when 
we don't have MCVs on both sides of the join, instead of just assuming 
uniform distribution and relying on ndistinct.

We may have histograms, but AFAIK we don't use those when estimating 
joins (at least not equijoins). That's another thing we might maybe look 
into, comparing the histograms to verify how much they overlap. But 
that's irrelevant here.

Anyway, count-min sketches would be a better way to estimate the part 
not covered by MCVs - we might even assume the uniform distribution for 
individual counters, because that's what we do without MCVs anyway.


3) It's not clear to me how to extend this for multiple columns, so that 
it can be used to estimate joins on multiple correlated columns. For 
MCVs it was pretty simple, but let's say we add this as a new extended 
statistics kind, and user does

     CREATE STATISTICS s (cmsketch) ON a, b, c FROM t;

Should that build sketch on (a,b,c) or something else? The trouble is a 
sketch on (a,b,c) is useless for joins on (a,b).

We might do something like for ndistinct coefficients, and build a 
sketch for each combination of the columns. The sketches are much larger 
than ndistinct coefficients, though. But maybe that's fine - with 8 
columns we'd need ~56 sketches, each ~8kB. So that's not extreme.


regards


[1] 
https://db.cs.cmu.edu/events/vaccination-2021-postgresql-optimizer-methodology-robert-haas/

[2] https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch

[3] https://dsf.berkeley.edu/cs286/papers/countmin-latin2004.pdf

[4] http://dimacs.rutgers.edu/~graham/pubs/papers/cmsoft.pdf

[5] http://dimacs.rutgers.edu/~graham/pubs/papers/cmz-sdm.pdf

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company