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
sur-simplification 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'échantillonage). 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
.