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.
You could probably collapse it to run in a lateral query in both directions at once, but the fact that this only tries to skip to the nearest non-skippable element might actually be an advantage, making the recursive part more lightweight. Demo at db<>fiddle:
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 |
It doesn't mind if the lists branch out. You can tighten the recursive cte join conditions to check for bi-directionality of the link to make it strictly follow the bi-directional path:
from node n2 join cte
on n2.id = cte.next
and n2.prev=cte.id --add this for strict
branches start with a uni-directional link, so this will filter them out.
It doesn't mind cycles/rings/loops, if you happen to have any, thanks to built-in cycle detection.
A covering index speeds things up:
create index on node (id)
include(is_skippable,prev,"next")
with(fillfactor=100);
You might be interested in pgrouting and Apache AGE.