vvek

Recursive queries in Postgres: walk a tree with WITH RECURSIVE, and stop it from looping forever

How WITH RECURSIVE works, how to walk org charts and folder trees, the SEARCH and CYCLE clauses, and when CTEs are materialized in Postgres.

Some data is a tree: folders inside folders, comments under comments, an employee who reports to a manager who reports to someone else. A plain JOIN goes one level deep. To go all the way down you would need to know the depth in advance, or run a query per level from your application.

Postgres has a better answer: WITH RECURSIVE. This post shows how it runs, a few patterns you will reuse, and the two things that bite people: infinite loops and unexpected materialization.

Start with plain CTEs

A WITH clause defines a named step for one query, called a common table expression (CTE). It lets you replace nested subqueries with a readable sequence:

WITH regional_sales AS (
    SELECT region, SUM(amount) AS total_sales
    FROM orders
    GROUP BY region
), top_regions AS (
    SELECT region
    FROM regional_sales
    WHERE total_sales > (SELECT SUM(total_sales) / 10 FROM regional_sales)
)
SELECT region, product, SUM(quantity) AS units
FROM orders
WHERE region IN (SELECT region FROM top_regions)
GROUP BY region, product;

Each name is available to the steps after it and to the final query. If you like this style, our posts on window functions build on the same habit of breaking a question into pieces.

How a recursive CTE runs

A recursive CTE has a fixed shape: a starting query, then UNION or UNION ALL, then a query that refers to the CTE itself.

WITH RECURSIVE t(n) AS (
    VALUES (1)
  UNION ALL
    SELECT n + 1 FROM t WHERE n < 100
)
SELECT sum(n) FROM t; -- 5050

Postgres evaluates it in a loop, using a working table:

  1. Run the starting query. Its rows go into the working table (and into the result).
  2. Run the recursive part against the working table. Its output becomes the new working table.
  3. Repeat until the recursive part returns no rows.
flowchart TD
  A[Run the starting query] --> B[Rows go to the result and the working table]
  B --> C[Run the recursive part on the working table]
  C -->|new rows| B
  C -->|no rows| D[Done]

Only the recursive part may mention the CTE's own name. The condition n < 100 is what ends it: eventually the recursive part returns nothing.

A real example: an org chart

Say you have an employees table with id, name and manager_id. To list everyone under a given manager, with their depth:

WITH RECURSIVE reports AS (
    SELECT id, name, manager_id, 1 AS depth
    FROM employees
    WHERE id = 42
  UNION ALL
    SELECT e.id, e.name, e.manager_id, r.depth + 1
    FROM employees e
    JOIN reports r ON e.manager_id = r.id
)
SELECT * FROM reports ORDER BY depth, name;

The same shape works for categories, folder paths, bill-of-materials lists and threaded comments. Walking upward is the same query with the join reversed: start from a leaf and join on e.id = r.manager_id.

Tip

Put an index on the column you join with in the recursive step (manager_id here). The recursive part runs once per level, and without an index every level scans the table. See reading EXPLAIN ANALYZE to check what the plan really does.

UNION or UNION ALL

UNION ALL keeps every row and is cheaper. UNION removes duplicate rows, including rows that duplicate any earlier result row, and that can end some cycles.

The danger of UNION ALL is data that loops. If employee A reports to B and B (by mistake) reports to A, the query never reaches an empty step, and it runs until you cancel it or run out of resources.

Stopping cycles properly: the CYCLE clause

Plain UNION only helps when whole rows repeat. In the org chart, the depth column changes every time, so rows never look identical. Postgres has a dedicated clause for this:

WITH RECURSIVE search_graph(id, link, data, depth) AS (
    SELECT g.id, g.link, g.data, 1
    FROM graph g
  UNION ALL
    SELECT g.id, g.link, g.data, sg.depth + 1
    FROM graph g, search_graph sg
    WHERE g.id = sg.link
) CYCLE id SET is_cycle USING path
SELECT * FROM search_graph;

CYCLE id SET is_cycle USING path adds two columns: a flag that says whether the row closed a loop, and an array of the values visited so far. Recursion stops at a loop instead of continuing. For a key made of several columns, write ROW(a, b); for a single column, leave ROW out, which is more efficient.

During development, a LIMIT in the outer query can stop a runaway recursion, because Postgres only evaluates the rows the outer query fetches. The documentation warns against relying on that in production, and it often fails once the outer query sorts or joins the result.

Controlling the output order: SEARCH

The result order of a recursive query is not guaranteed to follow the tree. The SEARCH clause adds an ordering column:

WITH RECURSIVE search_tree(id, link, data) AS (
    SELECT t.id, t.link, t.data FROM tree t
  UNION ALL
    SELECT t.id, t.link, t.data
    FROM tree t, search_tree st
    WHERE t.id = st.link
) SEARCH DEPTH FIRST BY id SET ordercol
SELECT * FROM search_tree ORDER BY ordercol;

Use DEPTH FIRST to list each parent followed by its descendants, as you would print a folder listing. Use BREADTH FIRST to list all of one level before the next. Without these clauses you would build a path array or depth counter by hand.

When a CTE is inlined and when it is materialized

Since Postgres 12, a non-recursive CTE that has no side effects and is referenced once is folded into the outer query. That means its filters and indexes work as if you had written a subquery. A CTE referenced more than once is computed once and stored, so the outer query's filters cannot be pushed into it.

You can override either choice:

-- Force inlining, so the filter on key can use an index
WITH w AS NOT MATERIALIZED (SELECT * FROM big_table)
SELECT * FROM w AS w1 JOIN w AS w2 ON w1.key = w2.ref
WHERE w2.key = 123;

MATERIALIZED goes the other way, and is useful when a costly function should run only once.

Data-changing CTEs

INSERT, UPDATE, DELETE and MERGE can appear in a WITH clause. Only the RETURNING output can be used by the rest of the query. A classic use is moving rows atomically:

WITH moved_rows AS (
    DELETE FROM products
    WHERE "date" >= '2010-10-01' AND "date" < '2010-11-01'
    RETURNING *
)
INSERT INTO products_log SELECT * FROM moved_rows;

Each data-changing CTE runs exactly once, to completion, even if the main query ignores its output. They all share one snapshot, so they cannot see each other's changes. The same idea powers the claim step of a Postgres job queue.

A short checklist

  • Name the starting query and the recursive query clearly, and keep the recursive part as small as possible.
  • Index the join column used in the recursive step.
  • Use CYCLE whenever the data could contain loops, even if you believe it cannot.
  • Add SEARCH if the order of the output matters.
  • Check the plan before blaming the CTE: since version 12 many are simply inlined.

Sources

Keep reading

A short email when we publish. Confirm once, unsubscribe any time.