MySQL - Adjacency List Model - Get Depth

Question

I have an organization table that has an id, a parent_id, and a name column. There are roughly 50k rows in this table. There is just one top level parent and the rest are all under that. In Oracle, I am able to easily retrieve the current depth of a particular organization with the level pseudocolumn:

SELECT id, parent_id, level, name
FROM organizations
START WITH parent_id = 1
CONNECT BY PRIOR id = parent_id

I am at a loss of what the proper way to do the above in MySQL is. I need to fetch the entire tree along with the node's depth in one query.

There are a plethora of questions on StackOverflow that have to do with this, but none of them seem to have a really good answer to it, mostly links to blogs with dubious solutions. Surely this is doable in some sort of straight-forward manner?

Unfortunately modifying the table in any way is not an option, so nested sets is not a possibility.

possible duplicate of [Using MySQL query to traverse rows to make a recursive tree](http://stackoverflow.com/questions/10646833/using-mysql-query-to-traverse-rows-to-make-a-recursive-tree) — RandomSeed, Jun 14 '13 at 14:46

score 4 · Answer 1 · edited May 23 '17 at 12:25

This is totally hilarious. I just picked up a +50 bounty on a similar question literally yesterday : Using MySQL query to traverse rows to make a recursive tree

I referenced how to do this with Stored Procedures in the DBA StackExchange (October 24, 2011)

I will post the same stored procedures along with the examples from my DBA StackExchange answer:

Code to Get the Parent for Any Given Node

DELIMITER $$
DROP FUNCTION IF EXISTS `junk`.`GetParentIDByID` $$
CREATE FUNCTION `junk`.`GetParentIDByID` (GivenID INT) RETURNS INT
DETERMINISTIC
BEGIN
    DECLARE rv INT;

    SELECT IFNULL(parent_id,-1) INTO rv FROM
    (SELECT parent_id FROM pctable WHERE id = GivenID) A;
    RETURN rv;
END $$
DELIMITER ;

Code to Get the Ancenstry for Any Given Node

DELIMITER $$
DROP FUNCTION IF EXISTS `junk`.`GetAncestry` $$
CREATE FUNCTION `junk`.`GetAncestry` (GivenID INT) RETURNS VARCHAR(1024)
DETERMINISTIC
BEGIN
    DECLARE rv VARCHAR(1024);
    DECLARE cm CHAR(1);
    DECLARE ch INT;

    SET rv = '';
    SET cm = '';
    SET ch = GivenID;
    WHILE ch > 0 DO
        SELECT IFNULL(parent_id,-1) INTO ch FROM
        (SELECT parent_id FROM pctable WHERE id = ch) A;
        IF ch > 0 THEN
            SET rv = CONCAT(rv,cm,ch);
            SET cm = ',';
        END IF;
    END WHILE;
    RETURN rv;
END $$
DELIMITER ;

Code to Get the Family Tree (or Descendants) for Any Given Node

DELIMITER $$

DROP FUNCTION IF EXISTS `junk`.`GetFamilyTree` $$
CREATE FUNCTION `junk`.`GetFamilyTree` (GivenID 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;

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

To demonstrate the execution of everything, here is the sample data

USE junk
DROP TABLE IF EXISTS pctable;
CREATE TABLE pctable
(
    id INT NOT NULL AUTO_INCREMENT,
    parent_id INT,
    PRIMARY KEY (id)
) ENGINE=MyISAM;
INSERT INTO pctable (parent_id) VALUES (0);
INSERT INTO pctable (parent_id) SELECT parent_id+1 FROM pctable;
INSERT INTO pctable (parent_id) SELECT parent_id+2 FROM pctable;
INSERT INTO pctable (parent_id) SELECT parent_id+3 FROM pctable;
INSERT INTO pctable (parent_id) SELECT parent_id+4 FROM pctable;
INSERT INTO pctable (parent_id) SELECT parent_id+5 FROM pctable;
SELECT * FROM pctable;

Here is the query to see all Parents, Ancestries, and Family Trees

SELECT
    id,parent_id,
    GetParentIDByID(id),
    GetAncestry(id),
    GetFamilyTree(id)
FROM pctable;

Give it a Try !!!

I get an error _ERROR 1292 (22007): Truncated incorrect DOUBLE value: '4,5'_ for getFamilyTree. Any suggestion as to why it might be happening!? Thank — idok, May 04 '13 at 00:27
Your GetAncestry Function is basically the perfect solution for the JSTree search function when using LazyLoad. Thanks mate! — Broco, Sep 02 '16 at 10:04

score 2 · Answer 2 · edited May 23 '17 at 12:02

There is no recursion in SQL without CTEs/Subquery Factoring, so there is specifically and absolutely no way to do this with arbitrary level depths in "Pure SQL," especially as implemented in MySQL. See How to transform a MSSQL CTE query to MySQL?

That is why all of the answers you find are hacks, to get around this very specific limitation of the engine. You can try this solution, if you still need one: Generating Depth based tree from Hierarchical Data in MySQL (no CTEs). (Of course, the limitation means that the queries aren't weird to parse, in the LangSec sense, which allows all sorts of beneficial parsing, and eliminates some security concerns, but helps you not at all.)

A bunch of Lefts Joins that exhaust the hierarchy are all you have left, sorry to dissapoint and use a bad pun.

In 2019, MySQL and MariaDB support CTEs – symcbean Jan 06 '20 at 22:09 — symcbean, Jan 06 '20 at 22:09

score 0 · Answer 3 · answered Oct 15 '20 at 08:37

@idok, the function will return "Truncated incorrect DOUBLE value" error if you have same parent id for more than one child, i have found the following fix from dba and it was given by Sivakumar Natarayan

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

Micromega · Answer 4 · 2012-06-15T17:39:49.107

-1

Mysql doesn't support recursive sql. When you have only 1 dimension then you can use a Left join with itself on the parent_id = id.

edited Jun 15 '12 at 17:39

answered Jun 15 '12 at 17:18

Micromega

12,486
7
35
72

MySQL - Adjacency List Model - Get Depth

4 Answers4

Linked