How to write SQL recursive CTE in 5 steps
Tags: postgres, yugabytedb, sql, database
Published: 2021-12-17 16:53:04

You don't need a Graph database to follow a hierarchy of nodes. SQL can do joins, self-join, and even joins to its previous result, iteratively. This `WITH RECURSIVE` clause is often called "Recursive CTE". This might require a bit of abstraction for the developers used to procedural languages. Here is how I explain it by joining "manually" the two first levels, without recursion, and then switching to "recursive" to go further. Starting with the first two levels helps to validate the logic easily. The example below is standard SQL, I have run it in YugabyteDB, which is PostgreSQL compatible.

## (0) Example: create the EMP table
I'll create the oldest sample table: EMP for employees with a self-reference to the manager:
```sql
CREATE TABLE emp (empno, ename,    job,        mgr,   hiredate,     sal, comm, deptno, email, other_info) as values
(7369, 'SMITH',  'CLERK',     7902, '1980-12-17',  800, NULL,   20,'SMITH@acme.com', '{"skills":["accounting"]}'),
(7499, 'ALLEN',  'SALESMAN',  7698, '1981-02-20', 1600,  300,   30,'ALLEN@acme.com', null),
(7521, 'WARD',   'SALESMAN',  7698, '1981-02-22', 1250,  500,   30,'WARD@compuserve.com', null),
(7566, 'JONES',  'MANAGER',   7839, '1981-04-02', 2975, NULL,   20,'JONES@gmail.com', null),
(7654, 'MARTIN', 'SALESMAN',  7698, '1981-09-28', 1250, 1400,   30,'MARTIN@acme.com', null),
(7698, 'BLAKE',  'MANAGER',   7839, '1981-05-01', 2850, NULL,   30,'BLAKE@hotmail.com', null),
(7782, 'CLARK',  'MANAGER',   7839, '1981-06-09', 2450, NULL,   10,'CLARK@acme.com', '{"skills":["C","C++","SQL"]}'),
(7788, 'SCOTT',  'ANALYST',   7566, '1982-12-09', 3000, NULL,   20,'SCOTT@acme.com', '{"cat":"tiger"}'),
(7839, 'KING',   'PRESIDENT', NULL, '1981-11-17', 5000, NULL,   10,'KING@aol.com', null),
(7844, 'TURNER', 'SALESMAN',  7698, '1981-09-08', 1500,    0,   30,'TURNER@acme.com', null),
(7876, 'ADAMS',  'CLERK',     7788, '1983-01-12', 1100, NULL,   20,'ADAMS@acme.org', null),
(7900, 'JAMES',  'CLERK',     7698, '1981-12-03',  950, NULL,   30,'JAMES@acme.org', null),
(7902, 'FORD',   'ANALYST',   7566, '1981-12-03', 3000, NULL,   20,'FORD@acme.com', '{"skills":["SQL","CQL"]}'),
(7934, 'MILLER', 'CLERK',     7782, '1982-01-23', 1300, NULL,   10,'MILLER@acme.com', null)
;

```
The self reference from mgr to empno can be declared as:
```sql
ALTER TABLE emp ADD PRIMARY KEY (empno)
;
ALTER TABLE emp ADD FOREIGN KEY (mgr) REFERENCES emp (empno)
;
```
This is not needed but it ensures the correctness of that that you query so that you can focus on your business logic rather than consistency test.

## (1) find the root (level 0)

The first step is to identify the root of the graph. Do you want to start by the employees and show their manager, or start by the mangager and show its employees? I'll do the latter. The root of the hierarchy is the one with no manager (`where mgr is null`)

```sql
-- (1) query to find the root
select emp.empno,emp.ename,emp.mgr
from emp where mgr is null           -- (1) this is the level 0
;
```

The result is simple:
```
yugabyte-> ;

 empno | ename | mgr
-------+-------+-----
  7839 | KING  |
(1 row)

yugabyte=>
```

## (2) define this level 0 in the WITH clause

I'll put it in a CTE (Common Table Expression), labelled as `levelN`, but until we add recursion it is level 0, and I select from it:

```sql
with
-- (2) define the root as as levelN (which is level 0 until we add recursion)
levelN as (
-- (1) query to find the root
select emp.empno,emp.ename,emp.mgr
from emp where mgr is null           -- (1) this is the level 0
) 
-- (2) query this level
select * from levelN
;
```

The result is the same. The top manager is KING. We just named it and put it in a WITH clause to prepare for future recursion.
```
yugabyte-> ;

 empno | ename | mgr
-------+-------+-----
  7839 | KING  |
(1 row)

yugabyte=>
```
I'm just building the blocks one by one. And I've left the comments to make it clear what is taken from the previous step and what is added.

### (3) define the join to the next level

Now that my level 0 is defined, I query the `emp` table again, to get the next level, with a join to level 0 to get the manager name: 

```sql
with 
-- (2) define the root as as levelN which is level 0 until we add recursion
levelN as (
-- (1) query to find the root
select emp.empno,emp.ename,emp.mgr
from emp where mgr is null           -- (1) this is the level 0
) 
-- (3) join employees with levelN to get level N+1 (which is level 1 here)
select emp.empno,emp.ename,emp.mgr,mgr.ename mgr_name
from emp
join levelN mgr on mgr.empno=emp.mgr
;
```

I have aliased the level 0 as `mgr` because it will be the manager of this new level of employee, for which I keep the table name `emp`. Then the join on `mgr.empno=emp.mgr` links the two levels. 

In the join result, I have added `mgr.ename` as `mgr_name` in order to see the name of the manager in the same line.

So here here are the employees reporting to KING:
```
yugabyte-> ;

 empno | ename | mgr  | mgr_name
-------+-------+------+----------
  7698 | BLAKE | 7839 | KING
  7566 | JONES | 7839 | KING
  7782 | CLARK | 7839 | KING
(3 rows)

yugabyte=>
```

## (4) concatenate the two levels with UNION

Now that I have two levels, I can start to build the hierarchy by concatenating them with a UNION ALL. You see `levelN`, wich is the level 0, in the first branch of the UNION, to show the level 0 and in the second branch to join the two levels.

Because I have added the manager name to the level 1, I add it also in the level zero, as an empty string here, in order to have the same structure in the UNION.

```sql
with 
-- (2) define the root as as levelN which is level0 until we add recursion
levelN as (
-- (1) query to find the root      --(4) add all columns
select emp.empno,emp.ename,emp.mgr,'' as mgr
from emp where mgr is null           -- (1) this is the level 0
) 
-- (4) concatenate level 0 on top of level l
select * from levelN  
union all
-- (3) join employees with level n to get level n+1 (which is level 1 here)
select emp.empno,emp.ename,emp.mgr,mgr.ename mgr_name
from emp
join levelN mgr on mgr.empno=emp.mgr
;
```

This starts to look good, here are the two levels together:
```
yugabyte-> ;

 empno | ename | mgr  | mgr_name
-------+-------+------+----------
  7839 | KING  |      |
  7698 | BLAKE | 7839 | KING
  7566 | JONES | 7839 | KING
  7782 | CLARK | 7839 | KING
(4 rows)

yugabyte=>
```

This is where you can validate that your join is correct.

The next step will just add recursion so that you don't need to do the same to add the level 3. The same definition (UNION ALL and JOIN from the previous level) can get to the next levels.

## (5) get it in one recursive WITH clause

Now that I have validated the result for the two first levels, it is time to get it recursive by adding the RECURSIVE keyword and moving the UNION ALL into the Common Table Expression. The first part of the UNION ALL is executed only once in the first iteration, but the second part will concatenate the next level.

```sql
-- (5) change to recursive 
with recursive
-- (2) define the root as as levelN which is level0 until we add recursion
levelN as (
-- (1) query to find the root      --(4) add all columns
select emp.empno,emp.ename,emp.mgr,'' as mgr
from emp where mgr is null           -- (1) this is the level 0
-- (5) move second branch into the CTE which is the one that will be iterated. It references levelN  from the previous iteration.
union all
-- (3) join employees with level n to get level n+1 (which is level 1 here)
select emp.empno,emp.ename,emp.mgr,mgr.ename mgr_name
from emp
join levelN mgr on mgr.empno=emp.mgr
) 
-- (4) concatenate level 0 on top of level l
select * from levelN
-- (5) we query only from levelN here, which includes the previous levels thanks to the recursion  
```


If you have validated the join with the first two level, this last transformation is automatic. At execution time, the first iteration will get the first level and the second part of the UNION ALL will have no rows because of the join with the previous result, which is empty (there is no previous level). The next iteration will add the result of the join. And again until the join returns no rows because we are at a leaf, with the previous result, taken as a list of managers, has no employees.

```
yugabyte-> ;

 empno | ename  | mgr  | mgr_name
-------+--------+------+----------
  7839 | KING   |      |
  7698 | BLAKE  | 7839 | KING
  7566 | JONES  | 7839 | KING
  7782 | CLARK  | 7839 | KING
  7788 | SCOTT  | 7566 | JONES
  7902 | FORD   | 7566 | JONES
  7844 | TURNER | 7698 | BLAKE
  7499 | ALLEN  | 7698 | BLAKE
  7521 | WARD   | 7698 | BLAKE
  7654 | MARTIN | 7698 | BLAKE
  7900 | JAMES  | 7698 | BLAKE
  7934 | MILLER | 7782 | CLARK
  7876 | ADAMS  | 7788 | SCOTT
  7369 | SMITH  | 7902 | FORD
(14 rows)

yugabyte=>
```
This is where the magic is. If you carefully test your first two levels, all others will come by transforming the query to be recursive, iterating by joining on its previous result. 
In the execution plan, you see it as Recursive union

```
                                                              QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
 CTE Scan on leveln  (cost=20.23..22.86 rows=131 width=72) (actual time=0.023..0.281 rows=14 loops=1)
   CTE leveln
     ->  Recursive Union  (cost=0.00..20.23 rows=131 width=46) (actual time=0.021..0.269 rows=14 loops=1)
           ->  Seq Scan on emp  (cost=0.00..1.14 rows=1 width=46) (actual time=0.019..0.021 rows=1 loops=1)
                 Filter: (mgr IS NULL)
           ->  Hash Join  (cost=0.33..1.65 rows=13 width=46) (actual time=0.054..0.058 rows=3 loops=4)
                 Hash Cond: (emp_1.mgr = mgr.empno)
                 ->  Seq Scan on emp emp_1  (cost=0.00..1.14 rows=14 width=14) (actual time=0.002..0.003 rows=14 loops=4)
                 ->  Hash  (cost=0.20..0.20 rows=10 width=36) (actual time=0.044..0.044 rows=4 loops=4)
                       ->  WorkTable Scan on leveln mgr  (cost=0.00..0.20 rows=10 width=36) (actual time=0.001..0.001 rows=4 loops=4)
```
The number of `loops` tells you how many time the second part was executed. All this runs the same in PostgreSQL and [YugabyteDB](https://www.yugabyte.com/yugabytedb/). Here is the example on db<>fiddle: https://dbfiddle.uk/sChh3Y09

A final remark: the declaration is recursive but the execution is iterative, with a loop until no rows are returned.