Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Matière Sélectionnée: Triage Externe, Join à Hachage, … Chapitres 1315: 13.113.5, 14.4,

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke 1

Matière Sélectionnée: Triage Externe, Join à Hachage,

…

Chapitres 13—15: 13.1—13.5, 14.4, …


Pourquoi Trier? Problème classique en informatique (Voir Knuth,

v.3)! Données requises en ordre trié

P.ex.: Trouver les étudiants en ordre croissant de gpa

Chargement en vrac de l’index à arbre B+ Élimination des duplicatas dans une collection

d’enregistrements Algorithme de Sort-merge join Problème commun: trier des données trop larges

pour tenir en mémoire


Merge Sort à 2 Voies: Requiert 3 Tampons

Passage 1: Lire une page, la trier (en mémoire), l’écrire sur disque. seulement une page tampon utilisée

Passage 2, 3, …, etc.: trois pages tampon utilisées

Mémoire principale

ENTREE 1

ENTREE 2

SORTIE

DisqueDisque


Merge Sort à 2 Voies: Algorithmeproc two-way_extsort(file)

// Trier un fichier sur disque en utilisant 3 pages tampons// Passage 0: produit des runs d’une pageLire chaque page du fichier dans la mémoire, le trier et l’écrire.//Fusionner des paires de runs pour produire de plus long runs// jusqu’à ce qu’il ne reste qu’un seul runWhile # de runs à la fin du passage précédent > 1 do: //Traiter les passages i=1,2,… While il y a des runs à fusionner issus du passage précédent

do: Prendre les 2 runs suivants du passage précèdent.

Lire chaque run dans un tampon d’entrée, 1 page à la fois.

Fusionner les runs et écrire le résultat dans le tampon de sortie en

forçant le contenu de ce tampon vers le disque page par page.

endproc


Merge Sort Externe à 2 Voies A chaque passage on lit et

écrit chaque page du fichier => 2N I/O’s par passage.

N pages dans le fichier => # de passages.

D’où le coût total est:

Idee: Divide et impera:

trier des sousfichiers et fusionner.

Dans l’exemple, le fichier d’entrée contient 7 pages; les pages noires montrent ce qui se passerait avec 8 pages.

log2 1N

2 12N Nlog

Fichier

runs de 1page

runs de 2 pages

runs de 4 pages

runs de 8 pages

PASSAGE 0

PASSAGE 1

PASSAGE 2

PASSAGE 3

9

3,4 6,2 9,4 8,7 5,6 3,1 2

3,4 5,62,6 4,9 7,8 1,3 2

2,34,6

4,7

8,91,35,6 2

2,3

4,46,7

8,9

1,23,56

1,22,3

3,4

4,56,6

7,8


Merge Sort Externe Général Coment utiliser plus de 3 pages tampon ? Pour trier un fichier avec N pages en utilisant B

pages tampon: Passage 0: utiliser B pages tampon. Produit

runs triés de B pages chacune. Passage 2, …, etc.: fusionner B-1 runs.

N B/

B tampons en mémoire

ENTREE 1

ENTREE B-1

SORTIE

DisqueDisque

ENTREE 2

. . . . . .

. . .


Merge Sort Externe Général: Algorithme

proc two-way_extsort(file)// Trier un fichier sur disque en utilisant B pages tampons// Passage 0: produit des runs de B pagesLire B pages du fichier dans la mémoire, les trier et les écrire.//Fusionner B-1 runs pour produire de plus long runs// jusqu’à ce qu’il ne reste qu’un seul runWhile # de runs à la fin du passage précédent > 1 do: //Traiter les passages i=1,2,… While il y a des runs à fusionner issus du passage précédent

do: Prendre les B-1 runs suivants du passage précèdent.

Lire chaque run dans un tampon d’entrée, 1 page à la fois.

Fusionner les runs et écrire le résultat dans le tampon de sortie en

forçant le contenu de ce tampon vers le disque page par page.

endproc


Coût du Merge Sort Externe

Nombre de passages: Coût = 2N * (# de passages) P.ex., avec 5 pages tampon, trier un fichier

de 108 pages: Passage 0: = 22 runs triés de 5 pages

chacune (le dernier n’ayant que 3 pages) Passage 1: = 6 runs triés de 20 pages

chacune (le dernier avec seulement 8 pages) Passage 2: 2 runs triés, 80 pages et 28 pages Passage 3: fichier trié de 108 pages

1 1 log /B N B

108 5/

22 4/


Nombre de Passages du Triage Externe

N B=3 B=5 B=9 B=17 B=129 B=257100 7 4 3 2 1 11,000 10 5 4 3 2 210,000 13 7 5 4 2 2100,000 17 9 6 5 3 31,000,000 20 10 7 5 3 310,000,000 23 12 8 6 4 3100,000,000 26 14 9 7 4 41,000,000,000 30 15 10 8 5 4


I/O pour le Merge Sort Externe

… de plus longs runs signifient souvent moins de passages!

Les algorithmes présentés font des I/O d’une page à la fois.

En pratique, on lit un bloc de pages sequentiellement!

Suggestion: les tampons devraient contenir des blocs de pages et non des pages individuelles. En pratique, la plupart des fichiers sont triés en 2-3

passages. Des DBMSs typiques trient 1M d’enreg.’s de la taille de 100

bytes en 15 minutes.


Nombre de Passages du Triage Optimisé

N B=1,000 B=5,000 B=10,000100 1 1 11,000 1 1 110,000 2 2 1100,000 3 2 21,000,000 3 2 210,000,000 4 3 3100,000,000 5 3 31,000,000,000 5 4 3

Taille des Blocs = 32, le passage initial produit des runs de 2B.


Double Tampons Afin de réduire le temps d’attente pour

que une requête I/O soit complétée, on peut prélire les données dans un bloc de réserve. Potentiellement, plus de passages sont

possibles; en pratique, la plupart des fichiers sont toujours triés en 2-3 passages.

SORTIE

SORTIE'

Disque Disque

ENTREE 1

ENTREE k

ENTREE 2

ENTREE 1'

ENTREE 2'

ENTREE k'

Taille de blocb

B tampons en mémoire, fusion à k voies


Utilisation des Arbres B+ pour Trier

Scénario: La table à trier a un indexe à arbre B+ sur les colonnes de triages.

Idée: Puiser les enregistrements dans l’ordre en traversant les feuilles de l’indexe.

Est-ce une bonne idée ? Cas à considérer:

L’index B+ est groupé: Bonne idée! L’index B+ est non groupé: Pourrait être une

très mauvaise idée!


Index B+ Groupé Utilisé pour Trier

Coût: partir de la racine à la feuille la plus à gauche et de là traverser toutes les pages feuilles (Alternative 1)

Si l’alternative 2 est utilisée? Coût additionnel de puiser les enreg.’s des données: chaque page puisée juste une fois.

Toujours meilleur que le triage externe!

(Oriente la recherche)

Enregistrements des données

Index

Entrees des donnees

("Sequence set")


Index B+ Nongroupé Utilisé pour Trier

Alternative (2) pour les entrées des données; chaque entrée contient le rid d’un enregistrement des données. En général, un I/O par enregistrement des données!

Données

Index

Entrées des données


Hash Join: Idée Deux phases: partition et vérification (‘’matching’’) Partition: Repartir les deux relations R et S en utilisant

la même fonction de hachage h: les tuples de R dans la partition i de R ne peuvent être joints que avec ceux de la partition i de S. Suppositions faites: Le # de pages tampon est B: 1 pour entrée et 1 pour sortie Le # de partitions est k Le # de pages tampon utilisé par les partitions est B-2 Hacher R et S sur les colonnes de join i et j

Matching: Lire une partition Ri de R en mémoire et ensuite la hacher en utilisant une fonction de hachage h2 (différente de h). Scanner la partition Si de S pour rechercher les tuples correspondants aux tuples de Ri (en utilisant h2 pour vérifier la table de hachage de Ri).


Hash Join: Algorithme// Calculer le join de deux relations R et S sur les colonnes Ri et Sj.// Repartir R en k partitionsforeach tuple r de R do: lire r et l’ajouter à la page tampon h(ri); // Forcer cette page vers le disque

au // fur et à mesure qu’elle se remplit

// Repartir S en k partitionsforeach tuple s of S do: lire s et l’ajouter à la page tampon h(sj); // Forcer cette page vers le disque

au // fur et à mesure qu’elle se remplit

//Phase de vérification (‘’Probing’’/’’matching’’)for l=1, …, k do: //Construire une table de hachage en mémoire pour Rl, utilisant h2

foreach tuple r de Rl do: lire r et l’insérer dans la table de hachage de Rl utilisant h2(ri);

// Scanner les tuples de Sl et vérifier les tuples correspondants à r dans Rl

foreach tuple s de Sl do: lire s et vérifier la table de hachage de Rl en utilisant h2(sj);

pour tout tuple correspondant r dans Rl, sortir <r,s>;réinitialiser la table de hachage pour préparer la prochaine partition;


Résumé

Le triage externe est important; un SGBD peut dédier une partie de la réserve des pages tampon juste pour cette tâche!

Le merge sort externe minimalise les coûts des entrées et sorties vers le disque: Passage 0: Produit des runs triés de taille B (# de page tampon).

Les passages suivants sont des runs de fusion. Le # de runs fusionnés à la fois dépend de B et de la taille du bloc. Bloc de large taille => petit # de runs à fusionner.

Les index à arbre B+ groupé sont bons pour le triage externe; les index nongroupés sont généralement très mauvais.

Les algorithmes de join sont cruciaux en pratique. Le hash join est largement supporté par les SGBDs.

Documents

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke1 Matière Sélectionnée: Triage Externe, Join à Hachage, … Chapitres 1315: 13.113.5, 14.4,