Bagaimana cara saya mengurutkan hasil permintaan rekursif dengan cara seperti pohon diperluas?

Anggaplah Anda memiliki nodestabel seperti ini:

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

Ini mewakili struktur pohon seperti simpul standar dengan simpul akar di bagian atas dan beberapa simpul anak yang menggantung dari simpul akar atau simpul anak lainnya.

Mari kita sisipkan beberapa nilai contoh:

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

Sekarang saya ingin mengambil 10 node root pertama dan semua anak mereka hingga kedalaman 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;

Ini bekerja dengan baik dan memberi saya hasil berikut:

 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

Seperti yang mungkin Anda perhatikan, tidak ada ORDER BYklausa, jadi urutannya tidak ditentukan. Urutan yang Anda lihat di sini adalah dari node root ke node yang lebih dalam.

Bagaimana saya memesan hasilnya seperti yang akan muncul dalam tampilan pohon diperluas, seperti yang Anda lihat dari contoh gambar di bawah ini?

Saya pada dasarnya ingin node anak ditempatkan tepat setelah simpul orangtua yang sesuai. Jika dua atau lebih node anak memiliki simpul orangtua yang sama, saya ingin mereka diurutkan berdasarkan stempel waktu mereka. Berdasarkan contoh di atas, inilah urutan output yang diinginkan yang saya coba capai:

 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

Array yang mewakili jalur dari root ke daun harus mencapai urutan pengurutan yang diinginkan:

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;

Jika dua atau lebih node anak memiliki simpul orangtua yang sama, saya ingin mereka diurutkan berdasarkan stempel waktu mereka.

Alihkan jalur dengan satu ke arah root dan tata oleh kolom itu tambahan:

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;