[PostgreSQL] WITH RECURSIVE 심화 — 조직도/그래프 순회와 CYCLE 절로 순환 탐지

설치·접속: PostgreSQL 설치와 접속

부제: 조직도를 재귀로 훑는데 데이터에 사이클이 섞여 무한 루프가 나고, UNION과 UNION ALL 중 뭘 써야 할지 헷갈릴 때

재귀 CTE는 앵커(시작 행) + 재귀 항(자기 자신을 참조)으로 트리·그래프를 훑는다. 조직도부터 시작한다.

CREATE TABLE org (
    id   int PRIMARY KEY,
    boss int REFERENCES org(id),
    name text
);
INSERT INTO org(id, boss, name) VALUES
 (1, NULL, 'CEO'),
 (2, 1, 'VP Eng'),   (3, 1, 'VP Sales'),
 (4, 2, 'Eng Manager'),
 (5, 4, 'Backend Dev'), (6, 4, 'Frontend Dev'),
 (7, 3, 'Sales Rep');

"VP Eng 밑으로 전부"를 레벨과 경로까지 붙여 뽑는다.

WITH RECURSIVE chart AS (
    SELECT id, boss, name, 1 AS lvl, name::text AS path
      FROM org WHERE name = 'VP Eng'          -- 앵커
  UNION ALL
    SELECT o.id, o.boss, o.name, c.lvl + 1, c.path || ' > ' || o.name
      FROM org o JOIN chart c ON o.boss = c.id -- 재귀 항
)
SELECT lvl, repeat('  ', lvl-1) || name AS node, path FROM chart ORDER BY path;

 lvl |       node       |                path                 
-----+------------------+-------------------------------------
   1 | VP Eng           | VP Eng
   2 |   Eng Manager    | VP Eng > Eng Manager
   3 |     Backend Dev  | VP Eng > Eng Manager > Backend Dev
   3 |     Frontend Dev | VP Eng > Eng Manager > Frontend Dev
(4 rows)

앵커가 시작점을 잡고, 재귀 항이 "직전 결과의 id를 boss로 갖는 행"을 계속 붙인다. lvl은 재귀할 때마다 +1, path는 문자열을 이어 붙여 경로를 만든다.

UNION vs UNION ALL

트리는 부모가 하나뿐이라 같은 노드가 두 번 나오지 않는다. 하지만 그래프는 다르다. 다이아몬드(1→2→4, 1→3→4)와 사이클(4→1)이 섞인 방향 그래프를 보자.

CREATE TABLE graph (src int, dst int);
INSERT INTO graph VALUES (1,2),(1,3),(2,4),(3,4),(4,1);  -- 4->1 로 순환

UNION은 집합 의미라 중복 행을 제거한다. 그 덕에 "도달 가능한 노드 집합"을 구할 때는 다이아몬드에서 4가 두 번 나와도 한 번으로 접히고, 사이클도 이미 본 노드가 재등장하면 자연히 멈춘다.

WITH RECURSIVE reach AS (
    SELECT dst AS node FROM graph WHERE src = 1
  UNION                                    -- 집합 의미: 중복 제거 → 사이클에서도 종료
    SELECT g.dst FROM graph g JOIN reach r ON g.src = r.node
)
SELECT node FROM reach ORDER BY node;

 node 
------
    1
    2
    3
    4
(4 rows)

UNION ALL은 중복을 안 지운다. 경로 개수를 세거나 모든 경로를 열거할 때는 이게 맞지만, 사이클이 있으면 영원히 안 멈춘다. 4→1→2→4→1→…을 계속 돌기 때문이다. 여기서 CYCLE 절이 필요하다.

CYCLE 절 (PG14+)로 순환 탐지

CYCLE 컬럼 SET 플래그 USING 경로배열을 붙이면, 지정한 컬럼 값이 현재까지의 경로에 이미 나온 순간을 감지해 플래그를 켜고 그 가지의 확장을 멈춘다. 무한 루프가 안전하게 끝난다.

WITH RECURSIVE walk AS (
    SELECT src, dst FROM graph WHERE src = 1
  UNION ALL
    SELECT g.src, g.dst FROM graph g JOIN walk w ON g.src = w.dst
) CYCLE src SET is_cycle USING cyclepath
SELECT src, dst, is_cycle, cyclepath FROM walk;

 src | dst | is_cycle |     cyclepath     
-----+-----+----------+-------------------
   1 |   2 | f        | {(1)}
   1 |   3 | f        | {(1)}
   2 |   4 | f        | {(1),(2)}
   3 |   4 | f        | {(1),(3)}
   4 |   1 | f        | {(1),(3),(4)}
   4 |   1 | f        | {(1),(2),(4)}
   1 |   2 | t        | {(1),(2),(4),(1)}
   1 |   3 | t        | {(1),(2),(4),(1)}
   1 |   2 | t        | {(1),(3),(4),(1)}
   1 |   3 | t        | {(1),(3),(4),(1)}
(10 rows)

cyclepath가 지금까지 지나온 src 목록을 배열로 쌓는다. 4→1로 1이 재등장하는 순간 is_cycle=t가 켜지고, 그 행은 결과에 나오되 거기서 더 확장하지 않는다. CYCLE 없이 UNION ALL로 이 그래프를 돌리면 쿼리가 끝나지 않는다.

CYCLE 절은 경로 열거에도 그대로 쓴다. 시작점 1에서 노드가 처음 반복될 때까지의 모든 경로를 뽑으면:

WITH RECURSIVE paths AS (
    SELECT src, dst, ARRAY[src, dst] AS p FROM graph WHERE src = 1
  UNION ALL
    SELECT g.src, g.dst, paths.p || g.dst
      FROM graph g JOIN paths ON g.src = paths.dst
) CYCLE dst SET looped USING trail
SELECT p AS path, looped FROM paths WHERE looped ORDER BY p;

     path      | looped 
---------------+--------
 {1,2,4,1,2}   | t
 {1,2,4,1,3,4} | t
 {1,3,4,1,2,4} | t
 {1,3,4,1,3}   | t
(4 rows)

정리

• 앵커 + 재귀 항: 앵커가 시작 행, 재귀 항이 직전 결과를 참조해 한 단계씩 확장.
• UNION: 집합 의미(중복 제거). 도달 가능 노드 "집합", 사이클 자동 종료. 단, dedup 비용이 있다.
• UNION ALL: 중복 유지. 경로 개수·모든 경로 열거. 사이클 있으면 반드시 CYCLE(또는 방문 배열)로 막아야 무한 루프를 피한다.
• CYCLE 절(PG14+): 순환 컬럼이 경로에 재등장하면 플래그를 켜고 멈춘다. 손으로 방문 배열을 굴리던 패턴을 문법으로 대체.

이렇게도 쓴다

CYCLE 없이 방문 배열로 직접 막는다. PG14 미만이거나 세밀한 제어가 필요할 때. (조합: 배열 + <> ALL)

WITH RECURSIVE walk AS (
    SELECT src, dst, ARRAY[src] AS visited FROM graph WHERE src = 1
  UNION ALL
    SELECT g.src, g.dst, walk.visited || g.src
      FROM graph g JOIN walk ON g.src = walk.dst
     WHERE g.src <> ALL(walk.visited)   -- 이미 지난 노드면 확장 중단
)
SELECT * FROM walk;

 

SEARCH 절로 깊이/너비 우선 순서를 매긴다. CYCLE과 짝으로 자주 쓰는 PG14+ 문법. (조합: SEARCH DEPTH FIRST)

WITH RECURSIVE chart AS (
    SELECT id, boss, name FROM org WHERE boss IS NULL
  UNION ALL
    SELECT o.id, o.boss, o.name FROM org o JOIN chart c ON o.boss = c.id
) SEARCH DEPTH FIRST BY id SET ordercol
SELECT id, name FROM chart ORDER BY ordercol;

 

상향 순회로 보고 라인(조상)을 뽑는다. 재귀 항의 조인 방향만 뒤집으면 된다. (조합: 역방향 join)

WITH RECURSIVE up AS (
    SELECT id, boss, name FROM org WHERE name = 'Backend Dev'
  UNION ALL
    SELECT o.id, o.boss, o.name FROM org o JOIN up ON o.id = up.boss
)
SELECT string_agg(name, ' <- ' ORDER BY id DESC) AS chain FROM up;

 

서브트리 인원수를 집계한다. 재귀로 하위를 모은 뒤 바깥에서 count. (조합: 재귀 + 집계)

WITH RECURSIVE sub AS (
    SELECT id FROM org WHERE name = 'VP Eng'
  UNION ALL
    SELECT o.id FROM org o JOIN sub ON o.boss = sub.id
)
SELECT count(*) - 1 AS reports FROM sub;  -- 본인 제외 하위 인원