Les jointures : Le Merge Join
Par Olivier le lundi 11 mai 2015, 18:00 - Lien permanent
Continuons notre analyse des jointures avec
aujourd'hui le merge join. Cette jointure est la plus efficace mais nécessite
certains prérequis. Voyons en détails comment elle fonctionne.
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.