Tutoriel de Bases de Données Relationnelles

Evaluation et optimisation de requêtes

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).