1©Gardarin 2001

Optimisation de Requêtes

1. Introduction2. Arbres relationnels3. Restructuration algébrique4. Le cas de l’objet5. Modèle de coût6. Choix du meilleur plan7. Conclusion

2©Gardarin 2001

1. ARCHITECTURE TYPE SGBD

ANALYSEUR

META-BASE

CONTROLE

OPTIMISEUR

EXECUTABLE

SYNTAXESEMANTIQUESCHEMA

VUESINTEGRITEAUTORISATIONS

ORDONNANCEMENTELABORATIOND'UN PLAN

EXECUTIONMETHODES D'ACCES

3©Gardarin 2001

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éesEtape 3 : dépendante des données

4©Gardarin 2001

2. ARBRES RELATIONNELS

PRODUIT CARTESIEN

JOINTURE

RESTRICTION

V. CRU "BEAUJOLAIS"

PROJECTION

V.NV, V.CRU

DIFFERENCE

—

B2B1

UNION

B1 B2

U

V

=

=A. NV V. NV

A V

A V

V

TRI

V

V.CRU, V.MILL

AGREGAT

V

V.CRU, V.MILL

COUNT(*),AVG(DEGRE)

5©Gardarin 2001

EXEMPLE D'ARBRERESULTAT

B.NOM, B.PRENOM

A.DATE

V.CRU

01-01-90

"MACON"

>

=

A.NV V.NV=

VINS V

=

B.NB A.NB

B.VILLE "MACON"

BUVEURS B

=

ABUS A

Coût d'exécution:• 10 millions de buveurs

dont 1 m à Paris• 10 millions d'abus dont

10000 de Volnay • 1000 vins

• 10 m + 10m * 1m + 10 m * 1000

• + 10 m + 10000 + …• de l'ordre de 10 ** 13• comparaisons de tuples !!!

6©Gardarin 2001

=R. NV V. NV

R V

=P.NP R.NP

P

=

V.MILLESIME = 1976

P.REGION « Bordelais »

V.DEGRE 14

V.CRU

Arbre linéaire droitSELECT V.CRU

FROM PRODUCTEURS P, VINS V, PRODUIT R

WHERE V.MILLESIME = 1976 AND V.DEGRE 14

AND P.REGION = « BORDELAIS » AND P.NP = R.NP

AND R.NV = V.NV.

7©Gardarin 2001

Typologie des arbres

Arbre linéaire droit Arbre linéaire gauche Arbre ramifié

8©Gardarin 2001

Autre exemple

SELECT P.NOM, SUM(L.PRIX * (1-L.DISCOUNT))

FROM CLIENTS C, COMMANDES O, LIGNES L, FOURNISSEUR F, PAYS P, CONTINENTS T

WHERE C.NUMCLI = O.NUMCLI

AND O.NUMCOM = L.NUMCO

AND L.NUMFOU = F.NUMFOU

AND C.NUMPAYS = F.NUMPAYS

AND F.NUMPAYS = P.NUMPAYS

AND P.NUMCONT = T.NUMCONT

AND T.NOM = « EUROPE »

AND O.DATE $D1 AND O.DATE < $D1 + INTERVAL 1

YEAR

GROUP BY P.NOM

ORDER BY RECETTE DESC ;

RECETTE

P.NOM, RECETTE

P.NOM

C.NUMCLI = O.NUMCLI

O.NUMCOM = L.NUMCO

$D1 O.DATE <$D1+1

L.NUMFOU = F.NUMFOU

C.NUMPAYS = F.NUMPAYS

F.NUMPAYS = P.NUMPAYS

L

C

FP.NUMCONT = T.NUMCONT

P

T

OT.NOM = « EUROPE »

9©Gardarin 2001

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éese.g., restriction et projection

10©Gardarin 2001

Commutativité des Jointures

R S S R

11©Gardarin 2001

Associativité des jointures

R S

T

S T

R

Il existe N!/2 arbre de jointure de N relations.Parmi les jointures, certaines sont des produits

cartésiens.

12©Gardarin 2001

Groupage des Restrictions

Ai = a

Aj = b

Ai = aet

Aj = b

13©Gardarin 2001

Semi-commutativité des Projections

Ai = a

A1, … Ap

Ai = a

A1, … Ap

Ai,A1,… Ap

Il est possible de descendre les projections, mais les attributs utilisés dans la suite doivent être conservés !!!

14©Gardarin 2001

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

15©Gardarin 2001

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é !!!

16©Gardarin 2001

Exemple d'Arbre Optimisé

B.NOM, B.PRENOM

A.DATE

V.CRU

01-01-83

"VOLNAY"

>=

A.NV V.NV=

V

Résultat

=

B.NB A.NB

B.VILLE "PARIS"

B

=

A

B.NB, B.NOM, B.PRENOM A.NB, A.NV

V.NV

B.NOM, B.PRENOM,A.NV

Coût d'exécution:

10 m + 1m * 100000 + 1 m * 1000 + …

de l'ordre de 10 ** 11 comparaisons de tuples !

17©Gardarin 2001

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

18©Gardarin 2001

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

19©Gardarin 2001

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

20©Gardarin 2001

Exemple de plan d'exécution

Employé

age() < 50 Groupe

directeur

ville = "Paris" couleur = "Rouge"

Véhicule

Fabriquant

numéro

Exemple :SELECT V.numéro FROM V in Vehicule, G in

V.Fabriquant, E in G.directeur WHERE E.age()) < 50 AND

V.couleur = "Rouge" AND G.ville = "Paris"

Plusieurs plans candidats:• descente des projections• sélections d'abord (?)• ordonnancement des

jointures• coût des méthodes

21©Gardarin 2001

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, …)

22©Gardarin 2001

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 =1SELECT *FROM R1WHERE A = valeur==> s = 1/NDIST(A) avec un modèle uniforme

23©Gardarin 2001

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).

24©Gardarin 2001

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

25©Gardarin 2001

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.

26©Gardarin 2001

Le calcul des tailles

Taille des tables de base dans le catalogueCalcul 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

27©Gardarin 2001

6. CHOIX DU MEILLEUR PLAN

Générateur de

Plans

Arbre d'opérations

Heuristiques

de choix

Plan d'exécution

Optimal

Schéma interne

Plans d'exécution

Stratégie de

Recherche

Bibliothèque de

transformations

Modèle de coût

28©Gardarin 2001

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) ;

29©Gardarin 2001

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 ;

30©Gardarin 2001

Illustration DP

ScanR1

JoinH R2

JoinH R3

JoinH R3

JoinS R2

JoinS R3

JoinH R2JoinS R3 JoinS R2

31©Gardarin 2001

Différentes Stratégies

Stratégiede recherche

AléatoireEnumérative

Exhaustive Augmentation GénétiqueAméliorationitérative

Recuitsimulé

32©Gardarin 2001

Amélioration itérativeFunction Iterative(Query)p:= Parse(Query) ; // Set the initial plan

S := {} ; // S is the set of locally optimum planswhile 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 plansp := Random(Parse(Query)); // Generate a new initial plan at

random}

}return Optimal(S) ; // Select best plan among all generated ones }

33©Gardarin 2001

Illustration IIParse(Query)

Profitabler1

Profitabler2

SELECTMINIMAL

COSTPLAN

Profitabler'1

Profitabler"1

Profitabler"2

Rand(Parse(Query)) Rand(Rand((Parse(Query)))

34©Gardarin 2001

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