Re: multivariate statistics / patch v7

Hi,

On 07/13/2015 10:51 AM, Kyotaro HORIGUCHI wrote:
>
> Ok, I understood the diferrence between what I thought and what you
> say. The code is actually concious of OR clause but is looks somewhat
> confused.

I'm not sure which part is confused by the OR clauses, but it's
certainly possible. Initially it only handled AND clauses, and the
support for OR clauses was added later, so it's possible some parts are
not behaving correctly.

>
> Currently choosing mv stats in clauselist_selectivity can be
> outlined as following,
>
> 1. find_stats finds candidate mv stats containing *all*
> attributes appeared in the whole clauses regardless of and/or
> exprs by walking whole the clause tree.
>
> Perhaps this is the measure to early bailout.

Not entirely. The goal of find_stats() is to lookup all stats on the
'current' relation - it's coded the way it is because I had to deal with
varRelid=0 cases, in which case I have to inspect the Var nodes. But
maybe I got this wrong and there's much simpler way to do that?

It is an early bailout in the sense that if there are no multivariate
stats defined on the table, there's no point in doing any of the
following steps. So that we don't increase planning times for users not
using multivariate stats.

> 2.1. Within every disjunction elements, collect mv-related
> attributes while checking whether the all leaf nodes (binop or
> ifnull) are compatible by (eventually) walking whole the
> clause tree.

Generally, yes. The idea is to check whether there are clauses that
might be estimated using multivariate statistics, and whether the
clauses reference at least two different attributes. Imagine a query
like this:

SELECT * FROM t WHERE (a=1) AND (a>0) AND (a<100)

It makes no sense to process this using multivariate statistics, because
all the Var nodes reference a single attribute.

Similarly, the check is not just about the leaf nodes - to be able to
estimate a clause at this point, we have to be able to process the whole
tree, starting from the top-level clause. Although maybe that's no
longer true, now that support for OR clauses was added ... I wonder
whether there are other BoolExpr-like nodes, that might make the tree
incompatible with multivariate statistics (in the sense that the current
implementation does not know how to handle them).

Also note that even though the clause may be "incompatible" at this
level, it may get partially processed by multivariate statistics later.
For example with a query:

SELECT * FROM t WHERE (a=1 OR b=2 OR c ~* 'xyz') AND (q=1 OR r=4)

the first query is "incompatible" because it contains unsupported
operator '~*', but it will eventually be processed as BoolExpr node, and
should be split into two parts - (a=1 OR b=2) which is compatible, and
(c ~* 'xyz') which is incompatible.

This split should happen in clauselist_selectivity_or(), and the other
thing that may be interesting is that it uses (q=1 OR r=4) as a
condition. So if there's a statistics built on (a,b,q,r) we'll compute
conditional probability

P(a=1,b=2 | q=1,r=4)

>
> 2.2. Check if all the collected attribute are contained in
> mv-stats columns.

No, I think you got this wrong. We do not check that *all* the
attributes are contained in mvstats columns - we only need two such
columns (then there's a chance that the multivariate statistics will get
applied).

Anyway, both 2.1 and 2.2 are meant as a quick bailout, before doing the
most expensive part, which is choose_mv_statistics(). Which is however
missing in this list.

> 3. Finally, clauseset_mv_selectivity_histogram() (and others).
>
> This funciton applies every ExprOp onto every attribute in
> every histogram backes and (tries to) make the boolean
> operation of the result bitmaps.

Yes, but this only happens after choose_mv_statistics(), because that's
the code that decides which statistics will be used and in what order.

The list is also missing handling of the 'functional dependencies', so a
complete list of steps would look like this:

1) find_stats - lookup stats on the current relation (from RelOptInfo)

2) apply functional dependencies

a) check if there are equality clauses that may be reduced using
functional dependencies, referencing at least two columns

b) if yes, perform the clause reduction

3) apply MCV lists and histograms

a) check if there are clauses 'compatible' with those types of
statistics, again containing at least two columns

b) if yes, use choose_mv_statistics() to decide which statistics to
apply and in which order

c) apply the selected histograms and MCV lists

4) estimate the remaining clauses using the regular statistics

a) this is where the clauselist_mv_selectivity_histogram and other
are called

I tried to explain this in the comment before clauselist_selectivity(),
but maybe it's not detailed enough / missing some important details.

>
> I have some comments on the implement and I also try to find the
> solution for them.
>
>
> 1. The flow above looks doing very similiar thins repeatedly.

I worked hard to remove such code duplicities, and believe all the
current steps are necessary - for example 2(a) and 3(a) may seems
similar, but it's really necessary to do that twice.

>
> 2. I believe what the current code does can be simplified.

Possibly.

>
> 3. As you mentioned in comments, some additional infrastructure
> needed.
>
> After all, I think what we should do after this are as follows,
> as the first step.

OK.

>
> - Add the means to judge the selectivity operator(?) by other
> than oprrest of the op of ExprOp. (You missed neqsel already)

Yes, the way we use 'oprno' to determine how to estimate the selectivity
is a bit awkward. It's inspired by handling of range queries, and having
something better would be nice.

But I don't think this is the reason why I missed neqsel, and I don't
see this as a significant design issue at this point. But if we can come
up with a better solution, why not ...

> I suppose one solution for this is adding oprmvstats taking
> 'm', 'h' and 'f' and their combinations. Or for the
> convenience, it would be a fixed-length string like this.
>
> oprname | oprmvstats
> = | 'mhf'
> <> | 'mhf'
> < | 'mh-'
> > | 'mh-'
> >= | 'mh-'
> <= | 'mh-'
>
> This would make the code in clause_is_mv_compatible like this.
>
> > oprmvstats = get_mvstatsset(expr->opno); /* bitwise representation */
> > if (oprmvstats & types)
> > {
> > *attnums = bms_add_member(*attnums, var->varattno);
> > return true;
> > }
> > return false;

So this only determines the compatibility of operators with respect to
different types of statistics? How does that solve the neqsel case? It
will probably decide the clause is compatible, but it will later fail at
the actual estimation, no?

>
> - Current design just manage to work but it is too complicated
> and hardly have affinity with the existing estimation
> framework.

I respectfully disagree. I've strived to make it as affine to the
current implementation as possible - maybe it's possible to improve
that, but I believe there's a natural difference between the two types
of statistics. It may be somewhat simplified, but it will never be
exactly the same.

> I proposed separation of finding stats phase and
> calculation phase, but I would like to propose transforming
> RestrictInfo(and finding mvstat) phase and running the
> transformed RestrictInfo phase after looking close to the
> patch.

Those phases are already separated, as is illustrated by the steps
explained above.

So technically we might place a hook either right after the find_stats()
call, so that it's possible to process all the stats on the table, or
maybe after the choose_mv_statistics() call, so that we only process the
actually used stats.

>
> I think transforing RestrictInfo makes the situnation
> better. Since it nedds different information, maybe it is
> better to have new struct, say, RestrictInfoForEstimate
> (boo!). Then provide mvstatssel() to use in the new struct.
> The rough looking of the code would be like below.
>
> clauselist_selectivity()
> {
> ...
> RestrictInfoForEstmate *esclause =
> transformClauseListForEstimation(root, clauses, varRelid);
> ...
>
> return clause_selectivity(esclause):
> }
>
> clause_selectivity(RestrictInfoForEstmate *esclause)
> {
> if (IsA(clause, RestrictInfo))...
> if (IsA(clause, RestrictInfoForEstimate))
> {
> RestrictInfoForEstimate *ecl = (RestrictInfoForEstimate*) clause;
> if (ecl->selfunc)
> {
> sx = ecl->selfunc(root, ecl);
> }
> }
> if (IsA(clause, Var))...
> }
>
>
> transformClauseListForEstimation(...)
> {
> ...
>
> relid = collect_mvstats_info(root, clause, &attlist);
> if (!relid) return;
> if (get_mvstats_hook)
> mvstats = (*get_mvstats_hoook) (root, relid, attset);
> else
> mvstats = find_mv_stats(root, relid, attset))
> }
> ...

So you'd transform the clause tree first, replacing parts of the tree
(to be estimated by multivariate stats) by a new node type? That's an
interesting idea, I think ...

I can't really say whether it's a good approach, though. Can you explain
why do you think it'd make the situation better?

The one benefit I can think of is being able to look at the processed
tree and see which parts will be estimated using multivariate stats.

But we'd effectively have to do the same stuff (choosing the stats,
...), and if we move this pre-processing before clauselist_selectivity
(I assume that's the point), we'd end up repeating a lot of the code. Or
maybe not, I'm not sure.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services