3

I have a, perhaps slightly esoteric, use case.

Given a table like the following:

 id1 | id2 |      timestamp      
-----+-----+---------------------
   3 |   4 | 2016-03-22 09:52:15
   1 |   2 | 2016-03-22 12:05:28
   2 |   3 | 2016-03-22 11:55:56
   5 |   6 | 2016-03-22 11:58:23
   6 |   7 | 2016-03-22 09:51:54

I would like to "trace" each id in id1 to its oldest id2 where connection can span over id1 and id2. For instance in the above dataset I would like the resultset to contain:

1 |   4 | 2016-03-22 09:52:15
5 |   7 | 2016-03-22 09:51:54

The results should be ordered by the timestamp column.
And ideally no other occurrences of "1" and "5".

I am using Amazon Redshift, which imposes some limitations.

So far I have dabbled with using window functions combined with a self join:

SELECT t1.id1,
FIRST_VALUE(t2.id2) OVER (
   PARTITION BY t1.id1, (t1.id1=t2.id1 or t1.id2=t2.id2)
   ORDER BY t2.timestamp ASC
   ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
)
FROM    test_decision t1
LEFT JOIN test_decision t2 ON t1.id1 = t2.id2

The general idea is to group based on logical expression (e.g. contains either id1 or id2), rather than partitioning only on rows with both. I've tried SELECT ... GROUP BY in a similar manner, but without getting the results I want.

I hope this use case makes sense to some of you.

In an effort to eliminate ambiguity: The rows are connected by having a value of id1 or id2 in either id1 or id2 columns of other rows. For instance, 1 leads to 4 through rows having (id1,id2) = (1,2),(2,3) and (3,4) in my example.

Regarding recursiveness: I think I can solve it by joining multiple times and coalescing the "outermost" value, my problem here is that the problem can be arbitrarily deep, e.g. I can solve this case by joining twice, but is there a way in SQL to get arbitrary recursion depth? And is that a good idea?

  • My question was why (for example) the 09:52:15 was chosen. Is it because it's the minimum of the three timestamps (12:05:28, 11:55:56, 09:52:15) of that group or because it's in the row of the "last" (3->4) transition of that group? – ypercubeᵀᴹ Mar 24 '16 at 7:06
  • Why do you mention And ideally no other occurrences of "1" and "5". Can there be multiple roots for a single path? – Erwin Brandstetter Mar 25 '16 at 2:48
4

It's a recursive problem by nature. SQL introduced recursive CTEs for that purpose quite some time ago. Since Redshift does not seem to support this, your only remaining option to solve this within the database is a user defined function (UDF). It seems like the only server-side language supported by Redshift is plpythonu.

Here is an old answer with a PL/pgSQL function and an rCTE implementing the same solution side-by-side. But it's using the default procedural language of Postgres: PL/pgSQL:

No idea why Redshift chose not to support PL/pgSQL.

  • Alright, thank you for what seems to be the correct answer – Christoffer Pedersen Mar 25 '16 at 11:38
3

I think you need a recursive query. Something like this:

WITH RECURSIVE 
  groups (id1, id2, timestamp, level) AS   
    ( SELECT t.id1, t.id2, t.timestamp, 1 
      FROM test_decision AS t
      WHERE NOT EXISTS
            ( SELECT * 
              FROM test_decision AS p
              WHERE p.id2 = t.id1
            )
     UNION ALL
       SELECT g.id1, t.id2, t.timestamp, g.level + 1
       FROM groups AS g
         JOIN test_decision AS t
           ON g.id2 = t.id1 
    ) 
SELECT DISTINCT ON (id1) 
    id1, id2, timestamp
FROM groups 
ORDER BY id1, level DESC ;

You may have to modify the final SELECT, depending on what you want exactly for the timestamp result. The minimum value in a group or the one from the "latest" id (by latest I mean the 4 in the group 1 -> 2 -> 3 -> 4, which is not necessarily the maximum id).

  • Thank you very much for this, it seems like a great solution in a newer version of postgres. However, I am stuck with redshift, which for the most part means postures 8.* constrains. One of the effects of this is that "with recursive" is sadly not supported – Christoffer Pedersen Mar 24 '16 at 6:42
  • Oh, I hadn't notice the Redshift tag, sorry. Which Postgres is it based on? 8.3? Your query suggests that it at least has window functions, right? – ypercubeᵀᴹ Mar 24 '16 at 7:08
  • It's a bit messy with regards to exactly which version, but generally it is somewhere around 8.4, with window functions, yes. There is a list of unsupported things here: docs.aws.amazon.com/redshift/latest/dg/… . I hope that helps, and thanks again – Christoffer Pedersen Mar 24 '16 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.