Jak posortować wyniki zapytania rekurencyjnego w sposób podobny do rozwiniętego drzewa?

Załóżmy, że masz takie nodestabele:

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

Reprezentuje standardową strukturę drzewiastą z węzłami głównymi u góry i kilkoma węzłami potomnymi zwisającymi z węzłów głównych lub innych węzłów potomnych.

Dodajmy kilka przykładowych wartości:

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

Teraz chcę pobrać pierwsze 10 węzłów głównych i wszystkie ich dzieci do głębokości 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;

Działa to świetnie i daje mi następujący wynik:

 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

Jak można zauważyć, nie ma ORDER BYklauzuli, więc kolejność nie jest zdefiniowana. Kolejność, którą tutaj widzisz, jest następująca: od węzłów głównych do głębszych.

Jak mam uporządkować wyniki tak, jak by były wyświetlane w rozwiniętym widoku drzewa, jak widać na poniższym obrazku przykładowym?

Zasadniczo chcę, aby węzły potomne były umieszczone zaraz za odpowiadającym im węzłem macierzystym. Jeśli dwa lub więcej węzłów podrzędnych ma ten sam węzeł nadrzędny, chcę, aby były posortowane według datownika. Na podstawie powyższego przykładu, oto pożądana kolejność wyjściowa, którą próbuję osiągnąć:

 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

Tablica reprezentująca ścieżkę od korzenia do liścia powinna osiągnąć pożądaną kolejność sortowania:

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;

Jeśli dwa lub więcej węzłów podrzędnych ma ten sam węzeł nadrzędny, chcę, aby były posortowane według datownika.

Przesuń ścieżkę o jeden w kierunku katalogu głównego i uporządkuj dodatkowo według tej kolumny:

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;