Recursive CTEs: trees and graphs

A tree in a table

The shop’s product categories could be grouped into a hierarchy, stored the usual way: each row points to its parent.

CREATE TEMP TABLE category_tree (name text PRIMARY KEY, parent text);
INSERT INTO category_tree VALUES
  ('All products', NULL),
  ('Computer gear', 'All products'), ('Home office', 'All products'),
  ('Accessories', 'Computer gear'), ('Displays', 'Computer gear'), ('Storage', 'Computer gear'),
  ('Audio', 'Computer gear'), ('Video', 'Computer gear'), ('Furniture', 'Home office');

“Everything under Computer gear” needs the children, then their children, then theirs, for as many levels as there are. Ordinary joins can only go a fixed number of levels deep.

How a recursive CTE runs

WITH RECURSIVE tree AS (
  -- 1. the starting rows
  SELECT name, parent, 0 AS depth, name AS path
  FROM category_tree WHERE parent IS NULL
  UNION ALL
  -- 2. the step: rows whose parent is in the previous level
  SELECT c.name, c.parent, t.depth + 1, t.path || ' > ' || c.name
  FROM category_tree c
  JOIN tree t ON c.parent = t.name
)
SELECT repeat('  ', depth) || name AS category, depth
FROM tree ORDER BY path;

    category     | depth
-----------------+-------
 All products    |     0
   Computer gear |     1
     Accessories |     2
     Audio       |     2
     Displays    |     2
     Storage     |     2
     Video       |     2
   Home office   |     1
     Furniture   |     2

PostgreSQL runs the first part once, then runs the second part against only the rows found in the previous round, adds what it finds, and repeats until a round finds nothing. Here that is three rounds that find rows (the root, its two children, their six children) and a fourth that finds none.

Walking up is the same idea with the join reversed. The ancestors of Storage:

WITH RECURSIVE up AS (
  SELECT name, parent FROM category_tree WHERE name = 'Storage'
  UNION ALL
  SELECT c.name, c.parent FROM category_tree c JOIN up ON c.name = up.parent
)
SELECT name FROM up;    -- Storage, Computer gear, All products

When the data has a loop

ERROR:  canceling statement due to statement timeout

The CYCLE clause makes PostgreSQL track the path and stop when a row repeats:

WITH RECURSIVE tree AS (
  SELECT name, parent, 0 AS depth FROM category_tree WHERE name = 'Computer gear'
  UNION ALL
  SELECT c.name, c.parent, t.depth + 1
  FROM category_tree c JOIN tree t ON c.parent = t.name
) CYCLE name SET is_cycle USING path
SELECT name, depth, is_cycle FROM tree ORDER BY depth, name;

     name      | depth | is_cycle
---------------+-------+----------
 Computer gear |     0 | f
 Accessories   |     1 | f
 …
 Computer gear |     2 | t

The query finishes and marks the row where the loop closed, so you can find and fix the bad data.

Check yourself

1. What are the two parts of a recursive CTE, and how often does each run?

   Show answer

   The starting (non-recursive) part runs once. The recursive part runs repeatedly, each time against the rows the previous round produced, until a round produces no rows.

   I could explain this without looking

2. Why did the cyclic category tree make the query run forever?

   Show answer

   Each round found the starting category again through the loop, so a new round always had rows to work on, and with a growing depth the rows never repeated exactly.

   I could explain this without looking

3. What does CYCLE name SET is_cycle USING path do?

   Show answer

   It tracks the name values visited along each path, stops following a path when a name repeats, and marks that row with is_cycle = true.

   I could explain this without looking