Walk a Tree With a Recursive CTE

A table where each row points at its parent: employees and managers, folders, comment replies, parts and sub-parts. One query cannot follow the chain to an unknown depth, because a join goes one step. A recursive CTE repeats a step until it runs out of rows. This page walks down from a manager to everyone below, walks up from an employee to the top, counts every manager's team, and then protects the query from a loop in the data.

Step 1: nine employees

manager_id points back at emp_id in the same table, and the top person has no manager.

CREATE TABLE employees (
  emp_id     int PRIMARY KEY,
  name       text NOT NULL,
  manager_id int REFERENCES employees (emp_id)
);
INSERT INTO employees VALUES
  (1, 'Maya Cruz',  NULL),
  (2, 'Omar Reyes', 1), (3, 'Lena Park',  1),
  (4, 'Ravi Das',   2), (5, 'Tina Lopez', 2), (6, 'Sam Ortiz', 3),
  (7, 'Uma Diaz',   4), (8, 'Vic Tan',    4), (9, 'Wes Lim',   6);

CREATE TABLE
INSERT 0 9

Step 2: walk down from one manager

A recursive CTE has two parts joined by UNION ALL. The first part is the starting row, here Omar Reyes. The second part joins the table to the rows found so far, and PostgreSQL repeats it until it returns nothing. level counts the steps, and path keeps the ids from the start, so the result can be sorted as a tree.

WITH RECURSIVE team AS (
  SELECT emp_id, name, 1 AS level, ARRAY[emp_id] AS path
  FROM employees
  WHERE emp_id = 2
  UNION ALL
  SELECT e.emp_id, e.name, t.level + 1, t.path || e.emp_id
  FROM employees AS e
  JOIN team AS t ON e.manager_id = t.emp_id
)
SELECT repeat('  ', level - 1) || name AS org, level
FROM team
ORDER BY path;

     org      | level
--------------+-------
 Omar Reyes   |     1
   Ravi Das   |     2
     Uma Diaz |     3
     Vic Tan  |     3
   Tina Lopez |     2
(5 rows)

Sorting by the id path puts every person right after their manager. repeat indents by level, so the output reads like an org chart.

Step 3: walk up to the top

To go the other way, join on the opposite columns: the next row is the one whose emp_id equals the current row's manager_id.

WITH RECURSIVE chain AS (
  SELECT emp_id, name, manager_id, 0 AS up
  FROM employees
  WHERE emp_id = 9
  UNION ALL
  SELECT e.emp_id, e.name, e.manager_id, c.up + 1
  FROM employees AS e
  JOIN chain AS c ON e.emp_id = c.manager_id
)
SELECT up, name FROM chain ORDER BY up;

 up |   name
----+-----------
  0 | Wes Lim
  1 | Sam Ortiz
  2 | Lena Park
  3 | Maya Cruz
(4 rows)

That is the chain of command for Wes Lim: Sam Ortiz, then Lena Park, then Maya Cruz at the top.

Step 4: count every manager's team

Start the walk from every employee at once, and remember where each walk started in root. Then count how many rows each root reached, minus the root itself.

WITH RECURSIVE tree AS (
  SELECT emp_id AS root, emp_id FROM employees
  UNION ALL
  SELECT t.root, e.emp_id
  FROM employees AS e
  JOIN tree AS t ON e.manager_id = t.emp_id
)
SELECT m.name, count(*) - 1 AS reports
FROM tree AS t
JOIN employees AS m ON m.emp_id = t.root
GROUP BY m.emp_id, m.name
HAVING count(*) > 1
ORDER BY reports DESC, m.name;

    name    | reports
------------+---------
 Maya Cruz  |       8
 Omar Reyes |       4
 Lena Park  |       2
 Ravi Das   |       2
 Sam Ortiz  |       1
(5 rows)

Maya has eight people below her, which is everyone else. Omar has four: Ravi, Tina, Uma and Vic. The HAVING clause leaves out people with no reports.

Step 5: stop on bad data

Someone edits a row, and Maya now reports to Wes, who reports to Sam, who reports to Lena, who reports to Maya. The data has a cycle. A recursive CTE on it never runs out of rows, so the query runs until the server stops it.

UPDATE employees SET manager_id = 9 WHERE emp_id = 1;

UPDATE 1

Add the CYCLE clause. PostgreSQL remembers the value of emp_id on every path, and when a row would repeat one, it marks that row in a new column and stops following it.

WITH RECURSIVE team AS (
  SELECT emp_id, name, manager_id
  FROM employees
  WHERE emp_id = 1
  UNION ALL
  SELECT e.emp_id, e.name, e.manager_id
  FROM employees AS e
  JOIN team AS t ON e.manager_id = t.emp_id
) CYCLE emp_id SET is_loop USING walked
SELECT emp_id, name, is_loop
FROM team
ORDER BY is_loop, emp_id;

 emp_id |    name    | is_loop
--------+------------+---------
      1 | Maya Cruz  | f
      2 | Omar Reyes | f
      3 | Lena Park  | f
      4 | Ravi Das   | f
      5 | Tina Lopez | f
      6 | Sam Ortiz  | f
      7 | Uma Diaz   | f
      8 | Vic Tan    | f
      9 | Wes Lim    | f
      1 | Maya Cruz  | t
(10 rows)

The last row is the proof: Maya Cruz appears a second time with is_loop true, so the walk came back to where it started and stopped there. To find the broken rows, select WHERE is_loop and look at the people on that path.

Related course: SQL Advanced.