DOC.PROTOTYPES.RU

Главная > Базы данных > Деревья SQL > Nested Sets > практика SQL >

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

Задача

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

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

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

База данных - 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 варианта добаления узла в дерево:

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

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

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

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

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

Основными параметрами принуждающие его к каким либо действиям являются 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();

Пояснения:

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

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

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

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

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

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 команды, поэтому просто их озвучу):

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

Сергей Томулевич aka Phoinix (02.07.2009 г.)
Copyright © 2011 Сергей Томулевич