SQL query to get the leaf record in a parent-child relationship

Question

I use PostgreSQL. I have 2 tables, products and product_renewals.

Products

+----+--------+
| id |  name  |
+----+--------+
|  1 | Foo    |
|  2 | Bar    |
|  3 | Foo    |
|  4 | Foo    |
+----+--------+

ProductRenewals

+----+--------+--------+
| id | old_id | new_id |
+----+--------+--------+
|  1 | 1      | 3      |
|  2 | 3      | 4      |
+----+--------+--------+

Each time a product is renewed, a renewal record is creating with the reference to the old and the new product.

What I'd like to be able to build is a query that, given a Product ID, returns the ID of the latest product in the renewal chain. If the product is not renewed (or is already the most recent one), then that ID is returned. What the database has to do is to walk the renewal chain from parent to child, down to the leaf.

Examples:

Case 1) Given ProductID 1, it returns 4 (4 renews 3 that renews 1)
Case 2) Given ProductID 3, it returns 4 (4 renews 3)
Case 3) Given ProductID 4, it returns 4 (4 is not renewed)
Case 4) Given ProductID 2, it returns 2 (2 is not renewed)

I would be ok if Case 3 and Case 4 returns nil (for simplicity).

I tried to build something and it seems to me I need a recursive query, but honestly I did not get a lot out of the attempts. Can you provide some guidance or reference?

Answer 1

This was written while exploring various ways, so if you just want the best solution, see at bottom, otherwise read on to follow the train of thoughts and the progressive refinements.

If you can guarantee order in our IDs (that is new_id > old_id for any renewal, if that is not true see below for enhanced method) then you can do:

WITH RECURSIVE renewals AS (
    SELECT old_id, new_id FROM ProductRenewals WHERE old_id = 1 
    UNION ALL
    SELECT pr.old_id, pr.new_id FROM ProductRenewals pr 
        INNER JOIN renewals r ON pr.old_id=r.new_id)
SELECT new_id FROM renewals ORDER BY new_id DESC LIMIT 1

Replace the 1 in old_id = 1 by the value you want to query for. This will return either nothing (cases 3 and 4) or the id (cases 1 and 2) as such:

test=# WITH RECURSIVE renewals AS (SELECT old_id, new_id FROM ProductRenewals WHERE old_id = 1 UNION ALL SELECT pr.old_id, pr.new_id FROM ProductRenewals pr INNER JOIN renewals r ON pr.old_id=r.new_id) SELECT new_id FROM renewals ORDER BY new_id DESC LIMIT 1;
 new_id
--------
      4
(1 row)

test=# WITH RECURSIVE renewals AS (SELECT old_id, new_id FROM ProductRenewals WHERE old_id = 2 UNION ALL SELECT pr.old_id, pr.new_id FROM ProductRenewals pr INNER JOIN renewals r ON pr.old_id=r.new_id) SELECT new_id FROM renewals ORDER BY new_id DESC LIMIT 1;
 new_id
--------
(0 rows)

test=# WITH RECURSIVE renewals AS (SELECT old_id, new_id FROM ProductRenewals WHERE old_id = 3 UNION ALL SELECT pr.old_id, pr.new_id FROM ProductRenewals pr INNER JOIN renewals r ON pr.old_id=r.new_id) SELECT new_id FROM renewals ORDER BY new_id DESC LIMIT 1;
 new_id
--------
      4
(1 row)

test=# WITH RECURSIVE renewals AS (SELECT old_id, new_id FROM ProductRenewals WHERE old_id = 4 UNION ALL SELECT pr.old_id, pr.new_id FROM ProductRenewals pr INNER JOIN renewals r ON pr.old_id=r.new_id) SELECT new_id FROM renewals ORDER BY new_id DESC LIMIT 1;
 new_id
--------
(0 rows)

If you replace the latest SELECT by SELECT MAX(new_id) FROM renewals you will get either an id or NULL. You could also do something like SELECT COALESCE(MAX(new_id), 0) FROM renewals, or reuse the id you used as input instead of 0 to match your first design.

Postgresql documentation on recursive CTE is at https://www.postgresql.org/docs/8.4/static/queries-with.html and you can find a canonical example with employees and managers at http://www.postgresqltutorial.com/postgresql-recursive-query/

With as slight change of the above, you do not need to hold any condition on how the id are ordered, just store a counter at each "iteration" step of the recursion, like that:

test=# WITH RECURSIVE renewals AS (SELECT 1 iter, old_id, new_id FROM ProductRenewals WHERE old_id = 1 UNION ALL SELECT r.iter + 1, pr.old_id, pr.new_id FROM ProductRenewals pr INNER JOIN renewals r ON pr.old_id=r.new_id) SELECT new_id FROM renewals ORDER BY iter DESC LIMIT 1;

(do not change the first 1, it is the starting counter completely not related to your id values, even if any value would fit here in fact)

In fact by slightly elaborating on this you can use this final form that both allows you to get exactly the result as expected (specially in case of non renewals) and also do not care about ordering at all. See:

test=# WITH RECURSIVE renewals AS (SELECT * FROM input UNION ALL SELECT r.iter + 1, pr.old_id, pr.new_id FROM ProductRenewals pr INNER JOIN renewals r ON pr.old_id=r.new_id), input AS (SELECT 1 iter, id old_id, id new_id FROM Products WHERE id = 1) SELECT new_id FROM renewals ORDER BY iter DESC LIMIT 1;
 new_id
--------
      4
(1 row)

test=# WITH RECURSIVE renewals AS (SELECT * FROM input UNION ALL SELECT r.iter + 1, pr.old_id, pr.new_id FROM ProductRenewals pr INNER JOIN renewals r ON pr.old_id=r.new_id), input AS (SELECT 1 iter, id old_id, id new_id FROM Products WHERE id = 2) SELECT new_id FROM renewals ORDER BY iter DESC LIMIT 1;
 new_id
--------
      2
(1 row)

rest=# WITH RECURSIVE renewals AS (SELECT * FROM input UNION ALL SELECT r.iter + 1, pr.old_id, pr.new_id FROM ProductRenewals pr INNER JOIN renewals r ON pr.old_id=r.new_id), input AS (SELECT 1 iter, id old_id, id new_id FROM Products WHERE id = 3) SELECT new_id FROM renewals ORDER BY iter DESC LIMIT 1;
 new_id
--------
      4
(1 row)

test=# WITH RECURSIVE renewals AS (SELECT * FROM input UNION ALL SELECT r.iter + 1, pr.old_id, pr.new_id FROM ProductRenewals pr INNER JOIN renewals r ON pr.old_id=r.new_id), input AS (SELECT 1 iter, id old_id, id new_id FROM Products WHERE id = 4) SELECT new_id FROM renewals ORDER BY iter DESC LIMIT 1;
 new_id
--------
      4
(1 row)