Algorithmes de jointure : boucle imbriquée, hachage, fusion

Vous connaissez déjà INNER JOIN en tant que syntaxe. Lors d'un entretien de niveau senior, les recruteurs demandent comment la base de données exécute physiquement une jointure. Il existe trois algorithmes :

• Jointure par boucles imbriquées
• Jointure par hachage
• Jointure par fusion (fusion après tri)

Le type de jointure logique (INNER, LEFT) est indépendant de l'algorithme. Le planificateur choisit l'algorithme en fonction de la taille des tables, des index et de l'ordre de tri. Comprendre dans quels cas chacun est le plus efficace constitue le cœur de cette leçon.

La boucle imbriquée est la méthode la plus simple : pour chaque ligne de la table externe, le système parcourt la table interne à la recherche de correspondances. En pseudocode, il s'agit de deux boucles, l'une à l'intérieur de l'autre.

Naïvement, sa complexité est O(outer * inner), ce qui est désastreux pour les tables volumineuses. Mais elle devient excellente lorsque le côté interne possède un index sur la clé de jointure : chaque ligne externe déclenche une recherche peu coûteuse dans l'index au lieu d'un parcours complet de la table interne.

C'est la méthode préférée du planificateur lorsque la table externe est petite et que la colonne de jointure interne est indexée.

L'indice révélateur d'une boucle imbriquée est la présence de loops sur le nœud interne. L'exemple affiche loops=3 parce que le côté externe a produit 3 lignes : le parcours de l'index interne a donc été exécuté 3 fois.

Le danger apparaît lorsque le côté externe est volumineux. S'il produit 2 millions de lignes, le côté interne s'exécute 2 millions de fois. Même une recherche rapide de 0,01 ms finit alors par prendre 20 secondes.

Lors d'un entretien, signalez toute boucle imbriquée dont la valeur de loops est élevée sur une table interne dépourvue d'un bon index : c'est la requête lente.

La jointure par hachage est adaptée aux grandes tables non triées. Elle se déroule en deux phases :

• Construction : lire la plus petite table et la charger dans une table de hachage en mémoire, indexée par la colonne de jointure.
• Sondage : parcourir la grande table ; pour chaque ligne, hacher la clé de jointure et la rechercher dans la table de hachage.

Chaque table n'est lue qu'une seule fois, ce qui donne approximativement O(outer + inner). Aucun index ni entrée triée n'est nécessaire, ce qui explique pourquoi cette méthode domine les grandes jointures analytiques fondées sur des conditions d'égalité.

Vous devez mentionner deux points à propos des jointures par hachage :

• Elles ne fonctionnent qu'avec des conditions de jointure fondées sur l'égalité (a.id = b.id). Une condition d'intervalle comme a.x < b.y ne peut pas utiliser une jointure par hachage.
• Le côté utilisé pour la construction doit tenir dans work_mem. Si ce n'est pas le cas, Postgres écrit des lots sur le disque (vous verrez Batches: > 1 et une utilisation du disque), ce qui ralentit fortement la jointure.

Ainsi, une jointure par hachage dont le côté de construction est gigantesque et dont work_mem est minuscule constitue un véritable problème de performances à signaler en situation réelle.

La jointure par fusion (fusion après tri) exige que les deux entrées soient triées selon la clé de jointure. Elle les parcourt ensuite simultanément, comme lors de la fusion de deux listes triées, en avançant le pointeur qui est en retard.

Elle est efficace lorsque les entrées sont déjà triées, par exemple lorsqu'elles proviennent directement d'un index dans l'ordre de la clé, car aucune étape de tri n'est alors nécessaire. Elle prend également en charge les jointures par intervalle et les jointures d'inégalité, contrairement à la jointure par hachage.

Si les entrées ne sont pas préalablement triées, le planificateur ajoute des nœuds Sort explicites, et le coût de ce tri peut rendre la jointure par hachage plus économique.

Retenez dans quels cas chaque algorithme est le plus efficace :

• Boucles imbriquées : petite table externe et clé de jointure interne indexée ; c'est également la seule option pour les jointures sans égalité lorsque les entrées ne sont pas triées.
• Jointure par hachage : grandes tables non triées jointes selon une égalité ; aucun index n'est nécessaire.
• Jointure par fusion : les deux entrées sont déjà triées selon la clé, souvent grâce aux index, ou il s'agit de jointures par intervalle ; cette méthode convient très bien aux ensembles très volumineux déjà triés.

Le planificateur estime le coût de chaque méthode et choisit la moins coûteuse selon ses estimations du nombre de lignes.

L'utilisation des ressources varie fortement, et les recruteurs approfondissent ce point :

• Boucles imbriquées : mémoire minimale ; le coût est principalement dû aux recherches répétées du côté interne.
• Jointure par hachage : nécessite de la mémoire pour la table de hachage ; écrit sur le disque si elle est trop volumineuse.
• Jointure par fusion : fusion peu coûteuse, mais tri préalable coûteux ; les tris utilisent également work_mem et peuvent écrire sur le disque.

Ainsi, augmenter work_mem peut transformer une jointure par hachage ou un tri lent qui utilise le disque en une opération effectuée en mémoire, ce qui constitue une réponse d'optimisation concrète.

Scénario classique : une requête était rapide en développement, mais lente en production. Le plan affiche une boucle imbriquée avec loops=3000000.

Le planificateur a sous-estimé le nombre de lignes externes (des statistiques obsolètes indiquaient 3 lignes, alors que la réalité en comptait 3 millions), et a donc choisi une boucle imbriquée. Avec des statistiques exactes, il aurait choisi une jointure par hachage.

Votre réponse lors de l'entretien : exécutez ANALYZE pour corriger l'estimation ; le planificateur choisira alors une jointure par hachage et la requête deviendra beaucoup plus rapide.

Vous ne devriez généralement pas imposer les algorithmes, mais vous pouvez le faire lors des tests pour les comparer. Postgres propose des commutateurs pour chaque méthode :

SET enable_nestloop = off; et des commutateurs similaires pour enable_hashjoin et enable_mergejoin. Désactivez-en un, réexécutez EXPLAIN ANALYZE et observez si l'autre méthode est réellement plus rapide.

Les véritables solutions restent les suivantes : des statistiques récentes, les bons index, une valeur suffisante pour work_mem et des prédicats sélectifs. L'imposition d'un choix ne sert qu'au diagnostic.

Appliquez tout cela à une charge de travail analytique qui joint deux grandes tables de faits et de dimensions sur un identifiant :

• Si la dimension tient en mémoire, prévoyez une jointure par hachage, souvent la meilleure option.
• Si les deux tables arrivent déjà triées grâce aux index, une jointure par fusion peut éviter la construction de la table de hachage.
• Une boucle imbriquée serait ici un signal d'alerte, généralement dû à une mauvaise estimation.

Lire la méthode choisie par le planificateur et déterminer si ce choix était justifié est précisément ce que ces questions cherchent à évaluer chez un profil senior.

Vous joignez deux grandes tables non triées selon une condition d'égalité a.id = b.id ; aucune ne possède d'index utile et les statistiques sont exactes. Quel algorithme de jointure le planificateur choisira-t-il probablement ?

Les trois algorithmes de jointure :

• Boucles imbriquées : chaque ligne externe déclenche une recherche interne ; excellente méthode avec une petite table externe et une clé interne indexée, mais dangereuse lorsque loops est très élevé.
• Jointure par hachage : construction puis sondage ; meilleure méthode pour les grandes jointures d'égalité non triées, limitée à l'égalité et contrainte par work_mem.
• Jointure par fusion : parcours simultané d'entrées triées ; idéale lorsque les données sont déjà triées ou pour les jointures par intervalle.

Le planificateur choisit en fonction du coût et des statistiques. Une boucle imbriquée surprenante avec un nombre de boucles énorme indique presque toujours une mauvaise estimation du nombre de lignes : corrigez les statistiques.