MySQL best practice: SELECT children recursive as performant as possible?

Question

I'd like to select a root item and it's children as much performant as possible. I prefer using the nested sets model, but this time the table structure is following the adjacency model. More about nested sets and adjancency model.

I've a dependencies-table, and a items-table.

Dependencies table

dependency_id | item_id | child_id 
            1 |       1 |        4
            2 |       2 |        5
            3 |       4 |        7
            4 |       7 |        3
            5 |       9 |        3
            6 |       1 |        2

Items table

item_id | name   | info
      1 | Item A | 1st Item
      2 | Item D | 2nd Item
      3 | Item C | 3rd Item
      4 | Item D | 4th Item
      5 | Item E | 5th Item
      6 | Item F | 6th Item

SQL, first try

# selecting children (non-recursive)
# result: 4, 2
SELECT 
   child_id AS id 
  FROM `dependencies_table`
 WHERE item_id = 1

I need this SELECT recursive.

Desired output

# children of item #1
dependency_id | item_id | child_id
            1 |       1 |        4 // 1st level
            6 |       1 |        2 // 1st level
            2 |       2 |        5 // 2nd level, 1->2->5

This case should be very common, but I'm wondering I couldn't find a best-practice for now. Please note: it's MySQL, so I'm not able using CTE!

How would you solve this problem? Thanks in advance!

Edit: I found an interesting thread, but my problem isn't solved yet. So, please don't close this Question.

Edit 2: Here's an interesting PHP solution, but unfortunately not what I actually want.

Answer 1

As a NoSQL Person i have to say thats what graphs are for. But yeah i get it..there are reasons for using SQL, but this particular example is just not what these Databases are made for, especially when you can have n level of children mysql is going to perform extremly slow, there is actually a query for this, even for n levels, but thats some crazy shit. (something about 42 Inner Joins if i remember correctly)

So Yeah, you want to fetch the tables and do the children stuff in php.

Here is how you get your result in php once you have fetched the entire Dependencies Table,

$dep = array();
$dep[] = array('item_id' =>'1', 'child_id' =>'4');
$dep[] = array('item_id' =>'2', 'child_id' =>'5');
$dep[] = array('item_id' =>'4', 'child_id' =>'7');
$dep[] = array('item_id' =>'7', 'child_id' =>'3');
$dep[] = array('item_id' =>'9', 'child_id' =>'3');
$dep[] = array('item_id' =>'1', 'child_id' =>'2');

function getchilds($dependencies, $id) {

    $ref = array();
    foreach($dependencies as $dep){
        $item_id = $dep['item_id'];
        $child = $dep['child_id'];
        if(!is_array($ref[$item_id])) $ref[$item_id] = array('id' => $item_id);
        if(!is_array($ref[$child])) $ref[$child] = array('id' => $child);
        $ref[$item_id]['children'][] = &$ref[$child];
    }
    return $ref[$id];
}

getchilds($dep,1);

This uses References to go through every item only once, i cant image anything more performant and it works for infinite number of levels. Actually i bet this is faster than any SQL Query for fixed number of levels.

for the first item this will basically give you

1 - 2 - 5
 \ 
  4 - 7 - 3

Answer 2

Oracle allows hierarchical queries using CONNECT BY PRIOR, but this is not supported in MySQL. As such, this is best accomplished in the programming language.

That said, if you must do this in SQL and accept a fixed recursion depth, you can use a messy set of self joins with UNION. For example, this recurses three levels:

SELECT a.child_id
  FROM dependencies_table a
  WHERE a.item_id = '1'
UNION
SELECT b.child_id
  FROM dependencies_table a
  JOIN dependencies_table b ON (a.child_id = b.item_id)
  WHERE a.item_id = '1'
UNION
SELECT c.child_id
  FROM dependencies_table a
  JOIN dependencies_table b ON (a.child_id = b.item_id)
  JOIN dependencies_table c ON (b.child_id = c.item_id)
  WHERE a.item_id = '1'

Yielding the following results as items that are in some way dependencies of item 1:

4
2
5
7
3

SQL Fiddle