Take the 2-minute tour ×

I'm looking for the simplest way to recursively get all the parent elements from a database using the adjacency list / single table inheritance model (id, parent_id).

My select currently looks like this:

$sql = "SELECT
             TIME_FORMAT(e.start_time, '%H:%i') AS start_time,
             $title AS title,
             $description AS description,
             $type AS type,
             $place_name AS place_name,
             p.parent_id AS place_parent_id,
             p.city AS place_city,
             p.country AS place_country
         FROM event AS e
         LEFT JOIN place AS p ON p.id = e.place_id                          
         LEFT JOIN event_type AS et ON et.id = e.event_type_id
         WHERE e.day_id = '$day_id'
         AND e.private_flag = 0
         ORDER BY start_time";

Each event is linked to a place, and each place can be a child of another place (upto about 5 levels deep)

Is this possible in a single select with mysql?

At the moment I am thinking it could be a separate function which loops through the returned $events array, adding place_parent_X elements as it goes, but am not sure how to implement this.

share|improve this question
add comment

3 Answers

It's possible to do it in MySQL, but you'll need to create a function and use in in a query.

See this entry in my blog for detailed explanations:

Here are the function and the query:

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;

        SET _parent = @id;
        SET _id = -1;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

                SELECT  MIN(id)
                INTO    @id
                FROM    place
                WHERE   parent = _parent
                        AND id > _id;
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, parent
                INTO    _id, _parent
                FROM    place
                WHERE   id = _parent;
        END LOOP;

SELECT  id, parent
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
        FROM    (
                SELECT  @start_with := 0,
                        @id := @start_with,
                        @level := 0
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    place hi
ON      hi.id = ho.id

The latter query will select all descendants of a given node (which you should set in the @start_with variable)

To find all ancestors of a given node you can use a simple query without functions:

SELECT  @r AS _id,
        @r := (
        SELECT  parent
        FROM    place
        WHERE   id = _id
        ) AS parent
FROM    (
        SELECT  @r := @node_id
        ) vars,

This article in my blog described this query in more detail:

For both these solutions to work in reasonable time, you need to have the indexes on both id and parent.

Make sure your id is defined as a PRIMARY KEY and you have a seconday index on parent.

share|improve this answer
Link to blog, please? –  razzed Jun 25 '09 at 16:08
@razzed: a moment, sorry :) –  Quassnoi Jun 25 '09 at 16:10
The second query looks good, could you explain what it's doing in more detail? –  meleyal Jun 26 '09 at 10:18
@htxt: see the link to the article in my blog which describes this query –  Quassnoi Jun 26 '09 at 10:23
@htxt: but note that it builds the list of ancestors, not descendants. To build a list of descendants, you'll still need the ugly function. –  Quassnoi Jun 26 '09 at 10:24
show 1 more comment

It's not possible with the standard parent-child DB design.

However, you could use a nested set approach and do it in one query, though that will take quite a bit of work to get to that point.

share|improve this answer
Nested sets would require a change in the db schema, which is not possible in my case –  meleyal Jun 25 '09 at 14:04
Yep. Then you'd have to do some sort of recursive approach, in either the MySQL (which you might not have access to do), or in your PHP (which will be messy and slow). –  mgroves Jun 25 '09 at 14:07
Messy and slow would be OK, I just need some pointers on how to do it ;) –  meleyal Jun 25 '09 at 14:09
add comment

Looks like the easiest is nested sets.

share|improve this answer
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. –  Sam I am Nov 13 '12 at 0:50
add comment

Your Answer


