16

Let's assume you have a nodes tables like this:

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

It represents a standard node-like tree structure with root nodes at the top and several child nodes dangling from root nodes or other child nodes.

Let us insert a couple of example values:

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

Now I want to retrieve the first 10 root nodes and all their children up to a depth of 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;

This works great and gives me the following result:

 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

As you might have noticed, there's no ORDER BY clause, so the order is not defined. The order you see here is from root nodes to deeper nodes.

How would I order the results as they would appear in an expanded tree view, as you can see from the example picture below?

Expanded tree view of nodes

I basically want the child nodes to be placed right after their corresponding parent node. If two or more child nodes have the same parent node, I want them to be sorted by their timestamp. Based on the example above, here's the desired output order that I'm trying to achieve:

 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
0

1 Answer 1

16

You can order by the array representing the path from the root up to the leaf:

To keep it simple I left out LIMIT (so we also don't need extra parentheses) and WHERE of your original query. Those can be added freely.

Basic query

WITH RECURSIVE node_rec AS (
   SELECT 1 AS depth, *
        , ARRAY[node] AS path
   FROM   nodes
   WHERE  parent IS NULL

   UNION ALL
   SELECT r.depth + 1, n.*
        , r.path || n.node
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   )
SELECT *
FROM   node_rec
ORDER  BY path;

The same can be simplified with the dedicated SEARCH clause in Postgres 14 or later:

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

   UNION ALL
   SELECT r.depth + 1, n.*
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   ) SEARCH DEPTH FIRST BY node SET path
SELECT *
FROM   node_rec
ORDER  BY path, ts;

Order by additional column

If two or more child nodes have the same parent node, I want them to be sorted by their timestamp.

We really need to sort by the timestamp column ts first on each level, and node is just a tiebreaker (the timestamp may not be unique). The simplest solution is to take both as record type:

WITH RECURSIVE node_rec AS (
   SELECT 1 AS depth, *
         , ARRAY[(ts, node)] AS path
   FROM   nodes
   WHERE  parent IS NULL

   UNION ALL
   SELECT r.depth + 1, n.*
        , r.path || (n.ts, n.node)
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   )
SELECT *
FROM   node_rec
ORDER  BY path;

Equivalent, simpler query with the SEARCH clause in Postgres 14 or later:

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

   UNION ALL
   SELECT r.depth + 1, n.*
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   ) SEARCH DEPTH FIRST BY ts, node SET path
SELECT *
FROM   node_rec
ORDER  BY path, ts;

AS you can see, the new syntax allows to specify multiple columns for the sort.

db<>fiddle here

6
  • 1
    Thank you, it works great! However, what about the "If two or more child nodes have the same parent node, I want them to be sorted by their timestamp" part? Is this doable with this approach? It might not always be the case that a higher node ID corresponds to a later time.
    – JohnCand
    Apr 14, 2014 at 14:27
  • 1
    @JohnCand: You can shift the path by one towards the root (repeat the root node in first position!) and order by that column additionally ... Apr 14, 2014 at 15:11
  • 1
    @ErwinBrandstetter I came across this post whilst seeking a solution for time ordered nested comments. I notice Postgres has “SEARCH DEPTH FIRST BY id SET ordercol” which appears to be a new syntax feature added since this answer. Would you be able to add an example using this new syntax? Feb 8 at 16:36
  • 1
    @Andy: I added new syntax for Postgres 14. While being at it, I also fixed the buggy 2nd query. Feb 9 at 5:08
  • 1
    @AndyFusniak: I haven't worked with KSUIDs, yet. Sounds like a smart approach. From a storage perspective char(27) seems like a poor choice to store 20 bytes of information, though. Related: dba.stackexchange.com/a/115316/3684, dba.stackexchange.com/a/256817/3684 Feb 9 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.