Nested Sets + PostgreSQL TRIGGER

Task

How convenient to make selections of trees of type Nested Sets, and not convenient to manage. How to udobnoposvetu trees types id->parent_id, but how inconvenient and expensive to use recursion with selections. It is clear that when using the modules for managing trees part of the problem is removed, but the process of working with the database not quite transparent, i.e. to modify data, we use some methods to change the location of the node in the tree,plus the transaction would not hurt. This inconsistency can be solved in two ways:

the
• to be Used for a table of stored procedures, which combine both methods of update (insert, delete);
the
• to Use triggers to avoid in General any non-standard methods of work;

the First method is that when you change the table structure, we need to change the procedure, as well as betmaxcasino careful when working with a table that all changes to the data have passed through our procedures, not paramilitarism. The second method is somewhat heavier tablicu the introduction of additional Boolean fields, and have Delineator "feints ears", although it allows to achieve maximum transparency.The first method — in the furnace, especially where the Internet is already such solution.Database — PostgreSQL as relevant to me at the moment, supplements for MySQL will write later.

table

so, what are the triggers we need:

the
• To insert a record to form the gap in the tree and key for the generated node;
the
• Before you upgrade is to rebuild the tree and generating keys for the updating node;
the
• After removing — remove the gap in the tree remaining after removal of the node;

Rake:

the
• At the time of trigger is required lochit table, or a separate tree, if carried in one table of a few trees;
the
• In PostgreSQL and MySQL in the triggers you can't disable recursion, like this;

the second Point more: In the trigger before update, you can update records from the same table, which would entail povtoryayu trigger and so on, so for the trigger that is called after the removal. In order to understand caused we zaprosit trigger or not, we introduce two additional Boolean fields that we pass in the request as a parameter (flag) astriger, not as data. Why two to tell later.The table structure will form from given the fact that we have it is to have a few trees.Let me explain why. I laugh to tears to listen to stupid developers who with foam at a mouth prove, what they say, ay-ay-ay, pribolshoy the number of nodes the host can affect the entire tree, and it's hard on the base. Yes, that's right. I do not argue.Only here I have never met a huge number of nodes in a single tree because:

the
• I don't use the common root node;

I share the trees on the nodes is zero;

Example: There is a certain forum. In the forum section of the 1'000 posts, each post 1'000 comments. Total comments — 1'000'000.So, the forum section is NOT the root node, comments as well as posts are NOT nodes of the same tree, appear only in the separators tree. In the end, I have 1'000 separate trees in the 1'000 comments. Update proishodila only within a maximum of 1'000 records. In some cases, if that many, the separator trees are commentarypeer level. In the end, the rebuild of the tree is not the load on the database. Study of the Mat.Don't let the bad news, the table structure is: 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 additional fields.Will do the function of blocking the tree change, while the transaction is not complete: SQL code (2)

CREATE OR REPLACE FUNCTION lock_ns_tree(integer)
RETURNS boolean AS
$BODY$
Tree_id DECLARE a 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 entry

we Have 3 options for adding a node to the tree:

the
• Adding to the subordination of a specific node, then we pass the parent_id;
the
• Add in a certain point in the tree, then we pass the left_key;
the
• Add to the end of the tree, then we don't need anything extra to transfer;

In the same sequence, we will determine the destination sozdaniemnovogo site. 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(NOV.tree);
- It is impossible these fields handles to put:
NEW._trigger_for_delete := FALSE;
NEW._trigger_lock_update := FALSE;
_left_key := 0;
_level := 0;
-- If we have specified 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 have indicated 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.OR left_key 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 haven't found anything:
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;
-- Set keys for the received node:
NEW.left_key := _left_key;
NEW.right_key := _left_key + 1;
NEW. level := _level;
-- Generated Razliv in the tree on the insertion location:
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 — the control field, therefore, they are immediately discharged regardless of the wishes of the user. the

• Even if we specify a parent_id — not the fact that such a node we have that it in the respective tree. In this case I don't find node in this tree, then parent_id is reset and the node is inserted at the end of the tree. Alternatively, you can filter and just search for the node at id, then you need to update a field tree created node. It all depends on the priority fields and specific implementation;
the
• If we have indicated left key, then we at least need to calculate the parent of the created node, parent determined on the principle that if we found the node on the left key, the parent will be the same as the found node, or if on the right, the parent will be found the us site, the same build and level. If the node is not found, then insert into the end of the tree left_key at the same time — reset;
the
• During the formation of the gap, further transmitted to the field _trigger_lock_update — just the same for what would be the trigger for UPDATE know that this update is only to the tree structure, and any additional calculations and modifications of the structure is not required, so how are the final key values;

Modify entry

more Precisely, this trigger will work exclusively with wood structure and not with variable data.The basic parameters of forcing him to any actions are parent_id or left_key(remembering, of course, about _trigger_lock_update as the control parameter for the trigger).The algorithm is simple: first the coordinates of the move, then rearrange the tree. SQL code (4)

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 whether we even have to do anything:
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;
-- Reset the field values that user to 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;
-- The tree has a tunable, well, let's start:
_left_key := 0;
_level := 0;
_skew_tree := OLD.right_key - OLD.left_key + 1;
-- Define where we move:
Changed-if parent_id:
IF NEW.parent_id <> OLD.parent_id THEN
-- If in obedience to another evil:
IF NEW.parent_id > 0 THEN
SELECT right_key, level + 1
INTO _left_key, _level
FROM ns_tree
WHERE id = NEW.AND tree parent_id = NEW.tree;
- Otherwise the root of the tree move:
ELSE
SELECT MAX(right_key) + 1 
INTO _left_key
FROM ns_tree
WHERE tree = NEW.tree;
_level := 0;
END IF;
-- If the parent is in the range of the moving node, 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  set  left_key and parent_id - no
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.OR left_key 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 are moving the tree
_skew_level := _level - OLD."level";
IF _left_key > OLD.left_key THEN
-- Moving 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
-- Moving 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;
-- The tree was rebuilt, leaving only our current node
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

FOR EACH ROW
EXECUTE PROCEDURE ns_tree_before_update_func();

Explanation:

the
• Initially, except for parameter _trigger_lock_update we check the _trigger_for_delete. This is because during the removal, we do not transfer the settings, as the field changes, so the deletion of records trigger will produce via UPDATE certain records. However more will be clear next;
the
• Again in this case, parent_id we have a priority bole than left_key, so check it first;
the
• When testing left_key we choose initially or node that will be in front of the roaming node (right_key = _left_key + 1), or the node at which we move the node (right_key = _left_key). Thus, in some cases, the query will return 2 nodes as a future neighbor and future parent that logic has no impact on this LIMIT 1 set, that would not just not to select unnecessary data, sorting is not important, as even if the results will be 2 knots, they can both be correct, so we are completely indifferent to which of them we'll be back. But I want to draw attention to the fact that if we attribute to the roaming node left_key = 1, it is natural that no peredistijs nor a parent node, we will not, for which we use an additional condition "ELSIF NEW.left_key = 1";
the
• When rebuilding the tree, the additional condition is "id <> OLD.id", this is because we cannot in a trigger to change a record, and so that is now changing.

Deleting records

Here with the removal of the most difficult. First, because there are 2 principle of removal of nodes:

the
• Delete node with descendants;
the
• to remove a node without descendants, in this case the child nodes are shifted on the tree on level up;

second, we can't the delete query to pass parameters to limit the recursive call of the trigger, however, a recursive call of the trigger is relevant only for the case of removal of a node with descendants.To make a universal trigger for both the removal would be costly, too much logic. Better still, two different solutions.In the first solution (delete node with descendants) we have the following algorithm:

the
• Updating child nodes for the presence of the field (parameter) _trigger_for_delete;
the
• Remove the child nodes;
the
• Remove gap keys in the tree (perestanem tree);

the 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 to execute the trigger:
IF OLD._trigger_for_delete = TRUE THEN RETURN OLD; END IF;
-- Mark to delete the 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 the marked nodes:
DELETE FROM ns_tree
WHERE
tree = OLD.tree AND
left_key > OLD.left_key AND
right_key < OLD.right_key;
-- Remove the break 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();

the second solution is to simply displace the child tree one level up, and removed the gap key. 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 break in the keys and move 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 

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();

in Fact everything. It remains only to put the indexes (I was lazy here to write the SQL team, so they just announce):

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

Enjoy ;-)

Article based on information from habrahabr.ru