Recursive SQL CTE — Missing Cycle Detection Crashed Payroll

-- ============================================================
-- SETUP: A realistic employee table with a self-referencing
-- parent (manager) relationship.
-- Tested on PostgreSQL 15, SQL Server 2019, MySQL 8.0+
-- ============================================================

CREATE TABLE employee (
    employee_id   INT          PRIMARY KEY,
    full_name     VARCHAR(100) NOT NULL,
    job_title     VARCHAR(100) NOT NULL,
    manager_id    INT          NULL,  -- NULL means this person is the root (CEO)
    FOREIGN KEY (manager_id) REFERENCES employee(employee_id)
);

INSERT INTO employee (employee_id, full_name, job_title, manager_id) VALUES
    (1, 'Sandra Okafor',   'CEO',                 NULL),
    (2, 'Marcus Webb',     'VP of Engineering',   1),
    (3, 'Priya Nair',      'VP of Marketing',     1),
    (4, 'Leo Hartmann',    'Senior Engineer',     2),
    (5, 'Yuki Tanaka',     'Senior Engineer',     2),
    (6, 'Carla Mendez',    'Marketing Manager',   3),
    (7, 'James Osei',      'Junior Engineer',     4),
    (8, 'Fatima Al-Amin',  'Junior Engineer',     4),
    (9, 'Ravi Patel',      'Marketing Analyst',   6);

-- ============================================================
-- THE RECURSIVE CTE
-- Goal: Starting from Sandra (the CEO), walk down the entire
-- reporting chain and show each person's depth level and their
-- full reporting path as a readable string.
-- ============================================================

WITH RECURSIVE org_hierarchy AS (

    -- ---- ANCHOR MEMBER ----
    -- This runs exactly ONCE. It seeds the worktable with just
    -- the root node (the CEO who has no manager).
    SELECT
        employee_id,
        full_name,
        job_title,
        manager_id,
        0                          AS depth_level,      -- CEO is at depth 0
        full_name::TEXT            AS reporting_path    -- Path starts with just the CEO name
    FROM employee
    WHERE manager_id IS NULL                            -- The root: no manager above them

    UNION ALL

    -- ---- RECURSIVE MEMBER ----
    -- This runs repeatedly. Each iteration joins the CURRENT
    -- worktable batch (org_hierarchy) to the employee table
    -- to find one more level of direct reports.
    SELECT
        e.employee_id,
        e.full_name,
        e.job_title,
        e.manager_id,
        oh.depth_level + 1,                            -- Go one level deeper
        oh.reporting_path || ' → ' || e.full_name      -- Append this person to the path
    FROM employee e
    INNER JOIN org_hierarchy oh
        ON e.manager_id = oh.employee_id               -- Match employees whose manager is in the current batch

)
-- ============================================================
-- FINAL SELECT — pull everything out of the accumulated CTE
-- ============================================================
SELECT
    employee_id,
    REPEAT('  ', depth_level) || full_name   AS indented_name,  -- Visual indentation by depth
    job_title,
    depth_level,
    reporting_path
FROM org_hierarchy
ORDER BY reporting_path;  -- Path ordering gives us a clean depth-first visual

-- ============================================================
-- Simulating a CYCLE: Let's corrupt the data to create a loop.
-- James Osei (id=7) will be made to 'manage' Leo Hartmann (id=4)
-- creating a circle: Leo → James → Leo → James → ...
-- ============================================================

-- WARNING: Do not run this on the real table without a transaction!
-- This temporarily breaks the tree for demonstration purposes.
BEGIN;

    UPDATE employee
    SET manager_id = 7         -- James now 'manages' Leo (his own senior!)
    WHERE employee_id = 4;     -- Creating the cycle: 4 → 7 → 4 → 7 ...

    -- ---- APPROACH 1: Manual cycle detection using an integer ARRAY ----
    -- Works on PostgreSQL 12+. Replace INT[] with a VARCHAR path string
    -- for SQL Server / MySQL compatibility.

    WITH RECURSIVE safe_org_traversal AS (

        -- Anchor: start at CEO, initialise the visited_ids array
        SELECT
            employee_id,
            full_name,
            manager_id,
            0                              AS depth_level,
            ARRAY[employee_id]             AS visited_ids,   -- Track every ID we've seen
            FALSE                          AS cycle_detected  -- Flag: are we in a loop?
        FROM employee
        WHERE manager_id IS NULL

        UNION ALL

        SELECT
            e.employee_id,
            e.full_name,
            e.manager_id,
            sot.depth_level + 1,
            sot.visited_ids || e.employee_id,              -- Append new ID to the visited list
            e.employee_id = ANY(sot.visited_ids)           -- TRUE if we've seen this ID before
        FROM employee e
        INNER JOIN safe_org_traversal sot
            ON e.manager_id = sot.employee_id
        WHERE
            NOT sot.cycle_detected                         -- STOP recursing if we already flagged a cycle
            AND e.employee_id <> ALL(sot.visited_ids)      -- Don't recurse into an already-visited node

    )
    SELECT
        employee_id,
        full_name,
        depth_level,
        cycle_detected,
        visited_ids
    FROM safe_org_traversal
    ORDER BY depth_level, employee_id;

ROLLBACK;  -- Undo the corrupted data

-- ============================================================
-- APPROACH 2: PostgreSQL 14+ declarative CYCLE clause (cleaner)
-- ============================================================

WITH RECURSIVE org_with_cycle_check AS (
    SELECT employee_id, full_name, manager_id, 0 AS depth_level
    FROM employee
    WHERE manager_id IS NULL

    UNION ALL

    SELECT e.employee_id, e.full_name, e.manager_id, owc.depth_level + 1
    FROM employee e
    INNER JOIN org_with_cycle_check owc ON e.manager_id = owc.employee_id
)
CYCLE employee_id           -- Tell PostgreSQL WHICH column to watch for repeats
SET is_cycle                -- A boolean column PostgreSQL adds automatically
USING cycle_path            -- An array column PostgreSQL manages for you
SELECT
    employee_id,
    full_name,
    depth_level,
    is_cycle
FROM org_with_cycle_check
ORDER BY depth_level;

-- ============================================================
-- SQL SERVER EQUIVALENT: Setting a custom recursion limit
-- Use this when you know your maximum legitimate tree depth
-- ============================================================
-- OPTION (MAXRECURSION 50)  <-- Add this at the very end of the query
-- OPTION (MAXRECURSION 0)   <-- 0 means UNLIMITED — dangerous with dirty data

-- ============================================================
-- PATTERN 1: Find ALL ancestors of a given employee (upward)
-- Use case: Show the full chain of command above 'James Osei'
-- ============================================================

WITH RECURSIVE ancestors_of_james AS (

    -- Anchor: start AT James Osei (our leaf node)
    SELECT
        employee_id,
        full_name,
        job_title,
        manager_id,
        0 AS levels_above
    FROM employee
    WHERE employee_id = 7      -- James Osei's ID

    UNION ALL

    -- Recursive: join UPWARD — find the manager of whoever we just found
    SELECT
        e.employee_id,
        e.full_name,
        e.job_title,
        e.manager_id,
        aj.levels_above + 1
    FROM employee e
    INNER JOIN ancestors_of_james aj
        ON aj.manager_id = e.employee_id   -- Flip! We go UP: CTE's manager_id matches parent's employee_id

)
SELECT
    levels_above,
    full_name,
    job_title
FROM ancestors_of_james
ORDER BY levels_above;

-- ============================================================
-- PATTERN 2: Subtree aggregation — headcount under each VP
-- Use case: HR dashboard showing how many people report to
-- each VP (including all levels below them)
-- ============================================================

WITH RECURSIVE full_subtree AS (

    -- Anchor: every direct report of the CEO (the VPs)
    -- We tag each person with the VP they ultimately roll up to
    SELECT
        employee_id,
        full_name,
        manager_id,
        employee_id   AS subtree_root_id   -- Each VP is the 'root' of their own subtree
    FROM employee
    WHERE manager_id = 1                   -- Direct reports of Sandra (CEO)

    UNION ALL

    -- Recursive: find everyone under the current batch,
    -- carrying forward the original subtree_root_id so we always
    -- know which VP this person ultimately rolls up to
    SELECT
        e.employee_id,
        e.full_name,
        e.manager_id,
        fs.subtree_root_id                 -- Preserve the root tag through all levels
    FROM employee e
    INNER JOIN full_subtree fs
        ON e.manager_id = fs.employee_id

)
-- Now aggregate the flat list — standard GROUP BY, no recursion needed here
SELECT
    root_emp.full_name                     AS vp_name,
    root_emp.job_title,
    COUNT(fs.employee_id)                  AS total_headcount_including_self_minus_one,
    COUNT(fs.employee_id) + 1              AS total_headcount_including_vp
FROM full_subtree fs
INNER JOIN employee root_emp
    ON fs.subtree_root_id = root_emp.employee_id
GROUP BY
    root_emp.employee_id,
    root_emp.full_name,
    root_emp.job_title
ORDER BY total_headcount_including_vp DESC;

-- ============================================================
-- PERFORMANCE DEMONSTRATION
-- Showing the difference between an untuned and a tuned
-- recursive CTE on a larger dataset.
-- ============================================================

-- STEP 1: Make sure this index EXISTS. Without it, every
-- recursive iteration does a full table scan.
-- On a 500k-row employee table this index reduces query time
-- from ~4s to ~30ms.
CREATE INDEX IF NOT EXISTS idx_employee_manager_id
    ON employee (manager_id);

-- STEP 2: EXPLAIN ANALYZE to see the execution plan
-- Always do this before shipping a recursive CTE to production.
-- Look for 'CTE Scan' and 'WorkTable Scan' nodes.
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
WITH RECURSIVE org_hierarchy AS (
    SELECT employee_id, full_name, manager_id, 0 AS depth_level
    FROM employee
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.employee_id, e.full_name, e.manager_id, oh.depth_level + 1
    FROM employee e
    INNER JOIN org_hierarchy oh ON e.manager_id = oh.employee_id
)
SELECT * FROM org_hierarchy;

-- ============================================================
-- TUNING PATTERN: Prune INSIDE the recursive member.
-- If you only care about the top 2 levels, add the WHERE
-- clause IN the recursive member — not just in the outer query.
-- ============================================================

-- WRONG (inefficient): The CTE computes ALL levels, then filters
WITH RECURSIVE all_levels AS (
    SELECT employee_id, full_name, manager_id, 0 AS depth_level
    FROM employee WHERE manager_id IS NULL
    UNION ALL
    SELECT e.employee_id, e.full_name, e.manager_id, al.depth_level + 1
    FROM employee e
    INNER JOIN all_levels al ON e.manager_id = al.employee_id
    -- No depth guard here — recurses to the bottom of the entire tree
)
SELECT * FROM all_levels
WHERE depth_level <= 2;   -- Filter applied AFTER full traversal — wasteful!

-- RIGHT (efficient): Stop recursing as soon as depth limit is hit
WITH RECURSIVE top_two_levels AS (
    SELECT employee_id, full_name, manager_id, 0 AS depth_level
    FROM employee WHERE manager_id IS NULL
    UNION ALL
    SELECT e.employee_id, e.full_name, e.manager_id, t2l.depth_level + 1
    FROM employee e
    INNER JOIN top_two_levels t2l ON e.manager_id = t2l.employee_id
    WHERE t2l.depth_level < 2    -- Guard INSIDE recursive member — stops traversal early
)
SELECT * FROM top_two_levels
ORDER BY depth_level, employee_id;

-- ============================================================
-- PRODUCTION SAFETY: Always set MAXRECURSION (SQL Server)
-- or check pg_stat_activity for runaway queries (PostgreSQL)
-- ============================================================

-- SQL Server: append to any recursive query in production
-- OPTION (MAXRECURSION 200)   -- Tune to your known maximum tree depth + buffer

-- PostgreSQL: set per-session if needed
-- SET work_mem = '64MB';  -- Give the worktable more memory before spilling to disk

-- ============================================================
-- CLOSURE TABLE APPROACH
-- A separate table storing all ancestor-descendant pairs.
-- This is an alternative to recursive CTEs for read-heavy workloads.
-- ============================================================

-- Tree table: just the nodes (no parent_id needed, though often kept)
CREATE TABLE category (
    category_id   INT PRIMARY KEY,
    name          VARCHAR(100) NOT NULL
);

-- Closure table: every ancestor-descendant pair + self-reference
CREATE TABLE category_closure (
    ancestor_id   INT NOT NULL,
    descendant_id INT NOT NULL,
    depth         INT NOT NULL,  -- 0 means self-reference
    PRIMARY KEY (ancestor_id, descendant_id),
    FOREIGN KEY (ancestor_id) REFERENCES category(category_id),
    FOREIGN KEY (descendant_id) REFERENCES category(category_id)
);

-- Insert categories
INSERT INTO category VALUES (1, 'Electronics'), (2, 'Laptops'), (3, 'Phones'), (4, 'Gaming Laptops');

-- Insert closure relationships (setup for new node 4: ancestor path)
INSERT INTO category_closure VALUES
    (1,1,0), (2,2,0), (3,3,0), (4,4,0),   -- self references
    (1,2,1), (1,4,2),                      -- Electronics -> Laptops (depth 1), Electronics -> Gaming Laptops (depth 2)
    (2,4,1);                               -- Laptops -> Gaming Laptops (depth 1)

-- Get all descendants of Electronics (depth 1: Laptops, depth 2: Gaming Laptops)
SELECT c.name, cc.depth
FROM category c
JOIN category_closure cc ON c.category_id = cc.descendant_id
WHERE cc.ancestor_id = 1 AND cc.depth > 0;  -- exclude self

-- Get all ancestors of Gaming Laptops
SELECT c.name AS ancestor, cc.depth
FROM category c
JOIN category_closure cc ON c.category_id = cc.ancestor_id
WHERE cc.descendant_id = 4 AND cc.depth > 0;

-- ============================================================
-- Compare: Recursive CTE query to do the same thing
-- ============================================================
WITH RECURSIVE cat_tree AS (
    SELECT category_id, name, 0 AS depth
    FROM category WHERE category_id = 1
    UNION ALL
    SELECT c.category_id, c.name, ct.depth + 1
    FROM category c
    JOIN cat_tree ct ON c.category_id = ?  -- This would need a self-referencing parent_id
)
SELECT * FROM cat_tree;
-- Note: closure table avoids the recursive join at read time