Postgresql - Skip certain types of nodes in DLL

BenH
May 7, 2024
150 views
0 votes
2 Answers

I’m on Postgres 15.1 and have a node table as follows:

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

This table represents a series of doubly linked lists, but on certain occasions for certain queries, I want to remove is_skippable nodes from the list and link around them.

For example, if I had the following data seeded in the DB, where there’s one linked list of A1 <-> A2 <-> A3 (with A2 skippable) and one of B1 <-> B2:

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

For certain queries I want to link around is_skippable nodes. So if I queried this full table, the result set I’m looking for is:

id	prev	next
A1	NULL	A3
A3	A1	NULL
B1	NULL	B2
B2	B1	NULL

Note that A2 isn’t in the result set and A2‘s pointers have been rewritten to the node before and after it.

Is there a well-supported way to do this in Postgres? I’ve seen answers for simple linked lists elsewhere on StackOverflow (like Linked list concept in postgresql), but they don’t entail having to rewrite pointers. Thanks!

Sample Fiddle here: https://dbfiddle.uk/4lB4TAtF.

Tags: postgresql postgresql-15

Answers

You could probably collapse it to run in a lateral query in both directions at once, but here’s an example: demo at db<>fiddle

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

here is a solution using a recursive cte :

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 ;

demo in dbfiddle

Please signup or login to give your own answer.

Click here to cancel reply.

Postgresql – Skip certain types of nodes in DLL

Answers