Algorithmes de jointure

Les algorithmes de jointure sont les méthodes physiques — jointure par boucles imbriquées, jointure par tri-fusion et jointure par hachage — qui combinent des tuples de deux relations ou plus selon une condition de jointure, et ils constituent généralement les opérateurs les plus critiques en termes de performance dans un plan de requête.

Definition

Un algorithme de jointure est un opérateur physique qui calcule la jointure de deux relations sur un prédicat en appariant systématiquement les tuples qui satisfont la condition, en utilisant l'itération imbriquée, la fusion triée ou le hachage pour trouver efficacement les tuples correspondants.

Scope

Ce sujet couvre les principaux algorithmes pour l'évaluation des jointures : les jointures par boucles imbriquées simples, par blocs et par index ; la jointure par tri-fusion et sa synergie avec des entrées déjà triées ; et la jointure par hachage, y compris les variantes grace et hybride qui gèrent les entrées plus grandes que la mémoire. Il analyse leur coût d'E/S et leurs exigences en mémoire, ainsi que les conditions dans lesquelles chacun est préféré. Il exclut l'énumération des ordres de jointure par l'optimiseur, qui est traitée dans le cadre de l'optimisation de requêtes basée sur les coûts.

Core questions

• En quoi les jointures par boucles imbriquées, par tri-fusion et par hachage diffèrent-elles en termes d'approche et de coût ?
• Quand une jointure par boucles imbriquées avec index surpasse-t-elle les alternatives ?
• Comment les jointures par hachage grace et hybride gèrent-elles les entrées plus grandes que la mémoire ?
• Comment le coût d'E/S de chaque méthode de jointure est-il analysé en termes de pages et de passes ?
• Quelle condition de jointure (égalité versus inégalité) chaque algorithme requiert-il ?

Key concepts

• jointure par boucles imbriquées
• jointure par boucles imbriquées par blocs
• jointure par boucles imbriquées avec index
• jointure par tri-fusion
• jointure par hachage
• jointure par hachage grace et hybride
• équijointure versus thêta-jointure
• analyse du coût d'E/S

Key theories

Jointures par boucles imbriquées

Pour chaque tuple d'une relation, l'algorithme scanne l'autre pour trouver des correspondances ; la jointure par boucles imbriquées par blocs réduit les E/S en mettant en tampon des pages, et la jointure par boucles imbriquées avec index remplace le balayage interne par une recherche d'index lorsqu'un est disponible, la rendant efficace pour les jointures sélectives.

Jointure par tri-fusion

Les deux entrées sont triées sur l'attribut de jointure puis fusionnées en une seule passe coordonnée ; elle est particulièrement intéressante lorsque les entrées sont déjà triées ou lorsque la sortie doit être triée, et elle gère efficacement les jointures par égalité.

Jointure par hachage

Une jointure par égalité est calculée en construisant une table de hachage en mémoire sur la relation la plus petite et en la sondant avec la plus grande ; les variantes grace et hybride partitionnent les deux entrées sur disque lorsqu'elles dépassent la mémoire, offrant de solides performances pour les grandes équijointures.

Clinical relevance

Les jointures dominent le coût des requêtes analytiques et de reporting qui combinent plusieurs tables ; ainsi, le choix de l'algorithme de jointure — souvent la décision la plus importante dans un plan — détermine si de telles requêtes sont interactives ou prennent des heures, rendant ces algorithmes centraux pour la performance des bases de données.

History

Les jointures par tri-fusion et par boucles imbriquées remontent aux premiers systèmes relationnels. La jointure par hachage et ses variantes grace et hybride ont été développées dans les années 1980, notamment dans la recherche sur les bases de données parallèles, et il a été montré qu'elles surpassaient le tri-fusion pour de nombreuses grandes équijointures. L'étude de Graefe de 1993 a consolidé l'analyse de ces algorithmes que les manuels de bases de données suivent encore.

Key figures

• Goetz Graefe
• David DeWitt

Seminal works

• graefe1993
• garciamolina2008

Frequently asked questions

Quel algorithme de jointure est le plus rapide ?

Cela dépend des entrées. La jointure par hachage est généralement la meilleure pour les grandes équijointures lorsque aucune des entrées n'est triée ; le tri-fusion l'emporte lorsque les entrées sont déjà triées ou que la sortie doit être ordonnée ; et la jointure par boucles imbriquées avec index est la meilleure lorsqu'une entrée est petite et que l'autre possède un index sélectif sur la colonne de jointure. L'optimiseur choisit en fonction du coût estimé.

Pourquoi la jointure par hachage ne peut-elle pas gérer les conditions d'inégalité ?

La jointure par hachage regroupe les tuples par le hachage de la clé de jointure de sorte que seuls les tuples avec des clés égales atterrissent dans le même compartiment (bucket). Cela fonctionne pour les conditions d'égalité (équijointure) mais pas pour les inégalités comme 'inférieur à', qui nécessitent de comparer des tuples entre différents compartiments — celles-ci sont plutôt gérées par des méthodes de type boucles imbriquées ou tri-fusion.