Postgres 15

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
select version();


version


PostgreSQL 15.0 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 8.5.0 20210514 (Red Hat 8.5.0-10), 64-bit



SELECT 1


CREATE TABLE node (
    id TEXT PRIMARY KEY,
    is_skippable BOOL,
    prev TEXT REFERENCES node(id),
    "next" TEXT REFERENCES node(id)
);

CREATE TABLE


INSERT INTO node VALUES 
  ('A1', FALSE, NULL, 'A2'), 
  ('A2', TRUE, 'A1', 'A3'), 
  ('A3', FALSE, 'A2', NULL),
  ('B1', FALSE, NULL, 'B2'), 
  ('B2', FALSE, 'B1', NULL)
returning *;


id
is_skippable
prev
next


A1
f
null
A2

A2
t
A1
A3

A3
f
A2
null

B1
f
null
B2

B2
f
B1
null



INSERT 0 5


select id,(with recursive cte as( 
            select n2.id,n2.prev,n2.is_skippable
            from node n2
            where n2.id=n1.prev
            union
            select n2.id,n2.prev,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.prev
              and cte.is_skippable) CYCLE prev SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as prev
        ,(with recursive cte as( 
            select n2.id,n2.next,n2.is_skippable
            from node n2
            where n2.id=n1.next
            union
            select n2.id,n2.next,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.next
              and cte.is_skippable) CYCLE next SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as next
from node n1
where not is_skippable;


id
prev
next


A1
null
A3

A3
A1
null

B1
null
B2

B2
B1
null



SELECT 4


--https://stackoverflow.com/a/78444143/5298879
select id,coalesce(
         (with recursive cte as( 
            select 1 as i, n2.prev 
            from node n2
            where n2.id=n1.prev
            union
            select cte.i+1, n2.prev 
            from node n2 join cte 
              on n2.id=cte.prev
              and is_skippable) CYCLE prev SET is_cycle USING path
          select prev from cte order by i desc limit 1)
         ,prev) as prev
        ,coalesce(
         (with recursive cte as( 
            select 1 as i, n2.next 
            from node n2
            where n2.id=n1.next
              and n2.is_skippable
            union
            select cte.i+1, n2.next 
            from node n2 join cte 
              on n2.id=cte.next
              and is_skippable) CYCLE next SET is_cycle USING path
          select next from cte order by i desc limit 1)
          ,next) as next
from node n1
where not is_skippable;


id
prev
next


A1
null
A3

A3
A1
null

B1
null
B2

B2
B1
null



SELECT 4


--https://stackoverflow.com/a/78444165/5298879
WITH RECURSIVE cte (id, prev, next, count) AS
(
SELECT n.id, n.prev, n.next, 0
  FROM node AS n
 WHERE NOT is_skippable
UNION ALL
SELECT c.id, COALESCE (n_prev.prev, c.prev), COALESCE(n_next.next, c.next), c.count + 1 
  FROM cte AS c
  LEFT JOIN node AS n_prev
    ON n_prev.id = c.prev
  LEFT JOIN node AS n_next
    ON n_next.id = c.next
 WHERE (c.prev IS NOT NULL AND n_prev.is_skippable)
    OR (c.next IS NOT NULL AND n_next.is_skippable)
)
SELECT DISTINCT ON (id) id, prev, next
  FROM cte
 ORDER BY id, count DESC ;


id
prev
next


A1
null
A3

A3
A1
null

B1
null
B2

B2
B1
null



SELECT 4


select now(),setseed(.42);

insert into node
select --array_sample('{C,D,E,F,G,H,I,J}'::text[],1)||n
     'X'||n as id
    , .2>random()
    , case when .95>random() then 'X'||(1+random()*(1e4-1))::int end
    , case when .95>random() then 'X'||(1+random()*(1e4-1))::int end
from generate_series(1,1e4)n
on conflict do nothing;


now
setseed


2024-05-07 19:10:57.467445+01




SELECT 1



INSERT 0 10000


create index on node (id)include(is_skippable,prev,"next")with(fillfactor=100);

CREATE INDEX


vacuum analyze node;

VACUUM


--https://stackoverflow.com/a/78444143/5298879
explain analyze verbose
select id,(with recursive cte as( 
            select n2.id,n2.prev,n2.is_skippable
            from node n2
            where n2.id=n1.prev
            union
            select n2.id,n2.prev,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.prev
              and cte.is_skippable) CYCLE prev SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as prev
        ,(with recursive cte as( 
            select n2.id,n2.next,n2.is_skippable
            from node n2
            where n2.id=n1.next
            union
            select n2.id,n2.next,n2.is_skippable
            from node n2 join cte 
              on n2.id=cte.next
              and cte.is_skippable) CYCLE next SET is_cycle USING path
          select id from cte where not is_skippable limit 1) as next
from node n1
where not is_skippable;


QUERY PLAN


Seq Scan on public.node n1  (cost=0.00..1486771.12 rows=7982 width=69) (actual time=0.104..263.144 rows=7982 loops=1)

  Output: n1.id, (SubPlan 2), (SubPlan 4)

  Filter: (NOT n1.is_skippable)

  Rows Removed by Filter: 2023

  SubPlan 2

    ->  Limit  (cost=93.08..93.12 rows=1 width=32) (actual time=0.014..0.014 rows=1 loops=7982)

          Output: cte_1.id

          CTE cte

            ->  Recursive Union  (cost=0.29..93.08 rows=21 width=44) (actual time=0.009..0.012 rows=1 loops=7982)

                  ->  Index Only Scan using node_id_is_skippable_prev_next_idx on public.node n2  (cost=0.29..4.30 rows=1 width=44) (actual time=0.007..0.007 rows=1 loops=7982)

                        Output: n2.id, n2.prev, n2.is_skippable, false, ARRAY[ROW(n2.prev)]

                        Index Cond: (n2.id = n1.prev)

                        Heap Fetches: 0

                  ->  Nested Loop  (cost=0.29..8.84 rows=2 width=44) (actual time=0.008..0.008 rows=1 loops=2358)

                        Output: n2_1.id, n2_1.prev, n2_1.is_skippable, CASE WHEN (ROW(n2_1.prev) = ANY (cte.path)) THEN true ELSE false END, array_cat(cte.path, ARRAY[ROW(n2_1.prev)])

                        Inner Unique: true

                        ->  WorkTable Scan on cte  (cost=0.00..0.20 rows=2 width=64) (actual time=0.000..0.000 rows=1 loops=2358)

                              Output: cte.path, cte.prev

                              Filter: (cte.is_skippable AND (NOT cte.is_cycle))

                        ->  Index Only Scan using node_id_is_skippable_prev_next_idx on public.node n2_1  (cost=0.29..4.30 rows=1 width=11) (actual time=0.006..0.006 rows=1 loops=1912)

                              Output: n2_1.id, n2_1.is_skippable, n2_1.prev, n2_1.next

                              Index Cond: (n2_1.id = cte.prev)

                              Heap Fetches: 0

          ->  CTE Scan on cte cte_1  (cost=0.00..0.42 rows=10 width=32) (actual time=0.014..0.014 rows=1 loops=7982)

                Output: cte_1.id

                Filter: (NOT cte_1.is_skippable)

                Rows Removed by Filter: 0

  SubPlan 4

    ->  Limit  (cost=93.08..93.12 rows=1 width=32) (actual time=0.016..0.016 rows=1 loops=7982)

          Output: cte_3.id

          CTE cte

            ->  Recursive Union  (cost=0.29..93.08 rows=21 width=44) (actual time=0.010..0.014 rows=1 loops=7982)

                  ->  Index Only Scan using node_id_is_skippable_prev_next_idx on public.node n2_2  (cost=0.29..4.30 rows=1 width=44) (actual time=0.008..0.008 rows=1 loops=7982)

                        Output: n2_2.id, n2_2.next, n2_2.is_skippable, false, ARRAY[ROW(n2_2.next)]

                        Index Cond: (n2_2.id = n1.next)

                        Heap Fetches: 0

                  ->  Nested Loop  (cost=0.29..8.84 rows=2 width=44) (actual time=0.008..0.009 rows=1 loops=2313)

                        Output: n2_3.id, n2_3.next, n2_3.is_skippable, CASE WHEN (ROW(n2_3.next) = ANY (cte_2.path)) THEN true ELSE false END, array_cat(cte_2.path, ARRAY[ROW(n2_3.next)])

                        Inner Unique: true

                        ->  WorkTable Scan on cte cte_2  (cost=0.00..0.20 rows=2 width=64) (actual time=0.000..0.000 rows=1 loops=2313)

                              Output: cte_2.path, cte_2.next

                              Filter: (cte_2.is_skippable AND (NOT cte_2.is_cycle))

                        ->  Index Only Scan using node_id_is_skippable_prev_next_idx on public.node n2_3  (cost=0.29..4.30 rows=1 width=11) (actual time=0.006..0.006 rows=1 loops=1946)

                              Output: n2_3.id, n2_3.is_skippable, n2_3.prev, n2_3.next

                              Index Cond: (n2_3.id = cte_2.next)

                              Heap Fetches: 0

          ->  CTE Scan on cte cte_3  (cost=0.00..0.42 rows=10 width=32) (actual time=0.015..0.015 rows=1 loops=7982)

                Output: cte_3.id

                Filter: (NOT cte_3.is_skippable)

                Rows Removed by Filter: 0

Planning Time: 1.275 ms

Execution Time: 264.227 ms



EXPLAIN


--https://stackoverflow.com/a/78444143/5298879
explain analyze verbose
select id,coalesce(
         (with recursive cte as( 
            select 1 as i, n2.prev 
            from node n2
            where n2.id=n1.prev
            union
            select cte.i+1, n2.prev 
            from node n2 join cte 
              on n2.id=cte.prev
              and is_skippable) CYCLE prev SET is_cycle USING path
          select prev from cte order by i desc limit 1)
         ,prev) as prev
        ,coalesce(
         (with recursive cte as( 
            select 1 as i, n2.next 
            from node n2
            where n2.id=n1.next
              and n2.is_skippable
            union
            select cte.i+1, n2.next 
            from node n2 join cte 
              on n2.id=cte.next
              and is_skippable) CYCLE next SET is_cycle USING path
          select next from cte order by i desc limit 1)
          ,next) as next
from node n1
where not is_skippable;


QUERY PLAN


Seq Scan on public.node n1  (cost=0.00..3546401.20 rows=7982 width=69) (actual time=0.066..366.128 rows=7982 loops=1)

  Output: n1.id, COALESCE((SubPlan 2), n1.prev), COALESCE((SubPlan 4), n1.next)

  Filter: (NOT n1.is_skippable)

  Rows Removed by Filter: 2023

  SubPlan 2

    ->  Limit  (cost=222.14..222.14 rows=1 width=36) (actual time=0.027..0.027 rows=1 loops=7982)

          Output: cte_1.prev, cte_1.i

          CTE cte

            ->  Recursive Union  (cost=0.29..221.86 rows=11 width=42) (actual time=0.010..0.022 rows=1 loops=7982)

                  ->  Index Only Scan using node_id_is_skippable_prev_next_idx on public.node n2  (cost=0.29..4.30 rows=1 width=42) (actual time=0.007..0.008 rows=1 loops=7982)

                        Output: 1, n2.prev, false, ARRAY[ROW(n2.prev)]

                        Index Cond: (n2.id = n1.prev)

                        Heap Fetches: 0

                  ->  Nested Loop  (cost=0.29..21.73 rows=1 width=42) (actual time=0.009..0.009 rows=0 loops=9821)

                        Output: (cte.i + 1), n2_1.prev, CASE WHEN (ROW(n2_1.prev) = ANY (cte.path)) THEN true ELSE false END, array_cat(cte.path, ARRAY[ROW(n2_1.prev)])

                        Inner Unique: true

                        ->  WorkTable Scan on cte  (cost=0.00..0.20 rows=5 width=68) (actual time=0.000..0.000 rows=1 loops=9821)

                              Output: cte.i, cte.path, cte.prev

                              Filter: (NOT cte.is_cycle)

                        ->  Index Only Scan using node_id_is_skippable_prev_next_idx on public.node n2_1  (cost=0.29..4.30 rows=1 width=10) (actual time=0.007..0.007 rows=0 loops=9375)

                              Output: n2_1.id, n2_1.is_skippable, n2_1.prev, n2_1.next

                              Index Cond: (n2_1.id = cte.prev)

                              Filter: n2_1.is_skippable

                              Rows Removed by Filter: 1

                              Heap Fetches: 0

          ->  Sort  (cost=0.28..0.30 rows=11 width=36) (actual time=0.026..0.026 rows=1 loops=7982)

                Output: cte_1.prev, cte_1.i

                Sort Key: cte_1.i DESC

                Sort Method: quicksort  Memory: 25kB

                ->  CTE Scan on cte cte_1  (cost=0.00..0.22 rows=11 width=36) (actual time=0.011..0.023 rows=1 loops=7982)

                      Output: cte_1.prev, cte_1.i

  SubPlan 4

    ->  Limit  (cost=222.14..222.14 rows=1 width=36) (actual time=0.016..0.016 rows=0 loops=7982)

          Output: cte_3.next, cte_3.i

          CTE cte

            ->  Recursive Union  (cost=0.29..221.86 rows=11 width=42) (actual time=0.009..0.012 rows=0 loops=7982)

                  ->  Index Only Scan using node_id_is_skippable_prev_next_idx on public.node n2_2  (cost=0.29..4.30 rows=1 width=42) (actual time=0.007..0.007 rows=0 loops=7982)

                        Output: 1, n2_2.next, false, ARRAY[ROW(n2_2.next)]

                        Index Cond: (n2_2.id = n1.next)

                        Filter: n2_2.is_skippable

                        Rows Removed by Filter: 1

                        Heap Fetches: 0

                  ->  Nested Loop  (cost=0.29..21.73 rows=1 width=42) (actual time=0.002..0.002 rows=0 loops=8375)

                        Output: (cte_2.i + 1), n2_3.next, CASE WHEN (ROW(n2_3.next) = ANY (cte_2.path)) THEN true ELSE false END, array_cat(cte_2.path, ARRAY[ROW(n2_3.next)])

                        Inner Unique: true

                        ->  WorkTable Scan on cte cte_2  (cost=0.00..0.20 rows=5 width=68) (actual time=0.000..0.000 rows=0 loops=8375)

                              Output: cte_2.i, cte_2.path, cte_2.next

                              Filter: (NOT cte_2.is_cycle)

                        ->  Index Only Scan using node_id_is_skippable_prev_next_idx on public.node n2_3  (cost=0.29..4.30 rows=1 width=10) (actual time=0.007..0.007 rows=0 loops=1946)

                              Output: n2_3.id, n2_3.is_skippable, n2_3.prev, n2_3.next

                              Index Cond: (n2_3.id = cte_2.next)

                              Filter: n2_3.is_skippable

                              Rows Removed by Filter: 1

                              Heap Fetches: 0

          ->  Sort  (cost=0.28..0.30 rows=11 width=36) (actual time=0.015..0.015 rows=0 loops=7982)

                Output: cte_3.next, cte_3.i

                Sort Key: cte_3.i DESC

                Sort Method: top-N heapsort  Memory: 25kB

                ->  CTE Scan on cte cte_3  (cost=0.00..0.22 rows=11 width=36) (actual time=0.010..0.013 rows=0 loops=7982)

                      Output: cte_3.next, cte_3.i

Planning Time: 0.944 ms

Execution Time: 368.270 ms



EXPLAIN


----https://stackoverflow.com/a/78444165/5298879
--ERROR:  could not write to file "pg_tblspc/421963/PG_15_202209061/pgsql_tmp/pgsql_tmp211922.1": No space left on device
/*
explain analyze verbose
WITH RECURSIVE cte (id, prev, next, count) AS
(
SELECT n.id, n.prev, n.next, 0
  FROM node AS n
 WHERE NOT is_skippable
UNION ALL
SELECT c.id, COALESCE (n_prev.prev, c.prev), COALESCE(n_next.next, c.next), c.count + 1 
  FROM cte AS c
  LEFT JOIN node AS n_prev
    ON n_prev.id = c.prev
  LEFT JOIN node AS n_next
    ON n_next.id = c.next
 WHERE (c.prev IS NOT NULL AND n_prev.is_skippable)
    OR (c.next IS NOT NULL AND n_next.is_skippable)
)
SELECT DISTINCT ON (id) id, prev, next
  FROM cte
 ORDER BY id, count DESC ;
*/
id	is_skippable	prev	next
A1	f	null	A2
A2	t	A1	A3
A3	f	A2	null
B1	f	null	B2
B2	f	B1	null
id	prev	next
A1	null	A3
A3	A1	null
B1	null	B2
B2	B1	null
id	prev	next
A1	null	A3
A3	A1	null
B1	null	B2
B2	B1	null
id	prev	next
A1	null	A3
A3	A1	null
B1	null	B2
B2	B1	null