DuckDB Recursive CTE Advanced Guide: Graph Traversal, Cycle Detection & Shortest Path

WITH RECURSIVE cte_name AS (
    -- Anchor: the starting point
    SELECT ...
    
    UNION ALL
    
    -- Recursive member: continues based on previous iteration
    SELECT ...
    FROM cte_name
    WHERE termination_condition
)
SELECT * FROM cte_name;

CREATE TABLE supply_chain (
    id INTEGER,
    from_node VARCHAR,
    to_node VARCHAR,
    node_type VARCHAR,  -- 'raw_material', 'component', 'product', 'warehouse', 'store'
    lead_time_days INTEGER
);

INSERT INTO supply_chain VALUES
(1,  'Steel',    'Engine',   'component',  3),
(2,  'Steel',    'Chassis',  'component',  5),
(3,  'Rubber',   'Tire',     'component',  2),
(4,  'Engine',   'CarA',     'product',    7),
(5,  'Chassis',  'CarA',     'product',    6),
(6,  'Tire',     'CarA',     'product',    4),
(7,  'CarA',     'EastWH',   'warehouse',  1),
(8,  'CarA',     'SouthWH',  'warehouse',  1),
(9,  'EastWH',   'Shanghai', 'store',      1),
(10, 'EastWH',   'Hangzhou', 'store',      1),
(11, 'SouthWH',  'Guangzhou','store',      1),
(12, 'SouthWH',  'Shenzhen', 'store',      1);

WITH RECURSIVE path_enum AS (
    -- Anchor: all raw materials
    SELECT 
        from_node AS start_node,
        to_node AS current_node,
        CAST(from_node || ' → ' || to_node AS VARCHAR) AS path,
        lead_time_days AS total_lead_time,
        1 AS depth
    FROM supply_chain
    WHERE from_node IN ('Steel', 'Rubber')
    
    UNION ALL
    
    -- Recursive: trace down the supply chain
    SELECT 
        pe.start_node,
        sc.to_node,
        pe.path || ' → ' || sc.to_node,
        pe.total_lead_time + sc.lead_time_days,
        pe.depth + 1
    FROM path_enum pe
    JOIN supply_chain sc ON sc.from_node = pe.current_node
    WHERE pe.depth < 10
      AND pe.path NOT LIKE '%' || sc.to_node || '%'
)
SELECT 
    start_node AS raw_material,
    path AS full_path,
    total_lead_time AS total_lead_days,
    depth AS levels
FROM path_enum
WHERE current_node LIKE '%Store%'
ORDER BY start_node, total_lead_time;

-- Only check reachability (no path details needed)
-- Use UNION for auto-deduplication, better performance
WITH RECURSIVE affected_stores AS (
    SELECT to_node AS store FROM supply_chain WHERE from_node = 'Steel'
    UNION
    SELECT sc.to_node
    FROM affected_stores a
    JOIN supply_chain sc ON sc.from_node = a.store
    WHERE sc.node_type = 'store'
)
SELECT * FROM affected_stores;
-- Result: Shanghai, Hangzhou, Guangzhou, Shenzhen

CREATE TABLE approval_chain (
    approver VARCHAR,
    approvee VARCHAR,
    level INTEGER
);

INSERT INTO approval_chain VALUES
('Alice', 'Bob', 1),
('Bob', 'Charlie', 2),
('Charlie', 'Alice', 3),  -- Cycle!
('Dave', 'Eve', 1),
('Eve', 'Frank', 2);

WITH RECURSIVE chain AS (
    SELECT 
        approver AS start_person,
        approvee AS current_person,
        approver || ' → ' || approvee AS path,
        1 AS depth
    FROM approval_chain
    
    UNION ALL
    
    SELECT 
        c.start_person,
        ac.approvee,
        c.path || ' → ' || ac.approvee,
        c.depth + 1
    FROM chain c
    JOIN approval_chain ac ON ac.approver = c.current_person
    WHERE c.depth < 10
)
SELECT 
    start_person,
    path AS cycle_path,
    depth AS cycle_depth
FROM chain
WHERE path LIKE '%' || current_person || '%';

WITH RECURSIVE chain AS (
    SELECT 
        approver AS start_person,
        approvee AS current_person,
        ',' || approver || ',' || approvee || ',' AS visited,
        1 AS depth
    FROM approval_chain
    
    UNION ALL
    
    SELECT 
        c.start_person,
        ac.approvee,
        c.visited || ac.approvee || ',',
        c.depth + 1
    FROM chain c
    JOIN approval_chain ac ON ac.approver = c.current_person
    WHERE c.depth < 10
      AND c.visited NOT LIKE '%,' || ac.approvee || ',%'
)
SELECT * FROM chain WHERE depth > 1 AND visited LIKE '%,' || current_person || '%';

CREATE TABLE roads (
    from_city VARCHAR,
    to_city VARCHAR,
    distance_km INTEGER
);

INSERT INTO roads VALUES
('Beijing', 'Tianjin', 137),
('Beijing', 'Jinan', 400),
('Tianjin', 'Jinan', 360),
('Tianjin', 'Shanghai', 1050),
('Jinan', 'Shanghai', 680),
('Jinan', 'Nanjing', 580),
('Shanghai', 'Nanjing', 270),
('Nanjing', 'Hangzhou', 250),
('Hangzhou', 'Ningbo', 140);

WITH RECURSIVE paths AS (
    SELECT 
        'Beijing' AS start_city,
        from_city AS current_city,
        distance_km AS total_distance,
        'Beijing → ' || from_city AS path,
        1 AS hops
    FROM roads
    WHERE from_city = 'Beijing'
    
    UNION ALL
    
    SELECT 
        p.start_city,
        r.to_city,
        p.total_distance + r.distance_km,
        p.path || ' → ' || r.to_city,
        p.hops + 1
    FROM paths p
    JOIN roads r ON r.from_city = p.current_city
    WHERE p.hops < 10
      AND p.path NOT LIKE '%' || r.to_city || '%'
)
SELECT 
    current_city,
    MIN(total_distance) AS min_distance,
    ARRAY_AGG(path ORDER BY total_distance LIMIT 1)[1] AS best_path
FROM paths
GROUP BY current_city
ORDER BY min_distance;

CREATE TABLE relationships (
    person_a VARCHAR,
    person_b VARCHAR,
    relation_type VARCHAR,
    strength INTEGER
);

INSERT INTO relationships VALUES
('Alice', 'Bob', 'colleague', 8),
('Bob', 'Charlie', 'friend', 7),
('Charlie', 'David', 'classmate', 9),
('Alice', 'Eve', 'neighbor', 5),
('Eve', 'Frank', 'friend', 6),
('Frank', 'Grace', 'colleague', 7);

CREATE OR REPLACE FUNCTION get_kdegree_connections(
    start_person VARCHAR,
    k_degree INTEGER
) RETURNS TABLE (
    target VARCHAR,
    degree INTEGER,
    path VARCHAR,
    strength_sum INTEGER
) AS $$
WITH RECURSIVE connections AS (
    SELECT 
        CASE WHEN person_a = start_person THEN person_b ELSE person_a END AS target,
        1 AS degree,
        start_person || ' → ' || 
        CASE WHEN person_a = start_person THEN person_b ELSE person_a END AS path,
        strength AS strength_sum
    FROM relationships
    WHERE person_a = start_person OR person_b = start_person
    
    UNION ALL
    
    SELECT 
        CASE WHEN r.person_a = conn.target THEN r.person_b ELSE r.person_a END,
        conn.degree + 1,
        conn.path || ' → ' || 
        CASE WHEN r.person_a = conn.target THEN r.person_b ELSE r.person_a END,
        conn.strength_sum + r.strength
    FROM connections conn
    JOIN relationships r ON r.person_a = conn.target OR r.person_b = conn.target
    WHERE conn.degree < k_degree
      AND (conn.path || ' → ' || 
           CASE WHEN r.person_a = conn.target THEN r.person_b ELSE r.person_a END
          ) NOT LIKE '%→ ' || CASE WHEN r.person_a = conn.target THEN r.person_b ELSE r.person_a END || '% →%'
)
SELECT * FROM connections;
$$ LANGUAGE sql;

-- Query Alice's 3rd-degree connections
SELECT * FROM get_kdegree_connections('Alice', 3);

-- Prevent infinite recursion causing OOM
WHERE pe.depth < 100

-- Only check if reachable, use UNION for dedup
WITH RECURSIVE reachable AS (
    SELECT start_node FROM edges WHERE id = 1
    UNION  -- Auto-deduplicates!
    SELECT e.to_node FROM reachable r JOIN edges e ON e.from_node = r.end_node
)
SELECT * FROM reachable;

-- Set appropriate parallelism
PRAGMA threads=8;
PRAGMA memory_limit='4GB';

-- For graphs with 1M+ edges, create indexed materialization
CREATE TABLE edges_indexed AS
SELECT * FROM edges ORDER BY from_node;