質問への回答。

質問の歴史。

カダンのアルゴリズムは、1984年にジェイ・カダンによって策定され、動的プログラミングを通じて最大部分配列問題を解決します。これにより、現在の位置での最大合計と遭遇したグローバル最大値の2つの状態を追跡します。この命令的なパターンを宣言的な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消費のために生産規模での分析には不適切でした。

別のアプローチでは、Pythonとpsycopg2のプロシージャカーソルを使用して行を反復処理し、実行中の変数を保持しました。これにより直感的な命令的ロジックと簡単なデバッグが提供されましたが、データ転送オーバーヘッドを最小化するためのチームの指令に違反し、カーソルベースの処理は往復レイテンシとセットベースの最適化の欠如によりパフォーマンスが悪化しました。

カダンのアルゴリズムをシミュレートする再帰CTEの実装が選ばれました。このソリューションは、各パーティションを単一の線形パスで処理し、再帰レベルごとに2つのスカラー値のみを保存し、データベースエンジンのネイティブ最適化を活用しました。これにより、全データセットに対してミリ秒単位の応答時間を実現し、純粋に宣言的な方法のままでした。

実装は、400ms以内に5000以上の有価証券の最大利益連続期間を特定しました。その後、DBAチームは、このパターンをリスクメトリックの計算やボラティリティクラスタリングの検出を含む「最適ウィンドウ」の分析に採用しました。

候補者が見逃しがちな点

再帰CTEは、排他的に負の値を含むパーティションをどのように扱い、初期アンカー行の選択がどのように誤ったゼロの返却を防ぐのですか？

多くの候補者は、アンカーのメンバーでcurrent_maxとglobal_maxをゼロに初期化することで、全てが負のシーケンスに対してゼロを返す原因となり（間違って空の部分配列が最適であることを示唆します）、正しいアプローチは各パーティション内の最初の行の実際の値で両方の集計を初期化することです。これにより、[-5, -2, -8]のようなシーケンスに対して、クエリは0ではなく-2を正しく返します。部分配列は少なくとも1つの要素を含む必要があるという制約を遵守します。このエッジケースを考慮しないことは、損失のみの期間を分析するときにサイレントな論理エラーを引き起こします。

厳密にANSI SQLを使用して、最大部分配列の実際の開始点と終了点（特定の行）を取得できますか？

はい、しかし、メタデータを追跡するために再帰CTEを拡張する必要があります。以下の2つの追加列を持ち運ぶ必要があります：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が必要であり、これにより、一つの反復の出力を次の反復の入力として使用でき、宣言的なパラダイム内で行ごとの状態を維持する計算が可能になります。