MySQL Stored Procedure – Update Adjacency Model to Nested Sets

hierarchyMySQLstored-procedures

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

Best Answer

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

Related Solutions

Mysql – Stored procedure to handle empty sets

If you are using MySQL 5.5 or 5.6, you can accomplish this with SIGNAL.

Simplified example, inside the body of the procedure...

IF NOT EXISTS (SELECT * FROM users WHERE username = input_username AND password = input_password) THEN
  SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = 'authentication failed.';
ELSE
  -- normal code to select and return the username other info to the caller, etc.
END IF;

This will throw an exception:

ERROR 1644 (45000): authentication failed.

If you wanted to be more specific, you'd need to declare a variable to use a the MESSAGE_TEXT and populate it accordingly before calling SIGNAL because SIGNAL only accepts a variable -- not an expression -- as an argument:

DECLARE custom_error TEXT DEFAULT NULL;
...
SET custom_error = LEFT(CONCAT('authentication failed for user ',IFNULL(CONCAT("'",input_username,"'"),'NULL')),128);
...
SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = custom_error;

Your code would probably take a different approach than IF ... EXISTS such as selecting INTO a variable and then testing that variable for null and then either returning it to the called with an unbounded SELECT or throwing the exception.

The reason for the LEFT( ...,128) is that this is the maximum length for an argument to MESSAGE_TEXT. Overrunning it won't hurt anything but you'll end up throwing an error about the invalid argument instead of the error you intended.

For simplicity, the example assumes that the password is in cleartext which obviously wouldn't be the case.

Sql-server – HierarchyID–multiple root values in one table

The dummy root is probably the right track, except you don't actually have to create a dummy root to make multiple roots. Your table also appears to be simultaneously an adjacency pair as well, so you've got a couple of immediate options on how you want to go using the table. Both should probably be tested for suitability, as I have a sneaky feeling that depending on read-a-lot or write-a-lot usage, your mileage from either case may vary.

Since the needs of both your developers and fellow DBAs must be considered, most of the other options are probably out of the question ( though there are loads and loads ). This SQL Fiddle illustrates a couple of ways to leverage the materialized paths inherit in your structure, first through leveraging a multiple-root HIERARCHYID, then through adjacency pair traversal through recursive CTEs.

To implement multiple roots, the only real "trick" to it is to preserve the sub-sequence on the root level. Instead of simply calling NULL descendants during root node creation, like so,

INSERT INTO dbo.FailCode ( IDOrg, Name )
VALUES ( HIERARCHYID::GetRoot().GetDescendant( NULL, NULL ), '1' );

each root node can be created using the root as the base level ( though the first one obviously doesn't matter ):

INSERT INTO dbo.FailCode ( IDOrg, Name )
VALUES ( HIERARCHYID::GetRoot().GetDescendant( (
            SELECT  MAX( IDOrg )
            FROM    dbo.FailCode
            WHERE   IDOrg.GetAncestor( 1 ) = HIERARCHYID::GetRoot() ), NULL ),  '1' );

INSERT INTO dbo.FailCode ( IDOrg, Name )
VALUES ( HIERARCHYID::GetRoot().GetDescendant( (
            SELECT  MAX( IDOrg )
            FROM    dbo.FailCode
            WHERE   IDOrg.GetAncestor( 1 ) = HIERARCHYID::GetRoot() ), NULL ),  '2' );

If you're in more of an UPDATE situtation, you can create the multiple root nodes off the primary key, if you like:

SELECT  CAST( '/' + CONVERT( VARCHAR( 16 ), ID ) + '/' AS HIERARCHYID ).ToString()
FROM    dbo.FailCode
WHERE   Name IN ( '1', '2' );

Children can then be added to each root node as necessary, business as usual stuff from there.

On the adjacency pairs side of your structure, either of the above inserts would do the trick - the ParentID for any root node just has to be NULL. Again, at this point, adding children is pretty evident.

Either way you go about it, the hierarchy capabilities are largely equivalent and either solution can be effective and efficient ( though the adjacency list model will certainly appear to be a little more involved! ).

HIERARCHYID

SELECT  Org = IDOrg.ToString(), ID, Name
FROM    dbo.FailCode
ORDER BY ID;

Adjacency List

;WITH cte_AdjacencyList AS (
    SELECT  Lvl = ROW_NUMBER() OVER (
                ORDER BY ID ), 
            Org = CAST( '/' + CONVERT( VARCHAR( 16 ), ROW_NUMBER() OVER (
                ORDER BY ID ) ) + '/' AS VARCHAR( 32 ) ),
            ParentID, ID, Name
    FROM    dbo.FailCode 
    WHERE   ParentID IS NULL
    UNION ALL
    SELECT  Lvl = ROW_NUMBER() OVER (
                ORDER BY fc.ID ),
            Org = CAST ( al.Org + CONVERT( VARCHAR( 16 ), ROW_NUMBER() OVER (
                ORDER BY fc.ID ) ) + '/' AS VARCHAR( 32 ) ),
            fc.ParentID, fc.ID, fc.Name
    FROM    dbo.FailCode fc
    INNER JOIN cte_AdjacencyList al
        ON  fc.ParentID = al.ID )
SELECT  Org, ID, Name
FROM    cte_AdjacencyList
ORDER BY ID;

Best Answer

Related Solutions

Mysql – Stored procedure to handle empty sets

Sql-server – HierarchyID–multiple root values in one table

Related Question