hierarchyMySQL
I'm new to MySQL. The GetFamilyTree(id) function that Rolando suggested in the Find highest level of a hierarchical field: with vs without CTEs question was great but when the id is greater than 999 it hangs.
Is there a solution that works with larger ids?
You definitely have to script this via MySQL Stored Procedure Language
Here is a Stored Function called GetParentIDByIDto Retrieve a ParentID given an ID to Search For
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 ;
Here is a Stored Function called GetAncestryto Retrieve a List of ParentIDs starting from the First Generation all the up the hierarchy given an ID to start with:
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 ;
Here is something to generate 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 what it generates:
mysql> USE junk
Database changed
mysql> DROP TABLE IF EXISTS pctable;
Query OK, 0 rows affected (0.00 sec)
mysql> CREATE TABLE pctable
-> (
-> id INT NOT NULL AUTO_INCREMENT,
-> parent_id INT,
-> PRIMARY KEY (id)
-> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.05 sec)
mysql> INSERT INTO pctable (parent_id) VALUES (0);
Query OK, 1 row affected (0.00 sec)
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+1 FROM pctable;
Query OK, 1 row affected (0.00 sec)
Records: 1 Duplicates: 0 Warnings: 0
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+2 FROM pctable;
Query OK, 2 rows affected (0.00 sec)
Records: 2 Duplicates: 0 Warnings: 0
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+3 FROM pctable;
Query OK, 4 rows affected (0.00 sec)
Records: 4 Duplicates: 0 Warnings: 0
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+4 FROM pctable;
Query OK, 8 rows affected (0.01 sec)
Records: 8 Duplicates: 0 Warnings: 0
mysql> INSERT INTO pctable (parent_id) SELECT parent_id+5 FROM pctable;
Query OK, 16 rows affected (0.00 sec)
Records: 16 Duplicates: 0 Warnings: 0
mysql> SELECT * FROM pctable;
+----+-----------+
| id | parent_id |
+----+-----------+
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 3 |
| 6 | 4 |
| 7 | 5 |
| 8 | 6 |
| 9 | 4 |
| 10 | 5 |
| 11 | 6 |
| 12 | 7 |
| 13 | 7 |
| 14 | 8 |
| 15 | 9 |
| 16 | 10 |
| 17 | 5 |
| 18 | 6 |
| 19 | 7 |
| 20 | 8 |
| 21 | 8 |
| 22 | 9 |
| 23 | 10 |
| 24 | 11 |
| 25 | 9 |
| 26 | 10 |
| 27 | 11 |
| 28 | 12 |
| 29 | 12 |
| 30 | 13 |
| 31 | 14 |
| 32 | 15 |
+----+-----------+
32 rows in set (0.00 sec)
Here are what the functions generate for each value:
mysql> SELECT id,GetParentIDByID(id),GetAncestry(id) FROM pctable;
+----+---------------------+-----------------+
| id | GetParentIDByID(id) | GetAncestry(id) |
+----+---------------------+-----------------+
| 1 | 0 | |
| 2 | 1 | 1 |
| 3 | 2 | 2,1 |
| 4 | 3 | 3,2,1 |
| 5 | 3 | 3,2,1 |
| 6 | 4 | 4,3,2,1 |
| 7 | 5 | 5,3,2,1 |
| 8 | 6 | 6,4,3,2,1 |
| 9 | 4 | 4,3,2,1 |
| 10 | 5 | 5,3,2,1 |
| 11 | 6 | 6,4,3,2,1 |
| 12 | 7 | 7,5,3,2,1 |
| 13 | 7 | 7,5,3,2,1 |
| 14 | 8 | 8,6,4,3,2,1 |
| 15 | 9 | 9,4,3,2,1 |
| 16 | 10 | 10,5,3,2,1 |
| 17 | 5 | 5,3,2,1 |
| 18 | 6 | 6,4,3,2,1 |
| 19 | 7 | 7,5,3,2,1 |
| 20 | 8 | 8,6,4,3,2,1 |
| 21 | 8 | 8,6,4,3,2,1 |
| 22 | 9 | 9,4,3,2,1 |
| 23 | 10 | 10,5,3,2,1 |
| 24 | 11 | 11,6,4,3,2,1 |
| 25 | 9 | 9,4,3,2,1 |
| 26 | 10 | 10,5,3,2,1 |
| 27 | 11 | 11,6,4,3,2,1 |
| 28 | 12 | 12,7,5,3,2,1 |
| 29 | 12 | 12,7,5,3,2,1 |
| 30 | 13 | 13,7,5,3,2,1 |
| 31 | 14 | 14,8,6,4,3,2,1 |
| 32 | 15 | 15,9,4,3,2,1 |
+----+---------------------+-----------------+
32 rows in set (0.02 sec)
MORAL OF THE STORY : Recursive data retrieval must be scripted in MySQL
Here is the reverse of GetAncestry. I call it GetFamilyTree.
Here is the algorithm:
I believe from my Data Structures and Algorithms classes in College, this is called something like preorder/prefix tree traversal.
Here is the code:
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 $$
Here is what each row produces
mysql> SELECT id,parent_id,GetParentIDByID(id),GetAncestry(id),GetFamilyTree(id) FROM pctable;
+----+-----------+---------------------+-----------------+--------------------------------------------------------------------------------------+
| id | parent_id | GetParentIDByID(id) | GetAncestry(id) | GetFamilyTree(id) |
+----+-----------+---------------------+-----------------+--------------------------------------------------------------------------------------+
| 1 | 0 | 0 | | 2,3,4,5,6,9,7,10,17,8,11,18,15,22,25,12,13,19,16,23,26,14,20,21,24,27,32,28,29,30,31 |
| 2 | 1 | 1 | 1 | 3,4,5,6,9,7,10,17,8,11,18,15,22,25,12,13,19,16,23,26,14,20,21,24,27,32,28,29,30,31 |
| 3 | 2 | 2 | 2,1 | 4,5,6,9,7,10,17,8,11,18,15,22,25,12,13,19,16,23,26,14,20,21,24,27,32,28,29,30,31 |
| 4 | 3 | 3 | 3,2,1 | 6,9,8,11,18,15,22,25,14,20,21,24,27,32,31 |
| 5 | 3 | 3 | 3,2,1 | 7,10,17,12,13,19,16,23,26,28,29,30 |
| 6 | 4 | 4 | 4,3,2,1 | 8,11,18,14,20,21,24,27,31 |
| 7 | 5 | 5 | 5,3,2,1 | 12,13,19,28,29,30 |
| 8 | 6 | 6 | 6,4,3,2,1 | 14,20,21,31 |
| 9 | 4 | 4 | 4,3,2,1 | 15,22,25,32 |
| 10 | 5 | 5 | 5,3,2,1 | 16,23,26 |
| 11 | 6 | 6 | 6,4,3,2,1 | 24,27 |
| 12 | 7 | 7 | 7,5,3,2,1 | 28,29 |
| 13 | 7 | 7 | 7,5,3,2,1 | 30 |
| 14 | 8 | 8 | 8,6,4,3,2,1 | 31 |
| 15 | 9 | 9 | 9,4,3,2,1 | 32 |
| 16 | 10 | 10 | 10,5,3,2,1 | |
| 17 | 5 | 5 | 5,3,2,1 | |
| 18 | 6 | 6 | 6,4,3,2,1 | |
| 19 | 7 | 7 | 7,5,3,2,1 | |
| 20 | 8 | 8 | 8,6,4,3,2,1 | |
| 21 | 8 | 8 | 8,6,4,3,2,1 | |
| 22 | 9 | 9 | 9,4,3,2,1 | |
| 23 | 10 | 10 | 10,5,3,2,1 | |
| 24 | 11 | 11 | 11,6,4,3,2,1 | |
| 25 | 9 | 9 | 9,4,3,2,1 | |
| 26 | 10 | 10 | 10,5,3,2,1 | |
| 27 | 11 | 11 | 11,6,4,3,2,1 | |
| 28 | 12 | 12 | 12,7,5,3,2,1 | |
| 29 | 12 | 12 | 12,7,5,3,2,1 | |
| 30 | 13 | 13 | 13,7,5,3,2,1 | |
| 31 | 14 | 14 | 14,8,6,4,3,2,1 | |
| 32 | 15 | 15 | 15,9,4,3,2,1 | |
+----+-----------+---------------------+-----------------+--------------------------------------------------------------------------------------+
32 rows in set (0.04 sec)
This algorithm works cleanly provided there are no cyclic paths. If there exists any cyclic paths, you would have to add a 'visited' column to the table.
Once you add visited column, here is the algorithm blocking cyclic relationships:
I created a new table called observations and populated your sample data. I changed the stored procedures to use observations instead of pctable. Here is your output:
mysql> CREATE TABLE observations LIKE pctable;
Query OK, 0 rows affected (0.04 sec)
mysql> INSERT INTO observations VALUES (1,3), (2,5), (3,0), (4,10),(5,0),(6,1),(7,5),(8,10),(9,10),(10,3);
Query OK, 10 rows affected (0.00 sec)
Records: 10 Duplicates: 0 Warnings: 0
mysql> SELECT * FROM observations;
+----+-----------+
| id | parent_id |
+----+-----------+
| 1 | 3 |
| 2 | 5 |
| 3 | 0 |
| 4 | 10 |
| 5 | 0 |
| 6 | 1 |
| 7 | 5 |
| 8 | 10 |
| 9 | 10 |
| 10 | 3 |
+----+-----------+
10 rows in set (0.00 sec)
mysql> SELECT id,parent_id,GetParentIDByID(id),GetAncestry(id),GetFamilyTree(id) FROM observations;
+----+-----------+---------------------+-----------------+-------------------+
| id | parent_id | GetParentIDByID(id) | GetAncestry(id) | GetFamilyTree(id) |
+----+-----------+---------------------+-----------------+-------------------+
| 1 | 3 | 3 | | 6 |
| 2 | 5 | 5 | 5 | |
| 3 | 0 | 0 | | 1,10,6,4,8,9 |
| 4 | 10 | 10 | 10,3 | |
| 5 | 0 | 0 | | 2,7 |
| 6 | 1 | 1 | 1 | |
| 7 | 5 | 5 | 5 | |
| 8 | 10 | 10 | 10,3 | |
| 9 | 10 | 10 | 10,3 | |
| 10 | 3 | 3 | 3 | 4,8,9 |
+----+-----------+---------------------+-----------------+-------------------+
10 rows in set (0.01 sec)
I changed the code for GetAncestry. There was WHILE ch > 1 it should be WHILE ch > 0
mysql> SELECT id,parent_id,GetParentIDByID(id),GetAncestry(id),GetFamilyTree(id) FROM observations;
+----+-----------+---------------------+-----------------+-------------------+
| id | parent_id | GetParentIDByID(id) | GetAncestry(id) | GetFamilyTree(id) |
+----+-----------+---------------------+-----------------+-------------------+
| 1 | 3 | 3 | 3 | 6 |
| 2 | 5 | 5 | 5 | |
| 3 | 0 | 0 | | 1,10,6,4,8,9 |
| 4 | 10 | 10 | 10,3 | |
| 5 | 0 | 0 | | 2,7 |
| 6 | 1 | 1 | 1,3 | |
| 7 | 5 | 5 | 5 | |
| 8 | 10 | 10 | 10,3 | |
| 9 | 10 | 10 | 10,3 | |
| 10 | 3 | 3 | 3 | 4,8,9 |
+----+-----------+---------------------+-----------------+-------------------+
10 rows in set (0.01 sec)
Try it now !!!
This works, provided the combination groupid - startdate is unique:
SELECT s1.groupid, s1.id FROM schedule s1, (
SELECT groupid, MAX(startdate) startdate
FROM schedule
WHERE @date >= startdate
GROUP BY groupid
) s2
WHERE s1.groupid = s2.groupid
AND s1.startdate = s2.startdate
Best Answer
There are several things you can do
THING #1
Expand all
VARCHAR(1024)toVARCHAR(10240)in all Stored Procedures. This will accommodate longer Family Tree Listings. This is vital becausequeue_childrencan grow longer and longer if you have a lopsided tree structure. It also possible that when queue_children was 1024 in length and did not delimit properly, it probably went into some infinite loop trying to terminate properly and never reached the condition when theLENGTH(queue_children)would be 0.THING #2
GROUP_CONCAT()'s maximum length is limited by group_concat_max_len (default is 1024). Try expanding group_concat_max_len to something ridiculously large (5000000000).
THING #3
Increase your thread_stack, perhaps 512K or 1M. This is needed for Stored Procedures with either recursive operations or, in this case, longer local variables to make room for.