PostgreSQLLa base de données la plus sophistiquée au monde.

Version anglaise

70.2. Exemples de statistiques multivariées

70.2.1. Dépendances fonctionnelles

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, « Statistiques utilisées par le planificateur », 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

70.2.2. Nombre N-Distinct Multivarié

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)

70.2.3. Listes MCV

Comme expliqué dans Section 70.2.1, « Dépendances fonctionnelles », 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 70.1, « Exemples d'estimation des lignes ». 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 70.2.1, « Dépendances fonctionnelles », 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