MySQL SELECT Tree Parent IDs

Question

How can I sort the records of a SELECT statement so that they represent a valid tree?

All of my attempts show sub-nodes nested under wrong parent nodes. What is the most reliable way to achieve this ordering?

Data

ID      Parent ID      Title
--------------------------------------------
0       NULL           Root
1       0              Node A
2       0              Node B
3       1              Sub-Node C
4       1              Sub-Node D
5       3              Sub-Node E

Output

ID      Parent ID      Title
--------------------------------------------
0       NULL           Root
1       0              Node A
3       1              Sub-Node C
5       3              Sub-Node E
4       1              Sub-Node D
2       0              Node B

Data Visualisation

Root
    Node A
        Sub-Node C
            Sub-Node E
        Sub-Node D
    Node B

While the examples provided below show some really cool queries, I don't think that it's the data layer's job to provide the visualization. You can do that easier (and a lot more visually appealing) with PHP. — Blindy, Apr 16 '11 at 17:57
@Blindy I agree with you. I was hoping that there would be a performance effective way to retrieve the results with a simple query but it doesn't look like it is going to be very easy that way. The only solution that comes to mind is to sort with PHP into a series of temporary arrays. I only require a flat array, but one which is sorted for adjacency. — Lea Hayes, Apr 16 '11 at 18:03
look at this answer for the same case: http://stackoverflow.com/a/33699713/5559741 — Wajih, Nov 13 '15 at 18:48

Emil Vikström · Answer 1 · 2016-08-29T12:23:14.523

13

You can use Nested Sets. Check out this article:

Managing Hierarchical Data in MySQL

The author describes a few different methods for building hierarchies in SQL, complete with example queries. It's a very good read about this subject!

edited Aug 29 '16 at 12:23

answered Apr 16 '11 at 17:48

Emil Vikström

90,431
16
141
175

1

I know this is an old question but just for future reference: Nested Sets are good for tree-structures that are being read most of the time but rarely changed (INSERT, UPDATE, DELETE) because writing options in nested sets are extremely costly: https://robsite.net/nested-sets-suck-on-how-not-to-map-trees-into-a-relational-database/ – Broco Aug 29 '16 at 08:56
Thank you, Broco! I agree somewhat with that solution. Feel free to post your own answer. It's in essence a materialized view! – Emil Vikström Aug 29 '16 at 12:25

score 5 · Accepted Answer · answered Apr 17 '11 at 16:59

5

Following the advice of @Blindy I have implemented this sort with PHP. Here are the two functions that seem to solve this issue relatively easily.

protected function _sort_helper(&$input, &$output, $parent_id) {
    foreach ($input as $key => $item)
        if ($item->parent_id == $parent_id) {
            $output[] = $item;
            unset($input[$key]);

            // Sort nested!!
            $this->_sort_helper(&$input, &$output, $item->id);
        }
}

protected function sort_items_into_tree($items) {
    $tree = array();
    $this->_sort_helper(&$items, &$tree, null);
    return $tree;
}

I would be interested to hear if there is a simpler approach, but this does seem to work.

answered Apr 17 '11 at 16:59

Lea Hayes

62,536
16
62
111

1

Call-time pass-by-reference has been removed in php5.4 – RouR Aug 14 '13 at 04:38
@RouR If I recall this just means that you need to change the way you invoke `_sort_helper`. Instead try using `$this->_sort_helper($input, $output, $item->id);` and `$this->_sort_helper($items, $tree, null);`. Let me know if this helps and I will update my answer accordingly :) – Lea Hayes Aug 14 '13 at 13:11

score 4 · Answer 3 · edited May 23 '17 at 11:51

MySQL has no support for recursive queries

You will need to self join the table as many times as the maximum hierarchy level is, but still it's pretty ugly to get one row for each hierarchy level that way.

See these posts for some ideas and examples:

Category Hierarchy (PHP/MySQL)

how can we write mysql query where parent id have a child id and next time child id is a parent id how can i do?

score 0 · Answer 4 · answered Feb 19 '13 at 23:48

I just finished this recursive function, and thought it was an elegant way about the problem. Here's what I did once I made a basic SELECT mysql query:

function orderChildren($data){
    $tree = array();
    foreach($data as $value){
        if($value['parent_id'] == null){  // Values without parents
            $tree[$value['id']] = $this->goodParenting($value, $data);
        }
    }
    return $tree;
}

private function goodParenting($parent, $childPool){
    foreach($childPool as $child){
        if($parent['id'] == $child['parent_id']){
            $parent['children'][$child['id']] = $this->goodParenting($child, $childPool);
        }
    }
    return $parent;
}

score 0 · Answer 5 · answered Mar 09 '13 at 02:18

Here is another way to do your PHP function.

function buildTree() {
  $data = array();
  $pointers = array();

  $sql = "SELECT ID,PARENT,TITLE FROM TREE ORDER BY TITLE ASC";
  $res = $this->db->query($sql);

  while ($row = $res->fetch(PDO::FETCH_ASSOC)) {
    if(!isset($pointers[$row['ID']])) {
      $pointers[$row['ID']] = $row;
    }

    if(!empty($row['PARENT'])) {
      if(!isset($pointers[$row['PARENT']])) {
        $pointers[$row['PARENT']] = $row;
      }
      $pointers[$row['PARENT']][$row['ID']] =  &$pointers[$row['ID']];
    } else {
      $data[$row['ID']] = &$pointers[$row['ID']]; // This is our top level
    }
  }

  unset($pointers);
  return $data;
}

MySQL SELECT Tree Parent IDs

5 Answers5

Linked