Nested Sets + PostgreSQL TRIGGER

Task

How convenient it is to make selections from trees like Nested Sets, and how not convenient to manage them. How to conveniently manage with trees like id-> parent_id, but it’s not convenient and costly to use recursion during selections. It is clear that when using modules to manage trees, part of the problem is removed, but the process of working with the database is not completely transparent, ie to change the data, we use some methods, to change the location of the node in the tree - others, plus more transactions would not hurt. This inconsistency can be solved in two ways:

• Use stored procedures for working with a table in which to combine both update (insert, delete) methods;
• Use triggers to exclude any non-standard methods of work in general;

The first method is inconvenient because when changing the structure of the table, we will need to change the procedure, as well as be as careful as possible when working with the table, so that all changes to the data go through our procedures, and not by direct queries. The second method makes the table slightly more complex by introducing additional Boolean fields, and also has to do some “tricks with your ears”, although it allows you to achieve maximum transparency of the work. The first way is into the firebox, especially somewhere the Internet already has a similar solution. The PostgreSQL database Actual to me at the moment, add-ons for MySQL will be written later.

Table

So, what triggers will we need:

• Before inserting a record, to form a gap in the tree and keys for the node being created;
• Before updating - to rebuild the tree and generate keys for the updated node;
• After deleting - deleting a gap in the tree remaining after removing the node;

Rake:

• At the time of the triggers, you need to lock a table, or a single tree, if you have several trees in one table;
• In PostgreSQL and MySQL, triggers cannot disable recursion, like this;

Point two is more detailed: In a trigger before an update, records from the same table can be updated, which would entail a repeated call of a trigger, and so on, also for a trigger called after deletion. In order to understand whether a request from a trigger is triggered or not, we introduce two additional Boolean fields that we will pass in the request as a parameter (flag) for the trigger, and not as data. Why two? I will tell you later. We will form the structure of the table immediately, taking into account that we will have several trees in it. I will explain why. It's ridiculous for me to listen to tears of stupid developers who, with foaming at the mouth, prove that they say, ah-ah-ah, with a large number of nodes, updating nodes can affect the whole tree, and it is so hard for the base. Yes exactly. I do not argue. Only now I have never had a huge number of nodes in one tree because:

• I do not use a common root node;
• I divide trees by nodes of zero level;

Example: There is some forum. In the forum section there are 1,000 posts, each post has 1,000 comments. Total comments - 1'000'000. So, the forum section is NOT the root node of the comments, just like the posts are NOT the nodes of a single tree, they are only tree separators. As a result, I have 1'000 separate trees with 1'000 comments. Updating occurs only within a maximum of 1,000 entries. In some cases, if this is too much, the tree separator is a comment at the first level. As a result, rebuilding the tree is not such a burden on the base. Study the mat part. Let's not talk about the sad, the structure of the table: SQL code (1)

 CREATE
   ns_tree (
     id SERIAL,
     left_key INTEGER NOT NULL,
     right_key INTEGER NOT NULL,
     level INTEGER NOT NULL DEFAULT 0,
     tree INTEGER NOT NULL,    
     parent_id INTEGER NOT NULL DEFAULT 0,
     _trigger_lock_update BOOLEAN NOT NULL DEFAULT FALSE,
     _trigger_for_delete BOOLEAN NOT NULL DEFAULT FALSE,
     field_1 ...,
     ...
 PRIMARY KEY (id)
 );
    

Actually - _trigger_lock_update and _trigger_for_delete , are our auxiliary fields. Immediately make the function a blocking tree for change until the transaction is completed: SQL code (2)

 CREATE OR REPLACE FUNCTION lock_ns_tree (integer)
     RETURNS boolean AS
 $ BODY $
 DECLARE tree_id ALIAS FOR $ 1;
     _id INTEGER;
 BEGIN
     SELECT id
         INTO _id
         FROM ns_tree
         WHERE tree = tree_id FOR UPDATE;
     RETURN TRUE;
 END;
 $ BODY $
   LANGUAGE 'plpgsql' VOLATILE
   COST 100;
 ALTER FUNCTION lock_ns_tree (integer) OWNER TO user;
    

Create a record

We have 3 options for adding a node to the tree:

• Adding a subordinate to a specific node, then we pass parent_id ;
• Adding to a certain point of the tree, then we pass left_key ;
• Adding to the end of the tree, then we do not need to transfer anything further;

In the same sequence, we will determine the destination of the node being created. SQL code (3)

 CREATE OR REPLACE FUNCTION ns_tree_before_insert_func ()
     RETURNS trigger AS
 $ BODY $
 DECLARE
     _left_key INTEGER;
     _level INTEGER;
     _tmp_left_key INTEGER;
     _tmp_right_key INTEGER;
     _tmp_level INTEGER;
     _tmp_id INTEGER;
     _tmp_parent_id INTEGER;
 BEGIN
     PERFORM lock_ns_tree (NEW.tree);
 - You can not put these fields handles:
     NEW._trigger_for_delete: = FALSE;
     NEW._trigger_lock_update: = FALSE;
     _left_key: = 0;
     _level: = 0;
 - If we indicated a parent:
     IF NEW.parent_id IS NOT NULL AND NEW.parent_id> 0 THEN
         SELECT right_key, "level" + 1
             INTO _left_key, _level
             FROM ns_tree
             WHERE id = NEW.parent_id AND
                   tree = NEW.tree;
     END IF;
 - If we specified the left key:
     IF NEW.left_key IS NOT NULL AND
        NEW.left_key> 0 AND 
        (_left_key IS NULL OR _left_key = 0) THEN
         SELECT id, left_key, right_key, "level", parent_id 
             INTO _tmp_id, _tmp_left_key, _tmp_right_key, _tmp_level, _tmp_parent_id
             FROM ns_tree
             WHERE tree = NEW.tree AND (left_key = NEW.left_key OR right_key = NEW.left_key);
         IF _tmp_left_key IS NOT NULL AND _tmp_left_key> 0 AND NEW.left_key = _tmp_left_key THEN
             NEW.parent_id: = _tmp_parent_id;
             _left_key: = NEW.left_key;
             _level: = _tmp_level;
         ELSIF _tmp_left_key IS NOT NULL AND _tmp_left_key> 0 AND NEW.left_key = _tmp_right_key THEN
             NEW.parent_id: = _tmp_id;
             _left_key: = NEW.left_key;
             _level: = _tmp_level + 1;
         END IF;
     END IF;
 - If the parent or left key is not specified, or we did not find:
     IF _left_key IS NULL OR _left_key = 0 THEN
         SELECT MAX (right_key) + 1
             INTO _left_key
             FROM ns_tree
             WHERE tree = NEW.tree;
         IF _left_key IS NULL OR _left_key = 0 THEN
             _left_key: = 1;
         END IF;
         _level: = 0;
         NEW.parent_id: = 0; 
     END IF;
 - Install the obtained keys for the node:
     NEW.left_key: = _left_key;
     NEW.right_key: = _left_key + 1;
     NEW. "Level": = _level;
 - We form a tree in the tree at the insertion point:
     UPDATE ns_tree
         SET left_key = left_key + 
             CASE WHEN left_key> = _left_key 
               THEN 2 
               ELSE 0 
             END,
             right_key = right_key + 2,
             _trigger_lock_update = TRUE
         WHERE tree = NEW.tree AND right_key> = _left_key;
     RETURN NEW;
 END;
 $ BODY $
   LANGUAGE 'plpgsql' VOLATILE
   COST 100;
 ALTER FUNCTION ns_tree_before_insert_func () OWNER TO user;

 CREATE TRIGGER ns_tree_before_insert_tr
     BEFORE INSERT
     ON ns_tree
     FOR EACH ROW
     EXECUTE PROCEDURE ns_tree_before_insert_func ();
    

Now some explanations:

• _trigger_lock_update and _trigger_for_delete are control fields, so we reset them immediately, regardless of the wishes of the user;
• Even if we specified parent_id , it’s not a fact that we have such a node and that it is in the corresponding tree. In the current case, if I do not find a node in this tree, then parent_id is reset, and the node is inserted at the end of the tree. Alternatively, you can filter by tree, but simply search for a node by id , then you will need to update the tree field of the node being created. It all depends on the priority of the fields and the specific implementation;
• If we specified the left key, then we, at a minimum, need to calculate the parent of the node being created, the parent is determined by the principle: if we find the node by the left key, the parent will be the same as the found node, otherwise if by the right key, then the parent will be the node found by us, we also build a level. If the node is not found, then we insert it at the end of the tree, while the left_key is reset;
• During the formation of the gap, the _trigger_lock_update field is additionally transmitted - just so that the trigger for UPDATE would know that this update is related solely to the tree structure, and no additional calculations and structure changes are required, since the final key values ​​are already transmitted;

Change record

More precisely, this trigger will work exclusively with the tree structure, and not with the data being changed. The main parameters forcing it to take any action are parent_id or left_key (remembering, of course, _trigger_lock_update as a controlling parameter for the trigger). The algorithm is simple: first move coordinates, then rebuild the tree. SQL code (4)

 CREATE OR REPLACE FUNCTION ns_tree_before_update_func ()
   RETURNS trigger AS
 $ BODY $
 DECLARE
     _left_key INTEGER;
     _level INTEGER;
     _skew_tree INTEGER;
     _skew_level INTEGER;
     _skew_edit INTEGER;
     _tmp_left_key INTEGER;
     _tmp_right_key INTEGER;
     _tmp_level INTEGER;
     _tmp_id INTEGER;
     _tmp_parent_id INTEGER;
 BEGIN
     PERFORM lock_ns_tree (OLD.tree);
 - And is it worth us to do anything at all:
     IF NEW._trigger_lock_update = TRUE THEN
         NEW._trigger_lock_update: = FALSE;
         IF NEW._trigger_for_delete = TRUE THEN
             NEW = OLD;
             NEW._trigger_for_delete = TRUE;
             RETURN NEW;
         END IF;
         RETURN NEW;
     END IF;
 - We reset the values ​​of the fields that the user can not change:
     NEW._trigger_for_delete: = FALSE;
     NEW.tree: = OLD.tree;
     NEW.right_key: = OLD.right_key;
     NEW. "Level": = OLD. "Level";
     IF NEW.parent_id IS NULL THEN NEW.parent_id: = 0;  END IF;
 - Check whether there are changes associated with the tree structure
     IF NEW.parent_id = OLD.parent_id AND NEW.left_key = OLD.left_key
     THEN
         RETURN NEW;
     END IF;
 - We are still rebuilding the tree, well, let's start:
     _left_key: = 0;
     _level: = 0;
     _skew_tree: = OLD.right_key - OLD.left_key + 1;
 - Determine where we transfer it:
 - If parent_id is changed:
     IF NEW.parent_id <> OLD.parent_id THEN
 - If in submission to another evil:
         IF NEW.parent_id> 0 THEN
             SELECT right_key, level + 1
                 INTO _left_key, _level
                 FROM ns_tree
                 WHERE id = NEW.parent_id AND tree = NEW.tree;
 - Otherwise, we transfer to the root of the tree:
         ELSE
             SELECT MAX (right_key) + 1 
                 INTO _left_key
                 FROM ns_tree
                 WHERE tree = NEW.tree;
             _level: = 0;
         END IF;
 - If suddenly the parent is in the range of the node being moved, check:
         IF _left_key IS NOT NULL AND 
            _left_key> 0 AND
            _left_key> OLD.left_key AND
            _left_key <= OLD.right_key 
         THEN
            NEW.parent_id: = OLD.parent_id;
            NEW.left_key: = OLD.left_key;
            RETURN NEW;
         END IF;
     END IF;
 - If left_key is specified, but parent_id is not
     IF _left_key IS NULL OR _left_key = 0 THEN
         SELECT id, left_key, right_key, "level", parent_id 
             INTO _tmp_id, _tmp_left_key, _tmp_right_key, _tmp_level, _tmp_parent_id
             FROM ns_tree
             WHERE tree = NEW.tree AND (right_key = NEW.left_key OR right_key = NEW.left_key - 1)
             LIMIT 1;
         IF _tmp_left_key IS NOT NULL AND _tmp_left_key> 0 AND NEW.left_key - 1 = _tmp_right_key THEN
             NEW.parent_id: = _tmp_parent_id;
             _left_key: = NEW.left_key;
             _level: = _tmp_level;
         ELSIF _tmp_left_key IS NOT NULL AND _tmp_left_key> 0 AND NEW.left_key = _tmp_right_key THEN
             NEW.parent_id: = _tmp_id;
             _left_key: = NEW.left_key;
             _level: = _tmp_level + 1;
         ELSIF NEW.left_key = 1 THEN
             NEW.parent_id: = 0;
             _left_key: = NEW.left_key;
             _level: = 0;
         ELSE
            NEW.parent_id: = OLD.parent_id;
            NEW.left_key: = OLD.left_key;
            RETURN NEW;
         END IF;
     END IF;
 - Now we know where we move the tree.
         _skew_level: = _level - OLD. "level";
     IF _left_key> OLD.left_key THEN
 - Move up the tree
         _skew_edit: = _left_key - OLD.left_key - _skew_tree;
         UPDATE ns_tree
             SET left_key = CASE WHEN right_key <= OLD.right_key
                                  THEN left_key + _skew_edit
                                  ELSE CASE WHEN left_key> OLD.right_key
                                            THEN left_key - _skew_tree
                                            ELSE left_key
                                       END
                             END,
                 "level" = CASE WHEN right_key <= OLD.right_key 
                                  THEN "level" + _skew_level
                                  ELSE "level"
                             END,
                 right_key = CASE WHEN right_key <= OLD.right_key 
                                  THEN right_key + _skew_edit
                                  ELSE CASE WHEN right_key <_left_key
                                            THEN right_key - _skew_tree
                                            ELSE right_key
                                       END
                             END,
                 _trigger_lock_update = TRUE
             WHERE tree = OLD.tree AND
                   right_key> OLD.left_key AND
                   left_key <_left_key AND
                   id <> OLD.id;
         _left_key: = _left_key - _skew_tree;
     ELSE
 - Move down the tree:
         _skew_edit: = _left_key - OLD.left_key;
         UPDATE ns_tree
             SET
                 right_key = CASE WHEN left_key> = OLD.left_key
                                  THEN right_key + _skew_edit
                                  ELSE CASE WHEN right_key <OLD.left_key
                                            THEN right_key + _skew_tree
                                            ELSE right_key
                                       END
                             END,
                 "level" = CASE WHEN left_key> = OLD.left_key
                                  THEN "level" + _skew_level
                                  ELSE "level"
                             END,
                 left_key = CASE WHEN left_key> = OLD.left_key
                                  THEN left_key + _skew_edit
                                  ELSE CASE WHEN left_key> = _left_key
                                            THEN left_key + _skew_tree
                                            ELSE left_key
                                       END
                             END,
                  _trigger_lock_update = TRUE
             WHERE tree = OLD.tree AND
                   right_key> = _left_key AND
                   left_key <OLD.right_key AND
                   id <> OLD.id;
     END IF;
 - Tree rebuilt, only our current node remains
     NEW.left_key: = _left_key;
     NEW. "Level": = _level;
     NEW.right_key: = _left_key + _skew_tree - 1;
     RETURN NEW;
 END;
 $ BODY $
     LANGUAGE 'plpgsql' VOLATILE
     COST 100;
 ALTER FUNCTION ns_tree_before_update_func () OWNER TO user;

 CREATE TRIGGER ns_tree_before_update_tr
     BEFORE UPDATE
     ON ns_tree
     FOR EACH ROW
     EXECUTE PROCEDURE ns_tree_before_update_func ();
    

Explanations:

• Initially, in addition to the _trigger_lock_update parameter , we also check the _trigger_for_delete parameter. This is done because during deletion, we do not pass parameters as a field change, therefore, we will delete records with a trigger through UPDATE of certain records. But it will become more clear further;
• Again in this case, parent_id is more priority than left_key , so we check it first;
• When checking left_key, we initially select either the node that will be in front of the node being moved ( right_key = _left_key + 1 ), or the node to which we move the node ( right_key = _left_key ). At the same time, in some cases, the result of the query will return 2 nodes, both the future neighbor and the future parent, which does not affect the logic, therefore LIMIT 1 is installed, so as not to simply choose unnecessary data, the sorting is not important, since even if the result of the sampling is 2 nodes, both of them will be correct, so it doesn’t matter to us which of them will return to us. But I want to draw attention to the fact that if we specify the left_key = 1 for the node being moved, then it’s natural that we’ll have neither the front node nor the parent node, for which we use the additional condition " ELSIF NEW.left_key = 1 ";
• When rebuilding the tree, the additional condition is " id <> OLD.id ", this is done because we cannot change the record in the trigger, which we are already changing.

Delete record

Here with the removal of the hardest. Firstly, because there are 2 principles for deleting nodes:

• Deleting a node with descendants;
• Deleting a node without descendants, with the child nodes moving up a level in the tree;

Secondly, we cannot transfer parameters in the request for deletion to limit the recursive call of the trigger, however, the recursive call of the trigger is relevant only for the case of deleting a node with descendants. Making a universal trigger for both removal principles will be costly, too much logic will be. Better after all, two different solutions. In the first solution (deleting a node with descendants) we will have the following algorithm:

• Update child nodes for setting the field (parameter) _trigger_for_delete ;
• Remove child nodes;
• Remove the gap in the keys in the tree (stop the tree);

SQL code (5)

 CREATE OR REPLACE FUNCTION ns_tree_after_delete_func ()
     RETURNS trigger AS
 $ BODY $
 DECLARE
     _skew_tree INTEGER;
 BEGIN
     PERFORM lock_ns_tree (OLD.tree);
 - Check whether the trigger should be executed:
     IF OLD._trigger_for_delete = TRUE THEN RETURN OLD;  END IF;
 - We mark on deleting child nodes:
     UPDATE ns_tree
         SET _trigger_for_delete = TRUE,
             _trigger_lock_update = TRUE
         WHERE
             tree = OLD.tree AND
             left_key> OLD.left_key AND
             right_key <OLD.right_key;
 - Remove marked nodes:
     DELETE FROM ns_tree
         WHERE
             tree = OLD.tree AND
             left_key> OLD.left_key AND
             right_key <OLD.right_key;
 - Remove the gap in the keys:
     _skew_tree: = OLD.right_key - OLD.left_key + 1;
     UPDATE ns_tree
         SET left_key = CASE WHEN left_key> OLD.left_key
                             THEN left_key - _skew_tree
                             ELSE left_key
                        END,
             right_key = right_key - _skew_tree,
             _trigger_lock_update = TRUE
         WHERE right_key> OLD.right_key AND
             tree = OLD.tree;
     RETURN OLD;
 END;
 $ BODY $
     LANGUAGE 'plpgsql' VOLATILE
     COST 100;
 ALTER FUNCTION ns_tree_after_delete_func () OWNER TO user;

 CREATE TRIGGER ns_tree_after_delete_tr
     AFTER DELETE
     ON ns_tree
     FOR EACH ROW
     EXECUTE PROCEDURE ns_tree_after_delete_func ();
    

In the second solution, we simply move the child tree one level up, and remove the key gap. SQL code (6)

 CREATE OR REPLACE FUNCTION ns_tree_after_delete_2_func ()
     RETURNS trigger AS
 $ BODY $
 DECLARE
 BEGIN
     PERFORM lock_ns_tree (OLD.tree);
 - Remove the gap in the keys and shift the child nodes:
    UPDATE ns_tree
         SET left_key = CASE WHEN left_key <OLD.left_key
                             THEN left_key
                             ELSE CASE WHEN right_key <OLD.right_key
                                       THEN left_key - 1 
                                       ELSE left_key - 2
                                  END
                        END,
             "level" = CASE WHEN right_key <OLD.right_key
                            THEN "level" - 1 
                            ELSE "level"
                       END,
             parent_id = CASE WHEN right_key <OLD.right_key AND "level" = OLD.level + 1
                            THEN OLD.parent_id
                            ELSE parent_id
                         END,
             right_key = CASE WHEN right_key <OLD.right_key
                              THEN right_key - 1 
                              ELSE right_key - 2
                         END,
             _trigger_lock_update = TRUE
         WHERE (right_key> OLD.right_key OR
             (left_key> OLD.left_key AND right_key <OLD.right_key)) AND
             tree = OLD.tree;
     RETURN OLD;
 END;
 $ BODY $
   LANGUAGE 'plpgsql' VOLATILE
   COST 100;
 ALTER FUNCTION ns_tree_after_delete_2_func () OWNER TO user;

 CREATE TRIGGER ns_tree_after_delete_2_tr
     AFTER DELETE
     ON ns_tree
     FOR EACH ROW
     EXECUTE PROCEDURE ns_tree_after_delete_2_func ();
    

Actually everything. It remains only to put down the indices (I'm lazy to write SQL commands here, so I’ll just voice them):

• Composite is not unique to fields ( left_key, right_key, level, tree );
• Not unique on the field ( parent_id );

Enjoy ;-)