Skip to main content
Database Administrators

Return to Answer

focus
Source Link
Erwin Brandstetter
Erwin Brandstetter
  • 182.1k
  • 28
  • 457
  • 620

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
   LIMIT  10
   )    
   UNION ALL
   SELECT r.depth + 1, n.*
        , r.path || n.node
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY path;

WITH RECURSIVE node_rec AS (
   (
SELECT 1 AS SELECTdepth, *
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   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;

AdditionalOrder by additional column as tiebreaker

-- sort by path, peers on the same level by timestamp
WITH RECURSIVE node_rec AS (
   (
   SELECT 1 AS depth, *
         , ARRAY[(ts, node)] AS path
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   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
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY path;

WITH RECURSIVE node_rec AS (
   (
   SELECT 1 AS depth, *
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   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;

db<>fiddle herehere

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, n.*
        , r.path || n.node
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY path;

WITH RECURSIVE node_rec AS (
   (
   SELECT *
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   UNION ALL
   SELECT 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;

Additional column as tiebreaker

-- sort by path, peers on the same level by timestamp
WITH RECURSIVE node_rec AS (
   (
   SELECT 1 AS depth, *
        , ARRAY[(ts, node)] AS path
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   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
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY path;

WITH RECURSIVE node_rec AS (
   (
   SELECT 1 AS depth, *
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   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;

db<>fiddle here

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;

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

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;

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;

db<>fiddle here

denoise
Source Link
Erwin Brandstetter
Erwin Brandstetter
  • 182.1k
  • 28
  • 457
  • 620
-- sort by path, peers on the same level by timestamp
WITH RECURSIVE node_rec AS (
   (
   SELECT 1 AS depth, *
        , ARRAY[(ts, node)] AS sort_pathpath
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   UNION ALL
   SELECT r.depth + 1, n.*
        , r.sort_pathpath || (n.ts, n.node)
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY sort_path;path;

db<>fiddle herehere

-- sort by path, peers on the same level by timestamp
WITH RECURSIVE node_rec AS (
   (
   SELECT 1 AS depth, *
        , ARRAY[(ts, node)] AS sort_path
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   UNION ALL
   SELECT r.depth + 1, n.*
        , r.sort_path || (n.ts, n.node)
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY sort_path;

db<>fiddle here

-- sort by path, peers on the same level by timestamp
WITH RECURSIVE node_rec AS (
   (
   SELECT 1 AS depth, *
        , ARRAY[(ts, node)] AS path
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   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
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY path;

db<>fiddle here

fix bug in second query; add new syntax for pg 14 per question from Andy; add fiddle
Source Link
Erwin Brandstetter
Erwin Brandstetter
  • 182.1k
  • 28
  • 457
  • 620

AnYou can order by the array representing the path from the root up to the leaf should achieve:

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, n.*
        , r.path || n.node
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY path;

The same can be simplified with the desired sort orderdedicated SEARCH clause in Postgres 14 or later:

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;

WITH RECURSIVE node_rec AS (
   (
   SELECT *
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   UNION ALL
   SELECT 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;

Additional column as tiebreaker

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

Shift the pathWe really need to sort by one towards the root and order by thattimestamp column additionallyts 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[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;
-- sort by path, peers on the same level by timestamp
WITH RECURSIVE node_rec AS (
   (
   SELECT 1 AS depth, *
        , ARRAY[(ts, node)] AS sort_path
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   UNION ALL
   SELECT r.depth + 1, n.*
        , r.sort_path || (n.ts, n.node)
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY sort_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
   LIMIT  10
   )    
   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

An array representing the path from the root up to the leaf should achieve the desired sort order:

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;

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

Shift the path by one towards the root and order by that column additionally:

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;

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

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, n.*
        , r.path || n.node
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   WHERE  r.depth < 4
   )
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 *
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   UNION ALL
   SELECT 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;

Additional column as tiebreaker

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:

-- sort by path, peers on the same level by timestamp
WITH RECURSIVE node_rec AS (
   (
   SELECT 1 AS depth, *
        , ARRAY[(ts, node)] AS sort_path
   FROM   nodes
   WHERE  parent IS NULL
   LIMIT  10
   )    
   UNION ALL
   SELECT r.depth + 1, n.*
        , r.sort_path || (n.ts, n.node)
   FROM   node_rec r 
   JOIN   nodes    n ON n.parent = r.node
   WHERE  r.depth < 4
   )
SELECT *
FROM   node_rec
ORDER  BY sort_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
   LIMIT  10
   )    
   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

add solution
Source Link
Erwin Brandstetter
Erwin Brandstetter
  • 182.1k
  • 28
  • 457
  • 620
clean up
Source Link
Erwin Brandstetter
Erwin Brandstetter
  • 182.1k
  • 28
  • 457
  • 620
Source Link
Erwin Brandstetter
Erwin Brandstetter
  • 182.1k
  • 28
  • 457
  • 620