data structures - Fetching linked list in MySQL database

Question

I have a MySQL database table with this structure:

table
    id INT NOT NULL PRIMARY KEY
    data ..
    next_id INT NULL

I need to fetch the data in order of the linked list. For example, given this data:

 id | next_id
----+---------
  1 |       2
  2 |       4
  3 |       9
  4 |       3
  9 |    NULL

I need to fetch the rows for id=1, 2, 4, 3, 9, in that order. How can I do this with a database query? (I can do it on the client end. I am curious if this can be done on the database side. Thus, saying it's impossible is okay (given enough proof)).

It would be nice to have a termination point as well (e.g. stop after 10 fetches, or when some condition on the row turns true) but this is not a requirement (can be done on client side). I (hope I) do not need to check for circular references.

Answer 1

Some brands of database (e.g. Oracle, Microsoft SQL Server) support extra SQL syntax to run "recursive queries" but MySQL does not support any such solution.

The problem you are describing is the same as representing a tree structure in a SQL database. You just have a long, skinny tree.

There are several solutions for storing and fetching this kind of data structure from an RDBMS. See some of the following questions:

• "What is the most efficient/elegant way to parse a flat table into a tree?"
• "Is it possible to make a recursive SQL query ?"

---

Since you mention that you'd like to limit the "depth" returned by the query, you can achieve this while querying the list this way:

SELECT * FROM mytable t1
 LEFT JOIN mytable t2 ON (t1.next_id = t2.id)
 LEFT JOIN mytable t3 ON (t2.next_id = t3.id)
 LEFT JOIN mytable t4 ON (t3.next_id = t4.id)
 LEFT JOIN mytable t5 ON (t4.next_id = t5.id)
 LEFT JOIN mytable t6 ON (t5.next_id = t6.id)
 LEFT JOIN mytable t7 ON (t6.next_id = t7.id)
 LEFT JOIN mytable t8 ON (t7.next_id = t8.id)
 LEFT JOIN mytable t9 ON (t8.next_id = t9.id)
 LEFT JOIN mytable t10 ON (t9.next_id = t10.id);

It'll perform like molasses, and the result will come back all on one row (per linked list), but you'll get the result.