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 finir par sélectionner le plan d'exécution estimé comme étant le plus rapide.
![[Note]](images/note.png)
Dans certaines situations, examiner chaque moyen d'exécuter une requête prendrait beaucoup de temps et de mémoire. En particulier, cela arrive lors de l'exécution de requêtes impliquant un grand nombre de jointures. Pour déterminer un plan de requête raisonnable (et non optimal) dans 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, qui sont simplement des représentations minimales de plans contenant seulement l'information nécessaire pour que le planificateur puisse prendre ses décisions. Une fois le chemin le moins coûteux déterminé, un arbre plan est construit pour être donné à 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, nous ignorerons la distinction entre chemins et plans.
Le planificateur/optimiseur commence par générer des plans pour parcourir chaque relation (table) invididuelle utilisée dans la requête. Les plans possibles sont déterminés par les index disponibles pour chaque relation. Il est toujours possible de réaliser un parcours séquentiel sur une relation, donc un plan de parcours séquentiel est toujours 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 seront considérés.
Une fois que tous les plans probables ont été trouvés pour parcourir les relations simples, des plans pour les relations jointes sont créés. Le planificateur/optimiseur préfère considérer les jointures entre deux relations pour lesquelles il existe une clause de jointure correspondante dans la qualification WHERE (c'est-à-dire pour lequel une restriction comme where rel1.attr1=rel2.attr2 existe). Des paires de jointures sans clause de jointure sont considérées seulement 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 toute autre relation. Tous les plans possibles sont générés pour chaque paire de jointure considérée par le planificateur/optimiseur. Les trois stratégies possibles de jointure sont :
jointure de boucle imbriquée (NdT : 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 à implémenter mais peut être très coûteuse en temps. (Par contre, 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 des valeurs provenant de la ligne actuelle de la relation de gauche comme clés pour un parcours indexé à droite.)
jointure tri et fusion (NdT : merge sort join) : Chaque relation est triée sur 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 pourrait ê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 découpage (hash join) : la relation de droite est tout d'abord parcourue et chargée dans une table de découpage en utilisant ses attributs de jointure comme clés de découpage. Ensuite, la relation de gauche est parcourue et les valeurs appropriées de chaque ligne trouvée sont utilisées comme clés de découpage pour localiser les lignes correspondantes dans la table.
Quand la requête implique plus de deux relations, le résultat final doit être construit par un arbre d'étapes de jointure, chacune ayant 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, plus les nœuds des jointures en boucle, jointures tri et rassemblement, et jointures de découpage si nécessaire, plus toutes les étapes auxiliaires nécessaires, tels que les nœuds de tri ou les nœuds de calcul des fonctions d'agrégat. La plupart des types de nœud de plan ont la capacité supplémentaire de faire une sélection (rejetant les lignes qui ne correspondent pas à une condition booléenne spécifiée) et une projection (calcul d'un ensemble de colonnes dérivées basé sur des valeurs de colonnes données, c'est-à-dire l'évaluation d'expressions scalaires si nécessaire). Une des responsabilités du planificateur est d'attacher les conditions de sélection à partir de la clause WHERE et du calcul des expressions de calculs requises aux nœuds les plus appropriés de l'arbre de plan.
Système de règles de
PostgreSQL