再帰的共通テーブル式（Recursive CTE）の紹介：Databricks SQLをチューリング完全にする機能

Databricksでは現在、再帰的共通テーブル式（CTE）がサポートされています。これにより、SQLでループや探索処理を表現するネイティブな方法が提供され、階層データやグラフ構造データの操作が可能になります。これらの機能はSQL標準に準拠しており、Teradataなどの従来のデータウェアハウスで使用されている馴染みのあるパターンに従っているため、これらのシステムからの移行が大幅に簡素化されます。Databricksはまた、再帰的CTEのサポートをApache Spark™にもコントリビュートし、完全にオープンソース化しています。

Databricksでは、再帰的なCTEに対して標準的なANSI SQL構文を使用しています。これには、RECURSIVEキーワードも含まれています。

この一見小さな機能は、SQLの表現能力を大幅に強化し、理論的にはSQLをチューリング完全にします。つまり、コンピュータが実行可能なあらゆる計算をSQLで表現できるようになります。再帰的CTEは、従来はPythonや外部ツールなどの手続き型コードが必要だった複雑な問題を、組み合わせ可能なSQL構文で解決できるようになります。

再帰的CTEは現在、Public Preview DBSQL 2025.20およびDatabricks Runtime 17.0で利用可能です (近日中に Lakeflow Declarative Pipelinesにも導入予定です)。このブログでは、再帰的CTEがどのように動作し、純粋なSQLを使用して実際の問題を解決するのにどのように役立つかを探ります。

再帰的CTEサポートの主な特徴

Databricksの再帰的CTEサポートには以下のものが含まれます：

• 組織図、フォルダ、ルーティングネットワークなどのツリー構造やグラフ構造の探索
• 完全にオープンソースで、Apache Spark™に統合されています
• 無限再帰に対する組み込みの保護機能（100ステップ、100万行）
• MAX RECURSION LEVELを使用したカスタマイズ可能な保護機能
• LIMITを使用した制御可能な無限再帰のサポート

再帰的CTEは、階層データを正規化されたテーブルに保存する伝統的なシステムと、柔軟なJSON/XML階層を生成する現代のアプリケーションからのデータの両方でうまく機能します。以下に、JSON階層のためのVariantデータ型を活用したRCTEを含む各例を示します。

さらに、再帰的CTEのサポートにより、レガシーデータベースシステムからの移行が簡素化されます。TeradataとPostgresは、構文が同一であるシステムの例であり、CONNECT BY構文を使用するOracleなどのシステムからも簡単に変換できます。

再帰的CTEの動作方法

再帰的CTEは、RECURSIVEキーワードで定義された共通テーブル式です。これらは、UNION ALLを使用して組み合わせられた2つの部分で構成されています：

1. 基本ケースのサブクエリ — 一度だけ実行され、再帰処理の開始点となります
2. 再帰ステップサブクエリ — CTE自体を参照し、新しい行を生成するために繰り返し実行されます

実行は基本クエリから始まります。その後、各イテレーションで、前のステップの出力を使用して再帰ステップが実行されます。これは新しい行が生成されなくなるまで続きます。

無限再帰による過剰なリソース消費を防ぐため、Databricksでは2つの安全制限を設けています：最大再帰深度100ステップ、および行制限100万行です。いずれかの閾値を超えると、クエリはエラーで失敗します。

再帰処理ですべての結果を生成するために100ステップ以上が必要な場合は、MAX RECURSION LEVELヒントを使用して上限値を変更できます：

 詳細については、CTEの ドキュメンテーションを参照してください。

「bp Supply Trading and Shipping – Market Riskでは、ビジネスユニット間のポートフォリオ階層レポートの理解が、効率的な事業運営に不可欠です。従来のコードをDatabricks SQLの再帰的CTEに置き換えることで、階層データ準備処理を約6分から約30秒に短縮し、12倍の性能向上を実現しました」— Dharmik Prajapati, bp Staff Software Engineer

再帰的CTEを使用して反復的なタスクを解決する例

ツリーと階層データのナビゲーション：部品表を使用して必要な材料を見つける

製造業では、製造される各部品には組み立てるための一連のコンポーネントが必要です。各コンポーネントは、さらに小さな一連の個々の部品に分解することができます。すべての部品の完全なセットはBill of Materials（BOM）と呼ばれます。

BOMはしばしば木構造、あるいは一般的には有向非巡回グラフ（DAG）を形成します。この例では、自転車の部品を見てみます。ここでは、各コンポーネントが正確に1つの親で使用されると仮定して、ツリー構造を簡略化します。

自転車1台を作るために必要な原材料の量を計算したいとしましょう。次のBOMを考えてみてください：

各行は、コンポーネント名、それが属する上位部品、および上位部品1単位の組み立てに必要なコンポーネント数を表しています。

再帰的CTEは一つの目標から始まります：一台の自転車を組み立てること。それが基本ケースです。各再帰ステップでは、コンポーネントをそのサブコンポーネントに分解します。例えば、自転車はフレーム、ドライブトレイン、そして2つのホイールを含みます。それぞれのホイールは、タイヤと32本のスポークで構成されています。再帰構造は、部品をより小さなピースに分解すると明確になります。

階層を完全に展開した後、中間のコンポーネント（親）をフィルタリングして、組み立てに必要な原材料のみを保持します。

このクエリは、1台の自転車を作るために必要な各基本材料の総量を計算します：

グラフ探索に基づく経路探索：ある都市からのすべての飛行経路を見つける

グラフデータ構造を使用した問題を見てみましょう。グラフは、エッジで接続された一連のノードで構成されています。これは、要素のペア間の関係や接続を表現するために使用されます。グラフ問題の解決には、Python、複雑なスクリプトロジック、または外部ライブラリが必要でした。今、再帰クエリがそれを簡単にします。

典型的なグラフ構造の問題は航空旅行：どの空港に一連のフライトを使用して到達できますか？例えば、以下の一日に存在するフライトのセットがあるとします：

各フライトは、出発地と目的地のIATAコードとともに、出発時間と到着時間が与えられます。

ある人が8時にBEG空港に到着し、その日に可能な旅行ルートをすべて見つけたいとします。

これは自然に反復的な問題として設定されます。新たに到達できる都市を発見するたびに、そこから出発する全てのフライトを、我々の到着時間以降に見つけ出します。このため、再帰的なCTEでは、各空港での到着時間を追跡します。 

これにより、到達可能なすべての空港と、必要なフライトの数とセットが生成されます。

このクエリは、スケジュールの制約を考慮した上で、ユーザーが到達可能なすべての目的地を探索するのに役立ちます。これは、旅行計画、パッケージルーティング、輸送物流などのアプリケーションをサポートします。

前の例では、私たちはWITH RECURSIVE ... AS (...) 句で列名を定義しました。ここでは、基本クエリで列名を定義します。どちらのアプローチも、Databricksの再帰的CTEで有効です。

半構造化データと非構造化データの探索：JSONファイルに保存されたすべての従業員を見つける

伝統的なシステムは、階層データを厳格な正規化テーブルにしばしば保存します。一方、現代のアプリケーションは頻繁に柔軟なJSON/XML階層を生成します。Databricksの再帰CTEとVARIANTデータ型の組み合わせにより、これらのデータパターンをシームレスに処理でき、伝統的な正規化データと柔軟なJSON/XML構造の両方を単一のシステムでクエリできます。

この例では、（比較的小さな）会社の階層が与えられています。しかし、完全に構造化されたテーブルの代わりに、JSONの形で与えられています：

テーブル内のすべての従業員と彼らのタイトルのリストが欲しいとします。社員データのフィールドは統一されたスキーマに従っていません。一部の社員は直属の部下を持ち、他の社員は持っていません。一部は彼らの場所を持ち、一部は持っていません！DatabricksのVARIANTデータ型を使用すると、すべての必要な共通点を再帰CTE内で使用してJSONのネストされた構造を完全に探索でき、違いは無視できます。

再帰の 基本ケース は、ルート従業員の完全なJSONデータで、その中には 部下 のリストが含まれています。各再帰ステップでは、クエリは各部下のデータを処理し、部下がいない従業員に到達するまでプロセスを繰り返します。

この例のための再帰クエリは次の通りです：

ここでのすべてのCTEがWITH RECURSIVEブロックの下にあるにもかかわらず、実際に再帰が必要なものだけが再帰的として扱われます。Databricksは、どのものが再帰を必要とするかをスマートに検出します—あなたがすべてをマークしたとしても！

クエリの出力：

使用方法

Databricksのドキュメンテートを読んで、再帰的CTEの使用を始めてください。

Databricks SQLについて詳しく知りたい方は、私たちのウェブサイトを訪れるか、ドキュメントを読んでください。また、Databricks SQLのプロダクトツアーもチェックしてみてください。既存のウェアハウスを高性能で、サーバーレスのデータウェアハウスに移行したい場合、そして素晴らしいユーザーエクスペリエンスと低コストを求めている場合、Databricks SQLが解決策です。無料で試してみてください。