par Guillaume Lelarge.

Jointure par hachage


L'algorithme de jointure par hachage vise le point faible de la jointure par boucle imbriquée : les nombreux parcours d'index B-tree lors de l'exécution de la requête interne. À la place, il charge les enregistrements candidats d'un côté de la jointure dans une table de la jointure qui peut être sondée très rapidement pour chaque ligne provenant de l'autre côté de la jointure. Configurer une jointure de hachage requiert une autre approche de l'indexation qu'une jointure par boucle imbriquée. Il est aussi possible d'améliorer les performances d'une jointure de hachage en sélectionnant peu de colonnes, ce qui se révèle être un challenge pour la plupart des ORM.

La stratégie d'indexation pour une jointure de hachage est très différente car il n'est pas nécessaire d'indexer les jointures de colonnes. Les seuls index améliorant les performances de la jointure de hachage sont ceux qui portent sur les prédicats where indépendants.

Astuce

Indexez les prédicats where indépendants pour améliorer les performances des jointures de hachage.

Considérez l'exemple suivant. Il extrait toutes les ventes pour les six derniers mois avec les détails correspondants de l'employé :

SELECT *
  FROM ventes s
  JOIN employes e ON (s.id_supplementaire = e.id_supplementaire
                  AND s.id_employe        = e.id_employe)
 WHERE s.date_vente > trunc(sysdate) - INTERVAL '6' MONTH

Le filtre DATE_VENTE est la seule clause where indépendante. Cela signifie que cela fait référence à une seule table et n'appartient pas aux prédicats de jointure.

--------------------------------------------------------------
| Id | Operation          | Name      | Rows  | Bytes | Cost |
--------------------------------------------------------------
|  0 | SELECT STATEMENT   |           | 49244 |    59M| 12049|
|* 1 |  HASH JOIN         |           | 49244 |    59M| 12049|
|  2 |   TABLE ACCESS FULL| EMPLOYES  | 10000 |     9M|   478|
|* 3 |   TABLE ACCESS FULL| VENTES    | 49244 |    10M| 10521|
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."ID_SUPPLEMENTAIRE"="E"."ID_SUPPLEMENTAIRE"
          AND "S"."ID_EMPLOYE"  ="E"."ID_EMPLOYE")
   3 - filter("S"."DATE_VENTE">TRUNC(SYSDATE@!)
                              -INTERVAL'+00-06' YEAR(2) TO MONTH)

La première étape de l'exécution est un parcours complet de la table pour charger tous les employés dans une table de hachage (identifiant 2 du plan). La table de hachage utilise les prédicats de jointure comme clé. À l'étape suivante, la base de données fait un autre parcours complet de la table VENTES et ignore toutes les ventes qui ne satisfont pas la condition sur DATE_VENTE (identifiant 3 du plan). Pour les enregistrements VENTES correspondants, la base de données accède à la table de hachage pour charger les détails correspondants des employés.

Le seul but de la table de hachage est d'agir comme une structure tem­poraire en mémoire pour éviter d'avoir à accéder de nombreuses fois à la table EMPLOYE. La table de hachage est initialement chargée en une seule fois, pour qu'il ne soit pas nécessaire d'utiliser un index pour récupérer efficacement des enregistrements seuls. L'information du prédicat con­firme qu'aucun filtre n'est appliqué sur la table EMPLOYES (identifiant 2 du plan). La requête n'a aucun prédicat indépendant sur cette table.

Important

Indexer les prédicats de jointure n'améliore pas les performances d'une jointure de hachage.

Cela ne signifie pas qu'il est impossible d'indexer une jointure de hachage. Les prédicats indépendants peuvent être indexés. Ces conditions sont appliquées lors d'une des deux opérations d'accès de table. Dans l'exemple ci-dessus, il s'agit du filtre sur DATE_VENTE.

CREATE INDEX date_ventes ON ventes (date_vente);

Le plan d'exécution suivant utilise cet index. Néanmoins, il utilise un parcours complet de table pour la table EMPLOYES car la requête n'a pas de prédicat where indépendant sur EMPLOYES.

---------------------------------------------------------------
| Id | Operation                    | Name       | Bytes| Cost|
---------------------------------------------------------------
|  0 | SELECT STATEMENT             |            |   59M| 3252|
|* 1 |  HASH JOIN                   |            |   59M| 3252|
|  2 |   TABLE ACCESS FULL          | EMPLOYES   |    9M|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| VENTES     |   10M| 1724|
|* 4 |    INDEX RANGE SCAN          | DATE_VENTES|      |     |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("S"."ID_SUPPLEMENTAIRE"="E"."ID_SUPPLEMENTAIRE"
       AND "S"."ID_EMPLOYE"  ="E"."ID_EMPLOYE"  )
4 - access("S"."DATE_VENTE" > TRUNC(SYSDATE@!)
                             -INTERVAL'+00-06' YEAR(2) TO MONTH)
Indexer une jointure de hachage est symétrique contrairement à la jointure par boucle imbriquée. Cela signifie que l'ordre de jointure n'influence pas l'indexation. L'index DATE_VENTES peut être utilisé pour charger la table de hachage si l'ordre de jointure est inversé.

Remarque

Indexer une jointure de hachage est indépendant de l'ordre de jointure.

Une approche assez différente pour optimiser les performances des join­tures de hachage est de minimiser la taille de la table de hachage. Cette méthode fonctionne car une jointure de hachage optimale est seulement possible si la table de hachage entière tient en mémoire. Du coup, l'op­ti­mi­seur utilisera automatiquement le plus petit côté de la jointure pour la table de hachage. Le plan d'exécution Oracle affiche la mémoire estimée nécessaire dans la colonne « Bytes ». Dans le plan d'exécution ci-dessus, la table EMPLOYES nécessite neuf méga-octets et est du coup la plus petite.

Il est aussi possible de réduire la taille de la table de hachage en changeant la requête SQL, par exemple en ajoutant des conditions supplémentaires pour que la base de données charge moins d'enregistrements dans la table de hachage. En continuant l'exemple ci-dessus, cela signifie qu'il faut ajouter un filtre sur l'attribut DEPARTEMENT pour que seuls soient considérés les employés du service commercial. Ceci améliore les performances de la jointure par hachage même s'il n'y a pas d'index sur l'attribut DEPARTEMENT parce que la base de données n'a pas besoin de stocker les employés qui ne peuvent pas avoir de ventes dans la table de hachage. En faisant cela, vous devez vous assurer qu'il n'existe pas d'enregistrements dans VENTES pour les employés qui ne font pas partie du service commercial. Utilisez les contraintes pour vous en assurer.

Lors de la diminution de la table de hachage, le facteur déterminant n'est pas le nombre de lignes mais l'empreinte mémoire. En fait, il est même possible de réduire la taille de la table de hachage en sélectionnant moins de colonnes, pour n'avoir que les attributs dont vous avez besoin :

SELECT s.date_vente, s.valeur_eur
     , e.nom, e.prenom
  FROM ventes s
  JOIN employes e ON (s.id_supplementaire = e.id_supplementaire
                  AND s.id_employe        = e.id_employe)
 WHERE s.date_vente > trunc(sysdate) - INTERVAL '6' MONTH
Cette méthode présente rarement des bugs parce que supprimer la mau­vaise colonne résultera rapidement en un message d'erreur. Néanmoins, il est possible de diminuer considérablement la taille de la table de hachage. Dans ce cas particulier, elle passe de 9 Mo à 234 Ko, une réduction de 97%.
----------------------------------------------------------------
| Id | Operation                    | Name        | Bytes| Cost|
----------------------------------------------------------------
|  0 | SELECT STATEMENT             |             | 2067K| 2202|
|* 1 |  HASH JOIN                   |             | 2067K| 2202|
|  2 |   TABLE ACCESS FULL          | EMPLOYES    |  234K|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| VENTES      |  913K| 1724|
|* 4 |    INDEX RANGE SCAN          | DATE_VENTES |      |  133|
----------------------------------------------------------------

Astuce

Sélectionner moins de colonnes pour améliorer les performances de la jointure de hachage.

Bien qu'au premier regard, il semble simple de supprimer quelques colonnes à partir d'une requête SQL, cela se révèle un vrai challenge lors de l'utilisation d'un outil ORM. Le support des objets partiels est très peu fréquent. Les exemples suivants montrent certaines possibilités.
Java

JPA définit FetchType.LAZY dans l'annotation @Basic. Il peut être appliqué sur le niveau de propriété :

@Column(name="junk")
@Basic(fetch=FetchType.LAZY)
private String junk;

Les connecteurs JPA sont libres de l'ignorer :

La stratégie LAZY est un conseil donné à l'exécution au fournisseur, lui indiquant que les données peuvent être récupérées au coup par coup lors du premier accès. L'implémentation permet de récupérer les données une par une si la stratégie LAZY a été spécifiée.

EJB 3.0 JPA, paragraphe 9.1.18

Hibernate 3.6 implémente la récupération au coup par coup via l'instrumentation bytecode au moment de la compilation. L'instrumentation ajoute du code supplémentaire aux classes compilées qui ne récupère pas les propriétés LAZY jusqu'à leur accès. L'approche est complètement transparente à l'application mais cela laisse la porte ouverte à une nouvelle dimension du problème N+1 : une requête d'extraction (select) pour chaque enregistrement et pour chaque propriété. C'est tout particulièrement dangereux comme JPA n'offre pas le contrôle à l'exécution pour récupérer à l'avance si nécessaire.

Le langage de requête native d'Hibernate, appelé HQL, résout le problème avec la clause FETCH ALL PROPERTIES (voir FewerColumnsInstrumentedHibernate.java) :

select v from Ventes v FETCH ALL PROPERTIES
 inner join fetch v.employe e FETCH ALL PROPERTIES
 where v.dateVente >:dt
La clause FETCH ALL PROPERTIES force Hibernate à récupérer l'entité en avance, même lors de l'utilisation d'un code instrumenté et de l'annotation LAZY.

Une autre option est de charger seulement les options sélectionnées pour qu'il utilise les objets de transport des données (DTO) au lieu des entités. Cette méthode fonctionne de la même façon dans HQL et JP-QL, c'est-à-dire que vous initialisez un objet dans la requête (exemple FewerColumnsJPA.java) :

select new ParentVentesDTO(v.dateVente , v.valeurEur
                       ,e.prenom, e.nom)
  from Ventes v
  join v.employe e
 where v.dateVente > :dt
La requête sélectionne seulement les données demandées et renvoie un objet ParentVentesDTO, un simple objet Java (POJO), pas une entité.

Résoudre un vrai problème de performance implique souvent beaucoup de code existant. Migrer ce code dans de nouvelles classes n'est probablement pas raisonnable. Mais l'instrumentation en byte-code cause des problèmes N+1, qui est généralement pire que le problème de performances original. L'exemple FewerColumnsJPA.java utilise une interface commune pour l'entité et le DTO, ce qui résout le problème. L'interface définit seulement les méthodes de récupération (getter) pour qu'un consommateur en lecture seule peut facilement être modifié pour accepter le DTO en entrée. C'est souvent suffisant parce que les grosses jointures de hachage sont généralement utilisées en reportant les procédures qui ne mettent rien à jour.

Si vous construisez un nouveau rapport, vous pouvez penser à récupérer les données via DTO ou un simple Map, comme démontré dans l'exemple FewerColumnsHibernate.java.

Perl

L'outil DBIx::Class n'agit pas comme un gestionnaire d'entités, donc cet héritage ne cause pas des problèmes d'alias. Le manuel supporte cette approche. La définition suivante du schéma définit la classe Ventes sur deux niveaux :

package UseTheIndexLuke::Schema::Result::ParentVentes;
use base qw/DBIx::Class::Core/;

__PACKAGE__->table('ventes');
__PACKAGE__->add_columns(qw/id_vente   id_employe
                            id_supplementaire
                            date_vente valeur_eur/);
__PACKAGE__->set_primary_key(qw/id_vente/);
__PACKAGE__->belongs_to('employe', 'Employes', 
           {'foreign.id_employe'
            => 'self.id_employe'
           ,'foreign.id_supplementaire'
            => 'self.id_supplementaire'});

package UseTheIndexLuke::Schema::Result::Ventes;
use base qw/UseTheIndexLuke::Schema::Result::ParentVentes/;

__PACKAGE__->table('ventes');
__PACKAGE__->add_columns(qw/junk/);

La classe Ventes est dérivée de la classe ParentVentes et ajoute l'attribut manquant. Vous pouvez utiliser les deux classes si besoin. Notez que la configuration de la table est requise aussi dans la classe dérivée.

Vous pouvez récupérer tous les employés avec la lecture en avance ou simplement sélectionner les colonnes comme indiqué ci-dessous :

my @ventes =
   $schema->resultset('ParentVentes')
          ->search($cond
                  ,{      join => 'employe'
                   ,'+columns' => ['employe.prenom'
                                  ,'employe.nom']
                   }
                  );

Il n'est pas possible de charger seulement les colonnes sélectionnées à partir de la table parent, ParentVentes dans ce cas.

DBIx::Class 0.08192 génère la requête SQL suivante. Elle récupère toutes les colonnes de la table VENTES et les attributs sélectionnés à partir d'EMPLOYES :

SELECT me.id_vente,
       me.id_employe,
       me.id_supplementaire,
       me.date_vente,
       me.valeur_eur,
       employe.prenom,
       employe.nom
  FROM sales me
  JOIN employes employe
        ON ( employe.id_employe        = me.id_employe
       AND   employe.id_supplementaire = me.id_supplementaire)
 WHERE(date_vente > ?)
PHP

La version 2 de l'outil Doctrine supporte la sélection des attributs à l'exécution. La documentation indique que les objets partiellement chargés pourraient se comporter bizarrement et requièrent le mot-clé partial pour accepter les risques. De plus, vous devez sélectionner explicitement les colonnes de la clé primaire :

$qb = $em->createQueryBuilder();
$qb->select('partial v.{id_vente, date_vente, valeur_eur},'
          . 'partial e.{employee_id, id_supplementaire, '
                     . 'prenom , nom}')
   ->from('Ventes', 'v')
   ->join('v.employe', 'e')
   ->where("v.date_vente > :dt")
   ->setParameter('dt', $dt, Type::DATETIME);

La requête SQL générée contient les colonnes demandées ainsi que les colonnes ID_SUPPLEMENTAIRE et ID_EMPLOYE provenant de la table VENTES.

SELECT v0_.id_vente          AS id_vente0,
       v0_.date_vente        AS date_vente1,
       v0_.valeur_eur        AS valeur_eur2,
       e1_.id_employe        AS id_employe3,
       e1_.id_supplementaire AS id_supplementaire4,
       e1_.prenom            AS prenom5,
       e1_.nom               AS nom6,
       v0_.id_supplementaire AS id_supplementaire7,
       v0_.id_employe        AS id_employe8
  FROM ventes v0_
 INNER JOIN employes e1_
         ON v0_.id_supplementaire = e1_.id_supplementaire
        AND v0_.id_employe        = e1_.id_employe
 WHERE v0_.date_vente > ?

Les objets renvoyés sont compatibles avec des objets complètement chargés mais les colonnes manquantes ne sont pas renseignées. Y accéder ne déclenche pas une exception.

Attention

MySQL ne connaît pas les jointures par hachage (il s'agit de la demande de fonctionnalité 2241).

Facts

  • Les jointures par hachage n'ont pas besoin d'index sur les prédicats de jointure. À la place, elles utilisent une table de hachage.

  • Une jointure par hachage utilise les index seulement si un index est disponible pour les prédicats indépendants.

  • Réduisez la taille de la table de hachage pour améliorer les performances, soit horizontalement (moins de lignes) soit verticalement (moins de colonnes).

  • Les jointures de hachage ne peuvent pas être utilisées sur des conditions d'intervalle dans les prédicats de jointure (jointures theta).

À propos de l'auteur

Photo de Markus Winand

Markus Winand teaches efficient SQL—inhouse and online. He minimizes the development time using modern SQL and optimizes the runtime with smart indexing—for that he also published the book SQL Performance Explained.

Livre de Markus

Couverture du livre « SQL : Au cœur des performances »

L'essence de SQL tuning dans 200 pages.

Acheter de Markus
(Livre de poche et PDF)

Achetez chez Amazon
(Seulement en poche)

“Use The Index, Luke!” by Markus Winand and translated by Guillaume Lelarge is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
Mentions légales | Contact | NO WARRANTY | Marque déposée | Privacy | CC-BY-NC-ND 3.0 license