Skip to content

1 4 4 4 complement

SQL, langage algébrique 4/4 : compléments : évaluation et optimisation

Note
Pour la formation NSI, cette partie est optionnelle, car elle n'est pas au programme. Laissée ici pour ceux et celles qui veulent en savoir plus mais pas d'évaluation sur ce sujet.

Ce complément introduit la manière dont un SGBD analyse, optimise et exécute une requête. Il est présenté dans le but de vous donner un aperçu de l'utilité de l'algèbre dans un contexte d'exécution de requêtes, mais ne fait pas partie du contenu du cours soumis à examen.

Supports complémentaires

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.

Nous avons une requête, exprimée en SQL, soumise au système. Comme vous le savez, SQL permet de déclarer un besoin, mais ne dit pas comment calculer le résultat. C'est au système de produire une forme opératoire, un programme, pour effectuer ce calcul. Notez que cette approche a un double avantage. Pour l'utilisateur, elle permet de ne pas se soucier d'algorithmique d'exécution. Pour le système elle laisse la liberté du choix de la meilleure méthode. C'est ce qui fonde l'optimisation, la liberté de déterminer la manière de répondre à un besoin.

figure17

Fig. 17 Les requêtes SQL sont déclaratives

En base de données, le programme qui évalue une requête a une forme très particulière. On l'appelle plan d'exécution. Il a la forme d'un arbre constitué d'opérateurs qui échangent des données. Chaque opérateur effectue une tâche précise et restreinte : transformation, filtrage, combinaisons diverses. Comme nous le verrons, un petit nombre d'opérateurs suffit à évaluer des requêtes, même très complexes. Cela permet au système de construire très rapidement, à la volée, un plan et de commencer à l'exécuter. La question suivante est d'étudier comment le système passe de la requête au plan.

figure18

Fig. 18 De la requête SQL au plan d'exécution.

Le passage de SQL à un plan s'effectue en deux étapes, que j'appellerai a et b. Dans l'étape a on tire partie de l'équivalence entre SQL, ou une grande partie de SQL, avec l'algèbre. Pour toute requête on peut donc produire une expression de l'algèbre. Et ici on trouve déjà une forme opérationnelle, qui nous dit quelles opérations effectuer. Nous l'appellerons plan d'execution logique. Une expression de l'algèbre peut se représenter comme un arbre, et nous sommes déjà proche d'un plan d'exécution. Il reste assez abstrait.

figure19

Fig. 19 Les deux phases de l'optimisation

Ce n'est pas tout à fait suffisant. Dans l'étape b le système va choisir des opérateurs particuliers, en fonction d'un contexte spécifique. Ce peut être la présence ou non d'index, la taille des tables, la mémoire disponible. Cette étape b donne un plan d'exécution physique, applicable au contexte.

Reste la question de l'optimisation. Il faut ici élargir le schéma : à chaque étape, a ou b, plusieurs options sont possibles. Pour l'étape a, c'est la possibilité d'obtenir plusieurs expressions équivalentes. La figure montre par exemple deux combinaisons possibles issues de la même requête sql. Pour l'étape b,les options sont liées au choix de l'algorithmique, des opérateurs à exécuter.

figure20

Fig. 20 Processus général d'optimisation et d'évaluation

Cette figure nous donne la perspective générale de cette partie du cours. Nous allons étudier les opérateurs, les plans d'exécution, les transformations depuis une requête SQL, et quelques critères de choix pour l'optimisation.