Utiliser des CTE récursives

Dans GoogleSQL pour BigQuery, une clause WITH contient une ou plusieurs expressions de table courantes (CTE) avec des tables temporaires que vous pouvez référencer dans une expression de requête. Les CTE peuvent être non récursives, récursives ou les deux. Le mot clé RECURSIVE active la récursion dans la clause WITH (WITH RECURSIVE).

Une CTE récursive peut se référencer elle-même, référencer une CTE précédente ou une CTE ultérieure. Une CTE non récursive ne peut référencer que les CTE précédentes et ne peut pas se référencer elle-même. Les CTE récursives s'exécutent en continu jusqu'à ce qu'aucun nouveau résultat ne soit trouvé, tandis que les CTE non récursives s'exécutent une fois. Pour ces raisons, les CTE récursives sont couramment utilisées pour interroger des données hiérarchiques et des données graphiques.

Prenons l'exemple d'un graphique dans lequel chaque ligne représente un nœud pouvant être associé à d'autres nœuds. Pour trouver la fermeture transitive de tous les nœuds accessibles à partir d'un nœud de démarrage particulier sans connaître le nombre maximal de sauts, vous avez besoin d'une CTE récursive dans la requête (WITH RECURSIVE). La requête récursive commence par le cas de base du nœud de démarrage, et chaque étape calcule les nouveaux nœuds jamais observés qui sont accessibles à partir de tous les nœuds observés jusqu'à l'étape précédente. La requête se termine lorsqu'aucun nouveau nœud ne peut être trouvé.

Toutefois, les CTE récursives peuvent être coûteuses en ressources informatiques. Par conséquent, avant de les utiliser, consultez ce guide et la section sur la clause WITH dans la documentation de référence de GoogleSQL.

Créer une CTE récursive

Pour créer une CTE récursive dans GoogleSQL, utilisez la clause WITH RECURSIVE comme indiqué dans l'exemple suivant :

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

L'exemple précédent produit les résultats suivants :

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

Une CTE récursive inclut une condition de base, un opérateur d'union et une condition récursive. La condition de base exécute la première itération de l'opération d'union récursive. La condition récursive exécute les itérations restantes et doit inclure une auto-référence à la CTE récursive. Seule la condition récursive peut inclure une auto-référence.

Dans l'exemple précédent, la CTE récursive contient les composants suivants :

• Nom de la CTE récursive: CTE_1
• Condition de base : SELECT 1 AS iteration
• Opérateur d'union : UNION ALL
• Condition récursive : SELECT iteration + 1 AS iteration FROM CTE_1 WHERE iteration < 3

Pour en savoir plus sur la syntaxe, les règles et les exemples de CTE récursives, consultez la section Clause WITH dans la documentation de référence de GoogleSQL.

Explorer la joignabilité dans un graphe orienté acyclique (DAG)

Vous pouvez utiliser une requête récursive pour explorer la joignabilité dans un graphe orienté acyclique (DAG). La requête suivante recherche tous les nœuds accessibles à partir du nœud 5 dans un graphe appelé GraphData :

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;

L'exemple précédent produit les résultats suivants :

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

Résoudre les erreurs de limite d'itération

Les CTE récursives peuvent entraîner une récursion infinie qui se produit lorsque la condition récursive s'exécute en continu sans répondre à une condition de fin. Pour mettre fin aux récursions infinies, une limite du nombre d'itérations est appliquée à chaque CTE récursive. BigQuery applique une limite de 500 itérations. Une fois que la CTE récursive atteint le nombre maximal d'itérations, l'exécution de la CTE est annulée avec une erreur.

Cette limite existe, car le calcul d'une CTE récursive peut s'avérer coûteux, et l'exécution d'une CTE avec un grand nombre d'itérations consomme de nombreuses ressources système et prend beaucoup plus de temps.

Les requêtes atteignant une limite d'itération ne disposent généralement pas d'une condition de fin appropriée, ce qui crée une boucle infinie ou utilise des CTE récursives dans des scénarios inappropriés.

Si vous rencontrez une erreur de limite d'itération de récursion, consultez les suggestions de cette section.

Vérifier la récursion infinie

Pour éviter une récursion infinie, assurez-vous que la condition récursive peut produire un résultat vide après avoir exécuté un certain nombre d'itérations.

Pour vérifier une récursion infinie, vous pouvez convertir votre CTE récursive en TEMP TABLE avec une boucle REPEAT pour les premières 100 itérations, comme suit :

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;

Remplacez les valeurs suivantes :

• recursive_cte_name: CTE récursive à déboguer.
• base_expression : condition de base de la CTE récursive.
• recursive_expression : condition récursive de la CTE récursive.
• termination_condition_expression : expression de fin de la CTE récursive.

Par exemple, considérons la CTE récursive suivante appelée TestCTE :

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

Cet exemple utilise les valeurs suivantes :

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

Le code suivant teste donc la récursion infinie de 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;

L'exemple précédent produit les résultats suivants, qui incluent l'ID d'itération et le nombre de lignes générées lors de cette itération :

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

Voici les résultats réels produits lors de l'itération 2:

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

Si le nombre de lignes est toujours supérieur à zéro, ce qui est le cas dans cet exemple, il est probable qu'il existe une récursion infinie.

Vérifier l'utilisation appropriée de la CTE récursive

Vérifiez si vous utilisez la CTE récursive dans un scénario approprié. Les CTE récursives peuvent être coûteuses à calculer, car elles sont conçues pour interroger des données hiérarchiques et des données graphiques. Si vous n'interrogez pas ces deux types de données, envisagez d'autres solutions, telles que l'utilisation de l'instruction LOOP avec une CTE non récursive.

Diviser une CTE récursive en plusieurs CTE récursives

Si vous pensez que votre CTE récursive a besoin de plus d'itérations que le nombre maximal autorisé, vous pourrez peut-être décomposer votre CTE récursive en plusieurs CTE récursives.

Vous pouvez diviser une CTE récursive avec une structure de requête semblable à celle-ci :

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

Remplacez les valeurs suivantes :

• base_expression : expression de condition de base pour la CTE actuelle.
• recursive_expression : expression de condition récursive pour la CTE actuelle.

Par exemple, le code suivant divise une CTE en trois CTE distinctes :

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

Dans l'exemple précédent, 500 itérations sont remplacées par 10 itérations afin d'accélérer l'affichage des résultats de la requête. La requête génère 30 lignes, mais chaque CTE récursive n'effectue que 10 itérations. La sortie ressemble à ceci :

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

Vous pouvez tester la requête précédente sur des itérations beaucoup plus volumineuses.

Utiliser une boucle au lieu d'une CTE récursive

Pour éviter les limites d'itération, envisagez d'utiliser une boucle au lieu d'une CTE récursive. Vous pouvez créer une boucle avec l'une des instructions de boucle, telle que LOOP, REPEAT ou WHILE. Pour plus d'informations, consultez la section Boucles.

Modifier la limite récursive

Si vous pensez que les facteurs suivants s'appliquent, contactez le service client pour augmenter la limite récursive :

• Vous avez une raison valide d'exécuter plus de 500 itérations par votre CTE récursive.
• Vous acceptez une exécution beaucoup plus longue.

N'oubliez pas que l'augmentation de la limite récursive présente des risques potentiels :

• Votre CTE peut échouer avec un message d'erreur différent, tel qu'un dépassement de la mémoire ou le délai avant expiration.
• Si votre projet utilise le modèle de tarification à la demande, votre CTE peut toujours échouer avec une erreur de niveau de facturation jusqu'à ce que vous passiez au modèle de tarification basé sur la capacité.
• Une CTE récursive avec un grand nombre d'itérations consomme beaucoup de ressources. Cela peut affecter les autres requêtes exécutées dans la même réservation, car elles sont en concurrence pour les ressources partagées.

Tarifs

Si vous utilisez la facturation à la demande, BigQuery facture le nombre d'octets traités lors de l'exécution d'une requête avec une CTE récursive.

Pour en savoir plus, consultez la section Calcul de la taille des requêtes.

Quotas

Pour en savoir plus sur les quotas et limites des CTE récursives, consultez la page Quotas et limites.