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

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