Les requêtes algébriques sont évaluées à
partir d'un ensemble canonique d'opérateurs.
Généralement cet ensemble comprend la sélection, la
projection, le produit cartésien et le produit (ou jointure). Toute
expression algébrique se traduit en une composition de ces opérateurs
canoniques. L'optimisation de cette expression consiste à trouver
le meilleur ordonnancement possible des opérateurs relativement
à un coût. Ce coût s'évalue généralement
par trois critères qui sont le nombre d'entrées/sorties,
le temps CPU et le nombre de buffers requis. Le résultat de l'optimisation
s'appelle un plan d'exécution.
L'optimisation peut se faire en deux passes, une première
s'appuyant sur les propriétés algébriques
des opérateurs qui permet surtout de limiter la taille des relations
manipulées et une seconde basée sur des fonctions
de coût qui permet d'affiner l'optimisation en tenant compte
des caractéristiques des relations et attributs manipulés
(taille des relations, discriminance des attributs, connaissance des clés,
existence de chemins d'accès efficaces, ...).
Optimisations algébriques
On peut représenter une requête sous forme d'un arbre algébrique
dont les feuilles sont des relations et les non-terminaux des opérateurs
canoniques. L'optimisation consiste à réorganiser l'arbre
en utilisant les propriétés algébriques de façon
à produire un arbre équivalent (c'est à dire produisant
la même réponse) mais dont l'évaluation sera plus efficace.
L'idée de base est de réduire au maximum la taille
des relations intermédiaires produites. Pour cela, il faut utiliser
le plus possible les sélections et les projections et les faire
le plus tôt possible. Il faut donc faire "descendre" les
sélections et projections dans l'arbre et rajouter éventuellement
des projections permettant de ne manipuler que les attributs effectivement
utilisés dans l'expression.
Règles de transformation de l'algèbre
relationnelle
1- Séquence de sélections :
SELECTION C1 and c2 ... and Cn(R) = SELECTION C1( SELECTION C2(...(
SELECTION Cn(R))))
2- Commutativité de la sélection :
SELECTION C1( SELECTION C2(R)) = SELECTION C2( SELECTION C1(R))
3- Séquence de projections :
PROJECTION L1( PROJECTION L2(...( PROJECTION Ln(R)))) = PROJECTION
L1(R)
4- Commutation de la sélection et de la projection :
PROJECTION A1, A2, ..., An( SELECTION C(R)) = SELECTION C( PROJECTION
A1, A2, ..., An(R))
5- Commutativité de la jointure :
R * S = S * R
6- Commutation de la sélection et de la jointure (ou produit
cartésien) :
à condition que C concerne seulement R : SELECTION C(R * S) = ( SELECTION C(R)) * S
à condition que C = C1 and C2 et C1 (C2) concerne seulement R
(S) : SELECTION C(R * S) = ( SELECTION C1(R)) * ( SELECTION C2(S))
7- Commutation de la projection et de la jointure (ou produit cartésien)
:
- L = {LR,LS} LR = R1, R2, ..., Rn LS = S1, S2, ..., Sm
C porte sur des attributs présents dans L
PROJECTION L(R * S) = PROJECTION LR(R) * PROJECTION LS(S)
- L = R1, ..., Rn, S1, ..., Sm
LRK = R1, ..., Rn, Rn+1, ..., Rn+k
LSP = S1, ..., Sm, Sm+1, ..., Sm+p
C porte sur Rn+1, ..., Rn+k, Sm+1, ..., Sm+p
PROJECTION L(R * S) = PROJECTION L(( PROJECTION LRK(R)) * ( PROJECTION
LSP(S)))
8- Commutativité des opérations ensemblistes (union et
intersection)
9- Associativité de la jointure, du produit cartésien,
de l'union et de l'intersection :
O = { UNION , INTERSECTION , *, X}
(R O S) O T = R O (S O T)
10- Commutation de la sélection avec les opérateurs ensemblistes
:
O = { UNION , INTERSECTION , -}
SELECTION C(R O S) = ( SELECTION C(R)) O ( SELECTION C(S))
11- Commutation de la projection avec les opérateurs ensemblistes
:
O = { UNION , INTERSECTION , -}
PROJECTION L(R O S) = ( PROJECTION L(R)) O ( PROJECTION L(S))
Algorithme général d'optimisation
heuristique
Les étapes principales de l'algorithme sont les suivantes :
- 1 Séparer les sélections conjonctives en une séquence
de sélections (règle 1) - 2 Descendre les opérations de sélection le plus bas
possible dans l'arbre (règles 2, 4, 6 et 10) - 3 Réarranger les feuilles de l'arbre pour évaluer les
sélections les plus restrictives d'abord (règle 9) - 4 Combiner les produits cartésiens avec des expressions de
sélection appropriées pour en faire des jointures - 5 Faire des projections le plus tôt possible dans l'arbre (le
cas échéant en en créant des nouvelles,non explicites dans la requête) pour manipuler seulement l'information
intéressante (règles 3, 4, 7 et 11) - 6 Identifier les sous arbres qui peuvent être exécutés
par un seul algorithme (les sélection - projection - jointure par
exemple)
Optimisation par une fonction de coût
L'idée est d'utiliser des informations supplémentaires
(stockées dans les catalogues de la base) pour minimiser certaines
opérations. Parmi les différents ordonnancements possibles,
on va chercher celui qui minimise la fonction de coût. Il faut noter
que le traitement nécessaire à l'optimisation peut être
long (notamment si la requête est complexe) et que cette approche
est donc plus adaptée dans un environnement de compilation de requêtes.
Les paramètres principaux de la fonction de coût
sont :
- le coût d'accès disque (le plus important)
- le coût de stockage des fichiers intermédiaires
- le coût de calcul
- le coût de communication (si les données ne sont
pas toutes sur le même site)
Les informations utilisées pour chaque relation sont le
plus souvent :
- site de stockage de la relation
- nombre de nuplets stockées (nt)
- nombre de blocs utilisés (nb)
- pour chaque attribut, son nombre de valeurs distinctes (nd)
Cette dernière information permet d'évaluer la sélectivité
d'un attribut (nt / nd).
Posté le 1 septembre 2009