Gilles Heurtebize 1 Projection et Jointure par hachage Bases De Données C1

Gilles Heurtebize1

Projection et Jointure par hachage

Bases De Données C1

Projection et jointure par hachage2

Plan

Projection par hachage.– Rappel sur la projection.– Principes de la projection par hachage.– Illustration.

Phase de projection/hachage. Phase d’élimination des doublons.

Jointure.– Principes de la jointure par hachage.– Illustration.

Phase de hachage. Phase de jointure.

– Coût de la jointure par hachage.


Projection par hachage


La projection

La projection d’une relation sans sélection consiste en:– Examiner les nuplets un par un et a éliminer les

champs que l’on ne veut pas garder.– Éliminer les nuplets en double.

C’est cette dernière étape qui coûte cher.– Deux techniques sont possibles:

– Le tri– Le hachage


Algorithme en deux phases.

Phase de projection et de hachage.– On accède séquentiellement à la table dans un tampon.– Chaque nuplet projeté est place par une fonction de hachage

uniforme dans un des M-1 tampons.(La fonction retourne un entier compris entre 1 et M-1).

– Quand un tampon est plein il est stocké sur le disque.A l’issue de cette phase on a M-1 partitions.

Phase d’élimination des doublons.– Lire une par une les M-1 partitions en mémoire.Du fait du

hachage, les doublons se trouvent dans la même partition.– Effectuer un tri et éliminer les doublons.

Principes de la projection par hachage


ILLUSTRATION

Phase de projection / hachage



Table A

Accès séquentiel

M-1 Tampons


Table A

ProjectionAccès séquentiel


M-1 Tampons


Table A


Hachage

Distribution dans les M-1 tampons


M-1 Tampons


Table A


Tampon 2 plein


M-1 Tampons


Table A


Écrire les nupletsPartition 2


M-1 Tampons


Table A


Partition 2

Hachage



M-1 Tampons


Table A


Partition 2

Tampon M-1 plein


M-1 Tampons


Table A


Partition 2

Écrire les nupletsPartition M-1


M-1 Tampons


Table A


Partition 2

Partition M-1

Hachage



M-1 Tampons


Table A


Partition 2

Partition M-1

Tampon 1 plein


M-1 Tampons


Table A


Partition 2

Partition M-1

Écrire les nupletsPartition 1


M-1 Tampons


Table A


Partition M-1

Partition 1

Partition 2


M-1 Tampons


ILLUSTRATION

Élimination des doublons



Partition 2

Partition M-1

Partition 1



Partition 2

Partition M-1

Partition 1

Lecture de la partition 1 en mémoire



Partition 2

Partition M-1

Partition 1

Tri en mémoireet élimination des doublons



Partition 2

Partition M-1

Partition 1



Partition 2

Partition M-1

Partition 1

Lecture de la partition M-1 en mémoire


Remarques

Algorithme adapté dans le cas ou le nombre de tampons est assez important par rapport à la relation projetée.

En cas de débordement d’une partition on peut récursivement recommencer l’opération en partitionnant la partition en sous partitions et éliminer les doublons dans chaque sous-partitions.


Une autre façon de faire pour éliminer les doublons en mémoire.

– Lecture page par page de la partition en mémoire centrale dans un tampon.

– Chaque nuplet n est hache avec une fonction h’ de hachage différente de h. (celle qui a permit de partitionner la table A)

– Chaque nuplet est placé dans les N-1 tampons restants.– Vérifier si il il existe un nuplet déjà stocké tel que h’(n’) = h’(n).– Si il n’existe pas, n’ est stocké à l’emplacement h’(n’).– Sinon vérifier si n est différent de n’.– Si n=n’ alors n’ est élimine sinon n’ est stocké.


Jointure par hachage


Jointure par hachage

Algorithme récent Très efficace quand une des deux tables est

petite.

Algorithme en option dans ORACLE.

Il est indispensable d’avoir des statistiques


Principes de la jointure par hachage

On hache la plus petite des deux tables sur l’attribut de jointure, en n partitions.

On hache la seconde table sur l’attribut de jointure avec la même fonction, en n autres partitions.

On associe les partitions par paire, et on fait la jointure.

Essentiel: pour chaque paire, au moins une partition doit tenir en mémoire.


ILLUSTRATION

Phase de hachage


Phase de hachage

Mémoire

Table A

Table B

M tampons


Phase de hachage

Table A

Table B

Lecture


Phase de hachage

Table A

Table B

Hachage



Phase de hachage

Table A

Table B

Partition A1

Partition A2

Partition Am-2

Écrire


Phase de hachage

Table A

Table B

Partition A1

Partition A2

Lecture

Partition An-2

Projection et jointure par hachage36Partition Bn-2

Phase de hachage

Table A

Table B

Partition B2Partition A2

Lecture

Hachage

Partition An-2



Phase de hachage

Au l’issue de la première phase,on obtient A n-2 partitionsassocies à B n-2 partitions.

Partition Bn-2


Partition An-2



Phase de jointure

ILLUSTRATION


Phase de jointure

Mémoire

Partition Bn-2


Partition An-2



Phase de jointure

Lecture de la partition A1 en mémoire

Partition Bn-2


Partition An-2



Phase de jointure

Partition A1 en mémoire

Lecture séquentielle de la partition B1 en

mémoire

Partition Bn-2


Partition An-2



Phase de jointure

Écriture


Jointure

Partition Bn-2


Partition An-2



Phase de jointure

Lecture de la partition A2 en mémoire

Partition Bn-2


Partition An-2



Phase de jointure

Lecture séquentielle de la partition B2 en

mémoire


Partition Bn-2


Partition An-2



Phase de jointure

Jointure


Partition Bn-2


Partition An-2



Phase de jointure

Lecture de la partition An-2 en mémoire

Partition Bn-2


Partition An-2



Phase de jointure

Partition An-2 en mémoire

Lecture séquentielle de la partition Bn-2 en

mémoire

Partition Bn-2


Partition An-2



Phase de jointure

Partition An-2 en mémoire

Lecture séquentielle de la partition Bn-2 en

mémoire

Jointure

Partition Bn-2


Partition An-2



Phase de jointure

Lecture en mémoire des

partitions de A

Jointure

Lecture séquentielle des des partitions de B

Partition Bn-2


Partition An-2



Pour la première phase– Chaque table est lu entièrement puis hachées dans

les partitions qui sont recopiés sur disque page par page.

2 (Nb Blocs x Partitions de A + Nb Blocs x Partitions de B ).

Pour la seconde phase– Chaque table partitionnée est lue une fois.

Au total 3 (Nb Blocs x Partition de A + Nb Blocs x Partition de B ).

Coût de la jointure par hachage


Remarques

Algorithme adapté quand toute partition de la plus petite table tiens en mémoire.

En cas de débordement d’une partition il faut appliquer la même méthode employée pour la projection.

L’algorithme de jointure présenté suppose que l’on a M-2 tampons pour une partition de la table A, un tampon pour la table B et un tampon pour la jointure.

Il existe d‘autres variantes de cet algorithme.


Remarques (suite)

Ex:– Si la table A est si petite qu’elle tiens en mémoire:

Partitionner la table A dans un des M-2 tampons comme précédemment.

Lire séquentiellement la table B en appliquant sur chaque nuplet la même fonction de hachage.

Le comparer avec les nuplets de la table A et faire la jointure si il y a lieu.

– Dans ce cas,chaque table n’est lu q’une seule fois.– le coût est de:

(Nb Blocs x Partition de A + Nb Blocs x Partition de B ).


Références

Cours de bases de données.

Aspects Systèmes.

Phillippe Rigaux, Michel Sholl

Documents

Gilles Heurtebize 1 Projection et Jointure par hachage Bases De Données C1