いくつか並列実行する部分区間をもつ E2E のレイテンシを分析する際、実行フローのクリティカルパスを特定したい。レイテンシのデータは field trace から取り出す。手元での計測ではなく、世の中（社内ベータテスト人口）の遅いケースではどんなクリティカルパスが支配的なのか。

・・・というような分析をするにあたり、データを Python に持っていくのではなく、できれば SQL だけで済ませたい。そこで SQL で shortest path を計算できないかチャットに聞いたら 「WITH RECURSIVE を使え」" という返事が来た。(実際は Claude でなく社内のチャットに聞いた。だいたい同じ返答だった。)

なんだそれ・・・ということで実際に試してみる。 (動かしてみたいひとはこの notebook をどうぞ):

WITH RECURSIVE paths AS (
  SELECT
    weight AS distance,
    dst AS tail,
    src || '.' || dst AS name
  FROM edges
  WHERE src = 'A'
  UNION ALL
  SELECT
    paths.distance + edges.weight AS distance,
    edges.dst AS tail,
    paths.name || '.' || edges.dst AS name
  FROM paths
  INNER JOIN edges ON edges.src = paths.tail
)
SELECT distance, name
FROM paths
WHERE tail = 'I'
ORDER BY distance

ここで "UNION ALL" を使うのは、わかるようなわからないようなかんじ。パーサは UNION ALL を使ったこの構造を特別に検知して再起（ループ）実行を plan するらしい。SQL なのに限りなく手続き的。

このアプローチはすべての経路を列挙するので効率的とはいえない。ダイクストラとかできないかな・・・とおもったが自分の SQL 力ではわからなかった。ただ自分の扱うフローは小さなグラフなので、このくらいの非効率は問題なさそう。

なおチャットはダイクストラもスルッと書いてよこしたが、正しいのかいまいちよくわからなかった・・・

-- Written by Claude. 
-- Not sure whether this is correct or a slop.
WITH RECURSIVE Dijkstra AS (
    -- Base case: starting node with cost 0
    SELECT 
        source_node AS node,
        0 AS cost,
        ARRAY[source_node] AS path
    FROM (SELECT 'A' AS source_node) s  -- Replace with your start node
    
    UNION ALL
    
    -- For each iteration, select the lowest-cost unvisited node
    SELECT 
        e.destination_node,
        d.cost + e.edge_weight,
        d.path || e.destination_node
    FROM Dijkstra d
    JOIN graph_edges e ON d.node = e.source_node
    WHERE NOT e.destination_node = ANY(d.path)
    -- This is critical - only process the lowest-cost node in each iteration
    AND NOT EXISTS (
        SELECT 1 FROM Dijkstra d2
        WHERE d2.cost < d.cost AND NOT EXISTS (
            SELECT 1 FROM Dijkstra d3
            WHERE d3.node = d2.node
        )
    )
)
SELECT node, path, cost
FROM Dijkstra
WHERE node = 'Z'  -- Replace with your destination node
ORDER BY cost
LIMIT 1;