再帰 CTE を使用する

GoogleSQL for BigQuery では、クエリ式で参照できる一時テーブルと 1 つ以上の共通テーブル式（CTE）が WITH 句に含まれています。CTE は、非再帰、再帰、またはその両方になり得ます。WITH 句で RECURSIVE キーワードを指定すると（WITH RECURSIVE）、再帰になります。

再帰 CTE は、その CTE 自体、先行する CTE、または後続の CTE を参照できます。非再帰 CTE は先行する CTE のみを参照でき、その CTE 自体は参照できません。再帰 CTE は、新しい結果が見つかるまで継続的に実行されますが、非再帰 CTE は 1 回だけ実行されます。このような理由から、再帰 CTE は階層データやグラフデータのクエリによく使用されます。

たとえば、各行が 1 つのノードを表し、そのノードは他のノードにリンクできるグラフを考えてみましょう。特定の開始ノードから到達可能なすべてのノードの推移的閉包を、最大ホップ数を知らずに求めるには、クエリに再帰 CTE が必要です（WITH RECURSIVE）。再帰クエリは、開始ノードの基本ケースから始まり、各ステップでは、前のステップまでに確認したすべてのノードから到達できる新しい未知のノードを計算することになります。新しいノードが見つからなくなると、クエリは終了します。

しかし再帰 CTE は計算量が多いため、使用する前に、このガイドと GoogleSQL リファレンス ドキュメントの WITH 句のセクションをご確認ください。

再帰 CTE を作成する

GoogleSQL で再帰 CTE を作成するには、次の例に示すように WITH RECURSIVE 句を使用します。

WITH RECURSIVE
  CTE_1 AS (
    (SELECT 1 AS iteration UNION ALL SELECT 1 AS iteration)
    UNION ALL
    SELECT iteration + 1 AS iteration FROM CTE_1 WHERE iteration < 3
  )
SELECT iteration FROM CTE_1
ORDER BY 1 ASC

上の例では、次の結果が生成されます。

/*-----------*
 | iteration |
 +-----------+
 | 1         |
 | 1         |
 | 2         |
 | 2         |
 | 3         |
 | 3         |
 *-----------*/

再帰 CTE には、基本的表現、ユニオン演算子、再帰的表現が含まれます。基本的表現は、再帰ユニオン演算の初回の反復処理を実行します。再帰的表現が残りの反復処理を実行します。また、再帰的表現には再帰 CTE への自己参照を 1 つ含める必要があります。自己参照を含むことができるのは再帰的表現だけです。

上の例では、再帰 CTE に次の構成要素が含まれています。

• 再帰 CTE 名: CTE_1
• 基本的表現: SELECT 1 AS iteration
• ユニオン演算子: UNION ALL
• 再帰的表現: SELECT iteration + 1 AS iteration FROM CTE_1 WHERE iteration < 3

再帰 CTE の構文、ルール、例の詳細については、GoogleSQL リファレンス ドキュメントの WITH 句をご覧ください。

有向非巡回グラフ（DAG）で到達可能性を確認する

有向非巡回グラフ（DAG）では、再帰クエリを使用して到達可能性を確認できます。次のクエリは、GraphData というグラフでノード 5 から到達できるすべてのノードを探索します。

WITH RECURSIVE
  GraphData AS (
    --    1          5
    --   / \        / \
    --  2 - 3      6   7
    --      |       \ /
    --      4        8
    SELECT 1 AS from_node, 2 AS to_node UNION ALL
    SELECT 1, 3 UNION ALL
    SELECT 2, 3 UNION ALL
    SELECT 3, 4 UNION ALL
    SELECT 5, 6 UNION ALL
    SELECT 5, 7 UNION ALL
    SELECT 6, 8 UNION ALL
    SELECT 7, 8
  ),
  R AS (
    (SELECT 5 AS node)
    UNION ALL
    (
      SELECT GraphData.to_node AS node
      FROM R
      INNER JOIN GraphData
        ON (R.node = GraphData.from_node)
    )
  )
SELECT DISTINCT node FROM R ORDER BY node;

上の例では、次の結果が生成されます。

/*------*
 | node |
 +------+
 | 5    |
 | 6    |
 | 7    |
 | 8    |
 *------*/

反復処理上限エラーのトラブルシューティング

再帰 CTE では、終了条件を満たさないまま再帰的表現が継続的に実行されると、無限再帰が発生する可能性があります。無限再帰を終了するために、再帰 CTE ごとに反復処理の上限が適用されます。BigQuery の反復処理の上限は 500 回です。再帰 CTE が反復処理の最大数に達すると、CTE の実行は中止され、エラーになります。

この上限が導入されている理由は、再帰 CTE の計算は高コストになり、大量の反復処理で CTE を実行すると多数のシステム リソースが消費され、完了までにかなりの時間がかかるためです。

反復処理の上限に達するクエリには、通常は適切な終了条件がないため、無限ループが発生するか、不適切なシナリオで再帰 CTE が使用されます。

再帰の反復処理上限エラーが発生した場合は、このセクションの提案を確認してください。

無限再帰を確認する

無限再帰を防ぐには、一定の回数の反復処理を行った後で再帰的表現が空の結果を生成できるようにします。

無限再帰を確認する 1 つの方法は、次のように、最初の 100 回の反復処理に REPEAT ループを使用して再帰 CTE を TEMP TABLE に変換することです。

DECLARE current_iteration INT64 DEFAULT 0;

CREATE TEMP TABLE recursive_cte_name AS
SELECT base_expression, current_iteration AS iteration;

REPEAT
  SET current_iteration = current_iteration + 1;
  INSERT INTO recursive_cte_name
    SELECT recursive_expression, current_iteration
    FROM recursive_cte_name
    WHERE termination_condition_expression
      AND iteration = current_iteration - 1
      AND current_iteration < 100;
  UNTIL NOT EXISTS(SELECT * FROM recursive_cte_name WHERE iteration = current_iteration)
END REPEAT;

次の値を置き換えます。

• recursive_cte_name: デバッグする再帰 CTE。
• base_expression: 再帰 CTE の基本的表現。
• recursive_expression: 再帰 CTE の再帰的表現。
• termination_condition_expression: 再帰 CTE の終了式。

たとえば、TestCTE という次の再帰 CTE を考えてみましょう。

WITH RECURSIVE
  TestCTE AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 3 FROM TestCTE WHERE MOD(n, 6) != 0
  )

この例では次の値を使用します。

• recursive_cte_name: TestCTE
• base_expression: SELECT 1
• recursive_expression: n + 3
• termination_condition_expression: MOD(n, 6) != 0

したがって次のコードでは、TestCTE をテストして無限再帰の有無を確認します。

DECLARE current_iteration INT64 DEFAULT 0;

CREATE TEMP TABLE TestCTE AS
SELECT 1 AS n, current_iteration AS iteration;

REPEAT
SET current_iteration = current_iteration + 1;

INSERT INTO TestCTE
SELECT n + 3, current_iteration
FROM TestCTE
WHERE
  MOD(n, 6) != 0
  AND iteration = current_iteration - 1
  AND current_iteration < 10;

UNTIL
  NOT EXISTS(SELECT * FROM TestCTE WHERE iteration = current_iteration)
    END REPEAT;

-- Print the number of rows produced by each iteration

SELECT iteration, COUNT(1) AS num_rows
FROM TestCTE
GROUP BY iteration
ORDER BY iteration;

-- Examine the actual result produced for a specific iteration

SELECT * FROM TestCTE WHERE iteration = 2;

上記の例では、反復処理 ID とその反復処理で生成された行の数を含む次の結果が生成されます。

/*-----------+----------*
 | iteration | num_rows |
 +-----------+----------+
 | 0         | 1        |
 | 1         | 1        |
 | 2         | 1        |
 | 3         | 1        |
 | 4         | 1        |
 | 5         | 1        |
 | 6         | 1        |
 | 7         | 1        |
 | 8         | 1        |
 | 9         | 1        |
 | 10        | 1        |
 *-----------+----------*/

2 の反復処理で生成された実際の結果は次のとおりです。

/*----------+-----------*
 | n        | iteration |
 +----------+-----------+
 | 7        | 2         |
 *----------+-----------*/

行数が常にゼロより大きい場合（この例ではそうなっています）、サンプルは無限に再帰する可能性が高くなります。

再帰 CTE の適切な使用を確認する

適切なシナリオで再帰 CTE を使用していることを確認します。再帰 CTE は、階層データとグラフデータをクエリするように設計されているため、計算コストが高くなる可能性があります。この 2 種類のデータをクエリしない場合は、非再帰 CTE で LOOP ステートメントを使用するなど、別の方法を検討してください。

1 つの再帰 CTE を複数の再帰 CTE に分割する

再帰 CTE の最大許容反復処理回数の上限を超えていると思われる場合は、再帰 CTE を複数の再帰 CTE に分割できます。

再帰 CTE は、次のようなクエリ構造で分割できます。

WITH RECURSIVE
  CTE_1 AS (
    SELECT base_expression
    UNION ALL
    SELECT recursive_expression FROM CTE_1 WHERE iteration < 500
  ),
  CTE_2 AS (
    SELECT * FROM CTE_1 WHERE iteration = 500
    UNION ALL
    SELECT recursive_expression FROM CTE_2 WHERE iteration < 500 * 2
  ),
  CTE_3 AS (
    SELECT * FROM CTE_2 WHERE iteration = 500 * 2
    UNION ALL
    SELECT recursive_expression FROM CTE_3 WHERE iteration < 500 * 3
  ),
  [, ...]
SELECT * FROM CTE_1
UNION ALL SELECT * FROM CTE_2 WHERE iteration > 500
UNION ALL SELECT * FROM CTE_3 WHERE iteration > 500 * 2
[...]

次の値を置き換えます。

• base_expression: 現在の CTE の基本的表現。
• recursive_expression: 現在の CTE の再帰的表現。

たとえば次のコードは、CTE を 3 つの異なる CTE に分割します。

WITH RECURSIVE
  CTE_1 AS (
    SELECT 1 AS iteration
    UNION ALL
    SELECT iteration + 1 AS iteration FROM CTE_1 WHERE iteration < 10
  ),
  CTE_2 AS (
    SELECT * FROM CTE_1 WHERE iteration = 10
    UNION ALL
    SELECT iteration + 1 AS iteration FROM CTE_2 WHERE iteration < 10 * 2
  ),
  CTE_3 AS (
    SELECT * FROM CTE_2 WHERE iteration = 10 * 2
    UNION ALL
    SELECT iteration + 1 AS iteration FROM CTE_3 WHERE iteration < 10 * 3
  )
SELECT iteration FROM CTE_1
UNION ALL
SELECT iteration FROM CTE_2 WHERE iteration > 10
UNION ALL
SELECT iteration FROM CTE_3 WHERE iteration > 20
ORDER BY 1 ASC

上記の例では、500 回の反復処理が 10 回の反復処理に置き換えられるので、クエリの結果をより迅速に確認できます。このクエリでは 30 行が生成されますが、各再帰 CTE の反復処理は 10 回のみです出力は次のようになります。

/*-----------*
 | iteration |
 +-----------+
 | 2         |
 | ...       |
 | 30        |
 *-----------*/

上記のクエリは、はるかに大規模な反復処理でテストできます。

再帰 CTE の代わりにループを使用する

反復処理の上限を回避するには、再帰 CTE の代わりにループを使用することを検討してください。ループは、さまざまなループ ステートメント（LOOP、REPEAT、WHILE など）のいずれかを使用して作成できます。詳細については、ループをご覧ください。

再帰の上限を変更する

次の条件に該当する場合は、カスタマーケアに連絡して再帰の上限を引き上げるように依頼してください。

• 再帰 CTE で 500 回を超える反復処理を実行する正当な理由がある。
• 実行時間が長くなっても構わない。

再帰の上限の引き上げには潜在的なリスクがあることに留意してください。

• メモリ超過やタイムアウトなどの別のエラー メッセージで CTE が失敗する場合があります。
• プロジェクトでオンデマンド料金モデルを使用している場合、容量ベースの料金モデルに切り替えるまで、CTE が課金階層のエラーで失敗する可能性があります。
• 多数の反復処理がある再帰 CTE では、多くのリソースが消費されます。これは、同じ予約内で実行されている他のクエリが共有リソースを奪い合うため、これらのクエリに影響する可能性があります。

料金

オンデマンド課金の場合、BigQuery は再帰 CTE を使用してクエリの実行中に処理されたバイト数に基づいて課金されます。

詳細については、クエリサイズの計算をご覧ください。

割り当て

再帰 CTE の割り当てと上限については、割り当てと上限をご覧ください。