31
Survol du Stockage et de l’Indexage Chapitre 8

1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

Embed Size (px)

Citation preview

Page 1: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

1

Survol du Stockage et de l’Indexage

Chapitre 8

Page 2: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

2

Objectifs

Stockage persistant Organisation des fichiers

Fichiers de données Fichiers d’indexes

Operations sur les fichiers Performance Comparaison

Sortes d’indexes Primaires Secondaires Groupés vs non-groupés; primaires vs secondaires, …

Page 3: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

3

Stockage des Données dans des Fichiers

Un SGBD stocke les relations dans des fichiers d’enregistrements (« records »).

Dans l’architecture d’un SGBD, le niveau des méthodes d’accès aux fichiers supporte le concept de fichier.

Le niveau des méthodes d’accès aux fichiers stocke les fichiers sous forme d’une ou plusieurs pages sur disque et administre ces pages.

L’administrateur des tampons (‘’buffer manager’’) emmène les pages de la mémoire secondaire à la mémoire principale (dans la réserve tampon -- ’’buffer pool’’). Le niveau des méthodes d’accès aux fichiers fait appel à l’administrateur des tampons.

Page 4: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

4

Données sur Stockage Externe

Disques: Peuvent puiser des pages au hasard à un coût fixe Cependant la lecture de plusieurs pages consécutives est moins

coûteuse que une lecture dans un ordre aléatoire Bandes magnétiques: Peuvent ne lire les pages que

séquentiellement Moins coûteux que les disques; utilisées pour archivage

Gestion des fichiers (GF): Méthode pour arranger un fichier d’enregistrements sur stockage externe. La GF utilise Identité d’enregistrement (‘’Record id’’ -- rid): Suffisant pour

localiser physiquement l’enregistrement Indexes: structures de données permettant de trouver les

identités des enregistrements à partir des valeurs des clés de recherche

Page 5: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

5

Organisation des Fichiers

Plusieurs alternatives existent, chacune étant idéale pour certaines situations, et pas pour d’autres: Tas (‘’Heap files’’): Adapté au scannage de tous les

enregistrements. Fichiers triés: Adapté aux situations où les

enregistrements doivent être puisés dans un certain ordre, ou lorsque une plage (‘’range’’) d’enregistrements est requis.

Indexes: Structures des données en forme d’arbres ou de hachage pour organiser les enregistrements.

• Comme les fichiers triés, ils accélèrent les recherches pour un sous ensemble d’enregistrements sur base des valeurs des clés.

• Les modifications sont plus rapides que dans les fichiers triés.

Page 6: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

6

Indexes Un index sur un fichier accélère les sélections sur

les clés de recherche pour cet index. Tout sous-ensemble des attributs d’une relation peut

servir de clé de recherche pour un index sur cette relation.

Une clé de recherche n’est pas la même chose qu’une clé au sens d’ensemble minimal d’attributs qui identifie de manière unique un enregistrement de la relation.

Un index contient une collection (généralement une liste triée) d’entrées des données et permet de puiser de manière efficiente toutes les entrées des données k* en utilisant une valeur de clé k.

Page 7: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

7

Entrées des Données k* dans un Index

Trois alternatives: une entrée des données peut être un enregistrement de données avec une valeur de clé

k une paire <k, rid> une paire <k, liste de rids>

Le choix d’une des alternatives dépend de la technique d’indexage utilisée pour localiser les entrées des données ayant une valeur de clé k. Exemples de techniques d’indexage: Arbres B+,

Arbres ISAM, hachage Typiquement, un index contient de l’information qui

oriente les recherches vers les entrées des données désirées.

Page 8: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

8

Entrées des Données k* dans un Index (Suite)

Les pages feuilles contiennent les entrées des données et sont chaînées. Les pages internes contiennent les entrées de l’index et dirigent la recherche.

Pages

internes

feuilles

pages

Page 9: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

9

Entrées des Données k* dans un Index (Suite)

Alternative 1: La structure de l’index est une organisation de

fichier pour les enregistrements de données (en lieu et place d’un tas ou d’un fichier trié).

Un maximum d’un index peut être créé sur une collection d’enregistrements de données suivant l’alternative 1. (Sinon, les enregistrements seront dupliqués, ce qui conduit à des redondances et à des inconsistances potentielles.)

Si les enregistrements des données sont très nombreux, le # de pages contenant les entrées des données sera très élevé.

Page 10: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

10

Entrées des Données k* dans un Index (Suite)

Alternatives 2 et 3: Ici, les entrées des données sont typiquement

plus petites que les enregistrements de données. Ainsi, ces 2 alternatives sont meilleurs que la première pour traiter les enregistrements de données larges. Elles sont encore bien meilleures lorsque les clés de recherche sont petites.

L’alternative 3 est plus compacte que l’alternative 2, mais utilise des enregistrements à taille variée, même si les clés de recherche sont à taille fixe.

Page 11: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

11

Classification des Indexes Primaire vs. secondaire: Selon que la clé de recherche

contient la clé primaire ou pas, on a un index primaire ou secondaire. Index unique: La clé de recherche contient une

candidate clé. Groupé vs. nongroupé (‘’Clustered’’ vs.’’unclustered’’):

Si l’ordre des enregistrements des données est le même que ou proche de celui des entrées des données, alors l’index est groupé; sinon il est nongroupé.

Eparpillé vs. dense (« sparse » vs. « dense »): Si une entrée des données apparait pour chaque valeur de la clé de recherche, alors l’indexe est dense, sinon il est éparpillé.

Page 12: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

12

Index Groupé vs. Nongroupé Supposez que l’alternative 2 est utilisée pour les

entrées des données et que les enregistrements de données sont stockés sur un tas (‘heap file’). Pour construire un index groupé, d’abord trier le tas (tout

en réservant de l’espace libre sur chaque page). Les pages en dépassement de capacité peuvent être

utiles pour les insertions. (D’où, l’ordre des enregistrements de données est proche de celui utilisé pour trier le tas.)Entrées d’index

Entrées des données

(Fichier Index)

(Fichier des données)

Enregistrements des données

Entrées des données

Enregistrements des données

Groupé Nongroupé

Page 13: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

13

Index Groupé vs. Nongroupé (Suite) Quelques remarques:

L’alternative 1 implique un index groupé; dans la pratique, l’inverse est aussi vrai car les fichiers triés sont rares.

Un fichier ne peut être groupé que sur au plus une clé de recherche.

Le coût de puiser des enregistrements de données en utilisant les index varie beaucoup selon que l’index en question est groupé ou pas.

L’alternative 3 est la plus naturelle pour les indexes secondaires.

Page 14: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

14

Indexes à Hachage

Bon pour les sélections d’égalité.• L’index est une collection de

compartiments (‘buckets’). Bucket = page domiciliaire plus zéro ou plus des pages de dépassement.

• Fonction de hachage h: h(r) = bucket auquel l’enregistrement r appartient. h utilise la clé de recherche de r.

Si l’alternative 1 est utilisée, les buckets contiennent les enregistrements des données; sinon, ils contiennent des pairs <key, rid> ou <key, rid-list>.

Page 15: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

15

Indexes à Arbre B+

Rappel: les pages feuilles contiennent les entrées des données et sont chaînées; les pages internes contiennent les entrées de l’index et dirigent la recherche Structure d’une entrée de l’index:P0 K 1 P 1 K 2 P 2 K m P m

Pages

internes

feuilles

pages

Page 16: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

16

Exemple d’Arbre B+

Trouvez 28*? 29*? Tous les x tels que 15* < x < 30*. Insertion/effacement: Trouvez les entrées des

données dans les feuilles et changez les. Besoin d’ajustage des parents quelques fois. Les changements peuvent parfois s’étendre jusqu’à la racine

2* 3*

Racine

17

30

14* 16* 33* 34* 38* 39*

135

7*5* 8* 22* 24*

27

27* 29*

Entree <= 17 Entree > 17

Page 17: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

17

Modèle de Coût pour Comparer des Organisations de Fichiers *

Nous ignorons les coûts en unités CPU, pour simplifier les choses: P: nombre de pages de données E: nombre d’enregistrements par pages T: temps moyen de lecture/écriture d’une page

sur disque Nous ignorons aussi les gains obtenus en faisant

de la prélecture d’une séquence de pages; D’où les coûts de I/O ne sont que approximatifs

‘’Average-case analysis’’ avec des simplifications simplistes

Ce modèle simpliste ne sert qu’à indiquer les tendances

Page 18: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

18

Organisations de Fichiers ‘’Heap files’’ (ordre aléatoire; insertions à la

fin) Fichiers triés suivant <age, sal> Fichier groupé en arbre B+, alternative 1

avec <age, sal> comme clé de recherche ‘’Heap file’’ avec index à arbre B +

nongroupé et avec <age, sal> comme clé de recherche

‘’Heap file’’ avec un indexe à hachage nongroupé; avec <age, sal> comme clé de recherche

Page 19: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

19

Opérations A Comparer ‘’Scan’’: Puiser tous les enregistrements du

disque Recherche sur base d’égalité ‘’Range selection’’ (sélection d’une plage de

valeurs) Insertion d’enregistrement Effacement d’enregistrement

Page 20: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

20

Simplifications dans l’Analyse Heap Files:

Sélection sur base de l’égalité utilisant la clé; exactement un enregistrement correspond à la valeur de la clé.

Fichiers triés: Compactage du fichier après effacement.

Indexes: Alt (2), (3): taille de l’entrée = 10% de ‘enregistrement. Hachage: pas de buckets de dépassement.

• 80% d’occupation => tailles du fichier = 1.25 fois la taille des données.

Arbre: 67% d’occupation (typique en pratique).• Implique une taille de fichier = 1.5 fois la taille des données.

Page 21: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

21

Coût des Opérations (a) Scan (b) Equality (c ) Range (d) Insert (e) Delete

(1) Heap PT 0.5PT PT 2T Search +T

(2) Sorted PT Tlog 2P Tlog 2 P + # matches

Search + PT

Search +PT

(3) Clustered 1.5PT Tlog F 1.5P Tlog F 1.5P + # matches

Search + T

Search +T

(4) Unclustered Tree index

PT(E+0.15) T(1 + log F 0.15P)

Tlog F 0.15P + # matches

T(3 + log F 0.15P)

Search + 2T

(5) Unclustered Hash index

PT(E+0.125)

2T PT 4T Search + 2T

Page 22: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

22

Considérations sur la Charge de Travail

Importantes questions pour le choix des indexes Questions à se poser pour chaque requête:

A quelle relations a-t-elle accès? Quels attributs sont puisés? Quels attributs sont impliqués dans les conditions de

sélection ou de join? Quelle est la sélectivité de ces conditions?

Pour chaque opération de modification: Quels attributs sont impliqués dans les conditions de

sélection ou de join? Quelle est la sélectivité de ces conditions?

Le type de la modification (INSERT/DELETE/UPDATE) ainsi que les attributs affectés.

Page 23: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

23

Choix d’Indexes

Quels indexes devraient être créés? Quelles relations devraient avoir des indexes? Quels attributs devraient former la clé de

recherche? Devrait-on avoir plusieurs indexes?

Quelle sorte d’index devrait-on avoir? Primaire? Groupé? Dense? Haschage? Arbre?

Page 24: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

24

Choix d’Indexes (Suite) Une approche:

Considérer les requêtes les plus importantes à tour de rôle. • Pour chacune de ces requêtes, considérer le meilleur plan

d’exécution qui utiliserait le choix actuel. Voir si un meilleur plan n’est pas réalisable avec des indexes additionnels. Si c’est le cas, créer ces derniers.

Cette approche suppose que l’on comprend comment un SGBD évalue des requêtes et crée des plans d’exécution.

La présente discussion considère des requêtes mono relationnelles.

Avant de créer un index, l’on doit aussi prendre son impact sur les modifications (dans la charge de travail du système) en considération, car Les indexes peuvent accélérer les requêtes et en même temps

ralentir les modifications. Ils requièrent aussi de l’espace disque !

Page 25: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

25

Guide pour la Sélection des Indexes Les attributs dans la clause WHERE sont des candidats

appropriés pour être des clés d’indexes: Une recherche sur base d’égalité suggère un indexe à hachage. Une plage des valeurs suggère un index à arbre. Le regroupement est particulièrement utile pour des requêtes à

plage; il est aussi utile pour des recherches sur base d’égalité en cas de duplicata.

Des clés de recherche à attributs multiples devraient être utilisées si la clause WHERE contient plusieurs conditions: L’ordre des attributs est important pour les requêtes à plage.

On essaie d’abord de choisir des indexes qui sont bénéfiques à autant de requêtes que possible.

Le choix d’un index regroupé devrait être basé sur les requêtes importantes qui en bénéficieraient le plus.

Page 26: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

26

Exemples d’Indexes Groupés Un index à arbre B+ sur E.age

peut être utilisé pour retrouver les tuples qualifiés.

Considérons la requête avec GROUP BY. Si le nombre de tuples avec

E.age > 10 est très élevé, utiliser un index sur E.age et ensuite faire un tri peut coûter bien cher.

Un index groupé sur E.dno peut faire mieux.

Requêtes à égalité et duplicatas: Un groupement sur E.hobby aiderait.

SELECT E.dnoFROM Emp EWHERE E.age>40

SELECT E.dno, COUNT (*)FROM Emp EWHERE E.age>10GROUP BY E.dno

SELECT E.dnoFROM Emp EWHERE E.hobby=Stamps

Page 27: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

27

Indexes avec Clés de Recherche Composées

Clés de Recherche Composées: Recherche sur une combinaison de champs. Requêtes à égalité: Chaque valeur

de champs est égale à une constante. P.ex.: pour l’index <sal,age>, on peut avoir:

• age=20 AND sal =75 Requêtes à plage: Un champ

donné n’est pas une constante. P.ex.:

• age =20; ou age=20 AND sal > 10

Les entrées des données dans l’index sont triées par la clé de recherche pour supporter des requêtes à plages.

sue 13 75

bob

cal

joe 12

10

20

8011

12

name age sal

<sal, age>

<age, sal> <age>

<sal>

12,20

12,10

11,80

13,75

20,12

10,12

75,13

80,11

11

12

12

13

10

20

75

80

Enregistrements des données triés par name

Entrées des données dans l’index triées par<sal,age>

Entrées des donnéestriées par <sal>

Exemples d’indexes utilisant l’ordre lexicographique.

Page 28: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

28

Clé de recherche Composée Pour retrouver des enregistrements de la relation

Emp avec age=30 AND sal=4000, un index sur <age,sal> serait meilleur que un index sur age ou un index sur sal.

Si la condition est 20<age<30 AND 3000<sal<5000: Un index à arbre groupé sur <age,sal> ou <sal,age>

est le meilleur choix. Si la condition est age=30 AND 3000<sal<5000:

Un index groupé sur <age,sal> est meilleur qu’un index sur <sal,age>.

Les indexes composés sont plus larges et plus souvent modifiés que les indexes simples.

Page 29: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

29

Spécification des Indexes en SQL

Le standard ne supporte pas (encore) les indexes !!! En pratique, chaque système commercial supporte les indexes. Un

exemple générique de création d’indexe est:

CREATE INDEX IndexAgeGpa ON Students

WITH STRUCTURE = BTREE

KEY = (age, gpa) Indexes en Oracle:

• Création:

CREATE INDEX index_name ON table_name (attribute)• Indexes composés:

CREATE INDEX index_name ON table_name (att1, …,attn)

• Destruction:

DROP INDEX index_name

Page 30: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

30

Résumé Plusieurs alternatives d’organisations de fichiers

existent, chacun étant approprié dans chaque situation.

Si des requêtes de sélection sont fréquentes, trier le fichier ou construire un index est important. Index à hachage seulement bons pour les

sélections sur base de l’égalité. Fichiers triés et indexes à arbre bons pour les

sélections des plages de valeurs; mais aussi bon pour sélections sur base de l’égalité. (Puisque les fichiers sont rarement trié en pratique, les arbres B+ sont de bien meilleurs indexes.)

Un index est une collection d’entrées des données plus une manière rapide de trouver ces entrées en usant des valeurs d’une clé de recherche.

Page 31: 1 Survol du Stockage et de lIndexage Chapitre 8. 2 Objectifs Stockage persistant Organisation des fichiers Fichiers de données Fichiers dindexes Operations

31

Résumé (Suite) Les entrées des données peuvent être des

enregistrements, ou des paires <key, rid> ou <key, rid-list>.

On peut avoir plusieurs indexes sur un fichier d’enregistrements donné, chacun ayant une clé de recherche différente.

Un index peut être groupé ou nongroupé, primaire ou secondaire, ainsi que dense ou éparpillé.

Les différences ci haut ont des conséquences sur l’utilité des données et la performance des opérations.