Is there a way to get nested data out of MySQL without using recursion?

Question

So let us say that I have a menu system with all the navigation items stored in a MySQL table like so:

Table: Menu
-------------------------------------------------------
| id | title      | url                   | parent_id |
-------------------------------------------------------
| 1  | Home       | /home                 | 0         |
| 2  | About      | /about                | 0         |
| 3  | History    | /about/history        | 2         |
| 4  | Location   | /about/location       | 2         |
| 5  | Staff      | /about/staff          | 2         |
| 6  | Articles   | /blog                 | 0         |
| 7  | Archive    | /blog/archive         | 6         |
| 8  | Tags       | /blog/tags            | 6         |
| 9  | Tag Name 1 | /blog/tags/tag-name-1 | 8         |
| 10 | Tag Name 2 | /blog/tags/tag-name-2 | 8         |
-------------------------------------------------------

As you can see this table is quite simple with the only complication being the self referencing column parent_id, which defines how the menu should be nested.

So this would produce the following menu:

- Home
- About
    - History
    - Location
    - Staff
- Articles
    - Archive
    - Tags
        - Tag Name 1
        - Tag Name 2

Is there a way to get this structure from the aforementioned table without making use of a recursive function in PHP (but it could be Python, Java or any other language) that queries the database with each iteration?

Ideally this could be handled with one MySQL query. Perhaps the table structure needs to be changed to accommodate this - if so how?

Is there a specific reason that prevents you from using a recursive function? It's the most reasonable solution for data structures like this. — Till Helge, Dec 01 '11 at 12:05
@TillHelgeHelwig The code does currently use a recursive function, but I would like to reduce the number of database hits incurred during menu rendering. So I figure I have two options. Either cache the menu or attempt to obtain the data in a single MySQL query. It would also be nice to get the nested structure out of MySQL for debugging purposes. — Treffynnon, Dec 01 '11 at 12:08
yes - see here http://stackoverflow.com/questions/5291054/hierarchical-sql-problem/5291159#5291159 — Jon Black, Dec 01 '11 at 12:08
@Treffynnon Ugh. Having a query inside the recursion is obviously bad. Just fetch all data at once and then have the recursion handle the "cached" data. Enough links are already posted about this. :) — Till Helge, Dec 01 '11 at 12:11
Yeah. Third party software is a PITA. I am trying to avoid changing as much code in it as possible. — Treffynnon, Dec 01 '11 at 12:12

Jan Dragsbaek · Accepted Answer · 2011-12-01T13:00:48.893

You could pull all of it out in one single pull, and then work with it recursively in PHP. That way you save some of the query time, but gain a little scripting time.

I would do something like this:

Get all data, ordered by parent id
Put row into $data[$parent_id][]

define function to build menu, takes one param which is id
get $data[$id] and work with that array, building the array.

while looping through the items, check if size of $data[current-item-id] > 0
if so, call above function with 0 as param

This way, you only query the database once, but use a little more of the servers ram.

score 2 · Answer 2 · edited May 23 '17 at 11:48

2

If you're fetching the whole tree and you can't or don't want to change the table structure, take a look at https://stackoverflow.com/a/8325451/4833

edited May 23 '17 at 11:48

Community

1
1

answered Dec 01 '11 at 12:11

VolkerK

95,432
20
163
226

score 1 · Answer 3 · answered Dec 01 '11 at 12:06

1

This can be done in sql query, take a look at this resource which explains recursion in a query

http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html.

answered Dec 01 '11 at 12:06

Matt Seymour

8,880
7
60
101

score 0 · Answer 4 · answered Dec 01 '11 at 12:07

MySQL don't have an default function to do that.

You can make an procedure with loop to get the data result you want, or create an function and use in your sql select.

Anyway you will use loop.

Example:

DROP PROCEDURE IF EXISTS famsubtree;
DELIMITER go
CREATE PROCEDURE famsubtree( root INT )
BEGIN
  DROP TABLE IF EXISTS famsubtree;
  CREATE TABLE famsubtree
    SELECT childID, parentID, 0 AS level
    FROM familytree
    WHERE parentID = root;
  ALTER TABLE famsubtree ADD PRIMARY KEY(childID,parentID);
  REPEAT
    INSERT IGNORE INTO famsubtree
      SELECT f.childID, f.parentID, s.level+1
      FROM familytree AS f
      JOIN famsubtree AS s ON f.parentID = s.childID;
  UNTIL Row_Count() = 0 END REPEAT;
E    ND ;
go
DELIMITER ;

And use to query:

call famsubtree(1);       -- from the root you can see forever
SELECT Concat(Space(level),parentID) AS Parent, Group_Concat(childID ORDER BY childID) AS Child
FROM famsubtree
GROUP BY parentID;

Is there a way to get nested data out of MySQL without using recursion?

4 Answers4