Algorithmes de jointure et ordre de jointure

Le jeu de données de cet article — perf_sales et employee

Quand tu joins deux tables, la base choisit en interne un algorithme de jointure — la procédure utilisée pour apparier les lignes des deux tables.

Différentes méthodes de jointure ont des coûts différents.

Le jeu de données est la table de ventes perf_sales (50 000 lignes ; emp_id pointe vers un commercial) et la table employés employee (30 lignes ; emp_id est de fait la clé primaire).

En joignant les deux sur emp_id, tu observeras laquelle apparaît comme boucle externe dans le plan et comment l'ordre de jointure évolue selon qu'un index existe.

Avant de passer aux exercices, vérifie les définitions de colonnes et un échantillon des données des deux tables utilisées dans cet article — perf_sales et employee. La génération de perf_sales prend un instant, donc le premier passage peut faire une pause de quelques secondes.

① Utilise PRAGMA table_info(perf_sales); et PRAGMA table_info(employee); pour voir les définitions de colonnes des deux tables.

② Utilise SELECT * FROM perf_sales LIMIT 5; et SELECT * FROM employee LIMIT 5; pour prévisualiser les 5 premières lignes de chacune.

③ Utilise SELECT COUNT(*) FROM perf_sales; et SELECT COUNT(*) FROM employee; pour confirmer l'écart de nombre de lignes (50 000 vs. 30).

Jointure en boucles imbriquées et ordre de jointure

Une jointure en boucles imbriquées parcourt la table externe une ligne à la fois et, pour chaque ligne, cherche les lignes de la table interne qui satisfont la condition de jointure — une boucle doublement imbriquée.

-- Comparer la même requête de jointure entre trois méthodes
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Flux interne d'une jointure en boucles imbriquées
-- for each e in employee:        -- boucle externe (30 lignes)
--   for each s in perf_sales:    -- interne (sans index, parcourt les 50 000 lignes)
--     if s.emp_id = e.emp_id then ajouter au résultat de jointure

• La boucle externe tourne autant de fois que la table a de lignes, donc place la plus petite table à l'extérieur
• Le côté interne est cherché de façon répétée depuis chaque ligne externe, donc indexe la clé de jointure pour en faire une recherche en un seul coup
• Dans le plan, la table qui apparaît en premier est l'externe, et celle qui apparaît ensuite est l'interne
• L'optimiseur choisit externe / interne automatiquement à partir des statistiques, donc l'ordre que tu écris dans FROM n'est pas forcément respecté

-- Joindre perf_sales et employee sur emp_id (total des ventes par employé dans dept 1)
-- Sans index sur perf_sales.emp_id, le plan tend à parcourir l'interne perf_sales en entier
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SCAN perf_sales AS s   (pas d'index, donc l'interne aussi est parcourue entièrement)

-- Ajoute un index sur perf_sales.emp_id et l'interne peut être cherchée via l'index
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

Regarde le plan d'une requête de jointure qui compte les ventes par commercial, et lis quelle table est sur la boucle externe. (Exécute-le correctement et l'explication apparaîtra.)

① Préfixe EXPLAIN QUERY PLAN à une requête qui joint employee et perf_sales sur emp_id et compte les lignes par nom d'employé avec GROUP BY, et vérifie son plan.

② La table qui apparaît en premier dans la sortie est la boucle externe, et celle qui apparaît ensuite est l'interne. Sans index encore sur perf_sales.emp_id, lis laquelle finit à l'extérieur et comment l'interne est lue.

Rends la table interne de la jointure consultable via un index et confirme que le plan passe de SCAN à SEARCH ... USING INDEX. Regroupe la création de l'index et la vérification du plan dans une seule exécution.

① Supprime tout index du même nom avec DROP INDEX IF EXISTS, puis crée un index sur la colonne emp_id de perf_sales avec CREATE INDEX.

② Préfixe EXPLAIN QUERY PLAN à une requête qui joint employee et perf_sales sur emp_id et compte les lignes par nom d'employé, et vérifie son plan. Confirme qu'employee (30 lignes) reste sur la boucle externe pendant que l'interne perf_sales est maintenant cherchée via l'index.

L'optimiseur choisit l'ordre de jointure automatiquement à partir des statistiques

L'ordre de jointure — quelle table va sur la boucle externe — est, en règle générale, choisi automatiquement par l'optimiseur à partir des statistiques.

Si tu as collecté les statistiques avec ANALYZE (couvert dans l'article précédent), l'optimiseur peut estimer plus précisément « quelle table est plus petite » et « si l'interne peut être cherchée via un index » et optimiser l'affectation externe / interne.

L'ordre que tu écris dans FROM peut tout à fait être remanié par l'optimiseur.

L'astuce pour lire l'ordre de jointure : dans la sortie d'EXPLAIN QUERY PLAN, la table la plus haute est plus proche de la boucle externe.

Quand la mauvaise table finit sur la boucle externe et que les choses ralentissent, la première chose à vérifier est si la clé de jointure de la table que tu veux comme interne a un index.

-- Après ANALYZE, externe / interne sont décidés plus précisément à partir des statistiques
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
ANALYZE;

-- Même avec perf_sales en premier dans FROM, l'optimiseur peut mettre la plus petite employee à l'extérieur
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM perf_sales s
JOIN employee e ON e.emp_id = s.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee AS e
--> SEARCH perf_sales AS s USING INDEX ix_sales_emp (emp_id=?)

Confirme que l'optimiseur choisit le même ordre de jointure même quand tu inverses l'ordre des tables dans FROM. Regroupe la création de l'index, la collecte de statistiques et la vérification du plan dans une seule exécution.

① Supprime tout index du même nom avec DROP INDEX IF EXISTS, crée un index sur emp_id de perf_sales, puis exécute ANALYZE; pour collecter les statistiques.

② Préfixe EXPLAIN QUERY PLAN à une requête dont le FROM est maintenant FROM perf_sales s JOIN employee e ON ... (la grande table écrite en premier dans FROM) et qui compte les lignes par nom d'employé, et vérifie son plan. Lis si l'optimiseur choisit toujours l'employee de 30 lignes pour la boucle externe même avec l'ordre du FROM inversé.

Jointure par hachage et jointure par tri-fusion — méthodes de jointure utilisées par d'autres bases

Les grandes bases (PostgreSQL / Oracle / SQL Server, etc.) utilisent aussi la jointure par hachage (construire une table de hachage à partir du plus petit côté et sonder l'autre contre elle) et la jointure par tri-fusion (trier les deux côtés par la clé de jointure et les parcourir en pas cadencé) en plus de la jointure en boucles imbriquées.

Le moteur qui alimente la console navigateur de ce cours n'utilise que la boucle imbriquée, donc cette section couvre les deux autres méthodes au niveau schéma-et-concept.

Jointure par hachage — transformer le plus petit côté en table de hachage et y faire passer l'autre

-- Même requête, conceptuellement exécutée comme une jointure par hachage
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Flux interne d'une jointure par hachage
-- H := { e.emp_id => e | e in employee }    -- (1) Build (transformer employee en table de hachage)
-- for each s in perf_sales:                  -- (2) Probe (faire passer perf_sales)
--   if H[s.emp_id] exists: ajouter au résultat de jointure

• Mettre la plus petite table côté build garde la table de hachage assez petite pour tenir en mémoire, ce qui rend l'opération rapide
• Ne marche que pour les jointures d'égalité (=) ; les conditions de plage (< / BETWEEN) ne peuvent pas être jointes comme ça
• Peut joindre de gros volumes de lignes des deux côtés en une seule passe chacun même sans index sur l'interne, donc c'est souvent plus rapide qu'une boucle imbriquée
• Apparaît comme Hash Join dans l'EXPLAIN des bases de production

Jointure par tri-fusion — trier les deux côtés, puis les parcourir ensemble

-- Même requête, conceptuellement exécutée comme une jointure par tri-fusion
SELECT e.name, s.amount
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id;

-- Flux interne d'une jointure par tri-fusion
-- E := sort(employee by emp_id)        -- (1) Sort (ordonner les deux par emp_id)
-- S := sort(perf_sales by emp_id)
-- i, j := 0, 0
-- while i < |E| and j < |S|:            -- (2) Merge
--   if E[i].emp_id = S[j].emp_id: ajouter au résultat de jointure, j++
--   else if E[i].emp_id < S[j].emp_id: i++
--   else: j++

• Si les deux côtés sont déjà triés (alignés par un index, par exemple), le coût du tri est essentiellement nul et c'est extrêmement rapide
• Gère aussi les jointures de plage (conditions de jointure incluant < ou BETWEEN) — un atout que la jointure par hachage n'a pas
• Le résultat sort trié par la clé de jointure, ce qui est pratique pour les agrégations et fusions en aval
• Apparaît comme Merge Join dans l'EXPLAIN des bases de production

Jointure par hachage et jointure par tri-fusion sont des méthodes d'autres SGBDR

La jointure par hachage et la jointure par tri-fusion sont des méthodes de jointure fournies par les grandes bases comme PostgreSQL / Oracle / SQL Server.

Le moteur qui alimente la console navigateur de ce cours n'utilise que la boucle imbriquée comme algorithme de jointure (il peut créer un index interne transitoire pour aider la jointure si nécessaire), donc la jointure par hachage et la jointure par tri-fusion ne peuvent pas être démontrées en direct dans cette console.

Pour celles-ci nous nous contentons des schémas et du code en lecture seule ci-dessus pour saisir l'idée.

En revanche, les côtés externe / interne de la jointure en boucles imbriquées, l'ordre de jointure et le basculement de SCAN à SEARCH côté interne piloté par l'index, tous couverts plus tôt dans cet article, sont observables pour de vrai.

La capacité à lire quelle méthode de jointure la base a choisie repose sur la même compréhension des boucles imbriquées et de l'ordre de jointure.

Les bases de production afficheront des termes comme Hash Join / Merge Join dans leur EXPLAIN, donc commence par te familiariser avec la lecture des plans en boucles imbriquées dans ce cours.

-- Ci-dessous à quoi pourrait ressembler EXPLAIN dans PostgreSQL (lecture seule ; non exécuté sur la console de ce cours)
-- EXPLAIN SELECT e.name, SUM(s.amount) FROM employee e
--   JOIN perf_sales s ON s.emp_id = e.emp_id GROUP BY e.name;
-- Exemples de plans :
--   Hash Join  (construire une table de hachage depuis employee, puis faire passer perf_sales)
--   ou Merge Join (trier les deux par emp_id, puis les apparier)
-- PostgreSQL choisit parmi ces méthodes automatiquement à partir des statistiques et du coût

-- Ce que la console de ce cours peut réellement démontrer est ceci (boucle imbriquée) :
DROP INDEX IF EXISTS ix_sales_emp;
CREATE INDEX ix_sales_emp ON perf_sales(emp_id);
EXPLAIN QUERY PLAN
SELECT e.name, SUM(s.amount) AS total
FROM employee e
JOIN perf_sales s ON s.emp_id = e.emp_id
WHERE e.dept_id = 1
GROUP BY e.name;
--> SCAN employee / SEARCH perf_sales USING INDEX ix_sales_emp (emp_id=?)

Pour conclure cet article, revérifie le plan de jointure avec l'index en place et lis la boucle externe, l'accès par index sur l'interne, et le sens du résultat. Regroupe la création de l'index, la vérification du plan et la vérification du résultat dans une seule exécution.

① Supprime tout index du même nom avec DROP INDEX IF EXISTS, puis crée un index sur emp_id de perf_sales.

② Préfixe EXPLAIN QUERY PLAN à une requête qui joint employee et perf_sales sur emp_id et compte les ventes par nom de commercial, et vérifie son plan.

③ Exécute la même requête d'agrégation (sans EXPLAIN QUERY PLAN) avec ORDER BY cnt DESC LIMIT 5; pour tirer les 5 meilleurs commerciaux par nombre. Lis à la fois le plan et le résultat réel.