Построение индекса по иерархии записей в реляционной БД Андрей Майоров. BYTE-force

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

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

Зачем? Выбирать сотрудников из отдела. Товары из раздела каталога. Статьи из раздела с подразделами....

Стандартные средства Photo by

CONNECT BY в Oracle Выбирает работника по имени John, его подчиненных, подчиненных его подчиненных, etc. Псевдоколонка LEVEL позволяет ограничить удаленность от стартовой записи. SELECT name FROM employee START WITH name = 'John' CONNECT BY PRIOR employee_id = manager

Недостатки CONNECT BY Выполняется столько запросов, сколько существует уровней иерархии. Довольно сложно делать иерархии, содержащие записи из разных таблиц. Подход работает только в Oracle.

Common Table Expressions Первый SELECT внутри CTE заменяет START WITH, второй – CONNECT BY PRIOR. WITH t( employee, name ) AS ( SELECT employee_id, name FROM employee WHERE name = 'John' UNION ALL SELECTnext.employee_id, next.name FROM employee as next INNER JOIN t ON t.employee_id = next.manager ) SELECT name FROM t

Сравним CTE с CONNECT BY Скорость работы должна быть сравнимой. Гетерогенные иерархии строятся проще. При помощи оператора UNION ALL можно присоединять к иерархии разные таблицы, каждый раз используя специфический критерий связи. CTE поддерживаются основными коммерческими СУБД, но не популярными СУБД с открытым кодом (MySQL, Firebird, PostgreSQL и др.).

Построение иерархии вручную Поддержку рекурсивных запросов можно эмулировать вручную, используя специальную временную таблицу. Такой подход похож на CTE. Может быть реализован в любой базе данных. Ручной метод не позволяет надеятся на оптимизацию со стороны СУБД, которая может существовать для штатных средств.

Стандартные средства... Хороши Не требуют дополнительных таблиц Очень просто вставлять и удалять записи Плохи Сопряжены с итеративной выборкой связанных записей. Даже с индексом по полю связи, это требует столько же выборок, сколько есть уровней иерархии.

Как ускорить выборку? Решение – самостоятельно сформировать «индекс» во вспомогательном поле или таблице. Варианты хранения индекса: –Lineage (materialized path) –Левые и правые индексы –Карта связей

Lineage (линидж) Источник - Denis Eaton-Hogg Bobbi Flekman Ian Faith David St. Hubbins Nigel Tufnel Derek Smalls Индекс Данные

Lineage За Все просто и понятно. Легко добавлять детей к любому узлу. Против Достаточно сложно «перевесить» узел – надо пересчитывать пути для всей ветки. Годится только для деревьев. Выборки сопряжены со строковыми операциями.

Левые и правые индексы Источник Предприятие 2 Управление 3 Инфраструктура 5 Энергия 6 Сервисные услуги 4 Производство 7 Месторождение А 8 Месторождение Б Индекс Данные

Левые и правые индексы За Выборки используют сравнения целых чисел. Против Очень сложно вставить узел в середину. Годится только для деревьев.

Карта связей Image by

Карта связей

За Несколько родителей у узла. Выборка проводится «просто по индексу». Данные можно хранить в covering index. Позволяет делать гетерогенные иерархии Есть методика эффективного обновления индекса. Против При большой вложенности индексная таблица может быть очень большой.

Рассмотрим граф Выше – родители, ниже – дети. Пути считаем идущими снизу вверх. Длина пути равна количеству ребер. Есть пути с одинаковой длиной

Новая связь между 7 и 8 Появляются новые пути: Прямой путь из 8 в 7 (длина 1). Пути из 8 через 7 во все объекты, в которые можно попасть из 7. Длина всех путей будет на единицу больше, чем из A

Новая связь между 7 и 8 Прямой путь из 8 в 7 (длина 1). Из 8 ко всем предкам объекта 7 (длина + 1). Из 7 ко всем потомкам объекта 8 (длина + 1). Отовсюду, докуда есть пути из 7, мы теперь можем попасть в 9 и A, и наоборот. Длина пути между 9 и 3 будет равна сумме длин путей до 8 и от 7 соответственно плюс A A B

Количество одинаковых путей Если из объекта 7 в объект x можно попасть cx путями с длиной dx, а из объекта y в объект 8 – cy путями с длиной dy, то из y в x можно будет попасть cx*cy путями с длиной dx+dy A A B x x y y Путей: 1 * 2 = 2 Длина: = 4

Добавляем связь parent - child Появляется следующий набор путей: foreach x in descendants( child ), dx in distances( x, child ), y in ancestors( parent ), dy in distances( parent, y ) добавляется count(x,child,dx)*count(parent,y,dy) путей между x и y с длиной dx+dy+1. count(x,y,d) – количество различных путей из x в y с длиной d ancestors(x) и descendants(x) содержат x distances(x, x) == [ ]

В нашей схеме данных … … RelationMap содержит все связи между всеми объектами на данный момент времени. Значит ее можно использовать для построения множества новых путей.

SQL: множество новых путей SELECTd.child,a.parent, a.distance + d.distance + 1, sum( a.count * d.count ) FROM( SELECT* FROM RelationMap WHEREchild 0, 1 ) AS a, ( SELECT* FROM RelationMap WHEREparent 0, 1 ) AS d GROUP BY d.object, a.ancestor, a.distance + d.distance + 1

Принципы работы запроса Выбираются все пути, в – потомок. К выборке добавляется путь от этого объекта к самому себе с длиной 0 и количеством повторений 1. Выбираются все пути, в – предок. Также добавляется путь к самому себе. Делается декартово произведение этих двух выборок, и получается множество всех возможных путей от объектов «сверху» к объектам «снизу». Длины путей складываются, количество повторений перемножается. В результате складывания длин путей, мы можем получить новые наборы путей с одинаковой длиной. Поэтому мы группируем набор записей и суммируем количество повторений внутри групп.

SQL: добавление путей UPDATERelationMap SETcount = om.count + st.count st JOIN RelationMap om ONst.child = om.child ANDst.parent = om.parent ANDst.distance = om.distance INSERTINTO RelationMap SELECTst.child, st.parent, st.distance, st.count st LEFT JOIN RelationMap om ONst.child = om.child ANDst.parent = om.parent ANDst.distance = om.distance WHEREom.child IS NULL

SQL: удаление путей UPDATERelationMap SETcount = om.count - st.count st JOIN RelationMap om ONst.child = om.child ANDst.parent = om.parent ANDst.distance = om.distance DELETE FROMRelationMap WHEREcount = 0

Особенности алгоритма Алгоритм не позволяет надежно вставлять несколько связей одновременно. Каждую вставку нужно просчитать последовательно. Порядок выполнения вставок не важен. Карта путей помогает избежать появления циклов в графе объектов. Для этого достаточно проверить, не существует ли уже путей, ведущих (т.е. в обратном направлении). Все это очень удобно делать в триггерах на таблице связей.

Гетерогенный случай Возможны случаи, когда логическая иерархия покрывает несколько таблиц с данными. Основной сложностью в этом случае является построение такой таблицы RelationMap, которая могла бы хранить ссылки на объекты разных типов. Обобщающую таблицу с путями, можно поддерживать тем же способом – при помощи триггеров на таблицах со связями.

В заключение Придумали сами. Используем уже несколько лет. И вам советуем. Подробная статья – на сайте: