Trabalhar com CTEs recursivos

No GoogleSQL para BigQuery, uma cláusula WITH contém uma ou mais expressões de tabela comuns (CTEs, na sigla em inglês) com tabelas temporárias que podem ser referenciadas em uma expressão de consulta. Os CTEs podem ser não recursivos, recursivos ou ambos. A palavra-chave RECURSIVE permite a recursão na cláusula WITH (WITH RECURSIVE).

Um CTE recursivo pode referenciar a si mesmo, um CTE anterior ou um CTE subsequente. Um CTE não recursivo pode se referir apenas a CTEs anteriores e não pode se referir a si mesmo. Os CTEs recursivos são executados continuamente até que nenhum novo resultado seja encontrado, enquanto os CTEs não recursivos são executados uma vez. Por esses motivos, os CTEs recursivos são normalmente usados para consultar dados hierárquicos e de gráficos.

Por exemplo, considere um gráfico em que cada linha representa um nó que pode ser vinculado a outros nós. Para encontrar o fechamento transitivo de todos os nós alcançáveis de um nó de início específico sem saber o número máximo de saltos, você precisará de um CTE recursivo na consulta (WITH RECURSIVE). A consulta recursiva começaria com o caso base do nó inicial, e cada etapa calcularia os novos nós não vistos que podem ser alcançados de todos os nós vistos até a etapa anterior. A consulta é concluída quando nenhum nó novo é encontrado.

No entanto, os CTEs recursivos podem ser caros em termos de computação. Portanto, antes de usá-los, leia este guia e a seção WITH da documentação de referência do GoogleSQL.

Criar um CTE recursivo

Para criar um CTE recursivo no GoogleSQL, use a cláusula WITH RECURSIVE, conforme mostrado no exemplo a seguir:

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

O exemplo anterior produz os seguintes resultados:

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

Um CTE recursivo inclui um termo base, um operador de união e um termo recursivo. O termo base executa a primeira iteração da operação de união recursiva. O termo recursivo executa as iterações restantes e precisa incluir uma autoreferência ao CTE recursivo. Somente o termo recursivo pode incluir uma autoreferência.

No exemplo anterior, o CTE recursivo contém os seguintes componentes:

• Nome recursivo do CTE: CTE_1
• Termo de base: SELECT 1 AS iteration
• Operador de união: UNION ALL
• Termo recursivo: SELECT iteration + 1 AS iteration FROM CTE_1 WHERE iteration < 3

Para saber mais sobre a sintaxe, as regras e os exemplos de CTE recursivos, consulte a cláusula WITH na documentação de referência do GoogleSQL.

Explorar a acessibilidade em um gráfico acíclico dirigido (DAG)

É possível usar uma consulta recursiva para explorar a acessibilidade em um gráfico acíclico dirigido (DAG). A consulta a seguir encontra todos os nós que podem ser alcançados do nó 5 em um gráfico chamado 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;

O exemplo anterior produz os seguintes resultados:

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

Resolver erros de limite de iteração

Os CTEs recursivos podem resultar em recursão infinita, que ocorre quando o termo recursivo é executado continuamente sem atender a uma condição de encerramento. Para encerrar recorrências infinitas, um limite de iterações para cada CTE recursivo é aplicado. Para o BigQuery, o limite de iteração é de 500 iterações. Quando um CTE recursivo atinge o número máximo de iterações, a execução do CTE é cancelada com um erro.

Esse limite existe porque a computação de um CTE recursivo pode ser cara, e executar um CTE com um grande número de iterações consome muitos recursos do sistema e leva muito mais tempo para ser concluído.

As consultas que alcançam o limite de iteração geralmente não têm uma condição de encerramento apropriada, criando um loop infinito ou usando CTEs recursivos em cenários inadequados.

Se ocorrer um erro no limite de iteração de recursão, veja as sugestões nesta seção.

Verificar a recursão infinita

Para evitar recursão infinita, verifique se o termo recursivo pode produzir um resultado vazio após executar um determinado número de iterações.

Uma maneira de verificar a recursão infinita é converter o CTE recursivo em um TEMP TABLE com uma repetição REPEAT para as primeiras iterações de 100, da seguinte maneira:

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;

Substitua os seguintes valores:

• recursive_cte_name: o CTE recursivo para depuração.
• base_expression: o termo base do CTE recursivo.
• recursive_expression: o termo recursivo do CTE recursivo.
• termination_condition_expression: a expressão de encerramento do CTE recursivo.

Por exemplo, considere o seguinte CTE recursivo chamado TestCTE:

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

Este exemplo usa os seguintes valores:

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

O código abaixo testaria o TestCTE em busca de recursão infinita:

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;

O exemplo anterior produz os resultados a seguir, que incluem o ID da iteração e o número de linhas que foram produzidas durante essa iteração:

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

Estes são os resultados reais produzidos durante a iteração 2:

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

Se o número de linhas for sempre maior que zero, o que é verdadeiro neste exemplo, a amostra provavelmente terá uma recursão infinita.

Verificar o uso adequado do CTE recursivo

Verifique se você está usando o CTE recursivo em um cenário adequado. Os CTEs recursivos podem ser caros de computar, porque foram projetados para consultar dados hierárquicos e dados de gráfico. Se você não estiver consultando esses dois tipos de dados, considere alternativas, como o uso da instrução LOOP com um CTE não recursivo.

Dividir o CTE recursivo em vários CTEs recursivos

Se você acha que seu CTE recursivo precisa de mais do que o número máximo de iterações permitidas, você pode dividi-lo em vários CTEs recursivos.

É possível dividir um CTE recursivo com uma estrutura de consulta semelhante a esta:

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

Substitua os seguintes valores:

• base_expression: o termo de base de termo recursivo para o CTE atual.
• recursive_expression: a expressão de termo recursivo para o CTE atual.

Por exemplo, o código abaixo divide um CTE em três CTEs distintos:

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

No exemplo anterior, 500 iterações foram substituídas por 10 iterações. Assim, é mais rápido ver os resultados da consulta. A consulta produz 30 linhas, mas cada CTE recursivo faz iterações apenas 10 vezes. A saída será assim:

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

É possível testar a consulta anterior em iterações muito maiores.

Usar um loop em vez de um CTE recursivo

Para evitar limites de iteração, considere usar um loop em vez de um CTE recursivo. É possível criar uma repetição com uma das várias instruções de loop, como LOOP, REPEAT ou WHILE. Para mais informações, consulte Repetições.

Mudar o limite recursivo

Se você acredita que os seguintes fatores se aplicam, entre em contato com o Atendimento ao cliente para aumentar o limite recursivo:

• Se você tiver um motivo válido para o CTE recursivo executar mais de 500 iterações.
• Você está de acordo com uma execução muito mais longa.

Lembre-se de que aumentar o limite recursivo pode causar riscos:

• O CTE pode falhar com uma mensagem de erro diferente, como memória excedida ou tempo limite.
• Se o projeto estiver usando o modelo de preços sob demanda, o CTE ainda poderá falhar com um erro no nível de faturamento até que você mude para o modelo de preços por capacidade.
• Um CTE recursivo com um grande número de iterações consome muitos recursos. Isso pode afetar outras consultas em execução na mesma reserva, já que elas competem por recursos compartilhados.

Preços

Se você usa o faturamento sob demanda, o BigQuery cobra com base no número de bytes processados durante a execução de uma consulta com um CTE recursivo.

Para mais informações, consulte Cálculo do tamanho da consulta.

Cotas

Para informações sobre cotas e limites de CTE recursivos, consulte Cotas e limites.