42.5. Planificateur/Optimiseur

42.5.1. Générer les plans possibles

Le planificateur/optimiseur décide quels plans devraient être générés suivant le type d'index défini sur les relations apparaissant dans une requête. Il y a toujours la possibilité d'exécuter un parcours séquentiel d'une relation, donc un plan utilisant seulement des parcours séquentiels 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 se trouve correspondre à la clé de l'index B-tree et que OPR soit 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 plusieurs index et que les restrictions de la requête font correspondre une clé d'un index, d'autres plans devront être considérés.

Après que tous les plans probables aient é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 clauses jointes disponibles sans 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 en boucle imbriquée (NdT : nested loop join) : la relation droite est parcourue une fois pour chaque ligne trouvée dans la relation gauche. Cette stratégie est facile à implémenter mais peut être très consommatrice en temps. (Néanmoins, si la relation droite peut être parcourue suivant un parcours indexé, ceci peut être une bonne stratégie. Il est possible d'utiliser des valeurs provenant de la ligne actuelle de la relation gauche comme clés pour un parcours indexé à droite.)

• jointure tri et assemblement (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 assemblées en prenant en compte que les deux relations sont triées sur les attributs de jointure. Ce type de jointure est plus attractif parce que chaque relation doit être parcourue seulement une fois.

• jointure de découpage (hash join) : la relation 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 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.

L'arbre de plan terminé consiste en des 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 plans ont la capacité supplémentaire de faire une sélection (annulant 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 des 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.