Cours 9: Optimisation : Index et

plan d’exécution

CHEIKHOU THIAM
[email protected]

INDEX :
B-arbre, Bitmap
Création d’index sous
oracle

1
 Définiti
on
• Pour compléter le schéma d’une table (relation),
on peut créer des index.

• Permet une recherche rapide d’une information.

2
Exemple : Index d’un
livre

3
 Index En
action
Select * From Nom Pre Adr
Etudiant 1 Martin Léo …
Where Nom = 2 Deloin Léa …
“dupont”
3 Garcia Luis …
• Un moyen pour récupérer la ou les 4 Fadle Mac …
lignes répondant à la clause
5 Milka Domi …
nom=’dupont’ est de balayer toute
la table (le fichier). 6 dupont Marco …
• Le temps de réponse sera prohibitif 7 Zara Thé …
dès que la table dépasse quelques
centaines de lignes. …
… …
• Afin d’optimiser ce type de requête,
on pourra indexer l’attribut ”nom”.
 Index (un
T
attribut)
Adr,
Nom Pre
Nom Ptr …
1 Martin Léo …
Deloin 2
Index
2 Deloin Léa …
sur
Dupon 6
T.Nom
Index : liste t 3 Garci Luis …
des noms Fadle 4
4 Mich
triée + un Fadle …
Garci 3 e
pointeur
l
vers le Martin 1
tuple 5 Milka Domi …
Milka 5
6 Dupont Marco …
Zara 7
7 Zara Thé …
…
…
… …
On peut effectuer
une recherche
dichotomique
 Plusieurs index sur une même
table T
Nom Pre C

Index 1 Martin Léo …

Sur 2 Deloin Léa …
T.No
m
3 Garci Luis …

Index 4 Fadle
Mic
…
h
Sur el
T.Pre 5 Milka Domi …
6 Dupont
Mar
…
c
o
7 Zara Thé …
… … …
Possibilité de créer plusieurs index
sur une même table.
 Index
composé T
Nom Pre Adr

1 Martin Léo …
Index
sur 2 Deloin Léa …
T.Nom
3 Garci Luis …

oIndex 4 Fadle Michel …

Inde
x n 5 Milka Domi …
Sur
6 Dup
Marco …
T..Prénom on
t
(Nom,Pre) 7 Zara Thé …

…
… …

Peut concerner plusieurs attributs d’une

même table (index composé) (cas clé
primaire composé).
 Création index : syntaxe
SQL
• Création d’un index
CREATE INDEX nom_index ON
nom_table(colonne[,colonne2 …]);

• Création index unique

CREATE UNIQUE INDEX nom_index ON
nom_table(colonne[,colonne2 …]);

• Exemple
CREATE INDEX IdxNomEtud On Etudiant (Nom)
• Suppression
DROP INDEX nom_index ; 8
 Index par
défaut
• Création implicite d’index :
– chaque fois qu’une clé primaire ou
– une contrainte d’unicité sur un attribut est
définie pour une table.
• Pour vérifier l’existence d’index : consulter
les vues (ORACLE)
– USER_INDEXES,
USER_IND_COLUMNS,
ALL_INDEXES,
– ALL_IND_COLUMNS ou
DBA_INDEXES
9
 Choix des
index
• On choisira de créer un index sur :
– Les attributs utilisés comme critère de jointure,
– Les attributs servant souvent de critères de sélection,
– Sur une table de gros volume (d’autant plus
intéressant si les requêtes sélectionnent peu de
lignes).

• L’adjonction d’index accélère la recherche des lignes.

Mais impact négatif sur la mise à jour de la table.
– Impact négatif sur les commandes d’insertion et de
suppression (car mise à jour de tous les index
portant sur la table)  coût.

10
 Type
d’index
• Organisation de l’index
– Séquentiel (index dense)
– Séquentiel indexé (index creux)
– Arbres B+ (par défaut dans
ORACLE)
– Bitmap
– Hashage

11
 Type d’index: Index séquentiel
(dense)
• Toutes les clés de recherche sont
présentes dans l’index Numéro
Numér d'enregistrem
Index o de ent relati
bloc 10 Cèdre en boule 10.99 f 0
10
0 40 Epinette bleue 25.99 1
20 90 Pommier 25.99 2
0
8 60 Erable argenté 15.99 3
40 50 Chêne 22.99 4
1
50 81 Catalpa 25.99 5
4 95 Génévrier 15.99 6
60 70 Herbe à puce 10.99 7
3 1
20 Sapin 12.99 8
70
80 Poirier 26.99 9
7
80
9
81
5
90
1
 Type d’index: Index creux/épars (séquentiel
indexé)
Numéro
Numér d'enregistrem
Index o de ent relat
bloc 10 Cèdre en boule 10.99 if 0
10 0
70 1 20 Sapin 12.99 1

40 Epinette bleue 25.99 2

0
50 Chêne 22.99 3

60 Erable argenté 15.99 4

70 Herbe à puce 10.99 5

80 Poirier 26.99 6
• Non dense 81 Catalpa 25.99 7
1
(creux) 90 Pommier 25.00 8

• Index plus petit 95 Génévrier 15.99 9

• Accès séquentiel rapide (accès
un blocà puis séquentiel dans
direct
le bloc
• Primaire

1
 Type index : Index par
Arbre-B
• Rappel arbre binaire (idem à indexation
séquentielle sur des clés triées (recherche
dichotomique)
14

1 1
0 6
8 1 1 1
2 5 8
Parcours de l’arbre A: 9
7 11
13
1 2 7 9 10
8 11
14 10 16 3 8 4 12
5 15
6 7 9 11
13 18

Cet index est équivalent à une recherche dans une

table triée
1
 Type index : Index par
• Arbre-B+
Au lieu d’une clé par nœud, chaque nœud est un bloc
contenant k clés triées et k+1 fils
• Les B-arbres sont équilibrés (toutes les feuilles à la même
profondeur).
• Les feuilles contiennent les valeurs des clés et le Rowid
• Arbre B+ Les clés sont répétées au niveau des feuilles (mais
Blo
pas dans un arbre B) c7 5
0

Blo Blo
c22 4 4 c66
5 0 5 0

Blo Blo Blo Blo Blo Blo

c
10 2 c
23 3 c
41 4 4 c
48 4 c
55 5 c
64 7
0 0 5 0 0 3 4 5 8 0 3 0 0

Pointeur vers
les données
(Rowid) 1
 Type d’index : Index par
Arbre-B
• Exemple : recherche
clé 48
Commencer par la racine
48 <50, prendre pointeur
gauche
48 > 45 (dernière clé du Blo
c57
bloc), prendre pointeur
droit 0

Blo Blo
c22 4 4 c66
5 0 5 0

Blo Blo Blo Blo Blo Blo

c
10 2 c
23 3 c
41 4 4 c
48 4 c
55 5 c
64 7
0 0 5 0 0 3 4 5 8 0 3 0 0
Lire Bloc 8
Comparer séquentiellement 48 aux autres clés
du Bloc
 Type d’index: Index
bitmap
Titre Genre
1 Vertigo Suspense
2 Brazil Science-fiction
Un index bitmap considère toutes les
3 Twin Peaks Fantastique valeurs possibles pour un attribut.
4 Underground Drame Pour chaque valeur, on stocke un
5 Easy Rider Drame tableau de bits (dit bitmap) avec
6 Psychose Drame
7 Greystoke Aventures autant de bits qu'il y a de lignes dans
8 Shining Fantastique la table.
9 Annie Hall Comédie
10 Jurassic Park Science-fiction
11 Metropolis Science-fiction Très utile pour les colonnes qui ne
12 Manhattan Comédie possèdent que quelques valeurs
13 Reservoir Dogs Policier distinctes.
14 Impitoyable Western
15 Casablanca Drame
16 Smoke Comédie

Index sur 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
genre Drame 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0
Science-fiction 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0
Comédie 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1
17
 Index bitmap

Rechercher les

Science-fiction
films de type Titre Genre
“drame” 1 Vertigo Suspense

Comédie
RowId

Drame
2 Brazil Science-fiction
3 Twin Peaks Fantastique
1- Sélectionner 1 0 0 0 4 Underground Drame
dans la table les 2 0 1 0 5 Easy Rider Drame
numéros de ligne 3 0 0 0 6 Psychose Drame
(RowId) ayant 4 1 0 0 7 Greystoke Aventures
5 1 0 0
Drame=“1” 8 Shining Fantastique
6 1 0 0
9 Annie Hall Comédie
7 0 0 0
10 Jurassic Park Science-fiction
8 0 0 0
11 Metropolis Science-fiction
9 0 0 1
10 0 1 0
12 Manhattan Comédie
11 0 1 0
13 Reservoir Dogs Policier
12 0 0 1 14 Impitoyable Western
13 0 0 0 15 Casablanca Drame
14 0 0 0 16 Smoke Comédie
15 1 0 0
16 0 0 1

18
 Type d’index:
Hashage
Hashage : utilise une fonction(h) qui appliquée à la
clé h(clé) donne l’adresse ou se trouve le tuples
(l’enregistrement)

Problème avec le hashage  conflits entre clés

 deux attributs qui ont la même valeur de
hashage
 prévoir des algos pour résoude les conflits 19
 Index dans
Oracle
• Plusieurs types d’index dans
Oracle :
– Arbres équilibrés (arbre B+)(par
défaut)
– Bitmap
– Hasahage
CREATE [UNIQUE | BITMAP] INDEX
[<schema>.]<nom
index> ON <nom
de table>
(<nom de colonne> [ASC|DESC]
[,<nom de colonne> [ASC|
DESC]]
20
 Table organisée en
index
• Table organisée en index
– Fusion entre la table (son contenu) et son index
– Toutes les valeurs de la table sont au sein d’un
index B- arbre
– Utile uniquement si la clé primaire constitue
l’essentiel des attributs (manipulés)

21
 Ordre
Oracle

CREATE TABLE (
id NUMBER NOT NULL PRIMARY
KEY, [...]
) ORGANIZATION INDEX;

22
 Conclusi
on
• Indexation processus important pour
l’accès rapide aux données

23
 Optimisation des
Requêtes Plan
d’exécution
EXPLAIN PLAN

24
 Outils d’optimisation
d’oracle
• Outils
– EXPLAIN: visualisation des plans
d'exécution
– ANALYSE: production de statistiques
– TKPROF: mesure du temps
d'exécution

25
 Plan
d’exécution
• Oracle conserve la trace du chemin d’accès d’une
requête dans une table appelée « plan_table »
• Tous les graphes des requêtes du LID et LMD (SELECT,
UPDATE , INSERT et DELETE) sont conservées

• Exemple

26
 Plan
d’exécution
• Id : Identifiant de l’opérateur ;
• Operation : type d’opération utilisée
• Name : Nom de la relation utilisée ;
• Cost: coût estimé par oracle;
• Rows : Le nombre de lignes qu’Oracle pense
transférer. ,
• Bytes : Nombre d’octets qu’oracle pense
transférer.

27
 Type
d’opération
• Chaque opération sur un objet est notée
avec :
– L’ordre d’exécution (ordre des opérateurs)
– Le chemin d’accès aux objets consultés
(table, index, cluster, view, …)
– Le type d’opération (opérateurs physiques)

28
 Type d’opération : chemin
d’accès
• Parcours séquentiel (balayage complet)
– TABLE ACCESS FULL
• Accès direct par adresse
– TABLE ACCESS BY (INDEX|USER|...)
ROWID
• Accès par index
– INDEX (UNIQUE|RANGE|...) SCAN
• Accès par hachage
– TABLE ACCESS HASH
• Accès par cluster
– TABLE ACCESS CLUSTER

29
 Type d’opération : Opérateurs
physiques
• Pour la jointure
– Boucles imbriquées: NESTED LOOPS
– Tri-fusion: SORT JOIN, MERGE JOIN
– Hachage: HASH JOIN
• Autres opérations
– Union d'ensembles d'articles: CONCATENATION, UNION
– Intersection d'ensembles d'articles: INTERSECTION
– Différence d'ensembles d'articles: MINUS
– Filtrage d'articles d'une table basé sur une autre table:
FILTER
– Intersection d'ensembles de ROWID: AND-EQUAL
– …

• Tous les données d’explain Plan sont stockées dans la table

PLAN_TABLE
30
31
 Structure de
PLAN_TABLE
STATEMENT_ID VARCHAR2(30) id choisi
TIMESTAMP DATE date d’exécution
REMARKS VARCHAR2(80
OPERATION ) opération (plus loin)
VARCHAR2(30
)
OPTIONS VARCHAR2(30) option de l’opération
OBJECT_NODE VARCHAR2(128) pour le réparti
OBJECT_OWNER VARCHAR2(30) propriétaire
OBJECT_NAME VARCHAR2(30) nom objet (table, index,
OBJECT_INSTANCE NUMBER(38) ….
OBJECT_TYPE VARCHAR2(30)
OPTIMIZER VARCHAR2(25 (unique, …)
5)
SEARCH_COLUMNS NUMBER
ID NUMBER(38) n° noeud courant
PARENT_ID NUMBER(38) n° noeud parent
POSITION NUMBER(38) 1 ou 2 (gauche ou
droite)
COST NUMBER(38)
CARDINALITY NUMBER(38)
BYTES NUMBER(38)
OTHER_TAG VARCHAR2(25 3
 Mise en
oeuvre
• Calcul du plan d’exécution remplissage dans
PLAN_TABLE
EXPLAIN PLAN
SET statement_id = 'p1' FOR
select noemp, nomemp
from EMPLOYE
where noemp > 3;

Visualisation EXPLAIN
PLAN command &
dbms_xplan.display
function
Plan hash value:
1519211061
SELECT plan_table_output| Name | FROM
| Id | Operation
table(dbms_xplan.display('plan_table',null,'basic'));
| 0 | SELECT STATEMENT | |
| 1 | TABLE ACCESS FULL | EMPLOYE |

8 rows
selected

33
 Mise en
oeuvre
• Calcul du plan d’exécution remplissage dans
PLAN_TABLE

EXPLAIN PLAN
SET statement_id = 'p1' FOR
select noemp, nomemp
from EMPLOYE
where noemp > 3;

column operation format a18

column options format a15
column object_name format a13
column id format 99
column parent_id format 99
column position format 99
select operation,options,object_name,id,parent_id,position
from plan_table
where statement_id='p1'

34
 Mise en
œuvre
EXPLAIN PLAN
SET statement_id = 'p1' FOR
select nomemp,nomdept, salaire
from employe, departement
where employe.nodept =
departement.nodept
and salaire >5000

OPERATION OPTIONS OBJECT_NAME ID PARENT_ID POSITION

-
SELECT STATEMENT 0 6
MERGE JOIN 1 0 1
TABLE ACCESS BY INDEX ROWID DEPARTEMENT 2 1 1
INDEX FULL SCAN PK_DEPARTEMENT 3 2 1
SORT JOIN 4 1 2
TABLE ACCESS FULL EMPLOYE 5 4 1

6 lignes
sélectionnées

35
 Mise en
œuvre
Vous pourrez aussi exécuter
exécuter « set
autotrace on »

set autotrace on
select noemp, nomempfrom
EMPLOYE where noemp >
3;
Plan hash value:
1519211061
| Rows | Bytes | Cost (%CPU)|
| Id | Operation | Name Time
| 0 | SELECT STATEMENT | | 11 | 275 | 3 (0)|
|* 1 | TABLE
00:00:01 | ACCESS FULL| EMPLOYE | 11 | 275 | 3 (0)|
| 00:00:01

Predicate Information (identified by operation

id):

1 - filter("NOEMP">3)

36
 Mise en
œuvre
SQL Developer permet d’obtenir un plan
d’exécution pour une requête grâce à l’icône .

select noemp,
departement.nomdeptfrom EMPLOYE,
Departementwhere
Employe.NoDept=Departement.NoDept
and salaire >2000;

37
Fi
n

38