Walking a Hierarchy

Walk parent-child tables — org charts, category trees, comment threads — with a recursive CTE that tracks depth and path.

SyntaxWITH RECURSIVE t (id, parent_id, depth, path) AS (roots UNION ALL SELECT c.id, c.parent_id, t.depth + 1, CONCAT(t.path, ',', c.id) FROM t JOIN tbl c ON c.parent_id = t.id) SELECT ... ORDER BY path

Self-referencing tables — an employees.manager_id, a categories.parent_id, a comments.parent_id — store a tree of unknown depth. A single join reaches one level; a recursive CTE reaches all of them.

The shape

The anchor selects the roots, usually WHERE parent_id IS NULL, or one specific node when you want a subtree. The recursive half joins the base table back to the CTE on child.parent_id = cte.id, and carries two extra columns that make the result usable:

  • depth — 0 in the anchor, depth + 1 in the recursive half. Use it to indent, or to cut the walk off at a level.
  • path — the ancestor ids concatenated. Ordering by the path is what produces tree order rather than arbitrary order; filtering on it gives you ancestor and subtree tests.

Direction

Joining child.parent_id = cte.id walks down from a root. Swap it to cte.parent_id = parent.id and start the anchor at a leaf to walk up the ancestor chain — the same query, reversed.

What trips people up

The path column is sized by the anchor, so CAST(id AS CHAR(200)) in the anchor, not a bare id. Index the parent column; without it every iteration is a full scan. And remember the recursive half cannot use ORDER BY or aggregates — sort and aggregate in the outer SELECT.

Example

Example · sql
CREATE TABLE employees (
    id         INT PRIMARY KEY NOT NULL,
    name       VARCHAR(100) NOT NULL,
    manager_id INT NULL,
    INDEX (manager_id),                    -- without this, every level is a table scan
    FOREIGN KEY (manager_id) REFERENCES employees (id)
);

-- Whole org chart, in tree order, indented by level.
WITH RECURSIVE org (id, name, manager_id, depth, path) AS (
    SELECT id, name, manager_id,
           0,
           CAST(id AS CHAR(200))           -- CAST sizes the path column for all levels
    FROM employees
    WHERE manager_id IS NULL               -- anchor: the roots
    UNION ALL
    SELECT e.id, e.name, e.manager_id,
           o.depth + 1,
           CONCAT(o.path, ',', e.id)
    FROM org AS o
    JOIN employees AS e ON e.manager_id = o.id
)
SELECT CONCAT(REPEAT('    ', depth), name) AS chart,
       depth,
       path
FROM org
ORDER BY path;                             -- path order is tree order

When to use it

  • Render an org chart with every report under a given manager.
  • Build a breadcrumb trail by walking a category up to its root.
  • Return a comment thread already in display order and indentation.
  • Roll up counts or totals from leaf nodes to every ancestor category.

More examples

One subtree, depth-limited

Changing the anchor from 'all roots' to 'one row' is the whole difference between a full walk and a subtree walk. Put the depth test in the recursive SELECT, not the outer query — an outer filter still pays for every level.

Example · sql
-- Everyone under manager 29, no more than three levels down.
WITH RECURSIVE reports (id, name, depth) AS (
    SELECT id, name, 0
    FROM employees
    WHERE id = 29                       -- anchor is a single node, not the roots
    UNION ALL
    SELECT e.id, e.name, r.depth + 1
    FROM reports AS r
    JOIN employees AS e ON e.manager_id = r.id
    WHERE r.depth < 3                   -- the brake lives in the recursive half
)
SELECT * FROM reports WHERE id <> 29;   -- drop the anchor row itself

Walking up: the ancestor chain of one node

Same query, opposite direction: the join condition follows parent_id upward instead of downward. The outer GROUP_CONCAT does the ordering and aggregation, because the recursive half is not allowed either.

Example · sql
-- Breadcrumb trail for a category page.
WITH RECURSIVE ancestors (id, name, parent_id, depth) AS (
    SELECT id, name, parent_id, 0
    FROM categories
    WHERE id = 4177                     -- start at the leaf
    UNION ALL
    SELECT c.id, c.name, c.parent_id, a.depth + 1
    FROM ancestors AS a
    JOIN categories AS c ON c.id = a.parent_id   -- join reversed: follow the parent
)
SELECT GROUP_CONCAT(name ORDER BY depth DESC SEPARATOR ' > ') AS breadcrumb
FROM ancestors;

Threaded comments in display order

Zero-padding each id before concatenating is what makes the path sort correctly — with raw ids, '10' sorts before '9'. This gives a template a pre-ordered, pre-indented list, so the application never has to reassemble the tree in memory.

Example · sql
WITH RECURSIVE thread (id, body, depth, sort_path) AS (
    SELECT id, body, 0,
           CAST(LPAD(id, 10, '0') AS CHAR(600))   -- fixed width so string order = id order
    FROM comments
    WHERE post_id = 91 AND parent_id IS NULL
    UNION ALL
    SELECT c.id, c.body, t.depth + 1,
           CONCAT(t.sort_path, '/', LPAD(c.id, 10, '0'))
    FROM thread AS t
    JOIN comments AS c ON c.parent_id = t.id
)
SELECT depth, CONCAT(REPEAT('  ', depth), body) AS rendered
FROM thread
ORDER BY sort_path;

Related

sql recursive ctesql self joinsql group concatsql withsql create index

Discussion

  • Be the first to comment on this lesson.