재귀 CTE 탐색

인접 리스트는 저장이 단순하지만 몇 단계인지 미리 모르는 조회를 일반 JOIN 개수로 표현할 수 없습니다.

깊이가 한 단계 늘 때마다 SQL을 바꾸면 데이터 변화가 쿼리 배포가 됩니다.

재귀 CTE는 시작 행 행에서 시작해 직속 간선을 반복합니다.

실무 쿼리에는 깊이뿐 아니라 정렬 가능한 전체 경로와 기존 순환을 끊는 방문 여부 경로가 함께 있어야 합니다.

ch14-1 트리에 데이터베이스가 네 번째 표시 단계로 존재합니다.

두 번 자기 참조 JOIN한 고정 쿼리와 순환 방지 조건이 있는 재귀 쿼리가 반환하는 노드 수를 비교합니다.

고정 단계 조인의 한계

고정 JOIN은 예상 깊이까지만 열을 펼칩니다.

데이터베이스처럼 더 깊은 노드는 오류 없이 누락되고 새 분기가 깊어질 때마다 SELECT와 UNION을 고쳐야 합니다.

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;

개발의 자식과 손자는 보이지만 Spring 아래 데이터베이스는 열 자체가 없어 반환되지 않습니다.

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

category 7 (데이터베이스) returned: no
SQL errors: 0

고정 깊이 쿼리는 누락을 오류로 알려주지 않아 더 위험합니다.

데이터 최대 깊이가 현재 3이라는 관찰을 스키마 상한으로 오해하면 새 노드 하나가 화면·권한·집계를 조용히 깨뜨립니다.

재귀 CTE는 시작 행과 재귀 구성원의 컬럼 타입을 맞춰야 합니다.

경로 문자열은 시작 행에서 충분한 길이로 CAST하지 않으면 깊어질 때 잘림 오류가 납니다.

두 번 JOIN 뒤 데이터베이스가 사라진 지점

1. 시작 행 — 출발 루트 한 행을 고정합니다.
2. 재귀 간선 — 현재 자손의 category_id를 다음 parent_id와 연결합니다.
3. 종료 조건 — 방문 여부 ID와 깊이 상한으로 오염된 그래프를 종료합니다.
4. 정렬 — sort_order와 경로 키로 부모 다음 자식 순서를 결정합니다.

재귀 CTE의 세 요소

시작 행은 깊이 0과 초기 전체 경로를 만듭니다.

재귀 구성원은 자식 이름과 ID를 경로에 추가하고 이미 방문한 ID는 제외합니다.

하위 탐색은 child.parent_id = current.category_id, 상위 탐색은 parent.category_id = current.parent_id로 간선 방향만 바뀝니다.

같은 스키마에서 둘을 별도 CTE로 명확히 표현합니다.

시작 행·간선·종료 조건을 쿼리로 옮기기

1. 유형 — 시작 행 경로를 CHAR(2000)으로 넓게 선언합니다.
2. 깊이 — 루트 0부터 한 간선마다 1 증가시킵니다.
3. 방문 여부 — ,id, 토큰을 경로에 쌓아 정확히 재방문을 막습니다.
4. 제한 — 업무상 최대 깊이보다 큰 안전 상한에서 중단합니다.

하위 항목과 이동 경로 탐색

루트 1에서 시작해 깊이 20까지 확장합니다.

visited_ids는 순환을 끊고 전체 경로는 화면 경로와 결과 검증에 사용합니다.

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 | depth | breadcrumb
1           | 0     | 개발
2           | 1     | 개발 > 백엔드
5           | 2     | 개발 > 백엔드 > Spring
7           | 3     | 개발 > 백엔드 > Spring > 데이터베이스

rows in subtree: 7
repeated category_id: 0

전체 경로 문자열 정렬은 로캘과 형제 sort_order를 완전히 반영하지 않을 수 있습니다.

안정적인 트리 순서가 필요하면 0으로 채운 정렬 경로를 별도로 누적합니다.

방문 경로의 LIKE는 안전장치이지 정상 트리의 주된 성능 경로가 아닙니다.

순환 없는 데이터에서는 부모 인덱스 조회가 각 단계의 핵심이고 최대 깊이와 하위 트리 크기를 관찰합니다.

자손과 조상의 ID·깊이 대조

1. 정상 하위 트리 — 7개 ID가 한 번씩 나오는지 확인합니다.
2. 깊이 제한 — 깊이 상한 2에서 데이터베이스가 의도적으로 제외되는지 봅니다.
3. 순환 예제 데이터 — 복사한 잘못된 테이블에서 방문 여부 방어 조건이 유한 행으로 끝나는지 확인합니다.
4. 조상 — 데이터베이스에서 부모 방향으로 루트까지 올라갑니다.

하향·상향 탐색 비교

데이터베이스에서 시작한 조상 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;

조상 결과는 7→5→2→1 네 행이고 거리 최대 3입니다.

전체 스캔은 node_count 7, maximum_depth 3을 반환합니다.

경로 타입과 UNION 선택이 만드는 비용

UNION으로 중복 제거를 맡길 수도 있지만 순환 원인을 감추고 비교 비용이 늘 수 있습니다.

UNION ALL과 명시적 방문 여부 방어 조건이 종료 이유를 더 잘 드러냅니다.

한 루트의 하위 트리가 수십만 행이면 재귀 CTE 한 번도 큰 작업입니다.

페이지 나누기가 필요하면 트리 순서 키나 클로저 테이블 등 별도 읽기 모델을 검토합니다.

고정·CTE·앱 반복·클로저 읽기 비교

깊이·순환·경로 폭을 바꾸는 실험

1. 제한 — 깊이 < 2와 < 3 결과 차이를 기록합니다.
2. 경로 폭 — 시작 행 CAST 길이를 20으로 줄여 잘림을 재현합니다.
3. 조상 — React 6에서 루트까지 거리를 확인합니다.
4. 여러 루트 트리 — 모든 루트를 시작 행으로 잡아 서로 다른 트리가 섞이지 않는지 봅니다.

루트별 크기와 재귀 지연 시간 관찰하기

루트별 노드 건수·최대 깊이·순회 지연 시간·검사한 행 수를 주기적으로 측정합니다.

cte_max_recursion_depth를 무작정 늘리지 않고 업무 깊이 상한과 순환 경보를 구분합니다.

여러 루트 트리·이름 구분자·권한 트리 예외

• category_name에 >가 있어도 표시 경로와 식별 경로를 혼동하지 않습니다.
• ID 문자열 방문 여부 방식은 구분자를 앞뒤에 넣어 1과 11의 부분 일치를 막습니다.
• 형제 이름 중복이면 전체 경로 이름만으로 노드를 식별하지 않습니다.
• 권한 트리는 누락이 보안 문제이므로 분류 UI보다 더 강한 순환·포괄성 검증이 필요합니다.

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

재귀 CTE 적용 기준

대부분의 일반 분류는 인접 리스트와 보호 조건이 있는 CTE로 충분합니다.

실제 지연 시간과 하위 트리 크기가 예산을 넘을 때 클로저로 이동합니다.

연습 문제

각 루트별 node_count, leaf_count, maximum_depth를 한 재귀 CTE로 계산하세요.

리프는 직속 자식이 없는 노드입니다.

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(NOT EXISTS (
         SELECT 1
         FROM categories AS child
         WHERE child.parent_id = forest.category_id
       )) AS leaf_count,
       MAX(depth) AS maximum_depth
FROM forest
GROUP BY root_id;

핵심 정리

• 고정 JOIN은 깊이가 늘면 오류 없이 노드를 누락합니다.
• 재귀 CTE는 시작 행·재귀 간선·종료 조건으로 구성됩니다.
• 경로 타입 폭, 방문 여부 ID, 깊이 제한을 명시합니다.
• 자손과 조상은 같은 간선의 반대 방향입니다.

다음 문서에서는 모든 조상·자손 경로를 클로저 테이블로 구축합니다.