EXPLAIN EXTENDED

Answering questions asked on the site.

James asks:

Your series on hierarchical queries in MySQL is tremendous! I’m using it to create a series of threaded conversations.

I’m wondering if there is a way to paginate these results.

Specifically, let’s say I want to limit the conversations to return 10 root nodes (parent=0) and all of their children in a query.

I can’t just limit the final query, because that will clip off children. I’ve tried to add LIMITs to your stored functions, but I’m not getting the magic just right.

How would you go about doing this?

A quick reminder: MySQL does not support recursion (either CONNECT BY style or recursive CTE style), so using an adjacency list model is a somewhat complicated task.

However, it is still possible. The main idea is storing the recursion state in a session variable and call a user-defined function repeatedly to iterate over the tree, thus emulating recursion. The article mentioned in the question shows how to do that.

Normally, reading and assigning session variables in the same query is discouraged in MySQL, since the order of evaluation is not guaranteed. However, in the case we only use the table as a dummy recordset and no values of the records are actually used in the function, so the actual values returned by the function are completely defined by the function itself. The table is only used to ensure that the function is called enough times, and to present its results in form of a native resultset (which can be returned or joined with).

To do something with the logic of the function (like, imposing a limit on the parent nodes without doing the same on the child nodes), we, therefore, should tweak the function code, not the query that calls the functions. The only thing that matters in such a query is the number of records returned and we don’t know it in design time.

Limiting the parent nodes is quite simple: we just use another session variable to track the number of parent branches yet to be returned and stop processing as soon as the limit is hit, that is the variable becomes zero.

Let’s create a sample table and see how to do this:

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,
        root INT NOT NULL,
        PRIMARY KEY (id),
        KEY ix_hierarchy_parent (parent, id),
        KEY ix_hierarchy_root (root)
) 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
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(100000);
COMMIT;

INSERT
INTO    t_hierarchy
SELECT  id,
        CASE (id - 1) % 8
        WHEN 0 THEN 0
        ELSE FLOOR((((id - 1) % 8) + 1) / 2) + ((id - 1) div 8) * 8
        END,
        ((id - 1) div 8) * 8 + 1
FROM    filler;

There are 100,000 hierarchical records in multiple trees (8 records in each tree).

To limit the number of trees returned, we create the function similar to the one created in the earlier posts and add a little condition that would decrease the session variable, @parent_limit, each time a parent entry is returned. When this variable hits zero, it’s a signal to stop processing the records:

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;
                        IF _parent = @start_with AND @parent_limit > 0 THEN
                                SET @parent_limit = @parent_limit - 1;
                        END IF;
                        IF @parent_limit = 0 THEN
                                SET @id = NULL;
                        END IF;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, parent
                INTO    _id, _parent
                FROM    t_hierarchy
                WHERE   id = _parent;
        END LOOP;
END;

Let’s check it:

SELECT  CONCAT(REPEAT('    ', level - 1), CAST(hi.id AS CHAR)) AS treeitem, parent, level, lmt
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level, @parent_limit as lmt
        FROM    (
                SELECT  @start_with := 0,
                        @parent_limit := 4,
                        @id := @start_with,
                        @level := 0
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    t_hierarchy hi
ON      hi.id = ho.id

select concat(repeat('    ',(`ho`.`level` - 1)),cast(`20100418_limit`.`hi`.`id` as char charset latin1)) AS `treeitem`,`20100418_limit`.`hi`.`parent` AS `parent`,`ho`.`level` AS `level`,`ho`.`lmt` AS `lmt` from (select `hierarchy_connect_by_parent_eq_prior_id`(`20100418_limit`.`t_hierarchy`.`id`) AS `id`,(@level) AS `level`,(@parent_limit) AS `lmt` from (select (@start_with:=0) AS `@start_with := 0`,(@parent_limit:=4) AS `@parent_limit := 4`,(@id:=(@start_with)) AS `@id := @start_with`,(@level:=0) AS `@level := 0`) `vars` join `20100418_limit`.`t_hierarchy` where ((@id) is not null)) `ho` join `20100418_limit`.`t_hierarchy` `hi` where (`20100418_limit`.`hi`.`id` = `ho`.`id`)

The first 3 branches in a proper hierarchy, almost instantly. Note that we need set @parent_limit to 4, i. e. one greater than the value we need.

Note that it is possible to achieve the similar behavior without using any recursive functions at all.

On most forums the filtering is performed on the topic starters, so it’s often a good idea to store the id of the topic starter along with each reply. In the sample table a did that as well.

With this, the filtering required becomes very simple:

SELECT  h.*
FROM    (
        SELECT  id
        FROM    t_hierarchy
        WHERE   parent = 0
        ORDER BY
                id
        LIMIT 3
        ) q
JOIN    t_hierarchy h
ON      h.root = q.id

select `20100418_limit`.`h`.`id` AS `id`,`20100418_limit`.`h`.`parent` AS `parent`,`20100418_limit`.`h`.`root` AS `root` from (select `20100418_limit`.`t_hierarchy`.`id` AS `id` from `20100418_limit`.`t_hierarchy` where (`20100418_limit`.`t_hierarchy`.`parent` = 0) order by `20100418_limit`.`t_hierarchy`.`id` limit 3) `q` join `20100418_limit`.`t_hierarchy` `h` where (`20100418_limit`.`h`.`root` = `q`.`id`)

This solution (that had been used on numerous forum engines for ages) is more efficient, since no function calls are involved, and more simple too.

However, it does not preserve the hierarchical order and does not allow sorting on anything but the topic starter, so if you need anything of these, the recursive function is still a way to go.

Hope that helps.

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

Ask me a question