OPTIMISATION DE
REQUETES SQL
Soit les relations
⚫ ACTEUR(numA, nom, prenom, anneeN)
⚫ FILM(numF, titre, duree, anneeS)
⚫ ROLE (numF, numA, nomRole)
Donner le nom et le prénom des acteurs nés après 1970
(inclus) qui ont joué le rôle de François Pignon dans des
filmssortis après 1990.
Question :
⚫ Quelle différence entre les deux requêtes suivantes ?
AUCUNE en termes de résultat retourné, mais les temps de traitements
seront différents
TRAITEMENT D’UNE REQUÊTE
BD BD’
R
A B C D E
S
A B C D E
R S
A B C D E A B C D E
tuples
tuples
Q Requête Q : Q
SELECT R.A, S.C
FROM R,S
WHERE R.B=S.B;
Exécutée Exécutée
en 5 ms en 105 ms
Une même requête peut s’exécuter
2
de différentes manières
QUESTIONS
Comment passe-t-on d’une requête SQL (définie dans
un langage déclaratif) à un programme (impératif)
manipulant les données ?
Comment optimise-t-on une requête afin de l’exécuter
efficacement pour trouver un résultat correct?
Analyse des différentes étapes du
traitement d’une requête
TRAITEMENT DE REQUÊTES
Validation de la syntaxe
de la requête
Requête SQL
Traduction de la requête
Analyse en arbre algébrique
Compilation
Recherche de l’arbre
Optimisation algébrique optimal
Exécution du programme
Exécution correspondant à l’arbre
algébrique optimal
Arbre algébrique Plan d’exécution
Pour la même requête, Il peut y avoir plusieurs plans
d’exécution possibles.
L’optimiseur doit choisir le plan ayant le coût le moins important.
Ce coût est mesuré en termes de différentes ressources :
➢Accès disque,
➢Temps CPU,
➢Espace mémoire utilisé,
Dans le cas des systèmes parallèles ou distribués il doit inclure
le coût de communication.
TRAITEMENT D’UNE REQUÊTE
A,C
R(A,B,C) et S(B,C,D, E) Validation OK
SELECT R.A, S.C
SELECT R.A, S.C
Analyse FROM R, S compilation B
FROM R, S WHERE R.B=S.B;
WHERE R.B=S.B;
R S
optimisation
Election du
A,C plan optimal
A,C
B
B
A,B B,C
A,B B,C
R S
R S
Choix des
algorithmes
Prog. Résultats
exécution
ANALYSE
Analyse lexicale et syntaxique :
⚫ Validation par rapport à la syntaxe SQL
⚫ Vérification des types :
présence des attributs et relations dans le schéma
compatibilité des types dans les prédicats
⚫ Décomposition en requêtes/sous-requêtes
COMPILATION
Règle de passage d’une requête SQL en AR
⚫ SELECT …. : permet de définir une projection
⚫ FROM … : permet de définir les feuilles de l’arbre
⚫ WHERE ….: permet de définir
Pour les comparaisons attribut/valeur: des sélections
Pour les comparaisons attribut/attribut : des jointures
OPTIMISATION
Optimiser c’est trouver le plan d’exécution d’une
requête dont le coût soit minimal (i.e. le temps de
réponse à la requête soit le plus rapide possible)
Qu’est-ce qui peut être optimisé dynamiquement?
Les accès disques
Il est indispensable que le temps lié à
l’optimisation soit négligeable par rapport au
temps imparti à l’exécution
ESPACE DE RECHERCHE
Caractérisé
par les plans “équivalents”
pour une même requête
⚫ ceux qui donnent le même résultat
générés$ en appliquant des règles
detransformation
Le coût de chaque plan est en général
différent
L'ordre des jointures est important
Optimisation algébrique
CHOIX ALGORITHMIQUES
Chaque opérateur peut être implémenté de
différentes façons.
⚫ La complexité de l’algorithme a un impact sur le
temps de traitement de la requête
La façon dont les jointures sont implémentées est
important
Optimisation physique
EXÉCUTION
Application pour chaque opération du plan
d ’exécution des programmes associés
⚫ MySQL, Postgres : C, C++
⚫ HSQL : JAVA
⚫ …
COMMENT OPTIMISER ?
Réécriture des compositions de projections et/ou
sélections
Réduire au plus tôt la taille et le nombre de
tuples manipulés
⚫ Tuples moins nombreux : grâce à la sélection
⚫ Tuples plus petit : grâce à la projection
Réordonner les jointures, en fonction de la taille
des relations manipulées
Choisir des algorithmes de jointures efficaces
selon les relations manipulées
RÉÉCRITURE DES COMPOSITIONS DE PROJECTIONS
ET/OU DE SÉLECTIONS
Exemple :
SELECT Enom
FROM Employe E, Travaux T,
Projet P
WHERE E.Eid = T.Eid
AND T.Pid = P.Pid
AND Enom !=‘Toto’
AND Pnom = ‘Linkannot’
AND (Durée=2 OR Durée=4)
RÉÉCRITURE DES COMPOSITIONS DE PROJECTIONS
ET/OU DE SÉLECTIONS
Enom
(Durée=2 Durée=4) (Pnom=“LinkAnnot”) (Enom !=“toto”)
Pid
Eid
Projet Travaux Employe
OPTIMISATION ALGÉBRIQUE
Principe:
Réduction au plus tôt du nombre et de la taille des
tuples manipulés
Manipulation algébrique
Exploitation des règles de transformation de certains
opérateurs
commutativité
associativité
RÈGLES DE TRANSFORMATION
Commutativité des opérations binaires
⚫ RSSR
⚫ R SS R
⚫ RSSR
Associativité des opérations binaires
⚫ ( R S ) T R (S T)
⚫ ( R S ) T R (S T )
Idempotence des opérations unaires
⚫ A1…An(Bm(R)) A1…An(R), Bi inclus
dans Ai
⚫ F1(F2(R)) F1 F2(R)
COMMENT PASSER DE L’UN À L’AUTRE?
Enom, Titre Enom, Titre
Budget>250
Employe
Budget>250
Travaux
Projet
Travaux Employe Projet
COMMENT PASSER DE L’UN À L’AUTRE?
Associativité de la jointure
Projet ( Travaux Employe )
Enom, Titre
( Projet Travaux ) Employe
Budget>250
Projet
Travaux Employe
COMMENT PASSER DE L’UN À L’AUTRE?
Associativité de la jointure
Projet ( Travaux Employe )
Enom, Titre
( Projet Travaux ) Employe
Budget>250
Projet Employe
Travaux Employe
Projet Travaux
COMMENT PASSER DE L’UN À L’AUTRE?
Commutativité de la
sélection et de la jointure
Budget>250 ( E (P T) )
Enom, Titre
(E Budget>250 ( P T) )
Budget>250
Projet Employe
Travaux Employe
Projet Travaux
COMMENT PASSER DE L’UN À L’AUTRE?
Commutativité de la
sélection et de la jointure
Budget>250 ( E (P T) )
Enom, Titre
(E Budget>250 ( P T) )
Budget>250 Employe
Projet Travaux
COMMENT PASSER DE L’UN À L’AUTRE?
Commutativité de la
sélection et de la jointure
(E Budget>250 ( P T) )
Enom, Titre
(E (Budget>250 (P) T) )
Budget>250 Employe
Projet Travaux
COMMENT PASSER DE L’UN À L’AUTRE?
Commutativité de la
sélection et de la jointure
(E Budget>250 ( P T) )
Enom, Titre
(E (Budget>250 (P) T) )
Employe
Budget>250
Travaux
Projet
ARBRES DE JOINTURES
Des arbres de jointures
équivalents peuvent être obtenus P
en appliquant les règles de E T
commutativité et d'associativité
SELECT * E
FROM E, T, P
WHERE E.Eid=T.Eid P T
AND T.Pid=P.Pid
T
P E
RAPPEL
Exemple :
Enom
SELECT Enom
FROM Employe E, Travaux T, Durée=2 Durée=4
Projet P
WHERE E.Eid = T.Eid Pnom=“LinkAnnot”
AND T.Pid = P.Pid
AND Enom !=‘Toto’ Enom!=“toto”
AND Pnom = ‘Linkannot’
AND (Durée=2 OR Durée=4)
Pid
Eid
Projet Travaux Employe
AUTRE PLAN ÉQUIVALENTE
Enom
Pid,Enom
Pid Pid,Eid Eid,Enom
Pnom=“LinkAnnot” Durée=2 Durée=4 Enom!=“toto”
Projet Travaux Employe
ALGORITHMES DE RECHERCHE
Limiter l'espace de recherche
⚫ heuristiques
par ex. appliquer les opérations unaires avant les autres
⚫ limiter la forme des arbres
Arbre linéaire Arbre touffu
R4
R3
R1 R2 R1 R2 R3 R4
LES ALGORITHMES DE JOINTURES
Les algorithmes de jointures sont couteux
Il existe différents algorithmes d’implantation des
jointures
Jointure par boucles imbriquées
Jointure par tri fusion
Jointure par hachage
Exemple :
On considère la jointure R⋈A S avec R(A,B) et S(A,C)
JOINTURE PAR BOUCLE IMBRIQUÉE
Algorithme le plus simple pour évaluer la jointure
Principe:
⚫ Comparer chaque nuplet de la relation R à tous les nuplets de
la relation S,
⚫ Concaténer les nuplets pour lesquels la condition de jointure est vérifiée
⚫ Ajouter le nouveau tuple au résultat.
JOINTURE PAR TRI-FUSION
Algorithme utile quand il n’y a pas d’index sur des tables de
grandes tailles
Principe:
⚫ Trier R et S par rapport à l’attribut de jointure A
⚫ Fusionner R et S
JOINTURE PAR HACHAGE
Algorithme utile quand il y a un index sur l’attribut
de jointure et qu’une des deux relations peut être
mise en mémoire
Principe:
On suppose que S est une relation de taille plus petite que R
⚫ Hacher S avec une fonction de hachage H (clé=A;
valeur=tuple de S)
⚫ Pour chaque tuple r de R, rechercher dans la structure de
hachage la clé r.A
60
COMMENT OPTIMISER ?
Le processus d’optimisation s’appuie sur :
1. Le schéma logique de la base, description des tables
2. Le schéma physique de la base, indexes et chemins
d'accès, tailles des blocs
3. Des statistiques : taille des tables, des index,
distribution des valeurs
4. Des statistiques : taux de mises-à-jour
5. Des algorithmes : ils peuvent différer selon les
systèmes
ESTIMER LE COÛT D’UN PLAN
La fonction de coût donne les temps I/O et CPU
⚫ nombre d’instructions et d’accès disques (écriture/lecture)
Estimation du nombre d’accès disque pendant
l’évaluation de chaque nœud de l’arbre algébrique
Estimation de la taille du résultat de chaque nœud par
rapport à ses entrées :
⚫ sélectivité des opérations
CONCLUSION
Maintenant vous savez se passe après un clic
sur le bouton ‘Execute’
