Lesson 29 of 54 18 minIntermediate

Recursive CTEs: hierarchies and bills of materials

A CTE that refers to itself: the anchor and recursive members, generating numbers and dates, walking down and up a management hierarchy, exploding a bill of materials, and MAXRECURSION.

A recursive CTE refers to its own name. It has two parts joined by UNION ALL: an anchor query that produces the starting rows, and a recursive query that produces new rows from the rows of the previous step. It repeats until a step produces no rows.

Query.sql

1WITH Numbers AS (2    SELECT 1 AS n            -- anchor: the first row3    UNION ALL4    SELECT n + 1             -- recursive: one new row from the last one5    FROM Numbers6    WHERE n < 5              -- stops when this is false7)8SELECT n FROM Numbers;

Output

Step	Input rows	Output rows
anchor	(none)	n = 1
1	n = 1	n = 2
2	n = 2	n = 3
3	n = 3	n = 4
4	n = 4	n = 5
5	n = 5	none, because 5 < 5 is false: stop

Each step only sees the rows the previous step produced, not the whole result so far. The final result is all the steps stacked together.

Filling in missing months

The GROUP BY lesson showed that January has no orders and so no row. Generate every month of the half-year first, then LEFT JOIN the orders to it:

Query.sql

1WITH Months AS (2    SELECT CAST('2024-01-01' AS date) AS MonthStart3    UNION ALL4    SELECT DATEADD(month, 1, MonthStart)5    FROM Months6    WHERE MonthStart < '2024-06-01'7)8SELECT m.MonthStart, COUNT(o.OrderId) AS Orders9FROM Months AS m10LEFT JOIN dbo.Orders AS o11    ON o.OrderDate >= m.MonthStart12   AND o.OrderDate <  DATEADD(month, 1, m.MonthStart)13GROUP BY m.MonthStart14ORDER BY m.MonthStart;

Output

Warning: Null value is eliminated by an aggregate or other SET operation.

MonthStart  Orders
----------  ------
2024-01-01       0
2024-02-01       2
2024-03-01       2
2024-04-01       2
2024-05-01       2
2024-06-01       2

Walking down a hierarchy

A table that refers to itself, such as staff with a ManagerId, holds a tree. A plain self join finds one level; a recursive CTE finds all of them:

Query.sql

1CREATE TABLE dbo.Staff (2    StaffId   int          NOT NULL PRIMARY KEY,3    Name      nvarchar(40) NOT NULL,4    JobTitle  nvarchar(40) NOT NULL,5    ManagerId int          NULL REFERENCES dbo.Staff (StaffId)6);7INSERT INTO dbo.Staff VALUES8    (1, N'Maya',  N'Managing director', NULL),9    (2, N'Omar',  N'Store manager',     1),10    (3, N'Lena',  N'Finance manager',   1),11    (4, N'Tom',   N'Yard supervisor',   2),12    (5, N'Priya', N'Sales lead',        2),13    (6, N'Sam',   N'Forklift driver',   4),14    (7, N'Kofi',  N'Sales assistant',   5),15    (8, N'Ruth',  N'Accounts clerk',    3);

Start from the person at the top (no manager) and, at each step, find the people whose manager was found in the step before:

Query.sql

1WITH Org AS (2    SELECT StaffId, Name, JobTitle, 0 AS Lvl,3           CAST(Name AS nvarchar(200)) AS Path4    FROM dbo.Staff5    WHERE ManagerId IS NULL6    UNION ALL7    SELECT s.StaffId, s.Name, s.JobTitle, o.Lvl + 1,8           CAST(o.Path + N' > ' + s.Name AS nvarchar(200))9    FROM dbo.Staff AS s10    JOIN Org AS o ON s.ManagerId = o.StaffId11)12SELECT REPLICATE(N'    ', Lvl) + Name AS Person, JobTitle, Lvl, Path13FROM Org14ORDER BY Path;

Output

Person            JobTitle           Lvl  Path
----------------  -----------------  ---  --------------------------
Maya              Managing director    0  Maya
    Lena          Finance manager      1  Maya > Lena
        Ruth      Accounts clerk       2  Maya > Lena > Ruth
    Omar          Store manager        1  Maya > Omar
        Priya     Sales lead           2  Maya > Omar > Priya
            Kofi  Sales assistant      3  Maya > Omar > Priya > Kofi
        Tom       Yard supervisor      2  Maya > Omar > Tom
            Sam   Forklift driver      3  Maya > Omar > Tom > Sam

Lvl counts the steps from the top: the anchor is 0, and each recursive step adds 1.
Path builds the chain of names. Sorting by it puts everyone under their manager, and REPLICATE indents them by level.
The CAST to nvarchar(200) matters: the anchor and recursive parts must have exactly the same type, and Name alone is only nvarchar(40).

Walking up

Turn the join around to go from one person up to the top. Start with Kofi and, at each step, find the manager of the previous row:

Query.sql

1WITH Chain AS (2    SELECT StaffId, Name, ManagerId, 0 AS StepsUp3    FROM dbo.Staff4    WHERE Name = N'Kofi'5    UNION ALL6    SELECT m.StaffId, m.Name, m.ManagerId, c.StepsUp + 17    FROM dbo.Staff AS m8    JOIN Chain AS c ON m.StaffId = c.ManagerId9)10SELECT StepsUp, Name FROM Chain;

Output

StepsUp  Name
-------  -----
      0  Kofi
      1  Priya
      2  Omar
      3  Maya

Exploding a bill of materials

A bill of materials (BOM) says what each thing is made of. BuildMart sells a garden shed kit. The kit is made of panels, and the panels are made of products off the shelf:

Query.sql

1CREATE TABLE dbo.Parts (2    PartId    int          NOT NULL PRIMARY KEY,3    Name      nvarchar(40) NOT NULL,4    ProductId int          NULL REFERENCES dbo.Products (ProductId)  -- set for shelf items5);6CREATE TABLE dbo.Bom (7    ParentId int NOT NULL REFERENCES dbo.Parts (PartId),8    ChildId  int NOT NULL REFERENCES dbo.Parts (PartId),9    Qty      int NOT NULL,10    PRIMARY KEY (ParentId, ChildId)11);12INSERT INTO dbo.Parts VALUES13    (1, N'Garden shed kit', NULL), (2, N'Wall panel', NULL),14    (3, N'Roof panel', NULL),      (4, N'Floor', NULL),15    (5, N'Timber 2x4 2.4 m', 6),   (6, N'Plywood sheet 18 mm', 7),16    (7, N'Wood screws (200)', 8);17INSERT INTO dbo.Bom VALUES18    (1, 2, 4), (1, 3, 2), (1, 4, 1), (1, 7, 3),19    (2, 5, 5), (2, 6, 1),20    (3, 5, 3), (3, 6, 1),21    (4, 5, 6), (4, 6, 2);

Exploding the kit means following the tree down and multiplying the quantities on the way: 4 wall panels each need 5 lengths of timber, so the kit needs 20 for its walls.

Query.sql

1WITH Explode AS (2    SELECT b.ParentId, b.ChildId, b.Qty AS TotalQty, 1 AS Lvl3    FROM dbo.Bom AS b4    WHERE b.ParentId = 15    UNION ALL6    SELECT b.ParentId, b.ChildId, e.TotalQty * b.Qty, e.Lvl + 17    FROM dbo.Bom AS b8    JOIN Explode AS e ON b.ParentId = e.ChildId9)10SELECT e.Lvl, par.Name AS PartOf, pt.Name, e.TotalQty11FROM Explode AS e12JOIN dbo.Parts AS pt  ON pt.PartId  = e.ChildId13JOIN dbo.Parts AS par ON par.PartId = e.ParentId14ORDER BY e.Lvl, par.Name, pt.Name;

Output

Lvl  PartOf           Name                 TotalQty
---  ---------------  -------------------  --------
  1  Garden shed kit  Floor                       1
  1  Garden shed kit  Roof panel                  2
  1  Garden shed kit  Wall panel                  4
  1  Garden shed kit  Wood screws (200)           3
  2  Floor            Plywood sheet 18 mm         2
  2  Floor            Timber 2x4 2.4 m            6
  2  Roof panel       Plywood sheet 18 mm         2
  2  Roof panel       Timber 2x4 2.4 m            6
  2  Wall panel       Plywood sheet 18 mm         4
  2  Wall panel       Timber 2x4 2.4 m           20

Interactive

Exploding the shed kit

Shopping list

Garden shed kit
- Wall panel ×4
  - …
  - …
- Roof panel ×2
  - …
  - …
- Floor ×1
  - …
  - …
- Wood screws (200) ×3

	Lvl	PartOf	Name	TotalQty
1	1	Garden shed kit	Floor	1
2	1	Garden shed kit	Roof panel	2
3	1	Garden shed kit	Wall panel	4
4	1	Garden shed kit	Wood screws (200)	3

The anchor reads the Bom rows whose parent is the kit (part 1): 4 rows at level 1. TotalQty is just Qty here.

Timber appears three times, once under each panel. To get a shopping list, keep only the shelf items, add up each one, and price it from Products:

Query.sql

1WITH Explode AS (2    SELECT b.ChildId, b.Qty AS TotalQty3    FROM dbo.Bom AS b4    WHERE b.ParentId = 15    UNION ALL6    SELECT b.ChildId, e.TotalQty * b.Qty7    FROM dbo.Bom AS b8    JOIN Explode AS e ON b.ParentId = e.ChildId9)10SELECT pr.Name, SUM(e.TotalQty) AS Qty, pr.Price,11       SUM(e.TotalQty) * pr.Price AS Cost12FROM Explode AS e13JOIN dbo.Parts    AS pt ON pt.PartId    = e.ChildId14JOIN dbo.Products AS pr ON pr.ProductId = pt.ProductId15GROUP BY pr.Name, pr.Price16ORDER BY Cost DESC;

Output

Name                 Qty  Price    Cost
-------------------  ---  -----  ------
Plywood sheet 18 mm    8  42.00  336.00
Timber 2x4 2.4 m      32   6.80  217.60
Wood screws (200)      3  11.90   35.70

The kit takes 32 lengths of timber, 8 plywood sheets and 3 boxes of screws, which cost 589.30 at today’s prices.

MAXRECURSION: the safety net

If the recursive part never stops producing rows, the query would run for ever. SQL Server stops it after 100 recursive steps by default:

Query.sql

1WITH Numbers AS (2    SELECT 1 AS n3    UNION ALL4    SELECT n + 1 FROM Numbers WHERE n < 2005)6SELECT MAX(n) AS Highest FROM Numbers;

Output

Msg 530, Level 16, State 1, Line 1
The statement terminated. The maximum recursion 100 has been exhausted before statement completion.

When you really need more steps, raise the limit for this query with OPTION (MAXRECURSION n), up to 32767, or 0 for no limit:

Query.sql

1WITH Numbers AS (2    SELECT 1 AS n3    UNION ALL4    SELECT n + 1 FROM Numbers WHERE n < 2005)6SELECT MAX(n) AS Highest FROM Numbers7OPTION (MAXRECURSION 200);

Output

Highest
-------
    200

Quick check

In each recursive step, which rows does the recursive part join to?

Quick check

A recursive CTE fails with “Types don’t match between the anchor and the recursive part”. What usually fixes it?

Practice

Using the Staff table from this lesson, list everyone who works under Omar, directly or indirectly, with how many levels below him they are. Do not include Omar himself.

Show a hint

The anchor selects the people whose ManagerId is Omar’s StaffId (2), at level 1. The recursive part joins Staff to the CTE on s.ManagerId = previous.StaffId.

Show the solution

Solution.sql

1WITH UnderOmar AS (2    SELECT StaffId, Name, 1 AS LevelsBelow3    FROM dbo.Staff4    WHERE ManagerId = 25    UNION ALL6    SELECT s.StaffId, s.Name, u.LevelsBelow + 17    FROM dbo.Staff AS s8    JOIN UnderOmar AS u ON s.ManagerId = u.StaffId9)10SELECT Name, LevelsBelow11FROM UnderOmar12ORDER BY LevelsBelow, Name;

Output

Name   LevelsBelow
-----  -----------
Priya            1
Tom              1
Kofi             2
Sam              2

Remember

A recursive CTE is an anchor query UNION ALL a recursive query that refers to the CTE.
Each step works on the rows produced by the previous step; it stops when a step produces none.
Generate numbers and dates, then LEFT JOIN data to fill in gaps.
Walk down a hierarchy by joining children to the previous level; walk up by joining managers.
A bill of materials multiplies quantities on the way down.
Anchor and recursive columns must have exactly the same types.
MAXRECURSION (default 100) stops runaway recursion; raise it with OPTION (MAXRECURSION n).

Foundations

Creating and changing data

Functions and expressions

Joins and combining tables

Grouping and subqueries

Advanced querying

Programmability

Indexes and performance

Master level

Recursive CTEs: hierarchies and bills of materials

Filling in missing months

Walking down a hierarchy

Walking up

Exploding a bill of materials

Exploding the shed kit

MAXRECURSION: the safety net

Remember