Cas B : la consolidation d'une hiérarchie

Une récursion par nœud : chaque exécution est parfaite, le total est une boucle de 40 002 instructions.

≈ 6 min de lectureLecture

En bref

Erreurs : E1, E4, E5, E13.
Boucle : 40 002 instructions pour 20 000 nœuds ; quadratique sans index.
Ensembliste : fermeture (préparation) + 1 requête ; chaque recalcul = 1 instruction.
Méthode : préparer la structure stable.

Sur cette page

Énoncé
Le modèle
La version procédurale
Pourquoi c'est une catastrophe
Mesures
La refonte ensembliste
Vérifier l'équivalence
Maintenir la préparation
Ce qu'on retient

Énoncé#

Une hiérarchie de 20 000 nœuds (organisation, nomenclature, plan de comptes) porte une valeur par nœud. On doit calculer, pour chaque nœud, le total de son sous-arbre, et le recalculer chaque fois que les valeurs changent.

Le modèle#

CREATE TABLE dbo.Noeuds (NoeudId int NOT NULL PRIMARY KEY, ParentId int NULL, Valeur decimal(18,2) NOT NULL);
CREATE INDEX IX_Noeuds_Parent ON dbo.Noeuds (ParentId) INCLUDE (Valeur);        -- l'index que la récursion réclame
CREATE TABLE dbo.Consolide (NoeudId int NOT NULL PRIMARY KEY, Total decimal(18,2) NULL);

-- Un arbre à 4 branches par nœud : 20 000 nœuds, 8 niveaux
WITH N AS (SELECT TOP (20000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS n FROM sys.all_columns AS a CROSS JOIN sys.all_columns AS b)
INSERT INTO dbo.Noeuds (NoeudId, ParentId, Valeur)
SELECT n, CASE WHEN n = 1 THEN NULL ELSE (n - 2) / 4 + 1 END, n % 100 FROM N;
INSERT INTO dbo.Consolide (NoeudId) SELECT NoeudId FROM dbo.Noeuds;

La version procédurale#

-- Pour chaque nœud : une CTE récursive qui somme son sous-arbre, puis une mise à jour
DECLARE @id int;
DECLARE c CURSOR LOCAL FAST_FORWARD FOR SELECT NoeudId FROM dbo.Noeuds ORDER BY NoeudId;
OPEN c; FETCH NEXT FROM c INTO @id;
WHILE @@FETCH_STATUS = 0
BEGIN
    WITH R AS
    (
        SELECT NoeudId, Valeur FROM dbo.Noeuds WHERE NoeudId = @id
        UNION ALL
        SELECT n.NoeudId, n.Valeur FROM dbo.Noeuds AS n JOIN R ON n.ParentId = R.NoeudId
    )
    UPDATE dbo.Consolide SET Total = (SELECT SUM(Valeur) FROM R) WHERE NoeudId = @id;
    FETCH NEXT FROM c INTO @id;
END;
CLOSE c; DEALLOCATE c;

Revue de code : la CTE récursive est la bonne façon de parcourir une hiérarchie ; l'index sur ParentId existe ; la mise à jour est ciblée sur la clé ; le curseur est local et en lecture seule. Rien à redire.

Pourquoi c'est une catastrophe#

Erreur cumulée	Où elle se cache
E1 boucle externe invisible	Une requête récursive par nœud : 20 000 exécutions
E5 dérivée recalculée	La structure de l'arbre (qui descend de qui) est redécouverte pour chaque nœud, alors qu'elle ne change pas à chaque exécution
E4 chemin d'accès oublié	Sans l'index sur `ParentId`, chaque pas de récursion parcourt la table
E13 validation par ligne	Une mise à jour validée séparément par nœud

Particularité de ce cas : le travail total n'est pas gonflé (somme des tailles de sous-arbres : environ 153 000 lignes visitées pour 20 000 nœuds) ; c'est le nombre d'exécutions et la redécouverte répétée de la structure qui coûtent. L'écart sur la première exécution est donc modeste ; il devient énorme sur les suivantes.

Mesures#

Nœuds	Variante	Instructions	Lectures logiques	CPU (ms)	Durée (ms)
2 500	P0 · boucle, sans index sur `ParentId`	5 002	328 653	6 441 à 11 785	6 917 à 12 533
2 500	P1 · boucle, index sur `ParentId`	5 002	185 054	235	505
2 500	S · fermeture + 1 requête	2	178 993	148	211
2 500	S2 · recalcul seul	1	17 557	27	33
5 000	P0	10 002	959 117	6 152 à 10 751	6 735 à 11 764
5 000	P1	10 002	390 104	459	1 021
5 000	S	2	377 395	337	401
5 000	S2	1	35 109	36	42
10 000	P0	20 002	3 259 761	51 061	53 965
10 000	P1	20 002	850 146	1 028	2 147
10 000	S	2	823 933	819	1 007
10 000	S2	1	70 225	99	115
20 000	P1	40 002	1 800 374	2 110	4 407
20 000	S (fermeture : 152 721 lignes)	2	1 727 072	1 679	2 020
20 000	S2	1	140 459	155	173

Sans index sur ParentId (P0), la boucle est quadratique : les lectures logiques passent de 328 653 à 959 117 puis 3 259 761 quand le nombre de nœuds double (× 2,9 puis × 3,4). Les durées sont instables d'une exécution à l'autre (la plage indiquée donne deux mesures).
Avec l'index (P1), la boucle devient linéaire, mais exécute 40 002 instructions pour 20 000 nœuds.
La première exécution ensembliste (S) est de l'ordre de deux fois plus rapide que la boucle indexée : elle construit la fermeture.
Chaque recalcul suivant (S2) ne coûte que la requête finale : 1 instruction, environ 13 fois moins de lectures logiques que la boucle (140 459 contre 1 800 374), et de l'ordre de 25 fois plus rapide (173 ms contre 4 407 ms, durées indicatives).

La refonte ensembliste#

La structure de l'arbre est une donnée stable : on la prépare une fois, sous une forme qui se joint.

Préparation#

-- PRÉPARATION — la hiérarchie devient une table de fermeture (ancêtre, descendant, profondeur)
CREATE TABLE dbo.Fermeture (Ancetre int NOT NULL, Descendant int NOT NULL, Profondeur tinyint NOT NULL,
                            CONSTRAINT PK_Fermeture PRIMARY KEY CLUSTERED (Ancetre, Descendant));
WITH F AS
(
    SELECT NoeudId AS Ancetre, NoeudId AS Descendant, CAST(0 AS tinyint) AS Profondeur FROM dbo.Noeuds
    UNION ALL
    SELECT f.Ancetre, n.NoeudId, CAST(f.Profondeur + 1 AS tinyint)
    FROM   F AS f JOIN dbo.Noeuds AS n ON n.ParentId = f.Descendant
)
INSERT INTO dbo.Fermeture (Ancetre, Descendant, Profondeur)
SELECT Ancetre, Descendant, Profondeur FROM F
OPTION (MAXRECURSION 200);

Exécution : une requête#

-- EXÉCUTION — une seule requête : tous les totaux, d'un coup
UPDATE c
SET    c.Total = s.Total
FROM   dbo.Consolide AS c
JOIN  (SELECT f.Ancetre, SUM(n.Valeur) AS Total
       FROM   dbo.Fermeture AS f
       JOIN   dbo.Noeuds    AS n ON n.NoeudId = f.Descendant
       GROUP BY f.Ancetre) AS s ON s.Ancetre = c.NoeudId;

Ce que la préparation rend possible#

-- La même préparation sert d'autres questions, chacune en UNE requête :
-- effectif et profondeur maximale par nœud
SELECT Ancetre, COUNT(*) AS nb_descendants, MAX(Profondeur) AS profondeur_max FROM dbo.Fermeture GROUP BY Ancetre;
-- le chemin complet d'un nœud (ses ancêtres, du plus proche à la racine)
SELECT Ancetre, Profondeur FROM dbo.Fermeture WHERE Descendant = 12345 ORDER BY Profondeur;
-- sous-arbre d'un nœud, sans récursion
SELECT n.* FROM dbo.Fermeture AS f JOIN dbo.Noeuds AS n ON n.NoeudId = f.Descendant WHERE f.Ancetre = 42;

Vérifier l'équivalence#

-- Équivalence : conserver Consolide après la version procédurale (Consolide_ref), remettre Total à NULL, exécuter la version ensembliste
SELECT * FROM dbo.Consolide_ref EXCEPT SELECT * FROM dbo.Consolide;     -- aucune ligne
SELECT * FROM dbo.Consolide EXCEPT SELECT * FROM dbo.Consolide_ref;     -- aucune ligne

Résultat : aucune ligne dans les deux sens, aux quatre tailles mesurées.

Maintenir la préparation#

La fermeture est une fonction de la structure (ParentId), pas des valeurs : les changements de valeurs n'obligent à rien (c'est le cas S2). Elle doit être régénérée, ou mise à jour de façon incrémentale, quand la structure change (déplacement, ajout ou suppression de nœud). La taille est de l'ordre de nœuds × profondeur moyenne : 152 721 lignes pour 20 000 nœuds. Voir E10.

Ce qu'on retient#

Une CTE récursive par entité est une boucle, même si chaque exécution est parfaite.
Quand la structure est stable et les valeurs changent, préparer la structure : le gain se mesure à chaque recalcul suivant, pas à la première exécution.
Une préparation sert plusieurs questions : effectif, profondeur, chemin, sous-arbre.