Université des sciences et de la Technologie

Houari Boumediene
USTHB – Alger

Département d’Informatique

ADMINISTRATION ET TUNING DE BASES DE DONNÉES

OPTIMISATION DES REQUÊTES

Responsable
Dr K. Boukhalfa
INTRODUCTION
 Ce que veut dire optimisation?
 Qu’est-ce qu’on optimise?
 Pourquoi il y a un espoir d’optimisation des requêtes?
 Quelles sont les sources du temps supplémentaire?
 Et si les Tables sont volumineuses?
 Et si les résultats intermédiaires sont volumineux?
SWAP

Select * From Clients

Where Ville = ‘Alger’
RAM BD
Chargement
E/S
Stockage
Charger tous les clients en RAM
Traitement
Si Client où ville =Alger représentent 10 %
Conséquences?
ÉVALUATION DES REQUÊTES: SURVOL

Évaluation d’une requête SQL:

 Analysée syntaxiquement, ensuite transformée en plan d’évaluation.
 Plan d’évaluation: Arbre d’opérations de l’algèbre relationnelle avec un choix d’algorithme pour chaque
opération.

Deux problématiques importantes dans l’optimisation:

 Énumération des plans alternatifs pour une requête
 Estimation des coûts de ces plans et choix de celui estimé être le moins cher

 On doit se montrer pragmatique:

 Idéalement: Trouver le meilleur plan.

 Pratiquement: Éviter les pires plans!

ARBRE ALGÉBRIQUE

 Algèbre relationnelle : modèle formel permettant d'exprimer et de calculer les requêtes sur les relations.

 Constituée d'un ensemble d'opérateurs algébriques : la sélection, la jointure, la projection, les opérateurs

ensemblistes.

 Le résultat de l'exécution d'un opérateur est toujours une relation, ce qui permet la composition.

 Utilisée également pour l'optimisation de requêtes.

 Une requête algébrique peut se présenter sous forme d'un arbre algébrique.

Arbre algébrique

 visualisation d'une requête sous une forme graphique d'arbre plus facile à lire qu'une forme linéaire
ARBRE ALGÉBRIQUE

Un arbre algébrique est un arbre représentant une requête

 Les nœuds feuilles sont les relations de base
 Les nœuds intermédiaires sont les opérateurs
 Le nœud racine est le résultat
 L'arc est un flux de données
STATISTIQUES ET CATALOGUES

L’évaluateur a besoin d’informations sur les relations ainsi que les indexes impliquées.
Les Catalogues contiennent:
 pour chaque relation: # tuples (NTuples) et # pages (NPages)
 pour chaque index: # valeurs de clés distinctes (NKeys) et # pages (NPages)
 pour chaque index à arbre: Hauteur de l’Index (Height), plus petites / plus grande valeurs de clé (Low/High)

Catalogues rafraîchis périodiquement.

 Automatiquement, Manuellement

D’autres types d’infos détaillées ([Link]., histogrammes des valeurs dans certains
champs) sont aussi stockées.
 Histogramme: structure donnant une approximation de la distribution des valeurs des données
CHEMINS D’ACCÈS ET CORRESPONDANCE D’INDEX

 Un chemin d’accès est une méthode pour puiser les tuples:

 Utilisation du Scannage du fichier, ou d’un index qui correspond à (‘’match‘’) une sélection (WHERE) de la requête.

 Un index à arbre correspond à une conjonction de termes qui mentionnent seulement des attributs
d’un préfixe de la clé de recherche.
 Index b-arbre sur a correspond à la sélection a=5, ou a>5
 L’index à arbre sur <a, b, c> correspond à la sélection a=5 AND b=3 et à a=5 AND b>6, mais pas à b=3.

 Un index à hachage correspond à une conjonction de termes qui a un terme de la forme attribut =
valeur pour chaque attribut de la clé de recherche de l’index.
 L’index à hachage sur <a, b, c> correspond à a=5 AND b=3 AND c=5; mais pas à b=3, ni à a=5 AND b=3, ni à a>5
AND b=3 AND c=5.

 Index Bitmap
UN ALGORITHME D’OPTIMISATION

1. Séparer chaque sélection σF1 ∧ … ∧ Fn(E) en une cascade σF1 (σF1 … (σFn(E)))

2. Descendre chaque sélection le plus bas possible dans l’arbre algébrique

3. Descendre chaque projection aussi bas possible dans l’arbre algébrique

4. Combiner des cascades de sélection et de projection dans une sélection seule, une projection
seule, ou une sélection suivie par une projection

5. Regrouper les nœuds intérieurs de l’arbre autour des opérateurs binaires (⋈, *, -, ∪). Chaque
opérateur binaire crée un groupe

6. Produire un programme comportant une étape pour chaque groupe, à évaluer dans n’importe
quel ordre mais tant qu’aucun groupe ne soit évalué avant ses groupes descendants.

17
QUELQUES PROBLÈMES

 La restructuration d’un arbre sous-entend souvent la permutation des opérateurs binaires

 Cette optimisation ignore la taille de chaque table, les facteurs de sélectivité, etc.
 Aucune estimation de résultats intermédiaires
Exemple:

(Ouvrier ⋈ Usine) ⋈ Contrat

Si cardinalité (Usine) <<<Cardinalité(Contrat) << Cardinalité(Ouvrier) alors l’expression suivante a des

chances d’être plus performante:

(Usine ⋈ Contrat) ⋈ Ouvrier

 Optimisation basée sur les modèles de coût

18
MÉTHODES D’OPTIMISATION
BASÉES SUR LES MODÈLES DE
COÛTS
«Cost-based Methods»

19
NOTIONS UTILES

 Les tables relationnelles sont stockées physiquement dans des fichiers sur disque

 Lorsqu’on veut accéder aux données, on doit transférer le contenu pertinent des fichiers dans la

mémoire

 Fichier = séquence de tuples

 Bloc (page) = unité de transfert de données entre disque et mémoire

 Facteur de blocage = nombre de tuples d’une relation qui «tiennent» dans un bloc

 Coût de lecture (ou écriture) d’une relation = nombre de blocs à lire du disque vers la mémoire

(ou à écrire de la mémoire vers le disque)

20
ESTIMATION DU COÛT DES OPÉRATIONS
PHYSIQUES

 TempsES : Temps d’accès à mémoire secondaire (MS)

 TempsUCT : Souvent négligeable

 TailleMC : espace mémoire centrale

 TailleMS : espace mémoire secondaire

21
MODÈLE DU COÛT D'UNE ENTRÉE- SORTIE EN
MÉMOIRE SECONDAIRE
Paramètre Signification
TempsESDisque(n) Temps total de transfert (lecture ou écriture) de n octets du disque
TempsTrans(n) Temps de transfert des n octets sans repositionnement
TempsPosDébut Temps de positionnement au premier octet à transférer (ex : 10 ms)
TempsRotation Délai de rotation (ex : 4 ms)
TempsDépBras Temps de déplacement du bras (ex : 6 ms)
TauxTransVrac Taux de transfert en vrac (ex : 2MB/sec)
TempsESBloc Temps de transfert d'un bloc (ex : 11 ms)
TempsTrans Temps de transfert d'un bloc sans repositionnement (ex : 1 ms)
TailleBloc Taille d'un bloc (ex : 2K octets)

22
 STATISTIQUES AU SUJET DES TABLES

Statistique Signification
||T|| Nombre de lignes de la table T

TailleLigne La taille d'une ligne de la table T

FBT Facteur de blocage moyen de T

NDIST (T,a) Nombre de valeurs distinctes de la colonne a pour la table T

MinT(colonne) Valeur minimum de la colonne de T

MaxT(colonne) Valeur maximum de la colonne de T

|T| Nombre de pages de la table T

23
COÛT D’UNE REQUÊTE OP5
⫪
 Soit R une requête composée de n opérations algébriques (Opi) OP4
⋈
 Coût (R) = ∑ Coût (OPi) OP3
 Coût (Opi) = Nombre de pages transférées de la mémoire secondaire vers la RAM ou ⋈

de la RAM vers la mémoire SWAP

OP1 OP2
 Pour calculer le Coût(Opi+1)
ville =‘Alger’ Coeif>3
 Il faut calculer le nombre de tuples du résultat intermédiaire de Opi (||Opi||)

 En utilisant le facteur de sélectivité de Opi : ||Opi||=FS*||Opi-1||

Etudiant Inscrit Module
 Le transformer en nombre de pages en utilisant les tailles du tuples (T_Tuples)

et de la page système |Opi|=T_tuples *||Opi||/PS

 Taille tuple = ∑ taille attributs du tuple  T_Tuple ((T))= T_Tuple (T)

 T_Tuple (T1 ⋈T2)=T_Tuple(T1)+T_tuple(T2)
 Une autre Formule |Opi|=||Opi||/#tuples par page
 T_Tuple (⫪A1,A2, …(T)) = ∑Taille (Ai)
 Si RAM non suffisante : Ajouter les pages transférées en mémoire SWAP
FACTEUR DE SÉLECTIVITÉ (FS)

 Désigne le pourcentage de lignes sélectionnées sur le nombre total de tuples

 Entre 0 et 1

 Opération trop sélective : SF tend vers zéro

 Opération non sélective : SF tend vers 1

 Exemple :

• Si étudiants habitant Alger représentent 20 %

• Le facteur de sélectivité du prédicat Ville=‘Alger’ est de 0,2%

• Si la table Etudiant contient 100 000 étudiants, la requête Select * from Etudiant where Ville
= Alger
• Retournera 20 000 tuples
FACTEUR DE SÉLECTIVITÉ

||(σ(R))|| = SF * ||R||

 SF (A = valeur) = 1 / NDIST(A)

 SF(A > valeur) = (max(A) - valeur) / (max(A) - min(A))

 SF(A < valeur) = (valeur - min(A)) / (max(A) - min(A))

 SF(A IN liste valeurs) = (1/NDIST(A)) * CARD(liste valeurs)

 SF(P et Q) = SF(P) * SF(Q)

 SF(P ou Q) = SF(P) + SF(Q) - SF(P) * SF(Q)

 SF(not P) = 1 - SF(P)

26
Le coût dépend de l'algorithme (index, hachage ou balayage).
FACTEUR DE SÉLECTIVITÉ

 La taille d’une jointure est estimée par la formule suivante:

 ||R1  ⋈ R2|| = Sel * ||R1|| * ||R2||

 sel: la sélectivité de la jointure

 Produit cartésien : Sel=1

 Jointure sur clé étrangère sur R1 : ||R1  R2|| =||R1||

 Une estimation de Sel si jointure quelconque

 SF (R1 a⋈b R2)=1/Max(NDIST(a), NDIST(b))

27
EXEMPLES

SELECT *
FROM R1, R2 ·

SF =1

SELECT *
FROM R1
WHERE A = valeur
· SF = 1/NDIST(A) avec un modèle uniforme

28
ALGORITHMES GÉNÉRAUX
POUR LES OPÉRATEURS
RELATIONNELS

29
LA SÉLECTION

Sélection sans index

SELECT NSS, Nom FROM Ouvrier WHERE Salaire > 15000

Plan d’exécution

• Pour chaque tuple t de ouvrier faire -- accès séquentiel En cas d’absence de statistiques, les

• si [Link] > 15000 alors réponse = réponse  πNSS, Nom (Ouvrier)

estimateurs considèrent une
distribution uniforme
 Coût = |T|=|Ouvrier|

 Sélection avec Index

 Charger l’index : Coût =|Index|

 Parcourir l’index en RAM , chercher les tuples à sélectionner: Coût = 0

 Charger les tuples sélectionnés : Coût=FS*|T|=FS(Salaire>15000)*|Ouvrier|

30
 Total = |Index|+FS*|T|
ALGORITHMES DE JOINTURE

T1 T2 T1⋈ T2
 Jointure sans index C DE F A B C C DE F
A B C

 Jointure par boucles imbriquées (nested loop)

 Jointure par tri-fusion (sort-join)

=
 Jointure par hachage (hash-join)

 Jointure avec index

 Jointure avec boucles indexées

31
JOINTURE PAR BOUCLES IMBRIQUÉES (JBI)

 R ⋈F S
 Principe:

 La première table est lue séquentiellement et de préférence stockée entièrement en mémoire

 Pour chaque tuple de R, il y a une comparaison avec les tuples de S

POUR chaque ligne lR de R

POUR chaque ligne lS de S
SI  sur lR et lS est satisfait
Produire la ligne concaténée à partir de lR et lS
FINSI
FINPOUR
FINPOUR
+ Algorithme simple
Complexité: (|R| + (|R|*|S|)
Si la table extérieure tient en mémoire: une seule lecture des deux tables suffit.

32
JOINTURE PAR TRI FUSION

Plus efficace que les boucles imbriquées pour les grosses

tables
Coût =
 |T1|+|T2| si T1, T2 déjà triées
 Principe
 2*|T1|*logb |T1|+|T2|+|T1| Si |T2| triée

 Trier les deux tables sur les colonnes de jointure  2*|T2|*logb |T2|+|T2|+|T1| Si |T1| triée

 2*|T1|*logb |T1|+ 2*|T2|*logb |T2|+|T2|+|T1| si

 Effectuer la fusion
aucune table n’est triée
 b : nombre de pages du tampon en mémoire centrale
 Complexité: Le tri qui coûte cher
disponible pour le tri

Très efficace quand une des deux tables est petite (1, 2, 3

fois la taille de la mémoire)

33
 Algorithme en option dans Oracle
JOINTURE PAR TRI FUSION

Trier R et S par tri externe et réécrire dans des fichiers temporaires

Lire groupe de lignes GR(cR) de R pour la première valeur cR de clé de jointure
Lire groupe de lignes GS(cS) de S pour la première valeur cS de clé de jointure
TANT QUE il reste des lignes de R et S à traiter

SI cR = cS
Produire les lignes concaténées pour chacune des combinaisons de lignes de
GR(cR) et GS(cS);
Lire les groupes suivants GR(cR) de R et GS(cS) de S;
SINON
SI cR < cS
Lire le groupe suivant GR(cR) de R
SINON
SI cR > cS
Lire le groupe GS(cS) suivant dans S
FINSI
FINSI FINSI

34
FIN TANT QUE
PRINCIPE DE LA JOINTURE PAR HACHAGE

1. Hacher la plus petite des deux tables en n fragments

2. Hacher la seconde table, avec la même fonction, en n autres fragments

3. Réunir fragments par paire, et faire la jointure entre les fragments

B0 B’0
B1 B’1
T1 F(x) F(x) T2
B2 B’2
B2 B’2

Exemple : fonction de hachage Modulo 4

35
COÛT JOINTURE PAR HACHAGE

1. Chargement de T1 : |T1|

2. Hachage de T1, création des groupes en RAM : 0

3. Déchargement des groupes en MS : |T1|

4. Chargement de T2 : |T2|

5. Hachage de T2, création des groupes en RAM : 0

6. Déchargement des groupes en MS : |T2|

7. Chargement du Block Bi de T1 avec B’i de T2, faire la jointure entre les deux blocs : |Bi|+|B’i|

8. Au total : ∑|Bi|+|B’i|=|T1|+|T2|

Coût Total = 3(|T1|+[T2|)

BOUCLE INDEXÉE

T1 a⋈b T2

 Comme boucles imbriquées mais avec l’utilisation de l’index défini sur l’attribut b de T2

1. Charger une partie de T1 en RAM

2. Charger l’index
3. Pour chaque tuple de T1, parcourir l’index, retourner les RID des tuples de T2 à joindre
4. Charger ces tuples en RAM
5. Coller les tuples
 Coût = |Index|+|T1|+||T1||*|T2|/NDIST(T2,b)
COMMENT SE FAIT L’OPTIMISATION

 Chercher le meilleur plan d ’exécution?

 coût excessif

 Solution approchée à un coût raisonnable

 Générer les alternatives

 heuristiques

 Choisir la meilleure estimation approximative du coût

38
PLUSIEURS PLANS D’EXÉCUTION POUR UN
ARBRE ALGÉBRIQUE
 Pour chaque opération logique
 plusieurs choix d’opérations physiques

39
CHOIX DU MEILLEUR PLAN

40
DIFFÉRENTES STRATÉGIES

41
OPTIMISATION BASÉE SUR MODÈLE DE COÛT

 Soit Q une requête à optimiser

 Procédure

1. Énumérer tous les plans {P1, …, Pm} pour chaque requête (notons que chaque requête possède
un ensemble d’opérations O1, …, Ok)

2. Pour chaque plan Pj

 Pour chaque opération Oi du plan Pj, énumérer les chemins d’accès

 Sélectionner le chemin ayant le coût le moins élevé Coût(Pi) = Σ(l=1, k) min(Ol)
3. Coût (Q): Σ(h=1, m) Coût(Ph)

42
STRUCTURES
D’OPTIMISATION
TECHNIQUES UTILISÉES

 Vues matérialisées
• Une vue est une requête nommée
• Une vue matérialisée : les données résultant de sa requête sont
stockées et maintenues

 Index
• Structures permettant d'associer à une clé d’un n-uplet l'adresse
relative de cet n-uplet

 Traitement parallèle

 Groupement

 Fragmentation

44
CLASSIFICATION

TECHNIQUES D’OPTIMISATION

STRUCTURES NON REDONDANTES

STRUCTURES REDONDANTES

TRAITEMENT
FRAGMENTATION
PARALLÈLE

INDEX VUES MATÉRIALISÉES

VERTICALE HORIZONTALE

MONO-TABLE MULTI-TABLES

ARBRE B INDEX BINAIRE INDEX DE

JOINTURE

45
OPTIMISATION PAR INDEX
C’est quoi un index?
Index populaires
Index
 Index simple: sur une seule table ou une seule vue
(arbre B, index binaire, index de projection)
Une table Plusieurs Tables
Star Join Index,
 Index de jointure: sur plusieurs tables dans B-tree, Projection
Bitmap Join Index

un schéma en étoile
• index de jointure en étoile Plusieurs Plusieurs
1 Seul Attribut 1 Seul Attribut
attributs attributs
• Index de jointure binaire

46
TECHNIQUES D’INDEXATION

Index bitmap (index binaire)

 Populaire dans les produits OLAP

• Microsoft SQL server, Sysbase IQ, Oracle

• Un vecteur de bits pour chaque valeur d’attribut

 Opération bit à bit pour l’exécution de requêtes

• Comparaison
• Jointure
• Agrégation
• Plus compact que les B+ arbres (compression)

47
B-ARBRE
Profondeur

 Arbre équilibré
Racine
@enfant
 Ordre d : ⌈ d/2 ⌉<=Nb-Enfants<=d

Clé
 Page non équilibré si NB-Enfants>d ou si NB-

Enfants <⌈ d/2 ⌉

 Recherche (CléR)

 Si CléR<Cléi alors descendre

 Sinon alors avancer

 Si dernière clé, descendre

 Si feuille, chercher CléR dans page, Exemple : Rechercher 37

Feuilles (Pages de
données)
retourner vrai si trouvé, faux sinon
B-ARBRE
Profondeur

Algorithme d’ajout
Racine
@enfant
 Si recherche =vrai alors afficher « impossible, clé

existe déjà » Clé

 Sinon, insérer dans la page feuille retournée

 Si page équilibrée après ajout alors fin

 Sinon, éclater la page en deux, équilibrer entre

les deux pages

 Vérifier si le père est équilibré, faire la même

Exemple : Ajouter 15
chose jusqu’à la racine Feuilles (Pages de
données)
 B-ARBRE
Profondeur
Algorithme de suppression
Racine
@enfant
 Si recherche =faux alors afficher « impossible, un

enregistrement qui n’existe pas »

Clé
 Sinon, supprimer dans la page feuille retournée

 Si page équilibrée après suppression alors fin

 Sinon ETAPE IMPORTATION si possible

 Équilibrer avec frère gauche ensuite droit (ramener

des tuples) si c’est possible

Sinon ETAPE Exportation

 Céder les tuples de la page

Exemple : Supprimer 75
Vérifier si le père est équilibré et faire la même chose jusqu’à la
Feuilles (Pages de
données)
racine
 PRINCIPE DE L’INDEX BITMAP
CREATE BITMAP INDEX
Soit un attribut A, ayant prenant n valeurs possibles [v1, …,vn] (domaine) Fonction_ib_idx ON
[Link]

Création d’un index bitmap sur l’attribut A:

Select * From Employé
where Fonction = Select count(*) From Employé
• On crée n tableaux de bit, un pour chaque valeur v i Soudeur where Fonction IN (‘Soudeur’,
‘Tourneur’)
• Le tableau contient un bit pour chaque tuple t
Select * From Employé
• Le bit d’un tuple t est à 1 si: t.A = v i, à 0 sinon
where Fonction IN (‘Soudeur’,
Table Employé Index binaire sur l’attribut Fonction ‘Tourneur’)
ROWID(RID) Soudeur Fraiseur Sableur Tourneur Soudeur Tourneur OR
ROWID(RID) N°E Nom Fonction

00055 :000 :0023 0 1 0 0 0 0 0

00055 :000 :0023 1 Karim Fraiseur
00234 :020 :8922 1 0 0 0 1 0 1
00234 :020 :8922 2 Hichem Soudeur
OR =
19000 :328 :6200 3 Salim Tourneur 19000 :328 :6200 0 0 0 1 0 1 1

21088 :120 :1002 4 Ali Sableur 21088 :120 :1002 0 0 1 0 0 0 0

20088 :120 :1012 5 Lyes Soudeur 20088 :120 :1012 1 0 0 0 1 0 1

25087 :120 :1023 6 Rabie Tourneur 25087 :120 :1023 0 0 0 1 0 1

51
1
 INDEX BINAIRE

CREATE BITMAP INDEX members_gender_i ON

members(gender);

EXPLAIN PLAN FOR

SELECT * FROM members
WHERE gender = 'F';
INDEX DE JOINTURE
Pré-calculent une opération de jointure
Utilisés avec les tables liées avec des clés étrangères avec plusieurs tables
Maintient des relations entre une clé étrangère (table fille) avec les clés primaires (tables mères)

Index de jointure Table Client

IdLigneVente idLigneClient idLigneArticle IdLigne noClient nomVille

V1 C1 A1 C1 1 Poitiers
V2 C2 A2
V3 C3 A1 C2 2 Nantes

V4 C1 A1
C3 3 Poitiers

C4 4 Paris

Table Ventes
Table Article
IdLigne noClient noArticle DateVente Montant
IdLigne noArticle catégorie

V1 1 10 10/01/2008 100
A1 10 Beauté

V2 2 20 10/01/2008 200
A2 20 Beauté

V3 3 10 10/01/2008 500
A3 40 Beauté

V4 1 10 20/01/2008 150
A4 50 Jouet
…

53
A5 60 Jouet
 INDEX DE JOINTURE BITMAP : EXEMPLE
Client
RIDC CID Nom Ville
Ventes IJB Ville IJB Cat SELECT count(*)
6 616 Yacine Alger RID CID PID TID Montant RID A B T RID B M Jo Jr F
FROM Ventes V, Client C
V V V
A B RIDV And
5 515 Karim Blida 61 1 1 0 0 1 1 0 0 0 0 1 1 1 1
4 414 Lyes Tipaza
1
6
106 11 25
2 1 0 0 2 1 0 0 0 0 1 1 2 1
WHERE [Link] = [Link]
3
2
313
212
Karima
Katia
Tipaza
Alger
2
61
6
106 66 28 3 1 0 0 3 0 1 0 0 0 1 0 3 0 AND [Link] = ‘Alger’
4 0 1 0 4 0 1 0 0 0 0 0 4 0
1 111 Rabah Alger 61
3 104 33 50 5 0 0 1 5 1 0 0 0 0 0 1 5 0
6
6 1 0 0 6 1 0 0 0 0 1 1 6 1
51
4
5
104 11 10 7 1 0 0 7 0 0 0 0 1 1 0 7 0 CREATE BITMAP INDEX
Produit 8 1 0 0 8 0 0 0 0 1
RIDP PID Nom Catégorie
5
41
4
105 66 14
9 1 0 0 9 0 0 0 0 1
1 0 8 0
Ventes_Pictaviens_bjix ON
1 0 9 0
6 106 Sonoflore Beauté 6
21
106 55 14
10 0 0 1 10 0 0 0 1 0 0 0 10 0 Ventes([Link]) FROM Ventes,
2
5 105 Clarins Beauté
11
11
12
0
0
0
0
1
1
11
12
0
0
0
0
0
0
1
1
0
0
0 0 11 0 Client WHERE [Link] =
4 104 WebCam Multimédia 7 101 44 20 0 0 12 0
3 103 Barbie Jouet
1
13 0 1 0 13 0 0 0 1 0 0 0 13 0 [Link]
11
8 101 33 27 14 0 1 0 14 0 0 1 0 0 0 0 14 0
2 102 Manure Jardinage 1
1 101 SlimForm Fitness 15 1 0 0 15 0 0 1 0 0 1 0 15 0
21
9 101 11 100 16 1 0 0 16 1 0 0 0 0
2 1 1 16 1
10
31
3
102 11 200
17
18
1
0
0
1
0
0
17
18
0
0
1
1
0
0
0
0
0
0
1
0
0
0
17
18
0
0
Deux opérations :
Temps 11
41
4
102 11 102 19
20
1
1
0
0
0
0
19
20
0
0
1
1
0
0
0
0
0
0
1
1
0
0
19 0 1. Lire dans le bitmap la
20 0
colonne P
RID T
TID Mois Année
41 21 1 0 0 21 1 0 0 0 0
12 102 55 103 1 1 21 1
6 11 Janvier 2019 4
22 1 0 0 22 1 0 0 0 0 1 1 22 1
5
4
22
33
Février
Mars
2019
2019
13
51
5
102 66 100 23
24
1
1
0
0
0
0
23
24
1
1
0
0
0
0
0
0
0
0
1 1 23 1 2. Compter le nombre de 1.
1 1 24 1
3
2
44
55
Avril
Mai
2019
2019
14
51
5
103 55 17
25 0 0 1 25 1 0 0 0 0 0 1 25 0  Pas de lecture dans la table
21 26 0 0 1 26 1 0 0 0 0
Ventes
15 103 44 45 0 1 26 0
1 66 Juin 2019 2 27 0 0 1 27 1 0 0 0 0 0 1 27 0
11
16 105 66 44
1
21
SELECT count(*)
17
2
104 66 40

FROM Ventes V,
18 Client
51
104C,22Produit
20 P ?

54
5
WHERE [Link] =[Link]
61 AND [Link]=[Link] and [Link] = ‘Alger’ and [Link]=‘Beauté’
104 22 20
6
CARACTÉRISTIQUES DES BITMAPS

 Les opérations de comparaison, jointure et d’agrégation sont réduites à une

arithmétique sur les bits, d’où un traitement plus efficace

 La réponse à une requête multidimensionnelle va consister à faire l’intersection

des vecteurs de bits des diverses dimensions

 Réduction significative en espace et nombre d’accès en mémoire secondaire

55
EXEMPLE 1 : SANS INDEX

select count(*) from actvars a, timelevel t where

[Link]=a.time_level and t.month_level=3;

58
EXEMPLE 1 : AVEC INDEX

59
EXEMPLE 2 : SANS INDEX

SQL> select count(*) from actvars a, timelevel t, prodlevel p where

[Link]=a.time_level and p.code_level=a.product_level and
month_level=3 and p.group_level='P4FR1LHPUXJ8';

60
EXEMPLE 2 : SANS INDEX

SQL> select count(*) from actvars a, timelevel t, prodlevel p where

[Link]=a.time_level and p.code_level=a.product_level and
month_level=3 and p.group_level='P4FR1LHPUXJ8';

61
VUES MATÉRIALISÉES

 Exigence de ressources:
• Espace disque
• Coût de maintenance (rafraîchissement des données)
• Coût de calcul

·Impossibilité de matérialiser toutes les vues

Problème de Sélection des Vues (PSV):

- Sélectionner un ensemble de vues afin de maximiser ou minimiser

une fonction objectif sous une contrainte

- Fonction « objectif »:
Optimiser le coût d’exécution des requêtes ou Optimiser le coût de
maintenance

62
EXEMPLE

CREATE MATERIALIZED VIEW VUE1

ENABLE QUERY REWRITE
AS
SELECT *
FROM Vente, Client, Article
WHERE [Link] = [Link] AND
[Link] = [Link]
AND [Link] = ‘Alger’

63
64
65
VUES MATÉRIALISÉES CANDIDATES
R5
R1 R6
R2
 Construire l’arbre algébrique de chaque requête
R4

 Construire l’arbre Algébrique Global (union des AA)

R3

 Toute opération intermédiaire est une VM candidate

 Les vues utilisées par plusieurs requêtes sont les plus

intéressantes

 Trouver l’ensemble des VM qui réduisent le coût d’exécution des

requêtes

 dépassant pas un espace de stockage alloué

 Dépassant pas un temps de mise à jour

 Problème NP-Complet

66
MAINTENANCE DES VUES MATÉRIALISÉES

 Vues matérialisées sont calculées à partir des sources

(tables)

 Mise à jour des sources implique la mise à jour des vues

 Deux méthodes de maintenance

 Statique
 Incrémentale

67
 RÉÉCRITURE DES REQUÊTES

 Processus de réécriture
 Après le processus de sélection des vues, toutes les requêtes définies sur la BD doivent
être réécrites en fonction des vues

 Sélectionner la meilleure réécriture pour une requête est une tâche difficile.

 Processus supporté dans la plupart des SGBD multidimensionnels (Oracle)

68
Fragmentation de Données

(Partitionnement)

69
LA FRAGMENTATION DE DONNÉES
Définition

 Décomposer les objets de la BD (relation, index, vues) en un ensemble de

morceaux appelés Partitions.

Fragmentation horizontale

 La table est fragmentée par rapport à ses instances en un ensemble de lignes.

Fragmentation verticale

 La table est fragmentée selon ses attributs en un ensemble de colonnes.

Fragmentation mixte

 La table est fragmentée horizontalement et verticalement.

70
TYPES DE FRAGMENTATION
Fragmentation horizontale
• Décomposer les objets en un ensemble de lignes (instances)

A1 A2 A3 A4 A5
Attributs
I2
A1 A2 A3 A4 A5
I4

I1 I8

I2
A1 A2 A3 A4 A5
I3
I1
I4
Instances

I5
I5
I6
I6

I7 A1 A2 A3 A4 A5

I8
I3
I9 I9

I10
A1 A2 A3 A4 A5

I7

I10

71
TYPES DE FRAGMENTATION
Fragmentation verticale
 Décomposer les objets en un ensemble de colonnes (attributs).
A1 A2 A3 A4 A5

I1

I2

I3

I4

I5

I6

I7

I8

I9

I10

A1 A4

I1 A1 A2 A1 A3 A5

I2 I1 I1

I3 I2 I2

I4 I3 I3

I5 I4 I4

I6 I5
I5
I7 I6
I6
I8 I7
I7
I9 I8
I8
I10 I9
I9
I10
I10

72
TYPES DE FRAGMENTATION
Fragmentation mixte
 Horizontale suivie d’une verticale.
A1 A2 A3 A4 A5
A1 A2 A3 A4 A5

I1 I1

I5
I2
I6

I3 A1 A2 A3 A4 A5

I4 I2

I4

I5 I8

I6 A1 A2 A3 A4 A5

I7 I3

I9

I8
A1 A2 A3 A4 A5
I9
I7

I10
I10

A1 A4 A1 A2 A1 A3 A5

I1 I1 I1

I5 I5 I5

I6 I6 I6

A1 A4 A1 A2 A1 A3 A5

I2 I2
I2
I4 I4
I4
I8
I8
I8

A1 A2
A1 A4
A1 A3 A5
I3
I3
I3
I9
I9
I9

A1 A2
A1 A4
I7 A1 A3 A5
I7
I10 I7
I10
I10

73
TYPES DE FRAGMENTATION
A1 A2 A3 A4 A5

I1

I2
Fragmentation mixte
 Verticale suivie d’une horizontale
I3

I4

I5

I6  Horizontale suivie d’un verticale

I7

I8

I9

I10

A1 A4 A1 A2 A1 A3 A5

I2 I2 I2

I4 I4 I4
A1 A4 A1 A2 A1 A3 A5
I8 I8 I8
I1 I1 I1

I2 I2 I2
A1 A4 A1 A2 A1 A3 A5
I3 I3 I3
I3 I3 I3

I4 I4 I4 I9 I9 I9

I5 I5 I5
A1 A4 A1 A2 A1 A3 A5

I6 I6 I6 I7 I7 I7

I10 I10 I10

I7 I7 I7

I8 I8 I8 A1 A4 A1 A2 A1 A3 A5

I1 I1 I1
I9 I9 I9
I5 I5 I5
I10 I10 I10
I6 I6 I6

74
FRAGMENTATION HORIZONTALE PRIMAIRE ET DÉRIVÉE (I)

Fragmentation horizontale primaire (FHP)

 Fragmenter une table en utilisant les prédicats de sélection définis sur cette table
Prédicat : Attribut  Valeur,  {=,<, , >, ,} et valeur Domaine(Attribut).
Client
Client1 1
 Exemple: Client (Client_id, Nom, Ville) Client
Client
- Client1 :  Ville=‘ Alger’(Client) Algérois
Algérois
- Client2 :  Ville=‘Béchar’(Client) Client
Client2 2
Impact de la FHP sur les requêtes Béchariens
Béchariens

 Optimisation des sélections

Client
Client1 1
Select
SelectNom,
Nom,Age
Age Client
Client Select
SelectNom,
Nom,Age
Age
From Algérois
FromClient
Client Algérois
From
Client FromClient2
Client2
Where
WhereVille=Béchar
Ville=Béchar Client2 2
Béchariens
Béchariens

75
FRAGMENTATION HORIZONTALE PRIMAIRE ET DÉRIVÉE (II)

Fragmentation horizontale dérivée (FHD)

 Fragmenter une table (S) selon des attributs d’une autre table (T) : (existence de lien entre S et T)
- Ventes(Client_id, Produit_id, Date, Montant)
- Ventes1=Ventes ⋉ Client1 Client Ventes
Ventes1 1
Client1 1
- Ventes2=Ventes ⋉ Client2
Algérois
Algérois
Impact de la FHD sur les requêtes Client
Client2 2 Ventes
Ventes2 2
Béchariens
Béchariens
 Optimisation de la jointure entre S et T

Ventes
Ventes1 1 Ventes
Ventes2 2
Ventes
Select
Selectsum(Montant)
sum(Montant)
Ventes

From
FromClient
ClientC,C,Ventes
VentesVV Select
Selectsum(Montant)
sum(Montant)
Where
[Link]=[Link]
[Link]=[Link] From
and FromVentes2
Ventes2
Ville=Béchar Client
Client1 1 Client
Ville=Béchar Client
Client Client2 2
Béchariens
Béchariens
Algérois
Algérois

76
 INTÉRÊT DE LA FRAGMENTATION HORIZONTALE(I)

Améliorer la performance
1. Partition Elimination (Pruning)
• Elimination des partitions non pertinentes
• Possibilité d’exécution parallèle des sous requêtes

Select
From
Where
Serveur
Requête
Fragment
Pertinent
Utilisateur Résultat local

Fragment non
Pertinent
Serveur
Table

Fragment
Pertinent
Résultat local

Résultat
Fragment non
Pertinent

77
INTÉRÊT DE LA FRAGMENTATION HORIZONTALE(II)

Amélioration de la performance
2. Partition Wise Joins
 Elimination des jointures non pertinentes
 Possibilité d’exécution parallèle des sous-jointures

Serveur
Select
From
Where

Utilisateur Requête

Table2
Table1
Serveur

Résultat

78
INTÉRÊT DE LA FRAGMENTATION HORIZONTALE(III)

Améliorer la manageabilité
Fragmentation horizontale préserve le schéma logique
 Toutes les opérations se font au niveau partition
 Possibilité de manipulation individuelle ou collective des partitions

Manipuler une partition à la fois.

 Possibilité de définir des index locaux aux partitions
 Existences de plusieurs Fonctions de manipulation des partitions
Fonction Signification
ADD PARTITION Ajouter une partition à une table déjà fragmentée
COLESCE PARTITION Redistribuer les tuples d’une partition dans les autres partitions
DROP PARTITION Supprimer une partition ainsi que son contenu
EXCHANGE PARTITION Convertir une table non fragmentée en une partition d’une autre table et
inversement
MERGE PARTITION Fusionner deux partitions dans une seule
SPLIT PARTITION Eclater une partition en deux partitions

79
TRUNCATE PARTITION Vider une partition sans la supprimer
EXEMPLE D’AJOUT DE DONNÉES
Alimentation hebdomadaire d’une table
 L’administrateur partitionne sa table par semaine
 L’alimentation de l’entrepôt consiste alors à ajouter une partition à la table
 Aucune autre partition ne sera touchée.

Semaine 1 Semaine 3
Semaine 5
Semaine 2 Semaine 4

80
INTÉRÊT DE LA FRAGMENTATION HORIZONTALE(IV)

Améliorer la maintenance et la disponibilité

La manipulation au niveau partition permet

 Cibler la maintenance sur certaines partitions
 Minimiser le temps de maintenance
La possibilité de stocker les partitions sur des emplacements différents permet
 L’effet des pannes de disques est limité
 Partitions saines toujours disponibles Maintenance

Partition1 Partition 2 Partition 3 Partition 4

81
AMÉLIORER LA MAINTENANCE ET LA DISPONIBILITÉ

Améliorer la maintenance et la disponibilité

La possibilité de stocker les partitions sur des emplacements différents permet
• L’effet des pannes de disques est limité
• Partitions saines toujours disponibles

Crash

Partition1 Partition 3
Partition5
Partition2 Partition4
Partition6

82
FRAGMENTATION HORIZONTALE ET INDEX
Un index peut être défini sur une table fragmentée ou non

Un index défini sur une table fragmentée peut être fragmenté ou non.

Index global

 Peut être non fragmenté défini sur une table fragmentée

 Peut être fragmenté où chaque partition de l’index référence plusieurs partitions de la table
Index local

 Equi-partitionné avec la table qu’il référence

 Chaque partition de l’index référence une et une seule partition de la table

83
FRAGMENTATION ET INDEX
Table non Table non
Index fragmentée
Index fragmentée

Table non fragmentée

Index non fragmentée Index fragmentée

Index Table Index Table Index Table

Global fragmentée Global fragmentée Local fragmentée

Table fragmentée

Index global non fragmenté Index global fragmenté

Index local

84
MODES DE FRAGMENTATION

Mode de fragmentation

2
Mode simple Mode composite

Range List Hash

Range-Hash Range-List Range-Range List-Range List-List List-Hash

85
FRAGMENTATION PAR INTERVALLE « RANGE »
Client 1

Age Age<18

Client 2
0 18 60 120
18Age<60

Domaine(Age) Client 3

Client Age60

CREATE TABLE Client

(Client_id NUMBER(5),
Nom Varchar2(20),
Ville Varchar2(20),
Age Number(3),
Genre Varchar2(1))
PARTITION BY RANGE (Age)
(
PARTITION Client_Moins_18 VALUES LESS THAN (18) TABLESPACE TBSMoins27,
PARTITION Client_18_59 VALUES LESS THAN (60) TABLESPACE TBS27-59,
PARTITION Client_60_Et_Plus VALUES LESS THAN (MAXVALUES) TABLESPACE TBSPlus60
);

86
FRAGMENTATION PAR LISTE « LIST »
Client 1

Ville Ville=‘Béchar’

Client 2
Poitiers Paris, Nantes Autres
Ville=‘Alger’ ou
Ville=‘Ouargla’
Domaine(Ville) Client 3

Client Ville= Autres

CREATE TABLE Client

(Client_id NUMBER(5),
Nom Varchar2(20),
Ville Varchar2(20),
Age Number(3),
Genre Varchar2(1))
PARTITION BY List (Ville)
(
PARTITION Client_Béchar VALUES (‘Béchar’) TABLESPACE TBSBECHAR,
PARTITION Client_Alg_Oua VALUES (‘Alger’,’Ouargla’) TABLESPACE TBSALGOUA,
PARTITION Client_Autres VALUES (DEFAULT) TABLESPACE TBSAUTRES
);

87
FRAGMENTATION PAR HACHAGE « HASH »
Client 1
CID F(CID)=x

Client 2
F(CID) F(CID)=y

Fonction de Client 3

Client hachage
F(CID)=z

CREATE TABLE Client

(Client_id NUMBER(5),
Nom Varchar2(20),
Ville Varchar2(20),
Age Number(3),
Genre Varchar2(1))
PARTITION BY Hash (CID)
(
PARTITIONS 3
STORE IN (TBS1, TBS2, TBS3)
);

88
MODES DE FRAGMENTATION COMPOSITE
Client 11
Client 1 Age<18 ET Genre=‘M’
List
(Genre) Client 12
Age<18 ET Genre=‘F’
Age<18
Age Genre
Client 21
Client 2
18Age<60 ET Genre=‘M’
List Client 22
Range (Genre)
(Age) 18Age<60 ET Genre=‘F’
18Age<60
Client 31
Client Age60 ET Genre=‘M’
Client 3
List Client 32
(Genre)
Age60 ET Genre=‘F’

Age60

Premier niveau de Deuxième niveau de

fragmentation fragmentation

89
MODES DE FRAGMENTATION COMPOSITE

CREATE TABLE Client

(Client_id NUMBER(5),
Nom Varchar2(20),
Ville Varchar2(20),
Age Number(3),
Genre Varchar2(1))
PARTITION BY RANGE (Age)
SUBPARTITION BY LIST (Genre)
SUBPARTITION TEMPLATE(
SUBPARTITION Client1 VALUES ('M') TABLESPACE TBSMasculin ,
SUBPARTITION Client2 VALUES ('F') TABLESPACE TBSFéminin )
(
PARTITION Client_Moins_18 VALUES LESS THAN (18),
PARTITION Client_18_59 VALUES LESS THAN (60),
PARTITION Client_60_Et_Plus VALUES LESS THAN (MAXVALUES)
);

90
FRAGMENTATION DÉRIVÉE PAR LE MODE RÉFÉRENCE

Fragmenter une table selon le schéma de fragmentation d’une autre table en utilisant le lien par clé
étrangère.

CREATE TABLE Ventes

(Client_id NUMBER(5),
Client Ventes Time_id NUMBER(5)),
Client1 1 Ventes1 1
Montant NUMBER(20),
Algérois CONSTRAINT order_items_fk
Algérois
Client
Client2 2 Ventes FOREIGN KEY(Client_id) REFERENCES Client(Client_id)
Ventes2 2
Béchariens
Béchariens )
PARTITION BY REFERENCE(order_items_fk);

91