Mit rekursiven CTEs arbeiten

In GoogleSQL for BigQuery enthält eine WITH-Klausel einen oder mehrere allgemeine Tabellenausdrücke (CTEs) mit temporären Tabellen, auf die Sie in einem Abfrageausdruck verweisen können. CTEs können nicht rekursiv, rekursiv oder beides sein. Das Keyword RECURSIVE aktiviert die Rekursion in der WITH-Klausel (WITH RECURSIVE).

Eine rekursive CTE kann auf sich selbst, eine vorherige CTE oder eine nachfolgende CTE verweisen. Ein nicht rekursiver CTE kann nur auf vorherige CTEs und nicht auf sich selbst verweisen. Rekursive CTEs werden kontinuierlich ausgeführt, bis keine neuen Ergebnisse gefunden werden. Nicht rekursive CTEs werden einmal ausgeführt. Aus diesen Gründen werden häufig rekursive CTEs für die Abfrage hierarchischer Daten und Diagrammdaten verwendet.

Betrachten Sie beispielsweise ein Diagramm, in dem jede Zeile einen Knoten darstellt, der mit anderen Knoten verknüpft werden kann. Sie benötigen einen rekursiven CTE in der Abfrage (WITH RECURSIVE), um den transitiven Abschluss aller erreichbaren Knoten von einem bestimmten Startknoten zu ermitteln, ohne die maximale Anzahl von Hops zu kennen. Die rekursive Abfrage würde mit dem Basisfall des Startknotens beginnen und jeder Schritt würde die neuen, nicht erkannten Knoten berechnen, die von allen bisher gesehenen Knoten bis zum vorherigen Schritt erreicht werden können. Die Abfrage ist abgeschlossen, wenn keine neuen Knoten gefunden werden können.

Rekursive CTEs können jedoch rechenintensiv sein. Bevor Sie diese verwenden, lesen Sie diese Anleitung und den Abschnitt WITH-Klausel der GoogleSQL-Referenzdokumentation.

Rekursiven CTE erstellen

Verwenden Sie zum Erstellen eines rekursiven CTE in GoogleSQL die WITH RECURSIVE-Klausel, wie im folgenden Beispiel gezeigt:

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

Das vorherige Beispiel führt zu den folgenden Ergebnissen:

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

Ein rekursiver CTE enthält einen Basisbegriff, einen Union-Operator und einen rekursiven Begriff. Der Basisbegriff führt die erste Iteration des rekursiven Union-Vorgangs aus. Der rekursive Begriff führt die verbleibenden Iterationen aus und muss einen Selbstverweis auf den rekursiven CTE enthalten. Nur der rekursive Begriff kann einen Selbstverweis enthalten.

Im vorherigen Beispiel enthält der rekursive CTE die folgenden Komponenten:

  • Rekursiver CTE-Name: CTE_1
  • Basisbegriff: SELECT 1 AS iteration
  • Union-Operator: UNION ALL
  • Rekursiver Begriff: SELECT iteration + 1 AS iteration FROM CTE_1 WHERE iteration < 3

Weitere Informationen zur rekursiven CTE-Syntax, den Regeln und Beispielen finden Sie in der WITH-Klausel in der GoogleSQL-Referenzdokumentation.

Erreichbarkeit in einem gerichteten azyklischen Graphen (Directed Acyclic Graph, DAG) ansehen

Mit einer rekursiven Abfrage können Sie die Erreichbarkeit in einem gerichteten azyklischen Graphen (Directed Acyclic Graph, DAG) prüfen. Mit der folgenden Abfrage werden alle Knoten gefunden, die von Knoten 5 in einem Graphen namens GraphData erreicht werden können:

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;

Das vorherige Beispiel führt zu den folgenden Ergebnissen:

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

Fehler beim Iterationslimit beheben

Rekursive CTEs können zu einer unendlichen Rekursion führen, die auftritt, wenn der rekursive Begriff kontinuierlich ausgeführt wird, ohne eine Beendigungsbedingung zu erfüllen. Für das Beenden von unendlichen Wiederholungen wird ein Limit von Iterationen für jeden rekursiven CTE erzwungen. Für BigQuery beträgt das Iterationslimit 500 Iterationen. Sobald ein rekursiver CTE die maximale Anzahl von Iterationen erreicht hat, wird die CTE-Ausführung mit einem Fehler abgebrochen.

Dieses Limit besteht, da die Berechnung eines rekursiven CTE teuer sein kann und das Ausführen eines CTE mit einer großen Anzahl von Iterationen viele Systemressourcen verbraucht und sehr viel länger dauert.

Bei Abfragen, die das Iterationslimit erreichen, fehlt in der Regel eine ordnungsgemäße Beendigungsbedingung, sodass eine Endlosschleife entsteht oder rekursive CTEs in unangemessenen Szenarien verwendet werden.

Wenn ein Fehler mit einem Rekursionslimit auftritt, lesen Sie die Vorschläge in diesem Abschnitt.

Auf unendliche Rekursion prüfen

Achten Sie darauf, dass der rekursive Begriff nach der Ausführung einer bestimmten Anzahl von Iterationen ein leeres Ergebnis liefern kann, um eine unbegrenzte Rekursion zu verhindern.

Eine Möglichkeit zur Prüfung der unendlichen Rekursion besteht darin, den rekursiven CTE in einen TEMP TABLE mit einer REPEAT-Schleife für die ersten 100 Iterationen zu konvertieren:

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;

Ersetzen Sie die folgenden Werte:

  • recursive_cte_name: Der rekursive CTE zum Debuggen.
  • base_expression: Der Basisbegriff des rekursiven CTEs.
  • recursive_expression: Der rekursive Begriff des rekursiven CTEs.
  • termination_condition_expression: Der Beendigungsausdruck des rekursiven CTEs.

Betrachten Sie beispielsweise den folgenden rekursiven CTE namens TestCTE:

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

In diesem Beispiel werden die folgenden Werte verwendet:

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

Mit dem folgenden Code wird daher TestCTE auf unendliche Rekursion getestet:

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;

Das vorherige Beispiel liefert die folgenden Ergebnisse, die die Iterations-ID und die Anzahl der Zeilen enthalten, die während dieses Durchlaufs erstellt wurden:

/*-----------+----------*
 | 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        |
 *-----------+----------*/

Dies sind die tatsächlichen Ergebnisse, die während der Iteration 2 erstellt wurden:

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

Wenn die Anzahl der Zeilen immer größer als null ist, was in diesem Beispiel der Fall ist, hat die Stichprobe wahrscheinlich eine unendliche Rekursion.

Angemessene Verwendung des rekursiven CTE überprüfen

Prüfen Sie, ob Sie den rekursive CTE in einem geeigneten Szenario verwenden. Rekursive CTEs können teuer sein, da sie zum Abfragen von Hierarchiedaten und Graphdaten verwendet werden. Wenn Sie diese beiden Arten von Daten nicht abfragen, sollten Sie Alternativen in Betracht ziehen, z. B. die Verwendung der LOOP-Anweisung mit einem nicht rekursiven CTE.

Rekursiven CTE in mehrere rekursive CTEs aufteilen

Wenn Sie der Meinung sind, dass Ihre rekursive CTE mehr als die maximal zulässige Iteration benötigt, können Sie Ihre rekursive CTE in mehrere rekursive CTEs aufteilen.

Sie können einen rekursiven CTE mit einer Abfragestruktur wie der folgenden aufteilen:

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
[...]

Ersetzen Sie die folgenden Werte:

  • base_expression: Der Basisbegriffsausdruck für den aktuellen CTE.
  • recursive_expression: Der rekursive Begriffsausdruck für den aktuellen CTE.

Der folgende Code teilt einen CTE beispielsweise in drei verschiedene CTEs auf:

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

Im vorherigen Beispiel werden 500 Iterationen durch zehn Iterationen ersetzt, sodass die Ergebnisse der Abfrage schneller angezeigt werden. Die Abfrage erzeugt 30 Zeilen, aber jeder rekursive CTE iteriert nur zehnmal. Die Ausgabe sieht in etwa so aus:

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

Sie können die vorherige Abfrage bei viel größeren Iterationen testen.

Anstelle eines rekursiven CTE eine Schleife verwenden

Um Iterationslimits zu vermeiden, sollten Sie eine Schleife anstelle eines rekursiven CTE verwenden. Sie können eine Schleife mit einer von mehreren Schleifenanweisungen erstellen, z. B. LOOP, REPEAT oder WHILE. Weitere Informationen zu Schleifen.

Rekursives Limit ändern

Wenn Sie der Meinung sind, dass die folgenden Faktoren zutreffen, wenden Sie sich an den Kundensupport, um das rekursive Limit zu erhöhen:

  • Es gibt einen relevanten Grund dafür, dass der rekursive CTE mehr als 500 Iterationen ausführt.
  • Sie sind mit einer viel längeren Ausführung zufrieden.

Beachten Sie, dass das Erhöhen des rekursiven Limits potenzielle Risiken mit sich bringt:

  • Ihr CTE kann mit einer anderen Fehlermeldung fehlschlagen, z. B. Speicher überschritten oder Timeout.
  • Wenn Ihr Projekt das On-Demand-Preismodell verwendet, schlägt Ihr CTE möglicherweise mit einem Fehler der Abrechnungsstufe fehl, bis Sie zum kapazitätsbasierten Preismodell wechseln.
  • Ein rekursiver CTE mit einer großen Anzahl von Iterationen verbraucht viele Ressourcen. Das kann sich auf andere Abfragen auswirken, die in derselben Reservierung ausgeführt werden, da sie um gemeinsam genutzte Ressourcen konkurrieren.

Preise

Wenn Sie On-Demand-Abrechnung verwenden, erfolgt die Abrechnung von BigQuery entsprechend der Anzahl der Byte, die während der Ausführung einer Abfrage mit einem rekursiven CTE verarbeitet werden.

Weitere Informationen zu Abfragegrößenberechnung.

Kontingente

Informationen zu rekursiven CTE-Kontingenten und -Limits finden Sie unter Kontingente und Limits.