Repair nested set tree

repair_nested_set_tree.sql

DROP PROCEDURE IF EXISTS tree_recover;
DELIMITER //
CREATE 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.
CREATE TABLE `tmp_tree` (
`id` CHAR(36) NOT NULL DEFAULT '',
`parent_id` CHAR(36) DEFAULT NULL,
`lft` INT(11) UNSIGNED DEFAULT NULL,
`rgt` INT(11) UNSIGNED DEFAULT NULL,
PRIMARY KEY (`id`),
INDEX USING HASH (`parent_id`),
INDEX USING HASH (`lft`),
INDEX USING HASH (`rgt`)
)
ENGINE = MEMORY
SELECT
`id`,
`parent_id`,
`lft`,
`rgt`
FROM `departments`;

# 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_id` IS NULL AND `lft` IS NULL AND `rgt` IS NULL
LIMIT 1) DO

UPDATE `tmp_tree`
SET `lft` = startId,
`rgt` = startId + 1
WHERE `parent_id` IS NULL
AND `lft` IS NULL
AND `rgt` IS NULL
LIMIT 1;

SET startId = startId + 2;

END WHILE;

# Switching the indexes for the lft/rght 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_id` = `parents`.`id`
WHERE `tmp_tree`.`lft` IS NULL
AND `parents`.`lft` IS NOT NULL
LIMIT 1;

# Finding the element's parent.
SELECT `parent_id`
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 rght 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 `departments`, `tmp_tree`
SET `departments`.`lft` = `tmp_tree`.`lft`,
`departments`.`rgt` = `tmp_tree`.`rgt`
WHERE `departments`.`id` = `tmp_tree`.`id`;

COMMIT;

DROP TABLE `tmp_tree`;

END//

DELIMITER ;

CALL tree_recover();