EXPLAIN EXTENDED

Answering questions asked on the site.

Michael asks:

I was wondering how to implement a hierarchical query in MySQL (using the ancestry chains version) for a single row, such that it picks up the parents (if any) and any children (if any).

The idea is, I want to be able to jump in at any point, provide an Id of some sort, and be able to draw out the entire hierarchy for that Id, both upwards and downwards.

We need to combine two queries here:

1. Original hierarchical query that returns all descendants of a given id (a descendancy chain)
2. A query that would return all ancestors of a given id (an ancestry chain)

An id can have only one parent, that’s why we can employ a linked list technique to build an ancestry chain, like shown in this article:

• Sorting lists

Here’s the query to to this (no functions required):

SELECT  @r AS _id,
         (
         SELECT  @r := parent
         FROM    t_hierarchy
         WHERE   id = _id
         ) AS parent,
         @l := @l + 1 AS lvl
 FROM    (
         SELECT  @r := 1218,
                 @l := 0,
                 @cl := 0
         ) vars,
         t_hierarchy h
WHERE    @r <> 0

To combine two queries, we can employ a simple UNION ALL.

The only problem that is left to preserve the correct level, since the ancestry chain query conts level backwards, and the hierarchical query will count it starting from zero.

Let’s create a sample table and see what we get:

Table creation details

CREATE TABLE t_hierarchy (
        id int(10) unsigned NOT NULL AUTO_INCREMENT,
        parent int(10) unsigned NOT NULL,
        PRIMARY KEY (id),
        KEY ix_hierarchy_parent (parent, id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

DELIMITER $$
CREATE PROCEDURE prc_fill_hierarchy (level INT, fill INT)
BEGIN
        DECLARE _level INT;
        DECLARE _fill INT;
        INSERT
        INTO    t_hierarchy (id, parent)
        VALUES  (1, 0);
        SET _fill = 0;
        WHILE _fill < fill DO
                INSERT
                INTO    t_hierarchy (parent)
                VALUES  (1);
                SET _fill = _fill + 1;
        END WHILE;
        SET _fill = 1;
        SET _level = 0;
        WHILE _level < level DO
                INSERT
                INTO    t_hierarchy (parent)
                SELECT  hn.id
                FROM    t_hierarchy ho, t_hierarchy hn
                WHERE   ho.parent = 1
                        AND hn.id > _fill;
                SET _level = _level + 1;
                SET _fill = _fill + POWER(fill, _level);
        END WHILE;
END
$$
DELIMITER ;

DROP FUNCTION IF EXISTS hierarchy_connect_by_parent_eq_prior_id;

DELIMITER $$

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

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

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

        LOOP
                SELECT  MIN(id)
                INTO    @id
                FROM    t_hierarchy
                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    t_hierarchy
                WHERE   id = _parent;
        END LOOP;       
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_fill_hierarchy(6, 5);
COMMIT;

Now, let’s try to UNION ALL the queries as is:

SELECT  CONCAT(REPEAT('    ', lvl  - 1), _id) AS treeitem, parent, lvl AS level
FROM    (
        SELECT  @r AS _id,
                (
                SELECT  @r := parent
                FROM    t_hierarchy
                WHERE   id = _id
                ) AS parent,
                @l := @l + 1 AS lvl
        FROM    (
                SELECT  @r := 1218,
                        @l := 0,
                        @cl := 0
                ) vars,
                t_hierarchy h
        WHERE   @r <> 0
        ORDER BY
                lvl DESC
        ) qi
UNION ALL
SELECT  CONCAT(REPEAT('    ', level  - 1), CAST(hi.id AS CHAR)), parent, level
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
        FROM    (
                SELECT  @start_with := 1218,
                        @id := @start_with,
                        @level := 0
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    t_hierarchy hi
ON      hi.id = ho.id

We see that the hierarchical order is mangled: the first resultset is upside down, the second one is starting from level = 1.

To fix it, we need to change the code that calculates level a little.

First, we need to reverse the ancestry part.

This can be easily done by sorting it on lvl DESC:

SELECT  CONCAT(REPEAT('    ', level  - 1), _id) AS treeitem, parent, level
FROM    (
        SELECT  @r AS _id,
                (
                SELECT  @r := parent
                FROM    t_hierarchy
                WHERE   id = _id
                ) AS parent,
                @l := @l + 1 AS level
        FROM    (
                SELECT  @r := 1218,
                        @l := 0,
                        @cl := 0
                ) vars,
                t_hierarchy h
        WHERE   @r <> 0
        ORDER BY
                level DESC
        ) qi

We now have it in correct order but with wrong level values.

Since a level is essentially a rownum here, we can just calculate it as a rownum instead:

SELECT  CONCAT(REPEAT('    ', level  - 1), id) AS treeitem, parent, level
FROM    (
        SELECT  _id AS id, parent,
                @cl := @cl + 1 AS level
        FROM    (
                SELECT  @r AS _id,
                        (
                        SELECT  @r := parent
                        FROM    t_hierarchy
                        WHERE   id = _id
                        ) AS parent,
                        @l := @l + 1 AS level
                FROM    (
                        SELECT  @r := 1218,
                                @l := 0,
                                @cl := 0
                        ) vars,
                        t_hierarchy h
                WHERE   @r <> 0
                ORDER BY
                        level DESC
                ) qi
        ) qo

We disregard the previously selected level at all, leaving it only inside the inline view qi for ordering purposes.

Now, we need to merge the descendancy tree query, but with levels starting from 6, not from 1.

Since this query will come after the ancestry one, we can use accumulated value of @cl (which we used to calculate level in the previous query) as a seed.

To do that, we can take the level returned by the descendancy tree query, and just add @cl to it.

The only problem it to determine when we should increment @cl and when we should add it to level.

We will just use a boolean field which will help us to tell the sets apart.

Here’s the query to do it:

SELECT  CONCAT(REPEAT('    ', level - 1), CAST(id AS CHAR)),
        parent,
        level
FROM    (
        SELECT  id, parent, IF(ancestry, @cl := @cl + 1, level + @cl) AS level
        FROM    (
                SELECT  TRUE AS ancestry, _id AS id, parent, level
                FROM    (
                        SELECT  @r AS _id,
                                (
                                SELECT  @r := parent
                                FROM    t_hierarchy
                                WHERE   id = _id
                                ) AS parent,
                                @l := @l + 1 AS level
                        FROM    (
                                SELECT  @r := 1218,
                                        @l := 0,
                                        @cl := 0
                                ) vars,
                                t_hierarchy h
                        WHERE   @r <> 0
                        ORDER BY
                                level DESC
                        ) qi
                UNION ALL
                SELECT  FALSE, hi.id, parent, level
                FROM    (
                        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
                        FROM    (
                                SELECT  @start_with := 1218,
                                        @id := @start_with,
                                        @level := 0
                                ) vars, t_hierarchy
                        WHERE   @id IS NOT NULL
                        ) ho
                JOIN    t_hierarchy hi
                ON      hi.id = ho.id
                ) q
        ) q2

, which is the answer to your question.

Hope that helps.

I’m always glad to answer the questions regarding database queries.

Ask me a question