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

12

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?

Tampilan simpul pohon yang diperluas

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
JohnCand
sumber
Adakah yang bisa menjelaskan kepada saya di mana depthkolom itu berasal? Saya tidak melihatnya di struktur tabel awal.
Sorin
@sorin, saya tahu ini adalah posting yang benar-benar tua, tetapi saya baru saja menemukannya di Google dan berpikir saya akan menjawab pertanyaan Anda. Kedalamannya berasal dari alias literal '1' di kueri pertama.
Sam

Jawaban:

11

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;
Erwin Brandstetter
sumber
Terima kasih, ini bekerja dengan baik! Namun, bagaimana dengan bagian "Jika dua atau lebih node anak memiliki simpul orangtua yang sama, saya ingin mereka diurutkan berdasarkan cap waktu mereka"? Apakah ini bisa dilakukan dengan pendekatan ini? Ini mungkin tidak selalu menjadi kasus bahwa ID node yang lebih tinggi sesuai dengan waktu kemudian.
JohnCand
@ JohnCand: Anda dapat menggeser jalur dengan satu menuju root (ulangi simpul root di posisi pertama!) Dan memesan dengan kolom itu tambahan ...
Erwin Brandstetter