How to write SQL recursive CTE in 5 steps

Franck Pachot - Dec 17 '21 - - Dev Community

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:

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)
;
Enter fullscreen mode Exit fullscreen mode

The self reference from mgr to empno can be declared as:

ALTER TABLE emp ADD PRIMARY KEY (empno)
;
ALTER TABLE emp ADD FOREIGN KEY (mgr) REFERENCES emp (empno)
;
Enter fullscreen mode Exit fullscreen mode

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)

-- (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
;
Enter fullscreen mode Exit fullscreen mode

The result is simple:

yugabyte-> ;

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

yugabyte=>
Enter fullscreen mode Exit fullscreen mode

(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:

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
;
Enter fullscreen mode Exit fullscreen mode

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=>
Enter fullscreen mode Exit fullscreen mode

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:

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
;
Enter fullscreen mode Exit fullscreen mode

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=>
Enter fullscreen mode Exit fullscreen mode

(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.

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
;
Enter fullscreen mode Exit fullscreen mode

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=>
Enter fullscreen mode Exit fullscreen mode

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.

-- (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
Enter fullscreen mode Exit fullscreen mode

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=>
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

The number of loops tells you how many time the second part was executed. All this runs the same in PostgreSQL and 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.

Image
10 Best SDDM Themes available for Linux

linux, opensource, bash, shell
Image
Hacking Cookies and PWA on Ubuntu

ubuntu, cookies, pwa, gnome
Image
RAG Pipeline Permissions for iPaaS Platforms

ai, rag, permissions, saas
Image
postgres.new: In-browser Postgres with an AI interface

webdev, programming, ai, opensource
Image
Learning Ruby Core Concepts Part 1
Image
Is Cash App Safe for Sending Money?
Image
Why Is Apple So Popular?
Image
How Secure is PayPal for Your Transactions?
Image
Rails Guides 7.2 in Spanish Translated with OpenAI

rails, openai, spanish, softwaredevelopment
Image
Build a Web App with Oats~i – Lesson 1: Fragments, Routing, and Default Routes

webdev, javascript, programming, tutorial
Image
Hardhat vs. Foundry: Which Is Better, or Should You Use Them Hand in Hand?

ethereum, blockchain, solidity, web3
Image
Discover Navy Federal’s Top Benefits
Image
Why Wayfair Shines Among Furniture Retailers
Image
How to Implement Multitenancy in ASP.NET Core with EF Core

programming, efcore, dotnet, aspnetcore
Image
Volume Testing With Apache Jmeter On Windows.

devops, sre, java
Image
Reminder about Friendly.rb - one month to the conference

techtalks, ruby, rails
Image
Why Do So Many People Choose DoorDash?
Image
This is the last Glitch newsletter I am posting here (not clickbait)

glitch, javascript, apps, codejam
Image
Prefill Pen

codepen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Terabox Video Player