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;