Como classifico os resultados de uma consulta recursiva de maneira expandida, como uma árvore?

12

Vamos supor que você tenha nodestabelas como esta:

CREATE TABLE nodes
(
    node serial PRIMARY KEY,
    parent integer NULL REFERENCES nodes(node),
    ts timestamp NOT NULL DEFAULT now()
);

Representa uma estrutura de árvore semelhante a um nó com nós raiz no topo e vários nós filhos pendurados em nós raiz ou outros nós filhos.

Vamos inserir alguns valores de exemplo:

INSERT INTO nodes (parent)
VALUES (NULL), (NULL), (NULL), (NULL), (1), (1), (1), (1), (6), (1)
     , (6), (9), (6), (6), (3), (3), (3), (15);

Agora, quero recuperar os 10 primeiros nós raiz e todos os seus filhos até uma profundidade de 4:

WITH RECURSIVE node_rec AS
(
    (SELECT 1 AS depth, * FROM nodes WHERE parent IS NULL LIMIT 10)

    UNION ALL

    SELECT depth + 1, n.*
    FROM nodes AS n JOIN node_rec ON (n.parent = node_rec.node)
    WHERE depth < 4
)
SELECT * FROM node_rec;

Isso funciona muito bem e me dá o seguinte resultado:

 depth | node | parent 
-------+------+--------
     1 |  1   |
     1 |  2   |
     1 |  3   |
     1 |  4   |
     2 |  5   |  1
     2 |  6   |  1
     2 |  7   |  1
     2 |  8   |  1
     2 | 10   |  1
     2 | 15   |  3
     2 | 16   |  3
     2 | 17   |  3
     3 |  9   |  6
     3 | 11   |  6
     3 | 13   |  6
     3 | 14   |  6
     3 | 18   | 15
     4 | 12   |  9

Como você deve ter notado, não há ORDER BYcláusula, portanto a ordem não está definida. A ordem que você vê aqui é de nós raiz para nós mais profundos.

Como eu ordenaria os resultados como eles apareceriam em uma exibição em árvore expandida, como você pode ver na figura de exemplo abaixo?

Visualização em árvore expandida de nós

Eu basicamente quero que os nós filhos sejam colocados logo após o nó pai correspondente. Se dois ou mais nós filhos tiverem o mesmo nó pai, quero que eles sejam classificados pelo carimbo de data e hora. Com base no exemplo acima, aqui está a ordem de saída desejada que estou tentando atingir:

 depth | node | parent | ts
-------+------+--------+---------
     1 |  1   |        | 2014-01-01 00:00:00
     2 |  5   |     1  | 2014-01-01 00:10:00
     2 |  6   |     1  | 2014-01-01 00:20:00
     3 |  9   |     6  | 2014-01-01 00:25:00
     4 |  12  |     9  | 2014-01-01 00:27:00
     3 |  11  |     6  | 2014-01-01 00:26:00
     3 |  13  |     6  | 2014-01-01 00:30:00
     3 |  14  |     6  | 2014-01-01 00:36:00
     2 |  7   |     1  | 2014-01-01 00:21:00
     2 |  8   |     1  | 2014-01-01 00:22:00
     2 |  10  |     1  | 2014-01-01 00:23:00
     1 |  2   |        | 2014-01-01 00:08:00
     1 |  3   |        | 2014-01-01 00:09:00
     2 |  15  |     3  | 2014-01-01 10:00:00
     3 |  18  |     15 | 2014-01-01 11:05:00
     2 |  16  |     3  | 2014-01-01 11:00:00
     2 |  17  |     3  | 2014-01-01 12:00:00
     1 |  4   |        | 2014-01-01 00:10:00
JohnCand
fonte
Alguém pode me explicar de onde vem a depthcoluna? Eu não o vejo na estrutura da tabela inicial.
Sorin
@sorin, eu sei que esse é um post antigo, mas eu me deparei com ele no Google e pensei em responder à sua pergunta. A profundidade vem do alias do literal '1' na primeira consulta.
Sam

Respostas:

11

Uma matriz que representa o caminho da raiz até a folha deve atingir a ordem de classificação desejada:

WITH RECURSIVE node_rec AS (
   (SELECT 1 AS depth, ARRAY[node] AS path, *
    FROM   nodes
    WHERE  parent IS NULL
    LIMIT  10
   )    
    UNION ALL
    SELECT r.depth + 1, r.path || n.node, n.*
    FROM   node_rec r 
    JOIN   nodes    n ON n.parent = r.node
    WHERE  r.depth < 4
)
SELECT *
FROM   node_rec
ORDER  BY path;

Se dois ou mais nós filhos tiverem o mesmo nó pai, quero que eles sejam classificados pelo carimbo de data e hora.

Mude o caminho por um para a raiz e ordene por essa coluna adicionalmente:

WITH RECURSIVE node_rec AS (
   (SELECT 1 AS depth, ARRAY[node] AS path, *
    FROM   nodes
    WHERE  parent IS NULL
    LIMIT  10
   )    
    UNION ALL
    SELECT r.depth + 1, r.path || n.parent, n.*
    FROM   node_rec r 
    JOIN   nodes    n ON n.parent = r.node
    WHERE  r.depth < 4
)
SELECT *
FROM   node_rec
ORDER  BY path, ts;
Erwin Brandstetter
fonte
Obrigado, funciona muito bem! No entanto, o que dizer da parte "Se dois ou mais nós filhos tiverem o mesmo nó pai, desejo que eles sejam classificados pelo carimbo de data / hora"? Isso é possível com essa abordagem? Pode não ser sempre que um ID de nó mais alto corresponda a um período posterior.
JohnCand
@JohnCand: Você pode mudar o caminho de um para o root (repetir o nó raiz na primeira posição!) E fim por essa coluna, além disso ...
Erwin Brandstetter