Merge Join
Une jointure par fusion requiert que les deux tables soient triées sur la colonne de jointure, puis parcourt et fusionne synchronement les lignes correspondantes ; adaptée aux données triées ou aux jointures après tri.
Objectif
Comprendre l'algorithme efficace des jointures ordonnées et analyser le compromis avec les coûts de tri.
Mécanisme
Après tri des deux tables sur la colonne de jointure, on parcourt synchronement en comparant les lignes courantes : égales, on émet une correspondance ; la plus petite avance. Complexité O(N+M), mais le tri coûte O(N log N + M log M). Avec des index triés, le tri est gratuit — très efficace.
Cas d’usage
- Optimisation de jointures ordonnées
- Choix d'algorithme de jointure
- Analyse de plans d'exécution