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

12

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?

Rozszerzony widok drzewa węzłów

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
JohnCand
źródło
Czy ktoś może mi wyjaśnić, depthskąd pochodzi kolumna? Nie widzę tego w początkowej strukturze tabeli.
sorin,
@sorin, wiem, że to naprawdę stary post, ale natknąłem się na niego w Google i pomyślałem, że odpowiem na twoje pytanie. Głębokość pochodzi od aliasu dosłownego „1” w pierwszym zapytaniu.
Sam

Odpowiedzi:

11

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;
Erwin Brandstetter
źródło
Dziękuję, działa świetnie! A co z częścią „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 znacznika czasu”? Czy jest to wykonalne przy takim podejściu? Nie zawsze może być tak, że wyższy identyfikator węzła odpowiada późniejszemu czasowi.
JohnCand
@JohnCand: Możesz przesunąć ścieżkę o jeden w kierunku katalogu głównego (powtórz węzeł główny w pierwszej pozycji!) I dodatkowo uporządkuj według tej kolumny ...
Erwin Brandstetter