jointure par hachage [Résolu]

[sitws]

salut,
j'ai lu un petit peu sur la jointure par hachage, et j'ai compris qu'on l'applique quand les tables ne sont pas indexées, et quand on a une equi jointure.
voici l'adresse du seul document ou il explique le mecanisme de la jointure par un schema: http://www.fil.univ-lille1.fr/~lhous...BDA-C6a-6p.pdf

est ce que vous pouvez me donner un exemple de deux relations, et une requete ou le SGBD applique la jointure par hachage.

Merci

[Jester]

Sous Oracle on peut forcer le hachage. Souvent ça marche bien pour les requêtes analytiques.

Code :

1
2
3
SELECT /*+ USE_HASH (s i) */ DISTINCT s.srvr_id
FROM servers s, serv_inst i
WHERE s.srvr_id = i.srvr_id;

[SQLpro]

La technique de jointure par hachage consiste à calculer une clef de hachage par rapport aux attributs de jointure. Ceci conduit à un entier de part et d'autre.
Il est bien plus facile de rapprocher deux entiers que deux clefs consituées de multiples colonnes, ou d'une longue colonne (par exemple une grande chaine de caractères), ou encore d'un composé de deux (plusieurs colonnes de type VARCHAR par exemple).
Bien entendu, c'est le moteur relationnel qui choisit le type de jointure a effectuer en fonction des statistiques et des index dont il dispose.
Contraindre le moteur à effectuer tel algorithme de jointure est généralement et sauf cas très exceptionnel, une très mauvaise idée : cela à toutes les chances de nuire d'emblée aux performances en sus de statifier le plan de requête !

De manière plus fine, l'opération consiste à réaliser un table de "hash bucket" dans laquelle on trouve une correspondance entre les attributs et la clef de hache calculée, puis faire les rapprochements.

A +

[sitws]

salut,
j'ai lu que L'algorithme de jointure par hachage crée en mémoire une table de hachage de la plus petite des deux entrées, puis lit l'entrée la plus grande et teste la table de hachage en mémoire pour rechercher les correspondances qui seront écrites dans une table de travail.

par exemple: si on a deux relations R1,R2
R1(ID,Nom) et R2(IDcmd,DateDeCommande,Client)
et notre requete est:select * from R1,R2 where R1.ID=R2.Client and client.Nom="Dupond"

j'ai trouvé dans ce document des schema qui illustre ce phenomene:http://www.fil.univ-lille1.fr/~lhous...BDA-C6a-6p.pdf

je suis bloqué dans le slide17.

ici en appliquant l'algorithme de jointure par hachage, le moteur va créer en memoire une table de hachage de la relation R1 contenant tous les tuples de R1(ce qui en bleu dans le petit rectangle) , ensuite est ce qu'il lit tout un tuple de R2 en memoire ou seulement le champ(à partir du disque) qui sert pour la correspondance , ici le champ client de la relation R2?

d'aprés le schema, je crois que ce qui est en vert et en bleu est un tuple, parce que en sortie on aura probablement un ensemble de tuples qui verifie la conditions; est ce que mon raisonnement est juste jusqu'à maintenant?

si oui, il me reste un seule souci, le petit rectangle en rouge represente tout un un tuple, sous ensemble de tuple, ou seulement l'attribut qui sert à executer la condition?

si j'ai mal raisonné, vos remarques sont les bienvenues.
Merci d'avance

[sitws]

salut,

Maintenant tous les points sont eclaircis dans ma tete, aprés avoir lu:
http://barzilouik.free.fr/cnam/DEA_S...temesSGBDR.pdf
(page 76)

il me reste seulement un seul souci(page 76):
pourquoi le cout de la premiere phase=2(BR+BS)?
BR le nombre de pages de la relation R
BS le nombre de pages de la relation S

il est evident que le cout =BR+BS mais pourquoi il l'ont multuplié par 2?


Merci

[sitws]

salut,
Aprés une longue recherche , j'ai trouvé que quand on parle du cout on parle du nombre d'entrée sortie, et devient evident que le cout de la phase de partitionnement =2(BR+BS)


Merci

[SQLpro]

Le coût ne concerne pas seulement les IO, mais en fonction des IO le cout de chaque opération élémentaire en terme de consommation CPU... Par exemple une jointure par hachage nécessite d'estimer le nombre de ligne à rapprocher et on en calcule le cout par rapport à une règle dépendante des statistiques de distribution des données (cardinalité de la jointure).

A +