Méthodes d’optimisation des requêtes
Cours
“Bases de données” 1. Introduction
Optimisation 2. Étude des coûts
3. Optimisation
3.1. Utilisation d’heuristiques
3° année (MISI)
3.2. Évaluation systématique
Antoine Cornuéjols 3.3. Optimisation dans Oracle
www.lri.fr/~antoine
[email protected]Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Étapes de traitement des requêtes Introduction
Requête en langage de haut niveau
IDENTIFICATION,
ANALYSE Scanneur Parseur Validation Langage de requête de bas niveau
ET VALIDATION
Le programmeur a la charge complète de l’optimisation des requêtes
Forme intermédiaire de la requête Arbre de requête
}
OPTIMISEUR
DE REQUÊTE
Langage de requête de haut niveau
Plan d'exécution
Optimisation Possède des systèmes dédiés à l’optimisation des requêtes
GÉNÉRATEUR DU
CODE DE LA REQUÊTE
Le programmeur peut souvent donner des “indications” (“hints”)
}
Code d'exécution de la requête
PROCESSEUR D'EXÉCUTION
Exécution
DE LA BASE DE DONNÉES
Résultat de la requête
3 4
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Introduction Introduction
Deux grandes techniques d’optimisation
Recherche du meilleur plan d’exécution
Utilisation de règles heuristiques
Coût excessif
Ré-ordonnent les opérations dans les arbres de requêtes
Recherche d’une solution approchée à un coût raisonnable
Évaluation systématique des coûts
Par heuristiques
Choix du plan d’exécution le moins coûteux
Par estimation approximative des coûts
Un optimiseur de requête combine généralement ces deux techniques
Un optimiseur de requête combine généralement ces deux techniques
5 6
Traitement et optimisation des requêtes
Méthodes d’optimisation des requêtes Analyse des coûts
Opérations de tri
Algorithme le plus utilisé : le tri-fusion
1. Phase de tri de petits sous-fichiers
1. Introduction
2. Fusion triée des sous-fichiers triés
2. Étude des coûts
Phase de tri
3. Optimisation Ex : Fichier de b=1024 blocs ; espace tampon de nB=5 blocs
3.1. Utilisation d’heuristiques -> nR=205 runs initiaux (205 sous-fichiers triés)
3.2. Évaluation systématique Phase de fusion
Ex : 4 sous-fichiers triés -> 52 = 205/4 , puis 13 , puis 4 , puis 1
3.3. Optimisation dans Oracle
Coût total : (2 . b) + (2 . (b . (logdM nR)))
Nb d’accès de blocs (lect. et écriture) Nb d’accès de blocs pour la phase de fusion
8
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Analyse des coûts : tri-fusion Analyse des coûts : tri-fusion
• Étape tri 3 4 15 9 12 18 2 5 16 6 7 14
– nombre de groupes = ! BT /M" = ! 12 /3" = 4 Passe de
– Coût = 2 * ( ! BT /M" * TempsPosDébut + BT * TempsTrans) = 104 fusion #1
ms produit 4/2 = 2
Positionnement Positionnement Positionnement Positionnement groupes
3 4 9 12 15 18 2 5 6 7 14 16
Lecture Lecture Lecture Lecture
Passe de
fusion #2
produit 2/2 =1
15 4 3 9 18 12 16 2 5 7 14 6
Création groupe
de 12/3 = 2 3 4 5 6 7 9 12 14 15 16 18
Positionnement Positionnement Positionnement Positionnement 4 groupes
Ecriture Ecriture Ecriture Ecriture
Coût des passes de fusion
3 4 15 9 12 18 2 5 16 6 7 14
= BT*(2*log M-1 (BT /M)-1) * TempsESBloc
= 12*(2*log 2 (12 /3)-1) *11ms = 396 ms
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Analyse des coûts : tri-fusion Analyse des coûts : tri-fusion
Estimation du coût
d’un tri-fusion
(FBM = 20)
TempsES (TRI) =
2*(BT /M* TempsPosDébut + BT*TempsTrans) + BT*(2*log M-1 (BT /M)-1) * TempsESBloc
= 104 ms + 396 ms = 500 ms
N = nb d’enregistrements
M = Taille de la mémoire centrale
disponible en nombre de blocs
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Analyse des coûts Analyse des coûts
Opérations de SELECTION Opérations de JOINTURE
Responsabilité du scanneur de fichiers Opération très coûteuse
Scrute les enregistrements d’un fichier pour extraire ceux qui satisfont à une
condition de sélection
Plusieurs méthodes de jointure
Plusieurs méthodes de recherche Utilisation de boucles imbriquées (force brute)
Test d’égalité : Une seule boucle si index ou clé de hachage sur l’autre attribut
Si index : parcours d’index Par tri-fusion préalable sur les deux attributs
Recherche linéaire (force brute) Par jointure-hachage et variantes
Recherche binaire si attribut clé sur lequel le fichier est trié
Utilisation d’un index primaire ou d’une clé de hachage
Utilisation d’un index secondaire (arbre-B+) Grande influence de l’espace tampon disponible
...
Sélections complexes (conjonction, disjonction, ...)
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Analyse des coûts Analyse des coûts
Opérations de PROJECTION et opérations sur les ensembles Traitement par flot ou par pipe-line
Projection Il faut éviter les lourds stockages intermédiaires
Simple si la liste des attributs de projection inclut une clé.
Sinon, problème des doublons
Traitement par flot
On utilise le résultat partiel d’une opération immédiatement dans les
Produit cartésien
opérations qui suivent
Potentiellement très coûteux. À éviter.
Union / Intersection / Différence
Même ensemble d’attributs sur chaque table
Souvent des techniques par tri-fusion
Traitement et optimisation des requêtes
Méthodes d’optimisation des requêtes Utilisation d’heuristiques
Arbre de requête (“query tree”)
structure de données arborescente
1. Introduction visualise graphiquement une requête relationnelle traduite en une
expression équivalente de l’algèbre relationnelle
2. Étude des coûts
Feuilles : tables utilisées dans la requête
3. Optimisation
Noeuds intermédiaires : opérations algébriques
3.1. Utilisation d’heuristiques
Noeud racine : dernière opération algébrique avant le retour du résultat
3.2. Évaluation systématique
3.3. Optimisation dans Oracle L’opération d’un noeud intermédiaire est déclenchée quand ses opérandes
sont disponibles.
On remplace alors le noeud par la relation produite par l’opération.
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Utilisation d’heuristiques Utilisation d’heuristiques
Arbre de requête Arbre de requête
πNO P, NUMS, NOMS, ADRESSE, DNAISS (((σEMPL P=’MEYZIEU’ (P ROJET )) #$NUMS=NoS (SERV ICE)
#$NoSSDIR=NoSS (EM P LOY E)) Première étape du processus de traduction et d’exécution
Vérification de l’existence des tables
πNO P, P.NUMS, E.NOMS, E.ADRESSE, E.DNAISS Vérification de l’existence des attributs
Vérification des droits d’accès de l’utilisateur
!"S.NoSSDIR=E.NoSS
!"P.NUMS=S.NoS EMPLOYE
On va ensuite optimiser l’arbre de requête
σP.EMPL P=’MEYZIEU’ SERVICE
PROJET
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Utilisation d’heuristiques Plans d’exécution équivalents
Optimisation de l’arbre de requête Plusieurs arbres algébriques équivalents
Recherche d’expressions algébriques équivalentes
" titre, descripteur " titre, descripteur
Optimisation par :
Utilisation de la commutativité de certains opérateurs ! ISBN = 1-111-1111-1
Conservation des seuls attributs nécessaires aux opérations ultérieures
! ISBN = 1-111-1111-1 Catégorie
Utilisation d’un ensemble de règles de transformation par l’optimiseur Livre Catégorie Livre
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Plans d’exécution équivalents Plans d’exécution équivalents
Règles d’équivalence de l’algèbre relationnelle Règles d’équivalence de l’algèbre relationnelle (suite)
! Eclatement d'une sélection conjonctive (SE) ! Commutativité restreinte de la sélection et de la jointure (CSJ)
– ! e1 ET e2 (T) = ! e1 (! e2 (T)) – ! e (T1 " T2) = ! e (T1) " T2
! Commutativité de la sélection (SC) ! si l'expression de sélection e ne contient que des colonnes de T1
– ! e1 (! e2 (T)) = ! e2 (! e1 (T)) ! Commutativité restreinte de la projection et de la sélection (CPS)
! Elimination des projections en cascades (PE) – # listeColonnes (! e (T)) = # listeColonnes (! e (# listeColonnes $ colonnes de e T))
– " liste1 (" liste2 (T)) = " liste1 (T) ! Commutativité restreinte de la projection et de la jointure (CPJ)
! Commutativité de la jointure (JC) – # listeColonnes (T1 " T2) =
– T1 # T2 = T2 # T1
– # listeColonnes (# listeColonnes % colonnes de T1(T1) " # listeColonnes % colonnes de T2(T2))
! Associativité de la jointure (JA)
! etc.
– T1 # (T2 # T3) = (T1 # T2) # T3
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Plans d’exécution équivalents Utilisation d’heuristiques
Pour chaque opération logique : plusieurs choix d’opérations physiques Optimisation de l’arbre de requête
En règle générale :
placer les opérateurs de projection et de sélection le plus près possible des
“feuilles”
" titre, descripteur (Balayage) " titre, descripteur (Balayage) " titre, descripteur (Balayage) Fusionner plusieurs sélections sur une même table en une seule afin
que le prédicat de sélection ne soit testé qu’une seule fois
! ISBN = 1-111-1111-1 (Balayage) ! ISBN = 1-111-1111-1 (Balayage) ! ISBN = 1-111-1111-1 (Balayage) Effectuer les sélections le plus tôt possible afin de réduire la taille des
(Jointure par (Jointure par (Jointure par tables intermédiaires (le plus près des feuilles)
tri-fusion) BIM) hachage)
Effectuer les projections le plus tôt possible, mais jamais avant les
Livre Catégorie Livre Catégorie Livre Catégorie
sélections (réduisent le nombre de colonnes et, souvent, le nombre de
tuples)
Placer les opérateurs de jointure le plus près possible du noeud racine
à cause du coût de leur évaluation (il devrait y avoir moins de tuples et de
colonnes près de la racine).
Traitement et optimisation des requêtes
Méthodes d’optimisation des requêtes Optimisation par évaluation des coûts
Complète l’utilisation d’heuristiques
Il faut évaluer le plus précisément des stratégies alternatives
1. Introduction tout en limitant le coût de l’optimisation elle-même.
2. Étude des coûts Surtout utilisée dans les requêtes compilées
3. Optimisation
Une évaluation des coûts est conservée dans le catalogue du SGBD
3.1. Utilisation d’heuristiques
Coût d’accès à un type de stockage secondaire (souvent le plus important)
3.2. Évaluation systématique Coût de calcul
3.3. Optimisation dans Oracle Coût d’usage de la mémoire
Coût des communications
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Optimisation par évaluation des coûts Optimisation par évaluation des coûts
Une évaluation des coûts est conservée dans le catalogue du SGBD Une évaluation des coûts est conservée dans le catalogue du SGBD
Exemple d’informations stockées :
Nombre d’enregistrements (tuples) d’un fichier Certaines valeurs ont besoin d’être remises à jour fréquemment :
Taille moyenne des enregistrements E.g. nombre d’enregistrements d’un fichier
Nombre de blocs d’autres, non
Facteur de blocage du fichier (nb max d’enregistrements par bloc) E.g. nombre de niveaux d’un index hiérarchique
Méthode d’accès primaire
Attributs d’accès primaire de chaque fichier
Informations sur tous les index secondaires et attributs d’indexation
Nombre de blocs de l’index de plus haut niveau
...
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Optimisation par évaluation des coûts Optimisation par évaluation des coûts
Exemple d’utilisation des fonctions de coût Exemple 2 d’utilisation des fonctions de coût
" titre, descripteur TempsES
(Balayage
= 11 ms)
! titre, descripteur (Balayage
TempsES = 11 ms)
(Ecriture du résultat
TempsES = 11 ms)
(Ecriture du résultat
TempsES = 11 ms) TempsES(Plan avec pipeline) = (Boucle imbriquée par
! ISBN = 1-111-1111-1TempsES(Balayage
= 92 314 ms) Coût total =
TempsES (JTFLivre! Catégorie) = 2 index secondaire sur
code de la table
interne Catégorie Coût total =
3 812 040 ms
873 540 ms TempsES = 44ms) 132ms
Catégorie
TempsES(Plan avec pipeline) =
(Ecriture du résultat
TempsES = 846 164 ms)
(Ecriture du résultat
TempsES = 11ms)
TempsES(S=IS pour index sur ISBN) +
(Jointure par tri-fusion
TempsES = 2 873 540 ms) N ! ISBN=1-11-111-1111 (Livre) * TempsES(S=IS sur code de
" ISBN = 1-111-1111-1 (Sélection par index
secondaire sur ISBN Catégorie)
TempsES = 55ms)
Livre Catégorie Livre = 55 ms + 33 ms = 88 ms
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Optimisation par évaluation des coûts Optimisation par évaluation des coûts
Estimation de la taille du résultat d’une opération Exemple d’estimation de la taille d’une projection
SELECT DISTINCT code, annéeParution FROM Livre ;
! Taille d'une sélection
– ! SelT (Expression de sélection)/ FBMT" blocs NLivre 1 000 000
! Taille d'une projection FBMLivre 20
CardLivre (code) 4 000
– N# liste(T) = NT si contient une clé candidate
CardLivre (annéeParution) 50
– N# C(T) = CardT (C) pour une colonne
– N# C1,C2,…,Cn(T) = k(1-(1- 1/k)NT) ! k = ! i=1,..,nCardT (Ci)
! k = $ i=1,..,nCardT (Ci) ! = CardLivre (code) * CardLivre (annéeParution)
! Taille d'une jointure naturelle ! = 4 000 * 50 = 200 000
– NR % S = NR * NS / maximum(CardR(cléJointure), CardS(cléJointure)) ! N" code,annéeParution(T)= k(1-(1- 1/k)N)
! = 198 652 lignes (en arrondissant)
Traitement et optimisation des requêtes
Méthodes d’optimisation des requêtes Optimisation dans Oracle
Oracle propose deux approches différentes
L’une basée sur des règles
L’autre sur les coûts
1. Introduction
Approche basée sur des règles
2. Étude des coûts Opérations classées selon une heuristique
3. Optimisation Considère 15 types d’accès différents (depuis force brute à ROWID)
3.1. Utilisation d’heuristiques Approche basée sur les coûts
Calcule le coût des stratégies en fonction des besoins en E/S, temps processeur,
3.2. Évaluation systématique
mémoire nécessaire
3.3. Optimisation dans Oracle
Possibilité d’intervention du développeur d’application
Peut fournir des “hints” (si il a des informations que n’a pas le SGBD)
Traitement et optimisation des requêtes Traitement et optimisation des requêtes
Optimisation dans Oracle Optimisation dans Oracle
Oracle : Rang Chemin d'accès
mode RULE 1 Sélection par ROWID
2 Sélection d'une ligne par jointure dans une organisation par
index groupant ou hachage hétérogène (CLUSTER) ! Cas Oracle
3 Sélection d'une ligne par hachage sur clé candidate
(PRIMARY ou UNIQUE) – outils
4 Sélection d'une ligne par clé candidate
5 Jointure par une organisation par index groupant ou !EXPLAIN PLAN
hachage hétérogène (CLUSTER)
6 Sélection par égalité sur clé de hachage (HASH CLUSTER) !SQL Trace
7 Sélection par égalité sur clé d'index groupant (CLUSTER)
8 Sélection par égalité sur clé composée !SQL Analyse (Enterprise Manager Tuning
9 Sélection par égalité sur clé simple d'index secondaire Pack)
10 Sélection par intervalle borné sur clé indexée
11 Sélection par intervalle non borné sur clé indexée !Oracle EXPERT
12 Tri-fusion
13 MAX ou MIN d'une colonne indexée
14 ORDER BY sur colonne indexée
15 Balayage
Traitement et optimisation des requêtes
Exercices
