Recursive queries (WITH RECURSIVE): hierarchies and graphs

Traverse trees and graphs with WITH RECURSIVE, mastering depth and cycle detection.

11 min · 3 questions

A recursive CTE is made of two parts joined by UNION ALL: an anchor term that provides the starting rows, and a recursive term that references the CTE itself. SQLite runs the anchor once, then applies the recursive term in a loop over the new rows, until it produces none. Let's create a hierarchy of managers to illustrate it.

CREATE TABLE employees (
  id INTEGER PRIMARY KEY,
  name TEXT NOT NULL,
  manager_id INTEGER
);

INSERT INTO employees (id, name, manager_id)
VALUES
  (1, 'Ada',    NULL),
  (2, 'Grace',  1),
  (3, 'Alan',   2),
  (4, 'Edsger', 2);

To unfold the org chart under Ada, the anchor selects the root with a depth of 0, and the recursive term joins each employee to their manager already present in the CTE, incrementing the depth. The depth column that you compute yourself is the simplest way to measure the levels of a hierarchy.

WITH RECURSIVE chain(id, name, depth) AS (
  SELECT id, name, 0
  FROM employees
  WHERE id = 1
  UNION ALL
  SELECT e.id, e.name, c.depth + 1
  FROM employees e
  JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, depth FROM chain;

A graph is modeled by an edge table (src, dst). The traversal follows the same mechanics, but a graph can contain cycles: following 1 -> 2 -> 3 -> 1 loops forever. The remedy is to remember the path traversed in a text column and reject any node already visited. The instr function looks for a node between two dots within that path.

CREATE TABLE edges (
  src INTEGER NOT NULL,
  dst INTEGER NOT NULL
);

INSERT INTO edges (src, dst) VALUES
  (1, 2), (2, 3), (3, 1), (2, 4);

WITH RECURSIVE walk(node, path) AS (
  SELECT 1, '.1.'
  UNION ALL
  SELECT e.dst,
         w.path || e.dst || '.'
  FROM edges e
  JOIN walk w ON e.src = w.node
  WHERE instr(w.path, '.' || e.dst || '.') = 0
)
SELECT node, path FROM walk;

Knowledge check

Make sure you remember the key points of this lesson.

1. In a recursive CTE, which operator links the anchor term to the recursive term?
   • UNION ALL (or UNION)
   • JOIN
   • INTERSECT
   • CROSS APPLY
2. Why does a cyclic graph risk infinite recursion with UNION ALL?
   • Because UNION ALL systematically sorts the results
   • Because the same nodes are revisited without deduplication
   • Because SQLite disables the index during recursion
   • Because the anchor is re-evaluated on each pass
3. How do you avoid an infinite loop when traversing a cyclic graph in SQLite?
   • Add an ORDER BY in the recursive term
   • Remember the path traversed and exclude already-visited nodes
   • Use the standard CYCLE clause
   • Increase the memory cache size