Recursive Queries

The previous lesson said that a common table expression can only reference expressions defined before it, and named the one exception: an expression can reference itself. This exception grows SQL’s expressive power qualitatively.

Suppose a library’s branches are organized as a tree: every branch has a parent branch, and Central sits at the root. The question “every branch under Central” cannot be written without knowing the depth of the tree — three levels need three joins, four levels need four. Depth, though, is a property of the data and changes over time. Computations like this, which cannot be expressed with a fixed number of joins, are written with a recursive common table expression.

The Two-Step Structure

A recursive expression starts with WITH RECURSIVE, and its body is made of two parts separated by UNION ALL:

• Anchor member: the query that does not reference the expression. It produces the starting rows.
• Recursive member: the query that references the expression itself. It derives new rows from the rows produced in the previous round.

Evaluation proceeds as follows: the anchor member runs and its result goes into a working table. Then the recursive member runs, but only over the rows added in the last round; the rows it produces are appended to the result and become the input for the next round. Processing stops in the round where no new row is produced. This is the query-language counterpart of the breadth-first search from the Data Structures course: it advances level by level.

Descending from the root of the branch tree, computing depth and path, is written with this structure:

sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);

WITH RECURSIVE tree(id, name, depth, path) AS (
  SELECT id, name, 0, name FROM branch WHERE parent_id IS NULL
  UNION ALL
  SELECT b.id, b.name, t.depth + 1, t.path || ' > ' || b.name
  FROM branch b JOIN tree t ON b.parent_id = t.id
)
SELECT depth, name, path FROM tree ORDER BY path;
SQL

┌───────┬──────────┬────────────────────────────────────────┐
│ depth │   name   │                  path                  │
├───────┼──────────┼────────────────────────────────────────┤
│ 0     │ Central  │ Central                                │
│ 1     │ Anadolu  │ Central > Anadolu                      │
│ 2     │ Kadikoy  │ Central > Anadolu > Kadikoy            │
│ 3     │ Bostanci │ Central > Anadolu > Kadikoy > Bostanci │
│ 3     │ Moda     │ Central > Anadolu > Kadikoy > Moda     │
│ 2     │ Uskudar  │ Central > Anadolu > Uskudar            │
│ 1     │ Avrupa   │ Central > Avrupa                       │
│ 2     │ Besiktas │ Central > Avrupa > Besiktas            │
└───────┴──────────┴────────────────────────────────────────┘

The anchor member selects the root: the row with no parent branch, at depth zero. The recursive member finds the children of every node found so far, increments the depth by one, and extends the path string. Depth and path are values that are not present in the table but accumulate while traversing; this is the real power of a recursive expression.

Because the ordering is done with ORDER BY path, the output reads in tree order: each node’s own subtree comes immediately below it. The depth column rises and falls as it goes, because the sort key is the path, not the depth.

Moving Upward

The same structure can also be built in the opposite direction. If the direction of the join condition is reversed, the walk goes from a node toward the root; this answers the question “which region does this branch belong to”:

sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);

WITH RECURSIVE parent_chain(id, name, parent_id, step) AS (
  SELECT id, name, parent_id, 0 FROM branch WHERE name = 'Moda'
  UNION ALL
  SELECT b.id, b.name, b.parent_id, z.step + 1
  FROM branch b JOIN parent_chain z ON b.id = z.parent_id
)
SELECT step, name FROM parent_chain ORDER BY step;
SQL

┌──────┬─────────┐
│ step │  name   │
├──────┼─────────┤
│ 0    │ Moda    │
│ 1    │ Kadikoy │
│ 2    │ Anadolu │
│ 3    │ Central │
└──────┴─────────┘

The only difference is in the join condition: descending writes b.parent_id = t.id, ascending writes b.id = z.parent_id. The chain stops at the root, because the root’s parent branch is null and matches no row.

Aggregating Over a Subtree

A recursive expression’s result is a table; it can be joined with other tables and grouped. The question “the total loan count within each branch’s own subtree” is answered by first producing, for every node, the nodes in its subtree, and then aggregating over that mapping:

sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);
CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT);
CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT);
INSERT INTO member VALUES (1,'Alice',7),(2,'Ben',8),(3,'Clara',5),(4,'Derek',5),
                       (5,'Evan',6),(6,'Fiona',6),(7,'Grace',7),(8,'Hannah',5);
INSERT INTO loan VALUES
  (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'),
  (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL),
  (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'),
  (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'),
  (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'),
  (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'),
  (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'),
  (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL),
  (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'),
  (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'),
  (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL),
  (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'),
  (25,4,8,'2024-03-13','2024-03-24');

WITH RECURSIVE subtree(root_id, id) AS (
  SELECT id, id FROM branch
  UNION ALL
  SELECT a.root_id, b.id FROM branch b JOIN subtree a ON b.parent_id = a.id
)
SELECT r.name AS branch, COUNT(l.id) AS subtree_total
FROM subtree a
JOIN branch r ON r.id = a.root_id
LEFT JOIN member m ON m.branch_id = a.id
LEFT JOIN loan l ON l.member_id = m.id
GROUP BY a.root_id, r.name
ORDER BY subtree_total DESC, r.name;
SQL

┌──────────┬───────────────┐
│  branch  │ subtree_total │
├──────────┼───────────────┤
│ Central  │ 25            │
│ Anadolu  │ 19            │
│ Kadikoy  │ 11            │
│ Uskudar  │ 8             │
│ Moda     │ 7             │
│ Avrupa   │ 6             │
│ Besiktas │ 6             │
│ Bostanci │ 4             │
└──────────┴───────────────┘

Here the anchor member does not take a single root but treats every branch as the root of its own subtree. The result is a mapping of “which node belongs to which subtree.” The numbers are internally consistent: Kadikoy’s 11 transactions are the sum of Moda’s 7 and Bostanci’s 4; Anadolu’s 19 is the sum of Kadikoy’s 11 and Uskudar’s 8. The 25 at the root is every transaction in the table.

With No Cycle Guard

Whether the branch tree is truly a tree depends on the correctness of the data. If an update mistakenly attaches a parent branch to its own child, the structure turns into a cyclic graph and the recursion never stops: every round reproduces the same nodes.

The block below deliberately produces this situation — Anadolu gets attached to Moda, which is its own descendant. So the query does not run forever, a depth limit is placed on the recursive member; the limit does not resolve the cycle, it only makes the result visible:

sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);
UPDATE branch SET parent_id = 7 WHERE id = 2;

WITH RECURSIVE tree(id, name, depth) AS (
  SELECT id, name, 0 FROM branch WHERE id = 4
  UNION ALL
  SELECT b.id, b.name, t.depth + 1
  FROM branch b JOIN tree t ON b.parent_id = t.id
  WHERE t.depth < 7
)
SELECT depth, id, name FROM tree ORDER BY depth, id;
SQL

┌───────┬────┬──────────┐
│ depth │ id │   name   │
├───────┼────┼──────────┤
│ 0     │ 4  │ Kadikoy  │
│ 1     │ 7  │ Moda     │
│ 1     │ 8  │ Bostanci │
│ 2     │ 2  │ Anadolu  │
│ 3     │ 4  │ Kadikoy  │
│ 3     │ 5  │ Uskudar  │
│ 4     │ 7  │ Moda     │
│ 4     │ 8  │ Bostanci │
│ 5     │ 2  │ Anadolu  │
│ 6     │ 4  │ Kadikoy  │
│ 6     │ 5  │ Uskudar  │
│ 7     │ 7  │ Moda     │
│ 7     │ 8  │ Bostanci │
└───────┴────┴──────────┘

Kadikoy reappears at depth three and six, Moda at depth one, four, and seven. The pattern repeats every three steps: 4 → 7 → 2 → 4. Had the limit been removed, the query would not have stopped; it would have kept producing rows until memory or temporary disk space ran out.

The correct fix is to track the nodes already visited and prevent a revisit. The path walked is accumulated in a string, and the recursive member refuses to take a node a second time if it has already appeared in the path:

sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);
UPDATE branch SET parent_id = 7 WHERE id = 2;

WITH RECURSIVE tree(id, name, depth, path) AS (
  SELECT id, name, 0, '/' || id || '/' FROM branch WHERE id = 4
  UNION ALL
  SELECT b.id, b.name, t.depth + 1, t.path || b.id || '/'
  FROM branch b JOIN tree t ON b.parent_id = t.id
  WHERE t.path NOT LIKE '%/' || b.id || '/%'
)
SELECT depth, id, name, path FROM tree ORDER BY depth, id;
SQL

┌───────┬────┬──────────┬───────────┐
│ depth │ id │   name   │   path    │
├───────┼────┼──────────┼───────────┤
│ 0     │ 4  │ Kadikoy  │ /4/       │
│ 1     │ 7  │ Moda     │ /4/7/     │
│ 1     │ 8  │ Bostanci │ /4/8/     │
│ 2     │ 2  │ Anadolu  │ /4/7/2/   │
│ 3     │ 5  │ Uskudar  │ /4/7/2/5/ │
└───────┴────┴──────────┴───────────┘

The query stopped at five rows. The /4/7/2/4/ step, which would have reached Kadikoy a second time, was eliminated because /4/ had already appeared in the path. Identifiers are written between slashes precisely so that the /4/ pattern is not confused with /14/ or /41/.

This guard visits every node once per path; in a general graph, the same node can be reached by different paths, so the row count can still grow. When every node needs to be visited exactly once, UNION — which removes duplicates — is used instead of UNION ALL; its cost is a uniqueness check on every round.

Outside a Hierarchy

The anchor member of a recursive expression does not have to come from a table. Starting from a fixed row and applying a rule, a sequence can be generated. A typical use for this is showing days with no data as zero in a report:

sqlite3 -box -header <<'SQL'
CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT);
INSERT INTO loan VALUES
  (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'),
  (3,5,1,'2024-03-04','2024-03-18'),(6,2,2,'2024-03-01','2024-03-12'),
  (10,1,3,'2024-03-04','2024-03-10'),(14,5,4,'2024-03-04','2024-03-09');

WITH RECURSIVE day(date) AS (
  SELECT '2024-03-01'
  UNION ALL
  SELECT date(date, '+1 day') FROM day WHERE date < '2024-03-06'
)
SELECT d.date, COUNT(l.id) AS transaction_count
FROM day d LEFT JOIN loan l ON l.pickup = d.date
GROUP BY d.date ORDER BY d.date;
SQL

┌────────────┬───────────────────┐
│    date    │ transaction_count │
├────────────┼───────────────────┤
│ 2024-03-01 │ 3                 │
│ 2024-03-02 │ 0                 │
│ 2024-03-03 │ 0                 │
│ 2024-03-04 │ 3                 │
│ 2024-03-05 │ 0                 │
│ 2024-03-06 │ 0                 │
└────────────┴───────────────────┘

Had only the loan table been grouped, March 2nd and 3rd would not appear at all; empty days would disappear from the report. The generated calendar forms the left side of the left outer join and fills the missing days with zero. The name of the date function varies by engine; what does not vary is the structure made of the anchor member and the stopping condition.

The stopping condition has to sit inside the recursive member. If the condition is written into an outer WHERE clause instead, generation does not stop; the outer filter only weeds out the rows already produced. This is the most common mistake made when writing a recursive query.

Summary

• A recursive common table expression is made of an anchor member and a self-referencing recursive member joined with UNION ALL; it stops in the round where no new row is produced.
• Values like depth, path, and step number are not present in the table; they accumulate during the traversal.
• Reversing the direction of the join condition lets the same structure walk both the subtree and the parent chain.
• If the data contains a cycle, the recursion does not stop; accumulating the visited nodes in a path and eliminating a repeated step is the guard that terminates the query.
• The anchor member can be a fixed row; this is the standard way to generate the calendar that fills in missing days in reports.

Next Step

What the computations in this lesson had in common is that the result changed the row set: traversal produced new rows, grouping reduced rows to one per group. In some questions, though, the rows should be preserved, and a value that looks at its neighbors added next to each one — a member’s running total next to that member’s transaction, up to that day. Grouping cannot do this, because grouping swallows rows. The next lesson introduces window functions, which compute over neighboring rows while preserving them, and shows how the frame definition changes the result within the same query.