Nous utilisons des exemples provenant de la base de données créée pour les tests de régression. Commençons avec une requête très simple :

EXPLAIN SELECT * FROM tenk1;

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

Comment le planificateur détermine la cardinalité de tenk1 est couvert dans Section 13.1, « Utiliser EXPLAIN » mais est répété ici pour être complet. Le nombre de lignes est trouvé dans pg_class :

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

 relpages | reltuples
----------+-----------
      345 |     10000

Le planificateur vérifiera l'estimation relpages (une opération peu chère) et, si incorrect, pourrait échelonner avec reltuples pour obtenir une estimation du nombre de lignes. Dans ce cas, il ne peut pas, du coup :

rows = 10000

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

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000;

                         QUERY PLAN
------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..470.00 rows=1031 width=244)
   Filter: (unique1 < 1000)

Le planificateur examine la condition de la clause WHERE  :

unique1 < 1000

et cherche la fonction de restriction à 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_statistics - nous pouvons suivre ceci en utilisant la vue plus simple, pg_stats :

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

                   histogram_bounds
------------------------------------------------------
 {1,970,1943,2958,3971,5069,6028,7007,7919,8982,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 (970 - 1943), 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 - bckt[2].min)/(bckt[2].max - bckt[2].min))/num_bckts
            = (1 + (1000 - 970)/(1943 - 970))/10
            = 0.1031

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.1031
     = 1031

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

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

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..470.00 rows=31 width=244)
   Filter: (stringu1 = 'ATAAAA'::name)

De nouveau, le planificateur examine la condition de la clause WHERE :

stringu1 = 'ATAAAA'

et cherche la fonction de restriction pour =, qui est eqsel. Ce cas est un peu différent car les valeurs les plus communes -- MCV (acronyme de Most Common Values) -- sont utilisées pour déterminer la sélectivité. Regardons-les avec quelques colonnes supplémentaires qui nous serons 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        | 672
most_common_vals  | {FDAAAA,NHAAAA,ATAAAA,BGAAAA,EBAAAA,MOAAAA,NDAAAA,OWAAAA,BHAAAA,BJAAAA}
most_common_freqs | {0.00333333,0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.00266667,0.00266667}

La sélectivité est simplement la fréquence la plus commune (MCF, acronyme de Most Common Frequency) correspondant au troisième MCV -- 'ATAAAA' :

selectivity = mcf[3]
            = 0.003

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

Le nombre affiché par EXPLAIN est un de plus que ceci à cause de quelques vérifications effectuées après l'estimation.

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..470.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.00333333 + 0.003 + 0.003 + 0.003 
            + 0.003 + 0.003 + 0.003 + 0.00266667 + 0.00266667))/(672 - 10)
            = 0.001465

c'est-à-dire ajouter toutes les fréquences pour les MCV et les soustraire de un -- parce qu'il n'est pas un d'entre eux -- et diviser les valeurs distinctes restantes. Notez qu'il n'y a pas de valeurs NULL donc nous n'avons pas à nous en soucier. Le nombre estimé de lignes est calculé comme d'habitude :

rows = 10000 * 0.001465
     = 15

Augmentons la complexité en considérant un cas avec plus d'une condition dans la clause WHERE :

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

                       QUERY PLAN
-----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..495.00 rows=2 width=244)
   Filter: ((unique1 < 1000) AND (stringu1 = 'xxx'::name))

Une supposition d'indépendence est faite et les sélectivités des restrictions individuelles sont multipliées ensemble :

selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx')
            = 0.1031 * 0.001465
            = 0.00015104

Les estimations des lignes sont calculées comme avant :

rows = 10000 * 0.00015104
     = 2

Enfin, nous examinons une requête qui inclut un JOIN avec une clause WHERE :

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

                                      QUERY PLAN
-----------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..346.90 rows=51 width=488)
   ->  Index Scan using tenk1_unique1 on tenk1 t1  (cost=0.00..192.57 rows=51 width=244)
         Index Cond: (unique1 < 50)
   ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..3.01 rows=1 width=244)
         Index Cond: ("outer".unique2 = t2.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. L'opérateur de restriction pour < est scalarlteqsel comme auparavant mais, cette fois, la valeur 50 est dans la première partie de l'histogramme unique1 :

selectivity = (0 + (50 - bckt[1].min)/(bckt[1].max - bckt[1].min))/num_bckts
            = (0 + (50 - 1)/(970 - 1))/10
            = 0.005057

rows        = 10000 * 0.005057
            = 51

La restriction pour la jointure est :

t2.unique2 = t1.unique2

Ceci est dû au côté boucle imbriquée de la méthode de jointure, avec tenk1 dans la boucle externe. L'opérateur est notre = familier, néanmoins la fonction de restriction est obtenue à partir de la colonne oprjoin de pg_operator - et est eqjoinsel. De plus, nous utilisons l'information statistique pour 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 pouvons utiliser 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) * min(1/10000, 1/1000)
            = 0.0001

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

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

Pour les personnes intéressées par plus de détails, l'estimation du nombre de lignes d'une relation est couverte dans src/backend/optimizer/util/plancat.c. La logique du calcul pour les sélectivités des clauses est dans src/backend/optimizer/path/clausesel.c. Les implémentations actuelles de l'opérateur et des fonctions de restriction des jointures sont disponibles dans src/backend/utils/adt/selfuncs.c.