Recursive CTEs: anatomy and simple case

You start with the most classic hierarchy problem: nested categories in a blog. A Post has a category_id. Categories have a parent_id (a recursive reference to themselves). You want:

• Given a parent, list all descendants (subtree).
• Given a node, list all ancestors (breadcrumbs).

In Python with loops, this takes N queries. In pure SQL with a recursive CTE, 1 query. This capsule shows you the anatomy and the first pattern.

The problem with Python loops (anti-pattern)

async def get_subcategories(parent_id):
    """Get all descendants of parent_id recursively."""
    children = await session.scalars(
        select(Category).where(Category.parent_id == parent_id)
    )
    result = []
    for child in children:
        result.append(child)
        # RECURSIVE call — N queries
        descendants = await get_subcategories(child.id)
        result.extend(descendants)
    return result


# For a 5-level tree with 100 categories:
# get_subcategories(root) → 1 query
# For each child → 1 query × N children
# For each grandchild → 1 query × M grandchildren
# Total: 100+ queries

Latency: each query ~5ms × 100 queries = 500ms. For a simple HTTP request. Unacceptable.

The solution: WITH RECURSIVE

WITH RECURSIVE subcategories AS (
    -- Base case (anchor)
    SELECT id, name, parent_id, 0 AS depth
    FROM categories
    WHERE id = 1  -- the parent_id you want to expand

    UNION ALL

    -- Recursive case
    SELECT c.id, c.name, c.parent_id, s.depth + 1
    FROM categories c
    JOIN subcategories s ON c.parent_id = s.id
)
SELECT * FROM subcategories;

1 query. Output:

 id | name             | parent_id | depth
----+------------------+-----------+-------
  1 | Electronics      |    NULL   |   0
  2 | Computers        |     1     |   1
  3 | Laptops          |     2     |   2
  4 | Desktops         |     2     |   2
  5 | Smartphones      |     1     |   1

All in a single query. Latency ~5ms for any depth.

Anatomy

WITH RECURSIVE name AS (
    -- 1. BASE CASE (anchor)
    SELECT initial_columns FROM table WHERE start_condition

    UNION ALL  -- 2. UNION ALL between base and recursive

    -- 3. RECURSIVE CASE
    SELECT next_columns FROM table
    JOIN name ON join_condition
    WHERE recursive_condition  -- optional
)
SELECT * FROM name;

3 parts:

Base case (anchor)

The "starting point" of the recursive expansion. For subcategories, the specific parent:

SELECT id, name, parent_id, 0 AS depth
FROM categories
WHERE id = 1

Returns the initial row. Runs only ONCE.

Recursive case

The part that runs REPEATEDLY, expanding from what's already in the CTE. Each iteration joins against the accumulated result:

SELECT c.id, c.name, c.parent_id, s.depth + 1
FROM categories c
JOIN subcategories s ON c.parent_id = s.id

s is the reference to the CTE itself. PostgreSQL runs this multiple times until there are no more rows to add (when no child has its parent_id in the CTE).

UNION ALL

Combines base + recursive. It has to be UNION ALL (not UNION) because the recursive query needs to see every row (even if they were "duplicates" — although they shouldn't be).

How PostgreSQL executes this

Conceptually:

Iteration 0 (base case):
  CTE = [(1, Electronics, NULL, 0)]

Iteration 1 (recursive):
  Find children of rows in the CTE:
  c WHERE c.parent_id IN (1)
  Returns: [(2, Computers, 1, 1), (5, Smartphones, 1, 1)]
  CTE = base + new = [
    (1, Electronics, NULL, 0),
    (2, Computers, 1, 1),
    (5, Smartphones, 1, 1)
  ]

Iteration 2:
  Find children of the new rows (depth=1):
  c WHERE c.parent_id IN (2, 5)
  Returns: [(3, Laptops, 2, 2), (4, Desktops, 2, 2)]
  CTE += new

Iteration 3:
  c WHERE c.parent_id IN (3, 4)
  Returns: empty

Stop. Final CTE returned.

Internally, PostgreSQL keeps a "working table" with the most recently added rows. Each iteration uses only those for the join. Efficient.

Setup: categories schema

CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_id INTEGER REFERENCES categories(id)
);

INSERT INTO categories (id, name, parent_id) VALUES
    (1, 'Electronics', NULL),
    (2, 'Computers', 1),
    (3, 'Laptops', 2),
    (4, 'Desktops', 2),
    (5, 'Smartphones', 1),
    (6, 'iPhone', 5),
    (7, 'Android', 5),
    (8, 'Books', NULL),
    (9, 'Fiction', 8),
    (10, 'Non-Fiction', 8);

-- Index for fast queries
CREATE INDEX idx_categories_parent ON categories(parent_id);

Practical case: the Electronics subtree

WITH RECURSIVE descendants AS (
    SELECT id, name, parent_id, 0 AS depth
    FROM categories
    WHERE id = 1  -- Electronics
    UNION ALL
    SELECT c.id, c.name, c.parent_id, d.depth + 1
    FROM categories c
    JOIN descendants d ON c.parent_id = d.id
)
SELECT * FROM descendants ORDER BY depth, name;

Output:

 id | name        | parent_id | depth
----+-------------+-----------+-------
  1 | Electronics |    NULL   |   0
  2 | Computers   |     1     |   1
  5 | Smartphones |     1     |   1
  3 | Laptops     |     2     |   2
  4 | Desktops    |     2     |   2
  6 | iPhone      |     5     |   2
  7 | Android     |     5     |   2

All descendants of Electronics in BFS-like order.

In SQLAlchemy 2.0

from sqlalchemy import select, union_all, literal_column
from sqlalchemy.orm import aliased


async def get_descendants(session: AsyncSession, parent_id: int):
    Category = ...  # imported

    # Anchor: the starting category
    anchor = (
        select(
            Category.id,
            Category.name,
            Category.parent_id,
            literal_column("0").label("depth"),
        )
        .where(Category.id == parent_id)
        .cte(name="descendants", recursive=True)
    )

    # Alias for the recursive join
    parent = aliased(Category, name="parent")

    # Recursive part
    recursive = (
        select(
            parent.id,
            parent.name,
            parent.parent_id,
            (anchor.c.depth + 1).label("depth"),
        )
        .join(anchor, parent.parent_id == anchor.c.id)
    )

    # Combine
    final_cte = anchor.union_all(recursive)

    # Query
    result = await session.execute(
        select(final_cte.c.id, final_cte.c.name, final_cte.c.depth)
        .order_by(final_cte.c.depth)
    )
    return result.all()

Verbose but it works. The syntax is complicated by the nature of recursive SQL — SQLAlchemy does what it can but pure SQL is more readable for many.

Alternative: use text() with raw SQL

For complex recursive CTEs, frequently more readable:

async def get_descendants_raw(session: AsyncSession, parent_id: int):
    result = await session.execute(text("""
        WITH RECURSIVE descendants AS (
            SELECT id, name, parent_id, 0 AS depth
            FROM categories WHERE id = :parent_id
            UNION ALL
            SELECT c.id, c.name, c.parent_id, d.depth + 1
            FROM categories c
            JOIN descendants d ON c.parent_id = d.id
        )
        SELECT id, name, depth FROM descendants ORDER BY depth, name
    """), {"parent_id": parent_id})

    return result.mappings().all()

More readable. For queries with recursive CTEs, raw SQL frequently beats a verbose ORM.

Tail recursion vs general recursion

PostgreSQL recursive CTEs are tail-recursive only — the recursive case can use the accumulated result but there can't be any logic "after" the recursion. This is fine for 99% of cases but limits some advanced patterns.

If you need something more complex (BFS-style algorithms with a priority queue), consider:

• Loops in the application with individual queries.
• Stored procedures with PL/pgSQL loops.
• Graph-specific applications: Neo4j.

Common traps and mistakes

1. UNION instead of UNION ALL.

UNION deduplicates — that's not what you want in a recursive CTE. Always use UNION ALL.

2. Reference to the CTE in the base case.

-- ❌ Error
WITH RECURSIVE x AS (
    SELECT * FROM x  -- reference to the CTE in the base case
)

The base case CANNOT reference the CTE. Only the recursive case.

3. No stop condition — infinite loop.

-- ❌ In a graph with a cycle (e.g. A→B→A)
WITH RECURSIVE x AS (...)
-- Infinite loop until PostgreSQL kills the query

PostgreSQL eventually kills it for memory/time, but it's an ugly error. Capsule 04 covers the CYCLE clause.

4. Performance without an index on parent_id.

A recursive CTE does many joins on parent_id. Without an index, sequential scans on every iteration. The index is mandatory.

5. Ordering by a column the recursive case modifies.

-- ❌ depth is computed in the CTE, you can't use it in the recursive WHERE
WHERE depth < 3  -- inside the recursive case — doesn't work as you expect

Filtering by depth requires LIMIT or a WHERE in the final SELECT.

6. WITH RECURSIVE by accident.

WITH RECURSIVE is opt-in. Without the RECURSIVE, it's a normal CTE:

-- NON-recursive CTE
WITH x AS (SELECT * FROM table) SELECT * FROM x;

-- Recursive CTE
WITH RECURSIVE x AS (...) SELECT * FROM x;

Exercise: query the subtree

Setup: the schema and data from the section.

Step 1: run the descendants query for Electronics. Verify the expected output.

Step 2: modify it to show only leaves (no children).

WITH RECURSIVE descendants AS (...)
SELECT * FROM descendants
WHERE id NOT IN (SELECT parent_id FROM categories WHERE parent_id IS NOT NULL);

Step 3: count of descendants per category.

For each category, how many descendants it has:

SELECT
    parent.id,
    parent.name,
    (
        WITH RECURSIVE d AS (
            SELECT id FROM categories WHERE id = parent.id
            UNION ALL
            SELECT c.id FROM categories c JOIN d ON c.parent_id = d.id
        )
        SELECT COUNT(*) - 1 FROM d  -- -1 to exclude the category itself
    ) AS descendant_count
FROM categories parent
WHERE parent.parent_id IS NULL;  -- top-level only

Step 4: measure performance.

EXPLAIN ANALYZE
WITH RECURSIVE descendants AS (
    SELECT id FROM categories WHERE id = 1
    UNION ALL
    SELECT c.id FROM categories c JOIN descendants d ON c.parent_id = d.id
)
SELECT COUNT(*) FROM descendants;

How long does it take? How many iterations did it do?

CTE Scan on descendants
  ->  Recursive Union
        ->  Index Scan using categories_pkey
        ->  Hash Join
              ->  Seq Scan on categories c
              ->  Hash
                    ->  WorkTable Scan on descendants

Summary and next step

What you learned:

• Problem with Python loops: N queries for traversal, latency degrades with depth.
• Recursive CTE solution: 1 query, constant latency.
• Anatomy: base case + UNION ALL + recursive case.
• Iteration: PostgreSQL accumulates rows until there are no more to add.
• SQLAlchemy vs raw SQL: raw is more readable for CTEs.
• Traps: UNION ALL not UNION, no recursion in the base case, index mandatory.

In the next capsule we go to the 3 canonical patterns with complete code: downward traversal (subtree), upward (breadcrumbs), concatenated path (full path as a string). Typical cases you'll use over and over.

Resources

1. PostgreSQL Docs — WITH Queries — reference.
2. SQLAlchemy 2.0 — Recursive CTE — reference.
3. Markus Winand — Hierarchical Queries — deep analysis.
4. Crunchy Data — CTE patterns — practical cases.

Capsule 02 of 08 — Module 8 — Advanced PostgreSQL for Backend Guide