13/04/2004

Chapitre 11
Optimisation des requêtes relationnelles

Une requête relationnelle formulée avec SQL est traduite en une expression algébrique représentée
sous la forme dʹune arborescence (arbre de requête) dans laquelle les noeuds internes sont les
opérateurs unaires ou binaires et les noeuds terminaux sont des relations de base ou des vues. Cet
arbre de requête est optimisé 1 avant dʹêtre transformé en un plan dʹexécution formé d’une suite
d’appels de procédures pour exécuter l’arbre optimisé. Le rôle de lʹoptimiseur du SGBD est de choisir
parmi tous les arbres équivalents possibles à une requête particulière, celui dont le plan dʹexécution
sera le plus performant. Comme le nombre dʹarbres est grand et que toutes les données ou facteurs
qui influencent le calcul dʹune expression ne sont pas connus à priori, le choix repose souvent sur une
heuristique générale dont lʹimplémentation peut varier dʹun optimiseur à lʹautre.

Avant de formuler cette heuristique générale dʹoptimisation, nous allons examiner les propriétés des
opérateurs relationnels qui sont à la base des transformations d’un arbre en un autre équivalent. Ces
transformations se font uniquement sur la base de règles syntaxiques 2.

Le MRD de la base OUC qui sera utilisé par les exemples de ce chapitre comprend trois relations:
Ouvrier (nas*, nom, salaire, spec, noUs)
Usine (noUs*, site, prod, nasChef)
Contrat(noCont*, fin, cout, noUs

L’attribut fin est de type Date. Le MCD ci-dessous est spécifié avec le formalisme UML. L’association
entre les classes Ouvrier et Usine est caractérisée par une multiplicité (auparavant les contraintes
structurelle du modèle E/As) : zéro ou plusieurs ouvriers travaillent dans au plus une usine.

Usine
0..1 noUs* 0..1
Tavaille site
prod Execute
0..*
nasChef
0..*
Ouvrier
nas* Contrat
nom noCont*
salaire fin
spec cout
noUs noUs

Figure 11.1 Modèle UML de la base OUC

Source : http://www.ift.ulaval.ca/~agamache/pageperso/LivreBD/PageIntroLivreBD.html
 André Gamache
Chapitre 11 Optimisation des requêtes SQL

Ce MRD a ses contraintes référentielles et éventuellement, il est possible de définir une

contrainte d’inclusion. Cette dernière existerait si chaque chef d’usine était obligatoirement
un ouvrier de cette usine. Le diagramme ci-dessous représente les contraintes référentielles et
la contrainte d’inclusion (ligne pointillée) entre les classes.

Usine

(p) (p)

Ouvrier (e) (e) Contrat

Figure 11.2 Diagramme des contraintes

La présence d’un cycle est gênante, car elle bloque la création d’une usine si le chef qui est
aussi un ouvrier n’est pas créé et ce dernier ne peut pas être créé si l’usine où il travaille n’est
pas créée. Pour éviter ce cycle de contraintes, il suffit de ne pas définir la contrainte
d’inclusion au moyen du mécanisme de l’intégrité référentielle et de le faire avec un trigger
de Pre-Insertion. Ce MRD sans la contrainte d’inclusion sera le modèle type auquel nous
ferons référence dans ce chapitre sur l’optimisation des requêtes.

Typologie des requêtes

Le nombre de requêtes qui peuvent utiliser pour interroger un modèle de données est très grand.
Dans la discussion de lʹoptimisation de celles-ci, il est utile de les classer ; nous emprunterons la
typologie proposée par Shasha3 qui regroupe les requêtes de la façon suivante :

a- Requête singulière (Point query)

C’est une requête basée sur une seule relation et dont le prédicat de sélection est composé avec une ou
plusieurs égalités dʹattributs de manière à ce que la réponse comprenne au plus un tuple.
SELECT *
FROM Ouvrier
WHERE nas = '1234';

b- Requête singulière multiple (Multipoint query)

C’est une requête basée sur une seule relation et dont le prédicat est composé avec une ou plusieurs
égalités dʹattributs, mais dont la réponse comprend plusieurs tuples.
SELECT *
FROM Ouvrier
WHERE salaire > 10000.00 And spec = ‘soudeur’;

© A. Gamache 2
Chapitre 11 Optimisation des requêtes SQL

c- Requête dʹintervalle (Range query)

Requête basée sur une relation et dont le prédicat comprend un test dʹintervalle. La réponse comprend
normalement plusieurs tuples.
SELECT *
FROM Ouvrier
WHERE salaire > 10000.00 and salaire < 50000.00;

d- Requête dʹappariement sur un ensemble ordonné dʹattributs Z (prefix match query)

Requête dont les conditions dʹégalité doivent inclure obligatoirement une sous-chaîne définie selon
lʹensemble ordonné Z. Par exemple, dans la relation Ouvrier, considérons le sous-ensemble ordonné Z
= {nas, nom} de cette classe. Une requête dont le prédicat comprend des égalités formulées avec un des
deux sous-ensembles {nas} ou {nas, nom} est une requête dʹappariement. Souvent, ce type de requête
découle de la présence dʹun index composé disponible dans le dictionnaire.
SELECT nom, salaire
FROM Ouvrier
WHERE nas = '1234' and nom = 'Trudel';

Par contre, la requête ci-dessous nʹest pas de ce type puisque lʹattribut nas est absent du prédicat.
SELECT nom, salaire
FROM Ouvrier
WHERE nom = 'Trudel' ;

Elle est cependant singulière multiple.

e- Requête min-max (Extremal query)

Requête formulée avec une seule relation et dont le prédicat est composé dʹégalités faisant référence à
avec une valeur minimale ou maximale. La réponse peut comprendre plusieurs tuples.
SELECT nom, salaire
FROM Ouvrier
WHERE salaire = MAX (SELECT salaire from Ouvrier);

f- Requête avec ordonnement (Ordering query)

Requête dont la réponse est affichée selon lʹordre dʹun ou plusieurs attributs.
SELECT nom, salaire
FROM Ouvrier
ORDER BY nom;

g- Requête de groupement (Grouping query)

Requête dont la réponse est partionnée par un ou plusieurs attributs.

© A. Gamache 3
Chapitre 11 Optimisation des requêtes SQL

SELECT noUs, AVG(salaire)

FROM Ouvrier
GROUP BY noUs ;
h- Requête de jointure (Joint query)
Requête comprenant une ou plusieurs jointures définies sur une ou plusieurs relations.
SELECT nas, nom, site
FROM Ouvrier O, Usine U
WHERE O.noUs = U.noUs;

Une telle requête est lourde à calculer puisquʹelle sous-tend la comparaison de tous les tuples de
lʹextension Ouvrier avec ceux de lʹextension Usine.
Bien entendu, une requête peut être à la fois du type intervalle et de groupement, comme une autre
peut être de type min-max et en même temps dʹintervalle. Les types de la requête prépondérants dans
une exploitation de la base ont une incidence sur la nature des index à créer et dans la manière avec
laquelle la réponse sera calculée. C’est cette opération de calcul de la réponse que l’optimisation
cherche à rendre rapide quelle que soit la catégorie à laquelle une requête appartient. Pour y arriver,
l’optimiseur transformera l’arbre de requête et fera un choix approprié d’un ou plusieurs algorithmes
de calcul qui exploiteront les index existants. Le résultat de cette opération est un plan de calcul
(Execution plan) qui fournit la réponse recherchée pour une requête.

Traitement d’une requête SQL

Toute requête SQL transmise au SGBD soit par un pilote ODBC, soit par une autre interface API
fournie par le développeur du système de gestion est l’objet d’un traitement en trois étapes :
1- Analyse de la requête
La clause SQL est l’objet d’une analyse syntaxique suivie d’une analyse sémantique. La première
phase de l’analyse consiste à vérifier si la clause SQL est conforme à la grammaire en validant les mots
clés utilisés (partie lexicographique) et ensuite en voyant à ce que la structure respecte celle imposée
par les règles d’écriture. Dans le cas d’un rejet, c’est une erreur de type 1. Dans une deuxième phase, il
y a validation du nom des tables, des attributs, des fonctions d’usager, … utilisés dans la requête.
Pour effectuer cette opération, le module d’analyse consultera le dictionnaire de données de la base. Si
l’analyse rejette la requête, c’est une erreur de type 2.

La deuxième phase de l’analyse est de nature sémantique et vise à débusquer les prédicats toujours
faux, à transformer une requête imbriquée en une jointure classique et à vérifier la cohérence d’un
prédicat au regard des contraintes de domaine définies dans la dictionnaire. Par exemple, si le salaire
maximum d’un employé est limité à 100 000.00$, il ne sert à rien de lancer l’exécution d’une requête
dont le prédicat est le suivant : Where salaire => 150000.00. Lors de l’étape d’analyse sémantique, il est
possible de rejeter la requête sur la base seule d’une contrainte de domaine (Erreur de type 3).
Finalement, une troisième phase consiste à générer l’arbre de la requête formulé au moyen des
opérateurs algébriques. Cette opération quoique non obligatoire a l’avantage de fournir une
représentation algébrique de la requête SQL dont les transformations sont facilement comprises

© A. Gamache 4
Chapitre 11 Optimisation des requêtes SQL

puisque nous maîtrisons la sémantique des opérateurs de l’algèbre. Souvent dans les SGBD
commercialisés, cet arbre n’est pas explicitement généré et le système passe directement à la
formulation du plan d’exécution. Un grand nombre de SGBD implémentent les phases 1 et 2. Par
contre, la phase 3 n’est pas encore très bien mise en œuvre par la plupart des systèmes. À la sortie de
l’analyse le SGBD récupère un plan d’exécution logique représenté soit par l’arbre de requête, soit par
une suite d’appels de procédures spécialisées dont le résultat est la réponse demandée. Ce plan
d’exécution dit logique pourra être par la suite converti lors de l’étape d’optimisation en un plan
d’exécution physique composé lui aussi de programmes organisés en arbre. À la limite, un plan
d’exécution logique peut coïncider avec le physique.
2- Optimisation de l’arbre de requête
L’arbre de requête est transformé en un plan d’exécution physique composé avec les procédures de
calcul des opérateurs algébriques qui sont exécutées dans un ordre choisi pour être efficace. Ce choix
dépend aussi de l’indexation de certains attributs et des algorithmes sous-jacents à leur indexation. La
difficulté est de choisir parmi de très nombreux plans d’exécution possibles, celui qui dans le contexte
présent s’avèrera le plus efficace.
3- Exécution du plan
Le plan d’exécution obtenu de l’étape d’optimisation est ensuite compilé (plus précisément les
programmes appelés par les nœuds du plan) et lancé afin d’aboutir aux résultats escomptés.

Transformations algébriques dʹun arbre de requête

Lʹarbre de requête peut être lʹobjet de plusieurs transformations de nature syntaxique basées sur les
propriétés des opérateurs de l’algèbre relationnelle. Le résultat recherché est un nouvel arbre dit
équivalent parce que donnant la même réponse, mais permettant un calcul plus rapide. Toutefois, la
décision dʹappliquer de telles transformations ne dépend pas uniquement de la requête en soi, mais
aussi des ressources dʹaccès disponibles et de la taille des diverses extensions.

1- Lʹintégration dʹune cascade de sélections

Lorsque qu’un sous-arbre d’une requête est formulé une cascade de sélection,
σp1 (σp2 ( (σp3(R))) ≡ σp1∧p2∧p3(R) ≡ σp2∧p1∧p3(R) ≡ σp3∧p2∧p1(R)
où pi est un prédicat formulé avec les attributs de R.
σ p1 σ p1 ∧ p2 ∧ p3

Exemple : σ p2 ≡
R
σ p3

Figure 11.3

© A. Gamache 5
Chapitre 11 Optimisation des requêtes SQL

Exemple SQL :
SELECT nas, nom
FROM (SELECT nas, nom FROM Ouvrier WHERE salaire < 30 000)
WHERE nom = 'Gagnon' ;

Cette requête SQL sera plutôt exécutée par l’équivalent algébrique de la requête suivante :

SELECT nas, nom

FROM Ouvrier
WHERE salaire < 30 000 and nom = 'Gagnon' ;

Il en sera autrement lorsque la requête sous-tend des jointures. Dans ce cas, le prédicat conjonctif sera
distribué parmi des diverses sélections pertinentes à chaque extension participante à la jointure.

2- Commutativité des sélections

σp2∧ p1 (R) ≡ σ p1∧ p2 (R) ≡ σ p1 (σp2 (R))

Il peut être utile dans certains cas de transformer une cascade de prédicats en une conjonction des
mêmes prédicats. Inversement, il peut utile de remplacer une conjonction de prédicats distincts par
une cascade de sélections dans laquelle l’ordre des sélections importe peu.
La requête ci-dessus est équivalente à la suivante dans laquelle les prédicats ont été commutés :

SELECT nas, nom

FROM (SELECT nas, nom From Ouvrier WHERE WHERE nom = 'Gagnon')
WHERE salaire < 30 000);

3- Commutativité de la sélection avec la jointure ou le produit cartésien

Lorsque tous les attributs du prédicat de sélection sont inclus dans le schéma de lʹun des opérandes, il
est possible dʹexécuter la sélection avant la jointure.
σp (R1 |x| R2) ≡ σp (R1) |x| R2 ssi p ∈ R1
De même, comme la jointure est commutative, on aura aussi l’expression équivalente suivante :
σp (R1 |x| R2) ≡ R2 |x|σp (R1)

Toutefois, si le prédicat p peut être transformé en une conjonction de prédicats p1 et p2 de sorte que
tous les attributs de p1 soient inclus dans le schéma de R1 et que tous les attributs de p2 soient inclus
dans le schéma R2, alors on a l’équivalence suivante :
σp (R1 |x| R2) ≡ σ p1 ∧ p2 (R1 |x| R2) ≡ σ p1 (R1) |x| σ p2 (R1)

© A. Gamache 6
Chapitre 11 Optimisation des requêtes SQL

Voici un exemple dans lequel l’équivalence est exprimée entre deux arbres de requête.

σ nom =’Tremblay’ And noUs =10 |X| Usine.noUs = Ouvrier.noUs

≡ σ noUs =10 σ nom =’Tremblay’
|X| Usine.noUs = Ouvrier.noUs
Usine Ouvrier
Usine Ouvrier

Figure 11.4

Dans cette transformation par la commutativité, la sélection descend vers les feuilles, permettant ainsi
dʹeffectuer plus tôt dans le calcul la sélection des tuples et dʹobtenir une extension intermédiaire moins
encombrante qui, si la taille le permet, pourrait être rangée totalement dans la RAM. Cette stratégie
accélère le calcul en évitant les accès au disque.

Voici un exemple dʹune descente plus profonde de la sélection. Voici une requête SQL avec deux
jointures dont lʹune est exprimée sous forme dʹune sous-requête :

SELECT noCont
FROM Ouvrier O, Usine U
WHERE O.noUS = U.noUs and nom = 'Plante' and noUs = 10 And
noUS IN (SELECT noUS
FROM Contrat
WHERE fin > 'dec-97');

Cette requête initiale avec une sous-requête est transformée par l’analyseur en une jointure triple :
SELECT noCont
FROM Ouvrier O, Usine U, Contrat C
WHERE O.noUS = U.noUs And U.noUs = C.noUS And O.nom = 'Plante' and
U.noUs = 10 And C.fin > 'dec-97');

N.B. Cette requête est plus facilement représentée par un arbre de requête évitant l’usage d’un sous-
arbre dans le prédicat de jointure entre Ouvrier et Usine.
Lʹarbre de la requête est donc le suivant:

Π noCont
σ O.nom =’Plante’ And U.noUS = 10 And fin > ‘dec-1997’

|X| U.noUS = C.noUS

© A. Gamache |X| O.noUS = U.noUS 7

Contrat

Usine Ouvrier
Chapitre 11 Optimisation des requêtes SQL

Cet arbre de requête peut être transformé lors de l’optimisation en commutant la sélection avec la
jointure de sorte que la sélection soit exécutée le plus tôt possible dans le calcul de la réponse. En effet
une sélection réduit la taille de la table intermédiaire qui occupe moins d’espace disque ce qui entraîne
moins de lectures.
Π noCont

|X| U.noUS = C.noUS

σ fin > ‘dec-1997’

|X| O.noUS = U.noUS
Contrat
σ U.noUS = 10 σ O.nom =’Plante’
Usine Ouvrier

Figure 11.5

Dʹautres transformations algébriques sont possibles comme par exemple la permutation des jointures.
Celles-ci sont avantageuses, notamment si elles réduisent la taille des extensions intermédiaires dans
le processus dʹévaluation de lʹarbre de requête.

4- Absorption des projections dans une cascade

Une cascade de projections est équivalente à la dernière projection de la cascade.
Π liste1 ( Π liste2 (Πliste3 ( R))) ≡ Π liste1(R)

En effet la liste précédente doit obligatoirement contenir les attributs de la liste suivante. À la fin, seuls
les attributs de la dernière liste de projection seront présents dans la réponse.
Voici un exemple d’une requête SQL de ce type :
Select nas
From (Select nas, nom
From (Select nas, nom, salaire

© A. Gamache 8
Chapitre 11 Optimisation des requêtes SQL

From Ouvrier));

La transformation fournit une autre clause SQL équivalente, en principe plus simple à calculer.
Select nas
From Ouvrier;

5- Commutativité de la sélection et de la jointure (ou du produit cartésien)

Lorsque tous les attributs du prédicat p de la sélection sont inclus dans le schéma dʹune relation
opérande de la jointure précédente, on a lʹéquivalence suivante :
σp (R1 |x| R2) ≡ σp(R1) |x| R2 ssi p ⊆ R1

Toutefois, si p = p1∧ p2 et que p1 contient que les attributs de R1 et si p2 est formulé quʹavec les
attributs de R2 alors on aura que :

σp (R1 |x| R2) ≡ σp1(R1) |x| σp2(R2)

6- Commutativité de la projection avec la jointure

Deux cas de figure sont à distinguer :
Cas 1: Soit la liste dʹattributs de sortie L = { A1, A2, ...An, B1, B2,... Bk} et dans laquelle les attributs Ai
appartiennent au schéma de R1, tandis que les attributs Bk sont inclus dans le schéma de R2. Si la
condition de jointure cj est formulée quʹavec les attributs de la liste L, alors on a lʹéquivalence suivante
:
ΠL (R1|x|cj R2) ≡ Π(A1, A2, ...An) (R1) |x|cj Π(B1, B2, ...Bk) (R2)

Cas 2: Sʹil y a des attributs dans la condition de jointure qui ne sont pas dans la liste de sortie L, alors
ces attributs L’= {C1, C2, ...Ct} doivent alors être ajoutés à la liste L de la projection finale. Une
projection supplémentaire avec L est alors nécessaire afin de pouvoir transformer la projection initiale
de la jointure.
ΠL+L’ (R1 |x|R2) ≡ Π(A1, A2, ...An, C1, .. Ct) (R1) |x| Π(B1, B2, ...Bn, C1, ... Ck) (R2)

Exemple :
SELECT nom, salaire
FROM Ouvrier O, Usine U
WHERE O.noUs = U.noUs ;

Lʹarbre de requête correspondant est le suivant :

Π nom, salaire

© A. Gamache 9
|X| Ouvrier.noUs = Usine.noUs

Ouvrier Usine
Chapitre 11 Optimisation des requêtes SQL

Figure 11.7

Lʹattribut noUs nʹest donc pas dans la liste de la projection et il y sera ajouté pour descendre la
projection et faire commutation avec la jointure .

Π nom. salaire

|X| Ouvrier.noUs = Usine.noUs

Π nom, salaire, noUs Π nom, salaire, noUs

Ouvrier Usine
Figue 11.8
Cette transformation permet en théorie de diminuer la taille de lʹextension en diminuant la taille de
chaque tuple. Dans certains cas, cette transformation place beaucoup plus de tuples dans la zone de
mémoire partagée de sorte quʹil y aura accélération du calcul de la jointure. Rappelons encore une fois
que si le SGBD exécute en pipeline cette clause, la jointure de deux tuples est accompagnée de la
projection sur le ou les attributs de sortie.

7- Commutativité de la sélection et de la projection

Sachant que la jointure est équivalente à une sélection du produit cartésien :

(R1 |x| R2) ≡ σR1.A = R2.A(R1 x R2) (1)

On a donc la suite des transformations suivantes :

ΠA, B (R1 |x| R2) ≡ Π A, B (σR1.A = R2.A (R1 x R2)) ≡ σR1.A = R2.A(ΠA, B (R1 x R2)) ≡ σ R1.A = R2.A
(ΠAR1 x Π A, B (R2)))
Dans cet exemple, la jointure est transformée en un produit cartésien et il y a
commutation entre la projection et la sélection (3). Ensuite la projection est
commutée avec le produit cartésien (4) pour provoquer une descente de la projection
vers les opérandes. Finalement, la sélection et le produit cartésien sont fusionnés
pour donner une jointure thêta (5).

L’arbre de requête est graduellement transformé pour donner la suite suivante :

© A. Gamache 10
Chapitre 11 Optimisation des requêtes SQL

Π a,b Π a,b σ R1.a = R2.a σ R1.a = R2.a |X|R1.a = R2.a

σ R1.a = R2.a Π a,b X Π a,b Π a,b

|X| R1.a = R2.a ≡ ≡ ≡ ≡

XR1.a = R2.a XR1.a = R2.a Π a,b Π a,b

R1 R2
R1 R2

R1 R2 R1 R2 R1 R2
(1) (2) (3) (4) (5)

Figure 11.6

L’exécution de cet arbre se fait de bas en haut. Il ne faut y avoir un calcul essentiel sériel. En effet, La
projection de R 1 est combinée la jointure pour que les deux opérations s’effectuent en parallèles.
Voici un exemple en SQL d’une telle transformation :
Select O.noUs, O.nom
From Ouvrier O, Usine U
Where O.noUs = U.noUs ;

Cette simple jointure pourrait être exécutée avec la projection des deux relations Ouvrier et Usine. En
principe, une telle transformation accélère le calcul si chaque opérateur est exécuté complètement
avant que le suivant soir lancé.

Select O1.noUs, O1.nom

From (Select noUs, nom From Ouvrier) O1, (Select noUs From Usine) U1
Where O1.noUs = U1.noUs ;

En pratique, cette transformation ne se fera pas, car la première forme peut être exécutée rapidement
en mode pipeline : un tuple de Ouvrier est comparé avec un tuple de Usine. Si la condition de jointure
est vérifiée, alors la projection du tuple est faite immédiatement et le résultat est stocké dans la table
de la réponse. On voit donc que seule la transformation algébrique est insuffisante pour obtenir une
exécution optimisée. Il faut aussi prendre en compte les algorithmes de calcul qui peuvent réaliser
plusieurs opérateurs dans une seule exécution. Ce rôle est dévolu à l’optimiseur qui se doit de
produire un PLAN D’EXÉCUTION de la requête formulée avec les algorithmes disponibles dans le
SGBD pour le calcul des requêtes.

8- Commutativité de la sélection avec lʹintersection, lʹunion et la différence

Avec ces opérateurs ensemblistes, il y a une obligation préalable concernant la compatibilité des
schémas. Les équivalences suivantes sont vérifiées :
σp (R1 ∩ R2) ≡ σp(R1) ∩ σp (R2)

© A. Gamache 11
Chapitre 11 Optimisation des requêtes SQL

σp (R1 ∪ R2) ≡ σp(R1) ∪ σp (R2)

σp (R1 − R2) ≡ σp(R1) − σp (R2)

Les arbres correspondants sont faciles construire ainsi :

L’intersection de deux relations :
σp ∩

∩ ≡ σp σp

R1 R2 R1 R2

L’union de deux relations :

∪
σp

≡ σp σp
∪

R1 R2 R1 R2

Différence entre deux relations :

σp −

− ≡ σp σp

R1 R2 R1 R2

Figure 11.9

En SQL-92, ces arbres correspondraient aux requêtes suivantes:

SELECT nom
FROM (SELECT *
FROM Ouvrier
INTERSECT
SELECT *
FROM OuvrierEnMission)
WHERE salaire > 50000 and noUs = 'u20';

© A. Gamache 12
Chapitre 11 Optimisation des requêtes SQL

La relation ou la vue relationnelle OuvrierEnMission est présumée avoir été créée dans le dictionnaire
avec un schéma identique à celui de la relation de base Ouvrier. Dans cette requête la sélection est
effectuée en dernier et constitue ce qui et appelé le 2e bloc de la clause SQL.
La requête équivalente dans laquelle la sélection est effectuée en premier avant l’intersection.

SELECT nom
FROM Ouvrier
WHERE salaire > 50000 and noUs = 'u20'
INTERSECT
SELECT nom
FROM OuvrierEnMission
WHERE salaire >50000 and noUs = 'u20';

Voici un exemple similaire avec lʹunion. Cet opérateur exige aussi deux schémas compatibles pour
que le calcul soit exécutable. Dans ce cas-ci, le schéma des deux opérandes est compatible avec lʹautre.
L’un des opérandes est une vue relationnelle OuvriersEnConge.

SELECT nom
FROM Ouvrier
WHERE salaire > 25000 and salaire < 50000
UNION
SELECT nom
FROM OuvriersEnConge
WHERE salaire > 25000 and salaire < 50000 ;

9- Commutativité des opérateurs ensemblistes : union et intersection

Ici encore, les deux schémas logiques, R1 et R2 doivent être identiques.
(R1 ∪ R2) ≡ (R2 ∪ R1)
(R1 ∩ R2) ≡ (R2 ∩ R1)
Toutefois, cette propriété ne tient pas pour la différence. L’inversion des opérandes change le contenu
de la réponse.

10− Associativité des opérateurs de jointure, du produit cartésien, de lʹunion et de lʹintersection.

Soit une double jointure :
R1 |x|(R2 |x|R3) ≡ (R1 |x|R2) |x|R3

Lʹassociativité est réalisée avec R1 et R2 puisque cette dernière relation, R2 comprend lʹattribut de
jointure de R1
R1 x (R2 x R3) + (R1 x R2) x R3
R1 ∪ (R2 ∪ R3) ≡ (R1 ∪ R2) ∪ R3
© A. Gamache 13
Chapitre 11 Optimisation des requêtes SQL

R1 ∩ (R2 ∩ R3) ≡ (R1 ∩ R2) ∩ R3

Heuristique générale de lʹoptimisation dʹune requête

Le principe général de l’optimisation algébrique est la transformation de lʹarbre de la requête initiale
en un autre équivalent en présumant quʹil est probablement plus rapide à exécuter4. Cette heuristique
est assistée par lʹaccès aux statistiques des tables et par la présence des index dans le dictionnaire.
Les étapes sont les suivantes :
1- Les prédicats de sélection sont transformés, sʹil y a lieu, en une cascade afin de pouvoir par la
suite les descendre vers les feuilles de lʹarbre, i.e. vers les relations de base. Lʹhypothèse sous-
tendue par cette opération est que le prédicat est suffisamment sélectif pour diminuer la taille des
relations intermédiaires et ainsi alléger les calculs, notamment ceux de jointure.
2- Descendre les opérateurs de sélection le plus bas possible en utilisant la commutativité de la
sélection avec les opérateurs de projection, de jointure, de l’union et dʹintersection.

3- Réorganiser les feuilles de lʹarbre en utilisant lʹassociativité des opérateurs binaires de sorte que le
sous-arbre ayant la sélection la plus restrictive soit exécutée en premier.

4- Transformer toute suite formée dʹune sélection et dʹun produit cartésien en une jointure thêta.

5- Descendre le plus possible les projections vers les feuilles de lʹarbre de requête.

6- Identifier les sous-arbres ayant des opérateurs qui peuvent être exécutés en même temps que
dʹautres (mode pipeline), notamment la sélection. Par exemple, une sélection suivie dʹune projection
est une paire dʹopérateurs exécutables simultanément.
Quelques problèmes avec lʹheuristique générale
La restructuration dʹun arbre de requête sous-tend très souvent la permutation des opérateurs
binaires, notamment celui de la jointure. Or, ces permutations algébriques ne sont pas toujours
justifiées sur la plan de la performance. Au contraire la connaissance de la taille des extensions de base
et de celles des relations intermédiaires peut réduire les avantages de ces transformations. Par
exemple une suite de jointures peut être transformée en plusieurs arbres de requête différents et le
choix de lʹarbre optimisé à exécuter est difficile si on ignore la taille des extensions, les facteurs de
sélectivité pour les différents opérateurs et lʹindexation des attributs.
Exemple :
(Ouvrier |x| Usine) |x| Contrat

Si card(Usine) <<< card(Contrat) <<< card(Ouvrier) alors lʹexpression ci-dessous a des chances dʹêtre
plus performante pour le calcul de la réponse.
( Usine |x| Contrat) |x| Ouvrier)

© A. Gamache 14
Chapitre 11 Optimisation des requêtes SQL

La taille de la relation intermédiaire résultant par exemple la jointure (Usine |x| Contrat) est plus
petite si la sélectivité de lʹattribut de jointure dans Contrat est près de 1 (grande sélectivité). Elle sera
vraisemblablement plus rapide à calculer. La sélectivité de lʹattribut de jointure dans chaque relation
interviendra donc dans le choix de la permutation de jointures. Toutefois, la cardinalité des extensions
et les sélectivités des attributs ne sont pas les seuls facteurs qui conditionnent la rapidité du calcul. La
présence dʹun index sur lʹattribut de jointure de la relation Ouvrier augmentera de façon significative
la vitesse de calcul de la relation intermédiaire. Cette nouvelle donne, le SGBD peut la découvrir à
partir des métadonnées stockées dans le dictionnaire. Il se peut fort bien qu’un index compense pour
lʹencombrement et fait en sorte que lʹexpression initiale soit celle qui est retenue comme étant lʹarbre
optimisé.

Un autre problème peut apparaître avec la transformation algébrique, notamment lors de la

permutation de la sélection avec la jointure. Un index est créé sur une table de base et peut être utilisé
que pour lʹaccès à aux tuples. de cette table.
σ |x|
R1.A = R2.A
p

|x| R1.A = R2.A* σp R2

* indexation de A dans R1
R1 R2 R1

Figure 11. 10

Or, si lʹopération de sélection est effectivement descendue le plus bas possible vers les feuilles et
appliquée avant la jointure, le résultat est une relation intermédiaire qui n’est plus indexée, car un
index du dictionnaire pointe sur les tuples dʹune table de base dont il connaît lʹemplacement. Par
conséquent, même si lʹattribut est indexé dans la table de base, celui-ci ne peut pas être utilisé dans la
table intermédiaire. Sʹil arrive que lʹattribut descendu soit celui de la jointure, alors cette descente
inhibant lʹutilisation de lʹindex dans le calcul de la jointure, autant alors l’éviter et faire en pipeline la
jointure et la sélection.
Limite de l’optimisation algébrique
On voit donc que la seule optimisation algébrique est insuffisante et peut même conduire à des
ralentissements du calcul. De plus, les diverses transformations algébriques conduisent à de
nombreux arbres de requêtes possibles parmi lesquels lʹoptimiseur doit sélectionner celui qui
deviendra le plan à exécuter. Or, cette sélection ne donne pas toujours les résultats escomptés parce
que des informations manquent pour guider ce choix. Ces métadonnées manquantes sont notamment,
la cardinalité des extensions, la sélectivité des attributs et la présence des index. Ces informations
seront à la base même de lʹoptimisation fondée sur le coût.

Modèle de coût
Pour estimer la taille des résultats intermédiaires, lʹoptimiseur doit avoir accès aux métadonnées
suivantes:

© A. Gamache 15
Chapitre 11 Optimisation des requêtes SQL

a- La distribution des valeurs de chaque attribut, sinon il fut assumer lʹhypothèse simplificatrice dʹune
distribution uniforme pour les valeurs des attributs et de faire aussi lʹhypothèse que ces derniers sont
indépendants les uns des autres.

b- Dans une extension, le nombre de valeurs non null pour un attribut Ai est noté card(Ai);

c- Les valeurs min(Ai) et max(Ai) pour chaque attribut de lʹextension courante; cette métadonnée
permettra de connaître le nombre maximum de valeurs différentes possible présentes dans la table;

d- La cardinalité de lʹextension de chaque relation, soit card(R1);

e- Le nombre de valeurs distinctes pour chaque attribut Ai dans une relation R, soit V(Ai, R).
Ces métadonnées stockées dans le dictionnaire permettront dʹavoir une meilleure approximation des
tailles des relations intermédiaires et cela, grâce à la sélectivité si associé à chaque opérateur. Pour un
calcul plus précis, il faudra sʹéloigner de la distribution uniforme présumée et calculer la distribution
des valeurs pour chaque attribut. Ce calcul plus lourd ne conduit pas toujours un gain significatif de
performance.

Sélectivité dʹun opérateur : si

En présumant une distribution uniforme des valeur, la sélectivité si dʹun attribut Ai est définie ainsi :
si = V(Ai, r)/card(r)
pi = 1/V(Ai, r)

La probabilité pi est celle de trouver une valeur donnée dans une extension R ou la fraction des
tuples qui seront obtenus par un opérateur de sélection. Par exemple, lʹattribut sexe dans une
extension a la probabilité de 1/2. Par conséquent avec une distribution uniforme, la moitié des tuples
de lʹextension courante réfèrent à des hommes, tandis que lʹautre à des femmes.

Sélection
Soit lʹopération de sélection suivante: σp(R1) où le prédicat est formulé quʹavec lʹattribut A, soit p (A=
10). Le nombre de tuples dans la réponse est estimé par
card(σp (R1)) = P(A) ∗ card(R1)

avec P(A), la proportion des tuples de R1 qui vérifient le prédicat p(A). Or, cette proportion est la
probabilité quʹun tuple de R1 vérifie le critère de sélection p définie pour cet opérateur comme étant le
suivant : P(A) = 1/V(Ai, R1)soit le la sélectivité du prédicat de sélection.
card(σp (R1)) = P(A) ∗ card(R1) = card(R1)/ V(Ai, R1)= si * card(R1)

© A. Gamache 16
Chapitre 11 Optimisation des requêtes SQL

Pour une extension donnée, plus le nombre de valeurs distinctes est grand, plus la taille de la réponse
sera petite. Dans le cas dʹune distribution non uniforme, le calcul de V(A, R1) est fonction de la nature
de A et de la distribution courante. Si la distribution n’est pas uniforme, il faut avoir l’histogramme
maintenu dans le dictionnaire. Avec ce dernier, il est possible de connaître combien de tuples ont une
valeur donnée pour chaque attribut. La sélectivité d’un attribut pour un intervalle de valeurs peut
alors être calculée plus précisément.

Projection
Une projection sous-tend toujours la suppression des doublets dans sa réponse. Plus le nombre de
doublets est grand plus la réponse risque dʹêtre petite. Par exemple, la projection de la relation
Ouvrier sur lʹattribut sexe, ne fournira que deux valeurs. La liste des attributs peut être plus ou moins
élaborée.
a- Avec une liste formée dʹun seul attribut A de R1 qui en est aussi la clé.
card(Π(A) ) = card(R1)

b- Avec une liste formée dʹun seul attribut quelconque A de R1

card(ΠA(R1)) = card(R1) ∗ P(A) = card(R1) ∗ 1/ V(A, R1)
où P(A) est la proportion des tuples avec une valeur distincte pour A.

c- Avec une liste formée avec deux attributs quelconques, A et B

card(ΠA, B (R1)) = card(R1) - (card(R1)∗ d) = card(R1) ∗ (1 - d)

où d est la proportion des tuples de R1 qui sont des doublets sur les deux attributs A, B. Or, comme
nous avons présumé une distribution uniforme, cette proportion d est valable pour toutes les paires
de valeurs qui apparaissent dans la table R1.
Jointure
La taille dʹune jointure est estimée grosso modo (approximation de 1er ordre) par la formule suivante :
R1 |x|R2 = Pj ∗ (card(R1) ∗ card(R2))
où Pj est la sélectivité de la jointure.

Calcul de la sélectivité pour une jointure: Pj

Supposons que la condition de jointure soit R1.A = R2.A et que lʹattribut A de R1 soit indépendant de
A de R2. Cela signifie quʹil nʹexiste pas de corrélation entre le A des deux relations.

Chaque tuple t de R1 est joint avec card(R2)/V(A,R2) tuples de R2, de sorte que nous avons au plus,
card(R1 |x| R2) = (card(R1) ∗ card(R2))/V(A, R2) = card(R1) ∗ card(R2) ∗1/V(A, R2)
card(R1 |x|R2) = card(R1) ∗ card(R2) ∗ Pj

© A. Gamache 17
Chapitre 11 Optimisation des requêtes SQL

et donc Pj = 1/V(A, R2). Toutefois, ce résultat suppose que tous les tuple de R1 (ou R2) participent à la
jointure.

La sélectivité de la jointure est estimée comme étant égale à lʹinverse du nombre de valeurs distinctes
de A dans la 2e relation opérande de la jointure. Cette sélectivité est généralement calculée avec les
statistiques recueillies dans le dictionnaire des données. Elles sont mises à jour périodiquement avec
ou sans l’intervention de l’administrateur de la base de données.

En inversant la jointure, on obtient :

card(R2 |x|R1) = (card(R1) ∗ card(R2))/V(A, R1) =
card(R2) ∗ card(R1) ∗ 1/V(A, R1) et donc Pj = 1/V(A, R1).

Il y a donc un avantage théorique avec les hypothèses avancées à exécuter une jointure en plaçant
comme premier opérande la relation ayant la plus petite taille. Ces estimés de Pj et les tailles des
extensions courantes varient avec la mise à jour des tables. Ces données sur les tables sont des
métadonnées rangées dans le dictionnaire de données du SGBD.

Ces métadonnées sont actualisées périodiquement par lʹexécution de la commande ANALYZE (pour
Oracle), RUNSTATS (pour DB2-V2) et UPDATE STATISTICS (pour IBM-Informix)

Cette approche ne tient pas compte des structures de données et de la charge dʹentrée-sortie
nécessaire pour traiter les tuples des relations. Il y a des structures telles les clusters, les index et le
hashing qui accélèrent passablement lʹaccès aux tuples et de ce fait allègent le calcul de la jointure.
Lorsque le plan dʹexécution estimé le plus efficace a été choisi, il est alors exécuté en faisant appel aux
algorithmes de base pour calculer la sélection, la projection et la jointure. Ceux-ci sont implémentés en
mettant à contribution les ressources présentes comme les index (cluster/non-clustered et dense/sparse),
les clusters et le hashing. Le choix dʹun algorithme pour calculer une jointure dépendra donc des
structures de données existantes au moment du calcul.

Algorithmes généraux pour les opérateurs relationnels

Sélection
Le calcul de la sélection peut se faire avec ou sans index. A priori lʹintérêt de lʹindex est grand, mais
son utilité dépend de la sélectivité du prédicat ou dʹune de ses parties appelées sous-critère. Plus la
sélectivité dʹun attribut A est faible, moins il y a dʹintérêt à utiliser son index.
a- Sélection sans index
La construction dʹun index est généralement coûteuse et nécessite un parcours séquentiel des tuples.
En général, comme les pages contiennent que des tuples dʹune même table, il est souvent plus
performant de parcourir les pages en testant un à un les tuples en regard du prédicat de sélection.
Tout tuple retenu est alors projeté immédiatement sur les attributs de la réponse (traitement pipeline)
et ensuite ajouté à lʹensemble réponse.

© A. Gamache 18
Chapitre 11 Optimisation des requêtes SQL

Lʹabsence dʹun index nʹest pas nécessairement catastrophique lorsquʹil sʹagit dʹattributs de faible
sélectivité (i.e. que pour une valeur de lʹattribut, beaucoup de tuples sont à vérifier). Il peut être aussi
rapide de parcourir séquentiellement une extension de la relation de taille raisonnable dont une partie
est en mémoire. Finalement, comme les pages contiennent que des tuples de même schéma logique, le
balayage total de lʹextension utilisera un minimum de pages.

Exemples :
La requête dʹintervalle ci-dessous peut être traitée efficacement même en lʹabsence dʹun index.
SELECT nas, nom
FROM Ouvrier
WHERE salaire > 15000.00 ;

En effet, on peut estimer avec les métadonnées que 85% des ouvriers ont un salaire supérieur à
15000.00 et quʹun balayage séquentiel sera plus efficace. Le seuil pour préférer le parcours séquentiel
est souvent fixé à à un facteur de sélectivité supérieur à 0.35.
Plan dʹexécution:
{
t : tuple de l’extension Ouvrier;
reponse m : set de_tuples; -- projection de Ouvrier sur
--attributs de sortie
Pour chaque tuple t de Ouvrier -- accès séquentiel
do
si t.salaire > 15000
alors reponse = reponse ∪ t[nas, nom]
fin_do
fin;}
Le plan d’exécution repose essentiellement sur un parcours séquentiel de la table. Lʹefficacité de cet
algorithme dépendra essentiellement de la taille de l’extension de la table Ouvrier.
b- Sélection avec index
Il peut y avoir, dans un prédicat de sélection, plusieurs attributs qui sont déjà indexés par autant de B-
arbres et dont lʹadresse de la racine de chaque arbre, rappelons-le, est stockée dans le dictionnaire du
SGBD. Il faut généralement faire un choix préalable pour exploiter dans le calcul que les attributs
indexés qui sont les plus sélectifs, i.e. ceux dont le facteur de sélectivité se rapproche de 1. Souvent, le
SGBD retient que les attributs dont la sélectivité dépasse un seuil donné. Les autres attributs seront
testés après lʹaccès aux tuples identifiés ou obtenus par un balayage séquentiel des tuples
éventuellement identifiés par lʹindex. Lʹorganisation de lʹindex disponible a aussi un impact sur la
performance du calcul. Un index dense/non-clustérisé sera moins performant quʹun autre
dense/clustérisé.
Ainsi, si le prédicat est formé dʹune conjonction d’attributs, le SGBD construira une liste dʹadresses
avec chaque attribut indexé, pour ensuite faire lʹintersection des rowid obtenus. Le résultat fournira les
adresses de tuples dont lʹaccès direct permettra de vérifier les autres attributs non indexés.

© A. Gamache 19
Chapitre 11 Optimisation des requêtes SQL

Rappel:
Un index dense est un index sur un attribut dont chaque pointeur conduit à un tuple. Au contraire, si
le pointeur conduit à un lot de tuples (ex. une page, lʹindex est dit non dense.
De même, si les entrées voisines dans lʹindex conduisent à des tuples qui sont à proximité voire dans
la même page, lʹindex est dit regroupé i.e. clustérisée. Au contraire, il est dit non clustérisé (sparse)

Algorithme SIDX2
Indexation de deux attributs du prédicat : (index sur salaire et une autre sur noUs)
SELECT nas, nom
FROM Ouvrier
WHERE salaire >= 25000.00 and noUs = 'u20'
and nom = 'Tremblay';

Plan dʹexécution :
Deux index sont utilisés : index idx_salaire et idx_noUs déjà définis sur la relation Ouvrier et
répertoriés dans le dictionnaire. La réponse est calculée sans avoir recours dans une première étape
aux tables.
{ --SIDX2
S, U, I set de rowid de Ouvrier;
S = Lire (idx_salaire_Ouvrier, 25000);-- set de rowid
U = Lire(idx_no_us_Ouvrier, 'u20'); -- set de rowid
I = Intersection (S, U); -- pour critère ET
Pour chaque rid de I -- rid est une adresse de tuple
do
{
t = Lire (Ouvrier, rid) --lire directe de t qui est un tuple
-- de Ouvrier
si t.nom = 'Tremblay' alors
reponse = Union ( reponse, (t.nas, t.nom));
fin_do;
fin;
Lorsque les critères sont liés par un OU, alors il y aura Union des ensembles S et U. Certains systèmes
adoptent une stratégie efficace soit dʹexploiter un index et de vérifier les autres critères en même
temps que lʹaccès aux tuples.

Une autre méthode encore plus efficace consisterait à lire dans le B-arbre la première feuille pour la
valeur 25000.00 et parcourir horizontalement les autres feuilles jusquʹà la dernière en vérifiant pour
chaque tuple si les autres termes du prédicat conjonctif sont vérifiés. Ce balayage via lʹindex est
efficace si la sélectivité de lʹattribut est assez grande.
Jointure sans index

© A. Gamache 20
Chapitre 11 Optimisation des requêtes SQL

La jointure peut être calculée par différents algorithmes selon la présence ou lʹabsence dʹindex sur les
attributs de jointure. En lʹabsence dʹindex, le calcul est fait en exploitant au maximum la structure
particulière du placement des tuples parmi les pages. Dans une jointure de type R1 |x| R2, nous
ferons lʹhypothèse que le premier opérande est toujours formé avec la relation ayant la plus petite
extension.
a- Algorithme de jointure par boucles imbriquées (JBI)
Cet algorithme est le plus simple, mais souvent le moins efficace avec des extensions de grandes
tailles. La première extension est lue séquentiellement et de préférence stockée entièrement en RAM.
Pour chaque tuple de R1 en RAM, il y a une comparaison avec les tuples de la deuxième extension,
R2. Soit np(R1) le nombre de pages utilisées pour stocker les tuples de R1, alors le coût de ce calcul est
approximé par :
Coût-JBI = np(R1) + np(R1) * np(R2)
Le coût est composé des pages de R1 lues initialement pour les placer en mémoire. Ensuite, pour
chaque page de R1 il faut lire toutes les pages de R2.

Soit les deux attributs de jointure A et B des relations R1 et R2, alors lʹalgorithme BI est le suivant :
{ -- JBI
Pour chaque tuple de R1
{do
Lire (R1, t1);-- t1 est une var. de tuple
Pour chaque tuple de R2
{do
Lire (R2, t2);
si t1.A = t2.B alors
reponse = t1 || t2 ;}}}
Cet algorithme est dʹautant plus coûteux que le nombre de pages de R2 est élevé.
b- Jointure par tri-fusion (JTF)
Les deux extensions sont en premier triées sur les deux attributs de jointure et ensuite les tuples triés
sont fusionnés pour retenir que les tuples ayant la même valeur pour les attributs de jointure. le coût
du tri est de lʹordre de nlog2n avec n égale au nombre de pages dʹune extension. Le traitement des
tuples en RAM est considéré comme négligeable.

Le coût de cet algorithme est composé des coûts de lecture des pages en mémoire :
coût-JTF = np(R1)*log2(np(R1)) + np(R2)*log2(np(R2)) + np(R1) + np(R2)
Cet algorithme est plus performant que le précédent. Son efficacité dépend essentiellement de celle
du tri utilisé (ex. Quicksort).
{-- Algo JTF
R1 = Trier (R1, A);
R2 = Trier(R2, B);
reponse = fusion de R1 et de R2;
fin;
© A. Gamache 21
Chapitre 11 Optimisation des requêtes SQL

}
c- Jointure par hashing (JH) : équijointure
Lʹidée de base est lire séquentiellement les tuples de la plus petite extension, R1 et de traiter par
hashing la valeur de lʹattribut de jointure A. Aucun attribut de la jointure n’est indexé ou si la
sélectivité de l’attribut de jointure est très grande. Tous les tuples de R1 qui ont une même valeur de
hashing sont placés dans une même page temporaire. Celle-ci est rappelée lors du calcul de la
jointure. Lors du hashing, les pages sont gardées le plus longtemps en mémoire RAM afin de pouvoir
y ranger, dans un deuxième temps, les tuples de R2 qui ont la même valeur de hashing.

t2 de R2
2 pages de
H(t2[B])
données

t1 de R1
H(t1[A])

1 ZMP

Figure 11.11
La deuxième relation R2 est lʹobjet du même traitement par hashing sur lʹattribut B. Dans une même
page, se retrouvent donc les tuples différents mais ayant la même valeur de hashing.
Hashing (R1, A, R2, B)
{ int p;
Pour chaque t1 de R1
do {
Lire (R1, t1)
p = h(t1, A);
Ecrire(page p, t1);
}
Pour chaquet2 de R2
do {
Lire (R2, t2);
Accéder(pagesR1, t2.B);
si TRUE alors Ecrire(reponse, t1||t2);}}
Si cette opération de regroupement est effectuée lors du chargement initial de chaque tuple, le
regroupement par la valeur de lʹattribut de jointure se fait progressivement (clustering). Dans ce cas, il
faudra déclarer un cluster qui devrait sous-tendre la création de deux index denses et regroupés
(clustered), un pour A et un autre pour B. La jointure se fera alors par lecture des tuples stockés dans
les pages clustérisées. Si une page vient à déborder, il y a gestion du débordement par chaînage des
pages. Au moment de la jointure, il suffit donc de faire la jointure des tuples qui se retrouvent dans la
même page ou à proximité, en vérifiant quʹils ont la même valeur pour les attributs de jointure et cela,
© A. Gamache 22
Chapitre 11 Optimisation des requêtes SQL

pour éviter les jointures de tuples qui sont en collision. Cet algorithme peut être utilisé efficacement
qu’avec l’équijointure, i.e. un prédicat de jointure construit avec l’égalité.
Jointure sans clustering préalable
Lorsque les tuples ne sont pas au préalable regroupés (clustered), il faudra en premier effectuer cette
opération de lecture et de placement des tuples dans des pages temporaires. Cette opération est
lourde en terme de temps de lecture. Une fois les tuples regroupés, lʹalgorithme se poursuit avec le
calcul de la jointure.

Une variante de cet algorithme est proposée par Babb5 . Elle est intéressante dans les cas où le
clustering est à faire ponctuellement (dynamiquement), juste avant le calcul de la jointure. Il sʹagit de
construire et dʹutiliser un vecteur de bits qui signale la présence dʹun tuple ayant une valeur de
hashing dans la première relation. Le vecteur de bits est gardé en mémoire RAM.

R1 0 R2
1 Vecteur de bits

1
0
1
Tuple t de R1 0 Tuple t de R2
?
1
h(t[A] = x 1 h(t[B] = x
x est l’indice dans le vecteur 0 x est l’indice dans le vecteur

Figure 11.12
En calculant la valeur de hashing dʹun tuple de R2 et de son indice correspondant dans le vecteur, il
est possible de savoir rapidement si les deux tuples doivent être joints ou pas. En effet, si la valeur
obtenue correspondant à un bit 1, cela signifie quʹil peut exister un tuple de R1 ayant la même valeur
pour lʹattribut de jointure. Ce tuple est recherché en RAM ou sur disque. Lʹintérêt de cet algorithme
est que la lecture des tuples ne se fait que pour ceux dont on est certain quʹils seront joints. Au
contraire, si le bit est 0, alors le tuple de R2 peut être mis de côté ou ne pas être lu, car il ne peut être
joint à aucun tuple de R1.
Optimisation avec le SGBD Oracle
Il y a au moins deux modes dʹoptimisation disponibles et spécifiés dans le fichier des paramètres
INIT.ORA : OPTIMIZER_MODE = {RULE, COST}. Le mode RULE repose sur le calcul dʹune
pondération globale obtenue à partir dʹune table de poids pour chaque chemin dʹaccès que peut
prendre en compte le noyau du SGBD. Avec les versions plus récentes (version 7 et suivantes), la
mode par coût est devenu le mode par défaut et le nouvel optimiseur est aussi capable de générer des
plans dʹexécution performants avec ce mode. Les étapes sont le suivantes :
1- génération dʹun ensemble de plans qui reposent sur les chemins dʹaccès;
2- ordonnement des plans avec les statistiques obtenues par la commande ANALYZE;

© A. Gamache 23
Chapitre 11 Optimisation des requêtes SQL

3- choix du plan dʹexécution qui a le moindre coût en ressource;

Le plan d’exécution dʹune requête est accessible par lʹentremise de la table System.Plan_table
et la commande EXPLAIN PLAN.
EXPLAIN PLAN set statement_id = 'q1'
INTO [system.]Plan_table FOR
select * from Empl where age <= 30';

Pour lire le plan dʹexécution généré il suffit de le lire dans la table Plan_table :
SELECT operation, options, object_name
FROM system.Plan_table
WHERE statement_id = 'q1';

Le plan affiché est lu de bas vers le haut.

OPERATION OBJECT_NAME
SELECT STATEMENT
Table access Empl by ROWID
Index Empl_age_idx RANGE SCAN
Figure 11.13
Lʹindex sur âge est utilisé pour trouver le premier rowid du tuple correspondant à 30. L’opération qui
est suivie dʹun parcours séquentiel dans lʹindex pour trouver les autres adresses rowid qui
correspondent aux employés dont lʹâge et inférieur ou égal à 30 (Range Scan). Pour chaque adresse
(rowid ou rid) trouvée, il y a un accès direct au tuple correspondant.
Par contre, une jointure donnera un plan dʹexécution comme celui-ci :
SELECT U.site, C.noCont, C.fin
FROM Usine U, Contrat C
WHERE U.noUs = C.noUs;
Le plan affiché par la commande EXPLAIN PLAN sera le suivant:

OPERATION OBJECT_NAME OPTIONS

SELECT STATEMENT
NESTED LOOPS
TABLE ACCESS Contrat FULL
TABLE ACCESS Usine BY ROWID
INDEX Usine UNIQUE SCAN
Figure 11.14

© A. Gamache 24
Chapitre 11 Optimisation des requêtes SQL

Lʹindex sur la relation Usine sera utilisé en accédant à sa première entrée et avec ce premier rowid, le
tuple correspondant dans la table Usine est consulté. Ensuite, pour ce tuple, il y a aura un balayage
séquentiel de la relation Contrat.

Pour que cette approche soit suivie, il faut que les statistiques aient été générées pour les tables, les
index et les clusters utilisés par les requêtes. Si celles-ci ne sont pas disponibles, le système sera forcé
dʹutiliser une approche par les règles (RULE based). Les statistiques sont au départ celles par défaut et
elles sont mises à jour à chaque fois que la commande ANALYZE est lancée par le DBA.
ANALYZE TABLE Ouvrier COMPUTE STATISTICS;
ou
ANALYZE TABLE Ouvrier ESTIMATE STATISTICS SAMPLE 3000 rows;

Pour obtenir les statistiques produites, notamment le nombre de tuples, la longueur moyenne dʹun
tuple, le nombre de valeurs distinctes pour chaque attribut, la plus grande valeur et la plus petite, il
suffit de consulter les tables USER_TABLES, USER_TAB_COLUMNS, USER_INDEXES.
Exemple :
SELECT *
FROM USER_TAB_COLUMN

Lʹapproche par coût est modulée par un paramètre qui est le but recherché. Deux buts sont possibles :
ALL_ROWS (le défaut) et FIRST_ROWS. Le premier but sous-tend une recherche pour obtenir tous les
tuples de la réponse dans le meilleur temps possible. Le deuxième but imposé au SGBD de retourner
au moins un tuple dans le plus court délai possible.
Optimisation par les coûts
Cette optimisation repose sur l’importance des écritures et des lectures prévisibles à partir des
statistiques rangées dans le dictionnaire. La mise à jour de ces statistiques est de la responsabilité du
DBA. Plusieurs paramètres régissent le fonctionnement ce mode d’optimisation et doivent être
précisés par l’administrateur :

a- OPTIMIZER_MODE : RULE ou COST (le défaut si les statistiques sont disponibles)

b- SORT_AREA_SIZE : taille de la mémoire disponible pour le tri
c- HASH_AREA_SIZE : taille de la mémoire disponible pour le hachage
d- HASH_JOIN_ENABLED : jointure par hachage autorisée

La collecte des statistiques est rendue possible par l’exécution de l’utilitaire ANALYSE qui obtient les
informations suivantes sur une table particulière de la base :

Information sur une table Description

NUM_ROWS Nombre de tuples

© A. Gamache 25
Chapitre 11 Optimisation des requêtes SQL

BLOCKS Nombre de pages sur disque

EMPTY_BLOCKS Nombre de pages libres sur disque
AVG_SPACE Espace moyen libre par page de données
CHAIN_CNT Nombre de pages chaînées
AVG_ROW_LEN Taille moyenne des tuples dans une table
SAMPLE_SIZE Taille de l’échantillon utilisé
LAST_ANALYSED Date de la dernière analyse sur une table

Ces informations sont conservées dans les tables du dictionnaire : DBA_TABLES, ALL_TABLES,
USER_TABLES qui sont accessibles à l’administrateur ayant les privilèges appropriés.

Les index peuvent aussi être analysés par l’utilitaire ANALYSE et les données obtenue stockées dans
les tables DBA_INDEX, ALL_INDEX, USER_INDEX.

Exemples :
ANALYSE TABLE Ouvrier COMPUTE STATISTICS FOR TABLE ;
ANALYSE TABLE Ouvrier COMPUTE FOR ALL INDEX ;
ANALYSE INDEX Ouvrier_idx COMPUTE STATISTICS ;

Affichage du plan dʹexécution dʹune requête

Le plan dʹune exécution optimisée peut être affiché par la commande suivante et cela avant que le
plan soit exécuté :
EXPLAIN PLAN INTO [system.]Plan_table FOR
select * from Empl where age < 30;

La table Plan_table doit être au préalable créée avec un schéma imposé par le SGBD. Le plan
dʹexécution de la clause SQL est optimisé et rangé dans cette table où il peut être relu par un SELECT.

Pour lire le plan dʹexécution de cette clause, il suffit donc de lire le tuple correspondant stocké dans la
table Plan_table:

SELECT operation, object_name, search_columns

FROM Plan_table;

La réponse identifie les objets utilisés et le genre dʹaccès effectué par le système.
Schéma de la table Plan_table pour le système Oracle
Le schéma de la table Plan_table est créé au préalable par le script Oracle UTLXPLAN.SQL. Lʹexécution
de ce script permet la cération de la table SYSTEM.Plan_table dont la structure, i.e. son schéma,
comprend obligatoirement les attributs ci-dessous :

Attribut Sémantique
© A. Gamache 26
Chapitre 11 Optimisation des requêtes SQL

Statement_id varchar2(30) identifiant de la clause SQL

TIMESTAMP date estampille de lʹexécution du EXPLAIN
REMARKS varchar2(80) commentaire
OPERATION varchar2(30) nom de lʹopérateur exécuté
OPTIONS varchar2(30) options utilisées par lʹopérateur
OBJECT_NODE varchar2(128) nom du lien BD
OBJEC_OWNER varchar2(30) propriétaire de la clause
OBJECT_NAME varchar2(30) nom de lʹobjet
OBJECT_INSTANCE numeric no de lʹétape de lʹobjet
OBJECT_TYPE varchar2(30)
OPTIMIZER varchar2(255)

SEARCH_COLUMNS numeric non utilisé

ID numeric no de lʹétape du plan
PARENT_ID numeric no de lʹétape
POSITION numeric
OTHER long info additionnelle
Figure 11.15
Modification des paramètres de la session courante
Pour modifier le but il suffira dʹutiliser la commande ALTER SESSION :

ALTER SESSION SET OPTIMIZER_GOAL = ALL_ROWS;

ou encore insérer un hint (directive à lʹoptimiseur) dans la requête par lʹentremise de la chaîne /*+ hint
*/.
Exemple :
SELECT /*+ ALL_ROWS */ nom
FROM Ouvrier;
Ou encore :
SELECT /*+ FIRST_ROWS */ nom
FROM Ouvrier;

Le calcul dʹune requête est accéléré par lʹintervention de lʹoptimiseur qui agit au niveau syntaxique et
au niveau des coûts dʹexécution. Cette optimisation est généralement réalisée automatiquement, bien
que lʹutilisateur puisse fournir des directives (hints) à lʹoptimiseur pour diriger son action, soit en le
forçant à utiliser un index, soit en bloquant son utilisation. De plus, lʹutilisateur peut forcer
lʹoptimiseur à agir seulement au niveau syntaxique, et vice versa, seulement au niveau des coûts.
Au delà de ces actions, lʹutilisateur peut aussi agir en optimisant la formulation de sa requête et de ce
fait, en assistant lʹoptimiseur dans la recherche du meilleur plan dʹexécution.
Mise au point des requêtes SQL

© A. Gamache 27
Chapitre 11 Optimisation des requêtes SQL

L’utilisateur peut aussi lors de l’écriture d’une requête peut aider l’optimiseur en évitant ou en
privilégiant certaines structures de clauses. En effet, certaines écritures d’une clause bloque ou pas
lʹusage de certaines ressources comme par exemple les index. Lʹutilisateur doit penser à la mise au
point de sa requête lorsque les statistiques affichent un nombre dʹaccès disque fort important ou que le
plan dʹexécution lʹinforme quʹun index existant nʹest point utilisé. Cependant, il ne sʹagit pas dʹune
étape dans le processus dʹoptimisation, mais davantage le développement de meilleures façons de
formuler des requêtes SQL dictées par l’expérience du DBA.
Les exemples examinés par la suite sont formulés avec les relations de la BD :
Ouvrier (nas*, nom, salaire, spec, noUs)
Usine (noUs*, site, prod, nasChef)
Contrat(noCont*, fin, cout, noUs

Les index suivants sont définis:

• index regroupant (cluster index) sur les clés primaires : nas, noUs, noCont;
• index non regroupant sur les attributs suivants : nom, salaire et spec de Ouvrier;
• index non regroupant sur lʹattribut site de Usine;

Validation de lʹusage des index

Plusieurs optimiseurs de requêtes nʹutiliseront pas un index sur un attribut lorsque celui-ci est dans
une expression arithmétique. Lʹaffichage du plan dʹexécution par la commande EXPLAIN PLAN est
mis à profit pour vérifier quels sont les index utilisés dans le calcul dʹune requête.

SELECT nas nom

FROM Ouvrier
WHERE salaire/12 > 2800.00;
Cependant la requête légèrement remaniée comme ci-dessous tirera profit de lʹexistence de lʹindex sur
salaire.
SELECT nas nom
FROM Ouvrier
WHERE salaire > 2800.00 * 12;

De même lorsquʹun attribut est traité par une fonction de chaîne.

SELECT nas nom
FROM Ouvrier
WHERE Subtr(nom, 1,1) = 'D';
Cette requête ne peut pas cependant être modifiée afin de forcer lʹusage de lʹindex sur le nom. Elle
sera donc calculée par un balayage séquentiel de la table Ouvrier.
Une comparaison avec une constante dʹun autre type ou dont la précision est différente. Supposons
que lʹattribut salaire ait le type number (5,2), i.e. le type réel. Lʹindex sur salaire est construit avec le
type réel pour les entrées. Une recherche avec le salaire comparé avec un entier risque au mieux dʹêtre
calculée sans recours à lʹindex.
© A. Gamache 28
Chapitre 11 Optimisation des requêtes SQL

SELECT nas nom

FROM Ouvrier
WHERE salaire = 23000; -- type réel pour salaire
-- comparé avec un entier
Toutefois, une légère modification de la requête peut permettre lʹexploitation de lʹindex sur salaire.
SELECT nas nom
FROM Ouvrier
WHERE salaire > 22999.99 and salaire < 23000.00;

Finalement, toute comparaison avec l’indicateur NULL supprime généralement lʹusage de lʹindex
puisque cette valeur nʹest pas indexée.
SELECT nas nom
FROM Ouvrier
WHERE salaire is NULL;

Élimination du DISTINCT dans une requête

En effet, une requête avec SELECT DISTINCT induit un tri des tuples pour supprimer les doublons.
Lorsquʹil nʹest pas nécessaire de lʹutiliser, il faut le supprimer de la requête. Cette modification ne
pourrait pas être faite par lʹoptimiseur, sauf dans le cas où il sʹagirait de trier sur une clé de relation.
SELECT DISTINCT nas
FROM Ouvrier
WHERE spec = 'soudeur';

Cette requête peut engendrer inutilement un tri puisque le nas est une clé de Ouvrier. Elle devrait être
modifiée ainsi :
SELECT nas
FROM Ouvrier
WHERE spec = 'soudeur';

Si lʹintention de lʹusager était dʹavoir une réponse triée, il suffit alors dʹajouter le ORDER BY nas. Plus
généralement, sʹil y a une clé parmi les attributs affichés, le DISTINCT nʹest pas nécessaire.
Vérification du traitement dʹune jointure formulée avec une sous-requête
Quelques systèmes ne peuvent pas déceler une jointure dans la requête imbriquée suivante :
SELECT nas
FROM Ouvrier O
WHERE O.noUs IN (SELECT noUs
FROM Usine U);

Si le plan dʹexécution fournit par le SGBD ne traite pas cette requête en utilisant lʹindex sur noUs, mais
effectue le calcul de la sous-requête en premier, suivie par le test dʹinclusion de noUs, il faudra
transformer la requête en une jointure explicite :
SELECT nas
© A. Gamache 29
Chapitre 11 Optimisation des requêtes SQL

FROM Ouvrier O, Usine U

WHERE O.noUs = U.noUs;
Cette requête affichera le nas de lʹouvrier qui travaille dans une usine. Si un ouvrier travaille dans
plusieurs usines, le nas sera affiché autant de fois. La requête suivante permet dʹafficher seulement les
nas, nom et spec des ouvriers qui sont aussi chef dʹusine à lʹendroit de leur travail.
SELECT nas, nom, spec
FROM Ouvrier
WHERE nas IN (SELECT nasChef FROM Usine);
La requête est transformée en jointure pour un calcul plus rapide :
SELECT nas, nom, spec
FROM Ouvrier O, Usine U
WHERE O.noUs = U.noUs and nas = nasChef;
Cas spécial
Une requête plus complexe pourrait être plus performante avec lʹusage dʹune table temporaire. Par
exemple, pour trouver les ouvriers les moins payés par département, la requête SQL corrélée suivante
peut être formulée :
SELECT nas
FROM Ouvrier O
WHERE salaire = (SELECT Min(salaire) FROM Ouvrier O1
WHERE O.spec = O1.spec);

Avec une telle requête, lʹusage dʹune table temporaire (Tempo) simplifie la formulation de la jointure.
SELECT min(salaire) as petitSal, spec INTO Tempo
FROM Ouvrier
GROUP BY spec;
SELECT nas
FROM Ouvrier O, Tempo T
WHERE O.spec = T.spec and O.salaire = T.petitSal;

Utilisation de la table temporaire

Certains systèmes, notamment les implémentations complètes de SQL-92 permettront de formuler
une requête en plusieurs étapes et cela, sans faire appel à une vue relationnelle. Pour ce faire, il y aura
création dʹune table temporaire dont le schéma est stocké dans le dictionnaire du SGBD.
Ainsi pour trouver les ouvriers dont le salaire est égal à un salaire payé à un soudeur, on pourra
exécuter la requête suivante :
SELECT salaire into Tempo --déjà créée
FROM Ouvrier
WHERE spec = 'soudeur';

SELECT nas, nom

FROM Ouvrier
WHERE salaire = (SELECT salaire FROM Tempo);
© A. Gamache 30
Chapitre 11 Optimisation des requêtes SQL

Les requêtes peuvent être réécrites et fusionnées pour éviter de faire appel à une table temporaire :
SELECT nas, nom
FROM Ouvrier
WHERE salaire = (SELECT salaire FROM Ouvrier);

Factorisation des tris

Une suite de requêtes similaires nécessitant un tri par le ORDER BY peut être calculée plus
rapidement si les tris sont réduits, lorsque cela est possible, à un seul. Par exemple, sʹil faut trouver,
en ordre croissant, les attributs nas et nom des ouvriers dont le salaire est compris dans une plage de
valeurs. Cette requête sera formulée autant de fois quʹil y aura de plages de valeurs.
SELECT nas, nom
FROM Ouvrier
WHERE salaire >20000.00 and salaire < 45000.00
ORDER BY nas;

Pour calculer cette requête, lʹindex sur le salaire pourrait ne pas être utilisé en raison de la plage de
valeurs pour lʹattribut salaire dont la sélectivité est faible. Lʹextension de Ouvrier sera de préférence
balayée entièrement et un tri sera fait sur les tuples sélectionnés. Un tel tri coûteux pourrait être
effectué pour chaque question similaire. Pour éviter ce tri coûteux, il suffira de créer une table
temporaire ou encore mieux une vue matérialisée :
SELECT nas, nom INTO Tempo FROM Ouvrier
WHERE salaire >10000.oo and salaire < 99999.00
ORDER BY nas;
La table Tempo est construite avec tous les tuples ordonnés sur le nas des ouvriers compris entre les
deux bornes de salaire qui ont été choisies à dessein pour inclure tous les ouvriers. Les requêtes
subséquentes pour afficher, en ordre, les ouvriers dont le salaire est compris dans une plage de
valeurs seront maintenant formulées sans tri sur la table Tempo.
SELECT nas, nom
FROM Tempo
WHERE salaire >20000.00 And salaire < 45000.00;

Avec une telle approche, un seul tri est exécuté sur les tuples stockés en ordre dans la table Tempo.
Toutefois, comme il sʹagit ici dʹune table temporaire, son extension nʹest pas automatiquement mise à
jour pour refléter les transactions en cours sur la BD. Les requêtes ci-dessus devront être exécutées sur
une période relativement courte pour avoir des réponses presque consistantes. Une autre façon pour
éviter ce problème est dʹutiliser de préférence un snapshot qui peut être mis à jour automatiquement et
donc, être en phase par rapport à lʹétat des tables de base.

Simplification des clauses SQL incluant un HAVING

© A. Gamache 31
Chapitre 11 Optimisation des requêtes SQL

Les requêtes sont parfois formulées pour obtenir une réponse correcte, sans le souci dʹobtenir la
clause la plus simple. Par exemple, la clause suivante donne le plus petit salaire payé pour la spécialité
ʹsoudeurʹ.
SELECT Min(salaire) as min_sal, spec
FROM Ouvrier
GROUP BY spec
HAVING spec = 'soudeur';

Cette requête ainsi formulée peut induire un tri qui nʹest pas esentiel pour le calcul de réponse.
Par contre, en modifiant la requête pour avoir la forme suivante :

SELECT min(salaire) as min_sal, spec

FROM Ouvrier
WHERE spec = 'soudeur';
La réponse est identique, sans avoir recours à un tri.

Traitement du connecteur logique OU

Avec une requête utilisant un prédicat disjonctif, il faut vérifier si le SGBD utilisé exploite bien les
index présents. Pour cela, il faut afficher le plan dʹexécution de la requête.

SELECT nas
FROM Ouvrier
WHERE nom = 'Langlois' or spec = 'soudeur';
Si le plan dʹexécution exploite les index existants sur le nom et la spécialité, cette requête sera
performante. Au contraire, si les index ne sont pas utilisés, il faut alors supprimer le connecteur
logique OU et reformuler la requête avec lʹopérateur UNION. La nouvelle requête deviendra :
SELECT nas
FROM Ouvrier
WHERE nom = 'Langlois'
UNION
SELECT nas
FROM Ouvrier
WHERE spec = 'soudeur';

Cette réécriture peut être avantageuse lorsquʹil y a un index sur les deux attributs du prédicat
disjonctif.
Ordre des tables dans la clause FROM
Dans certains SGBD lʹordre des tables dans la clause FROM est significatif. Par exemple, un SGBD
pourra utiliser un index avec la première table du FROM et balayer la seconde. Si ceci est confirmé par
le plan dʹexécution, il est plus performant alors de balayer la plus petite extension, donc de la placer
obligatoirement en deuxième place dans le FROM.
© A. Gamache 32
Chapitre 11 Optimisation des requêtes SQL

Vue relationnelle comme source de ralentissement

Une vue est une clause SQL placée dans le dictionnaire et qui est soit matérialisée ou fusionnée dans
une requête. La première approche est exceptionnelle puisque quʹelle est plus lourde à implémenter
en terme de calcul. La deuxième est celle généralement utilisée par plusieurs logiciels SGBD.
Par exemple, soit la vue suivante :
CREATE VIEW OuvrierQc AS
SELECT nas, nom, prod
FROM Ouvier O, Usine U
WHERE O.noUs = U.noUs and site = 'Québec';

Cette vue fournit les nas, nom et production des usines où travaille chaque ouvrier. Accessible aux
utilisateurs, elle peut engendrer inutilement des requêtes complexes.
SELECT spec
FROM OuvrierQc
WHERE nas = '3456';

Avec sa fusion avec la vue relationnelle, cette requête devient la jointure suivante :
SELECT spec
FROM Ouvrier O, Usine U
WHERE O.noUs = U.noUs and
site = 'Québec' and nas = '3456';
Cette jointure fournit la réponse attendue. Elle peut être aussi obtenue par une formulation plus
simple en exploitant le fait que lʹattribut specialité est inclus dans le schéma de la relation Ouvrier.
SELECT spec
FROM Ouvrier
WHERE nas = '3456' and noUs = 'Québec';

Mode d’optimisation de Oracle et syntaxe des clauses SQL

L’optimiseur du SGBD Oracle recourt à des algorithmes d’optimisation dont le comportement externe
est généralement prévisible à partir de la syntaxe de la clause SQL (rule-based), sauf pour
l’optimisation basée sur le coût (cost-based) qui sʹappuie sur des données internes comme la taille des
tuples, le nombre de tuples, la sélectivité des attributs et lʹéparpillement des clés pour établir un plan
dʹexécution optimisé. Lʹapproche par les règles établit un plan dʹexécution sur la base de la clause
SQL, et le plan est formulé en tenant compte de certaines règles dʹordonnement présentées dans les
pages suivantes. Cependant, il est possible dʹinfluencer le comportement de lʹoptimiseur syntaxique
par la formulation de la clause SQL.

Exemples : les index sur le noEmpl et celui sur le tauxH ne seront pas exploités.
SELECT *
FROM Empl

© A. Gamache 33
Chapitre 11 Optimisation des requêtes SQL

WHERE noEmpl like ‘%345Y’;

SELECT *
FROM Empl
WHERE tauxH * .33 > 24.25 ;

À noter que dans la requête qui précède, un index sur l’attribut tauxH ne serait pas très utile, car
toutes les valeurs de tauxH doivent être lues et transformées afin dʹeffectuer la comparaison du
prédicat.

De même, il est aussi difficile de tirer profit de lʹindex sur le nom dans la clause ci-dessous, lorsque ce
dernier est inclus dans une expression de chaîne :
SELECT *
FROM Empl
WHERE Substr(Empl.nom,5,1) = 'S';

Dans certains exemples ci-dessus, il est possible de transformer la requête en une autre équivalente
qui ne bloquerait pas lʹusage de l’index.
Mise à jour des index
Malgré leur intérêt pour la recherche, la multiplicité des index présentent quelques inconvénients
pour les opérations de mise à jour et de suppression. Cela peut donner lieu à divers phénomènes de
ralentissement :
- un ralentissement suite à la mise à jour des entrées de tous les index qui font référence à lʹattribut de
la table modifiée. Il y aura éventuellement, un rééquilibrage du B-arbre;

- une occupation trop importante par les index, de lʹespace sur disque et dans les pages de la ZMP;

- une augmentation du taux de remplacement des pages (page swapping) en raison de la présence des
index, ce qui peut ralentir la recherche.

Par ailleurs, l’opération de suppression (DELETE) des tuples se prolonge par une suppression de
l’entrée correspondante dans lʹindex, ce qui ralentit celle qui concerne les tuples. L’opération
d’insertion est aussi pénalisée par la mise à jour de l’index, même si l’insertion ne sous-tend pas de
recherche dans une table. Mais, tout ajout dans une table indexée entraîne la mise à jour de l’index.

Autre éléments de la clause SQL qui influencent le module optimiseur :

- Distinct dans le SELECT
Le traitement de la clause distinct est fait par un tri. La suppression des doublets est alors réalisée, à la
fin du calcul, lors de l’ordonnement des tuples de la réponse. Avec le distinct, les index ne sont pas

© A. Gamache 34
Chapitre 11 Optimisation des requêtes SQL

utilisés même s’ils existent et le SGBD fait un balayage complet. Le tri est fourni par le SGBD et
s’effectue dans un espace temporaire défini pour le système.

- GROUP BY
Cette clause sous-tend un tri interne dont le critère de classement inclut obligatoirement tous les
attributs du SELECT, sauf ceux utilisés comme argument dans une fonction. Aucun autre attribut
n’apparaît dans le SELECT.

Par exemple, on aura :

SELECT ville, Avg(age)
FROM Empl
WHERE metier = 'electricien'
GROUP BY ville ;

- Traitement de la sous-requête ( bloc de niveau 2)

Celle-ci est généralement transformée en jointure et optimisée sous cette forme.
SELECT *
FROM Ventes
WHERE Ventes.article IN (SELECT FROM Pieces_inv
WHERE article = ʹa2ʹ or article = ʹa3ʹ;
Dans cet exemple, la requête imbriquée est transformée en jointure simple pour obtenir l’expression
suivante qui est par la suite optimisée pour tirer profit des index.
SELECT *
FROM Ventes as V, Inventaire as I
WHERE V.article = I.article and
(V.article = 'a2' or V.article= 'a3');

- Transformation du prédicat dʹinclusion en un ensemble de constantes littérales.

Le prédicat dʹinclusion est parfois transformée par l’optimiseur en une jointure. Par exemple, la
requête ci-dessous, il y aura modification du avec prédicat d’inclusion pour exécuter plutôt une
jointure naturelle :
SELECT *
FROM Empl
WHERE Empl.nom in
('Gagnon','Mathieu','Valois', 'Audy');

Après transformation, la sélection est devenue une autojointure :

SELECT *
FROM Empl X, Empl Y
WHERE X.no_empl = Y.no_empl and
(X.nom = ‘Gagnon’ or X.nom=’Mathieu’ X.nom=’Valois’
© A. Gamache 35
Chapitre 11 Optimisation des requêtes SQL

or X.nom = 'Audy');

La jointure remplace le test dʹinclusion.

- Chemin d’accès unique
S’il y a un chemin d’accès unique, c’est-à-dire qui sous-tend l’accès à un seul tuple d’une table de base,
il est pris en compte en premier lieu. Par exemple, ce sera le cas si la requête utilise explicitement ou
implicitement :
a) un index du type unique pour un attribut; le rowid est fourni par la recherche dans lʹindex;
b) une référence à une valeur unique dans un ensemble : valeur de clé;
c) une valeur particulière de ROWID dans le WHERE.

- Traitement de la négation : NOT

L’index n’est pas utilisé pour traiter le NOT et le != au regard d’une valeur simple. Par exemple, on
aura :
SELECT * FROM Ventes WHERE article != 'a5' ;

Pour traiter certains cas de négation, il est plus rapide pour l’optimiseur d’éviter le balayage
séquentiel d’une table en effectuant, lorsque c’est possible, les transformations automatiques suivantes
de l’opérateur de négation :
!> sera transformé en <= !>= sera transformé en <
!< sera transformé en >= !<= sera transformé en >
- Optimisation du connecteur logique OR
Les index ne sont utilisés que si les attributs du OR dans le WHERE sont tous indexés. Si ce n’est pas
le cas, il faut placer l’attribut le plus spécifique (sélectivité sj ) en première position de la cascade
logique.
Voici un exemple :
SELECT *
FROM Ventes
WHERE nom ='Ted'or nom ='Valérie' or article = 'a1' ;

Si le nom est indexé, mais pas l’article, alors l’index n’est pas très utile, puisque la table doit être
parcourue entièrement pour les articles.
- Clause ORDER BY
Après une sélection, les tuples sont triés par une procédure de tri incorporée au système Oracle.
L’argument du tri peut comporter plusieurs attributs et se faire en ordre descendant ou ascendant.

Traitement de la jointure par Oracle

© A. Gamache 36
Chapitre 11 Optimisation des requêtes SQL

De façon générale, le calcul d’une jointure sera accéléré si les attributs de jointure sont indexés. Il faut
faire attention, cependant aux structures syntaxiques qui annulent l’usage des index comme par
exemple un prédicat avec une fonction :

a) Jointure sans attribut indexé : si aucun attribut indexé n’est disponible faire la jointure, le calcul est
fait avec un tri dynamique lancé par l’optimiseur;

b) Jointure avec index : s’il n’y a qu’un seul index de jointure disponible, la table non indexée est celle
qui est balayée en premier et doit pour cela apparaître en première position dans la clause FROM. S’il y
a un index sur les deux attributs de jointure, le noyau détermine le chemin d’accès selon une
pondération qui s’appuie sur l’indice de sélectivité des attributs de jointure (méthode heuristique).

Il est possible de spécifier à l’optimiseur de privilégier certaines règles ou lʹapproche par le coût, et
cela, au moyen des indices (hints) inclus sous forme de commentaire après le SELECT, DELETE et
INSERT. La directive à lʹoptimiseur est incluse dans la requête :

SELECT /*+ COST */ nom, ville

FROM Empl
WHERE age > 25 and ville in ('Quebec', 'Montreal', 'Trois-Rivieres',
'Boston');

Cette clause est optimisée avec lʹapproche par coût, même si le plan possible avec lʹapproche par les
règles était plus performant.
Sachant quʹune extension sera balayée entièrement pour répondre à une question, il sera plus
performant dʹéviter lʹusage des index qui prennent de la place en mémoire et qui doivent être
parcourus. Pour cela, une information peut être transmise à lʹoptimiseur à savoir de faire un balayage
complet de la table Empl et dʹignorer tout index sur âge ou sur ville.

SELECT /*+ FULL (Empl) */ nom, ville

FROM Empl
WHERE age > 25 and ville in ('Quebec', 'Montreal', 'Trois-Rivieres',
'Boston');

Conclusion

Références chapitre 11

1SMITH J.M., CHANG P.Y., Optimizing the performance of a Relational Algebra Database Interface,
CACM v. 18, no 10, pp. 68-79, 1975

© A. Gamache 37
Chapitre 11 Optimisation des requêtes SQL

2FREYTAG J.C., A Rule-based View of Query Optimization, ACM SIGMOD International

Conference San Francisco, 1987
3 SHASHA, Denis, Database Tuning; A Principled Approach, Prentice Hall, 1992, ISBN 0-13-205246-6
4GRAEFE G., DeWITT D., The EXODUS Optimizer Generator, ACM SIGMOD International
Conference, San Francisco, 1987
5BABB E., Implementing a relational Database by means of Specialized Hardware, ACM Transaction
on Data System, v. 4, no 1, 1979.

© A. Gamache 38