'

Построение индекса по иерархии записей в реляционной БД

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

Стандартные средства Photo by http://www.flickr.com/photos/shannonpatrick17/


Слайд 5

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


Слайд 6

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


Слайд 7

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 SELECT next.employee_id, next.name FROM employee as next INNER JOIN t ON t.employee_id = next.manager ) SELECT name FROM t


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

Lineage (линидж) Источник - http://www.sqlteam.com/article/more-trees-hierarchies-in-sql Denis Eaton-Hogg Bobbi Flekman Ian Faith David St. Hubbins Nigel Tufnel Derek Smalls Индекс Данные


Слайд 13

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


Слайд 14

Левые и правые индексы Источник - http://www.osp.ru/os/2003/04/182942/ 1 Предприятие 2 Управление 3 Инфраструктура 5 Энергия 6 Сервисные услуги 4 Производство 7 Месторождение А 8 Месторождение Б Индекс Данные 1 2 3 4 9 5 6 7 8 10 16 15 11 12 13 14


Слайд 15

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


Слайд 16

Карта связей Image by http://www.flickr.com/photos/36041246@N00/3344881664/


Слайд 17

Карта связей


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

SQL: добавление путей UPDATE RelationMap SET count = om.count + st.count FROM @tSubTree st JOIN RelationMap om ON st.child = om.child AND st.parent = om.parent AND st.distance = om.distance   INSERT INTO RelationMap SELECT st.child, st.parent, st.distance, st.count FROM @tSubTree st LEFT JOIN RelationMap om ON st.child = om.child AND st.parent = om.parent AND st.distance = om.distance WHERE om.child IS NULL


Слайд 28

SQL: удаление путей UPDATE RelationMap SET count = om.count - st.count FROM @tSubTree st JOIN RelationMap om ON st.child = om.child AND st.parent = om.parent AND st.distance = om.distance   DELETE FROM RelationMap WHERE count = 0


Слайд 29

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


Слайд 30

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


Слайд 31

В заключение Придумали сами. Используем уже несколько лет. И вам советуем. ? Подробная статья – на сайте: http://blogs.byte-force.com/files/folders/articles_ru/entry1148.aspx


×

HTML:





Ссылка: