La jointure par boucle imbriquée est l'algorithme de jointure le plus évident. Il fonctionne en utilisant des requêtes imbriquées : la requête externe pour récupérer les résultats d'une table et la deuxième requête pour chaque ligne provenant de la première requête, pour récupérer les données correspondantes dans l'autre table.
En fait, vous pouvez utiliser des extractions imbriquées pour implémenter vous-même l'algorithme des boucles imbriquées. Néanmoins, ce n'est pas recommandé car les latences réseau s'ajoutent aux latences des disques, ce qui aboutit à un temps de réponse encore pire. Les extractions imbriquées sont toujours très fréquentes car elles sont faciles à faire, même sans s'en rendre compte. Les ORM « aident » très souvent à obtenir ce type de comportement, au point que le problème d'extraction N+1 y a gagné sa très mauvaise notoriété.
Les exemples suivants montrent des exemples de requêtes imbriquées
accidentelles produits par différents ORM. Les exemples recherchent les
employés dont le nom commence par 'WIN'
et récupèrent toutes
les ventes (dans la table VENTES
) pour ces employés.
- Java
L'exemple JPA utilise l'interface CriteriaBuilder.
CriteriaBuilder constructeurRequete = em.getCriteriaBuilder(); CriteriaQuery<Employes> requete = constructeurRequete.createQuery(Employes.class); Root<Employes> r = requete.from(Employes.class); requete.where( constructeurRequete.like( constructeurRequete.upper(r.get(Employes_.nom)), "WIN%" ) ); List<Employes> emp = em.createQuery(requete).getResultList(); for (Employes e: emp) { // traitement d'un employe for (Ventes s: e.getVentes()) { // traitement des ventes pour cet employe } }
Hibernate JPA 3.6.0 génère des requêtes d'extraction (
select
) N+1 :select employes0_.id_supplementaire as supplementaire1_0_ -- AUTRES COLONNES from employes employes0_ where upper(employes0_.nom) like ? select ventes0_.id_supplementaire as supplementaire4_0_1_ -- AUTRES COLONNES from ventes ventes0_ where ventes0_.id_supplementaire=? and ventes0_.id_employe=? select ventes0_.id_supplementaire as supplementaire4_0_1_ -- AUTRES COLONNES from ventes ventes0_ where ventes0_.id_supplementaire=? and ventes0_.id_employe=?
- Perl
L'exemple Perl suivant utilise l'outil DBIx::Class :
my @employes = $schema->resultset('Employes') ->search({'UPPER(nom)' => {-like=>'WIN%'}}); foreach my $employe (@employes) { # traitement d'un employe foreach my $vente ($employe->ventes) { # traitement des ventes pour cet employe } }
DBIx::Class 0.08192 génère des requêtes d'extraction (
select
) N+1 :SELECT me.id_employe, me.id_supplementaire , me.nom, me.prenom, me.date_de_naissance FROM employes me WHERE ( UPPER(nom) LIKE ? ) SELECT me.id_vente, me.id_employe, me.id_supplementaire , me.date_vente, me.valeur_eur FROM ventes me WHERE ( ( me.id_employe = ? AND me.id_supplementaire = ? ) ) SELECT me.id_vente, me.id_employe, me.id_supplementaire , me.date_vente, me.valeur_eur FROM ventes me WHERE ( ( me.id_employe = ? AND me.id_supplementaire = ? ) )
- PHP
L'exemple Doctrine utilise l'interface du constructeur de requêtes :
$qb = $em->createQueryBuilder(); $qb->select('e') ->from('Employes', 'e') ->where("upper(e.nom) like :nom") ->setParameter('nom', 'WIN%'); $r = $qb->getQuery()->getResult(); foreach ($r as $ligne) { // traitement d'un employe foreach ($ligne->getVentes() as $vente) { // traitement des ventes pour cet employe } }
Doctrine 2.0.5 génère des requêtes d'extraction (
select
) N+1 :SELECT e0_.id_employe AS id_employe0 -- AUTRES COLONNES FROM employes e0_ WHERE UPPER(e0_.nom) LIKE ? SELECT t0.id_vente AS ID_VENTE1 -- AUTRES COLONNES FROM ventes t0 WHERE t0.id_supplementaire = ? AND t0.id_employe = ? SELECT t0.id_vente AS ID_VENTE1 -- AUTRES COLONNES FROM ventes t0 WHERE t0.id_supplementaire = ? AND t0.id_employe = ?
VENTES
avec des extractions imbriquées. L'effet est connu sous le nom de «
problème d'extractions N+1 » ou, plus court, « problème N+1 » car cela cause l'exécution de N+1 extractions au total si
la première requête renvoie N lignes.Activer la trace des requêtes SQL
Activer la trace des requêtes SQL pendant le développement et vérifier les requêtes SQL générées.
- DBIx::Class
export DBIC_TRACE=1
dans votre shell.- Doctrine
Uniquement possible au niveau du code source... n'oubliez pas de le désactiver en production. Pensez à développer votre propre traceur configurable.
$logger = new \Doctrine\DBAL\Logging\EchoSqlLogger; $config->setSQLLogger($logger);
- Hibernate (native)
<property name="show_sql">true</property>
dansApp.config
ouhibernate.cfg.xml
- JPA
Dans
persistence.xml
mais dépendant du connecteur JPA (par exemple pour eclipselink, Hibernate et OpenJPA) :<property name="eclipselink.logging.level" value="FINE"/> <property name="hibernate.show_sql" value="TRUE"/> <property name="openjpa.Log" value="SQL=TRACE"/>
La plupart des ORM propose un moyen automatique pour activer la trace des requêtes SQL. Malheureusement, cela inclut le risque de déployer accidentellement ce paramètre en production.
Même si l'approche des extractions imbriquées est mauvaise, elle
explique bien la jointure par boucle imbriquée. La
base de données exécute la jointure exactement comme les outils ORM
ci-dessus. L'utilisation d'un index pour une jointure par boucle imbriquée
est exactement la même que pour les requêtes select
montrées ci-dessus. Il est nécessaire d'avoir un index fonctionnel sur la table
EMPLOYES
et un index
concaténé pour les prédicats de la jointure sur la table
VENTES
:
CREATE INDEX emp_nom_maj ON employes (UPPER(nom));
CREATE INDEX ventes_emp ON ventes (id_supplementaire, id_employe);
Néanmoins, une jointure SQL est toujours plus efficace que les requêtes d'extraction imbriquées, même si des index identiques sont utilisés, car cette méthode évite beaucoup de communication réseau. Il est même plus rapide lorsque la quantité totale de données transférées est plus importante à cause de la duplication des attributs des employés pour chaque vente. Ceci est dû aux deux dimensions des performances : le temps de réponse et la bande passante. La bande passante a un impact mineur sur le temps de réponse mais les latences ont un impact énorme. Cela signifie que le nombre d'allers/retours vers la base de données est plus important pour le temps de réponse que la quantité de données réellement transférées.
Astuce
Exécutez les jointures dans la base de données.
La plupart des outils ORM proposent une façon de créer des
jointures SQL. Le mode de chargement à l'avance (eager
fetching) est probablement le plus intéressant. Il se
configure généralement au niveau des propriétés dans les correspondances
de l'entité (par exemple pour la propriété employes
dans la
classe Ventes
). L'outil ORM fera ensuite toujours la jointure
avec la table EMPLOYES
lors de l'accès à la table
VENTES
. Configurer le chargement à l'avance n'a de sens que
si vous avez toujours besoin des détails de l'employé quand vous regardez
les données de ventes.
Par contre, le chargement à l'avance est contre-performant si vous
n'avez pas besoin des enregistrements enfants à chaque fois que vous
accédez à l'objet parent. Pour une application annuaire, charger les
enregistrements de la table VENTES
lors de l'affichage des
informations sur l'employé n'a pas de sens. Vous pourriez avoir besoin des
données relatives aux ventes dans d'autres cas, mais pas toujours. Une
configuration statique n'est pas la solution.
Pour des performances optimales, vous devez regagner le contrôle sur les jointures. Les exemples suivants vous montrent comment obtenir une grande flexibilité sur le contrôle du comportement des jointures à l'exécution.
- Java
L'interface JPA
CriteriaBuilder
fournit la méthodeRoot<>.fetch()
pour contrôler les jointures. Cela vous permet de spécifier quand et comment joindre les objets indiqués dans la requête principale. Dans cet exemple, nous utilisons une jointure gauche pour récupérer tous les employés même si certains n'ont pas fait de ventes.Attention
JPA et Hibernate renvoient les employés pour chaque vente.
Cela signifie qu'un employé ayant 30 ventes apparaîtra 30 fois. Bien que cela soit très perturbant, c'est le comportement attendu (persistence EJB 3.0, paragraphe 4.4.5.3 “Fetch Joins”). Vous pouvez dé-dupliquer la relation parente ou utiliser la fonction
distinct()
comme indiqué dans l'exemple ci-dessous.CriteriaBuilder qb = em.getCriteriaBuilder(); CriteriaQuery<Employes> requete = qb.createQuery(Employes.class); Root<Employes> r = requete.from(Employes.class); requete.where(qb.like( qb.upper(r.get(Employes_.nom)), "WIN%") ); r.fetch("ventes", JoinType.LEFT); // necessaire pour eviter la duplication des // enregistrements Employe requete.distinct(true); List<Employes> emp = em.createQuery(requete).getResultList();
Hibernate 3.6.0 génère la requête SQL suivante :
select distinct employes0_.id_supplementaire as supplementaire1_0_0_ , employes0_.id_employe as employe2_0_0_ -- AUTRES COLONNES , ventes1_.id_vente as vente1_0__ from employes employes0_ left outer join ventes ventes1_ on employes0_.id_supplementaire=sales1_.id_supplementaire and employes0_.id_employe=sales1_.id_employe where upper(employes0_.nom) like ?
La requête a bien la jointure gauche attendue mais contient aussi un mot-clé
distinct
inutile. Malheureusement, JPA ne fournit pas d'appels API séparés pour filtrer les enregistrements parents dupliqués sans en même temps dé-dupliquer les enregistrements enfants. Le mot-clédistinct
dans une requête SQL est alarmant car la plupart des bases de données vont filtrer d'eux-mêmes les enregistrements dupliqués. Seulement quelques bases de données se rappellent que les clés primaires garantissent l'unicité dans ce cas.L'API native Hibernate résout le problème du côté client en utilisant un transformateur d'ensembles de résultats :
Criteria c = session.createCriteria(Employes.class); c.add(Restrictions.ilike("nom", 'Win%')); c.setFetchMode("ventes", FetchMode.JOIN); c.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY); List<Employes> result = c.list();
Cela génère la requête suivante :
select this_.id_supplementaire as supplementaire1_0_1_ , this_.id_employe as employe2_0_1_ -- AUTRES COLONNES this_ sur employes , ventes2_.id_vente as vente1_3_ -- AUTRES COLONNES ventes2_ sur ventes from employes this_ left outer join ventes ventes2_ on this_.id_supplementaire=sales2_.id_supplementaire and this_.id_employe=ventes2_.id_employe where lower(this_.nom) like ?
Cette méthode produit un SQL propre sans clause inattendue. Notez que Hibernate utilise
lower
pour les requêtes de recherche insensible à la casse, un détail important pour la construction d'index fonctionnels.- Perl
L'exemple suivant utilise l'outil DBIx::Class de Perl :
my @employes = $schema->resultset('Employes') ->search({ 'UPPER(nom)' => {-like => 'WIN%'} , {prefetch => ['ventes']} });
DBIx::Class 0.08192 génère la requête SQL suivante :
SELECT me.id_employe, me.id_supplementaire, me.nom -- AUTRES COLONNES FROM employes me LEFT JOIN ventes ventes ON (sales.id_employe = me.id_employe AND sales.id_supplementaire = me.id_supplementaire) WHERE ( UPPER(nom) LIKE ? ) ORDER BY ventes.id_employe, ventes.id_supplementaire
Notez la clause
order by
. Ce n'était pas demandé par l'application. La base de données doit trier l'ensemble de résultats et cela peut prendre du temps.- PHP
L'exemple suivant utilise l'outil Doctrine de PHP :
$qb = $em->createQueryBuilder(); $qb->select('e,s') ->from('Employes', 'e') ->leftJoin('e.ventes', 's') ->where("upper(e.nom) like :nom") ->setParameter('nom', 'WIN%'); $r = $qb->getQuery()->getResult();
Doctrine 2.0.5 génère la requête SQL suivante :
SELECT e0_.id_employe AS id_employe0 -- AUTRES COLONNES FROM employes e0_ LEFT JOIN ventes s1_ ON e0_.id_supplementaire = s1_.id_supplementaire AND e0_.id_employe = s1_.id_employe WHERE UPPER(e0_.nom) LIKE ?
Le plan d'exécution affiche l'opération NESTED LOOPS
OUTER
:
---------------------------------------------------------------
|Id |Operation | Name | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT | | 822 | 38 |
| 1 | NESTED LOOPS OUTER | | 822 | 38 |
| 2 | TABLE ACCESS BY INDEX ROWID| EMPLOYES | 1 | 4 |
|*3 | INDEX RANGE SCAN | EMP_NOM_MAJ | 1 | |
| 4 | TABLE ACCESS BY INDEX ROWID| VENTES | 821 | 34 |
|*5 | INDEX RANGE SCAN | VENTES_EMP | 31 | |
---------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - access(UPPER("NOM") LIKE 'WIN%')
filter(UPPER("NOM") LIKE 'WIN%')
5 - access("E0_"."ID_SUPPLEMENTAIRE"="S1_"."ID_SUPPLEMENTAIRE"(+)
AND "E0_"."ID_EMPLOYE" ="S1_"."ID_EMPLOYE"(+))
Astuce
Connaissez votre ORM et gagnez le contrôle sur les jointures.
Les différents outils ORM offrent différentes façons de contrôler le comportement des jointures. La récupération en avance est un premier exemple de ce qui est possible de faire, même si tous les ORM ne le proposent pas. Une bonne pratique est d'implémenter quelques exemples qui explorent les capacités de votre ORM. Cela peut aussi servir de référence lors du développement et vous montrera des facettes inattendues du comportement de l'ORM, comme la duplication des enregistrements parents lors de l'utilisation de jointure. Téléchargez les exemples pour commencer.
La jointure par boucle imbriquée offre de bonnes performances si la première requête renvoie un petit ensemble de résultats. Sinon, l'optimiseur pourrait choisir un autre algorithme de jointure, comme la jointure par hachage décrite dans la prochaine section mais ceci n'est possible que si l'application utilise une jointure pour indiquer à la base les données dont elle a réellement besoin.
Liens
Requêtes
CREATE
etINSERT
pour les exemplesArticle : « Latency: Security vs. Performance » sur les latences réseaux et les applications SQL.