Nested Sets

Transform any Adjacency List to Nested Sets using MySQL stored procedures

Adjacency Lists are among the most popular models for storing hierarchical data into databases, but sometimes they do not provide enough flexibility for certain types of projects. In some cases Nested Sets are required in order to improve performance or implement the required functionality.

A recent project of mine which had a initial category structure implemented as Adjacency List had to be transformed to Nested Sets due to the specific queries and UI. Building it with the current table structure was going to be hard not only for coding but for the overall performance, so the category structure had to be transformed.

I am not going to go into details about what are Adjacency Lists and what are Nested Sets, assuming that since you are reading this post you are familiar with both of them. I will only go through the logic and code required to transform your tables keeping both structures.

To transform the table I decided to make 2 MySQL stored procedures. Here is the logic:

  1. Create a helper table;
  2. Create a “nested_add_node” procedure that will simply add a row to the helper table and do all the calculation required for the Nested Sets model;
  3. Create a “nested_rebuild_table” procedure that will iterate through all the rows in the original table and add each row to the new helper table using the “nested_add_node” SP;
  4. Copy the left, right fields from the helper table to the original;
  5. Destroy the helper table;

Although this might not be the perfect solution, since the category tables is updated very rarely, the heaviness of the transformation is justified.

CREATE DEFINER=`root`@`localhost` PROCEDURE `nested_add_node`(
    IN value_id INT,
    IN value_parent INT
    DECLARE parent_left INT;
    DECLARE new_nright INT;
    DECLARE new_nleft INT;
    SET parent_left = (SELECT nleft FROM tmp_nested_helper WHERE set_id = value_parent);
    IF(parent_right IS NULL) THEN
        SET parent_left = 1;
    END IF;
    SET new_nleft = parent_left + 1;
    SET new_nright = parent_left + 2;
	UPDATE tmp_nested_helper SET nright = nright + 2 WHERE nright > parent_left;
	UPDATE tmp_nested_helper SET nleft = nleft + 2 WHERE nleft > parent_left;
        INSERT INTO tmp_nested_helper (set_id, set_parent, nleft, nright) VALUES(value_id, value_parent, new_nleft, new_nright);

This stored procedure calculates the left and right values for the node to be added, updates the rest of the table to make room for the new node and inserts the node into the helper table.

Now in order to process the whole table and update all the rows with their respective left and right values we will need another stored procedure:

CREATE DEFINER=`root`@`localhost` PROCEDURE `nested_rebuild_table`(IN parent_id INT)
    DECLARE tmp_id INT;
    DECLARE tmp_parent INT;
    DECLARE cur CURSOR FOR SELECT set_id, set_parent FROM nestedtest WHERE set_parent = parent_id;
    SET max_sp_recursion_depth = 255;
    IF(parent_id = 0) THEN
	CREATE TABLE IF NOT EXISTS tmp_nested_helper ENGINE=MEMORY AS (SELECT set_id, set_parent, nleft, nright FROM nestedtest);
	TRUNCATE TABLE tmp_nested_helper;
    END IF;
    OPEN cur;
    read_loop: LOOP
	FETCH cur INTO tmp_id, tmp_parent;
        IF done THEN
	  LEAVE read_loop;
        CALL nested_add_node(tmp_id, tmp_parent);
        CALL nested_rebuild_table(tmp_id);
   CLOSE cur;
   IF(parent_id = 0) THEN
	UPDATE nestedtest SET nestedtest.nleft = (SELECT tmp_nested_helper.nleft FROM tmp_nested_helper WHERE tmp_nested_helper.set_id = nestedtest.set_id);
        UPDATE nestedtest SET nestedtest.nright = (SELECT tmp_nested_helper.nright FROM tmp_nested_helper WHERE tmp_nested_helper.set_id = nestedtest.set_id);
	DROP TABLE tmp_nested_helper;
    END IF;

The nested_rebuild_table SP receives the root id which might not exist in the table and I have set it to zero. Remember that this is not an actual row but a way for the SP to know that it is the first call in the series of recursions. Once called, it will select all the rows in the first level with parent = 0, loop through them and for each row recursively add all the child nodes to the helper table until it goes through the whole staring table. At the end it will copy the new left and right values from the helper table to the original and drop the helper table.

Now that I have the rebuild table procedure, I can call it CALL nested_rebuild_table(0); to initially transform the table from Adjacency List to Nested Sets and after that in the PHP code call it when a new node is added/deleted/parent of a specific node is changed. This allows me to simplify the code in the admin panel for the project, use the Adjacency List logic where it suits me while still being able to implement the Nested Sets where needed, thus getting the best of both models for storing hierarchical data.


Category : MySQL, PHP
Tags : ,