pgsql: Apply multiple multivariate MCV lists when possible

Previous Topic Next Topic
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

pgsql: Apply multiple multivariate MCV lists when possible

Tomas Vondra-5
Apply multiple multivariate MCV lists when possible

Until now we've only used a single multivariate MCV list per relation,
covering the largest number of clauses. So for example given a query

    SELECT * FROM t WHERE a = 1 AND b =1 AND c = 1 AND d = 1

and extended statistics on (a,b) and (c,d), we'd only pick and use one
of them. This commit improves this by repeatedly picking and applying
the best statistics (matching the largest number of remaining clauses)
until no additional statistics is applicable.

This greedy algorithm is simple, but may not be optimal. A different
choice of statistics may leave fewer clauses unestimated and/or give
better estimates for some other reason.

This can however happen only when there are overlapping statistics, and
selecting one makes it impossible to use the other. E.g. with statistics
on (a,b), (c,d), (b,c,d), we may pick either (a,b) and (c,d) or (b,c,d).
But it's not clear which option is the best one.

We however assume cases like this are rare, and the easiest solution is
to define statistics covering the whole group of correlated columns. In
the future we might support overlapping stats, using some of the clauses
as conditions (in conditional probability sense).

Author: Tomas Vondra
Reviewed-by: Mark Dilger, Kyotaro Horiguchi



Modified Files
src/backend/statistics/extended_stats.c | 139 +++++++++++++++++---------------
src/test/regress/expected/stats_ext.out |  57 +++++++++++++
src/test/regress/sql/stats_ext.sql      |  35 ++++++++
3 files changed, 167 insertions(+), 64 deletions(-)