Postgres 14

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.

Help with an interesting Postgres question: Why isn't an Index Only Scan used on a partition accessed via the parent table?.

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

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

UPDATE nodes
SET    ts = ts + interval '1s' * node;  -- make timestamps ascending

CREATE TABLE



INSERT 0 18



UPDATE 18


TABLE nodes;


node
parent
ts


1
null
2024-02-09 13:07:18.446725

2
null
2024-02-09 13:07:19.446725

3
null
2024-02-09 13:07:20.446725

4
null
2024-02-09 13:07:21.446725

5
1
2024-02-09 13:07:22.446725

6
1
2024-02-09 13:07:23.446725

7
1
2024-02-09 13:07:24.446725

8
1
2024-02-09 13:07:25.446725

9
6
2024-02-09 13:07:26.446725

10
1
2024-02-09 13:07:27.446725

11
6
2024-02-09 13:07:28.446725

12
9
2024-02-09 13:07:29.446725

13
6
2024-02-09 13:07:30.446725

14
6
2024-02-09 13:07:31.446725

15
3
2024-02-09 13:07:32.446725

16
3
2024-02-09 13:07:33.446725

17
3
2024-02-09 13:07:34.446725

18
15
2024-02-09 13:07:35.446725



SELECT 18


-- simply order by path (incomplete solution)
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;


depth
node
parent
ts
path


1
1
null
2024-02-09 13:07:18.446725
{1}

2
5
1
2024-02-09 13:07:22.446725
{1,5}

2
6
1
2024-02-09 13:07:23.446725
{1,6}

3
9
6
2024-02-09 13:07:26.446725
{1,6,9}

4
12
9
2024-02-09 13:07:29.446725
{1,6,9,12}

3
11
6
2024-02-09 13:07:28.446725
{1,6,11}

3
13
6
2024-02-09 13:07:30.446725
{1,6,13}

3
14
6
2024-02-09 13:07:31.446725
{1,6,14}

2
7
1
2024-02-09 13:07:24.446725
{1,7}

2
8
1
2024-02-09 13:07:25.446725
{1,8}

2
10
1
2024-02-09 13:07:27.446725
{1,10}

1
2
null
2024-02-09 13:07:19.446725
{2}

1
3
null
2024-02-09 13:07:20.446725
{3}

2
15
3
2024-02-09 13:07:32.446725
{3,15}

3
18
15
2024-02-09 13:07:35.446725
{3,15,18}

2
16
3
2024-02-09 13:07:33.446725
{3,16}

2
17
3
2024-02-09 13:07:34.446725
{3,17}

1
4
null
2024-02-09 13:07:21.446725
{4}



SELECT 18


-- Same with SEARCH keyword in Postgres 14+
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;


depth
node
parent
ts
path


1
1
null
2024-02-09 13:07:18.446725
{(1)}

2
5
1
2024-02-09 13:07:22.446725
{(1),(5)}

2
6
1
2024-02-09 13:07:23.446725
{(1),(6)}

3
9
6
2024-02-09 13:07:26.446725
{(1),(6),(9)}

4
12
9
2024-02-09 13:07:29.446725
{(1),(6),(9),(12)}

3
11
6
2024-02-09 13:07:28.446725
{(1),(6),(11)}

3
13
6
2024-02-09 13:07:30.446725
{(1),(6),(13)}

3
14
6
2024-02-09 13:07:31.446725
{(1),(6),(14)}

2
7
1
2024-02-09 13:07:24.446725
{(1),(7)}

2
8
1
2024-02-09 13:07:25.446725
{(1),(8)}

2
10
1
2024-02-09 13:07:27.446725
{(1),(10)}

1
2
null
2024-02-09 13:07:19.446725
{(2)}

1
3
null
2024-02-09 13:07:20.446725
{(3)}

2
15
3
2024-02-09 13:07:32.446725
{(3),(15)}

3
18
15
2024-02-09 13:07:35.446725
{(3),(15),(18)}

2
16
3
2024-02-09 13:07:33.446725
{(3),(16)}

2
17
3
2024-02-09 13:07:34.446725
{(3),(17)}

1
4
null
2024-02-09 13:07:21.446725
{(4)}



SELECT 18


-- 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

   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;


depth
node
parent
ts
path


1
1
null
2024-02-09 13:07:18.446725
{"("2024-02-09 13:07:18.446725",1)"}

2
5
1
2024-02-09 13:07:22.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:22.446725",5)"}

2
6
1
2024-02-09 13:07:23.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)"}

3
9
6
2024-02-09 13:07:26.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:26.446725",9)"}

4
12
9
2024-02-09 13:07:29.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:26.446725",9)","("2024-02-09 13:07:29.446725",12)"}

3
11
6
2024-02-09 13:07:28.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:28.446725",11)"}

3
13
6
2024-02-09 13:07:30.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:30.446725",13)"}

3
14
6
2024-02-09 13:07:31.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:31.446725",14)"}

2
7
1
2024-02-09 13:07:24.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:24.446725",7)"}

2
8
1
2024-02-09 13:07:25.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:25.446725",8)"}

2
10
1
2024-02-09 13:07:27.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:27.446725",10)"}

1
2
null
2024-02-09 13:07:19.446725
{"("2024-02-09 13:07:19.446725",2)"}

1
3
null
2024-02-09 13:07:20.446725
{"("2024-02-09 13:07:20.446725",3)"}

2
15
3
2024-02-09 13:07:32.446725
{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:32.446725",15)"}

3
18
15
2024-02-09 13:07:35.446725
{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:32.446725",15)","("2024-02-09 13:07:35.446725",18)"}

2
16
3
2024-02-09 13:07:33.446725
{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:33.446725",16)"}

2
17
3
2024-02-09 13:07:34.446725
{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:34.446725",17)"}

1
4
null
2024-02-09 13:07:21.446725
{"("2024-02-09 13:07:21.446725",4)"}



SELECT 18


-- Same with SEARCH keyword in Postgres 14+
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;


depth
node
parent
ts
path


1
1
null
2024-02-09 13:07:18.446725
{"("2024-02-09 13:07:18.446725",1)"}

2
5
1
2024-02-09 13:07:22.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:22.446725",5)"}

2
6
1
2024-02-09 13:07:23.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)"}

3
9
6
2024-02-09 13:07:26.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:26.446725",9)"}

4
12
9
2024-02-09 13:07:29.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:26.446725",9)","("2024-02-09 13:07:29.446725",12)"}

3
11
6
2024-02-09 13:07:28.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:28.446725",11)"}

3
13
6
2024-02-09 13:07:30.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:30.446725",13)"}

3
14
6
2024-02-09 13:07:31.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:31.446725",14)"}

2
7
1
2024-02-09 13:07:24.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:24.446725",7)"}

2
8
1
2024-02-09 13:07:25.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:25.446725",8)"}

2
10
1
2024-02-09 13:07:27.446725
{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:27.446725",10)"}

1
2
null
2024-02-09 13:07:19.446725
{"("2024-02-09 13:07:19.446725",2)"}

1
3
null
2024-02-09 13:07:20.446725
{"("2024-02-09 13:07:20.446725",3)"}

2
15
3
2024-02-09 13:07:32.446725
{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:32.446725",15)"}

3
18
15
2024-02-09 13:07:35.446725
{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:32.446725",15)","("2024-02-09 13:07:35.446725",18)"}

2
16
3
2024-02-09 13:07:33.446725
{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:33.446725",16)"}

2
17
3
2024-02-09 13:07:34.446725
{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:34.446725",17)"}

1
4
null
2024-02-09 13:07:21.446725
{"("2024-02-09 13:07:21.446725",4)"}



SELECT 18

node	parent	ts
1	null	2024-02-09 13:07:18.446725
2	null	2024-02-09 13:07:19.446725
3	null	2024-02-09 13:07:20.446725
4	null	2024-02-09 13:07:21.446725
5	1	2024-02-09 13:07:22.446725
6	1	2024-02-09 13:07:23.446725
7	1	2024-02-09 13:07:24.446725
8	1	2024-02-09 13:07:25.446725
9	6	2024-02-09 13:07:26.446725
10	1	2024-02-09 13:07:27.446725
11	6	2024-02-09 13:07:28.446725
12	9	2024-02-09 13:07:29.446725
13	6	2024-02-09 13:07:30.446725
14	6	2024-02-09 13:07:31.446725
15	3	2024-02-09 13:07:32.446725
16	3	2024-02-09 13:07:33.446725
17	3	2024-02-09 13:07:34.446725
18	15	2024-02-09 13:07:35.446725

depth	node	parent	ts	path
1	1	null	2024-02-09 13:07:18.446725	{(1)}
2	5	1	2024-02-09 13:07:22.446725	{(1),(5)}
2	6	1	2024-02-09 13:07:23.446725	{(1),(6)}
3	9	6	2024-02-09 13:07:26.446725	{(1),(6),(9)}
4	12	9	2024-02-09 13:07:29.446725	{(1),(6),(9),(12)}
3	11	6	2024-02-09 13:07:28.446725	{(1),(6),(11)}
3	13	6	2024-02-09 13:07:30.446725	{(1),(6),(13)}
3	14	6	2024-02-09 13:07:31.446725	{(1),(6),(14)}
2	7	1	2024-02-09 13:07:24.446725	{(1),(7)}
2	8	1	2024-02-09 13:07:25.446725	{(1),(8)}
2	10	1	2024-02-09 13:07:27.446725	{(1),(10)}
1	2	null	2024-02-09 13:07:19.446725	{(2)}
1	3	null	2024-02-09 13:07:20.446725	{(3)}
2	15	3	2024-02-09 13:07:32.446725	{(3),(15)}
3	18	15	2024-02-09 13:07:35.446725	{(3),(15),(18)}
2	16	3	2024-02-09 13:07:33.446725	{(3),(16)}
2	17	3	2024-02-09 13:07:34.446725	{(3),(17)}
1	4	null	2024-02-09 13:07:21.446725	{(4)}

depth	node	parent	ts	path
1	1	null	2024-02-09 13:07:18.446725	{"("2024-02-09 13:07:18.446725",1)"}
2	5	1	2024-02-09 13:07:22.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:22.446725",5)"}
2	6	1	2024-02-09 13:07:23.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)"}
3	9	6	2024-02-09 13:07:26.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:26.446725",9)"}
4	12	9	2024-02-09 13:07:29.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:26.446725",9)","("2024-02-09 13:07:29.446725",12)"}
3	11	6	2024-02-09 13:07:28.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:28.446725",11)"}
3	13	6	2024-02-09 13:07:30.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:30.446725",13)"}
3	14	6	2024-02-09 13:07:31.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:23.446725",6)","("2024-02-09 13:07:31.446725",14)"}
2	7	1	2024-02-09 13:07:24.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:24.446725",7)"}
2	8	1	2024-02-09 13:07:25.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:25.446725",8)"}
2	10	1	2024-02-09 13:07:27.446725	{"("2024-02-09 13:07:18.446725",1)","("2024-02-09 13:07:27.446725",10)"}
1	2	null	2024-02-09 13:07:19.446725	{"("2024-02-09 13:07:19.446725",2)"}
1	3	null	2024-02-09 13:07:20.446725	{"("2024-02-09 13:07:20.446725",3)"}
2	15	3	2024-02-09 13:07:32.446725	{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:32.446725",15)"}
3	18	15	2024-02-09 13:07:35.446725	{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:32.446725",15)","("2024-02-09 13:07:35.446725",18)"}
2	16	3	2024-02-09 13:07:33.446725	{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:33.446725",16)"}
2	17	3	2024-02-09 13:07:34.446725	{"("2024-02-09 13:07:20.446725",3)","("2024-02-09 13:07:34.446725",17)"}
1	4	null	2024-02-09 13:07:21.446725	{"("2024-02-09 13:07:21.446725",4)"}