loading an entire linked list in a single Ruby/MySQL query

Question

I'm storing linked lists of data in records that look like this:

CREATE TABLE IF NOT EXISTS `data_nodes` (
  `record_id` int(11) NOT NULL,
  `prev_node` int(11) NOT NULL,
  `data` varchar(200) NOT NULL,
  PRIMARY KEY  (`record_id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

where prev_node is the record_id of the previous item in the list, or 0 if we're at the first item in the list.

A typical list might look something like :

record_id     prev_node     data
---------     ---------     ----
1             0             first item
12            1             second item
27            12            third item

I'm using Ruby's mysql module, and what I'd like to do is: given the record number of the last item in a list, load the entire list in a single query. (e.g. given the record id 27, return a result set that contains "first item", "second item", "third item")

Can this be done?

Thanks.

Answer 1

It looks like this would require recursion. I don't know if MySQL yet implements recursion in SQL, and if it does, it probably wouldn't be very performant. I'm not sure if storing the data like this is the best solution.

Answer 2

It's possible for tree of any fixed height N, but you won't be able to do this operation, if tree height becomes N+1.

In other words, if you know how many levels of parent/child nodes there are, you may build a query as explained here (search for Retrieving a Single Path): http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

You may use nested set model and RoR plugin acts_as_nested_set to get the results you want.

If you need help on the article, let know.

Answer 3

You would need a recursive SQL query, e.g. START WITH ... CONNECT BY in Oracle. Unfortunately, MySQL does not support such a construct in a single query. Stored functions can't do recursion either.