doc.prototypes.ru: Проекты: Деревья SQL: Nested Sets: Практика SQL: На базе триггеров PostgreSQL

Используем триггеры в PostgreSQL

Задача

Как удобно делать выборки из деревьев типа Nested Sets, и как не удобно им управлять. Как удобно управлять деревьями типа id->parent_id, но как не удобно и накладно использовать рекурсии при выборках. Понятно, что при использовании модулей для управления деревьями часть проблемы снимается, но при этом процесс работы с базой данных не совсем прозрачен т.е. для изменения данных мы используем одни методы, для изменения расположения узла в дереве - другие, плюс еще транзакции не помешали бы. Эту нестыковку можно решить двумя способами:

Использовать для работы с таблицей хранимые процедуры, в которой объединить оба метода обновления (вставки, удаления);
Использовать триггеры, для исключения вообще каких-либо нестандартных методов работы;

Первый способ неудобен тем, что при изменении структуры таблицы, нам потребуется еще изменять процедуру, а так же быть максимально внимательным, при работе с таблицей, что бы все изменения данных проходили через наши процедуры, а не прямыми запросами. Второй способ несколько утяжеляет тяблицу введением дополнительных булевых полей, а так же приходится делать некоторые "финты ушами", хотя позволяет добиться максимальной прозрачности работы.

Первый способ - в топку, тем более где-то интернетах уже есть подобное решение.

База данных - PostgreSQL, как актуальная мне на данный момент, дополнения для MySQL здесь.

Таблица

Итак, какие триггеры нам понадобятся:

До вставки записи - для формирования разрыва в дереве и ключей для создаваемого узла;
До обновления - для перестроения дерева и формирования ключей для обновляемого узла;
После удаления - удаление разрыва в дереве оставшееся после удаления узла;

Грабли:

На время работы триггеров, требуется лочить таблицу, или отдельное дерево, если у нес в одной таблице деревьев несколько;
В PostgreSQL и MySQL в триггерах нельзя отключить рекурсию, вот так;

Пункт второй подробнее: В триггере до обновления, могут обновляться записи из той же таблицы, что повлечет за собой повторый вызов триггера и так далее, так же и для триггера, вызываемого после удаления. Для того что бы понять вызван у нас запрос из триггера или нет, введем два дополнительных булевых поля, которые мы будем передавать в запросе как параметр (флаг) для триггера, а не как данные. Почему именно два - расскажу позднее.

Структуру таблицы сформируем сразу с учетом того, что у нас в ней будет храниться несколько деревьев. Объясню почему. Мне смешно до слез слушать глупых разработчиков, которые с пеной у рта доказывают, что мол, ай-ай-ай, при большом количестве узлов обновление узлов может затронуть все дерево, и это так тяжело для базы. Да, именно так. Не спорю. Только вот у меня еще ниразу не было огромного количества узлов в одном дереве потому, что:

я не использую общий корневой узел;
я разделяю деревья по узлам нулевого уровня;

Пример: Есть некоторый форум. В разделе форума 1'000 постов, у каждого поста 1'000 комментариев. Всего комментариев - 1'000'000. Так вот, раздел форума - НЕ является корневым узлом комментариев, так же как и посты НЕ являются узлами одного дерева, а являются только разделителями деревьев. В итоге, у меня 1'000 раздельных деревьев по 1'000 комментариев. Обновление происходит только лишь в пределах максимум 1'000 записей. В некоторых случаях, если и этого много, разделителем деревьев являются комментарии первого уровня. В итоге, перестроение дерева не является такой уж нагрузкой на базу. Изучайте мат часть.

TTTSSSaaa111

Не будем о грустном, структура таблицы:

SQL код (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) );

Собственно - _trigger_lock_update и _trigger_for_delete, являются нашими вспомогательными полями.

Сразу сделаем функцию блокирующую дереве на изменение, пока транзакция не закончена:

SQL код (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;

Создание записи

У нас есть 3 варианта добаления узла в дерево:

Добавление в подчинение определенному узлу, тогда мы передаем parent_id;
Добавление в определенную точку дерева, тогда мы передаем left_key;
Добавление в конец дерева, тогда нам не требуется ничего дополнительно передавать;

В такой же последовательности мы будем определять место назначения создаваемного узла.

SQL код (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); -- Нельзя эти поля ручками ставить: NEW._trigger_for_delete := FALSE; NEW._trigger_lock_update := FALSE; _left_key := 0; _level := 0; -- Если мы указали родителя: 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 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 _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; -- Устанавливаем полученные ключи для узла: NEW.left_key := _left_key; NEW.right_key := _left_key + 1; NEW."level" := _level; -- Формируем развыв в дереве на месте вставки: 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();

Теперь некоторые пояснения:

_trigger_lock_update и _trigger_for_delete - управляющие поля, поэтому их сразу сбрасываем не зависимо от пожеланий пользователя;
Даже если мы указали parent_id - не факт, что такой узел у нас есть и то, что он в соответсвующем дереве. В текущем случае, если я не нахожу узла в данном дереве, то parent_id сбрасывается, и узел вставляется в конец дерева. Как вариант, можно фильтровать по дереву, а просто искать узел по id, тогда нужно будет обновлять поле tree создаваемого узла. Все зависит от приоритетности полей и конкретной реализации;
Если мы указали левый ключ, то нам, как минимум, нужно вычислить родителя создаваемого узла, родителя определяем по принципу: если мы нашли узел по левому ключу, то родитель будет таким же как и у найденого узла, иначе если по правому, то родителем будет найденный нами узел, так же выстраиваем и уровень. Если же узел, не найден, то тогда вставляем в конец дерева, left_key при этом - сбрасывается;
Во время формирования разрыва, дополнительно передается поле _trigger_lock_update - как раз таки для того, что бы триггер для UPDATE знал, что это обновление связано исключительно со структурой дерева, и никаких дополнительных вычислений и изменений структуры не требуется, так как передаются уже конечные значения ключей;

Изменение записи

Точнее данный триггер будет работать исключительно со структурой дерева, а не с изменяемыми данными.

Основными параметрами принуждающие его к каким либо действиям являются parent_id или left_key (помня, конечно, о _trigger_lock_update как об управляющем параметре для триггера).

Алгоритм простой: сначала координаты перемещения, потом перестраиваем дерево.

SQL код (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); -- А стоит ли нам вообще что либо делать: 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; -- Сбрасываем значения полей, которые пользователь менять не может: 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; -- Проверяем, а есть ли изменения связанные со структурой дерева IF NEW.parent_id = OLD.parent_id AND NEW.left_key = OLD.left_key THEN RETURN NEW; END IF; -- Дерево таки перестраиваем, что ж, приступим: _left_key := 0; _level := 0; _skew_tree := OLD.right_key - OLD.left_key + 1; -- Определяем куда мы его переносим: -- Если сменен parent_id: IF NEW.parent_id <> OLD.parent_id THEN -- Если в подчинение другому злу: 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; -- Иначе в корень дерева переносим: ELSE SELECT MAX(right_key) + 1 INTO _left_key FROM ns_tree WHERE tree = NEW.tree; _level := 0; END IF; -- Если вдруг родитель в диапазоне перемещаемого узла, проверка: 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; -- Если же указан left_key, а parent_id - нет 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; -- Теперь мы знаем куда мы перемещаем дерево _skew_level := _level - OLD."level"; IF _left_key > OLD.left_key THEN -- Перемещение вверх по дереву _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 -- Перемещение вниз по дереву: _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; -- Дерево перестроили, остался только наш текущий узел 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();

Пояснения:

Изначально, кроме параметра _trigger_lock_update мы проверяем так же параметр _trigger_for_delete. Это сделано потому, что во время удаления, мы не передавать параметры, как изменение поля, поэтому удаление записей триггером будем производить через UPDATE определенных записей. Впрочем более понятно станет далее;
Опять же в данном случае, parent_id у нас боле приоритетный чем left_key, поэтому его проверяем первым;
При проверке left_key мы выбираем изначально либо узел, который будет перед перемещаемым узлом (right_key = _left_key + 1), либо узел в который мы перемещаем узел (right_key = _left_key). При этом, у некоторых случаях результатом запроса будет возвращаться 2 узла, как будущий сосед, так и будущий родитель, что на логику никак не влияет, по этому LIMIT 1 установлен, что бы не просто не выбирать лишние данные, сортировка не важна, так как даже если результатом выборки будет 2 узла, они оба будут корректны, поэтому нам совершенно безразлично какой из них нам вернется. Но хочу обратить внимание, на то, что если мы указываем у перемещаемого узла left_key = 1, то естественно, что ни впередистоящего, ни родительского узла у нас не будет, для чего используем дополнительное условие "ELSIF NEW.left_key = 1";
При перестроении дерева, дополнительным условием является "id <> OLD.id", это сделано потому, что мы не можем в триггере изменять запись, которую и так сейчас меняем.

Удаление записи

Вот с удалением сложнее всего. Во-первых, потому, что существует 2 принципа удаления узлов:

Удаление узла с потомками;
Удаление узла без потомков, при этом дочерние узлы смещаются по дереву на уровень вверх;

Во-вторых, мы не можем в запросе на удаление передавать параметры, что бы ограничить рекурсивный вызов триггера, впрочем, рекурсивный вызов триггера актуален только для случая удаления узла с потомками.

Делать универсальный триггер для обоих принципов удаления будет накладно, слишком много логики будет. Лучше все-таки два разных решения.

В первом решении (удаление узла с потомками) у нас будет следующий алгоритм:

Обновляем дочерние узлы на предмет установки поля (параметра) _trigger_for_delete;
Удаляем дочерние узлы;
Удаляем разрыв в ключах в дереве (перестаиваем дерево);

SQL код (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); -- Проверяем, стоит ли выполнять триггер: IF OLD._trigger_for_delete = TRUE THEN RETURN OLD; END IF; -- Помечаем на удаление дочерние узлы: 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; -- Удаляем помеченные узлы: DELETE FROM ns_tree WHERE tree = OLD.tree AND left_key > OLD.left_key AND right_key < OLD.right_key; -- Убираем разрыв в ключах: _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();

Во втором решении просто смещаем дочернее дерево на уровень вверх, и удаляем разрыв ключей.

SQL код (6) CREATE OR REPLACE FUNCTION ns_tree_after_delete_2_func() RETURNS trigger AS $BODY$ DECLARE BEGIN PERFORM lock_ns_tree(OLD.tree); -- Убираем разрыв в ключах и сдвигаем дочерние узлы: 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();

Собственно все. Осталось только проставить индексы (мне лениво сюда писать SQL команды, поэтому просто их озвучу):

Композитный не уникальный на поля (left_key, right_key, level, tree);
Не уникальный на поле (parent_id);

Наслаждайтесь ;-)