1

Optimisation des Requêtes Relationnelles

Chapitre 15

2

Survol de l’Optimisation Plan: Arbre d’opérateurs de l’algèbre relationnelle, plus un

choix d’algorithme pour chaque opérateur. Lorsqu’un opérateur est choisi pour calculer les prochains

tuples, il fait appel à ses propres inputs pour calculer ces prochains tuples («  pipelining»).

Pour chaque requête, il y a 2 problèmes à considérer: L’espace des plans à considérer

• Algorithme de recherche afin de trouver le plan le moins couteux (p.ex., l’on évite les produit Cartésiens)

• Considère seulement les ‘’left-deep plans’’. Le coût estimé du plan

Idéalement nous cherchons le meilleur plan; pratiquement, nous évitons les pires plans.

3

Heuristiques pour les Opérations Relationnelles Quelles sont les heuristiques utilisées dans

l’optimisation de l’algèbre relationnelle ? Traduction de SQL en algèbre relationnelle Utilisation des statistiques dans l’optimisation Génération des plans alternatifs durant l’optimisation Évaluation des requêtes imbriquées

Exemple: Sailors(sid:integer, sname: string, rating: integer, age:

real)Boats(bid:integer, bname: string, color: string)Reserves(sid: integer, bid: integer, day: date, rname:

string) Supposez:

longueur des tuples de Reserves = 40 bytes; #tuples/pg = 100; #pgs = 1000

longueur des tuples de Sailors = 50 bytes; #tuples/pg = 80; #pgs = 500

4

Blocs d’une Requête: Unités d’Optimisation

Une requête SQL est décomposée syntaxiquement en une collection de blocs de requêtes qui seront traduit en A.R. et optimisées un à la fois.

Les blocs imbriqués sont d’habitude traités comme des appels de procédure, un par tuple de la relation externe.

SELECT S.snameFROM Sailors SWHERE S.age IN (SELECT MAX (S2.age) FROM Sailors S2 GROUP BY S2.rating)

Bloc imbriquéBloc externe Pour chaque bloc, les plans considérés sont:

– Toutes les méthodes d’accès de chaque relation de la clause FROM.

– Tous les arbres de join penchés vers la gauche, considérant toutes les permutations des relations de la clause FROM ainsi que tous les algorithmes de join.

5

Equivalences de l’ Algèbre Relationnelle

Les équivalences de l’A.R. permettent de choisir différents ordres de joins et faire les sélections et projections avant les joins.

Sélections: (Cascade)

c cn c cnR R1 1 ... . . .

c c c cR R1 2 2 1 (Commutativité)

Projections: a a anR R1 1 . . . (Cascade)

Joins: R (S T) (R S) T (Associativité)

(R S) (S R) (Commutativité)

6

Equivalences de l’ Algèbre Relationnelle (Suite) Une projection est commutable avec une sélection

qui porte uniquement sur les attributs de la projection.

Une sélection impliquant des attributs de 2 arguments d’un produit Cartésien est convertible en un join.

Une sélection ne mentionnant que les attributs de R est réductible à R (i.e., (R S) (R) S ).

De même, si une projection suit un join R S, nous pouvons la pousser au niveau de R et S en ne retenant que les attributs de R et S dont on a besoin pour le join.

7

Enumération des Plans Alternatifs

Deux cas sont à considérer: Plans à une seule relation Plans à multiples relations

Les requêtes à une seule relation consistent en une combinaison de sélections, projections et opérations d’agrégat: Chaque chemin d’accès disponible (scannage ou index) est

considéré et le moins couteux est choisi. Les différentes opérations sont exécutées ensemble (P.ex.: si

un index est utilisé pour une sélection, une projection est effectuée pour chaque tuple extrait et le résultat de cette projection est immédiatement utilisé pour calculer l’agrégat.

8

Estimation des Coûts Pour chaque plan considéré, on effectue

ce qui suit: Estimer le coût de chaque opération dans

l’arbre plan.• Ce coût dépend des cardinalités des relations

d’entrée.• L’estimation des coûts des diverses opérations

(scannage, joins, etc.) a été discutée au Chapitre 14 ainsi que dans la Section 8.4.

Estimer la taille du résultat de chaque opération dans l’arbre.

• L’information sur les relations d’entrée est utilisée.• Pour les sélections et les joins nous supposons que

les termes mentionnées dans les conditions sont indépendants les uns des autres.

9

Coûts des Plans à une Seule Relation Existence d’index I dont la clé correspond à la condition

de sélection: Arbre B+: Height(I)+1; Hachage: 1.2

Index groupé I correspondant à un ou plusieurs termes de la condition de sélection: (NPages(I)+NPages(R)) * produit des FRs des termes

correspondants. Index non-groupé I correspondant à un ou plusieurs

termes de la condition de sélection: (NPages(I)+NTuples(R)) * produit des FRs des termes

correspondants. Scannage séquentiel de la relation:

NPages(R). Note: par défaut, aucune élimination des duplicatas

n’est effectuée lors des projections.

10

Exemple Supposez qu’un index existe sur rating:

(1/NKeys(I)) * NTuples(S) = (1/10) * 40000 tuples extraits. Index groupé: (1/NKeys(I)) * (NPages(I)+NPages(S)) =

(1/10) * (50+500) pages sont extraites. Index non-groupé: (1/NKeys(I)) * (NPages(I)+NTuples(S)) =

(1/10) * (50+40000) pages sont extraites. Supposez qu’un index existe sur sid:

Nous n’avons pas de choix que d’extraire tous les tuples et toutes les pages. Avec un index groupé, le coût serait 50+500; avec un index non-groupé, il serait 50+40000.

Scannage séquentiel: Nous extrayons toutes les pages (500).

SELECT S.sidFROM Sailors SWHERE S.rating=8

11

Requêtes à Multiple Relations Heuristique fondamentale du Système R: n’utiliser

que les plans inclinés vers la gauche (« left-deep join trees »). Le nombre de plans alternatifs croit très rapidement avec le

nombre de joins. D’où nous devons restreindre l’espace de recherche.

Les plans inclinés vers la gauche permettent de faire l’économie des tables temporaires pour stocker les résultats intermédiaires.

BA

C

D

BA

C

D

C DBA

12

Enumération des Plans Inclinés vers la Gauche Ces plans diffèrent dans l’ordre des relations, le

chemin d’accès des relations et l’algorithme de join utilisé.

Enumération en N passages (Si N relations sont jointes): Passage 1: Trouver le meilleur plan à une relation pour chaque

relation. Passage 2: Trouver le meilleur moyen de faire le join du résultat de

chaque plan à 1 relation (comme relation externe) avec une autre relation. (Tous les plans à 2 relations.)

Passage N: Trouver le meilleur moyen de faire le join du résultat de chaque plan à N-1 relations (comme relation externe) avec la Nème relation. (Tous les plans à N relation.)

Pour chaque sous-ensemble des relations, ne retenir que: Le plan le moins couteux pour chaque ordre intéressant des tuples.

13

Enumération des Plans (Suite)

ORDER BY, GROUP BY, opérations d’agrégats, etc. sont traités comme étape finale en utilisant soit un plan produisant les tuples dans un ordre intéressant, soit un operateur de tri additionnel.

Un plan à N-1 relation n’est pas combiné avec une relation additionnelle, à moins qu’il y ait une condition de join qui les lie ou que tous les termes dans la clause WHERE aient déjà été utilisés. Ainsi, on évite les produits Cartésiens, dans la mesure du

possible. Bien que l’espace des plans est élagué, cette

approche produit encore un nombre exponentiel de plans.

14

Coûts des Plans à Multiples Relations

Considérez le bloc: Le # maximal de tuples dans le résultat est le produit

des cardinalités des relations dans la clause FROM. Le Facteur de réduction (FR) associé avec chaque terme

reflète l’impact de ce terme dans la réduction de la taille du résultat.

Cardinalité du résultat = # max de tuples * produit des FRs.

Les plans à multiples relations sont construits en joignant une seule nouvelle relation à chaque fois. Le coût de l’algorithme du join, plus l’estimation de la

cardinalité du join nous fournissent à la fois l’estimation du coût du join ainsi que celle de la taille du résultat.

SELECT attribute listFROM relation listWHERE term1 AND ... AND termk

15

Exemple Passage1:

Sailors: L’arbre B+ correspond à rating>5; il est probablement moins coûteux. Cependant, si l’on prévoit que cette sélection extraira un nombre élevé de tuples et que l’arbre B+ est non-groupé, un scannage serait meilleur.

• L’arbre B+ est choisi car les tuples sont ordonnés selon rating).

Reserves: L’arbre B+sur bid correspond à bid=500.

Sailors: Index B+ sur rating Hachage sur sidReserves: Index B+ sur bid

Passage 2:Considérez chaque plan retenu au passage 1 comme relation externe et le joindre avec la seule relation restante. Ainsi, si l’on prend Reserves comme relation externe, le hachage existant sur sid peut être utilisé pour extraire les tuples correspondants de Sailors.

Reserves Sailors

sid=sid

bid=100 rating > 5

sname

16

Requêtes Imbriquées

Le bloc imbriqué est optimisé indépendamment avec le tuple de la relation externe qui fournit la condition de sélection.

Le bloc imbriquant est optimisé en prenant en considération le coût de l’appel du bloc imbriqué.

L’ordre implicite de ces deux blocs interdits certaines bonnes stratégies d’optimisation. Souvent, la requête non-imbriqué équivalente est mieux optimisable.

SELECT S.snameFROM Sailors SWHERE EXISTS (SELECT * FROM Reserves R WHERE R.bid=103 AND R.sid=S.sid)

Bloc imbriqué à optimiser: SELECT * FROM Reserves R WHERE R.bid=103 AND S.sid= valeur ext.

Requête non-imbriquée équivalente:SELECT S.snameFROM Sailors S, Reserves RWHERE S.sid=R.sid AND R.bid=103

17

Résumé L’optimisation fait deux considérations importantes:

Un ensemble de plans alternatifs qui forme un espace exponentiel à élaguer en ne considérant que les plans incliné vers la gauche.

Une estimation du coût de chaque plan.• Estimation de la taille du résultat et du coût de chaque opérations du

plan.• Utilisation des statistiques, indexes et implémentations appropriées

des opérateurs. Requêtes à une relation:

Considérer tous les chemins d’accès et choisir le meilleur. Considérer les sélections qui correspondent aux indexes et

combiner les sélections, projections et opérations d’agrégat. Requêtes à multiples relations:

Enumérer les plans à 1 relations en considérant les sélections/projections aussitôt que possible.

Pour chaque plan à i-1 relations (i < # relations) considérer la meilleur manière de le joindre avec une des N-i relations restantes.

Ne retenir à chaque niveau que les meilleurs plans pour chaque ordre intéressant de tuples.