fr
Traitement des requêtes
Requête
Plan d’exécution
Plan d’exécution : définit l’ensemble des
opérations (algorithmes) à exécuter pour
déterminer la réponse
Optimisation des requêtes Le meilleur plan
Réda DEHAK 2
Exemple
Select B,D
From R,S
Where R.A = “c” ∧ S.E = 2 ∧ R.C=S.C
R A B C S C D E
a 1 10 10 x 2
b 1 20 20 y 2
c 2 10 30 z 2
d 2 35 40 x 1 Réponse B D
e 3 45 50 y 3
2 x
Réda DEHAK 3
Comment?
• Idées :
1. Faire un produit cartésien
Sélectionner les tuples
Faire une projection
RXS R.A R.B R.C S.C S.D S.E
a 1 10 10 x 2
a 1 10 20 y 2
. . . . . .
. . . . . .
C 2 10 10 x 2
. . . . . .
Réda DEHAK
. . . . . . 4
Description des plans
• Algèbre relationnel :
B,D
R.A = “c” ∧
S.E = 2 ∧ ΠB,D [ σR.A=“c”∧ S.E=2 ∧ R.C = S.C (RXS)]
R.C=S.C
R S
Réda DEHAK 5
Plan II
B,D
R.A = “c” S.E = 2
R S
ΠB,D [ Join ( σR.A="c" ( R ) , σS.E=2 ( S ) ) ]
Réda DEHAK 6
Plan II
R S
A B C σ (R) σ(S) C D E
a 1 10 A B C C D E 10 x 2
b 1 20 c 2 10 10 x 2 20 y 2
c 2 10 20 y 2 30 z 2
d 2 35 30 z 2 40 x 1
e 3 45 50 y 3
B D
Réda DEHAK 2 x 7
Plan III
• Utilisation des indexes sur R.A et S.C
(1) Utiliser l’indexe sur R.A pour sélectionner les tuples de R vérifiant R.A
= "c"
(2) Utiliser l’indexe sur S.C pour sélectionner les tuples correspondants à
chaque tuple de R.
(3) Éliminer les tuples tel que S.E ≠ 2
(4) Projeter sur B,D
Réda DEHAK 8
Plan III
R S
A=“c” C
A B C I1 I2 C D E
a 1 10 10 x 2
<c,2,10> <10,x,2>
b 1 20 20 y 2
c 2 10 check=2? 30 z 2
d 2 35 output: <2,x> 40 x 1
e 3 45 50 y 3
next tuple:
<c,7,15>
Réda DEHAK 9
Problèmes
• Pour chaque requêtes :
– Comment déterminer un plan d’exécution?
– Comment évaluer le coût de chaque plan?
• Idéalement : trouver le meilleur plan
• Pratiquement : éviter les mauvais plans
• Les algorithmes utilisés pour évaluer une opération de base
Réda DEHAK 10
Plan
• Exécution d’une requête
– Étude des différents algorithmes
• Compilation des requêtes :
– Déterminer un plan logique.
– Déterminer le meilleur plan physique.
Réda DEHAK 11
Architecture d’un SGBD
Requêtes SQL
Plan d’exécution Parser
Évaluation
des
requêtes Évaluation des
Optimisation
opérateurs
Gestionnaire des Méthodes d’accès et fichiers
transactions
Gestionnaire du tampon
Gestion de la concurrence Récupération
Gestionnaire des Gestionnaire de l’espace
verrous disque
SGBD
Base de données Index, données
Réda DEHAK 12
Évaluation d’une requête
• Les principales composantes du query processor
Requête SQL
Parser
Arbre syntaxique
Détermination du meilleur plan
logique
Arbre correspondant au
plan logique
Détermination du meilleur plan
physique
Arbre correspondant au
plan physique
Réda DEHAK
Plan d’exécution 13
Opérations
C L
x C
Sélection Projection Produit cartésien Jointure
L - ∪ ∩
Renommage Différence Union Intersection
Réda DEHAK 14
Opérateurs supplémentaires
• Élimination des doublons :
δ : transformer le multi-set en ensemble.
• Grouper
γ Liste : La liste permet de spécifier les attributs du groupe ainsi que les
différents opérateurs d’agrégation.
• Tri :
Sortliste_attributs
Réda DEHAK 15
Exemples
Select nomrea, min(année) as minannée
From film
Group by nomrea
Having count(titre) >= 3
Πnomrea,minanne ( σcttitre>=3[ γnomrea,
min(année)àminannée, count(titre)àcttitre(film) ] )
Réda DEHAK 16
Exemples
Select distinct nomrea
From film
δ [ Πnomrea ( film ) ]
≠
Πnomrea ( δ (film) )
Réda DEHAK 17
Classification des algorithmes
1. Algorithmes en 1 passe
2. Algorithmes en 2 passes
3. Algorithmes en multi-passes
4. Méthodes classiques
5. Méthodes fondées sur le tri
6. Méthodes fondées sur le hachage
7. Méthodes fondées sur les indexes
Réda DEHAK 18
Étude des performances
• Card( R ) : nombre de tuples de la table R
• B( R ) : nombre de blocs physique de la table R.
• Card( R, A ) : nombre de valeurs différentes contenues
dans R pour l’attribut (s) A.
• M : nombre de blocs mémoires nécessaire.
Réda DEHAK 19
Méthodes classiques
Algorithme en 1 passe pour les
opérateurs unaires
1. Un tuple à la fois :
Condition M = 1
Nbre I/O : B( R )
R
Sélection
Projection
Opérateur
unaire
Buffer d’entrée Buffer de sortie
Réda DEHAK 21
Algorithme en 1 passe pour les
opérateurs unaires
• Élimination des doublons :
Condition B(δ (R) ) < M
Nbre I/O : B( R )
R
Déjà VU?
Buffer d’entrée
Buffer de sortie
M-1 buffers
Réda DEHAK 22
Grouper γ
Condition B(δ (γ<> ( R )) ) < M
Nbre I/O : B( R )
R
Groupe déjà vu?
Buffer d’entrée M-1 buffers
Réda DEHAK 23
Algorithme en 1 passe pour les
opérateurs binaires
• Union :
– Multiset : Évidente (M=1, B(R) + B(S))
– Ensemble.
• Intersection (Multiset, Ensemble).
• Différence (Multiset, Ensemble).
• Produit cartésien.
• Jointure.
Réda DEHAK 24
Algorithme en une passe
Idée : Charger la petite table entièrement en mémoire.
R&S
Traitement
Si Output
buffer
Disk M main memory buffers
Réda DEHAK 25
Algorithme en 1 passe pour les
opérateurs binaires
• Union :
– Multiset : Évidente (M=1, B(R) + B(S))
– Ensemble.
• Intersection (Multiset, Ensemble).
• Différence (Multiset, Ensemble).
• Produit cartésien.
• Jointure.
Condition Min( B(S), B(R) ) < M
Nbre I/O : B( R ) + B(S)
Réda DEHAK 26
Exemple : jointure
• 2 boucles imbriquées (tuples):
Join(R(X,Y), S(Y,Z))
For EACH tuple s IN S DO
FOR EACH tuple r IN R DO
IF r.Y == s.Y then
output join(r,s)
• 2 Possibilités :
1. Pour chaque tuple de S lire toutes les pages de R
Nbre d’IO : B(S) + card(S) * B(R)
2. Pour chaque page de S lire toutes les pages de R
Nbre d’IO : B(S) * (1 + B(R))
Réda DEHAK 27
Algorithme en :
une passe sur R
Plusieurs passe sur S
R&S
Lecture de Output
toutes les buffer
pages de S
Disk M main memory buffers
Réda DEHAK 28
Exemple : jointure
• 2 boucles imbriquées (tuples):
Join(R(X,Y), S(Y,Z))
For EACH tuple s IN S DO
FOR EACH tuple r IN R DO
IF r.Y == s.Y then
output join(r,s)
Condition M=2
Nbre I/O : (1 + B( R )) * B(S)
Réda DEHAK 29
Exemple : jointure
• 2 boucles imbriquées (blocs) :
Join(R(X,Y), S(Y,Z))
Idée : utiliser toute la mémoire disponible pour faire la jointure
décomposer S en plusieurs relations Si (i=1..n) de taille (M-1) blocs
FOR EACH i IN [1..n] DO
lire Si en mémoire (rajouter une structure de recherche pour accélérer la suite)
FOR EACH bloc b OF R DO
lire b en mémoire
FOR EACH tuple t OF b DO
Rechecher les tuples de Si (en mémoire) qui match avec t
output join(r,s)
Réda DEHAK 30
Algorithme en :
une passe sur R
Plusieurs passes sur S
R&S
Si
Lecture de Output
tous Rj buffer
Disk M main memory buffers
Réda DEHAK 31
Exemple : jointure
• 2 boucles imbriquées (blocs):
Join(R(X,Y), S(Y,Z))
Idée : utiliser toute la mémoire disponible pour faire la jointure
décomposer S en plusieurs relations Si (i=1..n) de taille (M-1) blocs
FOR EACH i IN [1..n] DO
lire Si en mémoire (rajouter une structure de recherche pour accélérer la suite)
FOR EACH bloc b OF R DO
lire b en mémoire
FOR EACH tuple t OF b DO
Rechecher les tuples de Si (en mémoire) qui match avec t
output join(r,s)
Condition M>=2
Nbre I/O : B( R ) * B(S) / (M-1)
Réda DEHAK 32
Conclusion
Opérateurs M nécessaire I/O
σ, Π 1 B
γ, δ B B
∩, ∪, -, x, Join Min(B(R), B(S)) B(R) + B(S)
Join ∀≥2 B(R) B(S) /(M-1)
Réda DEHAK 33
Algorithme en 2 passes fondés sur les
méthodes de tri
• Les données sont lues une première fois :
– Elles sont traitées en mémoire
– Transférer vers le disque
• Les données sont lues une deuxièmes fois pour calculer
le résultat
Réda DEHAK 34
Exemples : tri en 2 passes
• Tri fusion :
1. On subdivise R en plusieurs sous ensembles Ri (i=1..n)
2. On trie indépendamment chaque sous relation Ri
3. On fusionne toute les sous relations triées
Réda DEHAK 35
Exemples : tri en 2 passes
R
Trier en fusionnant
Réda DEHAK
M buffers 36
Exemples : tri en 2 passes
• Tri fusion :
1. On subdivise R en plusieurs sous ensembles Ri (i=1..n)
2. On trie indépendamment chaque sous relation Ri
3. On fusionne toute les sous relations triées
Condition B( R ) <= M2
Nbre I/O : 3 B( R )
Réda DEHAK 37
Applications
• L’algorithme peut calculer le résultat des deux
opérateurs δ, γ, en modifiant la deuxième phase.
Condition B( R ) <= M2
Nbre I/O : 3 B( R )
Réda DEHAK 38
Opérateurs binaires
Union :
• Première phase :
– Trier chaque sous relation Ri (taille M blocs) de R en mémoire.
– Trier chaque sous relation Sj (taille M blocs) de S en mémoire.
• Deuxième phase :
– Lire un bloc de chaque sous relation Ri et Sj en mémoire.
– Faire l’union en traitant chaque bloc.
Idem pour ∩, - , Join
Réda DEHAK 39
Jointure en 2 passes fondés sur les
méthodes de tri
deuxième phase
Sorted partitions
of R & S Join Result
Ri
Output
Si buffer
Disk M main memory buffers Disk
Réda DEHAK 40
Opérateurs binaires
Union :
Condition B( R ) + B(S) <= M2
• Première phase :
Nbre
– Trier chaque sous relation Ri (taille M I/O : 3de[ RB(enRmémoire.
blocs) ) + B(S) ]
– Trier chaque sous relation Sj (taille M blocs) de S en mémoire.
• Deuxième phase :
– Lire un bloc de chaque sous relation Ri et Sj en mémoire.
– Faire l’union en traitant chaque bloc.
Idem pour ∩ , - , Join
Réda DEHAK 41
Conclusion
Opérateurs M nécessaire I/O
γ, δ B 3B
∩, ∪, -, x, Join B ( R) + B ( S ) 3(B(R) + B(S))
Join MAX (B( R), B(S )) 5(B(R) + B(S))
Réda DEHAK 42
Algorithme en 2 passes fondés sur les
méthodes de hachage
Idée : Partitionner R et S en (M-1) sous relation avec
une fonction de hachage
Original
Relation OUTPUT Partitions
1
1
INPUT 2
hash 2
function
... h M-1
M-1
Disk M main memory buffers Disk
Réda DEHAK 43
Algorithme en 2 passes fondés sur les
méthodes de hachage
Idée : Partitionner R et S en (M-1) sous relation avec
une fonction de hachage
Partitions
of R & S Join Result
Hash table for partition
hash Ri (k < B-1 pages)
fn
h2
h2
Input buffer Output
for Si buffer
Disk B main memory buffers Disk
Réda DEHAK 44
Conclusion
Opérateurs M nécessaire I/O
γ, δ B 3B
∩, ∪, -, x, Join MIN ( B( R), B( S )) 3(B(R) + B(S))
⎛ 2M ⎞
Join (M>>k) MIN ( B( R), B( S )) ⎜⎜ 3 −
⎝
⎟(B( R) + B( S ) )
MIN ( B( R), B( S )) ⎟⎠
Réda DEHAK 45
Multi-passes
• Algorithme récursif :
– Si B( R ) ≤ M alors charger R en mémoire et effectuer le tri
– Sinon partitionner R en M relations R1,…,RM :
• Trier récursivement chaque Ri.
• Fusionner le résultat
Condition B( R ) <= Mk
Nbre I/O : (2k-1) B( R )
Réda DEHAK 46
Généralisation
Opérateurs M nécessaire I/O
k
γ, δ B (2k-1)B
∩, ∪, -, x, Join k MIN ( B( R), B( S )) (2k – 1) (B(R) + B(S))
Réda DEHAK 47
Conclusions
Opérateurs M nécessaire I/O
γ, δ B 3B
∩, ∪, -, x, Join MIN ( B( R), B( S )) 3(B(R) + B(S))
Opérateurs M nécessaire I/O
k
γ, δ B (2k-1)B
∩, ∪, -, x, Join k MIN ( B( R), B( S )) (2k – 1) (B(R) + B(S))
Réda DEHAK 48
Plan
• Exécution d’une requête
– Étude des différents algorithmes
• Compilation des requêtes :
– Déterminer un plan logique.
– Déterminer le meilleur plan physique.
Réda DEHAK 49
Construction de l’arbre
correspondant au plan logique
Requête
Parser
Préprocesseur
Génération du plan
logique
Réécriture
Meilleur plan logique
Réda DEHAK 50
Construction
SELECT A
FROM <list_B> A
WHERE C
Group by D E
HAVING E
γD+attr(E)
Réda DEHAK List_B 51
Comparaison des plans
B,D B,D
R.A = “c” ∧
S.E = 2 ∧
R.C=S.C
R.A = “c” S.E = 2
x
R S R S
Réda DEHAK 52
Optimisation de l’algèbre relationnel
• Règles de transformations (préserver l’équivalence) :
– Propriétés mathématiques des opérateurs.
• Quelle sont les bonnes transformations?
Réda DEHAK 53
Jointure
R S = S R
(R S) T =R (S T)
T R
R S S T
Réda DEHAK 54
Produit cartésien et Union
• RxS=SxR
• (R x S) x T = R x (S x T)
• RUS=SUR
• R U (S U T) = (R U S) U T
Réda DEHAK 55
Sélection
σp1 [ σp2 (R)] = σp2 [ σp1 (R)]
σp1∧p2(R) = σp1 [ σp2 (R)]
σp1vp2(R) = [ σp1 (R)] U [ σp2 (R)]
Réda DEHAK 56
Projection
• Soit :
– X un ensemble d’attributs
– Y un ensemble d’attributs
ΠXY(R) ≠ ΠX [ΠY (R) ]
Π X [Π Y (R) ] = Π X (R)
Réda DEHAK 57
Sélection, jointure
• p = prédicat avec que des attributs de R
q = prédicat avec que des attributs de S
m= prédicat avec des attributs de R et S
• σ p (R S) = [σp (R)] S
• σ q (R S) = R [σq (S)]
Réda DEHAK 58
Sélection, jointure
• σ p∧q (R S) = [σp (R)] [σq (S)]
• σ p∧q∧m (R S) = σm [ σp (R) σq (S)]
• σ p∨q (R S) = [σp (R) S]
∪ [R σq (S)]
Réda DEHAK 59
Sélection, projection
• Soit :
– x un sous ensemble d’attributs de R
– z l’ensemble des attributs utilisés pour prédicat P (sous
ensemble des attributs de R)
Π x [σp (R)] = Π x { σp [Π xz (R) ] }
Réda DEHAK 60
Projection, jointure
• Soit :
– x un sous ensemble d’attributs de R
– y un sous ensemble d’attributs de S.
– z l’intersection des attributs de R et de S.
Π xy [R S] = Π xy { [Π xz (R)] [Π yz (S)] }
Π xy [σp (R S)] =
Π xy {σp [Π xz’ (R) Π yz’ (S)] }
z’ = z ∪ attributs de P
Réda DEHAK 61
Sélection, union, différence
Union :
σp (R ∪ S) = σp (R) ∪ σp (S)
Différence :
σp (R - S) = σp (R) – S
= σp (R) - σp (S)
Réda DEHAK 62
Les transformations
1. Faire descendre les sélections :
– σp1∧p2 (R) à σp1 [ σp2 (R) ]
– σp1 [ σp2 (R) ] à σp2 [ σp1 (R) ]
– σp [ R S] à [ σp (R) S]
2. Faire descendre les projections :
– Π x [σp (R)] à Π x { σp [Π xz (R) ] }
– Π x [R S] à Π x { [Π xz (R) ] [Π xz (S) ]}
Réda DEHAK 63
Exemples(1)
• Soit le schéma relationnel suivant :
EMP(eid, did, sal, adresse)
Dept(did, dnom, etage, tel)
Budget(did, budget, dépenses, bénéfices)
Soit la requête suivante :
SELECT D.dnom, B.budget
FROM Emp E, Dept D, Budget B
WHERE E.did = D.did AND D.did = B.did AND
D.etage = 1 AND E.sal >= 59000 AND
E.adresse = ‘PARIS’
Réda DEHAK 64
Exemples(2)
On donne les informations suivantes :
– Employe(nom, grade, d_nom, adresse)
– Le nom de l’employé est une clé candidate
– La relation contient 10000 pages : B(employe)=10000
– M = 10
Réda DEHAK 65
suite
1) Soit la requête suivante :
SELECT grade, nom from personne where grade = ‘ING’
On suppose que 10% des tuples de personne vérifient cette
condition
a) En supposant qu’il existe un indexe B+tree plaçant sur l’attribut grade,
donnez le coût (nombre d’E/S) du meilleur plan?
b) Idem avec un indexe non plaçant?
c) Idem avec un indexe plaçant sur l’attribut nom?
d) Idem avec un indexe non plaçant sur l’attribut nom?
Réda DEHAK 66
suite
2) Soit la requête suivante :
SELECT nom from personne where grade = ‘ING’ and d_nom = ‘Prod’
On suppose que :
• 10% des tuples de personne vérifient la condition (grade = ‘ING’)
• 20% des tuples de personne vérifient la condition (d_nom = ‘Prod’)
• 5% des tuples de personne vérifient la condition du select
a) En supposant qu’il existe un indexe B+tree plaçant sur l’attribut grade
(l’unique indexe), donnez le coût (nombre d’E/S) du meilleur plan?
b) Idem avec un indexe plaçant sur d_nom?
c) Idem avec un indexe plaçant sur les attributs (grade, d_nom)?
d) Idem avec un indexe plaçant sur les attributs (grade, nom)?
e) Idem avec un indexe plaçant sur les attributs (d_nom, grade, nom)?
f) Idem avec un indexe plaçant sur les attributs (nom, grade, d_nom)?
Réda DEHAK 67
Suite
3) Soit la requête suivante :
SELECT grade, count(*) from personne group by grade
a) En supposant qu’il existe un indexe B+tree plaçant sur l’attribut grade,
donnez le coût (nombre d’E/S) du meilleur plan?
b) Idem avec un indexe non plaçant?
c) Idem avec un indexe plaçant sur l’attribut nom?
d) Idem avec un indexe plaçant sur les attributs (nom, grade)?
e) Idem avec un indexe plaçant sur les attributs (grade, nom)?
Réda DEHAK 68
suite
4) Soit la requête suivante :
SELECT grade, count(*) FROM personne WHERE d_name > ‘W’ group by grade
On suppose que 10% des tuples d’employe vérifient la condition du where
a) En supposant qu’il existe un indexe B+tree plaçant sur l’attribut grade, donnez
le coût (nombre d’E/S) du meilleur plan?
b) Idem avec un indexe non plaçant?
c) Idem avec un indexe plaçant sur l’attribut d_nom?
d) Idem avec un indexe plaçant sur les attributs (d_nom, grade)?
e) Idem avec un indexe plaçant sur les attributs (grade, d_nom)?
Réda DEHAK 69
Exemples(3)
• Soit le schéma relationnel suivant :
EMP(eid, did, sal, adresse)
Dept(did, dnom, etage, tel)
Budget(did, budget, dépenses, bénéfices)
Soit la requête suivante :
SELECT D.dnom, B.budget
FROM Emp E, Dept D, Budget B
WHERE E.did = D.did AND D.did = B.did AND
D.etage = 1 AND E.sal >= 59000 AND
E.adresse = ‘PARIS’
Réda DEHAK 70
Questions
1. Donner l’arbre optimisé de cette requête?
2. Quelles sont les possibilités pour l’ordre des jointures possibles
3. Supposant qu’on dispose des informations suivantes :
• indexe b+tree non plaçant sur Emp.did, Emp.sal, Dept.etage, Dept.did,
Budget.did.
• Min(Emp.sal)=10000, Max(Emp.sal)= 60000.
• Card(Employe, Adresse) = 200.
• L’entreprise est sur 2 étages.
• On a 50000 employés et 5000 départements.
a) Pour chaque nœud de l’arbre, donner une estimation du nombre de tuples de la
table?
b) Donner l’ordre optimal des jointures?
Réda DEHAK 71
