Em primeiro lugar, vamos tentar simplificar e esclarecer a descrição do algoritmo dada na página de manual. Para simplificar, considere apenas
union all em with recursive cláusula por enquanto (e union mais tarde):WITH RECURSIVE pseudo-entity-name(column-names) AS (
Initial-SELECT
UNION ALL
Recursive-SELECT using pseudo-entity-name
)
Outer-SELECT using pseudo-entity-name
Para esclarecer, vamos descrever o processo de execução da consulta em pseudocódigo:
working-recordset = result of Initial-SELECT
append working-recordset to empty outer-recordset
while( working-recordset is not empty ) begin
new working-recordset = result of Recursive-SELECT
taking previous working-recordset as pseudo-entity-name
append working-recordset to outer-recordset
end
overall-result = result of Outer-SELECT
taking outer-recordset as pseudo-entity-name
Ou ainda mais curto - o mecanismo de banco de dados executa a seleção inicial, tomando suas linhas de resultado como conjunto de trabalho. Em seguida, ele executa repetidamente a seleção recursiva no conjunto de trabalho, sempre substituindo o conteúdo do conjunto de trabalho pelo resultado da consulta obtido. Este processo termina quando o conjunto vazio é retornado pela seleção recursiva. E todas as linhas de resultados dadas primeiro pela seleção inicial e depois pela seleção recursiva são reunidas e alimentadas para a seleção externa, cujo resultado se torna o resultado geral da consulta.
Esta consulta está calculando fatorial de 3:
WITH RECURSIVE factorial(F,n) AS (
SELECT 1 F, 3 n
UNION ALL
SELECT F*n F, n-1 n from factorial where n>1
)
SELECT F from factorial where n=1
Seleção inicial
SELECT 1 F, 3 n nos dá valores iniciais:3 para argumento e 1 para valor de função.Seleção recursiva
SELECT F*n F, n-1 n from factorial where n>1 afirma que toda vez que precisamos multiplicar o valor da última função pelo valor do último argumento e diminuir o valor do argumento.O mecanismo de banco de dados executa assim:
Antes de tudo, ele executa o initail select, que fornece o estado inicial do conjunto de registros de trabalho:
F | n
--+--
1 | 3
Em seguida, ele transforma o conjunto de registros de trabalho com consulta recursiva e obtém seu segundo estado:
F | n
--+--
3 | 2
Então terceiro estado:
F | n
--+--
6 | 1
No terceiro estado não há linha que segue
n>1 condição na seleção recursiva, então o conjunto de trabalho é saídas de loop. O conjunto de registros externo agora contém todas as linhas, retornadas pela seleção inicial e recursiva:
F | n
--+--
1 | 3
3 | 2
6 | 1
A seleção externa filtra todos os resultados intermediários do conjunto de registros externo, mostrando apenas o valor fatorial final que se torna o resultado geral da consulta:
F
--
6
E agora vamos considerar a tabela
forest(id,parent_id,name) :id | parent_id | name
---+-----------+-----------------
1 | | item 1
2 | 1 | subitem 1.1
3 | 1 | subitem 1.2
4 | 1 | subitem 1.3
5 | 3 | subsubitem 1.2.1
6 | | item 2
7 | 6 | subitem 2.1
8 | | item 3
'Expandindo árvore completa ' aqui significa classificar os itens da árvore em ordem de profundidade legível por humanos enquanto calcula seus níveis e (talvez) caminhos. Ambas as tarefas (de classificação correta e cálculo de nível ou caminho) não podem ser resolvidas em um (ou mesmo em qualquer número constante de) SELECT sem usar a cláusula WITH RECURSIVE (ou cláusula Oracle CONNECT BY, que não é suportada pelo PostgreSQL). Mas essa consulta recursiva faz o trabalho (bem, quase faz, veja a nota abaixo):
WITH RECURSIVE fulltree(id,parent_id,level,name,path) AS (
SELECT id, parent_id, 1 as level, name, name||'' as path from forest where parent_id is null
UNION ALL
SELECT t.id, t.parent_id, ft.level+1 as level, t.name, ft.path||' / '||t.name as path
from forest t, fulltree ft where t.parent_id = ft.id
)
SELECT * from fulltree order by path
O mecanismo de banco de dados executa assim:
Em primeiro lugar, ele executa initail select, que fornece todos os itens de nível mais alto (roots) de
forest tabela:id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
1 | | 1 | item 1 | item 1
8 | | 1 | item 3 | item 3
6 | | 1 | item 2 | item 2
Em seguida, ele executa a seleção recursiva, que fornece todos os itens de 2º nível de
forest tabela:id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
2 | 1 | 2 | subitem 1.1 | item 1 / subitem 1.1
3 | 1 | 2 | subitem 1.2 | item 1 / subitem 1.2
4 | 1 | 2 | subitem 1.3 | item 1 / subitem 1.3
7 | 6 | 2 | subitem 2.1 | item 2 / subitem 2.1
Em seguida, ele executa a seleção recursiva novamente, recuperando itens de nível 3d:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
5 | 3 | 3 | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
E agora ele executa a seleção recursiva novamente, tentando recuperar itens de 4º nível, mas não há nenhum deles, então o loop é encerrado.
O SELECT externo define a ordem correta das linhas legíveis por humanos, classificando na coluna do caminho:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
1 | | 1 | item 1 | item 1
2 | 1 | 2 | subitem 1.1 | item 1 / subitem 1.1
3 | 1 | 2 | subitem 1.2 | item 1 / subitem 1.2
5 | 3 | 3 | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
4 | 1 | 2 | subitem 1.3 | item 1 / subitem 1.3
6 | | 1 | item 2 | item 2
7 | 6 | 2 | subitem 2.1 | item 2 / subitem 2.1
8 | | 1 | item 3 | item 3
OBSERVAÇÃO :A ordem das linhas resultante permanecerá correta apenas enquanto não houver caracteres de pontuação precedência de intercalação
/ nos nomes dos itens. Se renomearmos Item 2 em Item 1 * , ele quebrará a ordem das linhas, ficando entre Item 1 e seus descendentes.A solução mais estável é usar o caractere de tabulação (
E'\t' ) como separador de caminho na consulta (que pode ser substituído por um separador de caminho mais legível posteriormente:na seleção externa, antes de exibir para humano ou etc). Os caminhos separados por tabulação manterão a ordem correta até que haja tabulações ou caracteres de controle nos nomes dos itens - que podem ser facilmente verificados e descartados sem perda de usabilidade. É muito simples modificar a última consulta para expandir qualquer subárvore arbitrária - você só precisa substituir a condição
parent_id is null com perent_id=1 (por exemplo). Observe que esta variante de consulta retornará todos os níveis e caminhos relativos a Item 1 . E agora sobre erros típicos . O erro típico mais notável específico para consultas recursivas é definir condições de parada erradas na seleção recursiva, o que resulta em loops infinitos.
Por exemplo, se omitirmos
where n>1 condição na amostra fatorial acima, a execução da seleção recursiva nunca dará um conjunto vazio (porque não temos condição de filtrar uma única linha) e o loop continuará infinitamente. Essa é a razão mais provável pela qual algumas de suas consultas travam (o outro motivo não específico, mas ainda possível, é uma seleção muito ineficaz, que é executada em um tempo finito, mas muito longo).
Não há muitas diretrizes específicas de consulta RECURSIVA mencionar, tanto quanto eu sei. Mas eu gostaria de sugerir (bastante óbvio) procedimento de construção de consulta recursiva passo a passo.
-
Compile e depure separadamente sua seleção inicial.
-
Envolva-o com scaffolding WITH RECURSIVE construct
e comece a construir e depurar seu select recursivo.
A construção de scuffold recomendada é assim:
WITH RECURSIVE rec( <Your column names> ) AS (
<Your ready and working initial SELECT>
UNION ALL
<Recursive SELECT that you are debugging now>
)
SELECT * from rec limit 1000
Essa seleção externa mais simples produzirá todo o conjunto de registros externo, que, como sabemos, contém todas as linhas de saída da seleção inicial e cada execução da seleção recursiva em um loop em sua ordem de saída original - assim como nos exemplos acima! O
limit 1000 parte evitará o travamento, substituindo-a por uma saída superdimensionada na qual você poderá ver o ponto de parada perdido. - Após depurar a seleção inicial e recursiva, crie e depure sua seleção externa.
E agora a última coisa a mencionar - a diferença de usar
union em vez de union all em with recursive cláusula. Ele introduz a restrição de exclusividade de linha que resulta em duas linhas extras em nosso pseudocódigo de execução:working-recordset = result of Initial-SELECT
discard duplicate rows from working-recordset /*union-specific*/
append working-recordset to empty outer-recordset
while( working-recordset is not empty ) begin
new working-recordset = result of Recursive-SELECT
taking previous working-recordset as pseudo-entity-name
discard duplicate rows and rows that have duplicates in outer-recordset
from working-recordset /*union-specific*/
append working-recordset to outer-recordset
end
overall-result = result of Outer-SELECT
taking outer-recordset as pseudo-entity-name
