Оптимизации на базе Таблицы замыканий (Closure Table)

Таблица замыканий (Closure Table) - прекрасный паттерн, предназначенный для хранения древовидных данных в реляционной БД. Теории по нему много, поэтому давайте рассмотрим практику, разбавив ее некоторыми авторскими “фишечками”. За примерами далеко ходить не будем - моя PinaCMS2 как раз хранит структуру страниц сайта с использованием данного подхода.

Ниже в этой статье мы сведем выборку товаров категории к покрывающему индексу, предложим простой и эффективный диспетчер, а также научимся на лету скрывать и отображать категории на базе отсутствия и наличия соответствующих складских остатков.

Основная и вспомогательная таблицы

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

Пример структуры таблицы resource:

Поле	Тип	Назначение
id	INT	Идентификатор
title	VARCHAR	Название страницы
resource	VARCHAR	Часть URL страницы (slug)
parent_id	INT	Идентификатор родительской страницы
resource_type_id	INT	Идентификатор типа страницы
enabled	enum(‘Y’, ‘N’)	Активность страницы
order	INT	Порядковый номер

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

Запишем данную структуру в компактном виде:

resource (id, title, resource, parent_id, resource_type_id, enabled, order)

Вспомогательная таблица хранит соединения всех родителей со всеми детьми:

resource_tree (resource_id, resource_parent_id, length)

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

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

Триггер, запускающийся после вставки в основную таблицу, будет иметь вид:

IF (NEW.parent_id > 0) THEN
    INSERT INTO resource_tree (resource_parent_id, resource_id, length)
    SELECT resource_tree.resource_parent_id, NEW.id, resource_tree.length + 1
    FROM resource_tree WHERE resource_id = NEW.parent_id
    UNION
    SELECT NEW.parent_id, NEW.id, 1;
ELSE
    INSERT INTO resource_tree (resource_parent_id, resource_id, length)
    SELECT NEW.parent_id, NEW.id, 1;
END IF;

Триггер на удаление из основной таблицы:

DELETE t1 FROM resource_tree t1
JOIN resource_tree t2 ON t1.resource_id = t2.resource_id AND t2.resource_parent_id = OLD.id
JOIN resource_tree t3 ON t1.resource_parent_id = t3.resource_parent_id AND t3.resource_id = OLD.id;
DELETE FROM resource_tree WHERE resource_id = OLD.id;
DELETE FROM resource_tree WHERE resource_parent_id = OLD.id;

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

Создав вспомогательную таблицу и обеспечив согласованность данных, мы получаем доступ к простым и быстрым выборкам с большим потенциалом к улучшению.

Как получить хлебные крошки одним запросом

Просто выбираем родителей в порядке удаленности от текущего ресурса:

SELECT r.id, r.title
FROM resource_tree rt
INNER JOIN resource_r ON r.id = rt.resource_parent_id
WHERE rt.resource_id = :id
ORDER BY rt.length

Нужен ли индекс для этого запроса? Обычно глубина вложенности ресурса не слишком большая, что обуславливает небольшое количество элементов в выборке, поэтому для данного запроса важно быстро искать по полю resource_id, но не так важно быстро сортировать по полю length. В таблице уже присутствует первичный индекс (PRIMARY KEY) по полям (resource_id, resource_parent_id), первый элемент этого индекса может быть использован для быстрой фильтрации по полю resource_id, поэтому дополнительный индекс для данного запроса не нужен.

Получить активные товары из категории и ее подкатегорий в заданном маркетологом порядке

У нас есть поля order, enabled и resource_type_id, которые используются для получения списка активных товаров текущей категории. Наивный запрос мог бы быть таким:

SELECT r.id, r.title
FROM resource_tree rt
INNER JOIN resource r ON r.id = rt.resource_id
WHERE rt.resource_parent_id = :id
AND r.resource_type_id = :product_resource_type_id
AND r.enabled = ‘Y’
ORDER BY r.order ASC

В чем проблема этого запроса?

Чтобы сделать выборку, базе данных необходимо:

отфильтровать таблицу товаров по полям resource_type_id и enabled,
отфильтровать нашу вспомогательную таблицу resource_tree по полю resource_parent_id,
найти их пересечение,
а затем отсортировать полученный результат по полю order.

Это побуждает базу данных использовать временную таблицу (using temporary) и сортировать ее без использования индекса (using filesort).

Как же улучшить ситуацию? Давайте пойдем по пути денормализации и продублируем поля resource_type_id, enabled и order в таблице resource_tree.

resource_tree (resource_id, resource_parent_id, length, resource_enabled, resource_type_id, resource_order)

Просто добавить поля недостаточно - нужно немного изменить триггеры, поддерживающие вспомогательную таблицу в согласованном состоянии.

Теперь мы можем добавить индекс (resource_parent_id, resource_type_id, resource_enabled, resource_order) и переделать запрос таким образом, чтобы все фильтры и сортировка проводились по этому индексу:

SELECT r.id, r.title
FROM resource_tree rt
INNER JOIN resource r ON r.id = rt.resource_id
WHERE rt.resource_parent_id = :id
AND rt.resource_type_id = :product_resource_type_id
AND rt.resource_enabled = ‘Y’
ORDER BY rt.resource_order ASC

Фактически мы свели часто выполняемый запрос к запросу по покрывающему индексу.

Роутинг

Формирование полного адреса ресурса (странички) схоже с формированием хлебных крошек. Мы получаем родителей странички в порядке удаленности от корня и складываем их поля resource в цепочку, добавляя в конец поле resource самой странички. URL выводятся часто, меняются редко, поэтому можно хранить их в отдельной табличке и автоматически пересобирать с помощью триггеров.

Табличка имеет структуру:

resource_url (resource_id, resource_type_id, url, resource_enabled)

Приятный бонус этой таблицы, что поддерживать данные в ней можно тоже целиком с помощью триггеров.

Запрос из триггера на создание ресурса имеет простой вид:

INSERT INTO resource_url SET resource_id = NEW.id, resource_type_id = NEW.resource_type_id, resource_enabled = NEW.enabled, url = (
    SELECT concat(IFNULL(concat(group_concat(rp.resource ORDER BY rt.length DESC SEPARATOR '/'), '/'),''), r.resource)
    FROM resource r
    LEFT JOIN resource_tree rt ON rt.resource_id = r.id
    LEFT JOIN resource rp ON rp.id = rt.resource_parent_id
    WHERE r.id = NEW.id
    GROUP BY r.id
    LIMIT 1
);

Запрос из триггера на обновление ресурса сложнее:

UPDATE resource_url ru
INNER JOIN (
    SELECT resource_id FROM resource_tree WHERE resource_parent_id = NEW.id
    UNION
    SELECT NEW.id as resource_id
) as rt_link ON rt_link.resource_id = ru.resource_id
INNER JOIN (
    SELECT r.id, concat(IFNULL(concat(group_concat(rp.resource ORDER BY rt.length DESC SEPARATOR '/'), '/'),''), r.resource) as url
    FROM resource r
    INNER JOIN (
        SELECT resource_tree.resource_id
        FROM resource_tree
        WHERE resource_tree.resource_parent_id = NEW.id
        UNION
        SELECT NEW.id as resource_id
    ) as rt_link ON rt_link.resource_id = r.id
    LEFT JOIN resource_tree rt ON rt.resource_id = r.id
    LEFT JOIN resource rp ON rp.id = rt.resource_parent_id
    GROUP BY r.id
) d ON d.id = ru.resource_id
SET ru.url = d.url;

Автоматически скрываем категории, в которых нет товара в наличии

Благодаря таблице замыканий мы умеем быстро вычислять цепочки, ведущие из корня дерева в любой узел, поэтому для каждого узла мы можем эффективно агрегировать значения вложенных веток.

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

resource_amount (resource_id, amount)

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

IF (OLD.parent_id <> NEW.parent_id) THEN
    SET @amount = (SELECT amount FROM resource_amount WHERE resource_id = NEW.id);
    IF (@amount <> 0) THEN
        UPDATE resource_amount ra INNER JOIN (
            SELECT resource_parent_id FROM resource_tree rt 
            WHERE resource_id = OLD.parent_id 
            UNION 
            SELECT OLD.parent_id as resource_parent_id
        ) parents on parents.resource_parent_id = ra.resource_id 
        SET amount = amount - @amount;
        UPDATE resource_amount ra INNER JOIN (
            SELECT resource_parent_id FROM resource_tree rt 
            WHERE resource_id = NEW.parent_id 
            UNION 
            SELECT NEW.parent_id as resource_parent_id
        ) parents on parents.resource_parent_id = ra.resource_id 
        SET amount = amount + @amount;
    END IF;
END IF;

При поступлении товара на склад нам достаточно прибавить его значение цепочке из родительских узлов:

UPDATE resource_amount ra
INNER JOIN (
    SELECT resource_parent_id FROM resource_tree rt 
    WHERE resource_id = NEW.resource_id
    UNION 
    SELECT NEW.resource_id as resource_parent_id
) parents ON parents.resource_parent_id = ra.resource_id
SET ra.amount = ra.amount + NEW.amount;

У агрегирования общего количества товара на складе есть проблемы. В глубоком ветвистом дереве в узлах, близких к корневому, могут скапливаться суммы, превышающие максимальное значение для типа INT. Но для фильтрации категорий по наличию нам не важно знать точное количество складских остатков, достаточно понимать, оно больше нуля или меньше, поэтому в боевом коде мы агрегируем не остатки, а количество вложенных узлов, которые доступны на складе.

Теперь, чтобы отобрать категории в наличии, нам достаточно сделать один дополнительный JOIN

SELECT r.* FROM resource r
INNER JOIN resource_amount ra ON ra.resource_id = r.resource_id AND ra.amount > 0

Что это было: перенос логики в БД или поддержка согласованности данных в БД?

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

Является ли создание дополнительных таблиц с приведенными в примере триггерами переносом части бизнес-логики на сторону БД? Я считаю, что нет, так как мы в общем-то обеспечиваем эффективную денормализацию данных и поддержку согласованности данных в рамках этой денормализации.