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.

Answer 2

If what you are trying to avoid is having several queries (one for each node) and you are able to add columns, then you could have a new column that links to the root node. That way you can pull in all the data at once by the root id, but you will still have to sort the list (or tree) on the client side.

So in this is example you would have:

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

Of course the disadvantage of this as opposed to traditional linked lists or trees is that the root cannot change without writing on an order of magnitude of O(n) where n is the number of nodes. This is because you would have to update the root id for each node. Fortunately though you should always be able to do this in a single update query unless you are dividing a list/tree in the middle.

Answer 3

This is less a solution and more of a workaround but, for a linear list (rather than the tree Bill Karwin mentioned), it might be more efficient to use a sort column on your list. For example:

TABLE `schema`.`my_table` (
    `id` INT NOT NULL PRIMARY KEY,
    `order` INT,
    data ..,
    INDEX `ix_order` (`sort_order` ASC)
);

Then:

SELECT * FROM `schema`.`my_table` ORDER BY `order`;

This has the disadvantage of slower inserts (you have to reposition all sorted elements past the insertion point) but should be fast for retrieval because the order column is indexed.