LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ikejiri-makoto2

🚀 Databricksで再帰的CTEが使えるようになったので、東京から箱根までの最短経路を探してみた件

Posted at

はじめに - なぜ今さら再帰的CTE？

どうも、SQLで階層データを扱うたびに「なんでDatabricksは再帰的CTE使えないんだよ...」と嘆いていた皆さん、朗報です。

ついに来ました。Databricksで再帰的CTEが使えるようになりました！ 🎉

「え、今さら？PostgreSQLでは太古の昔から使えたよ？」という声が聞こえてきそうですが、まあそこは大人の事情ということで。

今回は、Databricksの公式ブログを参考に、実際に再帰的CTEを使ってグラフ探索や階層データ処理など、実践的なSQLを試してみました。

📊 検証環境

  • Databricks Runtime: 17.1 Beta (includes Apache Spark 4.0.0, Scala 2.13)

🎯 今回試したこと

  1. 基本的な再帰 - 数列生成（これは定番）
  2. 階乗の計算 - 数学的な再帰の実装
  3. フィボナッチ数列 - プログラマーの友
  4. 日付範囲の生成 - カレンダーテーブル作成
  5. グラフの最短経路探索 - 東京から各都市への最短ルート（本記事の目玉！）
  6. 累積和の計算 - ウィンドウ関数の代替手段

1. 基本的な再帰的CTE - 数値のシーケンス生成

まずは最もシンプルな例から始めましょう。1から5までの数値を生成する基本的な再帰的CTEです。

    WITH RECURSIVE recursive_cte(n) AS (
      -- ベースケース: 初期値として1を設定
      SELECT 1 AS n

      UNION ALL
      
      -- 再帰ケース: 前の値に1を加える（n < 5まで）
      SELECT n + 1 AS n 
      FROM recursive_cte 
      WHERE n < 5
    )
    SELECT * FROM recursive_cte
    ORDER BY n

実行結果：

n
1
2
3
4
5

2. 階乗の計算

数学的な再帰の典型例である階乗（n!）を計算してみます。

    WITH RECURSIVE factorial_cte(n, factorial) AS (
      -- ベースケース: 0! = 1
      SELECT 0 AS n, 1 AS factorial
      
      UNION ALL
      
      -- 再帰ケース: n! = n * (n-1)!
      SELECT 
        n + 1 AS n,
        factorial * (n + 1) AS factorial
      FROM factorial_cte
      WHERE n < 10  -- 10!まで計算
    )
    SELECT n, factorial
    FROM factorial_cte
    ORDER BY n

実行結果：

n factorial
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800

3. フィボナッチ数列の生成

プログラミングの教科書でお馴染みのフィボナッチ数列も再帰的CTEで実装できます。

    WITH RECURSIVE fibonacci_cte(n, current, previous) AS (
      -- ベースケース: F(0) = 0, F(1) = 1
      SELECT 
        1 AS n,
        1 AS current,
        0 AS previous
      
      UNION ALL
      
      -- 再帰ケース: F(n) = F(n-1) + F(n-2)
      SELECT 
        n + 1 AS n,
        current + previous AS current,
        current AS previous
      FROM fibonacci_cte
      WHERE n < 15  -- 最初の15個のフィボナッチ数
    )
    SELECT n, current AS fibonacci_number
    FROM fibonacci_cte
    ORDER BY n

実行結果：

n fibonacci_number
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610

4. 日付範囲の生成

カレンダーテーブルの作成も再帰的CTEで簡単に行えます。

    WITH RECURSIVE date_range AS (
      -- ベースケース: 開始日
      SELECT 
        DATE'2024-01-01' AS date_value
      
      UNION ALL
      
      -- 再帰ケース: 1日ずつ追加
      SELECT 
        DATE_ADD(date_value, 1) AS date_value
      FROM date_range
      WHERE date_value < DATE'2024-01-10'
    )
    SELECT 
      date_value,
      DAYOFWEEK(date_value) AS day_of_week,
      CASE DAYOFWEEK(date_value)
        WHEN 1 THEN '日曜日'
        WHEN 2 THEN '月曜日'
        WHEN 3 THEN '火曜日'
        WHEN 4 THEN '水曜日'
        WHEN 5 THEN '木曜日'
        WHEN 6 THEN '金曜日'
        WHEN 7 THEN '土曜日'
      END AS day_name_ja
    FROM date_range
    ORDER BY date_value

実行結果：

date_value day_of_week day_name_ja
2024-01-01 2 月曜日
2024-01-02 3 火曜日
2024-01-03 4 水曜日
2024-01-04 5 木曜日
2024-01-05 6 金曜日
2024-01-06 7 土曜日
2024-01-07 1 日曜日
2024-01-08 2 月曜日
2024-01-09 3 火曜日
2024-01-10 4 水曜日

5. 東京から箱根までの最短経路をSQLで探す

まずはグラフデータを準備

    # グラフ（都市間の接続）のテストデータを作成
    from pyspark.sql.types import StructType, StructField, StringType, IntegerType

    graph_schema = StructType([
        StructField("from_city", StringType(), False),
        StructField("to_city", StringType(), False),
        StructField("distance", IntegerType(), False)
    ])

    graph_data = [
        ("東京", "横浜", 30),
        ("東京", "千葉", 40),
        ("横浜", "鎌倉", 20),
        ("千葉", "成田", 30),
        ("鎌倉", "小田原", 35),
        ("横浜", "小田原", 50),
        ("小田原", "箱根", 20)
    ]

    graph_df = spark.createDataFrame(graph_data, schema=graph_schema)
    graph_df.createOrReplaceView("city_connections")

    print("都市間接続データ:")
    graph_df.display()

都市間接続データ：

from_city to_city distance
東京 横浜 30
東京 千葉 40
横浜 鎌倉 20
千葉 成田 30
鎌倉 小田原 35
横浜 小田原 50
小田原 箱根 20

再帰的CTEで最短経路を探索！

ここが今回のハイライトです。東京から到達可能な全ての都市への最短距離と経路を一発で求めます：

    WITH RECURSIVE reachable_cities AS (
      -- ベースケース: 東京から直接行ける都市
      SELECT 
        '東京' AS start_city,
        to_city AS current_city,
        distance AS total_distance,
        CONCAT('東京 -> ', to_city) AS path,
        1 AS hop_count
      FROM city_connections
      WHERE from_city = '東京'
      
      UNION ALL
      
      -- 再帰ケース: さらに先の都市を探索
      SELECT 
        r.start_city,
        c.to_city AS current_city,
        r.total_distance + c.distance AS total_distance,
        CONCAT(r.path, ' -> ', c.to_city) AS path,
        r.hop_count + 1 AS hop_count
      FROM reachable_cities r
      INNER JOIN city_connections c ON r.current_city = c.from_city
      WHERE r.hop_count < 4  -- 最大4ホップまで
    )
    SELECT DISTINCT
      current_city AS destination,
      MIN(total_distance) AS shortest_distance,
      FIRST(path) AS sample_path,
      MIN(hop_count) AS min_hops
    FROM reachable_cities
    GROUP BY current_city
    ORDER BY shortest_distance

実行結果：

destination shortest_distance sample_path min_hops
横浜 30 東京 -> 横浜 1
千葉 40 東京 -> 千葉 1
鎌倉 50 東京 -> 横浜 -> 鎌倉 2
成田 70 東京 -> 千葉 -> 成田 2
小田原 80 東京 -> 横浜 -> 小田原 2
箱根 100 東京 -> 横浜 -> 小田原 -> 箱根 3

東京から箱根まで最短100kmで、横浜→小田原経由が最適ルートということが分かりました！

6. 累積和の計算

ウィンドウ関数を使わずに累積和を計算することも可能です。

    # 売上データの作成
    sales_schema = StructType([
        StructField("month", IntegerType(), False),
        StructField("sales", IntegerType(), False)
    ])

    sales_data = [
        (1, 100),
        (2, 150),
        (3, 200),
        (4, 180),
        (5, 220),
        (6, 250)
    ]

    sales_df = spark.createDataFrame(sales_data, schema=sales_schema)
    sales_df.createOrReplaceView("monthly_sales")

累積和を計算する再帰的CTE：

    WITH RECURSIVE cumulative_sales AS (
      -- ベースケース: 最初の月
      SELECT 
        month,
        sales,
        sales AS cumulative_total
      FROM monthly_sales
      WHERE month = 1
      
      UNION ALL
      
      -- 再帰ケース: 前月までの累計に当月を追加
      SELECT 
        s.month,
        s.sales,
        c.cumulative_total + s.sales AS cumulative_total
      FROM monthly_sales s
      INNER JOIN cumulative_sales c ON s.month = c.month + 1
    )
    SELECT 
      month,
      sales,
      cumulative_total,
      ROUND(100.0 * sales / cumulative_total, 2) AS percentage_of_cumulative
    FROM cumulative_sales
    ORDER BY month

実行結果：

month sales cumulative_total percentage_of_cumulative
1 100 100 100.00
2 150 250 60.00
3 200 450 44.44
4 180 630 28.57
5 220 850 25.88
6 250 1100 22.73

🚨 注意事項とベストプラクティス

再帰的CTEを使う際の注意点をまとめました：

1. パフォーマンス

再帰的CTEは便利ですが、大量のデータや深い再帰には注意が必要です。

2. 終了条件

必ずWHERE句で終了条件を設定しましょう。今回の例では：

  • グラフ探索: WHERE r.hop_count < 4
  • 日付生成: WHERE date_value < DATE'2024-01-10'

終了条件がないと、理論上は無限に再帰してしまいます

3. メモリ使用量

再帰の深さが増すとメモリ使用量も増加します。特に各ステップで大量のデータを保持する場合は要注意です。

4. 代替手段の検討

場合によっては、ウィンドウ関数やJOINの方が効率的なことがあります。例えば累積和の計算は：

    -- ウィンドウ関数を使った方が効率的
    SELECT 
      month,
      sales,
      SUM(sales) OVER (ORDER BY month) AS cumulative_total
    FROM monthly_sales

🎬 まとめ

Databricksでの再帰的CTEサポートにより、以下のようなケースでSQLだけで複雑な処理が可能になりました：

  • ✅ 階層データの処理（組織図、カテゴリツリーなど）
  • ✅ グラフの探索（最短経路、到達可能性など）
  • ✅ 時系列データの生成
  • ✅ 数学的な再帰処理

ただし、パフォーマンスには注意が必要です。特に本番環境では、データ量と再帰の深さを考慮して使用しましょう。

「SQLだけでこんなことができるんだ！」 という発見があれば幸いです。

再帰的CTEを使った面白いユースケースがあれば、ぜひコメントで教えてください！

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?