TME Optimisation des requêtes avec jointures

L'objectif de ce TME est de trouver le plan d'exécution optimal pour traiter une requête contenant des jointures. Ce TME met en pratique les notions du cours sur l'optimisation de requêtes: plan d'exécution, espace de recherche, ordonnancement des jointures, modèle de coût, algorithme de jointure.

Sujet

Documentation

Installation des fichiers du TME

Préparation

Introduction

Dans la suite du TME, nous mesurons le coût d'une requête en nombre de lectures de blocs mémoire. C'est le nombre de consistent gets qui apparait dans les statistiques d'exécution d'une requête.

Un plan d'exécution est affiché de manière arborescente. Chaque noeud de l'arbre est un opérateur. Un opérateur a un numéro de noeud et un nom. Les noms des opérateurs sont indentés pour montrer l'arbre d'exécution : le noeud parent est celui dont le nom est décalé d'un caractère à gauche.

  0  SELECT
  1   NESTED LOOPS
  2    TABLE ACCESS
  3    TABLE ACCESS
 3  TABLE ACCESS (BY INDEX ROWID) OF 'C'
 4   INDEX (RANGE SCAN) OF 'I_C_DIVISION' (NON-UNIQUE)

Les opérateurs implémentés par le moteur de requêtes sont :

nom algorithme
nested loops jointure par boucles imbriquées
merge join jointure par fusion
hash join jointure avec hachage temporaire des tuples
sort (join) tri préliminaire avant jointure par fusion
table access full lecture séquentielle d'une relation
table access by rowid lecture non séquentielle d'une relation (un accès par tuple)
index (range scan) traversée d'un index (arbre B+)

IMPORTANT

Dans la suite de ce TME on demande au SGBD ne réaliser des jointures par boucles imbriquées (Nested Loop Join : voir diapo 13 du cours).
Ajouter la directive USE_NL(x,y,z,...) dans toutes les requêtes (x,y,z sont les tables qu'on veut joindre par boucles imbriquées, ici x=C, y=J, z=F)

Question 1 : Plan d'exécution choisi par l'optimiseur

1.1) Représenter l'arbre du plan d'exécution P choisi par défaut par l'optimiseur pour traiter la requête R?

1.2) Mesurer le coût du plan P (cf. Annexe1).

Question 2: Ordonancement des jointures

L'objectif est de trouver l'ordre optimal pour traiter les jointures.

2.1) Quelles relations de la BD peuvent être jointes avec J par jointure ? Même question pour C et F. Combien y a-t-il d'ordres de jointure différents pour traiter la requête R ?

2.2) En utilisant la directive /*+ use_nl(c,j,f) ordered */, construire un plan d'exécution pour chaque ordre de jointure. L'ordre est celui de la clause FROM (l'ordre est indépendant de l'ordre des prédicats de la clause where, ou de l'odre des paramêtres de la fonction use_nl !). Pour chaque plan, préciser clairement les index utilisés, et mesurer le coût du plan. Lire l'Annexe2 expliquant la directive ordered.

2.3) Quels sont les 3 plans de plus faible coût ? Comparer leur coût avec celui du plan P choisi par l'optimiseur ?

Question 3 : Coût des sélections

On veut connaitre le coût des sélections utilisées dans la requête R. Pour cela, on mesure le coût des sélections avec et sans index.

3.1) Quels sont les noms des index existants pour les relations J, C et F ?

3.2) Pour chaque requête de sélection pouvant servir à traiter la requête R, donner son expression SQL et son coût avec et sans index. Pour empêcher un accès par index, utiliser la directive /*+ no_index(nom_relation nom_index) */ (voir l'Annexe2). Donner aussi la cardinalité (nb de n-uplets) du résultat de la sélection.

num sélection SQL coût avec index coût sans index cardinal.
S1 sel(J, salaire > 59000 et sport = 'sport1')
S2 sel(C, division=1)

3.3) Pour les sélections S1, S2 l'accès par index est-il avantageux ? Expliquer pourquoi.

3.4) On veut traiter R en commençant par la sélection la moins couteuse (entre S1 et S2). Donner le plan de la requête R, qui utilise la sélection la moins couteuse? Est-ce le plan optimal ?

Question 4

(question supprimée)

Question 5 : Optimisation basée sur un modèle de coût

5.1) Ajouter dans le dictionnaire du SGBD les statistiques sur J, C et F et les index associés.

5.2) Lorsque le dictionnaire du SGBD contient des statistiques sur les données lues par la requête, l'optimiseur d'Oracle peut estimer plus précisément le coût des opérations d'un plan d'exécution. Cela lui permet de déterminer si un accès par index est intéressant ou non. Modifier le prédicat de sélection du salaire dans la requête R (incrémenter de 100 en 100, la valeur 59000) jusqu'à ce que le SGBD utilise l'index. On note R' la requête obtenue.

5.3) Supprimer les statistiques, la commande est :

Le plan choisi par l'optimiseur pour traiter R est-il le même avec et sans statistiques sur J,C,F ? Expliquer pourquoi.
Décrémenter de 1000 en 1000, la valeur 59000, jusqu'à ce que le SGBD n'utilise plus l'index. On note R'' la requête obtenue.

5.4) Lorsque l'optimiseur ne dispose pas de statistiques, il tente tente d'estimer la taille des résultats intermédiaires à partir d'un échantillon de données (technique appellée dynamic sampling). Désactiver le dynamic sampling en ajoutant la directive suivante.

select /*+ use_nl(c,j,f) dynamic_sampling(0) */ c.nom, f.budget

a) Expliquer pourquoi le plan généré par l'optimiseur est différent.
b) Dessiner l'arbre du plan d'exécution. Comprendre les opérations effectuées. L'optimiseur choisit de calculer une intersection entre deux ensembles. Quels sont ces 2 ensembles ?

Question 6 (facultatif)

6.1) Laisser le SGBD choisir les algorithmes de jointure, en supprimant la directive use_nl. Pourquoi la jointure par hachage est-elle choisie ?

6.2) Insérer des nuplets dans la table C jusqu'à ce que l'algorithme de jointure choisi change (pour un autre algorithme que le hash join)

Question 7 (facultatif)

7.1) Ajouter une 4eme table et proposer une requête de jointure entre les 4 tables qui ne puisse pas être transformée en un arbre linéaire gauche.

7.2) Ajouter suffisamment de données dans les tables pour qu'au moins une jointure par tri-fusion (sur les 3 jointures à effectuer) soit choisie par l'optimiseur.

Question 8 (facultatif)

Donner un exemple de requête R' de jointure entre C,J,F où le plan choisi par le SGBD consiste à commencer par une lecture séquentielle de F en entier. Cependant, ce plan serait efficace car la sélectivité de première jointure entre F et une autre relation serait très forte. R' est différent de R, vous pouvez changer les prédicats de la clause where.

Question 9 (facultatif)

Faire le TME JointureRépartie.

retour LesTravauxDirigés, Accueil,

Notice: "Undefined offset: 5" (...repeated 2 times)