Using MySQL query to traverse rows to make a recursive tree

Question

I have a bill of materials table that is set up like this:
item - parent

The end result when I display the bill of materials is that it is displayed like this:

item 1  - parent 0    
    item 2 - parent 1    
    item 3 - parent 1    

The final result could also be multi level like this:

item 3 - parent 0    
    item 4 - parent 3    
    item 76 - parent 3    

And it can go on ad infinitum:

item 76 - parent 0    
    item 46 - parent 76    

item 46 - parent 0     
    item 25 - parent 46

Right now, I either just get 1 level from the database:

SELECT * FROM bom WHERE parentId = $itemId (shorthand)

Or pull every row from the table and use my recursive function to sort out just the ones I need, but this is obviously inefficient as I may only need 10 rows, but I pull 10,000 records. The output of the recursive function will just create a tree like this:

item 1
   item 2
   item 3
      item 4
      item 76
         item 46
            item 25

All I know is that I am starting at item 1. Item 5 could have a parent of 11; they do not have to go sequential. I want to get all of the child branches in the tree. How could I do this query in mysql?

Solution 1

Back in October 24, 2011, someone posted a question in the DBA StackExchange about tree traversal in MySQL. The SQL for MySQL cannot support it.

I wrote up three(3) Stored Procedures (GetParentIDByID, GetAncestry and GetFamilyTree) in my answer to that question. Hope this information helps you construct what you are looking for.

Solution 2

Bill Karwin has posted a slide show about heirarchical data in MySQL. If changing your database design is an option, there are some other appealing ways to store your data to make it easier to query. The approaches he covers are:

• Adjacency List
• Path Enumeration
• Nested Sets
• Closure Table

Slide 69 has a nice table showing the pros and cons of each method, so I suggest you look at that slide first to see which approach might work for you, then go back and look at the details of how to implement it. Note that the design you have chosen (adjacency list) is the only one of the four designs presented that makes it hard to query a subtree.

Having said that, if you can't change your design or you want to stick with the adjacency list then I have to agree with Didier that you should take a look at Quassnoi's article "Hierarchical queries in MySQL". It is a very clear article and explains how to write the query efficiently.

Solution 3

AFAIK, it is non trivial to do this with MySQL.

Here is a good set of articles about it:

http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

Solution 4

MySQL (8) nowadays supports recursive queries.

Considering your table item(id, parent) and a starting item with id = 1, the following would do the job:

with recursive result(id, parent) as (select id, parent from item where id = 1 union all select i.id, i.parent from item i join result on i.parent = result.id) select * from result;

View more solutions

Comments

[phpmeh]

Ya I knew it wasn't a basic question. :P Thanks for the articles. I will definitely check that out.

[phpmeh]

Great resource. I put it up for bounty to get information just like that. Thank you!

[idok]

Excellent procedure. But then SELECT id,GetFamilyTree(id) FROM pctable; throws an error : ERROR 1292 (22007): Truncated incorrect DOUBLE value: '4,5'. I tried to debug it, but in vain. Would you have any idea! Thanks

[jscul]

Does the n^2 one even count? I mean, that table will become EXPANSIVE depending on your data structure... seems like the left/right node one would be the optimal choice but then you have to worry about indexing and re-indexing with row inserts, right?