Documentation PostgreSQL 14.22 » Internes » Comment le planificateur utilise les statistiques » Exemples d'estimation des lignes

Précédent | Niveau supérieur | Suivant
Chapitre 72. Comment le planificateur utilise les statistiques | Sommaire | 72.2. Exemples de statistiques multivariées

## 72.1. Exemples d'estimation des lignes

Les exemples montrés ci-dessous utilisent les tables de la base de tests de régression de PostgreSQL. Les affichages indiqués sont pris depuis la version 8.3. Le comportement des versions précédentes (ou ultérieures) pourrait varier. Notez aussi que, comme `ANALYZE` utilise un échantillonage statistique lors de la réalisation des statistiques, les résultats peuvent changer légèrement après toute exécution d'`ANALYZE`.

Commençons avec une requête simple :

    EXPLAIN SELECT * FROM tenk1;

                             QUERY PLAN
    -------------------------------------------------------------
     Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244)

Comment le planificateur détermine la cardinalité de `tenk1` est couvert dans Section 14.2 mais est répété ici pour être complet. Le nombre de pages et de lignes est trouvé dans `pg_class` :

    SELECT relpages, reltuples FROM pg_class WHERE relname = 'tenk1';

     relpages | reltuples
    ----------+-----------
          358 |     10000

Ces nombres sont corrects à partir du dernier `VACUUM` ou `ANALYZE` sur la table. Le planificateur récupère ensuite le nombre de pages actuel dans la table (c'est une opération peu coûteuse, ne nécessitant pas un parcours de table). Si c'est différent de `relpages`, alors `reltuples` est modifié en accord pour arriver à une estimation actuelle du nombre de lignes. Dans cet exemple, la valeur de `relpages` est mise à jour, donc l'estimation du nombre de lignes est identique à `reltuples`.

Passons à un exemple avec une condition dans sa clause `WHERE` :

    EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000;

                                       QUERY PLAN
    --------------------------------------------------------------------------------
     Bitmap Heap Scan on tenk1  (cost=24.06..394.64 rows=1007 width=244)
       Recheck Cond: (unique1 < 1000)
       ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
             Index Cond: (unique1 < 1000)

Le planificateur examine la condition de la clause `WHERE` et cherche la fonction de sélectivité à partir de l'opérateur `<` dans `pg_operator`. C'est contenu dans la colonne `oprrest` et le résultat, dans ce cas, est `scalarltsel`. La fonction `scalarltsel` récupère l'histogramme pour `unique1` à partir de `pg_statistic`. Pour les requêtes manuelles, il est plus simple de regarder dans la vue `pg_stats` :

    SELECT histogram_bounds FROM pg_stats
    WHERE tablename='tenk1' AND attname='unique1';

                       histogram_bounds
    ------------------------------------------------------
     {0,993,1997,3050,4040,5036,5957,7057,8029,9016,9995}

Ensuite, la fraction de l'histogramme occupée par « < 1000 » est traitée. C'est la sélectivité. L'histogramme divise l'ensemble en plus petites parties d'égales fréquences, donc tout ce que nous devons faire est de localiser la partie où se trouve notre valeur et compter une partie d'elle et toutes celles qui la précèdent. La valeur 1000 est clairement dans la seconde partie (993–1997), donc en supposant une distribution linéaire des valeurs à l'intérieur de chaque partie, nous pouvons calculer la sélectivité comme étant :

    selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets
                = (1 + (1000 - 993)/(1997 - 993))/10
                = 0.100697

c'est-à-dire une partie complète plus une fraction linéaire de la seconde, divisée par le nombre de parties. Le nombre de lignes estimées peut maintenant être calculé comme le produit de la sélectivité et de la cardinalité de `tenk1` :

    rows = rel_cardinality * selectivity
         = 10000 * 0.100697
         = 1007  (rounding off)

Maintenant, considérons un exemple avec une condition d'égalité dans sa clause `WHERE` :

    EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'CRAAAA';

                            QUERY PLAN
    ----------------------------------------------------------
     Seq Scan on tenk1  (cost=0.00..483.00 rows=30 width=244)
       Filter: (stringu1 = 'CRAAAA'::name)

De nouveau, le planificateur examine la condition de la clause `WHERE` et cherche la fonction de sélectivité pour `=`, qui est `eqsel`. Pour une estimation d'égalité, l'histogramme n'est pas utile ; à la place, la liste des valeurs les plus communes (most common values, d'où l'acronyme MCV fréquemment utilisé) est utilisé pour déterminer la sélectivité. Regardons-les avec quelques colonnes supplémentaires qui nous seront utiles plus tard :

    SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats
    WHERE tablename='tenk1' AND attname='stringu1';

    null_frac         | 0
    n_distinct        | 676
    most_common_vals  | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,JOAAAA,MCAAAA,NAAAAA,WGAAAA}
    most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003}

Comme `CRAAAA` apparaît dans la liste des MCV, la sélectivité est tout simplement l'entrée correspondante dans la liste des fréquences les plus courantes (MCF, acronyme de Most Common Frequencies) :

    selectivity = mcf[3]
                = 0.003

Comme auparavant, le nombre estimé de lignes est seulement le produit de ceci avec la cardinalité de `tenk1` comme précédemment :

    rows = 10000 * 0.003
         = 30

Maintenant, considérez la même requête mais avec une constante qui n'est pas dans la liste MCV :

    EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'xxx';

                            QUERY PLAN
    ----------------------------------------------------------
     Seq Scan on tenk1  (cost=0.00..483.00 rows=15 width=244)
       Filter: (stringu1 = 'xxx'::name)

C'est un problème assez différent, comment estimer la sélectivité quand la valeur n'est pas dans la liste MCV. L'approche est d'utiliser le fait que la valeur n'est pas dans la liste, combinée avec la connaissance des fréquences pour tout les MCV :

    selectivity = (1 - sum(mvf))/(num_distinct - num_mcv)
                = (1 - (0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 +
                        0.003 + 0.003 + 0.003 + 0.003))/(676 - 10)
                = 0.0014559

C'est-à-dire ajouter toutes les fréquences pour les MCV et les soustraire d'un, puis les diviser par le nombre des autres valeurs distinctes. Notez qu'il n'y a pas de valeurs NULL, donc vous n'avez pas à vous en inquiéter (sinon nous pourrions soustraire la fraction NULL à partir du numérateur). Le nombre estimé de lignes est ensuite calculé comme d'habitude :

    rows = 10000 * 0.0014559
         = 15  (rounding off)

L'exemple précédent avec `unique1 < 1000` était une sursimplification de ce que `scalarltsel` faisait réellement ; maintenant que nous avons vu un exemple de l'utilisation des MCV, nous pouvons ajouter quelques détails supplémentaires. L'exemple était correct aussi loin qu'il a été car, comme `unique1` est une colonne unique, elle n'a pas de MCV (évidemment, n'avoir aucune valeur n'est pas plus courant que toute autre valeur). Pour une colonne non unique, il y a normalement un histogramme et une liste MCV, et l'histogramme n'inclut pas la portion de la population de colonne représentée par les MCV. Nous le faisons ainsi parce que cela permet une estimation plus précise. Dans cette situation, `scalarltsel` s'applique directement à la condition (c'est-à-dire « < 1000 ») pour chaque valeur de la liste MCV, et ajoute les fréquence des MCV pour lesquelles la condition est vérifiée. Ceci donne une estimation exacte de la sélectivité dans la portion de la table qui est MCV. L'histogramme est ensuite utilisée de la même façon que ci-dessus pour estimer la sélectivité dans la portion de la table qui n'est pas MCV, et ensuite les deux nombres sont combinés pour estimer la sélectivité. Par exemple, considérez

    EXPLAIN SELECT * FROM tenk1 WHERE stringu1 < 'IAAAAA';

                             QUERY PLAN
    ------------------------------------------------------------
     Seq Scan on tenk1  (cost=0.00..483.00 rows=3077 width=244)
       Filter: (stringu1 < 'IAAAAA'::name)

Nous voyons déjà l'information MCV pour `stringu1`, et voici son histogramme :

    SELECT histogram_bounds FROM pg_stats
    WHERE tablename='tenk1' AND attname='stringu1';

                                    histogram_bounds
    --------------------------------------------------------------------------------
     {AAAAAA,CQAAAA,FRAAAA,IBAAAA,KRAAAA,NFAAAA,PSAAAA,SGAAAA,VAAAAA,XLAAAA,ZZAAAA}

En vérifiant la liste MCV, nous trouvons que la condition `stringu1 < 'IAAAAA'` est satisfaite par les six premières entrées et non pas les quatre dernières, donc la sélectivité dans la partie MCV de la population est :

    selectivity = sum(relevant mvfs)
                = 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003
                = 0.01833333

Additionner toutes les MFC nous indique aussi que la fraction totale de la population représentée par les MCV est de 0.03033333, et du coup la fraction représentée par l'histogramme est de 0.96966667 (encore une fois, il n'y a pas de NULL, sinon nous devrions les exclure ici). Nous pouvons voir que la valeur `IAAAAA` tombe près de la fin du troisième jeton d'histogramme. En utilisant un peu de suggestions sur la fréquence des caractères différents, le planificateur arrive à l'estimation 0.298387 pour la portion de la population de l'histogramme qui est moindre que `IAAAAA`. Ensuite nous combinons les estimations pour les populations MCV et non MCV :

    selectivity = mcv_selectivity + histogram_selectivity * histogram_fraction
                = 0.01833333 + 0.298387 * 0.96966667
                = 0.307669

    rows        = 10000 * 0.307669
                = 3077  (rounding off)

Dans cet exemple particulier, la correction à partir de la liste MCV est très petit car la distribution de la colonne est réellement assez plat (les statistiques affichant ces valeurs particulières comme étant plus communes que les autres sont principalement dûes à une erreur d'échantillonnage). Dans un cas plus typique où certaines valeurs sont significativement plus communes que les autres, ce processus compliqué donne une amélioration utile dans la précision car la sélectivité pour les valeurs les plus communes est trouvée exactement.

Maintenant, considérons un cas avec plus d'une condition dans la clause `WHERE` :

    EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000 AND stringu1 = 'xxx';

                                       QUERY PLAN
    --------------------------------------------------------------------------------
     Bitmap Heap Scan on tenk1  (cost=23.80..396.91 rows=1 width=244)
       Recheck Cond: (unique1 < 1000)
       Filter: (stringu1 = 'xxx'::name)
       ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
             Index Cond: (unique1 < 1000)

Le planificateur suppose que les deux conditions sont indépendantes, pour que les sélectivités individuelles des clauses puissent être multipliées ensemble :

    selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx')
                = 0.100697 * 0.0014559
                = 0.0001466

    rows        = 10000 * 0.0001466
                = 1  (rounding off)

Notez que l'estimation du nombre de lignes renvoyées à partir du bitmap index scan reflète seulement la condition utilisée avec l'index ; c'est important car cela affecte l'estimation du coût pour les récupérations suivantes sur la table.

Enfin, nous examinerons une requête qui implique une jointure :

    EXPLAIN SELECT * FROM tenk1 t1, tenk2 t2
    WHERE t1.unique1 < 50 AND t1.unique2 = t2.unique2;

                                          QUERY PLAN
    -----------------------------------------------------------------------------------------
    --------------------------------------------------------------------------------------
     Nested Loop  (cost=4.64..456.23 rows=50 width=488)
       ->  Bitmap Heap Scan on tenk1 t1  (cost=4.64..142.17 rows=50 width=244)
             Recheck Cond: (unique1 < 50)
             ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..4.63 rows=50 width=0)
                   Index Cond: (unique1 < 50)
       ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..6.27 rows=1 width=244)
             Index Cond: (unique2 = t1.unique2)

La restriction sur `tenk1`, `unique1 < 50`, est évaluée avant la jointure de boucle imbriquée. Ceci est géré de façon analogue à l'exemple précédent. Cette fois, la valeur 50 est dans la première partie de l'histogramme `unique1` :

    selectivity = (0 + (50 - bucket[1].min)/(bucket[1].max - bucket[1].min))/num_buckets
                = (0 + (50 - 0)/(993 - 0))/10
                = 0.005035

    rows        = 10000 * 0.005035
                = 50  (rounding off)

La restriction pour la jointure est `t2.unique2 = t1.unique2`. L'opérateur est tout simplement le `=`, néanmoins la fonction de sélectivité est obtenue à partir de la colonne `oprjoin` de `pg_operator`, et est `eqjoinsel`. `eqjoinsel` recherche l'information statistique de `tenk2` et `tenk1` :

    SELECT tablename, null_frac,n_distinct, most_common_vals FROM pg_stats
    WHERE tablename IN ('tenk1', 'tenk2') AND attname='unique2';

    tablename  | null_frac | n_distinct | most_common_vals
    -----------+-----------+------------+------------------
     tenk1     |         0 |         -1 |
     tenk2     |         0 |         -1 |

Dans ce cas, il n'y a pas d'information MCV pour `unique2` parce que toutes les valeurs semblent être unique, donc nous utilisons un algorithme qui relie seulement le nombre de valeurs distinctes pour les deux relations ensembles avec leur fractions NULL :

    selectivity = (1 - null_frac1) * (1 - null_frac2) * min(1/num_distinct1, 1/num_distinct2)
                = (1 - 0) * (1 - 0) / max(10000, 10000)
                = 0.0001

C'est-à-dire, soustraire la fraction NULL pour chacune des relations, et divisez par le maximum du nombre de valeurs distinctes. Le nombre de lignes que la jointure pourrait émettre est calculé comme la cardinalité du produit cartésien de deux inputs, multiplié par la sélectivité :

    rows = (outer_cardinality * inner_cardinality) * selectivity
         = (50 * 10000) * 0.0001
         = 50

S'il y avait eu des listes MCV pour les deux colonnes, `eqjoinsel` aurait utilisé une comparaison directe des listes MCV pour déterminer la sélectivité de jointure à l'intérieur de la aprtie des populations de colonne représentées par les MCV. L'estimation pour le reste des populations suit la même approche affichée ici.

Notez que nous affichons `inner_cardinality` à 10000, c'est-à-dire la taille non modifiée de `tenk2`. Il pourrait apparaître en inspectant l'affichage `EXPLAIN` que l'estimation des lignes jointes vient de 50 * 1, c'est-à-dire que le nombre de lignes externes multiplié par le nombre estimé de lignes obtenu par chaque parcours d'index interne sur `tenk2`. Mais ce n'est pas le cas : la taille de la relation jointe est estimée avant tout plan de jointure particulier considéré. Si tout fonctionne si bien, alors les deux façons d'estimer la taille de la jointure produiront la même réponse mais, à cause de l'erreur d'arrondi et d'autres facteurs, ils divergent quelque fois significativement.

Pour les personnes intéressées par plus de détails, l'estimation de la taille d'une table (avant toute clause `WHERE`) se fait dans `src/backend/optimizer/util/plancat.c`. La logique générique pour les sélectivités de clause est dans `src/backend/optimizer/path/clausesel.c`. Les fonctions de sélectivité spécifiques aux opérateurs se trouvent principalement dans `src/backend/utils/adt/selfuncs.c`.