par Guillaume Lelarge.

Fusion par tri


La jointure « sort-merge » combine deux listes triées comme une fermeture éclair. Les deux côtés de la jointure doivent être triés par les prédicats de jointure.

Une jointure « sort-merge » a besoin des mêmes index que la jointure par hachage, autrement dit un index sur les conditions indépendantes pour lire tous les enregistrements candidats d'un coup. L'indexation des prédicats de jointure est inutile. Cela ressemble à une jointure par hachage pour l'instant. Néanmoins, il y a un aspect unique à ce type de jointure : la symétrie absolue. L'ordre de jointure ne fait aucune différence, même pas au niveau des performances. Cette propriété est très utile pour les jointures externes. Pour les autres algorithmes, la direction des jointures externes (gauche ou droite) impose l'ordre de jointure, mais pas pour les jointures par fusion. La jointure par fusion peut même faire une jointure externe gauche ou droite en même temps. Cela s'appelle une jointure externe complète, comme indiqué dans l'animation suivante.

Figure 4.1 Jointure « sort-merge » (par fusion) exécutant un FULL OUTER JOIN

Bien que la jointure par fusion est plutôt performante une fois que les éléments en entrée sont triés, elle est rarement utilisée car le tri de chaque côté coûte cher. D'un autre côté, la jointure par hachage a besoin de ne prétraiter qu'un seul côté.

La force d'une jointure par fusion apparaît immédiatement si les entrées sont déjà triées. Il est possible d'exploiter l'ordre d'un index pour éviter le tri manuel. Le Chapitre 6, « Trier et grouper » explique ce concept en détail. Néanmoins, l'algorithme de jointure par hachage est supérieur dans bien des cas.

Facts

  • Les jointures par fusion n'ont pas besoin d'index sur les prédicats de jointure.

  • MySQL ne dispose pas des jointures par fusion.

À propos de l'auteur

Photo de Markus Winand

Markus Winand teaches efficient SQL—inhouse and online. He minimizes the development time using modern SQL and optimizes the runtime with smart indexing—for that he also published the book SQL Performance Explained.

Livre de Markus

Couverture du livre « SQL : Au cœur des performances »

L'essence de SQL tuning dans 200 pages.

Acheter de Markus
(Livre de poche et PDF)

Achetez chez Amazon
(Seulement en poche)

“Use The Index, Luke!” by Markus Winand and translated by Guillaume Lelarge is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
Mentions légales | Contact | NO WARRANTY | Marque déposée | Privacy | CC-BY-NC-ND 3.0 license