6. Evaluation et optimisation

L’objectif de ce chapitre est de montrer comment un SGBD analyse, optimise et exécute une requête. SQL étant un langage déclaratif dans lequel on n’indique ni les algorithmes à appliquer, ni les chemins d’accès aux données, le système a toute latitude pour déterminer ces derniers et les combiner de manière à obtenir les meilleures performances.

Le module chargé de cette tâche, l’optimiseur de requêtes, tient donc un rôle extrêmement important puisque l’efficacité d’un SGBD est fonction, pour une grande part, du temps d’exécution des requêtes. Ce module est complexe. Il applique d’une part des techniques éprouvées, d’autre part des heuristiques propres à chaque système. Il est en effet reconnu qu’il est très difficile de trouver en un temps raisonnable l’algorithme optimal pour exécuter une requête donnée. Afin d’éviter de consacrer des resources considérables à l’optimisation, ce qui se ferait au détriment des autres tâches du système, les SGBD s’emploient donc à trouver, en un temps limité, un algorithme raisonnablement bon.

La compréhension des mécanismes d’exécution et d’optimisation fournit une aide très précieuse quand vient le moment d’analyser le comportement d’une application et d’essayer de distinguer les goulots d’étranglements. Comme nous l’avons vu dans les chapitres consacrés au stockage des données et aux index, des modifications très simples de l’organisation physique peuvent aboutir à des améliorations (ou des dégradations) extrêmement spectaculaires des performances. Ces constatations se transposent évidemment au niveau des algorithmes d’évaluation : le choix d’utiliser ou non un index conditionne fortement les temps de réponse, sans que ce choix soit d’ailleurs évident dans toutes les circonsstances.

S1: traitement de la requête

Cette section est consacrée à la phase de traitement permettant de passer d’un requête SQL à une forme “opérationnelle”. Nous présentons successivement la traduction de la requête SQL en langage algébrique représentant les opérations nécessaires, puis les réécritures symboliques qui organisent ces opérations de la manière la plus efficace.

Décomposition en bloc

Une requête SQL est décomposée en une collection de blocs. L’optimiseur se concentre sur l’optimisation d’un bloc à la fois. Un bloc est une requête select-from-where sans imbrication. La décomposition en blocs est nécessaire à cause des requêtes imbriquées. Toute requête SQL ayant des imbrications peut être décomposée en une collection de blocs. Considérons par exemple la requête suivante qui calcule le film le mieux ancien:

select titre
from   Film
where  annee = (select min (annee) from Film)

On peut décomposer cette requête en deux blocs: le premier calcule l’année minimale \(A\). Le deuxième bloc calcule le(s) film(s) paru en \(A\) grâce à une référence au premier bloc.

select titre
from   Film
where  annee = A

Cette méthode peut s’avérer très inefficace et il est préférable de transformer la requête avec imbrication en une requête équivalente sans imbrication (un seul bloc) quand cette équivalence existe. Malheureusement, les systèmes relationnels ne sont pas toujours capables de déceler ce type d’équivalence. Le choix de la syntaxe de la requête SQL a donc une influence sur les possibilités d’optimisation laissées au SGBD.

Prenons un exemple concret pour comprendre la subtilité de certaines situations, et pourquoi le système à parfois besoin qu’on lui facilite la tâche. Notre base de données est toujours la même, rappelons le schéma de la table Role car il est important.

create table Role (id_acteur integer not null,
                   id_film integer not null,
                   nom_role varchar(30) not null,
                   primary key (id_acteur, id_film),
                   foreign key (id_acteur) references Artiste(id),
                   foreign key (id_film) references Film(id),
                   );

Le système crée un index sur la clé primaire qui est composée de deux attributs. Quelles requêtes peuvent tirer parti de cet index? Celles sur l’identifiant de l’acteur, celles sur l’identifiant du film? Réfléchissez-y, réponse plus loin.

Maintenant, notre requête est la suivante: “Dans quel film paru en 1958 joue James Stewart” (vous avez sans doute deviné qu’il s’agit de Vertigo)? Voici comment on peut exprimer la requête SQL.

select titre
from   Film f, Role r, Artiste a
where  a.nom = 'Stewart' and a.prenom='James'
and    f.id_film = r.id_film
and    r.id_acteur = a.idArtiste
and    f.annee = 1958

Cette requête est en un seul “bloc”, mais il est tout à fait possible – question de style ? – de l’écrire de la manière suivante:

select titre
from   Film f, Role r
where  f.id_film = r.id_film
and    f.annee = 1958
and    r.id_acteur in (select id_acteur
                      from Artiste
                      where nom='Stewart'
                      and prenom='James')

Au lieu d’utiliser in, on peut également effectuer une requête corrélée avec exists.

select titre
from   Film f, Role r
where  f.id_film = r.id_film
and    f.annee = 1958
and    exists (select 'x'
               from Artiste a
               where nom='Stewart'
               and prenom='James'
               and r.id_acteur = a.id_acteur)

Encore mieux (ou pire), on peut utiliser deux imbrications:

select titre from Film
where annee = 1958
and  id_film in
       (select id_film from Role
        where id_acteur in
             (select id_acteur
              from Artiste
              where nom='Stewart'
              and prenom='James'))

Que l’on peut aussi formuler en:

select titre from Film
where annee = 1958
and exists
       (select * from Role
        where id_film = Film.id
        and exists
             (select *
              from Artiste
              where id = Role.id_acteur
              and nom='Stewart'
              and prenom='James'))

Dans les deux dernier cas on a trois blocs. La requête est peut-être plus facile à comprendre (vraiment?), mais le système a très peu de choix sur l’exécution: on doit parcourir tous les films parus en 1958, pour chacun on prend tous les rôles, et pour chacun de ces rôles on va voir s’il s’agit bien de James Stewart.

S’il n’y a pas d’index sur le champ annee de Film, il faudra balayer toute la table, puis pour chaque film, c’est la catastrophe: il faut parcourir tous les rôles pour garder ceux du film courant car aucun index n’est disponible. Enfin pour chacun de ces rôles il faut utiliser l’index sur Artiste.

Pourquoi ne peut-on pas utiliser l’index sur Role?

La clé de Role est une clé composite (id_acteur, id_film). L’index est un arbre B construit sur la concaténation des deux identifiants dans l’ordre où il sont spécifiés. Souvenez-vous: un arbre B s’appuie sur l’ordre des clés, et on peut effectuer des recherches sur un préfixe de la clé. En revanche il est impossible d’utiliser l’arbre B sur un suffixe. Ici, on peut utiliser l’index pour des requêtes sur id_acteur, pas pour des requêtes sur id_film. C.Q.F.D.

Telle quelle, cette syntaxe basée sur l’imbrication a toutes les chances d’être extrêmement coûteuse à évaluer. Or il existe un plan bien meilleur (lequel?), mais le système ne peut le trouver que s’il a des degrés de liberté suffisants, autrement dit si la requête est à plat, en un seul bloc. Il est donc recommandé de limiter l’emploi des requêtes imbriquées à de petites tables dont on est sûr qu’elles résident en mémoire.

Traduction et réécriture

Nous nous concentrons maintenant sur le traitement d’un bloc, étant entendu que ce traitement doit être effectué autant de fois qu’il y a de blocs dans une requête. Il comprend plusieurs phases. Tout d’abord une analyse syntaxique est effectuée, puis une traduction algébrique permettant d’exprimer la requête sous la forme d’un ensemble d’opérations sur les tables. Enfin l’optimisation consiste à trouver les meilleurs chemins d’accès aux données et à choisir les meilleurs algorithmes possibles pour effectuer ces opérations.

L’analyse syntaxique vérifie la validité (syntaxique) de la requête. On vérifie notamment l’existence des relations (arguments de la clause from) et des attributs (clauses select et where). On vérifie également la correction grammaticale (notamment de la clause where). D’autres transformations sémantiques simples sont faites au delà de l’analyse syntaxique. Par exemple, on peut détecter des contradictions comme année = 1998 and année = 2003. Enfin un certain nombre de simplifications sont effectuées. À l’issue de cette phase, le système considère que la requête est bien formée.

L’étape suivante consiste à traduire la requête \(q\) en une expression algébrique \(e(q)\). Nous allons prendre pour commencer une requête un peu plus simple que la précédente: trouver le titre du film paru en 1958, où l’un des acteurs joue le rôle de John Ferguson (rassurez-vous c’est toujours Vertigo). Voici la requête SQL:

select titre
from   Film f, Role r
where  nom_role ='John Ferguson'
and    f.id = r.id_ilm
and    f.annee = 1958

Cette requête correspond aux opérations suivantes: une jointure entre les rôles et les films, une sélection sur les films (année=1958), une sélection sur les rôles (‘John Ferguson), enfin une projection pour éliminer les colonnes non désirées. La combinaison de ces opérations donne l’expression algébrique suivante:

\[\pi_{titre}(\sigma_{annee=1958 \land nom\_role='\mathrm{John\ Ferguson}'}(Film \Join_{id=id\_film} Role)\]

Cette expression comprend des opérations unaires (un seul argument) et des opérations binaires. On peut la représenter sous la forme d’un arbre (figure Expression algébrique sous forme arborescente), ou Plan d’Exécution Logique (PEL), représentant l’expression algébrique équivalente à la requête SQL. Dans l’arbre, les feuilles correspondent les tables arguments de l’expression algébrique, et les nœuds internes aux opérateurs algébriques. Un arc entre un nœud \(n\) et son nœud père \(p\) indique que ‘opération \(p\) s’applique au résultat de l’opération \(n\).

_images/QTradAlg.png

Fig. 6.1 Expression algébrique sous forme arborescente

L’interprétation de l’arbre est la suivante. On commence par exécuter les opérations sur les feuilles (ici les sélections); sur le résultat, on effectue les opérations correspondant aux nœuds de plus haut niveau (ici une jointure), et ainsi de suite, jusqu`à ce qu’on obtienne le résultat (ici après la projection). Cette interprétation est bien sûr rendue possible par le fait que tout opérateur prend une table en entrée et produit une table en sortie.

Avec cette représentation de la requête sous une forme “opérationnelle”, nous sommes prêts pour la phase d’optimisation.

S2: optimisation de la requête

La réécriture

Nous disposons donc d’un plan d’exécution logique (PEL) présentant, sous une forme normalisée (par exemple, les projections, puis les sélections, puis les jointures) les opérations nécessaires à l’exécution d’une requête donnée.

On peut reformuler le PEL grâce à l’existence de propriétés sur les expressions de l’algèbre relationnelle. Ces propriétés appelées lois algébriques ou encore règles de réécriture permettent de transformer l’expression algébrique en une expression équivalente et donc de réagencer l’arbre. Le PEL obtenu est équivalent, c’est-à-dire qu’il conduit au même résultat. En transformant les PEL grâce à ces règles, on peut ainsi obtenir des plans d’exécution alternatifs, et tenter d’évaluer lequel est le meilleur. Voici la liste des règles de réécriture les plus importantes:

  • Commutativité des jointures.

    \[R \Join S \equiv S \Join R\]
  • Associativité des jointures

    \[(R \Join S) \Join T \equiv R \Join (S \Join T)\]
  • Regroupement des sélections

    \[\sigma_{A='a' \wedge B='b'}(R) \equiv \sigma_{A='a'}(\sigma_{B='b'}(R))\]
  • Commutativité de la sélection et de la projection

    \[\pi_{A_1, A_2, ... A_p}(\sigma_{A_i='a} (R)) \equiv \sigma_{A_i='a}(\pi_{A_1, A_2, ... A_p}(R)), i \in \{1,...,p\}\]
  • Commutativité de la sélection et de la jointure

    \[\sigma_{A='a'} (R(...A...) \Join S) \equiv \sigma_{A='a'}(R) \Join S\]
  • Distributivité de la sélection sur l’union

    \[\sigma_{A='a'} (R \cup S) \equiv \sigma_{A='a'} (R) \cup \sigma_{A='a'} (S)\]
  • Commutativité de la projection et de la jointure

    \[\pi_{A_1 ... A_p}(R) \Join_{A_i=B_j}\pi_{B_1... B_q}(S))\; i \in \{1,..,p\}, j \in \{1,...,q\}\]
  • Distributivité de la projection sur l’union

    \[\pi_{A_1A_2...A_p} (R \cup S) \equiv \pi_{A_1A_2...A_p} (R) \cup \pi_{A_1A_2...A_p} (S)\]

Ces règles sont à la base du processus d’optimisation dont le principe est d’énumérer tous les plans d’exécution possible. Par exemple la règle 3 permet de gérer finement l’affectation des sélections . En effet si la relation est indexée sur l’atttribut B, la règle justifie de filter sur A seulement les enregistrements satisfaisant le critère \(B='b'\) obtenus par traversée d’index. La commutatitivité de la projection avec la sélection et la jointure (règles 4 et 7) d’une part et de la sélection et de la jointure d’autre part (règle 5) permettent de faire les sélections et les projections le plus tôt possible dans le plan (et donc le plus bas possible dans l’arbre) pour réduire les tailles des relations manipulées, ce qui est l’idée de base pour le choix d’un meilleur PEL. En effet nous avons vu que l’efficacité des algorithmes implantant les opérations algébriques est fonction de la taille des relations en entrée. C’est particulièrement vrai pour la jointure qui est une opération coûteuse. Quand une séquence comporte une jointure et une sélection, il est préférable de faire la sélection d’abord: on réduit ainsi la taille d’une ou des deux relations à joindre, ce qui peut avoir un impact considérable sur le temps de traitement de la jointure.

Pousser les sélections le plus bas possible dans l’arbre, c’est-à-dire essayer de les appliquer le plus rapidement possible et éliminer par projection les attributs non nécessaires pour obtenir le résultat de la requête sont donc deux heuristiques le plus souvent effectives pour transformer un PEL en un meilleur PEL (équivalent) .

Voici un algorithme simple résumant ces idées:

  • Séparer les sélections avec plusieurs prédicats en plusieurs sélections à un prédicat (règle 3).
  • Descendre les sélections le plus bas possible dans l’arbre (règles 4, 5, 6)
  • Regrouper les sélections sur une même relation (règle 3).
  • Descendre les projections le plus bas possible (règles 7 et 8).
  • Regrouper les projections sur une même relation.

Reprenons notre requête cherchant le film paru en 1958 avec un rôle “John Ferguson”. Voici l’expression algébrique complète.

\[\pi_{titre}(\sigma_{annee=1958 \land nom\_role='John\ Ferguson'}(Film \Join_{id=id\_film} (Role) )\]

L’expression est correcte, mais probablement pas optimale. Appliquons notre algorithme. La première étape donne l’expression suivante:

\[\pi_{titre}(\sigma_{annee=1958} ( \sigma_{nom\_role='John\ Ferguson'}(Film \Join_{id=id\_film} (Role) ))\]

On a donc séparé les sélections. Maintenant on les descend dans l’arbre:

\[\pi_{titre}( \sigma_{annee=1958} (Film) \Join_{id=id\_film} \sigma_{nom\_role='John\ Ferguson'}(Role) )\]

Finalement il reste à ajouter des projections pour limiter la taille des enregistrements. À chaque étape du plan, les projections consisteraient (nous ne les montrons pas) à supprimer les attributs inutiles. Pour conclure deux remarques sont nécessaires:

  • le principe “sélection avant jointure” conduit dans la plupart des cas à un PEL plus efficace; mais il peut arriver (très rarement) que la jointure soit plus réductrice en taille et que la stratégie “jointure d’abord, sélection ensuite”, conduise à un meilleur PEL.
  • cette optimisation du PEL, si elle est nécessaire, est loin d’être suffisante: il faut ensuite choisir le “meilleur” algorithme pour chaque opération du PEL. Ce choix va dépendre des chemins d’accès et des statistiques sur les tables de la base et bien entendu des algorithmes d’évaluation implantés dans le noyau. Le PEL est alors transformé en un plan d’exécution physique.

Cette transformation constitue la dernière étape de l’optimisation. Elle fait l’objet de la section suivante.

Plans d’exécution

Un plan d’exécution physique (PEP) est un arbre d’opérateurs (on parle d’algèbre physique), issus d’un “catalogue” propre à chaque SGBD. On retrouve, avec des variantes, les principaux opérateurs d’un SGBD à un autre. Nous les avons étudiés dans le chapitre Evaluation et optimisation, et nous les reprenons maintenant pour étudier quelques exemples de plan d’exécution.

On peut distinguer tout d’abord les opérateurs d’accès:

  • le parcours séquentiel d’une table, FullScan,
  • le parcours d’index, IndexScan,
  • l’accès direct à un enregistrement par son adresse, DirectAccess, nécessairement combiné avec le précédent.

Puis, une second catégorie que nous appellerons opérateurs de manipulation:

  • la sélection, Filter;
  • la projection, Project;
  • le tri, Sort;
  • la fusion de deux listes, Merge;
  • la jointure par boucles imbriquées indexées, IndexedNestedLoop, abrégée en INL.

Cela nous suffira. Nous reprenons notre requête cherchant les films parus en 1958 avec un rôle “John Ferguson”. Pour mémoire, le plan d’exécution logique auquel nous étions parvenu est le suivant.

\[\pi_{titre}( \sigma_{annee=1958} (Film) \Join_{id=id\_film} \sigma_{nom\_role='John\ Ferguson'}(Role) )\]

Nous devons maintenant choisir des opérateurs physiques, choix qui dépend de nombreux facteurs: chemin d’accès, statistiques, nombre de blocs en mémoire centrale. En fonction de ces paramètres, l’optimiseur choisit, pour chaque nœud du PEL, un opérateur physique ou une combinaison d’opérateurs.

Une première difficulté vient du grand nombre de critères à considérer: quelle mémoire allouer, comment la partager entre opérateurs, doit-on privilégier temps de réponse ou temps d’exécution, etc. Une autre difficulté vient du fait que le choix d’un algorithme pour un nœud du PEL peut avoir un impact sur le choix d’un algorithme pour d’autres nœuds (notamment concernant l’utilisation de la mémoire). Tout cela mène à une procédure d’optimisation complexe, mise au point et affinée par les concepteurs de chaque système, dont il est bien difficile (et sans doute peu utile) de connaître les détails. Ce qui suit est donc plutôt une méthodologie générale, illustrée par des exemples.

Prenons comme hypothèse directrice que l’objectif principal de l’optimiseur soit d’exécuter les jointures avec l’algorithme IndexNestedLoop (ce qui est raisonnable pour obtenir un bon temps de réponse et limiter la mémoire nécessaire). Pour chaque jointure, il faut donc envisager les index disponibles. Ici, la jointure s’effectue entre Film et Role, ce dernier étant indexé sur la clé primaire (id_acteur, id_film). La jointure est commutative (cf. les règles de réécriture. On peut donc effectuer, de manière équivalente,

\[Film \Join_{id=id\_film} Role\]

ou

\[Role \Join_{id\_film=id} Film\]

Regardons pour quelle version nous pouvons utiliser un index avec l’algorithme IndexNestedLoop. Dans le premier cas, nous lisons des tuples film (à gauche) et pour chaque film nous cherchons les rôles (à droite). Peut-on utiliser l’index sur rôle? Non, pour les raisons déjà expliquées dans la session 1: l’identifiant du film est un suffixe de la clé de l’arbre B, et ce dernier est donc inopérant.

Second cas: on lit des rôles (à gauche) et pour chaque rôle on cherche le film. Peut-on utiliser l’index sur film? Oui, bien sûr: on est dans le cas où on lit les tuples de la table contenant la clé étrangère, et où on peut accéder par la clé primaire à la seconde table (revoir le chapitre Opérateurs et algorithmes pour réviser les algorithmes de jointure si nécessaire). Nos règles de réécriture algébrique nous permettent de reformuler le plan d’exécution logique, en commutant la jointure.

\[\pi_{titre}(\sigma_{nom\_role='John\ Ferguson'}(Role) \Join_{id\_film=id} \sigma_{annee=1958} (Film) )\]

Et, plus important, nous pouvons maintenant implanter ce plan avec l’algorithme de jointures imbriquées indexées, ce qui donne l’arbre de la figure Le plan d’exécution “standard”.

_images/planEx-full1.png

Fig. 6.2 Le plan d’exécution “standard”

Note

L’opérateur de projection n’est pas montré sur les figures. Il intervient de manière triviale comme racine du plan d’exécution complet.

Peut-on faire mieux? Oui, en créant des index. La première possibilité est de créer un index pour éviter un parcours séquentiel de la table gauche. Ici, on peut créer un index sur le nom du rôle, et remplacer l’opérateur de parcours séquentiel par la combinaison habituelle (IndexScan + DirectAccess). Cela donne le plan de la figure Le plan d’exécution avec deux index.

_images/planEx-full2.png

Fig. 6.3 Le plan d’exécution avec deux index

Ce plan est certainement le meilleur. Cela ne signifie pas qu’il faut créer des index à tort et à travers: la maintenance d’index a un coût, et ne se justifie que pour optimiser des requêtes fréquentes et lentes.

Une autre possiblité pour faire mieux est de créer un index sur la clé étrangère, ce qui ouvre la possibilité d’effectuer les jointures dans n’importe quel ordre (pour les jointures “naturelles”, celles qui associent clé primaire et clé étrangère). Certains systèmes (MySQL) le fonct d’ailleurs systématiquement.

Si, donc, la table Role est indexée sur la clé primaire (id_acteur, id_film) et sur la clé étrangère id_film (ce n’est pas redondant), un plan d’exécution possible est celui de la figure Le plan d’exécution avec index sur les clés étrangères.

_images/planEx-full3.png

Fig. 6.4 Le plan d’exécution avec index sur les clés étrangères

Ce plan est comparable à celui de la figure Le plan d’exécution “standard”. Lequel des deux serait choisi par le système? En principe, on choisirait comme table de gauche celle qui contient le moins de tuples, pour minimiser le nombre de demandes de lectures adressées à l’index. Mais il se peut d’un autre côté que cette table, tout en contenant moins de tuples, soit beaucoup plus volumineuse et que sa lecture séquentielle soit considérée comme trop pénalisante. Ici, statistiques et évaluation du coût entrent en jeu.

On pourrait finalement créer un index sur l’année sur film pour éviter tout parcours séquentiel: à vous de déterminer le plan d’exécution qui correspond à ce scénario.

Finalement, considérons le cas où aucun index n’est disponible. Pour notre exemple, cela correspondrait à une sévère anomalie puisqu’il manquerait un index sur la clé primaire. Toujours est-il que dans un tel cas le système doit déterminer l’algorithme de jointure sans index qui convient. La figure Le plan d’exécution en l’absence d’index illustre le cas où c’est l’agorithme de tri-fusion qui est choisi.

_images/planEx-full4.png

Fig. 6.5 Le plan d’exécution en l’absence d’index

La présence de l’algorithme de tri-fusion pour une jointure doit alerter sur l’absence d’index et la probable nécessité d’en créer un.

Arbres en profondeur à gauche

Pour conclure cette section sur l’optimisation, on peut généraliser l’approche présentée dans ce qui précède au cas des requêtes multi-jointures, où de plus chaque jointure est “naturelle” et associe la clé primaire d’une table à la clé étrangère de l’autre. Voici un exemple sur notre schéma: on cherche tous les films dans lesquels figure un acteur islandais.

select *
from Film, Role, Artiste, Pays
where Pays.nom='Islande'
and   Film.id=Role.id_film
and   Role.id_acteur=Artiste.id
and   Artiste.pays = Pays.code

Ces requêtes comprenant beaucoup de jointures sont courantes, et le fait qu’elles soient naturelles est également courant, pour des raisons déjà expliquées.

Quel est le plan d’exécution typique? Une stratégie assez standard de l’optimiseur va être d’éviter les opérateurs bloquants et la consommation de mémoire. Cela mène à chercher, le plus systématiquement possible, à appliquer l’opérateur de jointure par boucles imbriquées indexées. Il se trouve que pour les requêtes considérées ici, c’est toujours possible. En fait, on peut représenter ce type de requête par une “chaîne” de jointures naturelles. Ici, on a (en ne considérant pas les sélections):

\[Film \Join Role \Join Artiste \Join Pays\]

Il faut lire au moins une des tables séquentiellement pour “amorcer” la cascade des jointures par boucles imbriquées. Mais, pour toutes les autres tables, un accès par index devient possible. Sur notre exemple, le bon ordre des jointures est

\[Artiste \Join Pays \Join Role \Join Film\]

Le plan d’exécution consistant en une lecture séquentielle suivi de boucles imbriquées indexées est donné sur la figure Le plan d’exécution en l’absence d’index. Il reste bien sûr à le compléter. Mais l’aspect important est que ce plan fonctionne entièrement en mode pipelinage, sans latence pour l’application. Il exploite au maximum la possibilité d’utiliser les index, et minimise la taille de la mémoire nécessaire.

_images/planEx-lefttree.png

Fig. 6.6 Le plan d’exécution en l’absence d’index

Ce plan a la forme caractéristique d’un arbre en profondeur à gauche (“left-deep tree”). C’est celle qui est recherchée classiquement par un optimiseur, et la forme de base que vous devriez retenir comme point de repère pour étudier un plan d’exécution. En présence d’une requête présentant les caractéristiques d’une chaîne de jointure, c’est la forme de référence, dont on ne devrait dévier qe dans des cas explicables par la présence d’index complémentaires, de tables très petites, etc.

Ce plan (le sous-plan de la figure Le plan d’exécution en l’absence d’index) fournit un tuple, et autant d’adresses de tuples qu’il y a de jointures et donc d’accès aux index. Il faut ensuite ajouter autant d’opérateurs DirectAccess, ainsi que les opérateurs de sélection nécessaires (ici sur le nom du pays). Essayez par exemple, à titre d’exercice, de compléter le plan de la figure Le plan d’exécution en l’absence d’index pour qu’il corresponde complètement à la requête.

Quiz

La relation Rôle(id_acteur, id_film, nom_role) a pour clé primaire la paire d’attributs (id_acteur, id_film). Sachant que le système construit un arbre B sur cette clé, lesquelles parmi les requêtes suivantes peuvent utiliser l’index ?

  1. Select * from Rôle where id_acteur = x and id_film=y
  2. Select * from Rôle where id_acteur = x
  3. Select * from Rôle where id_film=y

En déduire pourquoi le bon ordre de jointure entre les tables Film et Rôle est celui exposé en cours.

Dans le plan d’exécution de la Diapositive 5, comment pourrait –on éviter tout parcours séquentiel ?

  1. En créant un index sur la clé étrangère id_film dans Rôle.
  2. En créant un index sur le nom du rôle dans Rôle.
  3. En créant un index sur l’année de Film.

S3: illustration avec ORACLE

Supports complémentaires:

Cette section présente l’application concrète des concepts, structures et algorithmes présentés dans ce qui précède avec le SGBD ORACLE. Ce système est un bon exemple d’un optimiseur sophistiqué s’appuyant sur des structures d’index et des algorithmes d’évaluation complets. Tous les algorithmes de jointure décrits dans ce cours (boucles imbriquées, tri-fusion, hachage, boucles imbriquées indexées) sont en effet implantés dans ORACLE. De plus le système propose des outils simples et pratiques (explain notamment) pour analyser le plan d’exécution choisi par l’optimiseur, et obtenir des statistiques sur les performances (coût en E/S et coût CPU, entre autres).

Paramètres et statistiques

L’optimiseur s’appuie sur des paramètres divers et sur des statistiques. Parmi les plus paramètres les plus intéressants, citons:

  • OPTIMIZER_MODE: permet d’indiquer si le coût considéré est le temps de réponse (temps pour obtenir la première ligne du résultat), FIRST_ROW ou le temps d’exécution total ALL_ROWS.
  • SORT_AREA_SIZE indique la taille de la mémoire affectée à l’opérateur de tri.
  • HASH_AREA_SIZE indique la taille de la mémoire affectée à l’opérateur de hachage.
  • HASH_JOIN_ENABLED indique que l’optimiseur considère les jointures par hachage.

L’administrateur de la base est responsable de la tenue à jour des statistiques. Pour analyser une table on utilise la commande analyze table qui produit la taille de la table (nombre de lignes) et le nombre de blocs utilisés. Cette information est utile par exemple au moment d’une jointure pour utiliser comme table externe la plus petite des deux. Voici un exemple de la commande.

analyze table Film compute statistics for table;

On trouve alors des informations statistiques dans les vues dba\_tables, all_tables, user_tables. Par exemple:

  • NUM_ROWS, le nombre de lignes.
  • BLOCKS, le nombre de blocs.
  • CHAIN_CNT, le nombre de blocs chaînés.
  • AVG_ROW_LEN, la taille moyenne d’une ligne.

On peut également analyser les index d’une table, ou un index en particulier. Voici les deux commandes correspondantes.

analyze table Film compute statistics for all indexes;
analyze index PKFilm compute statistics;

Les informations statistiques sont placées dans les vues dba_index, all_index et user_indexes.

Pour finir on peut calculer des statistiques sur des colonnes. ORACLE utilise des histogrammes en hauteur pour représenter la distribution des valeurs d’un champ. Il est évidemment inutile d’analyser toutes les colonnes. Il faut se contenter des colonnes qui ne sont pas des clés uniques, et qui sont indexées. Voici un exemple de la commande d’analyse pour créer des histogrammes avec vingt groupes sur les colonnes titre et genre.

analyze table Film compute statistics for columns titre, genre size 20;

On peut remplacer compute par estimate pour limiter le coût de l’analyse. ORACLE prend alors un échantillon de la table, en principe représentatif (on sait ce que valent les sondages!). Les informations sont stockées dans les vues dba_tab_col_statistics et dba_part_col_statistics.

Plans d’exécution ORACLE

Nous en arrivons maintenant à la présentation des plans d’exécution d’ORACLE, tels qu’ils sont donnés par l’utilitaire explain. Ces plans ont classiquement la forme d’arbres en profondeur à gauche (voir la section précédente), chaque nœud étant un opérateur, les nœuds-feuille représentant les accès aux structures de la base, tables, index, cluster, etc.

Le vocabulaire de l’optimiseur pour désigner les opérateurs est un peu différent de celui utilisé jusqu’ici dans ce chapitre. La liste ci-dessous donne les principaux, en commençant par les chemins d’accès, puis les algorithmes de jointure, et enfin des opérations diverses de manipulation d’enregistrements.

  • FULL TABLE SCAN, notre opérateur FullScan.
  • ACCESS BY ROWID, notre opérateur DirectAccess.
  • INDEX SCAN, notre opérateur IndexScan.
  • NESTED LOOP, notre opérateur INL de boucles imbriquées indexées, utilisé quand il y a au moins un index.
  • SORT/MERGE, algorithme de tri-fusion.
  • HASH JOIN, jointure par hachage.
  • INTERSECTION, intersection de deux ensembles d’enregistrements.
  • CONCATENATION, union de deux ensembles.
  • FILTER, élimination d’enregistrements (utilisé dans un négation).
  • select, opération de projection (et oui ...).

Voici un petit échantillon de requêtes sur notre base en donnant à chaque fois le plan d’exécution choisi par ORACLE. Les plans sont obtenus en préfixant la requête à analyser par explain plan accompagné de l’identifiant à donner au plan d’exécution. La description du plan d’exécution est alors stockée dans une table utilitaire et le plan peut être affiché de différentes manières. Nous donnons la représentation la plus courante, dans laquelle l’arborescence est codée par l’indentation des lignes.

La première requête est une sélection sur un attribut non indexé.

explain plan
set statement_id='SelSansInd' for
select *
from Film
where titre = 'Vertigo'

On obtient le plan d’exécution nommé SelSansInd dont l’affichage est donné ci-dessous.

0 SELECT STATEMENT
  1 TABLE ACCESS FULL FILM

ORACLE effectue donc un balayage complet de la table Film. L’affichage représente l’arborescence du plan d’exécution par une indentation. Pour plus de clarté, nous donnons également l’arbre complet (figure Plan ORACLE pour une requête sans index) avec les conventions utilisées jusqu’à présent.

_images/planOra-selsansind.png

Fig. 6.7 Plan ORACLE pour une requête sans index

Le plan est trivial. L’opérateur de parcours séquentiel extrait un à un les enregistrements de la table Film. Un filtre (jamais montré dans les plans donnés par explain, car intégré aux opérateurs d’accès aux données) élimine tous ceux dont le titre n’est pas Vertigo. Pour ceux qui passent le filtre, un opérateur de projection (malencontreusement nommé select dans ORACLE ...) ne conserve que les champs non désirés.

Voici maintenant une sélection avec index sur la table Film.

explain plan
set statement_id='SelInd' for
select *
from Film
where id=21;

Le plan d’exécution obtenu est:

0 SELECT STATEMENT
 1 TABLE ACCESS BY ROWID FILM
  2 INDEX UNIQUE SCAN IDX-FILM-ID

L’optimiseur a détecté la présence d’un index unique sur la table Film. La traversée de cet index donne un ROWID qui est ensuite utilisé pour un accès direct à la table (figure Plan ORACLE pour une requête avec index).

_images/planOra-selind.png

Fig. 6.8 Plan ORACLE pour une requête avec index

Passons maintenant aux jointures. La requête donne les titres des films avec les nom et prénom de leur metteur en scène, ce qui implique une jointure entre Film et Artiste.

explain plan
set statement_id='JoinIndex' for
select titre, nom, prenom
from   Film f, Artiste a
where f.id_realisateur = a.id;

Le plan d’exécution obtenu est le suivant: il s’agit d’une jointure par boucles imbriquées indexées.

0 SELECT STATEMENT
  1 NESTED LOOPS
    2 TABLE ACCESS FULL FILM
    3 TABLE ACCESS BY ROWID ARTISTE
      4 INDEX UNIQUE SCAN IDXARTISTE

Vous devriez pour décrypter ce plan est le reconnaître: c’est celui, discuté assez longuement déjà, de la jointure imbriquée indexée. Pour mémoire, il correspond à cette figure du chapitre Opérateurs et algorithmes.

_images/planEx-indexedjoin.png

Fig. 6.9 Plan ORACLE pour une requête avec index

Ré-expliquons une dernière fois. Tout d’abord la table qui n’est pas indexée sur l’attribut de jointure (ici, Film) est parcourue séquentiellement. Le nœud IndexJoin (appelé NESTED LOOPS par ORACLE) récupère les enregistrements film un par un du côté gauche. Pour chaque film on va alors récupérer l’artiste correspondant avec le sous-arbre du côté droit.

On efffectue alors une recherche par clé dans l’index avec la valeur id_realisateur provenant du film courant. La recherche renvoie un ROWID qui est utilisé pour prendre l’enregistrement complet dans la table Artiste.

Dans certains cas on peut éviter le parcours séquentiel à gauche de la jointure par boucles imbriquées, si une sélection supplémentaire sur un attribut indexé est exprimée. L’exemple ci-dessous sélectionne tous les rôles jouées par Al Pacino, et suppose qu’il existe un index sur les noms des artistes qui permet d’optimiser la recherche par nom. L’index sur la table Rôle est la concaténation des champs id_acteur et id_film, ce qui permet de faire une recherche par intervalle sur le préfixe constitué seulement de id_acteur. La requête est donnée ci-dessous.

explain plan
set statement_id='JoinSelIndex' for
select nom_role
from   Role r, Artiste a
where  r.id_acteur = a.id
and    nom = 'Pacino';

Et voici le plan d’exécution.

0 SELECT STATEMENT
  1 NESTED LOOPS
    2 TABLE ACCESS BY ROWID ARTISTE
      3 INDEX RANGE SCAN IDX-NOM
    4 TABLE ACCESS BY ROWID ROLE
      5 INDEX RANGE SCAN IDX-ROLE

Notez bien que les deux recherches dans les index s’effectuent par intervalle (INDEX RANGE), et peuvent donc ramener plusieurs ROWID. Dans les deux cas on utilise en effet seulement une partie des champs définissant l’index (et cette partie constitue un préfixe, ce qui est impératif). On peut donc envisager de trouver plusieurs artistes nommé Pacino (avec des prénoms différents), et pour un artiste, on peut trouver plusieurs rôles (mais pas pour le même film). Tout cela résulte de la conception de la base.

_images/planOra-joinselindex.png

Fig. 6.10 Plan ORACLE pour une jointure et sélection avec index

Pour finir voici une requête sans index. On veut trouver tous les artistes nés l’année de parution de Vertigo (et pourquoi pas?). La requête est donnée ci-dessous: elle effectue une jointure sur les années de parution des films et l’année de naissance des artistes.

explain plan set
statement_id='JoinSansIndex' for
select nom, prenom
from Film f, Artiste a
where f.annee  = a.annee_naissance
and   titre = 'Vertigo';

Comme il n’existe pas d’index sur ces champs, ORACLE applique un algorithme de tri-fusion, et on obtient le plan d’exécution suivant.

0 SELECT STATEMENT
  1 MERGE JOIN
    2 SORT JOIN
      3 TABLE ACCESS FULL ARTISTE
    4 SORT JOIN
      5 TABLE ACCESS FULL FILM

L’arbre de la figure Plan ORACLE pour une jointure sans index montre bien les deux tris, suivis de la fusion. Au moment du parcours séquentiel, on va filtrer tous les films dont le titre n’est pas Vertigo, ce qui va certainement beaucoup simplifier le calcul de ce côté-là. En revanche le tri des artistes risque d’être beaucoup plus coûteux.

_images/planOra-joinsansindex.png

Fig. 6.11 Plan ORACLE pour une jointure sans index

Dans un cas comme celui-là, on peut envisager de créer un index sur les années de parution ou sur les années de naissance. Un seul index suffira, puisqu’il devient alors possible d’effectuer une jointure par boucles imbriquées.

Outre l’absence d’index, il existe de nombreuses raisons pour qu’ORACLE ne puisse pas utiliser un index: par exemple quand on applique une fonction au moment de la comparaison. Il faut être attentif à ce genre de détail, et utiliser explain pour vérifier le plan d’exécution quand une requête s’exécute sur un temps anormalement long.