Apply multiple multivariate MCV lists when possible
authorTomas Vondra <tomas.vondra@postgresql.org>
Mon, 13 Jan 2020 00:20:57 +0000 (01:20 +0100)
committerTomas Vondra <tomas.vondra@postgresql.org>
Mon, 13 Jan 2020 00:21:17 +0000 (01:21 +0100)
commiteae056c19ee8f5ebc45ac0fe13181f91c8791e00
treed0d41b085dd0460bb4a152f8c4532d7d177605e7
parentaaa6761876ba5b06a5c3fa914b2951ace1e31dee
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
Discussion: https://postgr.es/m/20191028152048.jc6pqv5hb7j77ocp@development
src/backend/statistics/extended_stats.c
src/test/regress/expected/stats_ext.out
src/test/regress/sql/stats_ext.sql