Recursive CTEs for Fun and Profit

Strategies for dealing with self-referencing data structures in Postgres

Oct 18, 2023

Have you ever dealt with a data structure that looked like this?

employee.ts

type Employee = {
  id: number;
  name: string;
  title: string;
  manager?: Employee;
  reports: Employee[];
}

This data structure is self-referencing. That is, it may reference others of its own type, if, for example, we need to reference an Employee’s manager or find one of their direct reports.

I use Typescript above for simplicity of type definitions, but because data storage mostly happens in the database in production environments (I hope), let’s translate this into the definition of a table. We’ll use Postgres-flavored SQL for this exercise, these same concepts will translate into roughly equivalent MySQL or SQLite.

create-employees.sql

CREATE TABLE employees (
  id SERIAL PRIMARY KEY,
  name VARCHAR(255) NOT NULL,
  title VARCHAR(255) NOT NULL,
  manager_id INT REFERENCES employees(id)
);

Great! So what do you do if you need to find the name and title of someone’s skip-level manager (i.e. your manager’s manager)? Wrong answers first!

find-skip-level.ts

async function getSkipLevel(employee_id: number): Employee | null {
  const employee = await db.query(`SELECT * FROM employees WHERE id = :employee_id`,
    { employee_id }
  );

  const skipCount = 0;
  let manager: Employee | null = employee;
  do {
    manager = await db.query(`SELECT * FROM employees WHERE id = :manager_id`,
      { manager_id: employee.id }
    );
    skipCount++;
  } while(skipCount < 2 && !== null);

  return manager;
}

Why is this a wrong answer? Well, besides the pseudo-database code, it is also a perfect example of an N+1 query. That is, a querying pattern where you make one initial query, and one additional query for every item of some iterator that you need to gather data on.

N+1 queries are bad becuase, in general, it takes more time to go back and forth from the database, with the wire time, serialization and deserialization, than the database spends actually performing your query. It would be much better to do this as one query.

Recursive CTEs

Recursive CTEs (Common Table Expressions) are a simple way to traverse self-referencing data with ease.

Wait, what’s a CTE?

Common Table Expressions help you write cleaner, more expressive queries by allowing you to construct one or more psuedo-tables in the scope of the query, that you can select from later. Here’s an example:

query.sql

ddl.sql

-- Wrap that Big Nasty Join™ into a CTE
with user_page_views as (
  select
  	users.id as user_id
  	, page_views.event_time
  	, page_views.page_path
  from page_views
  	inner join sessions on sessions.id = page_views.session_id
  	inner join users on users.id = sessions.user_id
)

-- And get a nice clean querying interface later!
select
 	page_path
    , date_trunc('day', event_time) as day
    , count(distinct user_id)
from user_page_views
group by 1, 2

CREATE TABLE users (
  ID serial PRIMARY KEY
  , name varchar(255)
);

CREATE TABLE sessions (
  ID serial PRIMARY KEY
  , started_at timestamptz
  , user_id INT REFERENCES users(id)
);

CREATE TABLE page_views (
  id SERIAL PRIMARY KEY
  , page_path varchar(255)
  , event_time timestamptz
  , session_id INT REFERENCES sessions(id)
);

INSERT INTO USERS (name) VALUES ('steve');
INSERT INTO SESSIONS (started_at, user_id) VALUES (now(), 1);
INSERT INTO page_views (page_path, session_id, event_time)
    VALUES  ('/', 1, now()),
            ('/pricing', 1, now());

So what would the SQL look like to replace our code above?

find-skip-level.sql

-- declare CTE as RECURSIVE
with RECURSIVE employee_managers as (
-- this is the base query
  select * from employees
  	where id = 4

-- The recursive part: create a UNION
-- that recursively joins a table to the CTE
  UNION ALL
  select employees.*
  from employees
-- note that we are JOINING to the CTE, not the table
  	JOIN employee_managers on employees.id = employee_managers.manager_id
),
-- Add the employee rank as their depth from the top, using ROW_NUMBER()
employee_chain as (
  select
      employee_managers.*
      , (ROW_NUMBER() OVER ()) - 1 as skip_count -- subtract 1 (postgres is 1-indexed!)
  from employee_managers
)

-- Now we can query the CTE to find the skip level
select * from employee_chain
where skip_count = 2;

🗣️ Send me a howler

Have a comment on this post, something to point out, or just want to say hi? Take a deep breath, count to ten, and then put it in writing to stevendcoffey@gmail.com 😌

Footnotes

In this post

Recursive CTEs