Iterate through "linked list" in one SQL query?

Question

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 1

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).

Answer 2

You might found this blog post heplful.

Answer 3

I'd say you should create a user-defined function in this vein:

create function FindLastId (ID as integer) returns integer as $$ declare newid integer; declare primaryid integer; declare continue boolean; begin set continue = true; set primaryid = $1; while (continue) select into newid redirectid from table where id = :primaryid;

        if newid is null then
            set continue = false;
        else
            set primaryid = :newid;
        end if;
    end loop;

    return primaryid;
end;
$$ language pgplsql;

I'm a bit shaky on the Postgres syntax, so you may have some cleanup to do. Anyway, you can then call your function like so:

select id, FindLastId(id) as EndId from table

On a table like so:

id     redirectid    data
1          3          ab
2        null         cd
3          2          ef
4          1          gh
5        null         ij

This will return:

id    EndId
1       2
2       2
3       2
4       2
5       5

Note that this will be markedly slow, but it should get you the ID's pretty quickly for a small result set on a well indexed table.