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