Recursive CTEs and Hierarchies

Some data points at itself: a category inside a category, an employee who reports to an employee, a part made of parts. The depth is not known in advance, so a query with one join per level is wrong the day somebody adds a level. A recursive CTE handles any depth. It starts from one set of rows, then keeps joining the table to the rows it found in the last round until nothing new turns up. The Intermediate course showed ordinary CTEs as named steps. This lesson adds the one that calls itself, and the bad data that can make it run forever.

The shape

A recursive CTE has two parts joined with UNION ALL: the anchor, which runs once, and the recursive term, which refers to the CTE's own name and runs again on the rows from the previous round. It stops when a round returns no rows. The smallest example counts to five.

WITH RECURSIVE n(i) AS (
  SELECT 1                              -- anchor: where to start
  UNION ALL
  SELECT i + 1 FROM n WHERE i < 5       -- recursive term: the next row, until the condition fails
)
SELECT i FROM n;

 i
---
 1
 2
 3
 4
 5
(5 rows)

The WHERE i < 5 is the stop. Without it, every round would produce another row, and the query would not end.

A category tree

The shop has products in categories, and the categories form a tree. Each row points to its parent. The top row has no parent. The tables below hold 11 categories, and product_categories puts each product of the shop in one of them.

CREATE TABLE categories (
  category_id integer PRIMARY KEY,
  parent_id   integer REFERENCES categories (category_id),
  name        text NOT NULL
);
INSERT INTO categories VALUES
  (1, NULL, 'All products'),
  (2, 1, 'Stationery'), (3, 1, 'Home'), (4, 1, 'Bags'), (5, 1, 'Electronics'),
  (6, 2, 'Notebooks'), (7, 2, 'Pens'), (8, 5, 'Cables'), (9, 5, 'Accessories'),
  (10, 9, 'Phone stands'), (11, 7, 'Gel pens');
CREATE TABLE product_categories (
  product_id  integer PRIMARY KEY REFERENCES products (product_id),
  category_id integer NOT NULL REFERENCES categories (category_id)
);
INSERT INTO product_categories VALUES
  (1, 6), (2, 11), (3, 3), (4, 3), (5, 4), (6, 4), (7, 8), (8, 10), (9, 9), (10, 2);

CREATE TABLE
INSERT 0 11
CREATE TABLE
INSERT 0 10

Walk down from the top. Each round adds the children of the rows from the round before, carries a depth, and builds a text path.

WITH RECURSIVE tree AS (
  SELECT category_id, name, 0 AS depth, name::text AS path
  FROM categories
  WHERE parent_id IS NULL
  UNION ALL
  SELECT c.category_id, c.name, t.depth + 1, t.path || ' > ' || c.name
  FROM categories c
  JOIN tree t ON c.parent_id = t.category_id
)
SELECT repeat('  ', depth) || name AS category, depth, path
FROM tree
ORDER BY path;

      category      | depth |                          path
--------------------+-------+---------------------------------------------------------
 All products       |     0 | All products
   Bags             |     1 | All products > Bags
   Electronics      |     1 | All products > Electronics
     Accessories    |     2 | All products > Electronics > Accessories
       Phone stands |     3 | All products > Electronics > Accessories > Phone stands
     Cables         |     2 | All products > Electronics > Cables
   Home             |     1 | All products > Home
   Stationery       |     1 | All products > Stationery
     Notebooks      |     2 | All products > Stationery > Notebooks
     Pens           |     2 | All products > Stationery > Pens
       Gel pens     |     3 | All products > Stationery > Pens > Gel pens
(11 rows)

Ordering by the path puts every child under its parent, and indenting by depth makes the tree readable. The first round returned the top row, the second its four children, and so on, to depth 3. The CTE has no idea how deep the tree is, and it does not need to.

Going up the tree

To find everything above a row, start at the row and join the other way: the next row is the one whose category_id equals this row's parent_id.

WITH RECURSIVE up AS (
  SELECT category_id, parent_id, name, 0 AS steps
  FROM categories
  WHERE name = 'Phone stands'
  UNION ALL
  SELECT c.category_id, c.parent_id, c.name, u.steps + 1
  FROM categories c
  JOIN up u ON c.category_id = u.parent_id
)
SELECT steps, name FROM up ORDER BY steps;

 steps |     name
-------+--------------
     0 | Phone stands
     1 | Accessories
     2 | Electronics
     3 | All products
(4 rows)

This is the breadcrumb: Phone stands, inside Accessories, inside Electronics, inside All products.

Totals for a whole branch

How many units were sold in Stationery, counting Pens, Gel pens and Notebooks under it? Build a list of every category together with each category below it, and use it to join the orders. The root of each branch is the first column.

WITH RECURSIVE branch (root_id, category_id) AS (
  SELECT category_id, category_id FROM categories
  UNION ALL
  SELECT b.root_id, c.category_id
  FROM branch b
  JOIN categories c ON c.parent_id = b.category_id
)
SELECT r.name AS branch, sum(oi.quantity) AS units
FROM branch b
JOIN categories r         ON r.category_id = b.root_id
JOIN product_categories pc ON pc.category_id = b.category_id
JOIN order_items oi        ON oi.product_id = pc.product_id
WHERE r.parent_id = 1 OR r.parent_id IS NULL
GROUP BY r.name
ORDER BY units DESC, r.name;

    branch    | units
--------------+-------
 All products |    41
 Stationery   |    21
 Electronics  |    10
 Home         |     6
 Bags         |     4
(5 rows)

All products is the sum of the four branches, 41. Stationery is 21: 3 notebooks and 18 gel pens, and the stickers were never ordered. Every branch adds up the rows of every category inside it, at any depth.

When the data has a loop

A tree has no loops, but a table does not know that. Suppose somebody sets the parent of Stationery to Notebooks, which is already inside Stationery. The walk now comes back to where it began. This runs inside a transaction that is rolled back, so the shop data is not changed. Without a stop, the recursion would never end, so the first query asks for only 8 rows.

BEGIN;
UPDATE categories SET parent_id = 6 WHERE category_id = 2;
WITH RECURSIVE tree AS (
  SELECT category_id, name, 0 AS depth FROM categories WHERE name = 'Stationery'
  UNION ALL
  SELECT c.category_id, c.name, t.depth + 1
  FROM categories c JOIN tree t ON c.parent_id = t.category_id
)
SELECT depth, name FROM tree LIMIT 8;

BEGIN
UPDATE 1
 depth |    name
-------+------------
     0 | Stationery
     1 | Notebooks
     1 | Pens
     2 | Gel pens
     2 | Stationery
     3 | Notebooks
     3 | Pens
     4 | Gel pens
(8 rows)

Stationery, Notebooks, Pens, Gel pens, then Stationery again at depth 2, and round again. PostgreSQL has a clause for this. CYCLE remembers the values of the column you name, and marks a row that has been seen before.

WITH RECURSIVE tree AS (
  SELECT category_id, name, 0 AS depth FROM categories WHERE name = 'Stationery'
  UNION ALL
  SELECT c.category_id, c.name, t.depth + 1
  FROM categories c JOIN tree t ON c.parent_id = t.category_id
) CYCLE category_id SET is_cycle USING visited
SELECT depth, name, is_cycle FROM tree;
ROLLBACK;

 depth |    name    | is_cycle
-------+------------+----------
     0 | Stationery | f
     1 | Notebooks  | f
     1 | Pens       | f
     2 | Gel pens   | f
     2 | Stationery | t
(5 rows)

ROLLBACK

The second Stationery row has is_cycle set to t, and the recursion does not follow it any further. The query ends, and you can also find the bad row by filtering on is_cycle. CYCLE is in the SQL standard and PostgreSQL has had it since version 14.

Making it fast

The recursive term joins on parent_id, and PostgreSQL does not create an index for a foreign key. On a big table, add CREATE INDEX ON categories (parent_id), or every round scans the whole table.

Common mistakes

• Forgetting the stop condition, or writing one that data can never meet.
• Using UNION instead of UNION ALL to hide duplicates. It works for plain rows, but it compares whole rows and slows each round, and it does not help when you carry a depth or a path.
• Adding no index on the parent column.
• Trusting that the data has no loops. Use CYCLE, or a depth limit, on data that people can edit.
• Using a recursive CTE for a fixed number of levels. A plain self-join is simpler there.

If you skip this, you will write one join for each level that exists today, and the first new level will quietly drop its rows from every report. What is the deepest level of nesting in your own data, and who is allowed to make it deeper?