위상 정렬은 그래프 이론과 스케줄링 수학에서 유래하며, 특정 정점이 다른 정점보다 먼저 와야 하는 의존성 그래프에서 실행 순서를 확립하기 위해 개발되었습니다. 데이터베이스 환경에서는 ETL 워크플로우, 스키마 마이그레이션 스크립트, 또는 계층적 작업 간의 참조 무결성을 존중해야 할 때 이러한 요구 사항이 발생합니다. ANSI SQL 재귀 CTE는 각 노드에 대해 가장 긴 경로의 깊이를 계산하여 유효한 위상 수준을 제공하는 선언적 솔루션을 제공합니다.
핵심 문제는 고유 식별자가 포함된 tasks 테이블과 필수 관계를 정의하는 dependencies 테이블이라는 두 개의 관계형 구조를 포함합니다. 유효한 정렬을 위해서는 모든 작업이 모든 종속성이 나열된 후에만 나타나야 하므로, 각 엣지가 노드 A에서 노드 B로 이어질 때 rank(A) < rank(B) 여야 하는 숫자 순위가 필요합니다. 이 순위를 절차적 반복이나 가변 변수를 사용하지 않고 집합 기반으로 계산하는 데 어려움이 있습니다.
해결책은 즉각적인 선행 작업의 최대 수준에 1을 더한 값을 위상 수준으로 계산하며, 이 값은 그래프를 재귀적으로 전파됩니다. 들어오는 엣지가 없는 원 노드는 수준 0에서 초기화됩니다. 이 방법은 가장 긴 체인이 가장 조기에 실행 가능한 위치를 결정하기 때문에 여러 상속 경로가 있는 DAG를 올바르게 처리합니다. 재귀 CTE는 종속성 그래프에 대해 반복적으로 조인하여 자식 작업별로 그룹화하고 최대 부모 수준을 집계한 다음 증가시킵니다.
WITH RECURSIVE topo_levels AS ( -- 앵커: 입학 차수 0인 소스 노드 식별 SELECT t.task_id, 0 AS level, CAST(t.task_id AS VARCHAR(1000)) AS path_trace FROM tasks t WHERE NOT EXISTS ( SELECT 1 FROM dependencies d WHERE d.task_id = t.task_id ) UNION ALL -- 재귀적: 최대 선행자 수준에 따라 레벨 계산 SELECT d.task_id, MAX(tl.level) + 1, MAX(tl.path_trace) || '->' || CAST(d.task_id AS VARCHAR(1000)) FROM dependencies d INNER JOIN topo_levels tl ON d.depends_on_task_id = tl.task_id WHERE tl.level < 1000 -- 재귀 안전장치 GROUP BY d.task_id HAVING COUNT(DISTINCT d.depends_on_task_id) = ( -- 이 작업에 대한 모든 종속성이 해결되었는지 확인 SELECT COUNT(*) FROM dependencies d2 WHERE d2.task_id = d.task_id ) ) SELECT task_id, level, path_trace FROM topo_levels ORDER BY level, task_id;
한 금융 리스크 관리 플랫폼은 800개 이상의 파생 상품 가격 모델을 매일 밤 재계산해야 했으며, 이 과정에서 이국적인 옵션이 변동성 표면에 의존했고, 변동성 표면은 원시 시장 데이터 피드에 의존했습니다. 기존의 수동 Excel 추적은 의존성이 여섯 개의 계층 레벨로 증가하면서 실패했고, 그로 인해 하류 프로세스가 필수 조건을 완료하기 전에 실행되면서 빈번한 계산 오류가 발생했습니다. 엔지니어링 팀은 외부 조정 인프라를 추가하지 않고 이러한 작업의 순서를 매기기 위해 원자적이고 데이터베이스 고유의 솔루션이 필요했습니다.
세 가지 아키텍처 패턴이 평가되었습니다. 첫 번째는 Apache Airflow를 도입하는 것이었으며, 이는 강력한 모니터링 및 재시도 의미를 제공하지만 네트워크 지연, 외부 상태 관리 및 안전한 온프레미스 환경에 대한 상당한 라이센스 비용을 초래했습니다. 두 번째 제안은 종속성을 쿼리하고 작업을 순차적으로 실행하기 위해 psycopg2를 사용하는 Python 절차적 드라이버였습니다. 유연하긴 했지만, 이는 네트워크 파티션에 취약한 외부 종속성을 만들고 메타데이터 저장소와의 트랜잭션 일관성이 부족했습니다. 세 번째 접근 방식은 재귀 CTE를 사용하여 PostgreSQL 내에서 순수하게 위상 정렬을 구현하여 작업 정의와 종속성이 이미 존재하는 데이터베이스 내에서 모든 조정 논리를 유지했습니다.
팀은 순수 SQL 솔루션을 선택했습니다. 이 솔루션은 워크플로 메타데이터의 ACID 준수를 유지하고, 의존성 해결을 위한 네트워크 왕복을 없애며, 동일한 위상 수준을 공유하는 병렬 실행 후보를 식별하기 위해 데이터베이스 최적화를 활용합니다. 구현 이후, 작업 간의 병렬성이 이전에는 수동 시퀀싱으로 인해 가려졌던 것을 노출하여 야간 배치 창이 6시간에서 45분으로 단축되었으며, 이후 6개월 동안 의존성 관련 생산 실패가 0으로 감소했습니다.
입력 그래프에 우발적 사이클이 포함된 경우 무한 재귀로부터 어떻게 보호합니까? ANSI SQL 재귀 CTE는 순환 그래프에서 무한 루프를 발생시키거나 런타임 오류를 발생시킬 수 있습니다.
후보자들은 종종 DAG 속성이 응용 프로그램 계층에서 강화되고 있다는 데이터 무결성 보장을 가정합니다. 실제로는 고아 원형 참조(예: 작업 A는 B, B는 C, C는 A에 의존함)가 표준 재귀 CTE가 재귀 한계를 초과하거나 모든 리소스를 소모하게 합니다. 강력한 솔루션은 재귀를 통해 경로 추적 문자열 또는 배열을 운반한 다음, 현재 노드가 누적 경로 내에 이미 존재하지 않는 행을 제외하고 재귀 멤버에서 필터링하는 것입니다. 대안으로 SQL:2023는 CYCLE 절(SEARCH DEPTH FIRST ... CYCLE task_id SET is_cycle USING path)을 도입하여 사이클을 자동으로 감지하고 부울 플래그를 설정하여 쿼리가 실패하지 않고 정상적으로 종료될 수 있도록 합니다.
어째서 재귀 단계에서 단순히 임의의 단일 선행자의 수준에 1을 추가하기보다는 MAX를 사용해야 합니까?
많은 후보자들은 임의의 부모 작업에 조인하고 그 수준을 1씩 증가시키는 잘못된 제안을 합니다. 이는 DAG의 노드가 종종 깊이가 다른 여러 개의 들어오는 엣지를 가지고 있음을 간과합니다. 작업 D가 작업 A(수준 0)와 작업 C(수준 4)에 모두 의존한다고 가정해 보십시오. MIN 또는 임의의 조인을 사용하면 D의 수준이 1로 지정되어 C가 D보다 먼저 완료되어야 한다는 제약을 위반하게 됩니다. MAX 집계는 D가 수준 5를 받아 가장 긴 의존성 체인을 올바르게 수용하도록 보장합니다. 이 구별은 다이아몬드 모양 의존성이나 수렴 작업 패턴이 있는 그래프에서 정확성을 위해 매우 중요합니다.
표준 재귀 CTE 접근 방식이 종속성의 전체 테이블 스캔으로 인해 2차 성능 저하를 보일 때, 수백만 개의 노드가 포함된 그래프에 대해 이 쿼리를 어떻게 최적화하시겠습니까?
거대한 그래프의 경우, 순진한 접근 방식은 적절한 인덱스 전략 없이 기본 테이블에 대해 반복적인 조인을 suffer하는 문제가 발생합니다. 후보자들은 종종 재귀 CTE가 엣지 테이블의 부모 및 자식 열 모두에 대한 인덱스에서 큰 이점을 본다는 사실을 간과합니다. 인덱싱 외에 한 가지 최적화는 중복 엣지를 없애기 위해 전이 감소를 먼저 계산하거나 그래프를 연결된 구성 요소로 분할하고 독립적으로 처리하는 것입니다. 극단적인 경우 SQL이 기본적으로 그래프 탐색보다 관계형 대수를 최적화하는 것을 인식할 때, 순전히 집합 기반 솔루션을 강요하기보다는 전용 처리 엔진(예: GraphX, Neo4j, 또는 NetworkX)으로 그래프를 내보내는 것이 올바른 아키텍처 결정입니다. 하지만 SQL의 한계를 이해하는 것은 성숙한 엔지니어링 판단임을 보여줍니다.