La corrélation multivariée peut être démontrée avec un jeu de test très simple -- une table avec deux colonnes, chacune contenant les même valeurs :
CREATE TABLE t (a INT, b INT);
INSERT INTO t SELECT i % 100, i % 100 FROM generate_series(1, 10000) s(i);
ANALYZE t;
Comme expliqué dans Section 14.2, l'optimiseur peut
déterminer la cardinalité de t en utilisant le
nombre de pages et de lignes obtenues dans
pg_class :
SELECT relpages, reltuples FROM pg_class WHERE relname = 't';
relpages | reltuples
----------+-----------
45 | 10000
La distribution des données est très simple; il n'y a que 100 valeurs différentes dans chaque colonne, distribuées de manière uniforme.
L'exemple suivant montre le résultat de l'estimation d'une conditino
WHERE sur la colonne a :
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1;
QUERY PLAN
-------------------------------------------------------------------------------
Seq Scan on t (cost=0.00..170.00 rows=100 width=8) (actual rows=100 loops=1)
Filter: (a = 1)
Rows Removed by Filter: 9900
L'optimiseur examine la condition et détermine que la sélectivité de cette
clause est de 1%. En comparant cette estimation avec le nombre de lignes
réel, on voit que l'estimation est très précise (elle est en fait exacte
car la table est très petite). En changeant la clause
WHERE pour utiliser la colonne
b, un plan identique est généré. Mais observons
ce qui arrive si nous appliquons la même condition sur chacune des
colonnes, en les combinant avec AND :
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1 AND b = 1;
QUERY PLAN
-----------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=1 width=8) (actual rows=100 loops=1)
Filter: ((a = 1) AND (b = 1))
Rows Removed by Filter: 9900
L'optimiseur estime la sélectivité pour chaque condition individuellement, en arrivant à la même estimation d'1% comme au dessus. Puis il part du principe que les conditions sont indépendantes, et multiplie donc leurs sélectivité, produisant une estimation de sélectivité finale d'uniquement 0.01%. C'est une sous estimation importante, puisque le nombre réel de lignes correspondant aux conditions (100) est d'un ordre de grandeur deux fois plus haut.
Ce problème peut être corrigé en créant un objet statistiques qui demandera
à ANALYZE de calculer des statistiques multivariées de
dépendances fonctionnelles sur les deux colonnes :
CREATE STATISTICS stts (dependencies) ON a, b FROM t;
ANALYZE t;
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1 AND b = 1;
QUERY PLAN
-------------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=100 width=8) (actual rows=100 loops=1)
Filter: ((a = 1) AND (b = 1))
Rows Removed by Filter: 9900
Un problème similaire apparaît avec l'estimation de la cardinalité d'un
ensemble de plusieurs colonnes, tel que le nombre de groupes qu'une clause
GROUP BY générerait. Quand GROUP BY
liste une seule colonne, l'estimation n-distinct (qui est visible comme le
nombre de lignes estimé par le nœud HashAggregate) est très précis :
EXPLAIN (ANALYZE, TIMING OFF) SELECT COUNT(*) FROM t GROUP BY a;
QUERY PLAN
-----------------------------------------------------------------------------------------
HashAggregate (cost=195.00..196.00 rows=100 width=12) (actual rows=100 loops=1)
Group Key: a
-> Seq Scan on t (cost=0.00..145.00 rows=10000 width=4) (actual rows=10000 loops=1)
Mais sans statistiques multivariées, l'estimation du nombre de groupe dans
une requête ayant deux colonnes dans le GROUP BY, comme
dans l'exemple suivant, est faux d'un ordre de grandeur :
EXPLAIN (ANALYZE, TIMING OFF) SELECT COUNT(*) FROM t GROUP BY a, b;
QUERY PLAN
--------------------------------------------------------------------------------------------
HashAggregate (cost=220.00..230.00 rows=1000 width=16) (actual rows=100 loops=1)
Group Key: a, b
-> Seq Scan on t (cost=0.00..145.00 rows=10000 width=8) (actual rows=10000 loops=1)
En redéfinissant l'objet statistiques pour inclure un nombre n-distinct pour les deux colonnes, l'estimation est bien améliorée :
DROP STATISTICS stts;
CREATE STATISTICS stts (dependencies, ndistinct) ON a, b FROM t;
ANALYZE t;
EXPLAIN (ANALYZE, TIMING OFF) SELECT COUNT(*) FROM t GROUP BY a, b;
QUERY PLAN
--------------------------------------------------------------------------------------------
HashAggregate (cost=220.00..221.00 rows=100 width=16) (actual rows=100 loops=1)
Group Key: a, b
-> Seq Scan on t (cost=0.00..145.00 rows=10000 width=8) (actual rows=10000 loops=1)
Comme expliqué dans Section 71.2.1, les dépendances fonctionnelles sont un type de statistiques peu coûteux et très efficace, mais leur limitation principale est leur nature globale (traquer les dépendances uniquement au niveau de la colonne, pas entre les valeurs des colonnes individuelles).
Cette section introduit la variante des listes MCV
(valeurs les plus communes), une extension directe de la statistique par
colonne décrite dans Section 71.1. Ces
statistiques adressent la limitation du sockage de valeurs individuelles
mais elles sont naturellement plus coûteuses, à la fois pour la
construction des statistiques lors du ANALYZE, pour le
stockage et pour le temps de planification.
Étudions cette requête à partir de Section 71.2.1, mais cette fois avec une liste MCV crée à partir du même ensemble de colonnes (assurez-vous de supprimer les dépendances fonctionnelles, pour s'assurer que le planificateur utilise les statistiques nouvellement créées).
DROP STATISTICS stts;
CREATE STATISTICS stts2 (mcv) ON a, b FROM t;
ANALYZE t;
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1 AND b = 1;
QUERY PLAN
-------------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=100 width=8) (actual rows=100 loops=1)
Filter: ((a = 1) AND (b = 1))
Rows Removed by Filter: 9900
L'estimation est aussi précise qu'avec les dépendances fonctionnelles grâce à la petite volumétrie de la table et à une distribution simple avec un petit nombre de valeurs distinctes. Avant de regarder les deuxième requête, qui n'était pas géré particulièrement bien par les dépendances fonctionnelles, inspectons un peu la liste MCV.
Inspecter la liste MCV est possible en utilisant la
fonction pg_mcv_list_items.
SELECT m.* FROM pg_statistic_ext join pg_statistic_ext_data on (oid = stxoid),
pg_mcv_list_items(stxdmcv) m WHERE stxname = 'stts2';
index | values | nulls | frequency | base_frequency
-------+----------+-------+-----------+----------------
0 | {0, 0} | {f,f} | 0.01 | 0.0001
1 | {1, 1} | {f,f} | 0.01 | 0.0001
...
49 | {49, 49} | {f,f} | 0.01 | 0.0001
50 | {50, 50} | {f,f} | 0.01 | 0.0001
...
97 | {97, 97} | {f,f} | 0.01 | 0.0001
98 | {98, 98} | {f,f} | 0.01 | 0.0001
99 | {99, 99} | {f,f} | 0.01 | 0.0001
(100 rows)
Ceci confirme qu'il y a 100 combinaisons distinctes dans les deux
colonnes, et que leur fréquence est pratiquement identique (fréquence de
1% frequency pour les deux). La fréquence de base est la fréquence
calculée par les statistiques par colonne, comme si il n'y avait pas de
statistiques multi-colonnes. S'il y avait des valeurs NULL dans une des
colonnes, cela se serait vu dans la colonne
nulls.
Lors de l'estimation de la sélectivité, le planificateur applique toutes
les conditions sur les éléments de la liste MCV, puis
additionne les fréquences de celles qui correspondent. Voir
mcv_clauselist_selectivity dans
src/backend/statistics/mcv.c pour les détails.
Comparé aux dépendances fonctionnelles, les listes MCV ont deux avantages majeurs. Tout d'abord, la liste enregistre les valeurs réelles, rendant possible la décision des combinaisons compatibles.
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1 AND b = 10;
QUERY PLAN
---------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=1 width=8) (actual rows=0 loops=1)
Filter: ((a = 1) AND (b = 10))
Rows Removed by Filter: 10000
Ensuite, les listes MCV gèrent un plus grand nombre de types de clause, pas uniquement les clauses d'égalité comme les dépendances fonctionnelles. Voir par exemple la requête d'intervalle, présentée précédemment :
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a <= 49 AND b > 49;
QUERY PLAN
---------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=1 width=8) (actual rows=0 loops=1)
Filter: ((a <= 49) AND (b > 49))
Rows Removed by Filter: 10000