MySQL – Implementing Parent-Level Count in Binary Search Tree

functionsMySQLtree

Based on this question, have any way to implement a parent level count?

Find highest level of a hierarchical field: with vs without CTEs

Example table:

+----+-----------+
| id | parent_id |
+----+-----------+
|  1 |         0 |
|  2 |         1 |
|  3 |         1 |
|  4 |         2 |
|  5 |         2 |
|  6 |         3 |
|  7 |         3 |
|  8 |         5 |
|  9 |         5 |
| 10 |         7 |
+----+-----------+

Function:

DELIMITER $$

DROP FUNCTION IF EXISTS `junk`.`GetFamilyTree` $$
CREATE FUNCTION `junk`.`GetFamilyTree` (GivenID INT, Count INT) RETURNS varchar(1024) CHARSET latin1
DETERMINISTIC
BEGIN

DECLARE rv,q,queue,queue_children VARCHAR(1024);
DECLARE queue_length,front_id,pos INT;

SET rv = '';
SET queue = GivenID;
SET queue_length = 1;
SET count_limit = Count;


WHILE queue_length > 0 && count_limit > 0 DO
    SET front_id = FORMAT(queue,0);
    IF queue_length = 1 THEN
        SET queue = '';
    ELSE
        SET pos = LOCATE(',',queue) + 1;
        SET q = SUBSTR(queue,pos);
        SET queue = q;
    END IF;
    SET queue_length = queue_length - 1;

    SELECT IFNULL(qc,'') INTO queue_children
    FROM (SELECT GROUP_CONCAT(id) qc
    FROM pctable WHERE parent_id = front_id) A;

    IF LENGTH(queue_children) = 0 THEN
        IF LENGTH(queue) = 0 THEN
            SET queue_length = 0;
        END IF;
    ELSE
        IF LENGTH(rv) = 0 THEN
            SET rv = queue_children;
        ELSE
            SET rv = CONCAT(rv,',',queue_children);
        END IF;
        IF LENGTH(queue) = 0 THEN
            SET queue = queue_children;
        ELSE
            SET queue = CONCAT(queue,',',queue_children);
        END IF;
        SET queue_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;
    END IF;
END WHILE;

RETURN rv;

END $$

I need implement a count on that function to limit iterate based on parameter passed on query.

SELECT id,parent_id, GetFamilyTree(1, 3) FROM pctable;

Detail: first param is id of desired family tree
secund param is a level depth of descendants

Example result of example table:

+----+-----------+
| id | parent_id |
+----+-----------+
|   1|        0  |
|   2|        1  |
|   3|        1  |
|   4|        2  |
|   5|        2  |
|   6|        3  |
|   7|        3  |
+----+-----------+

It is possible?

In this case, the count not working as well…its counting every tree item, not every tree level.

Best Answer

If you look at the GetFamilyTree code, there is nothing monitoring the tree height or any particular level.

To compensate, I have a revised version of this code

DELIMITER $$

DROP FUNCTION IF EXISTS `junk`.`GetFamilyTree` $$
CREATE FUNCTION `junk`.`GetFamilyTree` (GivenID INT,LevelLimit INT)
RETURNS varchar(1024) CHARSET latin1
DETERMINISTIC
BEGIN
    DECLARE rv,q,queue,queue_children,front_rc,level_part VARCHAR(1024);
    DECLARE queue_length,front_id,front_ht,pos,curr_level INT;

    SET rv = '';
    SET queue = CONCAT(GivenID,':0');
    SET queue_length = 1;

    WHILE queue_length > 0 DO
        SET front_id = FORMAT(queue,0);
        IF queue_length = 1 THEN
            SET front_rc = queue;
            SET queue = '';
            SET pos = LOCATE(':',front_rc);
        ELSE
            SET pos = LOCATE(',',queue);
            SET front_rc = LEFT(queue,pos - 1);
            SET q = SUBSTR(queue,pos + 1);
            SET queue = q;
            SET pos = LOCATE(':',front_rc);
        END IF;
        SET front_id = LEFT(front_rc,pos - 1);
        SET front_ht = SUBSTR(front_rc,pos + 1);
        SET queue_length = queue_length - 1;

        SELECT IFNULL(qc,'') INTO queue_children
        FROM (SELECT GROUP_CONCAT(CONCAT(id,':',front_ht+1)) qc
        FROM pctable WHERE parent_id = front_id) A;

        IF LENGTH(queue_children) = 0 THEN
            IF LENGTH(queue) = 0 THEN
                SET queue_length = 0;
            END IF;
        ELSE
            IF LENGTH(rv) = 0 THEN
                IF front_ht < LevelLimit THEN
                    SET rv = queue_children;
                END IF;
            ELSE
                IF front_ht < LevelLimit THEN
                    SET rv = CONCAT(rv,',',queue_children);
                END IF;
            END IF;
            IF LENGTH(queue) = 0 THEN
                SET queue = queue_children;
            ELSE
                SET queue = CONCAT(queue,',',queue_children);
            END IF;
            SET queue_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;
        END IF;
    END WHILE;

    #
    # Strip away level parts of the output
    #
    IF LENGTH(rv) > 0 THEN
        SET curr_level = 1;
        WHILE curr_level <= LevelLimit DO
            SET level_part = CONCAT(':',curr_level);
            SET rv = REPLACE(rv,level_part,'');
            SET curr_level = curr_level + 1;
        END WHILE;
    END IF;

    RETURN rv;
END $$

DELIMITER ;

This is how I changed it: For each id in the queue, I introduce a height.

Each member of the list will look like this:

id:height,id:height,id:height, ... ,id:height

I place a limit on when to concatenate by adding IF front_ht < LevelLimit THEN

When the list is compiled, I then taken the return value rv and remove all colons (:) and the number behind each colon. What's left is a comma-separated list of IDs within the height range set by LevelLimit. If you want the height to be included in the output, remove the Strip away level parts of the output code at the bottom of the Stored Procedure.

Give it a Try !!!

UPDATE 2014-11-29 16:05 EST

It is important to note that you need to make GROUP_CONCAT have enough space to collect a long list of info. Please run this in mysql:

SET GLOBAL group_concat_max_len = 1048576;
SET group_concat_max_len = 1048576;

Then, add this to my.cnf

[mysqld]
group_concat_max_len =1048576;
Related Question