Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Query Optimization: SQL est déclaratif ◦On dit ce que l’on veut obtenir ◦On ne

Query Optimization: SQL est déclaratif ◦On dit ce que l’on veut obtenir ◦On ne dit pas comment l’obtenir Optimiseur doit : ◦Comprendre la requête. Traduction en Plan d’Exécution Logique ◦Choisir le meilleur Plan d’Exécution Physique ◦Exécuter le Plan d’Exécution Physique Plan d’exécution Soit le schéma : ◦Cours (CODE, Intitule, Responsable) ◦Auditeurs (CODE_UE, CODE_AUDITEUR, Annee, Note) Soit la requête : Liste des années où A.malki a eu des auditeurs ? SELECT Annee  FROM Cours, Auditeurs  WHERE Responsable = ’A.malki’ AND  CODE = CODE_UE ; Exemple πAnnee (σresponsable=‘A.malki’(Cours ∞ Auditeurs) ) πAnnee (σresponsable=‘A.malki’(Cours) ∞ Auditeurs) πAnnee (σresponsable=‘A.malki’(Auditeurs ∞ Cours) )  πAnnee (Auditeurs ∞ σresponsable=‘A.malki’(Cours))  Quel est le meilleur plan d’exécution ?  le deuxième plan ◦Il faut mieux commencer par les sélections avant les jointure ◦La table cours après filtrage est plus petite que la table auditeur Exemple: Plan d’exécution logique Basées sur des règles heuristiques ◦( Rule-Based)  Basées sur l’estimation des coûts ◦(Cost-based) Comment choisir le meilleur plan d’exécution ? 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ées comme restriction et projection Rule-Based optimisation: Principe 1. Commutativité de la jointure : R ∞ S  S ∞ R 2. Associativité de la jointure : (R ∞ S) ∞ T  S ∞ (R ∞ T ) 3. Regroupement des sélections : σA=a(σB=bR)  σA=a^B=b R 4. Commutativité de la sélection et de la projection : πA1...An (σAi=aR)  σAi=a(πA1...An R), i  1,...,n 5. Commutativité de la sélection et de la jointure : σA=a(R ∞ S)  σA=a(R) ∞ S Rule-Based optimisation: règles de réécriture 6. Distributivité de la sélection sur l’union : σA=a(R  S)  σA=a(R)  σA=a(S) 7. Commutativité de la projection et de la jointure : πA1...AnB1...Bm (R ∞Ai=Bj S)  πA1...An R ∞Ai=Bj πB1...BmS ◦i  1,...,n et j 1,...,m 8. Distributivité de la projection sur l’union : πA1...An(R  S)  πA1...An (R)  πA1...An (S) Rule-Based optimisation: règles de réécriture Remonter les sélections le plus tôt possible (règles 4 & 5) Remonter les projections le plus haut possible (règles 4, 7 & 8) Décomposer les sélections en une composition. (règle 3) Rule-Based optimisation: Heuristiques La restructuration d’un arbre sous-entend souvent la permutation des opérateurs binaires Cette optimisation ignore la taille de chaque table, les facteurs de sélectivité, etc. Aucune estimation de résultats intermédiaires Optimisation basée sur les modèles de coût (Cost Based COB)) Rule-Based optimisation: Limites Une requête SQL est transformée en Plan d’exécution Le plan est composé d’opérateurs: ◦Opérateurs de sélection ◦Opérateurs de trie ◦Opérateurs de projection ◦Opérateurs de jointure Chaque opérateur à un coût d’évaluation ◦Coût en Entrées/Sorties ◦Dépend des statistiques (taille des tables, nb tuples, cardinalité, sélectivité…) Opérateurs algébriques Opération σA=aR 3 Algorithmes, selon la structure physique: ◦Sélection Séquentielle : TABLE ACCESS FULL ◦Sélection avec Index Arbre B+ : INDEX RANGE SCAN ◦Sélection par Hachage : PARTITION HASH SINGLE Impact de la sélectivité sur nombre de tuples en sortie et/ou le nombre d’accès Opérateurs de sélection Appliquer si aucun index sur R(A) Pour chaque page b de R ◦Pour chaque tuple t de b Si t.A=‘a’ Ajouter t dans S  Complexité ? |R| (nombre de pages)  le TABLE ACCESS FULL sera choisi par l’optimiseur si son coût |R| est minimal TABLE ACCESS FULL : Sélection Séquentielle Table ACCESS FULL: σresponsable=A.Malki Cours Page Code intitule Responsable Eleves P2 NFE205 Réseaux avancés A.Kechar 20 NSY135 Systèmes d’information avancés A.Bensaber 15 NFA011 Patrons de conception R.ALI 40 P3 NFE102 IHM E.Salim 20 NSY218 Systèmes Embarqués E.Boudrih 30 NSY219 Big Data F.Lokmen 25 P1 NFE106 Bases de données avancées A.Malki 30 NFP107 Développement web A.malki 100 NFE204 Développement mobile N.Eloulie 50 Code intitule Responsable Eleves Tampon de sortie P1 NFE106 Bases de données avancées A.Malki 30 NFP107 Développement web A.Malki 100 NFE204 Développement mobile N.Eloulie 50 Code intitule Responsable Eleves NFE106 Bases de données avancées A.Malki 30 P1 NFE106 Bases de données avancées A.Malki 30 NFP107 Développement web A.Malki 100 NFE204 Développement mobile N.Eloulie 50 Code intitule Responsable Eleves NFE106 Bases de données avancées A.Malki 30 NFP107 Développement web A.Malki 100 P1 NFE106 Bases de données avancées A.Malki 30 NFP107 Développement web A.Malki 100 NFE204 Développement mobile N.Eloulie 50 P1 NFE106 Bases de données avancées A.Malki 30 NFP107 Développement web A.Malki 100 NFE204 Développement mobile N.Eloulie 50 P2 NFE205 Réseaux avancés A.Kechar 20 NSY135 Systèmes d’information avancés A.Bensaber 15 NFA011 Patrons de conception R.ALI 40 P2 NFE205 Réseaux avancés A.Kechar 20 NSY135 Systèmes d’information avancés A.Bensaber 15 NFA011 Patrons de conception R.ALI 40 P2 NFE205 Réseaux avancés A.Kechar 20 NSY135 Systèmes d’information avancés A.Bensaber 15 NFA011 Patrons de conception R.ALI 40 P2 NFE205 Réseaux avancés A.Kechar 20 NSY135 Systèmes d’information avancés A.Bensaber 15 NFA011 Patrons de conception R.ALI 40 P3 NFE102 IHM E.Salim 20 NSY218 Systèmes Embarqués E.Boudrih 30 NSY219 Big Data F.Lokmen 25 P3 NFE102 IHM E.Salim 20 NSY218 Systèmes Embarqués E.Boudrih 30 NSY219 Big Data F.Lokmen 25 P3 NFE102 IHM E.Salim 20 NSY218 Systèmes Embarqués E.Boudrih 30 NSY219 Big Data F.Lokmen 25 Sélection par index appliqué si I sur R(A) INDEX RANGE SCAN Ouvrir la page P racine de I Tant que P n’est pas une feuille ◦Parcourir l’arbre de P avec A=’a’ ◦P = nouvelle page cible Sortie : L = liste de ROWIDS Sélectivité de l’attribut A : Sel (0 < Sel < 1) ||L|| = ||ROWID|| × Sel TABLE ACCESS BY INDEX ROWID Pour chaque l de L Ouvrir la page p pointée par l ◦Pour chaque tuple t de p Si t.A= ’a’ Ajouter t dans le tampon de sortie INDEX RANGE SCAN + TABLE ACCESS BY INDEX ROWID Complexité: |I| Complexité: ||ROWID|| × Sel Complexité finale: |I|+||ROWID|| × Sel INDEX RANGE SCAN + TABLE ACCESS BY INDEX ROWID Pourcentage de n-uplets pour une valeur cherchée Dépend du prédicat de sélection et des données : σA=aR Par défaut : Sel (R(A)) = (Card(R(A)) : nb de valeurs distinctes) Exemple : ◦R (A) est réparti sur 20 valeurs différentes (cardinalité = 20) ◦Statistiquement : Sel(R (a)) = = 5% Clé primaire : Sel (id)= (INDEX UNIQUE SCAN) Statistiques: ◦Histogramme de fréquences par valeur (R(A)) ◦Coût de calcul / mise à jour (requêtes d’agrégation)  Sélectivité: Sel  Parcours de l’index 1. Ordre du BTree ◦Dépend de la taille de la clé ◦Un nœud = une page (8ko + metadata + PCTFREE) ◦Contient 2 × O cases ◦Une case : Clé + ROWID  Taillecase : 3 + |cle| + 10 ◦ordre : O = ÷ 2 2. Hauteur du BTree ◦Division de l’espace par l’ordre à chaque niveau logO (||ROWID||) ◦Index dense : ||ROWID|| = ||R|| ◦Index non-dense : ||ROWID|| = |R| Plusieurs ROWIDS en sortie (L) ◦Si (||L|| > O ) plusieurs feuilles : ◦ =-1  INDEX RANGE SCAN:  nb feuilles supplémentaires INDEX RANGE SCAN:  nb feuilles supplémentaires Accès aux données via ROWIDS 1 ROWID = 1 page Optimisation : ◦Si 2 ROWIDS sur une même page = 1 accès ◦Tri des ROWIDS par page, puis accès clustering factor : ◦Degré de distribution aléatoire des données dans R ◦|R| << ||R|| ◦ = |R| (Index non-dense) ◦ = ||R|| (Très aléatoire/dispersé) - valeur par défaut Possibilité de trier les données physiquement Nombre de pages accédées : ||R|| × Sel × = Sel ×   Accès aux données via ROWIDS: Clustering factor Accès aux données via ROWIDS: Clustering factor Parcours de l’index : |I| (hauteur : logO (||ROWID||) ) Nombre de feuilles : = Accès aux données :  × Sel Coût moyen : |I| + +  × Sel (Index RANGE SCAN) Coût index unique : Sel = Coût index non dense :  = |R| L’accès aux données ( ×Sel ) n’est pas toujours obligatoire : ◦regarder si les données requises sont dans l’index ◦FAST FULL SCAN  INDEX RANGE SCAN + TABLE ACCESS BY INDEX ROWID : Complexité Appliquer si index Hash h sur R(a) β partitions Données placées sur les partitions en fonction de h Hacher la clé x: h(x) = v (1 ≤ v ≤ β) Recherche : ◦Pour chaque page p de la partition R(v) Pour chaque tuple t de p Si t.a =x Ajouter t dans S  Complexité ? Taille d’une partition ~  PARTITION HASH SINGLE : Sélection par Hachage PARTITION HASH SINGLE : Sélection par Hachage PARTITION HASH SINGLE : Sélection par Hachage Répartition des clés en fonction de la fonction de hachage ◦Sous Oracle : ORA_HASH. Peut être surchargée N-uplets uniformément répartis sur les partitions Problème de répartition ◦Fonction inadaptée ◦Répartition inégale des redondances reste meilleur qu’un Arbre B+ Combinaison de hachage Partitionnement par intervalles Intégré dans plusieurs opérateurs : ◦Sélection séquentielle : TABLE ACCESS FULL ◦Selection avec index : TABLE ACCESS BY ROWIDS ◦Sélection par tri : SORT ◦Jointures uploads/Ingenierie_Lourd/ partie2-chapitre6-optimisationbdd-bddav1-2021 1 .pdf