]>
...
Optimisation
Bibliographie
HopSlide Help (v2.5.3)
Keyboard
Toggle this help
alt-h
Reload slides
alt-r
Toggle slide selector
alt-s
alt-t
Open a full screen window
alt-w
Update size
alt-u
Toggle big cursor
alt-m
Toggle focus
alt-f
Toggle drawing area
alt-c
Next slide
PgDn
↓
Ret
Enter
Space
Previous slide
PgUp
↑
alt-p
First slide
Home
Last slide
End
Close slide
Esc
Mouse
Reload slides
shift Button1
Slides selector
crtl Button1
Focus enlarge/shrink
Button4
Button5
gnF36H4J1T8H7pFAAHEONDdc4AAAwCErwrFI1ExuQAAAABJRU5ErkJggg==
f83cyUw3hWh3qTYCQABBgAAGnnjiX1UpQAAAABJRU5ErkJggg==
oTQwvEAAAAASUVORK5CYII=
PQpAYQAAxDnTnFCCABrxzChBAA+4AgAADAN6IbfrsVDB3AAAAAElFTkSuQmCC
AeHxm5gUXjm4ZPP+Q8ff4oDRs9WoNhLjCru939IIxUNAAQQ40B3TgECaMD7hgABNOAOAAgwAOIo9yyRalo+AAAAAElFTkSuQmCC
z+V8PIw8L0n4kxGSh6B6NjAmohs0D0oXdMAAKIcaA7pwABNOB9Q4AAGnAHAAQYABaU9vBbRzekAAAAAElFTkSuQmCC
ADi8NuBl72pcAE+htbHicGAAQQ40B3TgECaMD7hgABNOAOAAgwANtDcqAqYx6xAAAAAElFTkSuQmCC
ARPp5s07HsgBLdwOTGiNwIR5C+xYbOAn1rgHRegOIH4LEwAIIMaB7pwCBNCA9w0BAmjAHQAQYABMAqbWGPAKOwAAAABJRU5ErkJggg==
IRyAEAAcQ40D0jgAAa8FYxQAANuAMAAmjAHQAQQAPuAIAAGnAHAAQYAOJ5EYdTDOvTAAAAAElFTkSuQmCC
gEQYAA1+Dm3GSWUswAAAABJRU5ErkJggg==
iTECIIAocwAEAPMcgzIQc0Lz+EtCwY4MAAIMAFAjCls0Uia9AAAAAElFTkSuQmCC
+MpwGSoPwffRsRggABBBJDoAFBhDLg1q0oEIX6ltQyfaDnM4pQAAxDnT3HCDAANr5Kk2SE6QoAAAAAElFTkSuQmCC
0xM+w0gwAANGVpo2ifr1AAAAABJRU5ErkJggg==
KP8B4jPBcKUstbkAAAAASUVORK5CYII=
QaClO4HqHkJKReQmN6YDAAKIcaB7xwABNOC9Y4AAAwAOHvV3Gx3bfwAAAABJRU5ErkJggg==
big-pointer.png
Fonctionnement d'un SGBD
I. Mirbel et P. Crescenzo
M1 MIAGE 2011/2012
Optimisation
Fonctionnement d'un SGBD
Introduction
Les transactions
La concurrence
La gestion de la mémoire tampon
La fiabilité
Les structures d'accès physiques
L'optimisation
Bibliographie
L'optimisation de requêtes
1. Introduction
2. Optimisation algébrique
3. Optimisation basée sur les coûts
Introduction
Optimisation
  • Une Introduction à l'optimisation de requêtes
  • Langages
    • Procéduraux (modèle réseaux) : optimisation utilisateur
    • Assertionnnels (SQL) : optimisation SGBD
  • Deux techniques d'optimisation
    • Expressions algébriques : transformation des requêtes
    • Opérations algébriques : évaluation des coûts des différentes stratégies
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/124 of 68
Introduction (suite)
Optimisation
Organisation de l'optimisation
image/svg+xml Requête Analyse lexicale,synthaxique & sémantique Optimisationalgébrique Optimisationbasée surles coûts Plan d'exécution Dépendences Profils Catalogue
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/125 of 68
L'optimisation de requêtes
1. Introduction
2. Optimisation algébrique
a. Introduction
b. Les opérateurs
c. Algorithme
d. Un exemple
3. Optimisation basée sur les coûts
Optimisation algébrique
Optimisation
image/svg+xml RequêteSQL Traduction Requêteoptimisée Requêtealgébrique Transformation en fonctiondes propriétés des opérateurs
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/127 of 68
L'optimisation de requêtes
1. Introduction
2. Optimisation algébrique
a. Introduction
b. Les opérateurs
c. Algorithme
d. Un exemple
e. Conclusion
3. Optimisation basée sur les coûts
Rappel notation algèbre relationnelle
Optimisation
  • Sélection : σ p (R)
  • Projection : π [attrs] R
  • Renommage : α [nom:nouv-nom] R
  • Produit cartésien : R 1 × R 2
  • Jointure naturelle : R 1 ∞ R 2
  • Theta-jointure : R 1 ∞ p R 2
  • Union : R 1 ∪ R 2
  • Intersection : R 1 ∩ R 2
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/129 of 68
Rappel notation algèbre relationnelle (suite)
Optimisation
  • Différence : R 1 - R 2
  • Division : R 1 / R 2
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1210 of 68
Propriétés des opérateurs
Optimisation
  • Commutativité pour jointures et pour produits cartésiens
    • E 1 ∞ f E 2 ≡ E 2 ∞ f E 1
    • E 1 ∞ E 2 ≡ E 2 ∞ E 1
    • E 1 × E 2 ≡ E 2 × E 1
  • Associativité pour jointures et pour produits cartésiens
    • (E 1 ∞ f2 E 2) ∞ f1 E 3 ≡ E 1 ∞ f2 (E 2 ∞ f1 E 3)
    • (E 1 ∞ E 2) ∞ E 3 ≡ E 1 ∞ (E 2 ∞ E 3)
    • (E 1 × E 2) × E 3 ≡ E 1 × (E 2 × E 3)
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1211 of 68
Propriétés des opérateurs (suite)
Optimisation
  • Cascades de projections
    • π A1,...,An( πB1,...,Bm(E)) ≡ π A1,...,An(E)
      • ⇒{A1,...,An} inclus dans {B1,..,Bm}
        • π[matr, nom](π[dept] Emp)⇒ ko
        • π[matr, nom](π[matr, nom, dept] Emp)⇒ ok
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1212 of 68
Propriétés des opérateurs (suite)
Optimisation
  • Cascade de sélections
    • σ f1 ( σ f2 (E)) ≡ σ f1 ∧ f2 (E)
  • Inversion σ et π
    • π A1,...,An ( σ F (E)) ≡ σ F ( π A1,...,An (E))
      • si F porte sur A1,...,An
    • π A1,...,An ( σ F (E)) ≡ π A1,...,An ( σ F ( π A1,...,An,B1,...,Bm (E)))
      • si F porte sur B1,...,Bm qui ne sont pas parmi A1,...,An
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1213 of 68
Propriétés des opérateurs (suite)
Optimisation
  • Exemples
    • π[matr,nom]σ nom='dupont' (Emp) ≡ σ nom='dupont' π[matr,nom] (Emp)
    • π[matr,nom]σ dept='30' (Emp) ≡ σ dept='30' π[matr,nom,dept] (Emp)
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1214 of 68
Propriétés des opérateurs (suite)
Optimisation
  • Inversion σ et ×
    • σ F (E1 × E2) ≡ σ F (E1) × E2 si F ne porte que sur attributs de E1
    • σ F (E1 × E2) ≡ σ F1 (E1) × σ F2 (E2) si F ≡ F1 ∧ F2 et Fi ne porte que sur attributs de Ei
    • σ F (E1 × E2) ≡ σ F2 ( σ F1 (E1) × E2) si F1 porte sur attributs de E1 et F2 sur ceux de E1 et E2
  • Exemple
    • σ dept='10' (Emp × Projet) ≡ σ dept='10' (Emp) × Projet
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1215 of 68
Propriétés des opérateurs (suite)
Optimisation
  • Inversion σ et ∪
    • σ F (E1 ∪ E2) ≡ σ F(E1) ∪σ F(E2)
  • Inversion σ et -
    • σ F(E1 - E2) ≡ σ F(E1) - σ F(E2)
  • Inversion σ et ∞
    • σ F(E1 ∞ E2) ≡ σ F(E1) ∞ σ F(E2)
    • Si F porte que les attributs partagés par E1 et E2
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1216 of 68
Propriétés des opérateurs (fin)
Optimisation
  • Inversion π et ×
    • π A1...An (E1 × E2) ≡ π B1...Bm (E1) × π C1...Ck (E2)
    • si dans A1,...,An, {B1,...,Bm} ∈ E1, {C1,...,Cm} ∈ E2
  • Inversion π et ∪
    • π A1...An (E1 ∪ E2) ≡ π A1...An (E1) ∪π A1...An (E2)
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1217 of 68
L'optimisation de requêtes
1. Introduction
2. Optimisation algébrique
a. Introduction
b. Les opérateurs
c. Algorithme
d. Un exemple
e. Conclusion
3. Optimisation basée sur les coûts
Un algorithme d'optimisation
Optimisation
  • 1. Séparer chaque sélection σ F1 ∧ .. ∧ Fn (E) en une cascade σF1(σF2...(σFn(...E)))
  • 2. Descendre chaque sélection le plus bas possible dans l'arbre
  • 3. Descendre chaque projection aussi bas que possible dans l'arbre
  • 4. Combiner des cascades de sélections et de projections dans une sélection seule, une projection seule, ou une sélection suivie par une projection
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1219 of 68
Un algorithme d'optimisation (suite)
Optimisation
  • 5. Regrouper les noeuds interieurs de l'arbre autour des opérateurs binaires (×, ∪, -). Chaque opérateur binaire crée un groupe
  • 6. Produire un programme comportant
    • une étape pour chaque groupe,
    • à évaluer dans n'importe quel ordre
    • Tel qu'aucun groupe ne soit évalué avant ses groupes descendants
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1220 of 68
L'optimisation de requêtes
1. Introduction
2. Optimisation algébrique
a. Introduction
b. Les opérateurs
c. Algorithme
d. Un exemple
e. Conclusion
3. Optimisation basée sur les coûts
Exemple d'optimisation
Optimisation
  • Livre(ISBN, titre, auteur, éditeur)
  • Prêt(n°carteP, ISBNP, date)
  • Lecteur(n°carte, nom, adresse)
Liste des noms des lecteurs et des titres des livres pour tous les prêts avant le 18.12.2006 ?
  • π [nom,titre]
    • σ [ date ≤ 18.12.2006]
    • σ [n°carte = n°carteP ∧ ISBN = ISBNP]
      • (Pret × Lecteur × Livre)
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1222 of 68
Exemple d'optimisation (suite)
Optimisation
Après décomposition des sélections
image/svg+xml X X Prêt Lecteur Livre [nom,titre] [date < 18.12.2006] [N°carte = N°carteP] [ISBN = ISBNP]
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1223 of 68
Exemple d'optimisation (suite)
Optimisation
Après descente des sélections
image/svg+xml X X Prêt Lecteur Livre [nom,titre] [date < 18.12.2006] [N°Carte = N°CarteP] [ISBN = ISBNP]
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1224 of 68
Exemple d'optimisation (suite)
Optimisation
Ajout des projections
image/svg+xml X X Prêt Lecteur Livre [nom,titre] [date < 18.12.2006] [N°carte = N°carteP] [ISBN = ISBNP] [ISBNP,nom] [ISBN,titre] [N°carteP,ISBNP] [N°carte,nom]
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1225 of 68
Exemple d'optimisation (suite)
Optimisation
Résultat
image/svg+xml X X Prêt Lecteur Livre [nom,titre] [date < 18.12.2006] [N°Carte = N°CarteP] [ISBN = ISBNP]
  • G1=(σ[date ≤ 18.12.2006] Prêt) ∞ [N°Carte=N°CarteP] Lecteur
  • π[nom,titre](G1 ∞ [ISBN=ISBNP] Livre)
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1226 of 68
L'optimisation de requêtes
1. Introduction
2. Optimisation algébrique
a. Introduction
b. Les opérateurs
c. Algorithme
d. Un exemple
e. Conclusion
3. Optimisation basée sur les coûts
Optimisation algébrique et optimisation des coûts
Optimisation
  • Optimisation logique insuffisante pour un plan d'exécution de coût minimal
    • ⇒Une opération algébrique peut donner plusieurs opérations physiques
    • ⇒Plusieurs opérations algébriques peuvent être réalisées en même temps par une seule opération physique
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1228 of 68
Optimisation algébrique et optimisation des coûts (suite)
Optimisation
  • Exécution d'une requête ⇒ plan d'exécution physique combinant des opérations physiques sur les données
    • Dépend des chemins d'accès et de la taille et du nombre des pages en mémoire centrale
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1229 of 68
L'optimisation de requêtes
1. Introduction
2. Optimisation algébrique
3. Optimisation basée sur les coûts
a. Les profils
b. Représentation interne des requêtes
Le balayage
Les index
La jointure
c. L'optimisation des coûts
Profils des relations
Optimisation
  • Profils des relations :
    • Informations quantitatives sur les caractéristiques des tables
    • Stockées dans le dictionnaire
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1231 of 68
Profils des relations (suite)
Optimisation
  • Les informations :
    • Cardinalité CARD(T) de chaque table T : nombre de tuples
    • Dimension (en octets) SIZE(T) de chaque tuple de T
    • Dimension (en octets) SIZE(Aj,T) de chaque attribut Aj dans T
    • Le nombre de valeurs distinctes VAL(Aj,T), de chaque attribut Aj dans T
    • Les valeurs minimum et maximum MIN(Aj,T) et MAX(Aj,T) de chaque attribut Aj dans T
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1232 of 68
Profils des relations (fin)
Optimisation
  • Commande update statistics activée par l'administrateur système pour calculer ces informations
  • L'optimisation basée sur les coûts nécessite la formulation d'hypothèses sur la taille des résultats intermédiaires produits par l'évaluation statistique des opérateurs algébriques
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1233 of 68
Profils des principaux opérateurs algébriques
Optimisation
  • Sélection : T' = σ Ai = v (T)
    • CARD(T') = (1/VAL(A i)) × CARD(T)
    • SIZE(T') = SIZE(T)
    • VAL(Ai, T') = 1
    • VAL(Aj, T') = col(CARD(T), VAL(Aj,T), CARD(T')), pour j ≠ i
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1234 of 68
Profils des principaux opérateurs algébriques (suite)
Optimisation
  • col(n,m,k) calcule le nombre de valeurs distinctes présentes dans les k objets extraits, en partant de n objets de m valeurs distinctes distribuées de façon homogène. On a les approximations suivantes :
    • col(n,m,k) = k si k ≤ m/2
    • col(n,m,k) = (k+m)/3 si m/2 ≤ k ≤ 2m
    • col(n,m,k) = m si k ≥ 2m
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1235 of 68
Profils des principaux opérateurs algébriques (suite)
Optimisation
  • Sélection (suite) : T' = σ Ai = v (T)
    • MAX(Ai, T') = MIN(Ai,T') = v
    • MAX(Aj, T') et MIN(Aj,T') conservent les mêmes valeurs que MAX(Aj, T) et MIN(Aj,T) pour j ≠ i
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1236 of 68
Profils des principaux opérateurs algébriques (suite)
Optimisation
  • Projection : T' = π A1, A2,..., An (T)
    • CARD(T') = MIN(CARD(T), π A1, A2,..., An VAL(Ai, T))
    • SIZE(T') = ∑ n i=1 SIZE(A i (T))
    • VAL(Ai, T'), MAX(Ai,T'), MIN(Ai,T') conservent les mêmes valeurs que VAL(Ai, T), MAX(Ai,T), MIN(Ai,T)
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1237 of 68
Profils des principaux opérateurs algébriques(suite)
Optimisation
  • Jointure : T' = T 1 ∞ a=b T 2 avec VAL(A,T1) = VAL(A,T2)
    • CARD(T') = (1/VAL(Ai,T1)) × CARD(T1) × CARD(T2)
    • SIZE(T') = SIZE(T 1) + SIZE(T 2)
    • VAL(Ai, T'), MAX(Ai,T'), MIN(Ai,T') conservent les mêmes valeurs que les relations avant la jointure
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1238 of 68
Profils des principaux opérateurs algébriques(fin)
Optimisation
  • Limites de cette approche statistique
    • Distribution uniforme des données dans les tables
    • Les formules qui portent sur le résultat d'une opération supposent des paramètres identiques à ceux des opérandes
    • ...
    • ⇒Utile pour évaluer la dimension des résultats intermédiaires
Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1239 of 68
L'optimisation de requêtes
1. Introduction
2. Optimisation algébrique
3. Optimisation basée sur les coûts
a. Les profils
b. Représentation interne des requêtes
Le balayage
Les index
La jointure
c. L'optimisation des coûts
Représentation interne des requêtes
Optimisation
Représentation de la requête donnée par l'optimiseur prend en compte
  • Les structures physiques utilisées pour implanter les tables
  • Les index
  • ⇒Représentation sous forme d'arbre dont
    • Les feuilles sont les structures de données physiques
    • Les noeuds intermédiaires représentent les opérations d'accès aux données supportées par les structures de données
      • Balayage séquentiel / ordonnancement
      • Accès aux index
      • jointures diverses
    • Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1241 of 68
    L'optimisation de requêtes
    1. Introduction
    2. Optimisation algébrique
    3. Optimisation basée sur les coûts
    a. Les profils
    b. Représentation interne des requêtes
    Le balayage
    Les index
    La jointure
    c. L'optimisation des coûts
    Opération de balayage
    Optimisation
    • Accès séquentiel à tous les tuples de la table en exécutant diverses opérations algébriques ou non-algébriques
      • Projections
      • Sélections simples (du type A i = v)
      • Tris des tuples de la table à partir des valeurs d'un attribut présent dans un ensemble ordonné d'attributs
      • Insertion, suppression et modification de tuples accédés pendant le balayage
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1243 of 68
    Opération de balayage (suite)
    Optimisation
    • Opération de balayage (suite)
      • Un pointeur sur le tuple courant est maintenu pendant le balayage
      • Les primitives dédiées au balayage
        • open
        • next
        • read
        • modify, delete
        • insert
        • close
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1244 of 68
    Opération de tri
    Optimisation
    • Opération de tri
      • cf théorie algorithmique (tri d'un tableau en mémoire centrale)
      • Problème supplémentaire : chargement des données en mémoire et nécessité parfois de trier des portions de données séparemment pour les fusionner ensuite
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1245 of 68
    L'optimisation de requêtes
    1. Introduction
    2. Optimisation algébrique
    3. Optimisation basée sur les coûts
    a. Les profils
    b. Représentation interne des requêtes
    Le balayage
    Les index
    La jointure
    c. L'optimisation des coûts
    Accès aux index
    Optimisation
    • Créés par l'administrateur pour améliorer les performances de requêtes
      • incluant des prédicats simples (du type A i = v)
      • portant sur des intervalles
    • ⇒Pédicat supporté par l'index
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1247 of 68
    Utilisation des index
    Optimisation
    • Si un seul prédicat supporté dans la requête
      • Utiliser cet index
    • Si la requête contient une conjonction de prédicats supportés par plusieurs index
      • Choisir le prédicat le plus sélectif pour l'accès primaire
      • Vérifier les autres prédicats sur les pages chargées en mémoire
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1248 of 68
    Utilisation des index (suite)
    Optimisation
    • Si la requête contient une disjonction de prédicats
      • Si l'un des prédicats n'est pas supporté par un index
        • ⇒balayage séquentiel
      • S'ils sont tous supportés
        • ⇒index ou balayage séquentiel
          image/svg+xml
          supprimer les tuples dupliqués parce que présents dans plusieurs index
          image/svg+xml
          Les accès multiples peuvent s'avérer plus coûteux qu'un balayage
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1249 of 68
    L'optimisation de requêtes
    1. Introduction
    2. Optimisation algébrique
    3. Optimisation basée sur les coûts
    a. Les profils
    b. Représentation interne des requêtes
    Le balayage
    Les index
    La jointure
    c. L'optimisation des coûts
    Méthodes de jointure
    Optimisation
    • Opérateur le plus coûteux
    • Risque d'explosion du nombre de tuples dans le résultat
        • image/svg+xml
        Bien définir la méthode de jointure
        image/svg+xml
        Bien choisir l'ordre des jointures
    • Trois techniques de jointures
      • Boucles imbriquées
      • Tri et fusion (ou balayage et fusion)
      • Hashage
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1251 of 68
    Jointure par boucles imbriquées
    Optimisation
    • Balayage d'une des deux tables (table externe)
    • Récupération de la valeur de l'attribut de jointure pour chaque tuple sélectionné dans la table externe
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1252 of 68
    Jointure par boucles imbriquées (suite)
    Optimisation
    • Recherche dans l'autre table, table interne, des tuples correspondant aux valeurs collectées dans la table externe
      • Avec index: Plus efficace si index sur attribut de jointure dans la table interne ⇒ création ad-hoc
      • Sans index : Balayage de la table interne pour chaque valeur de jointure
      image/svg+xml
      Coûts différents suivant la table sélectionnée comme table interne et comme table externe
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1253 of 68
    Jointure par boucles imbriquées (suite)
    Optimisation
    image/svg+xml Table externe Table interne JA a JA a a a Balayageexterne Balayageinterne ou accès indexé
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1254 of 68
    Jointure par tri et fusion (ou balayage et fusion)
    Optimisation
    • Nécessite que les deux tables soient ordonnées sur l'attribut de jointure
    • Consiste en la réalisation de 2 balayages coordonnés
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1255 of 68
    Jointure par tri et fusion (ou balayage et fusion)
    Optimisation
    image/svg+xml Table de gauche Table de droite JA JA Balayages droit gauche aabcdeff abbbcdde
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1256 of 68
    Jointure par hashage
    Optimisation
    • Nécessite qu'une fonction de hashage ait été définie sur l'attribut de jointure dans les deux tables
      • ⇒La fonction h décompose le domaine des attributs sur lesquels porte la jointure en B partitions dans chaque table
    • Les tuples résultats de la jointure vont donc être trouvés en faisant B jointures entre les partitions de numéros équivalents dans les deux tables
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1257 of 68
    Jointure par hashage (suite)
    Optimisation
    • Plusieurs versions de cette technique existent afin d'optimiser encore les performances
      • Choix de la fonction de hashage
      • Gestion des tampons en mémoire centrale
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1258 of 68
    Jointure par hashage (suite)
    Optimisation
    image/svg+xml Table droite Table gauche JA JA deac emaa jj jz .. hash(a) .. .. .. a hash(a) ..
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1259 of 68
    L'optimisation de requêtes
    1. Introduction
    2. Optimisation algébrique
    3. Optimisation basée sur les coûts
    a. Les profils
    b. Représentation interne des requêtes
    c. L'optimisation des coûts
    Optimisation basée sur les coûts
    Optimisation
    • L'optimisation globale dépend
      • Du choix des opérations d'accès aux données
        • ⇒balayage / index par exemple
      • De l'ordre dans lequel les opérations sont effectuées
        • ⇒ordre des différentes jointures dans une requête par exemple
      • De l'option d'exécution d'une opération quand il y en a plusieurs
        • ⇒choix de la méthode de jointure
      • De l'ordre d'exécution (niveau dans le plan d'exécution) si nécessaire
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1261 of 68
    Optimisation basée sur les coûts (suite)
    Optimisation
    • ⇒Utilisation de formules de coûts approximatifs
    • ⇒Construction d'arbres de décision
      • Chaque feuille correspond à un plan d'exécution dont les choix sont décrit dans les noeuds de la racine à la feuille
      • L'optimisation consiste à chercher la feuille correspondant au coût le plus bas
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1262 of 68
    Optimisation basée sur les coûts (suite)
    Optimisation
  • Exemple : exécution d'une requête conjonctive (uniquement des sélections, des projections et de jointures) sur 3 tables et avec 2 jointures
    • Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1263 of 68
    Optimisation basée sur les coûts (suite)
    Optimisation
  • Exemple : exécution d'une requête conjonctive (uniquement des sélections, des projections et de jointures) sur 3 tables et avec 2 jointures
    • image/svg+xml R S T 1 2 (R S) T 1 2 (R T) S 1 2 (S T) R 1 2 bouclesimbriquées R interne R externe fusion-balayage hashage 1 bouclesimbriquées 1 1 1 bouclesimbriquées T interne T externe fusion-balayage hashage 2 bouclesimbriquées 2 2 2 Stratégie 1 Stratégie 2 Stratégie 3 Stratégie 4 3 façons d'ordonner les jointures4 façons de réaliser les jointures=> 48 options
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1264 of 68
    Optimisation basée sur les coûts (suite)
    Optimisation
    • Evaluation en fonction du coût
      • Des opérations d'entrée / sortie
      • Des instructions CPU nécessaires à l'évaluation de chaque opération
    • Coût d'une feuille
      C total = C I/O x n I/O + C cpu x n cpu
      • C I/O et C cpu : paramètres connus
      • n I/O et n cpu : valeurs globales
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1265 of 68
    Optimisation basée sur les coûts (suite)
    Optimisation
    • Coût : somme de tous les coûts relatifs aux opérations qui constituent le plan d'exécution
    • Recherche d'une solution optimale par élimination des solutions correspondant à des sous-arbres dont le coût partiel est supérieur au coût de la stratégie globale (algorithme branch and bound)
    • Les résultats intermédiaires
      • souvent stockés dans un tampon.
      • si stockés en mémoire secondaire, le coût d'écriture doit faire partie de la stratégie
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1266 of 68
    Bibliographie
    Fonctionnement d'un SGBD
    Introduction
    Les transactions
    La concurrence
    La gestion de la mémoire tampon
    La fiabilité
    Les structures d'accès physique
    L'optimisation
    Bibliographie
    Bibliographie
    Bibliographie
    • Database Systems: The Complete Book. Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer D. Widom. Prentice Hall (October 2001), ISBN: 0130319953
    • Database Systems : concepts, languages and architectures. Paolo Atzeni, Stefano Ceri, Stefano Parabosci, Riccardo Torlone. McGraw-Hill Publishing Co. (April 1999), ISBN: 0077095006
    Fonctionnement d'un SGBD - Isabelle Mirbel - M1 MIAGE 11/1268 of 68