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.

I am not sure what you want. Are yo uhaving a problem implementing nested sets model (which you say you want to use) or are you just giving up on the thought of nested sets and using adjacency and are having a problem with that? Define what you mean by recursive? Are you limiting recursion depth at all? — Mike Brant, Sep 21 '13 at 00:14
@MikeBrant Thanks for your question. As I already mentioned, I prefer nested sets but have to use adjacency. It's about adjacency right now. Recursive: getting the children and children of the children, etc. A limited depth would be okay. — Mr. B., Sep 21 '13 at 00:21
@MarcusAdams Thanks for your advice. I just posted my desired output. — Mr. B., Sep 21 '13 at 00:29
I believe you cannot do it with just MySQL query alone, but you can use PHP to do recursive query. — invisal, Sep 21 '13 at 00:35
@invisal I try to avoid multiple queries, because that seems not to be that performant. — Mr. B., Sep 21 '13 at 00:40
That is just the type of thing you would want to deal on the PHP side rather than on MySQL level. — Prix, Sep 21 '13 at 01:33
For your future grammatical awareness: there is no such word as "performant". You probably mean "performance". — dar7yl, Sep 21 '13 at 16:37
@dar7yl "performant" is the adjective of "performance". I'm not a native speaker, but take a look: http://en.wiktionary.org/wiki/performant — Mr. B., Sep 21 '13 at 16:40

joschua011 · Accepted Answer · 2013-09-21T20:24:05.393

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

Unfortunately not what I actually wanted but a very good alternative. Thanks a lot! — Mr. B., Sep 24 '13 at 14:45

score 1 · Answer 2 · answered Sep 21 '13 at 20:04

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:

SQL Fiddle

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

2 Answers2

Linked