EXPLAIN EXTENDED

How to create fast database queries

Archive for August 17th, 2009

Hierarchical queries in MySQL: VARCHAR keys

Comments enabled. I *really* need your comment

Answering questions asked on the site.

Basit asks:

I'm trying to implement a hierarchical query in MySQL using solutions you posted in your article.

How can I make the tree menu if the id is unique VARCHAR, like the ones used on youtube?

We will need to fix the query and the function just a little:

  • The function should return a VARCHAR
  • The @start_with and other variables should be initialized with VARCHARs
  • The initial condition for _id should be a minimal VARCHAR possible, i. e. an empty string

Let's create a sample table and check how it works:

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

CREATE TABLE t_key (
        id INT NOT NULL PRIMARY KEY,
        string_id VARCHAR(32) NOT NULL
) ENGINE=Memory;

CREATE TABLE t_hierarchy (
        id VARCHAR(32) NOT NULL PRIMARY KEY,
        parent VARCHAR(32) NOT NULL,
        data VARCHAR(50) NOT NULL,
        KEY ix_hierarchy_parent (parent)
) 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(20);
COMMIT;

INSERT
INTO    t_key
SELECT  id,
        (
        SELECT  GROUP_CONCAT(CHAR(65 + FLOOR(RAND(20090817) * 25)) SEPARATOR '')
        FROM    (
                SELECT  NULL
                FROM    filler
                LIMIT 8
                ) q
        )
FROM    filler;

INSERT
INTO    t_hierarchy
SELECT  ki.string_id, COALESCE(kp.string_id, '_'), CONCAT('Row ', f.id)
FROM    filler f
JOIN    t_key ki
ON      ki.id = f.id
LEFT JOIN
        t_key kp
ON      kp.id = f.id DIV 3;

Here's the function:

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

        SET _parent = @id;
        SET _id = '';

        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
$$

And here's the query:

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

treeitem parent level
FDBVDDGT _ 1
ENCYPEWC FDBVDDGT 2
AJXOXCQA ENCYPEWC 3
CLYLKREW ENCYPEWC 3
YFCUVVRX ENCYPEWC 3
JVDDGUJJ FDBVDDGT 2
ELQWNYGL JVDDGUJJ 3
KTRBGCQA JVDDGUJJ 3
SCGYDUQU JVDDGUJJ 3
VEHXSYRL FDBVDDGT 2
BIKCFVOH VEHXSYRL 3
HAGFGSUW VEHXSYRL 3
TCBYTARM VEHXSYRL 3
GVPJESCI _ 1
HCNHAEWW GVPJESCI 2
KNIDSGBM GVPJESCI 2
SJPBIMNF GVPJESCI 2
JETHGIVJ SJPBIMNF 3
OBPXSXJF SJPBIMNF 3
VPOXBLBW SJPBIMNF 3
20 rows fetched in 0.0006s (0.0180s)
id select_type table type possible_keys key key_len ref rows filtered Extra
1 PRIMARY <derived2> ALL 20 100.00
1 PRIMARY hi eq_ref PRIMARY PRIMARY 98 ho.id 1 100.00
2 DERIVED <derived3> system 1 100.00
2 DERIVED t_hierarchy index PRIMARY 98 20 100.00 Using where; Using index
3 DERIVED No tables used

Works just fine.

Written by Quassnoi

August 17th, 2009 at 11:00 pm

Posted in MySQL