Upload
virginie-bauer
View
113
Download
0
Embed Size (px)
Citation preview
1
Évaluation des requêtes relationnelles
2
Concepts de base
Décomposition
Requête (ex:SQL)
Schémaconceptuel &
externe
Requête interne
Optimisation
Plan d'exécution
Exécution
Schéma interne &statistiques
BD
Résultats
3
Requête interne
SELECT titre, descripteurFROM Livre, CatégorieWHERE ISBN = 1-111-1111-1 AND Livre.code = Catégorie.code
Livre
{Clé primaire : ISBN}ISBN : CHAR(13)titre : VARCHAR(50)annéeParution : DomaineAnnéenomEditeur : VARCHAR(20)code : VARCHAR(10)
<<table>>
Catégorie
{Clé primaire : code}code : VARCHAR(10)descripteur : VARCHAR(20)codeParent : VARCHAR(10)
<<table>>
codeParent
Livre Catégorie
ISBN = 1-111-1111-1
titre , descrip teur
4
Optimisation statique ou dynamique
• Dynamique
– à chaque exécution
• EXECUTE IMMEDIATE de SQL
• Statique
– compilation
• PREPARE de SQL
– plusieurs exécutions
• EXECUTE
– réoptimisation automatique suite à modification de schéma interne?
5
Décomposition
• 1) Analyse syntaxique
• 2) Analyse sémantique
• 3) Résolution des vues
• 4) Simplification syntaxique
• 5) Simplification sémantique
6
Estimation du coût des opérations physiques
• TempsES : temps d’accès à mémoire secondaire (MS)
• TempsUCT – souvent négligeable
• TailleMC : espace mémoire centrale• TailleMS : espace mémoire secondaire
7
Modèle du coût d'une entrée-sortie en mémoire secondaire
Paramètre Signification TempsESDisque(n) Temps total de transfert (lecture ou écriture) de n octets du disque TempsTrans(n) Temps de transfert des n octets sans repositionnement TempsPosDébut Temps de positionnement au premier octet à transférer (ex : 10 ms) TempsRotation Délai de rotation (ex : 4 ms) TempsDépBras Temps de déplacement du bras (ex : 6 ms) TauxTransVrac Taux de transfert en vrac (ex : 2MB/sec) TempsESBloc Temps de transfert d'un bloc (ex : 11 ms) TempsTrans Temps de transfert d'un bloc sans repositionnement (ex : 1 ms) TailleBloc Taille d'un bloc (ex : 2K octets)
TempsESBloc = TempsESDisque(TailleBloc) = TempsPosDébut + TempsTrans (TailleBloc)TempsTrans (TailleBloc) = TailleBloc / TauxTransVrac
8
Statistiques au sujet des tables
Statistique SignificationNT Nombre de lignes de la table TTailleLigneT La taille d'un ligne de la table TFBT Facteur de blocage moyen de TFBMT Facteur de blocage maximal de T
Estimation :(TailleBloc-TailleDescripteurBloc )/TailleLigneT.
BT Nombre de blocs de la table TEstimation : NT / FBT
9
Statistiques (suite)
Statistique Signification FacteurSélectivitéT (Colonne) Facteur de sélectivité de la colonne
Estimation : 1/ CardT (Colonne) ou 1/10 (constante arbitraire)
FacteurSélectivitéT (Expression) Facteur de sélectivité de l’expression Estimation : FacteurSélectivitéT(Colonne [Valeur1..Valeur2].) = ((Valeur2- Valeur1)/ ( MaxT(Colonne)-MinT (Colonne))) pour Valeur1,Valeur2 [MinT (Colonne)..MaxT (Colonne)] ou 1/2 (constante arbitraire)
SelT (Expression de sélection) Nombre de lignes (cardinalité) de T sélectionnées par l'expression de sélection. Estimation : SelT (Colonne = Valeur )=FacteurSélectivité(Colonne) * NT
10
Statistiques (suite)Statistique SignificationCardT (Colonne): Nombre de valeurs distinctes (cardinalité) de la colonne pour la table TMinT (Colonne): Valeur minimum de la colonne dans la table TMaxT (Colonne): Valeur maximum de la colonne dans la table THauteurI Nombre de niveaux dans l'index ITailleEntréeI Taille d'une entrée dans un bloc interne de l'index
Approximation : taille de la clé d'index + taille pointeur de blocOrdreI Nombre maximum de fils pour un bloc interne de l'index I
Estimation :(TailleBloc-TailleDescripteurBloc)/TailleEntréeI.
OrdreMoyenI Nombre moyen de filsFBMf Nombre maximum de clés qui peuvent être insérées dans une feuille d'un
index arbre-B+
FI Nombre de blocs au niveau des feuilles de l'index ITHT Taille de l'espace d'adressage pour la fonction de hachageM Taille de mémoire centrale disponible en nombre de blocs
11
Maintien des statistiques par le SGBD
• Coût inversement relié à la précision• Mise à jour incrémentale
– à chaque mise à jour
• Mise à jour en différé– périodes de faible activité– déclenchement contrôlé par ABD
• Estimation par échantillonnage– tables très volumineuses
• Commande ANALYSE (Oracle)• contrôle du déclenchement• paramètres d ’échantillonnage
12
Coût des opérations de base
• Algèbre physique• Hypothèses
– Néglige effet de l ’antémémoire– Néglige écriture du résultat– TailleLigne < TailleBloc– Sans interruption
13
Balayage (BAL)
TempsES(BAL)=BT*TempsTrans+NombrePos* TempsPosDébut
Positionnement #1
...
Transfert sans bris de séquence
Positionnement #2
...
Transfert sans bris de séquence
Positionnement #3
...
Transfert sans bris de séquence
14
Exemple : TempsES (BALEditeur)
• Allocation sérielle sans fragmentation interne• FBEditeur = FBMEditeur = 60• BEditeur = NEditeur / FBEditeur = 50/ 60 = 1 bloc• TempsES (BALEditeur) = BEditeur * TempsTrans + NombrePos *
TempsPosDébut
• TempsES (BALEditeur) = 11 ms
NEditeur 50FBMEditeur 60
15
Exemple : TempsES (BALCatégorie)
• Allocation sérielle sans fragmentation interne• FBCatégorie= FBMCatégorie= 40• BCatégorie = NCatégorie / FBCatégorie = 4 000/ 40 = 100
blocs• Meilleur cas :
– TempsES (BALCatégorie) = BCatégorie* TempsTrans + NombrePos * TempsPosDébut
– = 100 * 1 ms + 1 * 10 ms = 110 ms• Pire cas :
– TempsES (BALCatégorie) = 100 * 1 ms + 100 * 10 ms = 1 100 ms
NCatégorie 4 000FBMCatégorie 40
16
Exemple : TempsES (BALLivre)
• Allocation sérielle sans fragmentation interne• FBLivre= FBMLivre= 20• BLivre = NLivre/ FBLivre = 1 000 000/ 20 = 50
000 blocs• Meilleur cas :
– TempsES (BALLivre) = 50,01 secs• Pire cas :
– TempsES (BALLivre) = 9,16 minutes
NLivre 1 000 000FBMLivre 20
17
Exemple : TempsES (BALLivre)
• Arbre-B+ primaire sur la clé primaire ISBN
• FBLivre = 2/3 FBMLivre = 13• BLivre = NLivre/ FBLivre = 1 000 000/ 13 = 76
924 blocs• Pire cas (consécutivité des feuilles non
assurée) !
– TempsES (BALLivre) = BLivre* TempsTrans + NombrePos * TempsPosDébut
– = 76 924* 1ms + 76 924 * 10ms = 848 164 ms = 14,1 minutes
NLivre 1 000 000FBMLivre 20
18
Sélection par égalité dans un index arbre-B+ primaire (S=IP)
• TempsES (S=IP) = – Parcours des niveaux d’index
• (HauteurI -1) * TempsESBloc +
– Parcours des feuilles SelT (CléIndex = Valeur)/ FBT* TempsESBloc
...
...
...
...
.........
Hauteur -1
Feuilles à transférer
19
Suite
• Cas d’une clé candidate– TempsES (S=IP sur clé candidate)=HauteurI *
TempsESBloc
• Estimation de HauteurI
– 1 + log OrdreMoyenI (CardT (CléIndex) / FBT)• OrdreMoyenI = 2/3 OrdreI• FBT = 2/3 FBMT
20
Index primaire code de la table Catégorie (clé primaire )
OrdreMoyenI = 2/3 OrdreI = 66
FBCatégorie = 2/3 FBMCatégorie = 26
HauteurI = 1 + log OrdreMoyenI (CardCatégorie (code) / FBCatégorie)
= 1+ log 66 (4 000 / 26) = 3
TempsES (S=IP) = HauteurI *TempsESBloc = 33 ms
NCatégorie 4 000FBMCatégorie 40CardCatégorie (code) 4 000OrdreI 100
21
Index primaire sur code de la table Livre
(clé étrangère)
OrdreMoyenI = 2/3 OrdreI = 66
FBLivre = 2/3 FBMLivre = 13
HauteurI = 1 + log OrdreMoyenI (CardLivre (code) / FBLivre) = 3
FacteurSélectivitéLivre (code) = 1/ CardLivre (code) = 1/4 000
SelLivre (code = Valeur ) = = 1 000 000/4000 = 250 lignes TempsES (S=IP) =
(HauteurI -1) * TempsESBloc + SelLivre (code = Valeur)/ FBLivre)* TempsESBloc
= 2* 11 ms + ( 250/ 13) * 11 ms = 22 ms +20 * 11 ms = 242 ms
NLivre 1 000 000FBMLivre 20CardLivre(code) 4 000OrdreI 100
22
Index primaire sur ISBN de Livre (clé primaire)
OrdreMoyenI = 2/3 OrdreI = 66
FBLivre = 2/3 FBMLivre = 13
HauteurI = 1 + log OrdreMoyenI (CardLivre (ISBN) / FBLivre) = 4
TempsES (S=IP) = HauteurI *TempsESBloc = 44 ms
NLivre 1 000 000FBMLivre 20CardLivre (ISBN) 1 000 000OrdreI 100
23
Taille de l'index primaire
TailleMS(IP) = TailleIndexInterne + Blivre
FBT = 2/3 FBMT BT = NT/ FBT TailleIndexInterne CardT(CléIndex)/
OrdreMoyenI
24
Index primaire sur code de Livre
FBLivre = 2/3*FBMLivre = 13
BLivre = NLivre/ FBLivre = 1 000 000/ 13 = 76 924
blocs
TailleIndexInterne CardLivre (code)/ OrdreMoyenI
=
61 blocs
TailleMS(IP) = TailleIndexInterne + BLivre 76 985
blocs
50 000 blocs pour allocation sérielle
25
Sélection par égalité dans un index arbre-B+ secondaire (S=IS)
...
...
...
...
.........
Hauteur -1
Feuilles à transférercontenant les références
aux blocs del'organisation primaire
... ...... ... ...Blocs de l'organisation
primaire à transférer...
26
Estimation de TempsES (S=IS)
Niveaux d’index
(HauteurI -1) * TempsESBloc
Feuilles de l ’index SelT (CléIndex = Valeur)/ OrdreMoyenI *TempsESBloc
Blocs de l ’organisation primaire
SelT (CléIndex = Valeur)*TempsESBloc
TempsES (S=IS sur clé candidate)
(HauteurI +1)*TempsESBloc
27
Estimation sans relecture de blocs
Éviter de relire les blocs de données de l ’organisation primaire
Nombre moyen de blocs à lire : (1- (1- FacteurSélectivitéT (CléIndex))FB )*
BT
28
Estimation de HauteurI pour index secondaire
Hypothèses clés répétées
OrdreMoyen = FB
HauteurI =logOrdreMoyenI (NT)
29
Index secondaire code de Livre (clé étrangère)
HauteurI = log66(1 000 000) = 4 SelLivre (code = Valeur )= 250 lignes TempsES (S=IS) = 2 827ms TempsES (S=ISa) = 2 827ms TempsES (S=IP) = 242ms
NLivre 1 000 000FBMLivre 20CardLivre(code) 4 000OrdreI 100
30
Index secondaire sur code de Livre (clé étrangère)
HauteurI = log66(1 000 000) = 4
SelLivre (code = Valeur) = 50 000 lignes TempsES (S=IS) = 558 371ms TempsES (S=ISa) = 361 207ms Pire que TempsES (BALLivre) = 50,01 secs
!
NLivre 1 000 000FBMLivre 20CardLivre(code) 20OrdreI 100
31
Index secondaire sur ISBN de Livre (clé primaire)
HauteurI = log66(1 000 000) = 4 TempsES (S=IS sur clé candidate)
= (HauteurI +1)*TempsESBloc = 55 ms
~TempsES (S=IP) = HauteurI *TempsESBloc = 44 ms
NLivre 1 000 000FBMLivre 20CardLivre (ISBN) 1 000 000OrdreI 100
32
Taille de l'index secondaire
Index secondaire code de Livre (clé étrangère)
TailleMS(IS) = NLivre / OrdreMoyenI = 15 152 blocs ~ 1/3 taille de la table !
TailleMS(IS) (15 152) + BLivre (50 000)< TailleMS(IP) (76 985)
NLivre 1 000 000FBMLivre 20CardLivre(code) 4 000OrdreI 100
33
Sélection par intervalle dans un index arbre-B+ primaire (S>IP)
~ clé non unique CléIndex [Valeur1..Valeur2] TempsES (S>IP) =
(HauteurI -1) * TempsESBloc +
SelT (CléIndex [Valeur1..Valeur2])/ FBT* TempsESBloc
34
Index primaire sur code de la table Livre (clé étrangère)
OrdreMoyenI = 2/3 OrdreI = 66
FBLivre = 2/3 FBMLivre = 13
HauteurI = 3
TempsES (S>IP) = 4 257 ms
NLivre 1 000 000FBMLivre 20CardLivre (code) 4 000SelLivre (code [Valeur1..Valeur2] ) 5 000OrdreI 100
35
Sélection par intervalle dans un index arbre-B+ secondaire (S>IS)
~ clé non unique
36
Sélection par égalité avec hachage (S=H)
Hachage statique + chaînage TempsES (S=H) = NT/( THT* FBT) *
TempsESBloc
...
Adresse dupaquet
0
1
2
3
TH -1
37
Hachage sur ISBN de Livre (clé primaire)
Hypothèse ~ idéale TR = 80% FBLivre = 0,8* FBMLivre = 16
THLivre = NLivre/ FBLivre = 62 500 blocs pas de débordements
TempsES (S=H) = 1 000 000/( 62 500* 16) * 11ms =11 ms
TempsES (S=IP) = HauteurI *TempsESBloc =
44 ms
NLivre 1 000 000FBMLivre 20
38
Hachage sur code de Livre (clé étrangère)
Hypothèse ~ idéale THLivre = CardLivre(code) = 4 000
FBLivre = FBMLivre = 20
NLivre 1 000 000FBMLivre 20CardLivre(code) 4 000
TempsES (S=H) = 1 000 000/( 4 000 * 20) * 11ms = 143 msTempsES (S=IP) = 242 ms
39
Taille de l'organisation par hachage
TailleMS(S=H) = NT/FBT Hachage sur ISBN de Livre (clé
primaire) Hypothèse ~ idéale TailleMS(S=H) = THLivre = NLivre/ FBLivre
= 62 500 blocs
40
Sélection par clé composée
Hypothèse de distribution indépendante
FacteurSélectivitéT(C1 = V1 et C2 = V2 et… et Cn = Vn) = FacteurSélectivitéT (C1)* FacteurSélectivitéT (C2) * …* FacteurSélectivitéT (Cn)
41
Index secondaire sur clé composée {code, annéeParution} de Livre
HauteurI = log33(1 000 000) = 4 FacteurSélectivitéLivre(code = V1 et annéeParution = V2) =
FacteurSélectivitéLivre (code)* FacteurSélectivitéLivre (annéeParution)
= 1/CardLivre (code) * 1/CardLivre (annéeParution) = 1/200 000
SelLivre (code = V1 et annéeParution = V2)= NLivre/ 200 000 = 5 lignes TempsES (S=IS) = (HauteurI - 1) * TempsESBloc +
SelLivre (code = V1 et annéeParution = V2)/ OrdreMoyenI *TempsESBloc +
SelLivre (code = V1 et annéeParution = V2) * TempsESBloc
TempsES (S=IS) = 3 * 11 ms + 5/ 33 *11 ms + 5 * 11 ms = 99 ms
SELECT *FROM LivreWHERE code = unCode AND annéeParution = uneAnnée
NLivre 1 000 000FBMLivre 20CardLivre (code) 4 000CardLivre (annéeParution) 50OrdreI 50
42
Index secondaire sur clé composée {code, annéeParution} de Livre
HauteurI = log33(1 000 000) = 4 TempsES (S=IS) = (HauteurI - 1) * TempsESBloc +
SelLivre ({code, annéeParution} [{unCode, min} .. {unCode, max}])/ OrdreMoyenI *TempsESBloc +
SelLivre ({code, annéeParution} [{unCode, min} .. {unCode, max}]) * TempsESBloc
FacteurSélectivitéLivre({code, annéeParution} [{unCode, min} .. {unCode, max}]) ~ FacteurSélectivitéLivre(code) = 1/4 000
TempsES (S=IS) = 2 827ms (idem index sur code seul)
SELECT *FROM LivreWHERE code = unCode
NLivre 1 000 000FBMLivre 20CardLivre (code) 4 000CardLivre (annéeParution) 50OrdreI 50
43
Index secondaire sur clé composée {code, titre} de Livre
HauteurI = log6(1 000 000) = 8
TempsES (S=IS) = 3 289 ms
SELECT *FROM LivreWHERE code = unCode
NLivre 1 000 000FBMLivre 20CardLivre (code) 4 000OrdreI 10
44
ORGANISATIONS HÉTÉROGÈNES
Adapter les formules facteur de blocage doit tenir compte
de la présence de plusieurs tables
45
TRI D'UNE TABLE (TRI)
Utilité jointure par tri-fusion élimination des doubles (DISTINCT) opérations d ’agrégation (GROUP
BY) résultats triés (ORDER BY)
Tri externe si M est petit tri-fusion
46
Tri fusion externe
Étape tri nombre de groupes = BT /M = 12 /3 = 4 Coût = 2 * ( BT /M * TempsPosDébut + BT *
TempsTrans) = 104 ms
15 4 3
P ositionnem ent
Lecture
Créationde 12/3 =4 groupes
9 18 12
Lecture
P os itionnem ent
16 2 5
Lecture
P os itionnem ent
7 14 6
P ositionnem ent
Lecture
3 4 15
P ositionnem ent
E criture
9 12 18
E criture
P os itionnem ent
2 5 16
E criture
P os itionnem ent
6 7 14
P ositionnem ent
E criture
47
Étape fusion
Coût des passes de fusion = BT*(2*log M-1 (BT /M)-1) * TempsESBloc
= 12*(2*log 2 (12 /3)-1) *11ms = 396 ms
3 4 15 9 12 18 2 5 16 6 7 14
3 4 9 12 15 18 2 5 6 7 14 16
2 3 4 5 6 7 9 12 14 15 16 18
Passe defusion #1
produit 4/2 = 2groupes
Passe defusion #2
produit 2/2 =1groupe
48
Coût total du tri-fusion externe
TempsES (TRI) =
2*(BT /M* TempsPosDébut + BT*TempsTrans) + BT*(2*log M-1 (BT /M)-1) * TempsESBloc
= 104 ms + 396 ms = 500 ms
49
Tri de Livre
Allocation sérielle sans fragmentation interne M = 50
TempsES (TRI) = 29,5 mins
NLivre 1 000 000FBMLivre 20BLivre 50 000
50
SÉLECTION CONJONCTIVE PAR INTERSECTION (S)
Index I1 sur code Index I2 sur annéeParution TempsES(S) =
TempsES(Extraction de la liste des références de I1) +
TempsES(Extraction de la liste des références de I2) +
TempsES(Lecture des blocs de données)
SELECT *FROM LivreWHERE code = unCode AND annéeParution = uneAnnée
NLivre 1 000 000FBMLivre 20CardLivre (code) 4 000CardLivre (annéeParution) 50OrdreI1 100OrdreI2 100
51
Suite
TempsES(Extraction de la liste des références de I1) =
(HauteurI1 - 1) * TempsESBloc + SelLivre (code = Valeur)/ OrdreMoyenI *TempsESBloc = 77 ms
TempsES(Extraction de la liste des références de I2) =
(HauteurI2 - 1) * TempsESBloc + SelLivre (annéeParution = Valeur)/ OrdreMoyenI *TempsESBloc = 3 377 ms
TempsES(Lecture des blocs de données) =
SelLivre (code = V1 et annéeParution = V2)*TempsESBloc = 55 ms
TempsES(S) = 3 509 ms
> TempsES (S=IS pour index I1) = 2 827 ms
52
Si CardLivre (annéeParution) = 100
TempsES(S) = 1809,5 ms < TempsES (S=IS pour index I1) =
2 827 ms
NLivre 1,000,000FBMLivre 20CardLivre (code) 4,000CardLivre (annéeParution) 100OrdreI1 100OrdreI2 100
53
SÉLECTION DISJONCTIVE PAR UNION (S)
FacteurSélectivitéT(C1 = V1 ou C2 = V2 ou… ou Cn = Vn) =
1-((1-FacteurSélectivitéT (C1))*
(1-FacteurSélectivitéT (C2)) * …*
(1-FacteurSélectivitéT (Cn)))
54
OPÉRATIONS DE JOINTURE
Cas de deux tables RS Extension directe à d ’autres cas
union, intersection, jointure externe, ...
55
Jointure par boucles imbriquées
Boucles imbriquées par lignes (BI)
TempsES (BI) = BR * TempsESBloc + NR * (BS * TempsTrans +
TempsPosDébut) Meilleur cas (antémémoire suffisamment grande) :
TempsES (BI) = TempsES (BALR) + TempsES (BALS) = (BR + BS) * TempsTrans + 2*TempsPosDébut
POUR chaque ligne lR de RPOUR chaque ligne lS de S
SI sur lR et lS est satisfait Produire la ligne concaténée à partir de lR et lS
FINSIFINPOUR
FINPOUR
56
BI : Livre Catégorie
R=Livre et S=Catégorie TempsES (BI) = 30,57 hrs
R = Catégorie et S = Livre
TempsES (BI) = 56,57 hrs
Meilleur cas (sans relecture)
TempsES (BI) = 50 120 ms
NLivre 1 000 000FBLivre 20BLivre 50 000
NCatégorie 4 000FBCatégorie 40BCatégorie 100
57
Boucles imbriquées par blocs (BIB)
TempsES (BIB) = BR * TempsESBloc + BR * (BS * TempsTrans + TempsPosDébut)
POUR chaque bloc bR de R POUR chaque bloc bS de S POUR chaque ligne lR de bR
POUR chaque ligne lS de bS
SI sur lR et lS est satisfait Produire la ligne concaténée à partir de lR et lS FINSI
FINPOUR FINPOURFINPOUR
FINPOUR
58
BIB: Livre Catégorie
R=Livre et S=Catégorie TempsES (BIB) = 100,83 mins
R = Catégorie et S = Livre
TempsES (BIB) = 83,37 mins
Meilleur cas (sans relecture)
TempsES (BIB) = 50 120 ms
NLivre 1 000 000FBLivre 20BLivre 50 000
NCatégorie 4 000FBCatégorie 40BCatégorie 100
59
Boucles imbriquées multi-blocs (BIM)
TempsES (BIM) =
BR * TempsTrans + BR/(M-2) * TempsPosDébut + BR/(M-2) * (BS * TempsTrans + TempsPosDébut)
POUR chaque tranche de M-2 blocs de RPOUR chaque bloc bS de S POUR chaque ligne lR de la tranche
POUR chaque ligne lS de bS
SI sur lR et lS est satisfait Produire la ligne concaténée à partir de lR et lS FINSI
FINPOUR FINPOURFINPOUR
FINPOUR
60
BIM: Livre Catégorie
M = 50 R=Livre et S=Catégorie
TempsES (BIM) = 175,04secs
R = Catégorie et S = Livre
TempsES (BIM) = 150,16secs
NLivre 1 000 000FBLivre 20BLivre 50 000
NCatégorie 4 000FBCatégorie 40BCatégorie 100
61
Jointure par boucles imbriquées avec index sur la table interne (BII)
TempsES (BII) = BR * TempsESBloc +
NR * TempsES (Sélection par index)
POUR chaque ligne lR de RPOUR chaque ligne lS de S satisfaisant (sélection en utilisant un index) Produire la ligne concaténée à partir de lR et lSFINPOUR
FINPOUR
62
BII: LivreCatégorie
Cas des index primaires R=Livre et S=Catégorie
TempsES (BII) = BLivre * TempsESBloc + N Livre
* TempsES(S=IPCatégorie pour l'index primaire sur code) = 9,32 hrs
R = Catégorie et S = Livre
TempsES (BII) = B Catégorie * TempsESBloc + N
Catégorie * TempsES(S=IPLivre pour l'index
primaire sur code) = 16,15 mins
NLivre 1 000 000FBLivre 20BLivre 50 000
NCatégorie 4 000FBCatégorie 40BCatégorie 100
TempsES(S=IPCatégorie pour l'index primaire sur code) 33ms
TempsES(S=IPLivre pour l'index primaire sur code) 242ms
63
Contexte avantageuxpour BII
Jointure sélective
Peu de mémoire viveLivre
Catégorie ISBN = 1-11-111-1111-1(Sélection par index
secondaire sur ISBN)
titre , descrip teur(Balayage)
(Boucle imbriquéeavec index secondaire
sur code de la tableinterne Catégorie)
64
Jointure par boucles imbriquées avec hachage sur la table interne (BIH)
TempsES (BIH) = BR * TempsESBloc +
NR * TempsES(Sélection par hachage)
POUR chaque ligne lR de RPOUR chaque ligne lS de S satisfaisant (sélection en utilisant le hachage) Produire la ligne concaténée à partir de lR et lSFINPOUR
FINPOUR
65
BIH: LivreCatégorie
R=Livre et S=Catégorie
TempsES (BIH) = BLivre * TempsESBloc + N Livre * TempsES(S=HCatégorie pour hachage sur code) = 3,21 hrs
R = Catégorie et S = Livre
TempsES (BIH) = BCatégorie * TempsESBloc + NCatégorie* TempsES(S=HLivrepour hachage sur code)= 11,75 mins
TempsES(S=HCatégorie pour hachage sur code) 11ms
TempsES(S=HLivre pour hachage sur code) 176ms
NLivre 1 000 000FBLivre 20BLivre 50 000
NCatégorie 4 000FBCatégorie 40BCatégorie 100
66
Jointure par tri-fusion (JTF)Trier R et S par tri externe et réécrire dans des fichiers temporairesLire groupe de lignes GR(cR) de R pour la première valeur cR de clé de jointureLire groupe de lignes GS(cS) de S pour la première valeur cS de clé de jointureTANT QUE il reste des lignes de R et S à traiter
SI cR = cS
Produire les lignes concaténées pour chacune des combinaisons delignes de GR(cR) et GS(cS);
Lire les groupes suivants GR(cR) de R et GS(cS) de S; SINON SI cR < cS
Lire le groupe suivant GR(cR) de R SINON SI cR > cS
Lire le groupe GS(cS) suivant dans SFINSI
FINSIFINSI
FIN TANT QUE TempsES (JTF) = TempsES (TRIR) + TempsES (TRIS) + 2*(BR +
Bs) * TempsESBloc
67
JTF: LivreCatégorie
M = 50 TempsES (JTF) =
TempsES (TRILivre) + TempsES (TRICatégorie) + 2*(BLivre + BCatégorie) * TempsESBloc = 2 873 540 ms
>>TempsES (BIM) = 150 160 ms (R = Catégorie)
NLivre 1 000 000FBMLivre 20BLivre 50,000TempsES(TRILivre) 1 770 000 ms
NCatégorie 4 000FBMCatégorie 40BCatégorie 100TempsES(TRICatégorie) 1 340 ms
68
Si 100 fois plus de Catégories
M = 50 TempsES (JTF) = 3 444 000 ms
< TempsES (BIM) = 10 464 180 ms
M = 10 TempsES (JTF) = 6 180 000 ms
<< TempsES (BIM) = 62 535 000 ms
NLivre 1 000 000FBMLivre 20BLivre 50,000TempsES(TRILivre) 1 770 000 ms
NCatégorie 400 000FBMCatégorie 40BCatégorie 10 000TempsES(TRICatégorie) 350 000 ms
69
Jointure par hachage (JH)
Égalité seulement 1- Partition des tables (Si h [0..n-1], M ≥ n)
{Partitionner R par hachage}POUR chaque ligne lR de R
Ajouter lR au tampon de Ri où i = h(v) et v est la valeur de l'attribut de jointure de lRSI le tampon de Ri devient plein
Evacuer le tampon de Ri et le chaîner au paquet correspondantFINSI
FINPOUR
{Partitionner S par hachage}POUR chaque ligne lS de S
Ajouter lS au tampon de Si où i = h(v) et v est la valeur de l'attribut de jointure de tSSI le tampon de Si devient plein
Evacuer le tampon de Si et le chaîner au paquet correspondantFINSI
FINPOUR
70
Jointure par hachage (suite)
Jointure par itération sur les parties
TempsES (JH) = TempsES (BALR) + TempsES (BALs) +
2 * (BR + Bs) *TempsESBloc
POUR chaque partie Ri
Lire tous les blocs de la partie Ri
POUR chaque bloc de la partie Si
POUR chaque ligne tS de chaque bloc de Si
Apparier tS avec les lignes correspondantes tR de Ri et produire les lignes concaténées à partir de tR et tS
FINPOURFINPOUR
FINPOUR Hypothèse :
taille de R < taille de S
taille de Ri M blocs
71
Hachage récursif
Si M < Ri (~ BR /M ) hacher récursivement ~log M (BR)-1 passes
ne dépend que de la plus petite table TempsES (JH) =
TempsES (BALR) + TempsES (BALs) +
2 * (BR + Bs) * log M (BR)-1 *TempsESBloc
Si BR M
TempsES (JH) = TempsES (BALR) + TempsES (BALs)
72
JH: LivreCatégorie
R = Catégorie (la plus petite table) M = 50 TempsES (JH) = 1 152 320 ms
>TempsES (BIM) = 150 160 ms (R = Catégorie)
< TempsES (JTF) = 3 444 000 ms
NLivre 1 000 000FBLivre 20BLivre 50 000TempsES (BALLivre) 50 010 ms
NCatégorie 4 000FBCatégorie 40BCatégorie 100TempsES (BALCatégorie) 110 ms
73
Si 100 fois plus de Catégories
R = Catégorie (la plus petite table) M = 50 TempsES (JH) = 2 700 020 ms
<< TempsES (BIM) = 10 464 180 ms (R = Catégorie)
NLivre 1 000 000FBLivre 20BLivre 50 000TempsES (BALLivre) 50 010 ms
NCatégorie 400 000FBCatégorie 40BCatégorie 10 000TempsES (BALCatégorie) 10 010 ms
74
Pré-jointure par une organisation hétérogène (PJ)
Organisation hétérogène sériel par grappe index primaire hachage
TempsES (PJ) ~ TempsES (BALR) + TempsES (BALs) meilleur cas
pas de fragmentation interne...
75
PJ: LivreCatégorie
TempsES (PJ) = 50 120 ms meilleur cas
NLivre 1 000 000FBLivre 20BLivre 50 000TempsES (BALLivre) 50 010 ms
NCatégorie 4 000FBCatégorie 40BCatégorie 100TempsES (BALCatégorie) 110 ms
76
Comparaison des méthodes de jointure
BIM une des deux tables est petite
JTF 2 grandes tables
nombre de passes de tri dépend de la plus grande table ordre intéressant
JH 2 grandes tables nombre de passes ne dépend que de la plus petite table
BII ou BIH utilisation partielle d’une des deux tables
PJ optimal pour jointure si peu de fragmentation interne pénalise opérations sur une table
77
AGRÉGATION, ÉLIMINATION DES DOUBLES, OPÉRATIONS ENSEMBLISTES
Principe général appariement de lignes sur valeurs
communes Adapter les algorithmes de jointure
et estimation de coût
78
Optimisation
Chercher le meilleur plan d ’exécution? coût excessif
Solution approchée à un coût raisonnable Générer les alternatives
heuristiques Choisir la meilleure
estimation approximative du coût
79
Plans d'exécutions équivalents
Plusieurs arbres algébriques équivalents
etc.
Livre Catégorie
ISBN = 1-111-1111-1
titre, descripteur
Livre
Catégorie ISBN = 1-111-1111-1
titre , descrip teur
80
Règles d ’équivalences de l ’algèbre relationnelle
Eclatement d'une sélection conjonctive (SE) e1 ET e2 (T) = e1 ( e2 (T))
Commutativité de la sélection (SC) e1 ( e2 (T)) = e2 ( e1 (T))
Elimination des projections en cascades (PE) liste1 ( liste2 (T)) = liste1 (T)
Commutativité de la jointure (JC) T1T2 = T2T1
Associativité de la jointure (JA) T1 (T2T3) = (T1T2) T3
81
Suite
Commutativité restreinte de la sélection et de la jointure (CSJ)
e (T1 T2) = e (T1) T2
si l'expression de sélection e ne contient que des colonnes de T1
Commutativité restreinte de la projection et de la sélection (CPS)
listeColonnes ( e (T)) = listeColonnes ( e ( listeColonnes colonnes de e T))
Commutativité restreinte de la projection et de la jointure (CPJ)
listeColonnes (T1 T2) =
listeColonnes ( listeColonnes colonnes de T1(T1) listeColonnes colonnes de T2(T2))
etc.
82
Plusieurs plans d ’exécution pour un arbre algébrique
Pour chaque opération logique plusieurs choix d ’opérations physiques
etc.
Livre Catégorie
ISBN = 1-111-1111-1
titre , descrip teur
(Jo inture partri-fusion)
(Balayage)
(Balayage)
L ivre Catégorie
ISBN = 1-111-1111-1
titre , descrip teur
(Jo inture parBIM )
(Balayage)
(Balayage)
L ivre Catégorie
ISBN = 1-111-1111-1
titre , descrip teur
(Jo inture parhachage)
(Balayage)
(Balayage)
83
Mise en œuvre du plan d'exécution
Matérialisation des tables intermédiaires
Pipeline
84
MISE EN ŒUVRE PAR MATÉRIALISATION
Livre
Catégorie
annéeParution = 2000
titre , descrip teur (Balayage)
(Boucle imbriquée parindex secondaire sur
code de la tableinterne Catégorie)
(Sélection par indexsecondaire surannéeParution)
85
MISE EN ŒUVRE PAR PIPELINE
Livre
Catégorie
annéeParution = 2000
titre , descrip teur (Balayage)
(Boucle imbriquée parindex secondaire sur
code de la tableinterne Catégorie)
(Sélection par indexsecondaire surannéeParution)
86
Réalisation des opérations par itérateur
Interface standard Ouvrir
déclenche l’opération Suivant
produit la ligne suivante Fermer
termine l ’opération
Certaines opérations moins adaptées ex: Ouvrir pour le tri-fusion
tri des deux tables…
87
Heuristiques d'optimisation
Élaguer l ’espace des solutions solutions non applicables
Exemples d ’heuristiques sélections le plus tôt possible projections le plus tôt possible arbres biaisés à gauche seulement les jointures plus restrictives en premier jointures supportées par index, hachage ou
grappe en premier
88
Heuristique : arbres biaisés à gauche seulement
Jointure de n tables (2*(n-1))!/(n-1)! ordres différents pour n
tables n! biaisés à gauche
T 1 T 2
T 3
T 4
T 1 T 2 T 3 T 4 T 3 T 4
T 2
T 1
Arbre biaisé à gauche Arbre biaisé à droiteArbre équilibré
89
Optimisation heuristique
Oracle mode RULE
Rang Chemin d'accès1 Sélection par ROWID2 Sélection d'une ligne par jointure dans une organisation par
index groupant ou hachage hétérogène (CLUSTER)3 Sélection d'une ligne par hachage sur clé candidate
(PRIMARY ou UNIQUE)4 Sélection d'une ligne par clé candidate5 Jointure par une organisation par index groupant ou
hachage hétérogène (CLUSTER)6 Sélection par égalité sur clé de hachage (HASH CLUSTER)7 Sélection par égalité sur clé d'index groupant (CLUSTER)8 Sélection par égalité sur clé composée9 Sélection par égalité sur clé simple d'index secondaire10 Sélection par intervalle borné sur clé indexée11 Sélection par intervalle non borné sur clé indexée12 Tri-fusion13 MAX ou MIN d'une colonne indexée14 ORDER BY sur colonne indexée15 Balayage
90
Optimisation par coût
Minimiser le coût Stratégies
programmation dynamique amélioration itérative recuit simulé algorithme génétique
91
ESTIMATION DU COÛT D'UN PLAN D'EXÉCUTION
Livre Catégorie
(Jointure par tri-fusionTem psES = 2 873 540 ms)
(BalayageTem psES = 92 314 ms)
ISBN = 1-111-1111-1
titre , descrip teur
(Ecriture du résultatTem psES = 846 164 ms)
(Ecriture du résultatTem psES = 11 ms)
(BalayageTem psES = 11 ms)
Coût total =3 812 040ms
TempsES(Plan avec pipeline) = TempsES (JTFLivreCatégorie) = 2 873 540 ms
92
Autre exemple
Livre
Catégorie
titre , descrip teur
(Boucle imbriquée parindex secondaire sur
code de la tableinterne Catégorie
Tem psES = 44ms)
ISBN = 1-11-111-1111-1 (Sélection par indexsecondaire sur ISBNTem psES = 55ms)
(Ecriture du résultatTem psES = 11ms)
(Ecriture du résultatTem psES = 11 ms)
(BalayageTem psES = 11 ms)
Coût total =132ms
TempsES(Plan avec pipeline) =
TempsES(S=IS pour index sur ISBN) +
N ISBN=1000 Œuvre * TempsES(S=IS sur code de Catégorie)
= 55 ms + 33 ms = 88 ms
93
ESTIMATION DE LA TAILLE DU RÉSULTAT D'UNE OPÉRATION
Taille d'une sélection SelT (Expression de sélection)/ FBMT blocs
Taille d'une projection N C1,C2,…,Cn(T) = (1- colonnes Ci de la projection (1-
FacteurSélectivitéT (Ci)))*NT
Taille d'une jointure naturelle NR S = NR * NS /
maximum(CardR(cléJointure), CardS(cléJointure))
94
VARIATIONS DU MODÈLE D'ESTIMATION DU COÛT
Simplification nombre de blocs à transférer
Jointures taille du résultat
Contexte réparti seulement coût de transfert entre sites
Hypothèses sur distributions Coût UCT
95
Contrôle du processus d'optimisation
Cas Oracle outils
EXPLAIN PLANSQL TraceOracle EXPERT
HINTS pour forcer l ’utilisation d ’un chemin
SELECT /*+ INDEX(EMPLOYÉ INDEX_SEXE)*/
FROM EMPLOYÉ WHERE SEXE = ‘F’
96
Exemple d ’utilisation de EXPLAIN PLAN
SQL> start utlxplan.sql Pour créer la table plan_tableTable created....SQL> run 1 explain plan 2 set statement_id = 'com' 3 for select * from commandes, lignes_de_commande 4* where no_commande = commande_no_commande
Explained.
97
Suite
SQL> run 1 SELECT LPAD(' ',2*(LEVEL-1))||operation||' '||options 2 ||' '||object_name 3 ||' '||DECODE(id, 0, 'Cost = '||position) "Query Plan" 4 FROM plan_table 5 START WITH id = 0 AND statement_id = 'com' 6* CONNECT BY PRIOR id = parent_id AND statement_id ='com'
Query Plan---------------------------------------------SELECT STATEMENT Cost = NESTED LOOPS TABLE ACCESS FULL LIGNES_DE_COMMANDE TABLE ACCESS BY ROWID COMMANDES INDEX UNIQUE SCAN COMMANDE_PK
98
Paramètre OPTIMIZER_MODE
COST (statistique): minimise le coût estimé besoin de statistiques (ANALYSE) plus précis plus coûteux
RULE (heuristique) appelé à disparaître ?
99
OPTIMIZER_GOAL
ALTER SESSION SET OPTIMIZER_GOAL = RULE ALL_ROWS minimise le temps total (plutôt MERGE
JOIN) FIRST_ROWS minimise temps réponse (plutôt
NESTED LOOPS) CHOOSE