Re: [HACKERS] PATCH: multivariate histograms and MCV lists

On Sun, 10 Mar 2019 at 13:09, Dean Rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com> wrote:
> Here are some more comments:
>

One more thing --- the comment for statext_clauselist_selectivity() says:

* So (simple_selectivity - base_selectivity) may be seen as a correction for
* the part not covered by the MCV list.

That's not quite right. It should really say that (simple_selectivity
- base_selectivity) is an estimate for the part not covered by the MCV
list, or that (mcv_selectivity - base_selectivity) is a correction for
the part covered by the MCV list. Those 2 statements are actually
equivalent, and different from what you wrote.

Perhaps the easiest way to see it is to work through a simple example:

Suppose you had the following clauses:

a = 1 AND b >= 0 AND b <= 10

The per-column stats might be expected to give reasonable independent
estimates for the following 2 things:

P(a = 1)

P(b >= 0 AND b <= 10) -- in general, greater than P(b >= 0) * P(b <= 10)

but the overall estimate produced by clauselist_selectivity_simple()
would then just be the product of those 2 things:

simple_sel = P(a = 1) * P(b >= 0 AND b <= 10)

which might not be so good if the columns were correlated.

Now suppose you had MCV stats, which included MCV items for the
following specific values:

(a=1,b=1), (a=1,b=2), (a=1,b=3)

but no other relevant MCV entries. (There might be lots of other MCV
items that don't match the original clauses, but they're irrelavent
for this discssion.) That would mean that we could get reasonable
estimates for the following 2 quantities:

mcv_sel = P(a = 1 AND b IN (1,2,3))
= P(a = 1 AND b = 1) + P(a = 1 AND b = 2) + P(a = 1 AND b = 3)

mcv_basesel = base_freq(a = 1 AND b IN (1,2,3))
= P(a = 1) * (P(b = 1) + P(b = 2) + P(b = 3))

So how is that useful? Well, returning to the quantity that we're
actually trying to compute, it can be split into MCV and non-MCV
parts, and since they're mutually exclusive possibilities, their
probabilities just add up. Thus we can write:

P(a = 1 AND b >= 0 AND b <= 10)

= P(a = 1 AND b IN (1,2,3)) -- MCV part
+ P(a = 1 AND b >= 0 AND b <= 10 AND b NOT IN (1,2,3)) -- non-MCV part

= mcv_sel + other_sel

So the first term is easy -- it's just mcv_sel, from above. The second
term is trickier though, since we have no information about the
correlation between a and b in the non-MCV region. Just about the best
we can do is assume that they're independent, which gives:

other_sel = P(a = 1 AND b >= 0 AND b <= 10 AND b NOT IN (1,2,3))
~= P(a = 1) * P(b >= 0 AND b <= 10 AND b NOT IN (1,2,3))

and that can now be written in terms of things that we know

other_sel ~= P(a = 1) * P(b >= 0 AND b <= 10 AND b NOT IN (1,2,3))

= P(a = 1) * P(b >= 0 AND b <= 10)
- P(a = 1) * P(b IN (1,2,3)) -- mutually exclusive possibilities

= simple_sel - mcv_basesel

So, as I said above, (simple_selectivity - base_selectivity) is an
estimate for the part not covered by the MCV list.

Another way to look at it is to split the original per-column estimate
up into MCV and non-MCV parts, and correct the MCV part using the MCV
stats:

simple_sel = P(a = 1) * P(b >= 0 AND b <= 10)

= P(a = 1) * P(b IN (1,2,3))
+ P(a = 1) * P(b >= 0 AND b <= 10 AND b NOT IN (1,2,3))

The first term is just mcv_basesel, so we can define other_sel to be
the other term, giving

simple_sel = mcv_basesel -- MCV part
+ other_sel -- non-MCV part

Clearly mcv_basesel isn't the best estimate for the MCV part, and it
should really be mcv_sel, so we can improve upon simple_sel by
applying a correction of (mcv_sel - basesel) to it:

better estimate = simple_sel + (mcv_sel - mcv_basesel)
= mcv_sel + other_sel

(where other_sel = simple_sel - mcv_basesel)

Of course, that's totally equivalent, but looking at it this way
(mcv_selectivity - base_selectivity) can be seen as a correction for
the part covered by the MCV list.

All of that generalises to arbitrary clauses, because the matching
items in the MCV list are independent possibilities that sum up, and
the MCV and non-MCV parts are mutually exclusive. That's also why the
basesel calculation in mcv_clauselist_selectivity() must only include
matching MCV items, and the following XXX comment is wrong:

+ for (i = 0; i < mcv->nitems; i++)
+ {
+ *totalsel += mcv->items[i]->frequency;
+
+ if (matches[i] != STATS_MATCH_NONE)
+ {
+ /* XXX Shouldn't the basesel be outside the if condition? */
+ *basesel += mcv->items[i]->base_frequency;
+ s += mcv->items[i]->frequency;
+ }
+ }

So I believe that that code is correct, as written.

Regards,
Dean