Re: PoC/WIP: Extended statistics on expressions

Hi,

Here is an updated version of the patch series, addressing most of the 
issues raised so far. It also adapts the new version of the bootstrap 
patches shared by Justin on March 3.

I've merged the two patches reworking tracking of expressions, that I 
kept separate to make review easier. But as we agree it's a good 
approach, I've merged them into the main patch. FWIW I agree trying to 
undo the bitmapsets entirely would be a step too far - the patch is 
already quite large, so I'll leave it for the future.

As for the changes, I did a bunch of cleanup in the code supporting 
functional dependencies and mcv. Most of this was cosmetic in the "not 
changing" behavior - comments, undoing some unnecessary changes to make 
the code more like before, regression tests, etc.

There are a couple notable changes, worth mentioning explicitly.


1) functional dependencies

I looked at merging dependency_is_compatible_expression and 
dependency_is_compatible_clause, and I've made the code of those 
functions much more similar. I didn't go as far as actually merging 
those functions. Maybe we actually should do that to correctly handle 
"nested cases" with Vars in expressions, but I'm not sure about that.

I added support for the SAOP and OR clauses. Not sure about the OR case, 
but SAOP was missing mostly because that feature was added after this 
patch was created.

This also required rethinking the handling of RestrictInfo - it was 
required for expressions but not for Vars, for some reason. But that 
would not work for OR clauses. So now it's mostly what we do for Vars.

There's a couple minor FIXMEs remaining, I'll look into those next.


2) ndistinct

So far the code in selfuncs.c using ndistinct stats to estimate GROUP BY 
was quite WIP / experimental, and when I started looking at it, adding 
regression tests etc., I discovered a bunch of bugs. Some of that was 
due to the reworks in tracking expressions, but not all. I fixed all of 
that and cleaned the code quite a bit. I'm not going to claim it's bug 
free, but I think it's in a much better shape now.

There's one thing that's bugging me, in how we handle "partial" matches. 
For each expression we track both the original expression and the Vars 
we extract from it. If we can't find a statistics matching the whole 
expression, we try to match those individual Vars, and we remove the 
matching ones from the list. And in the end we multiply the estimates 
for the remaining Vars.

This works fine with one matching ndistinct statistics. Consider for example

     GROUP BY (a+b), (c+d)

with statistics on [(a+b),c] - that is, expression and one column. We 
parse the expressions into two GroupExprInfo

     {expr: (a+b), vars: [a, b]}
     {expr: (c+d), vars: [c, d]}

and the statistics matches the first item exactly (the expression). The 
second expression is not in the statistics, but we match "c". So we end 
up with an estimate for "(a+b), c" and have one remaining GroupExprInfo:

     {expr: (c+d), vars: [d]}

Without any other statistics we estimate that as ndistinct for "d", so 
we end up with

     ndistinct((a+b), c) * ndistinct(d)

which mostly makes sense. It assumes ndistinct(c+d) is product of the 
ndistinct estimates, but that's kinda what we've been always doing.

But now consider we have another statistics on just (c+d). In the second 
loop we end up matching this expression exactly, so we end up with

     ndistinct((a+b), c) * ndistinct((c+d))

i.e. we kinda use the "c" twice. Which is a bit unfortunate. I think 
what we should do after the first loop is just discarding the whole 
expression and "expand" into per-variable GroupExprInfo, so in the 
second step we would not match the (c+d) statistics.

Of course, maybe there's a better way to pick the statistics, but I 
think our conclusion so far was that people should just create 
statistics covering all the columns in the query, to not have to match 
multiple statistics like this.


3) regression tests

The patch adds a bunch of regression tests - I admit I've been adding 
the tests a bit arbitrarily, mostly copy-paste of existing tests and 
tweaking them to use expressions. This helped with identifying bugs, but 
the runtime of the stats_ext test suite grew quite a lot - maybe 2-3x, 
and it's not one of the slowest cases on my system (~3 seconds). I think 
we need to either reduce the number of new tests, or maybe move some of 
the tests into a separate parallel test suite.


regards

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