42.5. Planificateur/Optimiseur
La tâche du planificateur/optimiseur est
de créer un plan d'exécution optimal. En fait, une requête SQL donnée
(et donc, l'arbre d'une requête) peut être exécutée de plusieurs
façons, chacune arrivant au même résultat. Si ce calcul est possible,
l'optimiseur de la requête examinera chacun des plans d'exécution
possibles pour sélectionner le plan d'exécution estimé comme le plus
rapide.
![[Note]](images/note.png)
Note
Dans certaines situations, examiner toutes les façons d'exécuter
une requête prend beaucoup de temps et de mémoire. En
particulier, lors de l'exécution de requêtes impliquant un grand
nombre de jointures. Pour déterminer un plan de requête
raisonnable (mais non optimal) en un temps raisonnable,
PostgreSQL™ utilise un
Optimiseur génétique de requêtes (
Genetic Query
Optimizer
).
La procédure de recherche du planificateur fonctionne en fait avec
des structures de données appelés chemins,
simples représentations minimales de plans ne contenant que
l'information nécessaire au planificateur pour prendre ses décisions.
Une fois le chemin le moins coûteux déterminé, un arbre plan est construit pour être passé à
l'exécuteur. Ceci représente le plan d'exécution désiré avec
suffisamment de détails pour que l'exécuteur puisse le lancer. Dans
le reste de cette section, la distinction entre chemins et plans est
ignorée.
42.5.1. Engendrer les plans possibles
Le planificateur/optimiseur commence par engendrer des plans de
parcours de chaque relation (table) invididuelle utilisée dans la
requête. Les plans possibles sont déterminés par les index
disponibles pour chaque relation. Un parcours séquentiel d'une
relation étant toujours possible, un plan de parcours séquentiel
est systématiquement créé. Supposons qu'un index soit défini sur
une relation (par exemple un index B-tree) et qu'une requête
contienne le filtre relation.attribut OPR
constante. Si relation.attribut
correspond à la clé de l'index B-tree et OPR est un des opérateurs listés dans la classe d'opérateurs de l'index, un autre plan est
créé en utilisant l'index B-tree pour parcourir la relation. S'il
existe d'autres index et que les restrictions de la requête font
correspondre une clé à un index, d'autres plans sont considérés.
Lorsque tous les plans réalistes de parcours des relations simples
ont été découverts, des plans pour les relations jointes sont
créés. Le planificateur/optimiseur considère les jointures entre
toutes les paires de relations pour lesquelles il existe une clause
de jointure correspondante dans la qualification WHERE (c'est-à-dire pour lesquelles une restriction
semblable à where rel1.attr1=rel2.attr2
existe). Les paires jointes sans clause de jointure sont
considérées uniquement quand il n'existe pas d'autre choix,
c'est-à-dire lorsqu'une relation particulière n'a pas de clause de
jointure disponible vers une autre relation. Tous les plans
possibles pour chaque paire jointe considérée par le
planificateur/optimiseur sont engendrées. Les trois stratégies
possibles de jointure sont :
-
jointure de boucle imbriquée
(
nested
loop join
) : la relation de droite est parcourue
une fois pour chaque ligne trouvée dans la relation de
gauche. Cette stratégie est facile à implanter mais peut être
très coûteuse en temps. (Toutefois, si la relation de droite
peut être parcourue à l'aide d'un index, ceci peut être une
bonne stratégie. Il est possible d'utiliser les valeurs
issues de la ligne actuelle de la relation de gauche comme
clés du parcours d'index à droite.)
-
jointure de tri fusionné
(
merge
sort join
) : chaque relation est triée selon les
attributs de la jointure avant que la jointure ne commence.
Puis, les deux relations sont parcourues en parallèle et les
lignes correspondantes sont combinées pour former des lignes
jointes. Ce type de jointure est plus intéressant parce que
chaque relation n'est parcourue qu'une seule fois. Le tri
requis peut être réalisé soit par une étape explicite de tri
soit en parcourant la relation dans le bon ordre en utilisant
un index sur la clé de la jointure.
-
jointure de hachage (
hash
join
) : la relation de droite est tout d'abord
parcourue et chargée dans une table de hachage en utilisant
ses attributs de jointure comme clés de hachage. La relation
de gauche est ensuite parcourue et les valeurs appropriées de
chaque ligne trouvée sont utilisées comme clés de hachage
pour localiser les lignes correspondantes dans la table.
Quand la requête implique plus de deux relations, le résultat final
doit être construit à l'aide d'un arbre d'étapes de jointure,
chacune à deux entrées. Le planificateur examine les séquences de
jointure possibles pour trouver le moins cher.
L'arbre de plan terminé est composé de parcours séquentiels ou
indexés des relations de base, auxquels s'ajoutent les noeuds des
jointures en boucle, des jointures de tri fusionné et des jointures
de hachage si nécessaire, ainsi que toutes les étapes auxiliaires
nécessaires, telles que les noeuds de tri ou les noeuds de calcul
des fonctions d'agrégat. La plupart des types de noeud de plan ont
la capacité supplémentaire de faire une sélection (rejet des lignes qui ne correspondent
pas à une condition booléenne spécifiée) et une projection (calcul d'un ensemble dérivé de
colonnes fondé sur des valeurs de colonnes données, par
l'évaluation d'expressions scalaires si nécessaire). Une des
responsabilités du planificateur est d'attacher les conditions de
sélection issues de la clause WHERE et le
calcul des expressions de sortie requises aux noeuds les plus
appropriés de l'arbre de plan.
Système de règles de PostgreSQL
