계층적인 조상을 정렬 가능한 구분 문자열로 보고 계층에 노출해야 한다고 가정할 때, ANSI SQL의 재귀 CTE를 사용하여 이러한 계통 경로를 구성하여 동등한 순서의 형제와 깊이 제약을 보장하는 방법은 무엇입니까?

질문에 대한 답변.

질문의 배경.

계층적 데이터 모델은 일반적으로 트리 구조를 나타내기 위해 인접 목록이나 중첩 집합을 사용합니다. 인접 목록은 저장 공간을 최소화하고 삽입을 간소화하지만, 분석 보고서는 종종 효율적인 필터링을 가능하게 하기 위해 "물리적 경로"(예: "Root/Category/Subcategory")를 요구합니다. SQL:1999 이전에는 이러한 계층 구조를 평면화하려면 절차적 커서나 애플리케이션 측 재귀가 필요했습니다. ANSI SQL 표준에서 재귀 공통 테이블 표현식(CTE)의 도입으로 선언적 탐색이 가능해졌지만, 깊이 제한이 있는 결정론적이고 순서가 지정된 경로를 구축하는 것은 재귀 종결 및 정렬 안정성에 대한 복잡성을 추가합니다.

문제.

재귀 인접 목록을 각 행이 전체 조상 계통을 포함하는 비정형 형식으로 변환해야 합니다(예: "/A/B/C"). 솔루션은 세 가지 제약 조건을 적용해야 합니다: (1) 모든 수준의 형제는 경로 내에서 어휘 순서로 나타나야 하며, (2) 정형 데이터에서 잘못된 쿼리로 인한 무절 처리 방지를 위해 지정된 최대 깊이를 초과해서는 안 되며, (3) 구현은 독점적인 계층 확장을 사용하지 않고 엄격히 ANSI SQL 구문을 따라야 합니다.

솔루션.

이 솔루션은 두 단계의 CTE 접근 방식을 사용합니다. 첫 번째로 비재귀 CTE는 창 함수를 사용하여 각 노드의 형제 간의 서수 위치를 계산합니다. ANSI SQL은 재귀 CTE의 재귀 구성원 내에서 창 함수를 금지하기 때문에 이 사전 계산이 필요합니다. 두 번째로, 재귀 CTE는 트리를 탐색하며 노드 이름과 사전 계산된 정렬 키를 연결하고 깊이 제한 및 선택적 순환 감지를 WHERE 절에 적용합니다.

WITH RECURSIVE 
OrderedNodes AS (
  -- 1단계: 형제에게 결정론적 순서 할당
  SELECT 
    node_id, 
    parent_id, 
    node_name,
    ROW_NUMBER() OVER (PARTITION BY parent_id ORDER BY node_name, node_id) AS sibling_order
  FROM taxonomy
),
PathBuilder AS (
  -- 앵커 구성원: 루트 노드 초기화
  SELECT 
    node_id,
    node_name,
    1 AS depth,
    CAST(node_name AS VARCHAR(1000)) AS materialized_path,
    CAST(sibling_order AS VARCHAR(100)) AS sort_key
  FROM OrderedNodes
  WHERE parent_id IS NULL
  
  UNION ALL
  
  -- 재귀 구성원: 자식 추가
  SELECT 
    c.node_id,
    c.node_name,
    p.depth + 1,
    p.materialized_path || '/' || c.node_name,
    p.sort_key || '.' || CAST(c.sibling_order AS VARCHAR(100))
  FROM OrderedNodes c
  INNER JOIN PathBuilder p ON c.parent_id = p.node_id
  WHERE p.depth < 5  -- 엄격한 깊이 제약
    AND p.materialized_path NOT LIKE '%/' || c.node_name || '%'  -- 순환 방지
)
SELECT 
  node_id, 
  materialized_path,
  depth
FROM PathBuilder
ORDER BY sort_key;

실생활의 상황

문제 설명.

글로벌 전자상거래 플랫폼은 PostgreSQL 데이터베이스(ANSI SQL 준수 모드)에 100,000개 이상의 카테고리를 유지합니다. 마케팅 팀은 외부 광고 플랫폼을 위해 매일 CSV 내보내기를 요구하는데, 이는 각 수준에서 엄격한 알파벳 정렬을 가진 완전한 카테고리 경로(예: "Electronics/Computers/Laptops")를 기대합니다. 기존 솔루션은 N+1 쿼리를 실행하는 Python 스크립트를 사용하여 20분의 실행 시간과 빈번한 시간 초과를 초래했습니다.

고려된 다양한 솔루션.

솔루션 A: 애플리케이션 측 캐시와 정기적인 재생성. 팀은 6시간마다 백그라운드 작업을 통해 Redis 캐시에 경로를 확정하는 것을 고려했습니다. 장점에는 간단한 Python 구현과 피크 시간 동안 데이터베이스 부하가 줄어드는 것이 포함되었습니다. 그러나 단점으로는 상당한 데이터 노후화(최대 6시간), 카테고리가 재부모 되는 경우의 캐시 무효화 복잡성, 전체 트리에 대한 과도한 메모리 소비가 있었습니다.

솔루션 B: 재귀 CTE를 사용한 데이터베이스 뷰. 이 접근 방식은 ANSI SQL 재귀 CTE 패턴을 사용하여 필요 시 경로를 계산하는 뷰를 생성합니다. 장점으로는 데이터 신선도 보장(실시간 결과), 단일 진실 출처 및 데이터베이스의 쿼리 최적화를 활용한 조인이 있습니다. 단점으로는 데이터베이스 서버의 CPU 집약성과 데이터에 순환 참조가 포함된 경우 무한 재귀의 위험이 있습니다(예: 카테고리가 우연히 자신의 자손에 연결된 경우).

솔루션 C: 트리거 유지를 통한 물리화된 열. 이 방법은 테이블에 materialized_path 열을 추가하고 삽입, 업데이트 또는 삭제 시 트리거를 통해 업데이트합니다. 장점으로는 매우 빠른 읽기 성능(단순 인덱스 스캔)이 있습니다. 단점으로는 상당한 쓰기 오버헤드, 서브트리 이동 또는 이름 변경을 위한 복잡한 트리거 논리 및 형제 이름 변경 시 어휘 순서 제약을 유지하는데 어려움이 있습니다.

선택된 솔루션 및 결과.

팀은 솔루션 B(재귀 CTE 뷰)를 선택했습니다. 읽기 중심의 작업량(읽기:쓰기 비율 100:1)은 트리거의 유지 부담 없이 필요 시 계산의 이점을 누렸습니다. 순환 위험을 완화하기 위해 WHERE 절에 LIKE 패턴 검사를 구현하고, 비즈니스 규칙에 따라 깊이 제한을 5개 수준으로 설정했습니다. 또한 앵커 CTE에서 창 함수 정렬을 최적화하기 위해 (parent_id, node_name)에 대한 복합 인덱스를 생성했습니다. 결과적으로 내보내기 시간이 20분에서 8초로 단축되었고, 동시에 롤아웃 단계에서 레거시 데이터에서 3개의 순환 참조를 감지하고 분리했습니다.

후보자들이 자주 놓치는 점

왜 집계 함수나 창 함수가 CTE의 재귀 구성원에 나타날 수 없으며, 이는 형제 정렬에 어떤 영향을 미칩니까?

ANSI SQL 표준은 재귀 쿼리가 단조롭고 고정 점에 도달할 수 있도록 보장하기 위해 집계 함수(SUM와 같은)나 창 함수(ROW_NUMBER와 같은)를 포함하는 것을 금지합니다. 창 함수는 전체 작업 집합을 물리화하고 분할해야 하므로 재귀 종료를 위한 스트리밍 의미론을 위반할 수 있으며 비결정성을 도입할 수 있습니다. 그 결과, 재귀 내에서 동적으로 형제 정렬을 계산할 수 없습니다. 올바른 접근 방식은 솔루션에서 보여준 것처럼 별도의 비재귀 CTE에서 서수 위치를 사전 계산한 다음, 재귀 조인에서 해당 계산된 열을 참조하는 것입니다. 후보자들은 종종 재귀 SELECT 목록에 ROW_NUMBER()를 직접 배치하려고 시도하여 구문 오류나 예측할 수 없는 실행 계획을 초래합니다.

전문적인 순환 참조를 프로프라이어터리 순환 감지 구문(예: PostgreSQL의 CYCLE 절) 없이 계층에서 어떻게 처리합니까?

순수 ANSI SQL은 내장된 CYCLE 감지 메커니즘을 제공하지 않습니다(물론 SQL:2023에서는 CYCLE 및 SEARCH 절이 도입되었지만 아직 널리 구현되지 않았습니다). 무한 재귀를 방지하기 위해 방문한 노드를 수동으로 추적해야 합니다. 표준 이식 가능한 기술은 방문한 노드 ID의 구분된 문자열(또는 지원되는 경우 배열)을 축적하고 현재 node_id가 이미 그 축적기에 존재하는지 확인하는 것입니다. WHERE p.materialized_path NOT LIKE '%/' || c.node_id || '%'와 같은 조건을 사용하면 순환을 효과적으로 제거하지만, 이 방법은 문자열 길이 오버플로우를 방지하기 위한 적절한 깊이 제한을 가정합니다. 대규모 데이터 세트를 위해 비트 문자열이나 해시 경로를 사용할 수도 있습니다.

형제 노드가 동일한 이름을 공유할 때 결정론적 정렬을 보장하는 요소와 물리적 경로에 대한 총 정렬이 중요한 이유는 무엇입니까?

결정론적 정렬은 형제 간의 총 정렬을 설정하는 데 의존합니다. 창 함수가 단지 ORDER BY node_name을 사용하고 두 형제가 동일한 이름을 공유하면 데이터베이스는 임의의 순서로 반환할 자유가 있습니다(구현에 따라 정의됨) 이는 서로 다른 쿼리 실행이나 데이터베이스 버전 간에 비결정적인 경로 문자열로 이어질 수 있습니다. 이 비결정성은 쿼리 결과 캐싱을 깨뜨리고 테스트를 복잡하게 하며 다운스트림 시스템의 "플래핑" 데이터를 초래할 수 있습니다. 해결 방법은 ORDER BY node_name, node_id 절에 일반적으로 기본 키 node_id와 같은 고유한 결정 버퍼를 추가하는 것입니다. 이는 모든 형제가 고유한 서수 위치를 가지도록 보장하여 물리적인 경로와 보조 sort_key가 재생 가능하고 안정적이도록 합니다.