How to resolve SQL id chain?

Question

I have an MySQL DB with table like that:

|  id   | redirect |
+-------+----------+
|   1   |   NULL   |
|   2   |    3     |
|   3   |   NULL   |
|   4   |    5     |
|   5   |    6     |
|   6   |    8     |
|   7   |   NULL   |
|   8   |   NULL   |
+-------+----------+

I need to create query for recursive resolving redirects. So I can get results:

Thanks

OP's after the left node from the starting ID, if no leaf node, then self reference. — xQbert, Jul 03 '14 at 18:03
iam not sure if its resolvable with a single querry, but why not resolve it once at time of data base entry. — vlad_tepesch, Jul 03 '14 at 18:14
@Satwik Nadkarny: It actually does make sense. Those rows "have to be 8" because 8 is the terminating node for the path beginning with 4, it's also the terminating node for the path beginning with 5, and beginning with 6. — spencer7593, Jul 03 '14 at 18:38
A stored **procedure** can call itself (recursively). Stored procedure recursion is controlled by the system variable [`max_sp_recursion_depth`](http://dev.mysql.com/doc/refman/5.5/en/server-system-variables.html#sysvar_max_sp_recursion_depth). Stored **functions** cannot be recursive, so you could make a function that calls a recursive stored procedure. You don't necessarily have to use recursion either. You could just use a `WHILE` loop in a stored function or procedure. See similar: http://stackoverflow.com/questions/3438111/mysql-stored-procedure-that-calles-itself-recursively — Marcus Adams, Jul 03 '14 at 18:45

spencer7593 · Answer 1 · 2014-07-03T18:57:59.173

One approach is to get each "level" with a separate query.

To get the first level, we can test for a NULL in redirect_id column to identify a "terminating" node.

To get the second level, we can use a JOIN operation to match rows that have a redirect_id that match the id from a "terminating" row (identified previously).

The third level follows the same pattern, adding another JOIN operation to return rows that redirect to a level two row.

And so on.

For example:

SELECT t1.id  AS start_id
     , t1.id  AS terminate_id
  FROM mytable t1
 WHERE t1.redirect_id IS NULL

 UNION ALL

SELECT t2.id
     , t1.id
  FROM mytable t1
  JOIN mytable t2 ON t2.redirect_id = t1.id
 WHERE t1.redirect_id IS NULL

 UNION ALL

SELECT t3.id
     , t1.id
  FROM mytable t1
  JOIN mytable t2 ON t2.redirect_id = t1.id
  JOIN mytable t3 ON t3.redirect_id = t2.id
 WHERE t1.redirect_id IS NULL


 UNION ALL

SELECT t4.id
     , t1.id
  FROM mytable t1
  JOIN mytable t2 ON t2.redirect_id = t1.id
  JOIN mytable t3 ON t3.redirect_id = t2.id
  JOIN mytable t4 ON t4.redirect_id = t3.id
 WHERE t1.redirect_id IS NULL

The limitation of this single-query UNION ALL approach is that it would need to be extended to a finite maximum number of levels. (This approach is not truly "recursive".)

If we needed a truly recursive approach, we could run each query separately, just adding an extra "level" for each run, following the same pattern. We'd know that we'd exhausted all possible paths when the result of a query returns no rows.

I've demonstrated the use of the UNION ALL operator to combine the results into a single set, using a single query. (Add an ORDER BY clause at the end of the statement if the order of the rows is important. It would also be easy to include a literal "level" column to the resultset, e.g. 1 AS level for the first SELECT, the 2 on the second query, etc. to identify how far a node was from the termination.

MySQL doesn't support an Oracle style CONNECT BY syntax (in Oracle, we COULD write a single query that would traverse this set and return the specified rows, an arbitrary number of levels.)

To get a truly "recursive" approach in MySQL would require multiple queries. (Note that MySQL can support "recursion" in stored procedure calls, if the server is configured to allow it.)

How to resolve SQL id chain?

1 Answers1