Boucles imbriquées

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 = ?

Par défaut, les ORM ne génèrent pas des jointures SQL. À la place, elles exécutent une requête sur la table 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> dans App.config ou hibernate.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éthode Root<>.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

Exemples complets en Java, Perl et PHP [ZIP]
Requêtes CREATE et INSERT pour les exemples
Article : « Latency: Security vs. Performance » sur les latences réseaux et les applications SQL.

À propos de l'auteur

Markus Winand est l’ambassadeur de la renaissance SQL. Il a pour mission d’initier les développeurs à l’évolution du SQL au 21ème siècle. Markus peut être engagé comme formateur, conférencier et consultant chez winand.at.

Boucles imbriquées

Activer la trace des requêtes SQL

Astuce

Attention

Astuce

Liens

À propos de l'auteur

Table des matières

Latest Blog Posts

Entrer en contact avec Markus Winand

Boucles imbriquées

Activer la trace des requêtes SQL

Astuce

Attention

Astuce

Liens

À propos de l'auteur

Livre de Markus

Table des matières

Latest Blog Posts

Entrer en contact avec Markus Winand