Optimisation de Requêtes
1. Introduction
2. Arbres relationnels
3. Restructuration algébrique
4. Le cas de l’objet
5. Modèle de coût
6. Choix du meilleur plan
7. Conclusion
1
1. ARCHITECTURE TYPE SGBD
SYNTAXE
ANALYSEUR SEMANTIQUE
SCHEMA
VUES
CONTROLE INTEGRITE
AUTORISATIONS
ORDONNANCEMENT
META-BASE OPTIMISEUR ELABORATION
D'UN PLAN
EXECUTABLE EXECUTION
METHODES D'ACCES
2
ETAPES DE L'OPTIMISATION
(1) Obtention d’une représentation canonique
(2) Réécriture = transformation par :
• simplification
• ordonnancement des opérations élémentaires
(3) Planning = construction des plans
d'exécution candidats
• choix des algorithmes pour chaque opérateur,
• calcul du coût de chaque plan,
• choix du meilleur plan.
Etapes 1 et 2 : indépendantes des données
Etape 3 : dépendante des données
3
2. ARBRES RELATIONNELS
RESTRICTION PROJECTION TRI
V. CRU = "BEAUJOLAIS" [Link], [Link] [Link], [Link]
V
JOINTURE V
DIFFERENCE V
A. NV = V. NV
— AGREGAT
A V
B1 B2
PRODUIT CARTESIEN UNION
COUNT(*),AVG(DEGRE)
[Link], [Link]
U
A V B2
B1
V
4
EXEMPLE D'ARBRE
Coût d'exécution: RESULTAT
• 10 millions de buveurs [Link], [Link]
dont 1 m à Paris
• 10 millions d'abus dont [Link] > 01-01-90
10000 de Volnay
• 1000 vins [Link] = "MACON"
[Link] [Link]
• 10 m + 10m * 1m + 10 m =
* 1000
• + 10 m + 10000 + … [Link] [Link] VINS V
=
• de l'ordre de 10 ** 13
• comparaisons de tuples !!!
[Link] = "MACON" ABUS A
BUVEURS B
5
Arbre linéaire droit
SELECT [Link]
[Link]
FROM PRODUCTEURS P, VINS V,
PRODUIT R
WHERE [Link] = 1976 AND
[Link] = 1976
[Link] 14
AND [Link] = « BORDELAIS » AND
[Link] 14 [Link] = [Link]
AND [Link] = [Link].
[Link] = « Bordelais »
[Link] [Link]
=
R. NV = V. NV
R V
6
Typologie des arbres
Arbre linéaire droit Arbre linéaire gauche Arbre ramifié
7
Autre exemple
RECETTE SELECT [Link], SUM([Link] * (1-
[Link]))
[Link], RECETTE FROM CLIENTS C, COMMANDES O, LIGNES L,
FOURNISSEUR F, PAYS P, CONTINENTS T
[Link]
WHERE [Link] = [Link]
[Link] = [Link]
AND [Link] = [Link]
[Link] = [Link]
AND [Link] = [Link]
[Link] = [Link] AND [Link] = [Link]
AND [Link] = [Link]
L
AND [Link] = [Link]
[Link] = [Link]
AND [Link] = « EUROPE »
C
[Link] = [Link] AND [Link] $D1
F AND [Link] < $D1 + INTERVAL 1
[Link] = [Link] YEAR
$D1 [Link] <$D1+1 GROUP BY [Link]
P [Link] = « EUROPE » ORDER BY RECETTE DESC ;
O
T
8
3. RESTRUCTURATION
ALGEBRIQUE
Problème :
• suivant l'ordre des opérateurs algébriques dans un
arbre, le coût d'exécution est diffèrent
Pourquoi?
• 1. le coût des opérateurs varient en fonction du
volume des données traitées
i.e., plus le nombre de tuple des relations traitées
est petit, plus les coûts cpu et d'E/S sont minimisés
• 2. certains opérateurs diminuent le volume des
données
e.g., restriction et projection
9
Commutativité des Jointures
R S S R
10
Associativité des jointures
Il existe N!/2 arbre de jointure de N relations.
Parmi les jointures, certaines sont des produits
cartésiens.
T R
R S S T
11
Groupage des Restrictions
Ai = a
Ai = a
et
Aj = b
Aj = b
12
Semi-commutativité des
Projections
Il est possible de descendre les projections,
mais les attributs utilisés dans la suite doivent
être conservés !!!
A1, … Ap
A1, … Ap
Ai = a
Ai = a
Ai,
A1,… Ap
13
Règles de Restructuration
(1) Commutativité des jointures
(2) Associativité des jointures
(3) Groupabilité des restrictions
(4) Semi-commutativité des projections et
restrictions
(5) Semi-commutativité des restrictions et
jointures
(6) Semi-distributivité des projections / jointures
(7) Distributivité des restrictions / unions ou
différences
(8) Distributivité des projections / unions
14
Heuristique d'Optimisation
Appliquer d'abord les opérations réductrices
(restrictions et projections) en les groupant
sur chaque relation.
• 1. Dégrouper les restrictions (Règle 3')
• 2. Descendre les restrictions (Règles 4, 5 et 7)
• 3. Grouper les restrictions aux feuilles (Règle 3)
• 4. Descendre les projections (Règles 4, 6 et 8)
L'ordre des unions, différences et jointures
reste inchangé !!!
15
Exemple d'Arbre Optimisé
Résultat Coût d'exécution:
[Link], [Link]
10 m + 1m *
[Link] [Link] 100000 + 1 m *
=
1000 + …
[Link], [Link],[Link]
[Link] [Link] [Link]
de l'ordre de 10 **
=
11 comparaisons
[Link], [Link], [Link] [Link], [Link] de tuples !
[Link] = "VOLNAY"
[Link] = "PARIS"
[Link] > 01-01-83
V
B A
16
Ordonnancement des Jointures
HEURISTIQUES :
• Choix des relations de taille minimum
• Jointures pré-calculés d ’abord (indexes)
• Semi-jointures plus réductrices
ORDONNANCEMENT DES AGREGATS
• Permutations difficiles
• Profiter des tris des jointures, dédoublement, etc..
• Gains importants pour MIN et MAX
17
4. LE CAS DE L ’OBJET
Les mêmes règles s’appliquent
• cas dégénéré des objets « plats »
Il faut en plus traiter
• jointures par parcours de références
• méthodes et polymorphisme (?)
• collections (imbriquées)
Peu d’optimiseurs objets puissants
18
Algèbre d'objets
L’algèbre relationnelle est étendue :
• RESTRICTION : Application d'un critère (avec méthodes) à une
classe
• PROJECTION : Application d'attributs ou de méthodes à une classe
• JOINTURE_REF : Jointure par parcours de référence
• JOINTURE_VAL : Jointure par comparaison de valeurs
• NEST : Groupage d'une collection par rapport à d'autres attributs
• UNNEST : Aplatissage d'un attribut en une collection
• FLATEN : Suppression d'un niveau de collections
• UNION : Union d'objets dans une même classe
• DIFFERENCE : Suppression des objets d'une classe d'une autre
classe
Langage cible d ’un optimiseur de requêtes OO
19
Exemple de plan d'exécution
Employé Exemple :
SELECT [Link]éro
age() < 50 Groupe FROM V in Vehicule, G in
[Link], E in [Link]
WHERE [Link]()) < 50 AND
directeur Véhicule [Link] = "Rouge" AND
[Link] = "Paris"
ville = "Paris" couleur = "Rouge"
Plusieurs plans candidats:
• descente des projections
Fabriquant • sélections d'abord (?)
• ordonnancement des
numéro jointures
• coût des méthodes
20
Problème de
l'Ordonnancement
Il faut pouvoir ordonner jointures, union, différence,
agrégat, … en fonction des tailles des relations
arguments
Il faut pouvoir prendre en compte les algorithmes par
index afin de les favoriser (sélection, jointure sur
index, parcours)
Nécessité de développer un modèle de coût général
permettant d'évaluer le coût d'un plan, c'est-à-dire
d'un arbre annoté par des choix d'algorithmes.
Annotation:
• Marque associée à un noeud indiquant l'algorithme à utiliser
pour l'opérateur avec ses paramètres (index, hachage, …)
21
5. MODELE DE COUT
Facteur de sélectivité
• Proportion de tuples du produit cartésien des
relations touchées qui satisfont une condition.
Exemple:
SELECT *
FROM R1, R2
==> s =1
SELECT *
FROM R1
WHERE A = valeur
==> s = 1/NDIST(A) avec un modèle uniforme
22
Sélectivité des Restrictions
TAILLE ((R)) = s * TAILLE(R) avec:
s (A = valeur) = 1 / NDIST(A)
s(A > valeur) = (max(A) - valeur) / (max(A) - min(A))
s(A < valeur) = (valeur - min(A)) / (max(A) - min(A))
s (A IN liste valeurs) = (1/NDIST(A)) * CARD(liste valeurs)
s(P et Q) = s(P) * s(Q)
s(P ou Q) = s(P) + s(Q) - s(P) * s(Q)
s( not P) = 1 - s(P)
Le coût dépend de l'algorithme (index, hachage ou
balayage).
23
Sélectivité des Projections
TAILLE(x(R)) = p(x) * (1-d) * TAILLE(R)
• avec p(x) = Larg(x) / Larg(R)
• d = probabilité de doubles
• CARD(X) / CARD(DOM(X))**2
24
Sélectivité des Jointures
TAILE( R1 |><| R2) = p * TAILLE(R1) *
TAILLE(R2)
• p dépend du type de jointure et de la corrélation
des colonnes :
p = 0 si aucun tuple ne joint
p = 1 / MAX(NDIST(A),NDIST(B)) si distribution uniforme
équiprobable des attributs A et B sur un même domaine
p = 1 si produit cartésien
L'algorithme change radicalement les coûts
• linéaire si index,
• produit des tailles si boucles imbriquées.
25
Le calcul des tailles
Taille des tables de base dans le catalogue
Calcul des tailles à la compilation
• application du coefficient de sélectivité
• hypothèse d ’uniformité
Possibilité d’histogrammes
• RunStat(<Table>, <attribut>)
• Stockage dans le catalogue de l’histogramme de
distribution de l ’attribut
• Utilisation par le modèle de coût
26
6. CHOIX DU MEILLEUR PLAN
Arbre Schéma
d'opérations interne
Plans
d'exécution Bibliothèque
Générateur de
de
Plans
transformatio
Stratégie de ns
Heuristiqu
Recherche es
de choix
Modèle de coût
Plan d'exécution
Optimal
27
Sélectivité minimum
Rel = liste des relations à joindre ;
p = plus petite relation ;
Tant que Rel non vide {
R = relation de selectivité minimum de
Rel ;
p = join(R,p) ;
Relations = Relations - R ; } ;
Return(p) ;
28
Programmation Dynamique
PlanOuverts = liste de tous les plans mono-relation
possible ;
Eliminer tous les plans équivalents excepté le moins coûteux
;
Pour chaque PlanOuverts p {
Pour chaque opérateur n’appartenant pas au plan p {
Etendre le plan en ajoutant cet opérateur ;
Calculer le coût du nouveau plan ;
Insérer le nouveau plan dans la liste Nouveaux ; }
Eliminer tous les plans équivalents excepté le moins
coûteux ;
Transférer les plans Nouveaux dans PlanOuverts ; }
Retourner le plan optimal ;
29
Illustration DP
ScanR1
JoinS R3
JoinH R2
JoinS R2 JoinH R3
JoinH R3 JoinS R3 JoinH R2 JoinS R2
30
Différentes Stratégies
Stratégie
de recherche
Enumérative Aléatoire
Amélioration Recuit Génétique
Exhaustive Augmentation
itérative simulé
31
Amélioration itérative
Function Iterative(Query)
p:= Parse(Query) ; // Set the initial plan
S := {} ; // S is the set of locally optimum plans
while not StopCond()
{ nmoves := 0;
while nmoves < MaxMoves(Query) and Transformable(p)
{ p' := Transform (p) ; // Apply a transformation rule
if Cost(p') < Cost(p) then
{ p ::= p';
nmoves ::= nmoves + 1;
}
Insert (S, p') ; // Maintain the set of interesting plans
p := Random(Parse(Query)); // Generate a new initial plan at
random
}
}
return Optimal(S) ; // Select best plan among all generated ones }
32
Illustration II
Parse(Query) Rand(Parse(Query)) Rand(Rand((Parse(Query)))
Profitable Profitable
Profitable
r'1 r"1
r1
Profitable
Profitable r"2
r2
SELECT
MINIMAL
COST
PLAN
33
7. CONCLUSION
Problème essentiel des SGBD
Nécessité d’un modèle de coût
Approches par compilation dans un langage
d’accès (opérateurs avec annotations)
Stratégies de choix aléatoires
34