Précédent Remonter Suivant

Chapitre 9  Optimisation de Requêtes

Exercice A :
Soit la base STATION DE SKI de schéma: 
hotel (noms,nomh,categorie,adresse,tel,nb_chambres)
station (noms,gare)
activite (type_activite,noms)
Pour chacune des requêtes suivantes, on demande:
  1. l'arbre syntaxique de la requête
  2. le plan d'exécution obtenu par la restructuration algébrique
  3. le plan d'exécution obtenu par une optimisation globale.
Requête 1 :
adresse, numéro de téléphone et nombre de chambres des hôtels de catégorie 3' dans la station de nom (noms 'persey'. 
SELECT adresse, tel, nb_chambres
FROM hotel
WHERE noms='pesey' AND categorie=3;
(1) arbre syntaxique de la requête : Figure 9.1


(2) restructuration algébrique : Les principes qu'il faut prendre en compte pour la restructuration algébrique sont les suivants:
  1. évaluer les sélections (ou restrictions) le plus tôt possible. En effet, la relation qu'on obtient par l'évaluation de sélections est plus petite que la relation initiale.
  2. faire des projections pour réduire la taille de la relation en question.
  3. permuter les jointures. En principe (R S ) T = R ( S T) si et seulement si, l'attribut commun est le même pour les trois relations.
Pour la requête ci-dessus, aucune restructuration algébrique n'est nécessaire.


(3) optimisation globale : Pour trouver le plan d'exécution ``optimal'', il faut estimer le coût d'E/S pour chaque opération algébrique.

Pour évaluer la sélection (noms='pesey' AND catégorie=3), plusieurs stratégies existent: utiliser les index existants de la relation ``hotel'' ou balayage séquentiel de cette relation. L'utilisation de l'index permet d'avoir un accès direct aux tuples de la relation qui satisfont le prédicat de sélection.
balayage séquentiel :
on parcourt séquentiellement la relation: on lit en MC chaque page de la relation en séquence, on lit en séquence les tuples de la page courante on évalue le prédicat en Mémoire Centrale (MC). Le coût en E/S de l'évaluation de la sélection est le coût de lecture de la relation en MC (dans la suite de l'exercice on ne compte pas le cout d'écriture du résultat sur le disque qui est le même quelle que soit la stratégie.
cout(selection) = nombre  pages  de  la  relation hotel  =  1000
.

index non dense sur noms :
On utilise l'index pour trouver et lire en MC la page qui contient les tuples qui satisfont la contrainte (noms='pesey'). Le pr'edicat (les contraintes noms = 'pesey' et catégorie=3 sont vérifiées sur tous les tuples de la page. Le coût de la sélection est estimé par la formule:
Selectivite_predicat_de_la_cle × (NPI(hotel) + NPR(hotel)) (1)
  • Sélectivité_prédicat_de_la_clé (noms);
  • NPI (hotel) est le nombre des pages feuilles de l'index plaçant de la relation hôtel;
  • NPR(hotel) est le nombre de pages de la relation hôtel.

La sélectivité du prédicat (noms='pesey') est calcule par la formule:
Selectivite_predicat_sur_cle = 1/(nb valeurs differentes;de la cle (noms))
Pour la requête donnée, on n'a pas directement l'information sur le nombre de valeurs différentes de noms, mais on peut l'obtenir à partir de la relation station. En effet noms est le clé primaire de la relation station, et le nombre de valeurs différentes est 1000 (le nombre de tuples de la relation station). Alors comme on a une contrainte référentielle pour l'attribut noms de la relation hôtel, le nombre de valeurs différentes de ce attribut pour hôtel est au maximum 1000. Donc, la sélectivité du prédicat sur noms est 1/1000 = 0.001
A partir de la formule (1), le coût d'E/S est 0.001 × (26 + 1000) = 1.026 E/S (accès direct).
index dense sur catégorie:
Le coût de l'évaluation du prédicat dans ce cas est calculé par la formule:
Selectivite_predicat_de_la_cle × (NPI(hotel) + NPT(hotel))
  • Sélectivité_prédicat_de_la_clé (catégorie);
  • NPI est le nombre des pages feuilles de l'index non plaçant de la relation hôtel;
  • NPT(R) est le nombre de tuples de la relation hôtel.
La sélectivité du prédicat (catégorie=3') est estimée par la formule:
Selectivite_predicat_sur_cle = 1/(nb valeurs differentes de la cle (categorie))

Pour la requête donnée, la sélectivité du prédicat sur l'attribut catégorie est 1/5. Donc, le coût d'évaluation de la sélection est : 1/5 × (33 + 10000) = 2007 E/S. Le coût est trop élevé (l'index n'a aucun intérêt car le nombre de catégories différentes est trop faible).


Requête 2 :
nom de station (noms) et la gare de la station pour le sstations ayant pour activité le tennis.


SELECT noms, gare
FROM station, activite
WHERE type_activite = ``tennis''
AND station.noms=activite.noms
arbre syntaxique de la requête: Figure 9.1


restructuration algébrique : Figure 9.1


optimisation globale : Pour choisir le plan d'exécution le meilleur, il faut estimer le coût d'E/S minimum pour chacun des opérations algébriques et choisir le moins cher. Le coût de cette requête est:
cout(requete) = cout(evaluation_predicat_restriction) + cout(evaluation_jointure)
  • coût(évaluation_prédicat_restriction) :
    balayage séquentiel :
    Le coût d'évaluation de la restriction est égal au nombre pages de la relation activité = 300.
    index dense sur type_activité :
    Le coût d'E/S est estimé par:
    Selectivite_predicat_de_la_cle × (NPI(hotel) + NPT(hotel))

    Pour la requête donnée, la sélectivité du prédicat sur l'attribut type_activité est 1/(nb différentes de valeurs de type_activité) = 1/40. Alors, le coût d'évaluation de la sélection est : 1/40 × (10 + 3000) = 76 E/S. La relation obtenue n'est pas dans l'ordre de noms.


  • coût(évaluation_jointure) : Pour l'évaluation de jointure il existe plusieurs algorithmes qu'on peut utiliser: (a) boucles imbriquées, (b) tri-fusion. Pour calculer le coût de la jointure il faut d'abord calculer la taille de la relation Temp (Figure 9.1). La taille d'une relation après avoir évalué le prédicat de la sélection est donné par la formule :
    Selectivite  du  predicat restriction  × NPT(R)
    La sélectivité du prédicat type_activité = 'tennis' est 1/40, alors le nombre des tuples lus en MC (taille de la relation Temp) est 1/40 × 3000 = 75 tuples. Comme la relation Temp est constituée d'un seul attribut (noms), alors on peut considérer qu' elle tient dans 1 ou au plus 2 pages.
    boucles imbriquées :
    Le coût de l'évaluation de la jointure est :
    cout(station Temp) = {
    {
    {
    {
    {
    {
    {
    {
    NBPstation + lceil NBPstation/b rceil × NBPTemp,
    si station est  la  petite  relation
    NBPTemp + lceil NBPTemp/b rceil × NBPstation,
    si  Temp  est  la  petite  relation
    NBPTemp + NBPstation,
    si  une  de  deux  relations  tient  en  MC

    Dans notre cas, la relation Temp tient en MC (2 pages au maximum) alors le coût(station semijoin Temp) = NBPTemp + NBPstation = 2 + 100 = 102 E/S. Dans le cas où Temp est déjà en MC (après l'évaluation de la sélection et de la projection), le coût(station semijoin Temp) = NBPstation = 100 E/S.

    tri-fusion :


    Le coût d'évaluation de la jointure est :
    cout(station semijoin Temp) = NBPstation + NBPTemp + cout(tri_station) + cout(tri_Temp)
./figures/q12_arbre_syntaxique.eps
Figure 9.1 : Arbres Syntaxique et Restructuration Algébrique pour les requêtes (1) et (2)


Exercice B :
Soit le schéma suivant: 
    CREATE TABLE FILM (                 CREATE TABLE VU (                     
           TITRE   VARCHAR2(32),               SPECTATEUR      VARCHAR2(32), 
           REALISATEUR VARCHAR2(32),           TITRE           VARCHAR2(32)  
           ACTEUR VARCHAR2(32)         );                                    
    );
Soit la requête SQL: 
               SELECT ACTEUR, REALISATEUR
                 FROM FILM, VU
                WHERE FILM.TITRE=VU.TITRE
Dans chacun des cas suivants, donner l'algorithme de jointure de ORACLE (par EXPLAIN, un arbre d'exécution commenté, une explication textuelle ou tout autre moyen de votre choix):
  1. Il n'existe pas d'index sur TITRE ni dans FILM ni dans VU, Tri-fusion (voir cours): Figure 9.2 et plan d'exécution Oracle.
    fi-optim1.ps
    Figure 9.2 : Plan d'exécution

    Plan d'exécution
------------------------------------------------------------------------
0 SELECT STATEMENT
  1 MERGE JOIN
    2 SORT JOIN
      3 TABLE ACCESS FULL VU
    4 SORT JOIN
      5 TABLE ACCESS FULL FILM
  2. Il existe un index sur TITRE dans FILM seulement. La table VU est prise comme table directrice: pour chaque titre dans VU parcouru séquentiellement, on cherche à travers l'index le ROWID s'il existe d'un nuplet de FILM et on fait la jointure (comme la relation FILM n'est pas normalisée, il y a plusieurs nuplets de même titre) (Figure 9.3).
    fi-optim2.ps
    Figure 9.3 : Plan d'exécution

    CREATE INDEX FILM_TITRE_idx on FILM (TITRE);

Plan d'exécution
------------------------------------------------------------------------
0 SELECT STATEMENT
  1 NESTED LOOPS
    2 TABLE ACCESS FULL VU
    3 TABLE ACCESS BY ROWID FILM
      4 INDEX RANGE SCAN FILM_TITRE_IDX
  3. Il existe un index sur TITRE dans les deux relations. idem (l'optimiseur choisit la dernière table comme table directrice de la clause FROM quand il existe un index sur la colonne de jointure dans les deux tables) 
    CREATE INDEX FILM_TITRE_idx on FILM (TITRE);
CREATE INDEX VU_TITRE_idx on VU (TITRE);

Plan d'exécution
-----------------------------------------------------------------------
0 SELECT STATEMENT
  1 NESTED LOOPS
    2 TABLE ACCESS FULL VU
    3 TABLE ACCESS BY ROWID FILM
      4 INDEX RANGE SCAN FILM_TITRE_IDX


Exercice C :
Soit la requête : 
    SELECT  e.enom, d.dnom
    FROM    emp e, dept d
    WHERE   e.dno = d.dno
    AND     e.sal = 10000
sur la relation EMP de schéma (EMPNO, SAL, MGR, DNO). Cette requête affiche le nom des employés dont le salaire (SAL) est égal à 10000, et celui de leur département. Indiquez le plan d'exécution dans chacune des hypothèses suivantes.
  1. Index sur DEPT(Dno) et sur EMP(Sal) Figure 9.4.
    fi-optim3.ps
    Figure 9.4 : Plan d'exécution

    Plan d'execution
--------------------------------------------------------------------------
0 SELECT STATEMENT
  1 NESTED LOOPS
    2 TABLE ACCESS BY ROWID EMP
      3 INDEX RANGE SCAN EMP_SAL
    4 TABLE ACCESS BY ROWID DEPT
      5 INDEX UNIQUE SCAN DEPT_DNO
    Boucles imbriquées (NESTED LOOP) : on choisit de parcourir un sous-ensemble de EMP en utilisant l'index, puis on accède a DEPT avec l'index sur DEPTNO.
  2. Index sur EMP(Sal) seulement. Figure 9.5.
    fi-optim8.ps
    Figure 9.5 : Plan d'exécution

    Plan d'execution
--------------------------------------------------------------------------
0 SELECT STATEMENT
  1 NESTED LOOPS
    2 TABLE ACCESS FULL DEPT
    3 TABLE ACCESS BY ROWID EMP
      4 INDEX RANGE SCAN EMP_SAL
    Algorithme de SCAN-INDEX. Equivalent à une jointure par NESTED-LOOP brutal. On pourrait (i) changer l'ordre des tables sans modifier la complexité, et (ii) faire un tri-fusion.
  3. Index sur EMP(Dno) et sur EMP(Sal) Figure 9.6.
    fi-optim4.ps
    Figure 9.6 : Plan d'exécution

    Plan d'execution
--------------------------------------------------------------------------
0 SELECT STATEMENT
  1 NESTED LOOPS
    2 TABLE ACCESS FULL DEPT
    3 TABLE ACCESS BY ROWID EMP
      4 AND-EQUAL
        5 INDEX RANGE SCAN EMP_DNO
        6 INDEX RANGE SCAN EMP_SAL
    Comme l'index sur EMP(DNO) n'est pas unique, on a intérêt à limiter la liste des adresses de tuples en utilisant les deux index et en faisant l'intersection.
  4. Voici une autre requête, légèrement différente. Plan d'exécution s'il n'y a pas d'index. 
        SELECT e.enom
    FROM emp e, dept d
    WHERE  e.dno = d.dno
    AND    d.ville = 'Paris'
    
    Plan d'execution
--------------------------------------------------------------------------
0 SELECT STATEMENT
  1 MERGE JOIN
    2 SORT JOIN
      3 TABLE ACCESS FULL DEPT
    4 SORT JOIN
      5 TABLE ACCESS FULL EMP
    Algorithme de tri-fusion classique.
  5. Que pensez-vous de la requête suivante par rapport à la précédente ? 
        SELECT e.enom
    FROM emp e
    WHERE  e.dno IN (SELECT d.dno
                        FROM Dept d
                        WHERE d.Ville = 'Paris')
    Voici le plan d'exécution donné par ORACLE : 
    0 SELECT STATEMENT
  1 MERGE JOIN
    2 SORT JOIN
      3 TABLE ACCESS FULL EMP
    4 SORT JOIN
      5 VIEW
        6 SORT UNIQUE
          7 TABLE ACCESS FULL DEPT
    Qu'en dites vous ? Création d'une table temporaire (VIEW) contenant les numéros des départements à Paris. On a éliminé les doublons (SORT UNIQUE). Ensuite on fait un tri-fusion. Donc exécution différente pour une requête équivalente.
Exercice D :
Sur le même schéma, voici maintenant la requête suivante. 
  SELECT * 
  FROM EMP X WHERE X.SAL IN (SELECT SAL 
                               FROM EMP
                              WHERE EMP.EMPNO=X.MGR)
Cette requête cherche les employés dont le salaire (SAL) est égal à celui de leur patron (MGR). On donne le plan d'exécution avec Oracle (outil EXPLAIN) pour cette requête dans deux cas: (i) pas d'index, (ii) un index sur le salaire et un index sur le numéro d'employé. Expliquez dans les deux cas ce plan d'exécution (éventuellement en vous aidant d'une représentation arborescente de ce plan d'exécution).
  1. Pas d'index. 
    Plan d'exécution
------------------------------------------------------------------------
0 FILTER
  1 TABLE ACCESS FULL EMP
  2 TABLE ACCESS FULL EMP
    Figure 9.7.
    fi-optim6.ps
    Figure 9.7 : Plan d'exécution

    Boucles imbriquées (FILTER) : On parcourt la table EMP (ligne 2); pour chaque employé, on regarde le salaire SAL et le numéro du patron MGR; on parcourt alors la table EMP (ligne 3) pour trouver l'employé dont le numéro est MGR et on compare le salaire à SAL. Donc c'est une boucle imbriquée brutale : on aurait pu faire un tri-fusion.
  2. Index empno et index sal. 
    Plan d'exécution
------------------------------------------------------------------------
0 FILTER
  1 TABLE ACCESS FULL EMP
  2 AND-EQUAL
    3 INDEX RANGE SCAN I-EMPNO 
    4 INDEX RANGE SCAN I-SAL
    Figure 9.8.
    fi-optim7.ps
    Figure 9.8 : Plan d'exécution

    Boucles imbriquées (FILTER) : on parcourt la table EMP (ligne 2). Pour chaque employé, le salaire SAL et le numéro EMPNO, valeur de l'attribut MGR servent de clé pour accéder à l'index (lignes 4 et 5). L'intersection des listes de row-id (ligne 3) obtenues par les étapes 4 et 5 donne si elle est non vide un row-id de patron ayant même salaire que l'employé
  3. Dans le cas où il y a les deux index (salaire et numéro d'employé) et où la requête est : 
    SELECT * 
  FROM EMP X 
 WHERE X.SAL = (SELECT SAL 
                  FROM EMP
                 WHERE EMP.EMPNO=X.MGR)
    on a le plan d'exécution suivant: 
    Plan d'exécution
------------------------------------------------------------------------
0 FILTER
  1 TABLE ACCESS FULL EMP
  2 TABLE ACCESS ROWID EMP 
    3 INDEX RANGE SCAN I-EMPNO
    Expliquez-le. Dans ce cas, seul l'index sur les numéros d'employés est utilisé. Boucles imbriquées (FILTER); on parcourt la table EMP: pour chaque employé, l'attribut MGR donne le numéro d'employé de son patron. On accède à son patron par l'index sur les numéros d'employé (lignes 4 puis 3): on vérifie alors si son salaire est égal à celui de l'employé.


Exercice E :
On reprend le schéma CINEMA donné dans le cours, mais on ne sais plus quels index existent.

Questions:
  1. Donner l'ordre SQL pour la requête: Quels sont les films d'Hitchcock visibles après 20h00 ? 
          SELECT F.TITRE
        FROM SEANCE S, FILM F, ARTISTE A
       WHERE A.NOM = 'Hitchcock'
         AND F.ID-REALISATEUR = A.ID-REALISATEUR
         AND S.ID-FILM = F.ID-FILM
         AND S.HEURE_DEBUT > '20:00'
  2. Donner l'expression algébrique correspondante et proposez un arbre de requête qui vous paraît optimal. sigmaHEURE_DEBUT > '20:00' SEANCE (sigmaNOM='Hitchcock' ARTISTEID-Artiste=ID-Realisateur FILM)
  3. Sous ORACLE, l'outil EXPLAIN donne le plan d'exécution suivant: 
    0 SELECT STATEMENT
  1 MERGE JOIN
    2 SORT JOIN
      3 NESTED LOOPS
        4 TABLE ACCESS FULL ARTISTE
        5 TABLE ACCESS BY ROWID FILM
          6 INDEX RANGE SCAN IDX-ARTISTE-ID
    7 SORT JOIN
     8 TABLE ACCESS FULL SEANCE
    Commentez le plan donné par EXPLAIN. Pourrait-on améliorer les performances de cette requête? L'existence d'un tri-fusion indique qu'il manque un index. Ici on peut résoudre le pb en créant un index sur SEANCE(id-Film).
Exercice F :
Soit le schéma suivant:
CREATE TABLE Artiste (                CREATE TABLE Film (                 
       ID-artiste     NUMBER(4),             ID-film        NUMBER(4),    
       Nom            VARCHAR2(32),          Titre          VARCHAR2(32), 
       Adresse        VARCHAR2(32)           Année          NUMBER(4),    
);                                           ID-réalisateur NUMBER(4)     
                                      );                                  

CREATE TABLE Joue (
       ID-artiste     NUMBER(4),
       ID-film        NUMBER(4)
);
Questions:
  1. Donner l'ordre SQL pour la requête: Afficher le nom des acteurs et le titre des films où ils ont joué.

  2. Donner l'expression algébrique correspondante.
  3. Quel est à votre avis le plan d'exécution dans s'il n'existe que deux index, un sur FILM(ID-réalisateur), et un sur ARTISTE(ID-artiste)¸?
  4. Idem, avec un index sur FILM(ID-Film), et un sur JOUE(ID-Artiste).
  5. Idem, avec un index sur FILM(ID-Film), et un sur JOUE(ID-Film). 
  1.    SELECT nom, titre
   FROM   artiste, film, joue
   WHERE  artiste.ID-artiste = joue.ID-artiste
   AND    film.ID-film = joue.ID-film
  2. Artiste (Film Joue)) 
  3. 0 SELECT STATEMENT
  1 MERGE JOIN
    2 SORT JOIN
      3 NESTED LOOPS
        4 TABLE ACCESS FULL JOUE
        5 TABLE ACCESS BY ROWID ARTISTE
          6 INDEX UNIQUE SCAN ARTISTE_IDX
    7 SORT JOIN
      8 TABLE ACCESS FULL FILM
    Comme il n'y a qu'un seul index utilisable, on fait un parcours séquentiel sur Joue pour utiliser l'index le plus tôt possible, puis on fait un tri fusion. On peut aussi faire le parcours séquentiel initial sur Film. Petit piège : l'index sur ID_réalisateur n'est pas utilisable pour la jointure. 
  4. 0 SELECT STATEMENT
  1 NESTED LOOPS
    2 NESTED LOOPS
      3 TABLE ACCESS FULL ARTISTE
      4 TABLE ACCESS BY ROWID JOUE
        5 INDEX RANGE SCAN JOUE_ARTISTE
    6 TABLE ACCESS BY ROWID FILM
      7 INDEX UNIQUE SCAN FILM_IDX
    Comme il y a une seule table (ARTISTE) sans index propre à la jointure, on la choisit pour effectuer le parcours séquentiel initial. 
  5. 0 SELECT STATEMENT
  1 MERGE JOIN
    2 SORT JOIN
      3 NESTED LOOPS
        4 TABLE ACCESS FULL JOUE
        5 TABLE ACCESS BY ROWID FILM
          6 INDEX UNIQUE SCAN FILM_IDX
    7 SORT JOIN
      8 TABLE ACCESS FULL ARTISTE
    Les index existant ne peuvent servir qu'à une seule jointure : celle entre JOUE et FILM. Donc il ne reste que la solution de faire un TRI-FUSION pour la jointure avec ARTISTE. NB : on parcours JOUE puis on accède à FILM par l'index. On pourrait faire le contraire (parcourir FILM et accéder à JOUE). Quand il a des statistiques, le SGBD choisit la plus petite des tables pour le parcours séquentiel.

Précédent Remonter Suivant