質問への回答。

トポロジカルソートはグラフ理論およびスケジューリング数学から発生し、特に、特定の頂点が他の頂点に先行しなければならない依存関係グラフにおける実行シーケンスを確立するために開発されました。データベース環境では、これはETLワークフロー、スキーマ移行スクリプト、または参照整合性が階層操作にわたって尊重されなければならない複雑なデータ変換を調整する際に発生します。ANSI SQLの再帰的CTEは、各ノードへの最長経路の深さを計算することによって宣言的な解決策を提供し、これは有効なトポロジカルレベルとして機能します。

コアの問題は、ユニークな識別子を含むtasksテーブルと前提関係を定義するdependenciesテーブルという二つの関係構造に関連しています。有効なソートには、すべてのタスクがすべての依存関係がリストされた後にのみ表示される必要があり、ノードAからノードBへのすべてのエッジについてrank(A) < rank(B)という数値ランクが必要です。この課題は、手続き的イテレーションや可変変数なしにこのランクを計算することにあります。

解決策は、グラフを再帰的に伝播させ、すべての直接の前任者の最大レベルに1を加えたものとしてトポロジカルレベルを計算します。受け取るノードは、入辺がない場合にレベル0で初期化されます。この方法は、最長のチェーンが最も早い安全な実行位置を決定するため、複数の遺伝的継承パスを持つDAGを正しく処理します。再帰的CTEは、依存関係グラフに対して反復的に結合し、子タスクによってグループ化して、最大の親レベルを集約し、その後増分を行います。

WITH RECURSIVE topo_levels AS (
    -- アンカー：入度がゼロのソースノードを特定する
    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トラッキングは、依存関係が6つの階層に達すると計算エラーが頻発し、下流プロセスが前提条件を完了する前に実行されることが原因で失敗していました。エンジニアリングチームは、外部のオーケストレーションインフラを追加せずに、これらのタスクをシーケンスするための原子的なデータベースネイティブソリューションを必要としていました。

採用が検討された三つのアーキテクチャパターン。最初は、ネットワークのレイテンシや外部の状態管理、セキュアなオンプレミス環境に対するライセンスコストが大きいが、ロバストなモニタリングと再試行セマンティクスを提供するApache Airflowを採用することでした。二つ目は、依存関係をクエリしてタスクを順次実行するためにpsycopg2を使用したPython手続きドライバーを提案しました。柔軟でしたが、これは外部の依存関係を脆弱にし、ネットワークパーティションに弱く、メタデータリポジトリとのトランザクション整合性が欠如していました。三つ目のアプローチは、再帰的CTEを使用してPostgreSQL内で純粋にトポロジカルソートを実装し、タスク定義と依存関係がすでに存在しているデータベース内でオーケストレーションロジックを保持しました。

チームは、ワークフローメタデータとACID準拠を維持し、依存関係解決のためのネットワークラウンドトリップを排除し、データベースオプティマイザを活用して同一のトポロジカルレベルを共有する並列実行候補を特定する純粋なSQLソリューションを選択しました。実装後、夜間のバッチウィンドウは6時間から45分に圧縮され、手動シーケンシングによって隠されていた固有の並列性が明らかになり、依存関係に関連する生産失敗はその後の6ヶ月でゼロに減少しました。

候補者が見落とすことが多いこと

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）を導入し、これによりサイクルを自動的に検出し、ブールフラグを設定し、クエリが失敗せずに優雅に終了することができます。

なぜ再帰ステップがMAXを使用して集計しなければならないのか？単に任意の単一の前任者のレベルに1を加えるだけではいけないのか？

多くの候補者は任意の親タスクに結合してそのレベルを1増加させることを提案し、DAGのノードがしばしば深さの異なる複数の入辺を持つことを無視しています。タスクDがタスクA（レベル0）とタスクC（レベル4）の両方に依存していると考えてみてください。MINまたは任意の結合を使用するとDにレベル1が割り当てられ、Dの前にCが完了する必要があるという制約に違反します。MAX集計は、Dがレベル5を受け取り、最長の依存関係チェーンを正しく考慮することを保証します。この区別は、ダイヤモンド形の依存関係や収束するワークフローパターンを示すグラフの正しさにとって重要です。

標準の再帰的CTEアプローチが依存関係の完全テーブルスキャンによる二次的なパフォーマンス低下を示す場合に、数百万のノードを含むグラフのクエリをどのように最適化しますか？

巨大なグラフに対して、ナイーブなアプローチは適切なインデックス戦略なしでベーステーブルに再帰的に結合するため、繰り返しの結合の結果が持続する。候補者は、再帰的CTEがエッジテーブルの親列と子列の両方に対してインデックスから大いに利益を得ることを見落としがちです。インデックスに加えて、最初に冗長なエッジを排除するために推移的削減を計算するか、グラフを連結成分に分割して個別に処理することが一つの最適化手法です。極端な場合、SQLは根本的にリレーショナル代数のために最適化されていることを認識することが正しいアーキテクチャの決定であり、専用の処理エンジン（例：GraphX、Neo4j、またはNetworkX）にグラフをエクスポートすることになりますが、SQLの制限を理解することは成熟したエンジニアリング判断を示します。