EXPLAIN EXTENDED

Continuing on the theme of hierarchical queries in MySQL:

• Hierarchical queries in MySQL
• Hierarchical queries in MySQL: adding level
• Hierarchical queries in MySQL: adding ancestry chains.
• Hierarchical queries in MySQL: finding leaves
• Hierarchical queries in MySQL: finding loops
• Hierarchical data in MySQL: parents and children in one query

Assume we have a table with hierarchical structure like this:

We have two trees here: one starting from 1, another one starting from 2.

The problem is: given any item, we should identify the whole tree this item belongs to, and return the whole tree in the hierarchical order.

This also can be easily done using hierarchical queries in MySQL.

In this article: Hierarchical queries in MySQL I shown how to implement a function that returnes tree items in correct order, being called sequentially.

This function is reentrable and keeps its state in session variables, one of which, @start_with, defines the parent element for the tree we want to build.

We have two problems here:

1. Given an item, define a root of the tree it belongs to
2. Build a whole tree, starting from the root

The first problem can be solved by iterating the linked list backwards, starting from the variable given as an input.

This article:

• Sorting lists

describes how to do it in great detail, that's why I'll just put a query here.

Let's create the table described above:

Table creation details

CREATE TABLE filler (
id INT NOT NULL PRIMARY KEY AUTO_INCREMENT
) ENGINE=Memory;

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_filler(cnt INT)
BEGIN
DECLARE _cnt INT;
SET _cnt = 1;
WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

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_filler(18);
COMMIT;

INSERT
INTO    t_hierarchy (id, parent)
SELECT  id, id DIV 3
FROM    filler;

To find the root, for, say, 10, we need to rewind the tree, treating is a a linked list (id to parent)

SELECT  CONCAT(REPEAT('    ', level  - 1), CAST(_id AS CHAR)) 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 := 10,
@l := 0
) vars,
t_hierarchy h
WHERE   @r <> 0
) q

We traced the ancestry chain up to the very first item in the tree, which has no parents. This is, we identified the tree.

To get the whole tree. we just need to assign id retrieved in the last row of the query above, to the session variable @start_with, and call the tree building function repeatedly in a rowsource.

This can be easily done by applying ORDER BY level DESC LIMIT 1 to the query above.

The only problem we still have is that this function does not return @start_with itself, only its children and deeper. This of course can be easily solved by prepending the rowset with the @start_with itself.

Here's the final query:

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

, which returns the whole tree of 1, given 10 as an input, since 1 is the ultimate ancestor of 10.

If we provide, say, 18 as a input, we will get the following:

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

, since 18 is the member of other tree, having 2 as a root.