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

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

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

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

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

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

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

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

8 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

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

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

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

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

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

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

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

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

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

18 Карта связей

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

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

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

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

23 Количество одинаковых путей Если из объекта 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

24 Добавляем связь 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) == [ ]

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

26 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

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

28 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

29 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

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

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

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