Stored Procedure to update an adjacency Model to Nested Sets Model

Question

If you don't already know, these two models are the most common ways to store a tree in a relational DB.

Adjacency Model:

+-------------+----------------------+--------+
| category_id | name | parent |
+-------------+----------------------+--------+
| 1 | ELECTRONICS | NULL |
| 2 | TELEVISIONS | 1 |
| 3 | TUBE | 2 |
| 4 | LCD | 2 |
| 5 | PLASMA | 2 |
| 6 | PORTABLE ELECTRONICS | 1 |
| 7 | MP3 PLAYERS | 6 |
| 8 | FLASH | 7 |
| 9 | CD PLAYERS | 6 |
| 10 | 2 WAY RADIOS | 6 |
+-------------+----------------------+--------+

Nested Sets:

+-------------+----------------------+-----+-----+
| category_id | name | lft | rgt |
+-------------+----------------------+-----+-----+
| 1 | ELECTRONICS | 1 | 20 |
| 2 | TELEVISIONS | 2 | 9 |
| 3 | TUBE | 3 | 4 |
| 4 | LCD | 5 | 6 |
| 5 | PLASMA | 7 | 8 |
| 6 | PORTABLE ELECTRONICS | 10 | 19 |
| 7 | MP3 PLAYERS | 11 | 14 |
| 8 | FLASH | 12 | 13 |
| 9 | CD PLAYERS | 15 | 16 |
| 10 | 2 WAY RADIOS | 17 | 18 |
+-------------+----------------------+-----+-----+

You can also take a look here

I have a Table in adjacency Model in MySQL and I have decided to convert it to the nested sets model. I need a code to fill the LEFT and RIGHT columns based on the parent column to mix them both and reach to something like this

What I need:

+-------------+----------------------+--------+-----+-----+
| category_id | name | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
| 1 | ELECTRONICS | NULL | 1 | 20 |
| 2 | TELEVISIONS | 1 | 2 | 9 |
| 3 | TUBE | 2 | 3 | 4 |
| 4 | LCD | 2 | 5 | 6 |
| 5 | PLASMA | 2 | 7 | 8 |
| 6 | PORTABLE ELECTRONICS | 1 | 10 | 19 |
| 7 | MP3 PLAYERS | 6 | 11 | 14 |
| 8 | FLASH | 7 | 12 | 13 |
| 9 | CD PLAYERS | 6 | 15 | 16 |
| 10 | 2 WAY RADIOS | 6 | 17 | 18 |
+-------------+----------------------+--------+-----+-----+

• Ammy T: You might want to check this one stackoverflow.com/questions/3623645/…
• icc97: Note: Nested sets are sometimes called Modified Pre-order Tree Traversal (MPTT), although I do much prefer nested sets :)

Answer 1

Finally I found the solution but it needed some optimization and tweaks to work with my case and I added sorting with ID to get the tree sorted too, the answer is mainly got from here so credit goes to @deceze,

CREATE DEFINER=`root`@`localhost` PROCEDURE `tree_recover`()
 MODIFIES SQL DATA
BEGIN
 DECLARE currentId, currentParentId CHAR(36);
 DECLARE currentLeft INT;
 DECLARE startId INT DEFAULT 1;
 # Determines the max size for MEMORY tables.
 SET max_heap_table_size = 1024 * 1024 * 512;
 START TRANSACTION;
 # Temporary MEMORY table to do all the heavy lifting in,
 # otherwise performance is simply abysmal.
 DROP TABLE IF EXISTS `tmp_tree`;
 CREATE TABLE `tmp_tree` (
 `id` bigint(36) NOT NULL DEFAULT '0',
 `parent` char(36) DEFAULT NULL,
 `lft` int(11) unsigned DEFAULT NULL,
 `rgt` int(11) unsigned DEFAULT NULL,
 PRIMARY KEY (`id`),
 INDEX USING HASH (`parent`),
 INDEX USING HASH (`lft`),
 INDEX USING HASH (`rgt`)
 ) ENGINE = MEMORY
 SELECT `id`,
 `parent`,
 `lft`,
 `rgt`
 FROM `tree`;
 # Leveling the playing field.
 UPDATE `tmp_tree`
 SET `lft` = NULL,
 `rgt` = NULL;
 # Establishing starting numbers for all root elements.
 WHILE EXISTS (SELECT * FROM `tmp_tree` WHERE `parent` = 0 AND `lft` IS NULL AND `rgt` IS NULL LIMIT 1) DO
 UPDATE `tmp_tree`
 SET `lft` = startId,
 `rgt` = startId + 1
 WHERE `parent` = 0
 AND `lft` IS NULL
 AND `rgt` IS NULL
 ORDER BY `id` ASC
 LIMIT 1;
 SET startId = startId + 2;
 END WHILE;
 # Switching the indexes for the lft/rgt columns to B-Trees to speed up the next section, which uses range queries.
 DROP INDEX `lft` ON `tmp_tree`;
 DROP INDEX `rgt` ON `tmp_tree`;
 CREATE INDEX `lft` USING BTREE ON `tmp_tree` (`lft`);
 CREATE INDEX `rgt` USING BTREE ON `tmp_tree` (`rgt`);
 # Numbering all child elements
 WHILE EXISTS (SELECT * FROM `tmp_tree` WHERE `lft` IS NULL LIMIT 1) DO
 # Picking an unprocessed element which has a processed parent.
 SELECT `tmp_tree`.`id`
 INTO currentId
 FROM `tmp_tree`
 INNER JOIN `tmp_tree` AS `parents`
 ON `tmp_tree`.`parent` = `parents`.`id`
 WHERE `tmp_tree`.`lft` IS NULL
 AND `parents`.`lft` IS NOT NULL
 ORDER BY `tmp_tree`.`id` DESC 
 LIMIT 1;
 # Finding the element's parent.
 SELECT `parent`
 INTO currentParentId
 FROM `tmp_tree`
 WHERE `id` = currentId;
 # Finding the parent's lft value.
 SELECT `lft`
 INTO currentLeft
 FROM `tmp_tree`
 WHERE `id` = currentParentId;
 # Shifting all elements to the right of the current element 2 to the right.
 UPDATE `tmp_tree`
 SET `rgt` = `rgt` + 2
 WHERE `rgt` > currentLeft;
 UPDATE `tmp_tree`
 SET `lft` = `lft` + 2
 WHERE `lft` > currentLeft;
 # Setting lft and rgt values for current element.
 UPDATE `tmp_tree`
 SET `lft` = currentLeft + 1,
 `rgt` = currentLeft + 2
 WHERE `id` = currentId;
 END WHILE;
 # Writing calculated values back to physical table.
 UPDATE `tree`, `tmp_tree`
 SET `tree`.`lft` = `tmp_tree`.`lft`,
 `tree`.`rgt` = `tmp_tree`.`rgt`
 WHERE `tree`.`id` = `tmp_tree`.`id`;
 COMMIT;
 DROP TABLE `tmp_tree`;
END

• azerafati: note that I'm also using 0 instead of null for parent nodes!