無限ループを避ける

無限ループの問題

ループが終わらないのはなぜか

-- Simple recursive CTE that WOULD loop forever
-- (do NOT run this as-is; illustration only)
WITH RECURSIVE counter AS (
  SELECT 1 AS n          -- base case
  UNION ALL
  SELECT n + 1           -- recursive term
  FROM counter
  -- no WHERE clause to stop it!
)
SELECT n FROM counter;

深さ制限を追加する

WITH RECURSIVE counter AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1
  FROM counter
  WHERE n < 10       -- stop at depth 10
)
SELECT n FROM counter;

階層クエリで深さを制限する

CREATE TEMP TABLE employees (
  id   INT PRIMARY KEY,
  name TEXT,
  manager_id INT
);

INSERT INTO employees VALUES
  (1, 'Alice', NULL),
  (2, 'Bob',   1),
  (3, 'Carol', 2),
  (4, 'Dave',  3);

WITH RECURSIVE hierarchy AS (
  SELECT id, name, manager_id, 1 AS depth
  FROM employees
  WHERE manager_id IS NULL          -- root

  UNION ALL

  SELECT e.id, e.name, e.manager_id, h.depth + 1
  FROM employees e
  JOIN hierarchy h ON e.manager_id = h.id
  WHERE h.depth < 5                 -- depth limit
)
SELECT id, name, depth FROM hierarchy ORDER BY depth, id;

循環検出とは

CREATE TEMP TABLE edges (
  from_node INT,
  to_node   INT
);

-- Introduce a cycle: 1->2->3->1
INSERT INTO edges VALUES
  (1, 2),
  (2, 3),
  (3, 1),   -- cycle back to 1
  (1, 4);   -- also a non-cyclic branch

SELECT * FROM edges;

配列で訪問済みノードを追跡する

WITH RECURSIVE traverse AS (
  -- Start from node 1
  SELECT from_node,
         to_node,
         ARRAY[from_node] AS visited
  FROM edges
  WHERE from_node = 1

  UNION ALL

  SELECT e.from_node,
         e.to_node,
         t.visited || e.from_node
  FROM edges e
  JOIN traverse t ON e.from_node = t.to_node
  WHERE NOT (e.from_node = ANY(t.visited))   -- skip visited nodes
)
SELECT from_node, to_node, visited
FROM traverse;

CYCLE句（PostgreSQL 14以降）

WITH RECURSIVE traverse AS (
  SELECT from_node, to_node
  FROM edges
  WHERE from_node = 1

  UNION ALL

  SELECT e.from_node, e.to_node
  FROM edges e
  JOIN traverse t ON e.from_node = t.to_node
)
CYCLE from_node SET is_cycle USING path
SELECT from_node, to_node, is_cycle, path
FROM traverse;

深さ制限と循環検出を組み合わせる

WITH RECURSIVE traverse AS (
  SELECT from_node,
         to_node,
         1 AS depth,
         ARRAY[from_node] AS visited
  FROM edges
  WHERE from_node = 1

  UNION ALL

  SELECT e.from_node,
         e.to_node,
         t.depth + 1,
         t.visited || e.from_node
  FROM edges e
  JOIN traverse t ON e.from_node = t.to_node
  WHERE t.depth < 10                           -- depth limit
    AND NOT (e.from_node = ANY(t.visited))     -- cycle guard
)
SELECT from_node, to_node, depth, visited
FROM traverse;

完全なパスを文字列として作成する

WITH RECURSIVE traverse AS (
  SELECT from_node,
         to_node,
         1 AS depth,
         ARRAY[from_node] AS visited,
         from_node::TEXT AS path_str
  FROM edges
  WHERE from_node = 1

  UNION ALL

  SELECT e.from_node,
         e.to_node,
         t.depth + 1,
         t.visited || e.from_node,
         t.path_str || ' -> ' || e.from_node::TEXT
  FROM edges e
  JOIN traverse t ON e.from_node = t.to_node
  WHERE t.depth < 10
    AND NOT (e.from_node = ANY(t.visited))
)
SELECT from_node, to_node, path_str, depth
FROM traverse
ORDER BY depth;

max_recursive_iterationsを設定する

-- PostgreSQL: set a statement timeout as a safety net
SET statement_timeout = '5s';

-- Now any query that runs longer than 5 seconds is cancelled
WITH RECURSIVE counter AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 FROM counter WHERE n < 1000000
)
SELECT MAX(n) FROM counter;

-- Reset to default when done
SET statement_timeout = '0';

適切な深さ制限を選ぶ

-- Example: org chart with a generous but safe depth cap
WITH RECURSIVE org AS (
  SELECT id, name, manager_id, 1 AS depth
  FROM employees
  WHERE manager_id IS NULL

  UNION ALL

  SELECT e.id, e.name, e.manager_id, o.depth + 1
  FROM employees e
  JOIN org o ON e.manager_id = o.id
  WHERE o.depth < 20    -- realistic upper bound for an org chart
)
SELECT id, name, depth
FROM org
ORDER BY depth, name;

深さ制限と循環検出の比較

まとめ：再帰クエリを安全に保つ