Niki Yoshiuchi Niki Yoshiuchi - 14 days ago 5
SQL Question

Iterate through "linked list" in one SQL query?

I have a table that looks basically like this:

id | redirectid | data


where the redirectid is an id to another row. Basically if a row is selected, and it has a redirectid, then the redirectid data should be used in it's place. There may be multiple redirects until redirectid is NULL. Essentially these redirects form a linked list in the table. What I'd like to know is, given an id, is it possible to set up a sql query that will iterate through all the possible redirects and return the id at the end of the "list"?

This is using Postgresql 8.3 and I'd like to do everything in on sql query if possible (rather than iterate in my code).

Answer

Does postgresql support recursive queries that use WITH clauses? If so, something like this might work. (If you want a tested answer, provide some CREATE TABLE and INSERT statements in your question, along with the results you need for the sample data in the INSERTs.)

with Links(id,link,data) as (
  select
    id, redirectid, data
  from T
  where redirectid is null
  union all
  select
    id, redirectid, null
  from T
  where redirectid is not null
  union all
  select
    Links.id,
    T.redirectid,
    case when T.redirectid is null then T.data else null end
  from T
  join Links
  on Links.link = T.id
)
  select id, data
  from Links
  where data is not null;

Additional remarks:

:( You can implement the recursion yourself based on the WITH expression. I don't know postgresql syntax for sequential programming, so this is a bit pseudo:

Insert the result of this query into a new table called Links:

select
    id, redirectid as link, data, 0 as depth
  from T
  where redirectid is null
  union all
  select
    id, redirectid, null, 0
  from T
  where redirectid is not null

Also declare an integer ::depth and initialize it to zero. Then repeat the following until it no longer adds rows to Links. Links will then contain your result.

  increment ::depth;
  insert into Links
  select
    Links.id,
    T.redirectid,
    case when T.redirectid is null then T.data else null end,
    depth + 1
  from T join Links
  on Links.link = T.id
  where depth = ::depth-1;
end;

I think this will be better than any cursor solution. In fact, I can't really think of how cursors would be useful for this problem at all.

Note that this will not terminate if there are any cycles (redirects that are ultimately circular).