Recursive CTEs: SQL’s Hidden Graph Traversal Engine

When developers run into graph problems, such as working with hierarchies, finding routes between cities, or mapping social network connections, the first reaction is often to grab a specialised tool. We tend to think we need a graph database like Neo4j or a Python library like NetworkX to handle these challenges.

For massive, billion-node graphs, those tools are necessary. But for a substantial percentage of operational data, e.g. supply chains with a few thousand nodes, organisational charts, or navigation paths, introducing a new database engine can be architectural overkill.

Your current relational database can likely already handle most graph problems just fine. The key is a feature that has been in the SQL standard since 1999 but still isn’t widely used: Recursive Common Table Expressions (CTEs).

This article shows how to do graph traversal, pathfinding, and cycle detection using only standard SQL.

Prerequisites

If you want to try these examples, you’ll need access to a modern relational database like Postgres, Oracle, or MySQL.

I’ll use SQLite on my local computer for the examples. Keep in mind that the exact SQL syntax may vary slightly depending on your database.

A Quick Refresher on Standard CTEs

Before diving into recursive common table expressions, let’s review what a regular, non-recursive CTE does.

A Common Table Expression is a temporary result set you define within a single SELECT, INSERT, UPDATE, or DELETE statement. You can think of it as a named subquery or a temporary view that only exists while the query runs.

The main reason to use CTEs is to make queries more straightforward to read. They help you break up complex logic into clear, step-by-step parts. Instead of writing messy queries full of subqueries, you can organise your logic in named sections at the top. For complex SQL, you can also reuse the same CTE more than once in a statement.

Consider a simple sales table.

CREATE TABLE sales (id SERIAL PRIMARY KEY,region TEXT,amount INT);INSERT INTO sales (region, amount) VALUES ('North', 100);INSERT INTO sales (region, amount) VALUES ('North', 150);INSERT INTO sales (region, amount) VALUES('South', 200);INSERT INTO sales (region, amount) VALUES ('South', 50);INSERT INTO sales (region, amount) VALUES('East', 300);

We want to find out which region(s) sales are greater than or equal to the average sales of all regions. First, we use a CTE to calculate total sales for each region. Then, we filter these results by comparing each region’s total to the average, which we get from a subquery over the CTE.

WITH region_totals AS (-- Calculate total sales per regionSELECT region, SUM(amount) as total_salesFROM salesGROUP BY region)SELECT region, total_salesFROM region_totalsWHERE total_sales > (SELECT AVG(total_sales) FROM region_totals);-- Output is ...region  total_sales------  -----------East    300

Let’s check. Regional totals are:

North = 250
South = 250
East = 300

The average of these values is 266.67, and yes, only the East region has sales greater than this average.

The WITH region_totals AS (…) block defines the CTE. The subsequent query treats region_totals like it’s a real table. Once the query finishes, the CTE vanishes.

A Recursive CTE takes this concept one step further. Instead of just passing data down to the main query, it can reference itself to generate new rows based on previous rows.

The Anatomy of a Recursive CTE

A Recursive CTE works like a loop inside a query. Unlike a regular SELECT statement that runs once, a recursive CTE keeps running until there’s no more data. It builds the result set step by step.

The syntax is standardised, but the logic requires a mental shift from “set-based” thinking to “iterative” thinking.

Every recursive CTE has the same basic structure: an initial (or anchor) query to start the result set, a recursive query that joins back to itself to add more rows, and a stopping point when there are no more rows to add.

For example,

WITH RECURSIVE graph_cte AS (    -- 1. Initial query to start the result set (The Anchor)    SELECT *    FROM table    WHERE id = 1    UNION ALL    -- 2. Recursive query that joins back to itself to add more rows    SELECT t.*    FROM table t    JOIN graph_cte g ON t.parent_id = g.id        -- 3. Stopping point: The recursion terminates automatically when this JOIN    --    finds no more matches and returns 0 rows.)SELECT * FROM graph_cte;

When you run this, the database engine does a Breadth-First Search (BFS). It runs the anchor query, adds the results to a working table, then uses those results for the recursive step. This repeats until the recursive step returns no more rows.

Example 1. The Organisational Hierarchy (Trees)

The most common graph problem in business software is the tree structure. File systems, comment threads, and organisational charts all model hierarchical relationships, even though the meaning of those relationships differs in each case.

Let’s define a simple employees table.

CREATE TABLE employees (id SERIAL PRIMARY KEY,name TEXT NOT NULL,manager_id INT REFERENCES employees(id),role TEXT);INSERT INTO employees (id, name, manager_id, role) VALUES(1, 'Alice', NULL, 'CEO'),(2, 'Bob', 1, 'VP Engineering'),(3, 'Charlie', 1, 'VP Sales'),(4, 'Dave', 2, 'Backend Lead'),(5, 'Eve', 2, 'Frontend Lead'),(6, 'Frank', 4, 'Junior Dev');select * from employees;id name    manager_id role-- ------- ---------- --------------1  Alice              CEO2  Bob     1          VP Engineering3  Charlie 1          VP Sales4  Dave    2          Backend Lead5  Eve     2          Frontend Lead6  Frank   4          Junior Dev

The problem

We want to create a report that shows every employee, their management path (e.g., “Alice -> Bob -> Dave”), and their depth in the hierarchy.

The SQL Solution

WITH RECURSIVE org_chart AS (    -- Anchor: Start with the Boss (Depth 1)    SELECT        id,        name,        manager_id,        role,        1 AS depth,        name AS path    FROM employees    WHERE manager_id IS NULL    UNION ALL    -- Recursive: Find employees managed by the previous layer    SELECT        e.id,        e.name,        e.manager_id,        e.role,        oc.depth + 1 AS depth,        oc.path || ' -> ' || e.name AS path    FROM employees e    JOIN org_chart oc      ON e.manager_id = oc.id    -- Depth guard to prevent infinite recursion (e.g., cycles)    WHERE oc.depth < 10)SELECT    id,    name,    manager_id,    role,    depth,    pathFROM org_chartORDER BY depth, path;

And here is the output.

id  name     manager_id  role            depth  path--  -------  ----------  --------------  -----  -----------------------------1   Alice                CEO             1      Alice2   Bob      1           VP Engineering  2      Alice -> Bob3   Charlie  1           VP Sales        2      Alice -> Charlie4   Dave     2           Backend Lead    3      Alice -> Bob -> Dave5   Eve      2           Frontend Lead   3      Alice -> Bob -> Eve6   Frank    4           Junior Dev      4      Alice -> Bob -> Dave -> Frank

How this works

The process starts with the anchor query, which selects the top-level employee where manager_id is NULL. This gives us Alice and starts the result set at depth 1, with a path containing just her name.

Next, the recursive query keeps joining the current results back to the employees table using manager_id = id. The first round finds Alice’s direct reports, Bob and Charlie, giving them a depth of 2 and extending their paths. Later rounds keep expanding from the new rows. Bob and Charlie lead to Dave and Eve, and Dave leads to Frank. Each level increases the depth and adds to the path.

Eventually, the recursive step finds no new rows because there are no more employees whose manager_id matches the current set. At that point, the recursion stops. The final result is a flat view of the organisational hierarchy, built step by step by the database engine without any loops in your code.

The end result is a flat view of the organisational hierarchy, built in SQL with a breadth-first recursive query. There’s no need for loops or extra control flow in your application.

Example 2. Pathfinding in a Network (Graphs)

Trees are simple because they only go in one direction, from the top down. Graphs are more complex because they can have cycles and multiple paths.

Let’s look at a transportation network. Unlike an org chart, you can travel from Point A to Point B in several ways, and each connection (like a road or flight) has a weight, such as cost or distance.

CREATE TABLE connections (    origin TEXT,    destination TEXT,    cost INT);INSERT INTO connections VALUES('New York', 'London', 500),('New York', 'Paris', 600),('London', 'Dubai', 400),('Paris', 'Dubai', 350),('Dubai', 'Tokyo', 500),('Paris', 'Tokyo', 800);select * from connections;origin    destination  cost--------  -----------  ----New York  London       500New York  Paris        600London    Dubai        400Paris     Dubai        350Dubai     Tokyo        500Paris     Tokyo        800

The problem

Find all possible routes from New York to Tokyo, and calculate the total cost for each route.

The SQL solution

Here, we need to keep track of state as we recurse. We have to follow the running total cost and the order of cities visited.

WITH RECURSIVE travel_planner AS (    -- Anchor: Flights leaving New York    SELECT         origin,        destination,        cost as total_cost,        origin || ' > ' || destination as route,        1 as hops    FROM connections    WHERE origin = 'New York'UNION ALL    -- Recursive: Flights leaving from the previous destination    SELECT         c.origin,        c.destination,        tp.total_cost + c.cost, -- Accumulate cost        tp.route || ' > ' || c.destination, -- Extend route        tp.hops + 1    FROM connections c    JOIN travel_planner tp ON c.origin = tp.destination)SELECT route, total_cost, hops FROM travel_planner WHERE destination = 'Tokyo'ORDER BY total_cost ASC;

How this works

The query uses a recursive CTE to find all possible flight routes from New York to Tokyo, building each route one step at a time.

Anchor phase

The anchor query picks all direct flights leaving New York. Each row is a one-hop route, setting the total cost, route string, and hop count.

Recursive expansion

For each route discovered so far, the recursive member looks for flights whose origin matches the current route’s destination. When a match is found, the query:

• adds the new flight’s cost to the running total,

• appends the destination to the route string,

• increments the hop count.

This process repeats, extending routes one flight at a time, until no further connections can be made.

Result selection

After all possible routes are found, the final SELECT filters for routes ending in Tokyo and sorts them by total cost, so the cheapest routes come first.

The output

route                              total_cost  hops---------------------------------  ----------  ----New York > Paris > Tokyo           1400        2New York > London > Dubai > Tokyo  1400        3New York > Paris > Dubai > Tokyo   1450        3

We’ve basically written a pathfinding algorithm using only SQL. The database engine explores the graph step by step – first New York’s neighbours, then their neighbours – until it finds the destination.

Example 3. Cycle Detection (The Infinite Loop Trap)

The previous flight example assumes the graph is a Directed Acyclic Graph (DAG), so you always move forward. But real-world graphs can have loops. For example, if London connects to Dubai and Dubai connects back to London, the query could get stuck in an infinite loop and run until it hits a memory limit or times out.

To handle general graphs, we need to add cycle detection. This means checking if the node we’re about to visit has already been visited in the current path.

Let us add a loop to our data.

INSERT INTO connections VALUES ('Dubai', 'New York', 900); -- The Loop

If we run the previous query now, it will crash (or run forever). Let’s patch it with cycle detection.

A More Robust SQL Solution

WITH RECURSIVE travel_safe AS (    -- Anchor: start from New York    SELECT        origin,        destination,        cost AS total_cost,        origin || '->' || destination AS path_history,        0 AS is_cycle,        1 AS depth    FROM connections    WHERE origin = 'New York'    UNION ALL    -- Recursive: expand paths    SELECT        c.origin,        c.destination,        ts.total_cost + c.cost AS total_cost,        ts.path_history || '->' || c.destination AS path_history,        CASE            WHEN instr(ts.path_history, c.destination) > 0 THEN 1            ELSE 0        END AS is_cycle,        ts.depth + 1 AS depth    FROM connections c    JOIN travel_safe ts      ON c.origin = ts.destination    WHERE ts.is_cycle = 0          -- stop expanding cyclic paths      AND ts.depth < 10            -- safety brake)SELECT    path_history,    total_cost,    is_cycleFROM travel_safeWHERE destination = 'Tokyo';

And our output

path_history                    total_cost  is_cycle------------------------------  ----------  --------New York->Paris->Tokyo          1400        0New York->London->Dubai->Tokyo  1400        0New York->Paris->Dubai->Tokyo   1450        0

How this works

To make the traversal safe, the query keeps track of the route so far as a text string. Each time a new connection is added, the destination city is added to this path, creating a record of every city visited.

Before extending a route, the recursive step checks if the next destination is already in the path string. If it is, that branch is marked as a cycle and won’t be expanded further. Other branches that aren’t cyclic keep exploring the graph.

In addition to cycle detection, the query also sets a hard depth limit. This acts as a safety brake, ensuring recursion can’t run forever, even if the data contains unexpected loops or very deep chains.

With these checks, the CTE can walk the graph by joining on origin = destination, building longer routes until it reaches Tokyo, finds a cycle, or hits the depth limit. This gives you a graph traversal in SQL with per-path “visited” tracking, using simple strings in SQLite instead of arrays.

In short, the CTE explores the graph by joining connections on c.origin = ts.destination, building longer routes until it reaches Tokyo, finds a cycle, or hits the depth limit. This is a graph traversal with a “visited” check for each path, done in SQLite using strings. For other databases, you get away with using arrays instead.

Example 4. Six Degrees of Separation (Shortest Path)

Sometimes, we don’t care about the exact route, just the distance. In social networks, this is the classic “Six Degrees of Separation” idea, which says everyone is connected to everyone else by at most six people. This idea became famous in the game “Six Degrees of Kevin Bacon,” where the goal is to link the actor Kevin Bacon to another actor through the shortest path of connections.

So, given two people, can we figure out what the shortest chain of friends is connecting them?

Because Recursive CTEs operate in a Breadth-First manner (processing all friends, then all friends-of-friends), the first time the recursion finds the target user, it is guaranteed to be the shortest path (in an unweighted graph).

First, we need some data.

CREATE TABLE friendships (    user_name   TEXT NOT NULL,    friend_name TEXT NOT NULL);-- Alice's immediate friendsINSERT INTO friendships VALUES ('Alice', 'Bob');INSERT INTO friendships VALUES ('Bob', 'Alice');INSERT INTO friendships VALUES ('Alice', 'Carol');INSERT INTO friendships VALUES ('Carol', 'Alice');-- Long chain (Alice → Bob → Dan → Erin → Frank → Grace → Kevin)INSERT INTO friendships VALUES ('Bob', 'Dan');INSERT INTO friendships VALUES ('Dan', 'Bob');INSERT INTO friendships VALUES ('Dan', 'Erin');INSERT INTO friendships VALUES ('Erin', 'Dan');INSERT INTO friendships VALUES ('Erin', 'Frank');INSERT INTO friendships VALUES ('Frank', 'Erin');INSERT INTO friendships VALUES ('Frank', 'Grace');INSERT INTO friendships VALUES ('Grace', 'Frank');INSERT INTO friendships VALUES ('Grace', 'Kevin');INSERT INTO friendships VALUES ('Kevin', 'Grace');-- Shorter path (Alice → Carol → Kevin)INSERT INTO friendships VALUES ('Carol', 'Kevin');INSERT INTO friendships VALUES ('Kevin', 'Carol');-- Extra noiseINSERT INTO friendships VALUES ('Bob', 'Helen');INSERT INTO friendships VALUES ('Helen', 'Bob');

Now we find out how many degrees of separation there are between Kevin and everyone else.

WITH RECURSIVE paths(person, degree, path) AS (    -- Anchor: start at Kevin    SELECT        'Kevin' AS person,        0       AS degree,        '|Kevin|' AS path    UNION ALL    -- Recursive: expand one hop, avoid revisiting nodes already in the path    SELECT        f.friend_name AS person,        p.degree + 1  AS degree,        p.path || f.friend_name || '|' AS path    FROM friendships f    JOIN paths p      ON f.user_name = p.person    WHERE p.degree < 10      AND instr(p.path, '|' || f.friend_name || '|') = 0),ranked AS (    SELECT        person,        degree,        path,        ROW_NUMBER() OVER (            PARTITION BY person            ORDER BY degree        ) AS rn    FROM paths    WHERE person <> 'Kevin')SELECT    person,    degree,    replace(trim(path, '|'), '|', ' -> ') AS shortest_pathFROM rankedWHERE rn = 1ORDER BY degree, person;

How this works

The query expands Kevin’s paths using a recursive CTE. The first query begins with Kevin, sets his degree to zero, and starts tracking the route. Each recursive step extends the search by one hop, joining the current results back to the relations table. As new people are found, the degree increases by 1, and their names are added to the path.

To prevent loops, each path keeps a record of visited names. Before extending a path, the query checks if the next person is already in the path and skips them if so. A hard depth limit adds another safety brake, making sure recursion doesn’t go on forever. This process creates many possible paths, including different ways to reach the same person at different depths.

After all paths are found, a second CTE ranks them by length for each person. A window function selects the shortest path for each person and retains it, discarding longer paths. The final SELECT formats these paths and orders the results by degree, so the closest connections come first.

The resulting output is a “six degrees” view of the network: the minimum number of steps from Kevin to every other reachable person, computed entirely inside SQLite using recursive SQL and a small amount of post-processing.

person  degree  shortest_path------  ------  ---------------------------------------Carol   1       Kevin -> CarolGrace   1       Kevin -> GraceAlice   2       Kevin -> Carol -> AliceFrank   2       Kevin -> Grace -> FrankBob     3       Kevin -> Carol -> Alice -> BobErin    3       Kevin -> Grace -> Frank -> ErinDan     4       Kevin -> Grace -> Frank -> Erin -> DanHelen   4       Kevin -> Carol -> Alice -> Bob -> Helen

Performance Optimisation and Limits

Recursive CTEs are powerful, but they aren’t a replacement for a dedicated graph engine. They work well within certain limits, but performance drops quickly if you go beyond those limits.

One key thing to watch is indexing. During recursion, the database keeps joining the working set back to the base table. If the join columns aren’t indexed, each step turns into a full table scan. What should be a quick operation can become much slower, so you should always think about indexing columns used in the recursive join.

Another limit is the size of the working table. Recursive CTEs keep intermediate results as they go. In very wide graphs, such as social networks where a single node may have thousands of neighbours, these sets can grow very large, and if they spill to disk, performance can suffer. Because of this, recursive CTEs shouldn’t be used for wide, highly connected graphs.

Finally, always use recursion carefully. In the real-world data is often messy, and cycles can appear without you even realising it. Without safeguards, a recursive query can loop forever or use up all system resources. Adding a simple depth limit to the recursive WHERE clause is a reliable safety brake, ensuring the query stops even in the presence of unexpected loops or bad data.

Summary

SQL is often seen as just a language for simple reports and CRUD operations. But it’s actually a declarative logic programming language. This article shows how standard SQL, using recursive Common Table Expressions (CTEs), can solve many real-world graph problems without a dedicated graph database.

It shows how relational databases can do hierarchy traversal, pathfinding, cycle detection, and shortest-path calculations using just SQL recursion. With real-world examples such as org charts, route planning, cycle-safe traversal, and six degrees of separation, the article explains both how recursive CTEs work and where their limits lie.

The main point is that while recursive CTEs aren’t a replacement for large graph engines, they are a powerful and underused tool for working with small to medium graphs inside your existing relational database—as long as you know their performance limits and use safety checks.

You don’t always need to set up a Neo4j instance or write a Python script to traverse a tree or find a path. Sometimes, all you need is SQL and a new way of thinking.