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
temporaire 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 confirme 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
jointures 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'optimiseur 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
----------------------------------------------------------------
| 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.
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
(voirFewerColumnsInstrumentedHibernate.java
) :select v from Ventes v FETCH ALL PROPERTIES inner join fetch v.employe e FETCH ALL PROPERTIES where v.dateVente >:dt
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
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'exempleFewerColumnsHibernate.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 classeParentVentes
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
etID_EMPLOYE
provenant de la tableVENTES
.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 a introduit la jointure par hachage à partir de la version 8.0.18 en 2019.
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).