CODEWITHSUNDEEP
sqlpostgresql
Kyle Decot
Kyle Decot

Reputation: 20825

Get Row's Sequence (Linked-List) in PostgreSQL

I have a submissions table which is essentially a single linked list. Given the id of a given row I want to return the entire list that particular row is a part of (and it be in the proper order). For example in the table below if had id 2 I would want to get back rows 1,2,3,4 in that order.

(4,3) -> (3,2) -> (2,1) -> (1,null)

I expect 1,2,3,4 here because 4 is essentially the head of the list that 2 belongs to and I want to traverse all the through the list.

http://sqlfiddle.com/#!15/c352e/1

enter image description here

Is there a way to do this using postgresql's RECURSIVE CTE? So far I have the following but this will only give me the parents and not the descendants

WITH RECURSIVE "sequence" AS (
  SELECT * FROM submissions WHERE "submissions"."id" = 2
  UNION ALL SELECT "recursive".* FROM "submissions" "recursive"
    INNER JOIN "sequence" ON "recursive"."id" = "sequence"."link_id"
)

SELECT "sequence"."id" FROM "sequence"

Upvotes: 3

Views: 2608

Answers (2)

cachique
cachique

Reputation: 1271

This approach uses what you have already come up with.
It adds another block to calculate the rest of the list and then combines both doing a custom reverse ordering. 

WITH RECURSIVE pathtobottom AS (
-- Get the path from element to bottom list following next element id that matches current link_id
  SELECT 1 i, -- add fake order column to reverse retrieved records
  * FROM submissions WHERE submissions.id = 2
  UNION ALL
  SELECT pathtobottom.i + 1 i, -- add fake order column to reverse retrieved records
  recursive.* FROM submissions recursive
    INNER JOIN pathtobottom ON recursive.id = pathtobottom.link_id
)
,  pathtotop AS (
-- Get the path from element to top list following previous element link_id that matches current id
  SELECT 1 i, -- add fake order column to reverse retrieved records
  * FROM submissions WHERE submissions.id = 2
  UNION ALL
  SELECT pathtotop.i + 1 i, -- add fake order column to reverse retrieved records
  recursive2.* FROM submissions recursive2
    INNER JOIN pathtotop ON recursive2.link_id = pathtotop.id
), pathtotoprev as (
-- Reverse path to top using fake 'i' column
  SELECT pathtotop.id FROM pathtotop order by i desc
), pathtobottomrev as (
-- Reverse path to bottom using fake 'i' column
  SELECT pathtobottom.id FROM pathtobottom order by i desc
)
-- Elements ordered from bottom to top
SELECT pathtobottomrev.id FROM pathtobottomrev where id != 2 -- remove element to avoid duplicate
UNION ALL
SELECT pathtotop.id FROM pathtotop;
/*
-- Elements ordered from top to bottom
SELECT pathtotoprev.id FROM pathtotoprev
UNION ALL
SELECT pathtobottom.id FROM pathtobottom where id != 2; -- remove element to avoid duplicate
*/

Upvotes: 1

Abelisto
Abelisto

Reputation: 15624

In was yet another quest for my brain. Thanks.

with recursive r as (
  select *, array[id] as lst from submissions s where id = 6
  union all 
  select s.*, r.lst || s.id 
  from 
    submissions s inner join 
      r on (s.link_id=r.id or s.id=r.link_id)
    where (not array[s.id] <@ r.lst)
)
select * from r;

Upvotes: 0

Related Questions