DBA Olivier Berthommé

Les prérequis à un merge Join

Cette jointure ne fonctionne qu'avec 2 ensembles triés selon la clé de jointure. Il n'est pas possible autrement.
Attention, Oracle, appelle dans la littérature cette jointure "Sort Merge Join". Cela indique bien qu'il faut trier les données et comme ce n'est généralement pas le cas sur Oracle, ce tri est un surcoût à l'opérateur de jointure lui-même.

Quel SQL pour une jointure Merge Join ?

Une fois n'est pas coutume, je vous donne un exemple avec SQL Server. La même jointure existe sur Oracle mais vous allez voir qu'elle est plus souvent utilisée sous SQL Server du fait des prérequis.

Et son plan d'exécution généré :


On peut voir que les 2 ensembles de la requête sont triés selon la clé de jointure :

• Les 2 tables sont des clustered indexes donc les données sont organisées en B+Tree selon la Primary Key (BusinessEntityID)
• La jointure de la requête (INNER JOIN) se fait sur BusinessEntityID
  

Sous SQL Server, lorsqu'une table est créée, qu'elle possède une PK et qu'aucune instruction ne précise le contraire (pas d'instruction NONCLUSTERED), elle sera stockée en B+Tree ; donc triée sur disque.
C'est cette configuration de stockage par défaut qui rend les Merge Join si souvent utilisables avec SQL Server.
Sous Oracle, les tables sont créées par défaut en Heap (= NONCLUSTERED) et ne sont pas ordonnées ; l'optimiseur n'utilise le Merge Join que si une étape de tri est effectuée (ou qu'il accède aux données par un B-Tree).

Algorithme de jointure

Avec 2 ensembles triés selon la clé de jointure, la fusion est beaucoup plus performante. Voici en pseudo-algorithme le principe du Merge-Join:

var ensemble1;
var ensemble2;
var match = empty;
while ( ensemble1 not empty AND ensemble2 not empty )
{
..element1 = ensemble1.next;
..element2 = ensemble2.next;
..if (element1.key == element2.key)
....then
......match += element1+element2;
......element1 = ensemble1.next;
....else
......if (element1.key > element2.key)
........then element2 = ensemble2.next;
........else element1 = ensemble1.next;
......endif;
..endif
}

Les points notables par rapport au Nestead Loop :

• Les 2 ensembles sont lu maximum une fois chacun
• Dès que l'un ou l'autre a été parcouru totalement, la jointure est finie
• Lorsqu'il n'y a pas de correspondance, on prend l'élément suivant de l'ensemble dont la clé est la plus petite

Améliorations avec les B-Tree

L'algorithme dans les SGBDR est bien plus performant que celui décrit ci-dessous. Il utilise notamment les bornes (min-max) des branches (éléments fils d'un noeud).
Grâce à cette connaissance, le moteur est capable de ne pas parcourir certaines sous-branches si elles sont inutiles : lorsque le max d'une branche du premier ensemble et strictement supérieur au min d'une branche du second ensemble, il ne peut pas y avoir de correspondance. C'est ce qu'on appelle l'élagage ; en anglais "pruning". Dans certains cas, cet élagage permet d'éliminer de nombreuses lectures.
Note : le parcours des arbres se fait en Depth-first et peut être lu dans l'ordre croissant ou décroissant de clé selon le résultat attendu.

Représentation schématique

Avantages et limites du Merge Join

Vous l'avez compris, le gros défaut de cet algorithme de jointure est ses prérequis : les 2 ensembles à fusionner doivent être triés selon la clé de jointure. C'est pour cela qu'Oracle parle dans ses documents de "Sort Merge Join".
L'avantage énorme de cette fusion est son efficacité lorsque les 2 ensembles sont importants et que le résultat de fusion est faible. Dans ce cas, il va y avoir de nombreux élagages et les parcours des arbres seront très simplifiés.
Note : Le tri est conservé par la jointure ; si le résultat doit être trié (clause ORDER BY), c'est un avantage non négligeable.