질문에 대한 답변.

질문의 역사.

카다인의 알고리즘은 1984년 Jay Kadane에 의해 형성되었으며, 현재 위치에서 끝나는 최대 합계와 만난 전역 최대를 추적하여 동적 프로그래밍을 통해 최대 하위 배열 문제를 해결합니다. 이 명령형 패턴을 선언형 ANSI SQL로 변환하는 것은 재귀 CTE를 통해 순차적 반복을 시뮬레이션하는 것을 요구합니다. 표준 창 함수는 이전 행의 계산 결과에 의존하는 실행 집계를 표현할 수 없으므로, 복잡한 알고리즘 논리를 집합 기반 처리의 제약 내에서 구현하는 응시자의 능력을 테스트합니다.

문제.

정렬된 숫자 관찰 테이블(예: 일일 손익)에서 단일 연속 행 블록을 식별하는 것이 목표입니다. 단순한 실행 총계와는 달리, 최적의 하위 배열은 임의의 지점에서 시작하고 끝날 수 있으며, 현재 하위 배열을 확장할 것인지 또는 매 행마다 새로 시작할 것인지는 직전 하위 배열의 누적 합에 따라 달라집니다. 이 의존성은 간단한 집계를 금지하는 재귀 정의를 만듭니다.

해결책.

우리는 처음 행을 current_max_ending_here 및 global_max_so_far로 초기화하는 재귀 CTE를 사용합니다. 재귀 구성원은 정렬 키를 사용하여 다음 행에 조인하며, 새 current_max를 GREATEST(current_value, previous_current_max + current_value)로 계산하고 global_max는 GREATEST(previous_global_max, new_current_max)로 업데이트합니다. 최종 집계는 모든 반복에서 최대 global_max를 선택합니다. 이 접근법은 각 파티션에 대해 O(n) 시간에 실행되며, 순수한 집합 기반으로 유지됩니다.

WITH RECURSIVE numbered AS (
    SELECT 
        partition_id,
        observation_date,
        value,
        ROW_NUMBER() OVER (PARTITION BY partition_id ORDER BY observation_date) AS rn
    FROM daily_returns
),
kadane AS (
    -- 앵커: 각 파티션의 첫 번째 행으로 초기화
    SELECT 
        partition_id,
        rn,
        value,
        value AS current_max_ending_here,
        value AS global_max_so_far
    FROM numbered
    WHERE rn = 1
    
    UNION ALL
    
    -- 재귀 단계: 상태를 앞으로 전파
    SELECT 
        n.partition_id,
        n.rn,
        n.value,
        GREATEST(n.value, k.current_max_ending_here + n.value) AS current_max_ending_here,
        GREATEST(k.global_max_so_far, GREATEST(n.value, k.current_max_ending_here + n.value)) AS global_max_so_far
    FROM kadane k
    JOIN numbered n 
        ON k.partition_id = n.partition_id 
        AND n.rn = k.rn + 1
)
SELECT partition_id, MAX(global_max_so_far) AS maximum_subarray_sum
FROM kadane
GROUP BY partition_id;

삶의 상황

정량적 거래 데스크는 모멘텀 전략을 위한 최적의 역사적 윈도우를 식별할 필요가 있었습니다. 특히, 자산 클래스마다 가장 높은 누적 수익을 제공하는 연속 거래 일 수열을 요구했습니다. 데이터 세트는 주식 기호별로 파티션화된 수백만 개의 일일 P&L 기록을 포함하고 있으며, 연구 팀은 수천 개의 증권에 대한 임시 분석을 위해 서브 초 소요 대기를 요구했습니다.

개념 증명 단계에서 초기에는 테이블을 자체적으로 자기 조인하여 가능한 모든 시작 및 종료 날짜를 생성한 후 그 사이의 합을 집계하는 단순한 강제 조인 접근 방식을 사용했습니다. 이 접근 방식은 재귀 CTE가 필요하지 않았고 개념적으로 간단했지만, O(n²) 복잡도로 인해 실행 몇 시간 후에 쿼리 타임아웃이 발생하여 생산 규모 분석에는 비현실적이었습니다. CPU 및 I/O 소비가 지나치기 때문입니다.

대안적인 접근법으로는 psycopg2와 함께 Python의 절차적 커서를 사용하여 행을 반복하면서 실행 변수를 유지하는 방식이 있었습니다. 이는 직관적인 명령형 논리를 제공하고 디버깅이 용이했지만, 데이터 전송 오버헤드를 최소화하기 위한 팀의 요구 사항을 위반했으며, 커서 기반 처리의 성능이 둔화되어 대기 시간이 길어지고 집합 기반 최적화가 결여되었습니다.

카다인의 알고리즘을 시뮬레이션하는 재귀 CTE 구현이 선택되었습니다. 이 솔루션은 각 파티션을 단일 선형 패스로 처리하며, 재귀 수준당 두 개의 스칼라 값만 저장하고 데이터베이스 엔진의 재귀 쿼리에 대한 기본 최적화를 활용했습니다. 이는 전체 데이터 세트에서 원하는 밀리초 수준의 응답 시간을 달성했습니다.

구현은 400ms 이내에 5천 개 이상의 증권에 대한 최대 수익의 비율을 성공적으로 식별했습니다. DBA 팀은 후속으로 위험 지표 계산 및 변동성 클러스터링 탐지를 포함한 유사한 "최선의 윈도우" 분석을 위해 이 패턴을 채택했습니다.

후보자들이 자주 놓치는 점

재귀 CTE가 오로지 음수값만으로 이루어진 파티션을 어떻게 다루며, 초기 앵커 행 선택이 잘못된 0 반환을 방지하는 이유는 무엇입니까?

많은 후보자들이 앵커 구성원에서 current_max와 global_max를 0으로 초기화하는데, 이는 알고리즘이 모두 음수인 수열에 대해 0을 반환하게 만들어 (비어 있는 하위 배열이 최적임을 잘못 암시합니다). 올바른 접근 방식은 각 파티션의 첫 번째 행의 실제 값으로 두 집계 모두를 초기화하는 것입니다. 이는 [-5, -2, -8]와 같은 수열에서 쿼리가 0이 아닌 -2를 올바르게 반환하도록 보장합니다. 이 한계 사례를 고려하지 않으면 손실만 발생하는 기간 분석 시 논리적 오류가 발생하게 됩니다.

최대 하위 배열의 실제 시작 및 종료 경계(구체적인 행)를 순수 ANSI SQL을 사용하여 검색할 수 있습니까?

예, 그러나 메타데이터를 추적하기 위해 재귀 CTE를 확장해야 합니다. 두 개의 추가 열: current_start_rn (현재 후보 하위 배열의 시작 인덱스)와 best_start_rn/best_end_rn (전역 최대의 경계)을 유지해야 합니다. 재귀 구성원에서 현재 값이 확장된 합계를 초과하면 current_start_rn을 현재 row_num으로 설정하고, 그렇지 않으면 이전 행에서 상속합니다. global_max_so_far가 업데이트될 때 현재 row_num을 best_end_rn으로 캡처하고 current_start_rn을 best_start_rn으로 캡처합니다. 이는 재귀 CTE가 단순한 스칼라 축적기뿐만 아니라 복잡한 상태 개체를 유지할 수 있다는 이해를 보여줍니다. 이는 최적 윈도우의 위치를 복원할 수 있게 해줍니다.

이 문제를 SUM() OVER 또는 MAX() OVER와 같은 표준 창 함수를 사용하여 해결할 수 없는 이유는 무엇이며, SQL 표준의 어떤 구체적인 제한이 창 기반 접근 방식을 방해합니까?

표준 창 함수는 정적으로 정의된 프레임(예: ROWS BETWEEN)에서 집계를 계산합니다. 최대 하위 배열 문제는 현재 행을 포함할지 여부가 이전 행의 집계 결과에 따라 달라지는 실행 집계를 요구합니다. 이는 상호 의존성 또는 재귀를 생성하여 창 함수가 표현할 수 없게 합니다. 재귀 CTE가 필요합니다. 이는 한 반복의 출력을 다음에 대한 입력으로 사용할 수 있게 해서 선언적 패러다임 내에서 행별 상태 기반 계산을 가능하게 합니다.