Apply multiple multivariate MCV lists when possible

Enterprise / PostgreSQL - Tomas Vondra [postgresql.org] - 13 January 2020 00:21 EST

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

eae056c19e Apply multiple multivariate MCV lists when possible
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(-)

Upstream: git.postgresql.org


  • Share