p
u
b
l
i
c
i
t
é
publicité

Discussion: jointure par hachage

  1. #1
    Candidat au titre de Membre du Club
    Inscrit en
    janvier 2010
    Messages
    110
    Détails du profil
    Informations forums :
    Inscription : janvier 2010
    Messages : 110
    Points : 12
    Points
    12

    Par défaut jointure par hachage

    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

  2. #2
    Membre émérite Avatar de Jester
    Inscrit en
    septembre 2003
    Messages
    813
    Détails du profil
    Informations forums :
    Inscription : septembre 2003
    Messages : 813
    Points : 967
    Points
    967

    Par défaut

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

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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;

  3. #3
    Rédacteur
    Avatar de SQLpro
    Homme Profil pro
    Expert SGBDR & SQL
    Inscrit en
    mai 2002
    Messages
    14 646
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Expert SGBDR & SQL
    Secteur : Conseil

    Informations forums :
    Inscription : mai 2002
    Messages : 14 646
    Points : 32 535
    Points
    32 535

    Par défaut

    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 +
    Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL
    Site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/
    Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.
    Blog SQL, SQL Server, modélisation données : http://blog.developpez.com/sqlpro
    http://www.sqlspot.com : modélisation, conseils, audit, optimisation, formation
    * * * * * Enseignant CNAM PACA - ISEN Toulon - CESI Aix en Provence * * * * *

  4. #4
    Candidat au titre de Membre du Club
    Inscrit en
    janvier 2010
    Messages
    110
    Détails du profil
    Informations forums :
    Inscription : janvier 2010
    Messages : 110
    Points : 12
    Points
    12

    Par défaut

    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

  5. #5
    Candidat au titre de Membre du Club
    Inscrit en
    janvier 2010
    Messages
    110
    Détails du profil
    Informations forums :
    Inscription : janvier 2010
    Messages : 110
    Points : 12
    Points
    12

    Par défaut

    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

  6. #6
    Candidat au titre de Membre du Club
    Inscrit en
    janvier 2010
    Messages
    110
    Détails du profil
    Informations forums :
    Inscription : janvier 2010
    Messages : 110
    Points : 12
    Points
    12

    Par défaut

    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

  7. #7
    Rédacteur
    Avatar de SQLpro
    Homme Profil pro
    Expert SGBDR & SQL
    Inscrit en
    mai 2002
    Messages
    14 646
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Expert SGBDR & SQL
    Secteur : Conseil

    Informations forums :
    Inscription : mai 2002
    Messages : 14 646
    Points : 32 535
    Points
    32 535

    Par défaut

    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 +
    Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL
    Site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/
    Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.
    Blog SQL, SQL Server, modélisation données : http://blog.developpez.com/sqlpro
    http://www.sqlspot.com : modélisation, conseils, audit, optimisation, formation
    * * * * * Enseignant CNAM PACA - ISEN Toulon - CESI Aix en Provence * * * * *

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. jointure par hachage
    Par yarab dans le forum Optimisations
    Réponses: 0
    Dernier message: 16/07/2011, 20h49
  2. Estimation de coût (jointure par hachage)
    Par megainfo dans le forum Optimisations
    Réponses: 2
    Dernier message: 15/10/2010, 20h20
  3. jointure par champ expression sql
    Par gg2vig dans le forum SAP Crystal Reports
    Réponses: 3
    Dernier message: 28/11/2007, 10h30
  4. [Hibernate 3.2.5] Jointure par Criteria
    Par pbossard dans le forum Hibernate
    Réponses: 2
    Dernier message: 06/11/2007, 10h15
  5. recherche de jointure par requête
    Par vacknov dans le forum Requêtes
    Réponses: 4
    Dernier message: 25/07/2006, 22h21

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo