질문의 역사
**중첩 집합 모델(Nested Set Model)**은 1990년대 Joe Celko에 의해 SQL에서 재귀 조인 없이 트리 구조를 표현하는 방법으로 대중화되었습니다. 각 노드에 왼쪽(lft) 및 오른쪽(rgt) 정수 경계를 할당함으로써, 이 모델은 전체 서브트리를 단순한 범위 쿼리를 통해 선택할 수 있도록 합니다. 그러나 표준은 간격 무결성 제약 조건을 인 enforce하지 않기 때문에 동시 대량 삽입이나 레거시 마이그레이션 오류로 인해 간격이 부분적으로 겹치는 경우가 자주 발생해 위계 의미가 파괴됩니다. 이 질문은 OLAP 큐브 또는 추천 엔진을 지원하기 전에 계층 구조를 검증해야 하는 데이터 웨어하우징 시나리오에서 발생합니다.
문제
유효한 중첩 집합에서 임의의 두 노드는 서로 다르거나(a.rgt < b.lft) 또는 엄격한 포함 관계에 있어야 합니다(a.lft < b.lft AND a.rgt > b.rgt). 부분 겹침 — a.lft < b.lft이지만 a.rgt가 b.lft와 b.rgt 사이에 있는 경우 —은 노드가 형제이자 자손처럼 보이는 논리적 불가능성을 생성하며, 서브트리 쿼리를 파괴합니다. 이러한 위반 사항을 감지하기 위해서는 모든 구간 쌍을 비교하여 적절한 포함이 없는 교차를 찾아야 하므로, 이는 절차적으로 수행할 경우 계산적으로 비싼 작업입니다.
해결책
우리는 포함 없이 교차를 식별하기 위해 자기 조인을 사용한 간격 대수를 적용합니다. 술어는 노드 a가 노드 b보다 먼저 시작하지만 b의 범위 내에서 끝날 때, 즉 부분 겹침을 나타낼 때를 감지합니다.
SELECT a.id AS violating_node_a, b.id AS violating_node_b, a.lft AS a_left, a.rgt AS a_right, b.lft AS b_left, b.rgt AS b_right FROM nested_set a JOIN nested_set b ON a.lft < b.lft -- a는 b보다 먼저 시작 AND a.rgt > b.lft -- a는 b가 시작하는 것보다 뒤에서 끝남(교차) AND a.rgt < b.rgt -- 그러나 a는 b가 끝나는 것보다 먼저 끝남(포함 없음) WHERE a.id < b.id; -- 대칭 중복을 피하기 위해
이 쿼리는 불법적으로 교차하는 모든 노드 쌍을 반환합니다. 읽기 중심의 생산 환경에서 실행 가능하도록 하기 위해, (lft, rgt) 및 (rgt, lft)에 대한 복합 인덱스가 통해 인덱스 전용 검사를 가능하게 하여 복잡성을 O(n²) 전체 테이블 스캔에서 O(n log n) 범위 조회로 줄입니다.
레거시 IBM DB2 시스템에서 PostgreSQL 데이터 웨어하우스로의 소프트웨어 중단 없는 전자상거래 제품 분류 체계 이전 중, 엔지니어링 팀은 분석 대시보드를 위한 빠른 카테고리 롤업 쿼리를 지원하기 위해 중첩 집합 모델을 선택했습니다. ETL 파이프라인은 배치된 윈도우 함수를 사용하여 lft 및 rgt 값을 계산했지만 레거시 시스템의 내보내기 API의 경쟁 조건으로 인해 오류가 발생하여 147개의 카테고리 간격이 겹쳤습니다. 이러한 겹침으로 인해 수익 보고서에 제품이 이중 계산되어 예상 판매량이 12% 증가했습니다.
세 가지 구제 전략이 평가되었습니다.
전략 1: 커서를 이용한 절차적 검증. PL/pgSQL 함수가 각 노드를 반복 검사해 높은 lft 값을 가진 모든 다른 노드와의 겹침을 확인했습니다. 개념적으로는 간단했으나, 이 방법은 행 수준 잠금을 가져오고 230만 개 카테고리에서 완료하는 데 38분이 걸리는 바람에 재고 업데이트를 위한 엄격한 5분 신선도 SLA를 위배했습니다. 수용할 수 없는 동시성 저하로 인해 거부되었습니다.
전략 2: 재귀 CTE를 통한 재구성. 우리는 중첩 집합 모델을 완전히 버리고 인접 리스트에서 재귀 CTE를 사용하여 나무를 재구성하는 것을 고려했습니다. 이렇게 하면 손상을 수정할 수 있지만 전체 테이블을 재작성해야 하며 카탈로그 API를 일시 중단해야 하므로 제품 검색이 오프라인으로 전환됩니다. 이는 특정 손상 레코드를 감사할 수 있는 것이 아니라 증상 처리에 그쳤습니다.
전략 3: 집합 기반 간격 대수(ANSI SQL). 우리는 엄격히 표준 SQL 술어를 사용하여 자기 조인 쿼리를 구현했습니다. 간격 열에 대해 B-tree 인덱스를 활용함으로써 검증은 4.2초 만에 완료되어 어떤 147 노드 쌍이 포함 규칙을 위배했는지 정확히 확인할 수 있었습니다. 이를 통해 영향을 받는 서브카테고리만 수동 수정할 수 있도록 검역 조치를 취하면서 나머지 카탈로그는 정상적으로 유지할 수 있었습니다.
우리는 전략 3을 선택했습니다. 이는 작가를 차단하지 않고 가동 중단 없이 정밀한 결과를 제공했습니다. 결과적으로 간격 경계가 엄격한 슈퍼세트를 형성하는 깨끗한 분류 체계가 되었고, 참조 무결성을 복원하며 이후 ACID 준수 업데이트에서 새로운 겹침이 추가된 데이터베이스 제약으로 인해 발생할 수 없게 되었습니다.
조인 술어를 작성할 때 유효한 부모-자식 포함 관계와 잘못된 부분 겹침을 어떻게 구별합니까?
후보자들은 종종 교차를 포함으로 혼동합니다. 그들은 a.lft < b.lft AND a.rgt > b.lft (이는 교차만 확인)라고 작성하고 위반 사항이 감지된다고 잘못 믿습니다. 중요한 세부 사항은 끝점의 독점성입니다: 엄격한 포함의 경우 부모의 오른쪽 경계는 자식의 오른쪽 경계를 초과해야 합니다 (a.rgt > b.rgt). 부분 겹침은 정확히 a.lft < b.lft AND a.rgt > b.lft AND a.rgt < b.rgt일 때 발생합니다. 초보자들은 종종 세 번째 조건을 놓쳐 쿼리가 유효한 부모-자식 쌍에 대한 잘못된 양성 반응을 반환하게 만듭니다. 또한, 그들은 자기 쌍(a.id != b.id)를 제외해야 하거나 대칭 중복을 처리해야 한다는 것을 잊어 a.id < b.id를 강제로 적용하여 중복 위반 보고서를 초래합니다.
노드가 겹침이 없도록 보일 때 여전히 루트에서 고아 상태가 될 수 있는 이유는 무엇이며, 이를 집합 연산만으로 어떻게 감지합니까?
고아 상태의 노드는 단일 행이 이 전체 간격(lft, rgt)을 포함하지 않아 루트로 가는 경로가 없는 상태입니다. 후보자들은 종종 LEFT JOIN을 시도하여 NULL 부모를 찾으려 하지만, 이는 정당한 루트 노드(부모가 없어야 함)와 진정한 고아를 구별하는 데 실패합니다. 올바른 접근 방법은 전역 루트를 제외한 NOT EXISTS를 사용하는 것입니다:
SELECT c.id FROM nested_set c WHERE NOT EXISTS ( SELECT 1 FROM nested_set p WHERE p.lft < c.lft AND p.rgt > c.rgt ) AND c.lft != (SELECT MIN(lft) FROM nested_set);
초보자들이 놓치는 엣지 케이스는 다중 루트 시나리오입니다: 테이블이 우연히 서로 다른 두 개의 트리를 포함하는 경우 두 번째로 작은 lft를 가진 노드는 최소값을 체크할 경우 부모가 없는 것처럼 보일 수 있습니다. 쿼리는 단일 루트(최소 lft)를 명시적으로 식별하고 이를 제외해야 하며, 그렇지 않으면 두 번째 루트를 고아로 잘못 플래그할 수 있습니다.
비계층적으로 연결된 두 개의 별개 조상이 한 노드를 포함하는 다중 부모 위반을 어떻게 감지하겠습니까? ANSI SQL만 사용하여 창 같은 함수 없이.**
이는 겹침 감지와는 다릅니다. 왜냐하면 두 조상은 서로 분리되어 있지만(유효한 형제), 모두 잘못된 자식 노드는 공유하기 때문입니다. 이는 트리 속성(단일 부모)을 위반하지만 조상 간의 간격 겹침을 생성하지 않습니다. 후보자들은 종종 모든 조상을 대상으로 GROUP BY child_id HAVING COUNT(*) > 1를 시도하지만, 이는 유효한 깊은 노드가 자연스럽게 많은 조상(조부모 등)을 가지기 때문에 실패합니다. 해결책은 즉각 부모를 식별하는 것입니다: 자식의 lft 값보다도 작지만 여전히 lft 값을 최대값으로 가지는 조상입니다.
SELECT c.id AS child_id FROM nested_set c JOIN nested_set p ON p.lft < c.lft AND p.rgt > c.rgt WHERE NOT EXISTS ( SELECT 1 FROM nested_set p2 WHERE p2.lft > p.lft AND p2.rgt < p.rgt AND p2.lft < c.lft AND p2.rgt > c.rgt ) GROUP BY c.id HAVING COUNT(*) > 1;
하위 쿼리는 후보와 자식 사이의 중간 노드가 존재하지 않도록 즉각적인 부모를 걸러냅니다. 초보자들은 이 "가장 가까운 조상" 논리를 놓치고 вместо набуя каждую глубокую ноду как нарушение.