Dans cet article nous allons voir comment la jointure la plus basique fonctionne : le "nested loop" où en français la boucle imbriquée.

SQL nécessitant une boucle imbriquée

Cette jointure apparait généralement lorsque 2 tables sont lues et que l'une des deux ensembles ont beaucoup moins de lignes que la seconde.
Je change vos habitudes et vous propose le SQL suivant qui va demander un nested loop.
SQL de nested loop

Cette requête génère le plan suivant:
Nested_loops.png

Pour l'exemple, je ne fais pas de jointure entre 2 tables mais sur 2 éléments de la même table Person :

  • Un sous-ensemble extrait de l'index IX_Person_LastName_FirtsName_MiddleName (where MiddleName like 'B%')
  • La table personne entière pour récupérer tous les champs (select *) via l'index Cluster PK_Person...

Nous avons donc 2 ensembles à joindre selon la clé BusinessEntityID qui est la PK de la table. Un des 2 sous-ensembles (l'index IX) est beaucoup plus petit que le second (toute la table).

Algorithme du Nested Loop


var ensemble1;
var ensemble2;
var match = empty;
for (element1 in ensemble1)
{
..for (element2 in ensemble2)
..{
....if (element1 == element2) then match += element1+element2;
..}
}

La boucle principale passe tous les éléments du 1er ensemble (le plus petit des deux) et la seconde boucle tous les éléments du second ensemble.

Représentation schématique

Avantages et limites du Nested loop

Cette boucle est performante dans le cas où l'un au moins des 2 ensembles à joindre est petit.
En effet, dans ce un cas ou il n'y aurait que 3 lignes, la boucle principale ne serait parcourue que 3 fois et donc le second élément lui aussi 3 fois. Le problème se pose lorsque les 2 ensembles sont importants (>100 lignes) puisque dans un tel cas le sous-ensemble imbriqué sera parcouru autant de fois...
Cas particulier : lors de jointures type CROSS JOIN ou CARTESIAN JOIN sur Oracle, cette boucle est obligatoire puisqu'elle génère toutes les lignes demandées (pour chacune des lignes de l'ensemble 1 un lien à toutes les lignes de l'ensemble 2).