재귀 CTE 탐색

인접 리스트는 저장이 단순하지만, 몇 단계인지 미리 모르는 조회를 일반 JOIN의 개수로 나타낼 수는 없습니다. 깊이가 한 단계 늘 때마다 SQL을 고쳐야 한다면, 데이터의 변화가 곧 쿼리의 배포가 됩니다.

재귀 CTE(recursive common table expression)는 시작 행에서 출발해 직속 간선을 반복해서 따라갑니다. 오염되었을 수 있는 그래프를 탐색할 때는 깊이 제한과 방문 경로의 검사가 필요하고, 화면에 보여 줄 이름 경로와 정렬에 쓸 키는 요구에 따라 나눕니다.

이 글은 14장 1편의 처음 일곱 노드 트리, 곧 Spring 5의 부모가 백엔드 2인 상태를 기준으로 하며, 계속 cs_db_lab에서 실행합니다. 앞 글의 이동 실험을 되돌리지 않았다면 CALL move_category_adjacency(5, 2);로 먼저 되돌립니다. 데이터베이스 7은 루트에서 간선 세 개를 지난 깊이 3의 노드입니다.

고정 단계 조인의 한계

고정된 JOIN은 예상한 깊이까지만 열을 펼칩니다. 데이터베이스처럼 더 깊은 노드는 오류 없이 빠지고, 새 분기가 깊어질 때마다 SELECT와 UNION을 고쳐야 합니다.

USE cs_db_lab;

SELECT root.category_id AS root_id,
       child.category_id AS child_id,
       grandchild.category_id AS grandchild_id
FROM categories AS root
LEFT JOIN categories AS child
  ON child.parent_id = root.category_id
LEFT JOIN categories AS grandchild
  ON grandchild.parent_id = child.category_id
WHERE root.category_id = 1
ORDER BY child.sort_order, grandchild.sort_order;

root_id | child_id | grandchild_id
1       | 2        | 4
1       | 2        | 5
1       | 3        | 6

개발의 자식과 손자는 보이지만, Spring 아래의 데이터베이스 7은 담을 열 자체가 없어 나오지 않습니다. 고정된 깊이의 쿼리는 이 누락을 오류로 알려 주지 않아 더 위험합니다. 현재 데이터의 최대 깊이가 3이라는 사실을 스키마의 상한으로 오해하면, 새 노드 하나가 화면과 권한, 집계를 조용히 깨뜨립니다.

재귀 CTE로 바꿀 때는 출발 루트 한 행을 시작 행으로 고정하고, 현재 자손의 category_id를 다음 행의 parent_id와 잇습니다. 방문한 ID와 깊이 상한으로 오염된 그래프에서도 끝나게 하고, sort_order와 경로 키로 부모 다음에 자식이 오는 순서를 정합니다.

재귀 CTE의 세 요소

시작 행은 깊이 0과 처음의 전체 경로를 만듭니다. 재귀 부분은 자식의 이름과 ID를 경로에 덧붙이고, 이미 방문한 ID는 제외합니다. 하위 탐색은 child.parent_id = current.category_id, 상위 탐색은 parent.category_id = current.parent_id로 간선의 방향만 바뀌므로, 같은 스키마에서 두 탐색을 별도의 CTE로 분명하게 나타냅니다.

재귀 CTE의 결과 열 타입은 시작 행의 SELECT만 보고 정해집니다(WITH와 재귀 CTE). 그래서 경로 문자열은 시작 행에서 충분한 폭으로 CAST해야 하며, 그러지 않으면 깊어질 때 엄격 모드에서 오류 1406(Data too long)이 납니다. 폭은 최대 깊이와 이름의 길이, 구분자의 길이에서 계산하고, 아래의 CHAR(2000)은 이름이 짧은 이 예제에 충분한 크기입니다.

깊이는 루트 0부터 간선 하나마다 1씩 늘립니다. 방문 여부는 ,id, 형태의 토큰을 경로에 쌓아 정확히 같은 ID의 재방문만 막고, 업무상의 최대 깊이보다 큰 안전 상한에서 멈춥니다.

더 깊이: MySQL이 재귀 CTE를 실행하는 규칙

재귀 부분은 반복할 때마다 바로 앞 반복이 만든 행만 입력으로 받습니다. 그래서 루트에서 시작한 탐색은 한 번의 반복에 한 단계씩 내려가고, 재귀 부분이 새 행을 하나도 만들지 않으면 끝납니다. 재귀의 단계 수는 cte_max_recursion_depth(기본값 1000)가 제한하며, 이보다 깊이 재귀하면 서버가 실행을 끝냅니다. SELECT라면 max_execution_time으로 실행 시간 자체에 상한을 둘 수도 있습니다.

재귀 부분에 쓸 수 있는 문법에도 제약이 있습니다. MySQL 8.4 매뉴얼에 따르면 재귀 SELECT에는 집계 함수와 윈도 함수, GROUP BY, ORDER BY, DISTINCT를 쓸 수 없습니다. 다만 DISTINCT를 막는 규칙은 각 SELECT에만 해당하므로, 두 부분을 UNION DISTINCT로 잇는 것은 허용됩니다. 또 CTE는 재귀 부분의 FROM에서 한 번만 참조해야 하며 서브쿼리 안에서는 참조할 수 없고, 다른 테이블과 조인하더라도 CTE를 LEFT JOIN의 오른쪽에 둘 수 없습니다. 그래서 하위 항목의 수 같은 집계는 재귀가 끝난 뒤 바깥 쿼리에서 계산합니다.

재귀 부분에는 LIMIT과 OFFSET을 쓸 수 있습니다. 결과는 바깥 SELECT에 LIMIT을 붙인 것과 같지만, 요청한 수만큼 행을 만들면 그 즉시 행 생성을 멈추므로 더 효율적입니다. 다만 재귀 부분에는 ORDER BY를 쓸 수 없으므로, 이 LIMIT은 트리의 특정 부분을 고르는 용도보다 순회가 지나치게 커지지 않게 막는 안전장치로 쓰는 편이 맞습니다.

하위 항목과 이동 경로 탐색

루트 1에서 시작해 깊이 20까지 펼칩니다. visited_ids는 순환을 끊고, breadcrumb는 화면의 경로와 결과의 검증에 씁니다.

WITH RECURSIVE category_tree AS (
  SELECT
    category_id,
    category_name,
    parent_id,
    sort_order,
    0 AS depth,
    CAST(category_name AS CHAR(2000)) AS breadcrumb,
    CAST(CONCAT(',', category_id, ',') AS CHAR(2000)) AS visited_ids
  FROM categories
  WHERE category_id = 1

  UNION ALL

  SELECT
    child.category_id,
    child.category_name,
    child.parent_id,
    child.sort_order,
    parent.depth + 1,
    CONCAT(parent.breadcrumb, ' > ', child.category_name),
    CONCAT(parent.visited_ids, child.category_id, ',')
  FROM categories AS child
  JOIN category_tree AS parent
    ON child.parent_id = parent.category_id
  WHERE parent.depth < 20
    AND parent.visited_ids NOT LIKE
      CONCAT('%,', child.category_id, ',%')
)
SELECT category_id,
       category_name,
       depth,
       breadcrumb
FROM category_tree
ORDER BY breadcrumb;

category_id | category_name | depth | breadcrumb
1           | 개발          | 0     | 개발
2           | 백엔드        | 1     | 개발 > 백엔드
4           | Java          | 2     | 개발 > 백엔드 > Java
5           | Spring        | 2     | 개발 > 백엔드 > Spring
7           | 데이터베이스  | 3     | 개발 > 백엔드 > Spring > 데이터베이스
3           | 프론트엔드    | 1     | 개발 > 프론트엔드
6           | React         | 2     | 개발 > 프론트엔드 > React

일곱 노드가 한 번씩, 고정 JOIN이 놓친 데이터베이스 7까지 나옵니다. 경로 문자열의 정렬에서는 짧은 접두사가 먼저 오고, 같은 위치에서는 '백'이 '프'보다, 'Java'가 'Spring'보다 앞서므로 부모 다음에 그 자손이 이어집니다.

깊이 조건은 새로 만들 자식이 아니라, 재귀에 참여하는 부모의 깊이를 검사합니다. WHERE parent.depth < 2로 바꾸면 깊이 1의 부모는 자식을 만들 수 있어 깊이 2까지 나오므로, ID 1부터 6까지 여섯 행이고 깊이 3의 7은 빠집니다. < 3으로 바꾸면 깊이 2의 Spring이 자식 7을 만들어 일곱 행이 됩니다. 코드의 parent.depth + 1과 함께 읽으면 이 차이가 보입니다.

전체 경로 문자열의 정렬은 정렬 규칙을 따를 뿐 형제의 sort_order를 반영하지 않습니다. 이 예제에서는 이름 순서와 sort_order가 우연히 같지만, 안정적인 트리 순서가 필요하면 LPAD(sort_order, 5, '0')처럼 0으로 채운 정렬 경로를 따로 누적합니다. 방문 경로의 LIKE는 안전장치이지 정상 트리의 주된 성능 경로가 아니며, 순환이 없는 데이터에서는 단계마다의 부모 인덱스 조회가 핵심이므로 최대 깊이와 하위 트리의 크기를 지켜봅니다.

하향 탐색과 상향 탐색의 비교

데이터베이스 7에서 시작한 조상 CTE는 Spring, 백엔드, 개발의 순서로 올라가야 합니다. 두 쿼리의 ID 집합과 깊이를 대조합니다.

WITH RECURSIVE ancestors AS (
  SELECT category_id, category_name, parent_id, 0 AS distance
  FROM categories
  WHERE category_id = 7

  UNION ALL

  SELECT parent.category_id,
         parent.category_name,
         parent.parent_id,
         child.distance + 1
  FROM categories AS parent
  JOIN ancestors AS child
    ON parent.category_id = child.parent_id
  WHERE child.distance < 20
)
SELECT category_id, category_name, distance
FROM ancestors
ORDER BY distance;

WITH RECURSIVE depth_scan AS (
  SELECT category_id, parent_id, 0 AS depth
  FROM categories
  WHERE parent_id IS NULL
  UNION ALL
  SELECT child.category_id, child.parent_id, parent.depth + 1
  FROM categories AS child
  JOIN depth_scan AS parent ON child.parent_id = parent.category_id
  WHERE parent.depth < 20
)
SELECT COUNT(*) AS node_count,
       MAX(depth) AS maximum_depth
FROM depth_scan;

category_id | category_name | distance
7           | 데이터베이스  | 0
5           | Spring        | 1
2           | 백엔드        | 2
1           | 개발          | 3

node_count | maximum_depth
7          | 3

조상은 7 → 5 → 2 → 1의 네 행이고 최대 거리는 3이며, 루트에서 시작한 전체 스캔도 일곱 노드와 최대 깊이 3을 돌려줍니다. 데이터베이스까지의 하향 깊이와 상향 거리가 같으므로 두 방향의 탐색이 일치합니다.

다만 이 조상 탐색과 깊이 스캔, 뒤의 연습 문제는 방문 경로 검사 없이 깊이 상한만 둡니다. 순환이 생긴 조상 탐색은 상한까지 같은 노드를 반복할 수 있고, 모든 루트에서 시작하는 스캔은 루트가 없는 순환 덩어리를 아예 발견하지 못합니다.

UNION의 선택과 경로의 비용

UNION은 모든 열이 같은 행만 제거합니다. 다시 방문할 때 depth와 경로가 달라지는 이 모델에서는 같은 노드라도 다른 행이므로, UNION만으로는 순환을 끊을 수 없습니다. UNION ALL과 명시적인 방문 여부의 검사가 종료하는 이유를 더 잘 드러냅니다.

한 루트의 하위 트리가 수십만 행이라면 재귀 CTE 한 번도 큰 작업입니다. 페이지를 나누어야 한다면 트리 순서의 키나 클로저 테이블 같은 별도의 읽기 모델을 검토합니다.

운영에서는 루트별 노드의 수와 최대 깊이, 순회의 지연 시간, 검사한 행의 수를 주기적으로 측정합니다. cte_max_recursion_depth를 무작정 늘리지 않고, 업무의 깊이 상한과 순환의 경보를 구분합니다.

이름과 ID에도 주의할 점이 있습니다. category_name에 >가 들어 있어도 표시 경로와 식별 경로를 혼동하지 않아야 하고, ID 문자열로 방문 여부를 검사할 때는 구분자를 앞뒤에 넣어 1과 11이 부분적으로 일치하지 않게 합니다. 형제의 이름이 겹칠 수 있다면 전체 경로의 이름만으로 노드를 식별하지 않으며, 권한의 트리는 누락이 곧 보안 문제이므로 분류 화면보다 강한 순환과 포괄성의 검증이 필요합니다.

대부분의 일반적인 분류는 인접 리스트와 보호 조건이 있는 CTE로 충분합니다. 실제 지연 시간과 하위 트리의 크기가 예산을 넘을 때 클로저 테이블로 옮깁니다.

정리

• 고정된 JOIN은 깊이가 늘면 오류 없이 노드를 빠뜨립니다.
• 재귀 CTE는 시작 행과 재귀 간선, 종료 조건으로 이루어집니다.
• 결과 열의 타입은 시작 행에서 정해지므로 경로의 폭을 CAST로 넉넉히 정합니다.
• 방문한 ID와 깊이 제한으로 오염된 그래프에서도 탐색을 끝냅니다.
• 자손과 조상의 탐색은 같은 간선을 반대 방향으로 따라갑니다.

연습 문제

1. 조회의 폭 계산

처음의 트리에서 parent.depth < 1로 제한하면 어떤 ID가 나오고 최대 깊이는 얼마인가요? 또 다른 데이터에서 깊이 20까지 한 경로의 모든 이름이 100글자이고 구분자 ' > '가 세 글자라면, breadcrumb에 필요한 최대 글자 수는 얼마이고 CHAR(2000)으로 충분한가요?

2. 루트별 요약

루트별 node_count와 leaf_count, maximum_depth를 재귀 CTE 하나로 계산해 보세요. 리프(leaf)는 직속 자식이 없는 노드입니다. 이어서 프론트엔드 3을 루트로 옮기면 결과가 어떻게 바뀌나요?

WITH RECURSIVE forest AS (
  SELECT category_id AS root_id,
         category_id,
         parent_id,
         0 AS depth
  FROM categories
  WHERE parent_id IS NULL
  UNION ALL
  SELECT parent.root_id,
         child.category_id,
         child.parent_id,
         parent.depth + 1
  FROM forest AS parent
  JOIN categories AS child
    ON child.parent_id = parent.category_id
  WHERE parent.depth < 20
)
SELECT root_id,
       COUNT(*) AS node_count,
       SUM(is_leaf) AS leaf_count,
       MAX(depth) AS maximum_depth
FROM (
  SELECT f.root_id, f.depth,
         NOT EXISTS (
           SELECT 1
           FROM categories AS c
           WHERE c.parent_id = f.category_id
         ) AS is_leaf
  FROM forest AS f
) AS nodes
GROUP BY root_id
ORDER BY root_id;

root_id | node_count | leaf_count | maximum_depth
1       | 7          | 3          | 3

root_id | node_count | leaf_count | maximum_depth
1       | 5          | 2          | 3
3       | 2          | 1          | 1

다음 글 클로저 테이블에서는 같은 조상과 자손의 경로를 조회할 때마다 계산하지 않고 클로저 테이블에 구체화해, 깊이 조건을 인덱스가 있는 행으로 읽습니다.