Case B: consolidating a hierarchy

One recursion per node: each execution is perfect, the total is a loop of 40,002 statements.

≈ 5 min readReading

In brief

Errors: E1, E4, E5, E13.
Loop: 40,002 statements for 20,000 nodes; quadratic without an index.
Set-based: closure (preparation) + 1 query; each recalculation = 1 statement.
Method: prepare the stable structure.

On this page

Problem statement
The model
The procedural version
Why it is a disaster
Measurements
The set-based redesign
Verifying equivalence
Maintaining the preparation
Takeaways

Problem statement#

A hierarchy of 20,000 nodes (organization, bill of materials, chart of accounts) carries one value per node. We must compute, for each node, the total of its subtree, and recompute it every time the values change.

The model#

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);        -- the index that the recursion demands
CREATE TABLE dbo.Consolide (NoeudId int NOT NULL PRIMARY KEY, Total decimal(18,2) NULL);

-- A tree with 4 branches per node: 20,000 nodes, 8 levels
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;

The procedural version#

-- For each node: a recursive CTE that sums its subtree, then an update
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;

Code review: the recursive CTE is the right way to traverse a hierarchy; the index on ParentId exists; the update targets the key; the cursor is local and read-only. Nothing to complain about.

Why it is a disaster#

Accumulated error	Where it hides
E1 invisible outer loop	One recursive query per node: 20,000 executions
E5 derived data recomputed	The tree structure (who descends from whom) is rediscovered for every node, even though it does not change from one execution to the next
E4 forgotten access path	Without the index on `ParentId`, each recursion step scans the table
E13 per-row commit	An update committed separately for each node

A peculiarity of this case: the total work is not inflated (sum of subtree sizes: about 153,000 rows visited for 20,000 nodes); what costs is the number of executions and the repeated rediscovery of the structure. The gap on the first execution is therefore modest; it becomes enormous on the following ones.

Measurements#

Nodes	Variant	Statements	Logical reads	CPU (ms)	Duration (ms)
2,500	P0 · loop, without an index on `ParentId`	5,002	328,653	6,441 to 11,785	6,917 to 12,533
2,500	P1 · loop, index on `ParentId`	5,002	185,054	235	505
2,500	S · closure + 1 query	2	178,993	148	211
2,500	S2 · recalculation only	1	17,557	27	33
5,000	P0	10,002	959,117	6,152 to 10,751	6,735 to 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 (closure: 152,721 rows)	2	1,727,072	1,679	2,020
20,000	S2	1	140,459	155	173

Without an index on ParentId (P0), the loop is quadratic: logical reads go from 328,653 to 959,117 then 3,259,761 each time the number of nodes doubles (× 2.9 then × 3.4). Durations are unstable from one run to the next (the range shown gives two measurements).
With the index (P1), the loop becomes linear, but executes 40,002 statements for 20,000 nodes.
The first set-based execution (S) is about twice as fast as the indexed loop: it builds the closure.
Each subsequent recalculation (S2) costs only the final query: 1 statement, about 13 times fewer logical reads than the loop (140,459 versus 1,800,374), and about 25 times faster (173 ms versus 4,407 ms, indicative durations).

The set-based redesign#

The tree structure is stable data: we prepare it once, in a form that can be joined.

Preparation#

-- PREPARATION — the hierarchy becomes a closure table (ancestor, descendant, depth)
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);

Execution: one query#

-- EXECUTION — a single query: all the totals at once
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;

What the preparation makes possible#

-- The same preparation serves other questions, each in ONE query:
-- headcount and maximum depth per node
SELECT Ancetre, COUNT(*) AS nb_descendants, MAX(Profondeur) AS profondeur_max FROM dbo.Fermeture GROUP BY Ancetre;
-- the full path of a node (its ancestors, from the closest to the root)
SELECT Ancetre, Profondeur FROM dbo.Fermeture WHERE Descendant = 12345 ORDER BY Profondeur;
-- subtree of a node, without recursion
SELECT n.* FROM dbo.Fermeture AS f JOIN dbo.Noeuds AS n ON n.NoeudId = f.Descendant WHERE f.Ancetre = 42;

Verifying equivalence#

-- Equivalence: keep Consolide after the procedural version (Consolide_ref), reset Total to NULL, run the set-based version
SELECT * FROM dbo.Consolide_ref EXCEPT SELECT * FROM dbo.Consolide;     -- no rows
SELECT * FROM dbo.Consolide EXCEPT SELECT * FROM dbo.Consolide_ref;     -- no rows

Result: no rows in either direction, at all four measured sizes.

Maintaining the preparation#

The closure is a function of the structure (ParentId), not of the values: value changes require nothing (that is case S2). It must be regenerated, or updated incrementally, when the structure changes (a node is moved, added or deleted). Its size is on the order of nodes × average depth: 152,721 rows for 20,000 nodes. See E10.

Takeaways#

A recursive CTE per entity is a loop, even if each execution is perfect.
When the structure is stable and the values change, prepare the structure: the gain shows up on every subsequent recalculation, not on the first execution.
One preparation serves several questions: headcount, depth, path, subtree.