Module 8: Recursive CTEs + Final Project

Closure table: the alternative when a recursive CTE isn't enough

A recursive CTE is elegant but does work on every query: it traverses the tree each time. For hierarchies that change rarely and are queried a lot, you can pre-compute all the ancestor-descendant relationships in a closure table. Each query is then a simple SELECT (not recursive), with the trade-off: you have to maintain the closure table when the hierarchy changes.

This capsule gives you the complete pattern, a decision matrix vs the recursive CTE, and maintenance via triggers.

The concept

Schema with a recursive CTE:

categories
├── id
├── name
└── parent_id  -- FK to self (adjacency list)

Every subtree or ancestors query does a recursive traversal.

Schema with a closure table:

categories (same)
├── id
├── name
└── parent_id

category_closure  -- pre-calculated relationships
├── ancestor_id    (an ancestor)
├── descendant_id  (a descendant)
└── depth          (how many levels between them)

Every ancestor-descendant relationship is stored. For a 4-level tree, Electronics → Laptop:

ancestor_id | descendant_id | depth
-----------+---------------+-------
Electronics| Electronics   |  0     (self)
Electronics| Computers     |  1
Electronics| Laptops       |  2
Computers  | Computers     |  0
Computers  | Laptops       |  1
Laptops    | Laptops       |  0

Each node has a "self" row (depth 0). Each relationship is stored explicitly.

Queries are simple:

-- Subtree of Electronics: SELECT from the closure table
SELECT cat.* FROM categories cat
JOIN category_closure cc ON cat.id = cc.descendant_id
WHERE cc.ancestor_id = 1  -- Electronics
ORDER BY cc.depth;

-- Ancestors of Laptops
SELECT cat.* FROM categories cat
JOIN category_closure cc ON cat.id = cc.ancestor_id
WHERE cc.descendant_id = 3  -- Laptops
ORDER BY cc.depth DESC;

No WITH RECURSIVE. Just a SELECT. A typical query plan.

Trade-off

Aspect	Recursive CTE	Closure table
Storage	Only `categories`	+ closure table (can be large)
Query speed	Recursive each time	Simple SELECT (fast)
Insert/update	Trivial (only `categories`)	Triggers or app-managed
Hierarchy changes	Trivial	Maintenance overhead
Code complexity	Verbose recursive query	More complex schema, simple queries

The closure table wins when:

The hierarchy changes rarely (e.g. blog categories edited occasionally).
Hierarchy queries are very frequent.
Performance is critical (latency-sensitive).

The recursive CTE wins when:

The hierarchy changes frequently.
Queries are occasional.
You want schema simplicity.

Complete setup

-- Categories (adjacency list, same as before)
CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_id INTEGER REFERENCES categories(id)
);

-- Closure table
CREATE TABLE category_closure (
    ancestor_id INTEGER NOT NULL REFERENCES categories(id) ON DELETE CASCADE,
    descendant_id INTEGER NOT NULL REFERENCES categories(id) ON DELETE CASCADE,
    depth INTEGER NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id)
);

-- Indexes for fast queries
CREATE INDEX idx_closure_ancestor ON category_closure(ancestor_id);
CREATE INDEX idx_closure_descendant ON category_closure(descendant_id);

Initialize the closure table from existing data

If you already have categories populated and want to add the closure:

-- Self-rows (every node is its own ancestor, depth 0)
INSERT INTO category_closure (ancestor_id, descendant_id, depth)
SELECT id, id, 0 FROM categories;

-- Direct parents (depth 1)
INSERT INTO category_closure (ancestor_id, descendant_id, depth)
SELECT parent_id, id, 1 FROM categories WHERE parent_id IS NOT NULL;

-- Transitive ancestors (depth 2+)
-- Using a recursive CTE! Ironic — use a recursive CTE once to populate the closure
WITH RECURSIVE all_ancestors AS (
    SELECT ancestor_id, descendant_id, depth FROM category_closure
    UNION
    SELECT cc.ancestor_id, ccc.descendant_id, cc.depth + ccc.depth
    FROM category_closure cc
    JOIN category_closure ccc ON cc.descendant_id = ccc.ancestor_id
    WHERE cc.depth + ccc.depth NOT IN (
        SELECT depth FROM category_closure
        WHERE ancestor_id = cc.ancestor_id AND descendant_id = ccc.descendant_id
    )
)
INSERT INTO category_closure
SELECT ancestor_id, descendant_id, depth FROM all_ancestors
ON CONFLICT DO NOTHING;

Simpler: repopulate completely with a CTE:

TRUNCATE category_closure;

WITH RECURSIVE pairs AS (
    SELECT id AS ancestor_id, id AS descendant_id, 0 AS depth FROM categories
    UNION ALL
    SELECT p.ancestor_id, c.id AS descendant_id, p.depth + 1
    FROM pairs p
    JOIN categories c ON c.parent_id = p.descendant_id
)
INSERT INTO category_closure (ancestor_id, descendant_id, depth)
SELECT ancestor_id, descendant_id, depth FROM pairs;

A full repopulate is simpler and more robust.

Queries with the closure table

Subtree (descendants)

-- All descendants of Electronics, including self
SELECT cat.id, cat.name, cc.depth
FROM categories cat
JOIN category_closure cc ON cat.id = cc.descendant_id
WHERE cc.ancestor_id = 1  -- Electronics
ORDER BY cc.depth, cat.name;

Output similar to a recursive CTE but with a trivial query plan:

Hash Join
  ->  Index Scan using idx_closure_ancestor on category_closure
        Index Cond: (ancestor_id = 1)
  ->  Hash on categories

Much faster than recursive — just one indexed join.

Ancestors

-- All ancestors of Laptops, ordered from root to node
SELECT cat.id, cat.name, cc.depth
FROM categories cat
JOIN category_closure cc ON cat.id = cc.ancestor_id
WHERE cc.descendant_id = 3  -- Laptops
ORDER BY cc.depth DESC;

Path as a string

-- Generate the full path
SELECT string_agg(cat.name, ' > ' ORDER BY cc.depth DESC) AS path
FROM categories cat
JOIN category_closure cc ON cat.id = cc.ancestor_id
WHERE cc.descendant_id = 3;

Direct children only (depth 1)

SELECT cat.* FROM categories cat
JOIN category_closure cc ON cat.id = cc.descendant_id
WHERE cc.ancestor_id = 1 AND cc.depth = 1;  -- only direct children

Maintenance: triggers

When you insert/delete a row in categories, you have to update category_closure. Triggers automate this.

INSERT trigger

When a new node is inserted, add all its ancestor relationships:

CREATE OR REPLACE FUNCTION insert_closure() RETURNS TRIGGER AS $$
BEGIN
    -- Self row (depth 0)
    INSERT INTO category_closure (ancestor_id, descendant_id, depth)
    VALUES (NEW.id, NEW.id, 0);

    -- If it has a parent, add all relationships from the parent's ancestors
    IF NEW.parent_id IS NOT NULL THEN
        INSERT INTO category_closure (ancestor_id, descendant_id, depth)
        SELECT cc.ancestor_id, NEW.id, cc.depth + 1
        FROM category_closure cc
        WHERE cc.descendant_id = NEW.parent_id;
    END IF;

    RETURN NEW;
END;
$$ LANGUAGE plpgsql;


CREATE TRIGGER trigger_insert_closure
AFTER INSERT ON categories
FOR EACH ROW EXECUTE FUNCTION insert_closure();

DELETE trigger

ON DELETE CASCADE on the FK already deletes closure rows when you delete a category. But there's also something to consider:

If you delete an INTERMEDIATE node, the rows connecting ancestors via that node are also deleted (cascade handles it correctly).
If you want to "re-parent" (move children to the grandparent), that's more complex logic (typically app-managed).

UPDATE trigger (parent change)

If parent_id changes, you have to update the closure:

CREATE OR REPLACE FUNCTION update_closure() RETURNS TRIGGER AS $$
BEGIN
    IF OLD.parent_id IS DISTINCT FROM NEW.parent_id THEN
        -- Delete the old relationships
        DELETE FROM category_closure
        WHERE descendant_id IN (
            SELECT descendant_id FROM category_closure WHERE ancestor_id = NEW.id
        )
        AND ancestor_id IN (
            SELECT ancestor_id FROM category_closure
            WHERE descendant_id = NEW.id AND ancestor_id != NEW.id
        );

        -- Repopulate (simpler)
        WITH RECURSIVE new_pairs AS (
            SELECT NEW.id AS ancestor_id, NEW.id AS descendant_id, 0 AS depth
            UNION ALL
            -- ... recursive logic ...
        )
        INSERT INTO category_closure ...;
    END IF;
    RETURN NEW;
END;
$$ LANGUAGE plpgsql;

UPDATE triggers are MORE COMPLEX. Frequently simpler: repopulate the entire closure when the hierarchy changes:

async def re_parent_category(session, cat_id: int, new_parent_id: int):
    cat = await session.get(Category, cat_id)
    cat.parent_id = new_parent_id
    await session.commit()

    # Repopulate the closure (simple, robust)
    await session.execute(text("TRUNCATE category_closure"))
    await session.execute(text("""
        INSERT INTO category_closure (ancestor_id, descendant_id, depth)
        WITH RECURSIVE pairs AS (
            SELECT id AS aid, id AS did, 0 AS d FROM categories
            UNION ALL
            SELECT p.aid, c.id, p.d + 1
            FROM pairs p JOIN categories c ON c.parent_id = p.did
        )
        SELECT aid, did, d FROM pairs
    """))
    await session.commit()

Trade-off: a full repopulate is slow for large trees (millions of nodes). For typical trees (hundreds to thousands), trivial.

Detailed decision matrix

Use a recursive CTE if:

The hierarchy is relatively small (<10k nodes).
The hierarchy changes frequently.
Hierarchy queries are occasional (not critical path).
You want a simple schema.

Use a closure table if:

The hierarchy is large (>10k nodes).
The hierarchy changes rarely (taxonomies, categories).
Hierarchy queries are very frequent (on the critical path).
Performance is critical.

Typical cases:

Blog/e-commerce categories: closure table — stable taxonomy, frequent queries.
Comment threads: recursive CTE — comments change constantly.
Org chart: depends — closure table for frequent "who reports to X" queries; recursive CTE if reorgs are frequent.
Filesystem-like (folders): closure table — folders rarely moved, "what's in this folder" queries very frequent.

Materialized view as a compromise

A third option: a materialized view over a recursive CTE. It combines the advantages:

CREATE MATERIALIZED VIEW category_paths AS
WITH RECURSIVE paths AS (
    SELECT id, name, parent_id, name::TEXT AS path, 0 AS depth
    FROM categories WHERE parent_id IS NULL
    UNION ALL
    SELECT c.id, c.name, c.parent_id, p.path || ' > ' || c.name, p.depth + 1
    FROM categories c JOIN paths p ON c.parent_id = p.id
)
SELECT * FROM paths;

-- Indexes
CREATE UNIQUE INDEX idx_paths_id ON category_paths(id);
CREATE INDEX idx_paths_path_trgm ON category_paths USING gin (path gin_trgm_ops);

-- Refresh when the hierarchy changes
REFRESH MATERIALIZED VIEW CONCURRENTLY category_paths;

Trade-off:

Simpler than a closure table (fewer triggers).
Refresh takes time (O(n) in categories).
Allows periodic manual refresh, not automatic per-change.

For apps with a low frequency of changes, an MV is a good compromise.

Common traps and mistakes

1. Closure table without self-rows.

-- ❌ Forgetting self-rows (depth 0)
-- Result: subtree queries don't include the node itself

Self-rows are MANDATORY. Triggers must create them.

2. Complex triggers for a parent_id UPDATE.

UPDATE triggers are fragile. More robust: repopulate the entire closure when a parent changes (if the tree isn't huge).

3. Closure table without foreign keys.

-- ❌ Without an FK, the closure can become inconsistent
ancestor_id INTEGER NOT NULL,
descendant_id INTEGER NOT NULL

-- ✅ FK with CASCADE
ancestor_id INTEGER NOT NULL REFERENCES categories(id) ON DELETE CASCADE

4. Closure table without indexes.

-- Without indexes, subtree queries are a seq scan
CREATE INDEX idx_closure_ancestor ON category_closure(ancestor_id);
CREATE INDEX idx_closure_descendant ON category_closure(descendant_id);

Both indexes are mandatory.

5. Migrating from adjacency list to closure without testing.

A closure table is a more complex schema. Isolation tests are critical to catch inconsistencies between categories and category_closure.

6. Closure table on a hierarchy that changes a lot.

If the hierarchy changes 1000 times/day, closure maintenance is overhead that a recursive CTE doesn't have. Re-evaluate the approach.

7. Storage assumption.

A closure table of a balanced 4-level tree with 10k nodes: ~50k rows in the closure. For 1M nodes: ~5M rows. Verify the storage requirements.

8. Performance assumption.

Closure table queries are fast but NOT instant. For very frequent queries with large datasets, consider additional caching (Redis).

Exercise: implement a closure table

Setup:

-- Categories and closure table
CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_id INTEGER REFERENCES categories(id)
);

CREATE TABLE category_closure (
    ancestor_id INTEGER NOT NULL REFERENCES categories(id) ON DELETE CASCADE,
    descendant_id INTEGER NOT NULL REFERENCES categories(id) ON DELETE CASCADE,
    depth INTEGER NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id)
);

CREATE INDEX idx_closure_ancestor ON category_closure(ancestor_id);
CREATE INDEX idx_closure_descendant ON category_closure(descendant_id);

-- Data
INSERT INTO categories (id, name, parent_id) VALUES
    (1, 'Electronics', NULL),
    (2, 'Computers', 1),
    (3, 'Laptops', 2),
    (4, 'Smartphones', 1);

Step 1: populate the closure table.

WITH RECURSIVE pairs AS (
    SELECT id AS aid, id AS did, 0 AS d FROM categories
    UNION ALL
    SELECT p.aid, c.id, p.d + 1
    FROM pairs p JOIN categories c ON c.parent_id = p.did
)
INSERT INTO category_closure SELECT aid, did, d FROM pairs;

-- Verify
SELECT * FROM category_closure ORDER BY ancestor_id, depth, descendant_id;

Step 2: simple queries vs a recursive CTE.

-- Subtree of Electronics
-- A. With the closure table
SELECT cat.name, cc.depth
FROM categories cat
JOIN category_closure cc ON cat.id = cc.descendant_id
WHERE cc.ancestor_id = 1
ORDER BY cc.depth;

-- B. With a recursive CTE
WITH RECURSIVE x AS (
    SELECT id, name, 0 AS depth FROM categories WHERE id = 1
    UNION ALL
    SELECT c.id, c.name, x.depth + 1
    FROM categories c JOIN x ON c.parent_id = x.id
)
SELECT name, depth FROM x ORDER BY depth;

Compare the plans with EXPLAIN ANALYZE. Closure is the simpler plan.

Step 3: trigger for INSERT.

CREATE OR REPLACE FUNCTION insert_closure() RETURNS TRIGGER AS $$
BEGIN
    INSERT INTO category_closure (ancestor_id, descendant_id, depth)
    VALUES (NEW.id, NEW.id, 0);

    IF NEW.parent_id IS NOT NULL THEN
        INSERT INTO category_closure (ancestor_id, descendant_id, depth)
        SELECT cc.ancestor_id, NEW.id, cc.depth + 1
        FROM category_closure cc
        WHERE cc.descendant_id = NEW.parent_id;
    END IF;

    RETURN NEW;
END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER trigger_insert_closure
AFTER INSERT ON categories
FOR EACH ROW EXECUTE FUNCTION insert_closure();

Step 4: insert a new category and verify the closure auto-updated.

INSERT INTO categories (name, parent_id) VALUES ('Tablets', 1);

-- Verify the closure
SELECT * FROM category_closure
WHERE descendant_id = (SELECT id FROM categories WHERE name = 'Tablets');

Step 5: compare performance.

For 10k categories:

Closure subtree query: ~5ms
Recursive CTE: ~20-50ms

A significant difference for very frequent queries.

See discussion

Step 1: the populate generates all pairs. Verify:

Self-rows: 4 (one per category).
Direct relationships: 3 (Computers→Laptops, Electronics→Computers, etc.).
Transitive: 1 (Electronics→Laptops, depth 2). Total: 8 rows in the closure.

Step 2: both return the same result. Plans:

Closure: simple Hash Join + Index Scan.
Recursive CTE: Recursive Union + iterated Index Scans.

Step 3-4: the trigger keeps the closure automatic. Inserting Tablets adds 2 rows: (Tablets, Tablets, 0) and (Electronics, Tablets, 1).

Step 5: closure is ~5x faster for subtree queries on large datasets.

Key lessons:

Closure table = pre-compute the relationships.
Simple queries vs recursive.
Trade-off: more complex schema, maintenance via triggers.
Useful for stable hierarchies with frequent queries.

Summary and next step

What you learned:

Closure table: pre-calculated ancestor-descendant relationships.
Schema: ancestor_id, descendant_id, depth + indexes on both.
Self-rows mandatory (depth 0).
Simple queries vs recursive — faster but more maintenance.
Triggers for INSERT (DELETE via CASCADE; UPDATE via repopulate).
Decision matrix: stable + frequent queries → closure. Changes a lot + occasional queries → CTE.
Third option: a materialized view over a recursive CTE.

In the next capsule we start the final integrating project: a refactor of the Blog API. Capsule 06 covers phase 1 (setup, baseline, 3 components: JSONB, FTS, MV).

Resources

Bill Karwin — SQL Antipatterns book — chapter dedicated to hierarchies.
PostgreSQL Wiki — Hierarchical patterns — discussion of approaches.
Closure Table on Wikipedia — general reference.
Markus Winand — Hierarchical Queries — technical analysis.

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

← PreviousThe `CYCLE` clause and graphs: avoiding infinite loops Next →Final project — phase 1: setup, baseline, 3 components (JSONB, FTS, MV)