Close

09.12.2015

Деревья в БД

Иерархические структуры данных не просто хранить в реляционных Базах Данных (БД).

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

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

Я выложу тут обзор возможных решений известных мне.

Полезное

Начну с полезной ссылки … вдруг вы сами хотите разобраться глубоко в этом вопросе

http://911datasets.org/index.php/Help:Tree_Structures

про хранение деревьев в реляционных БД.

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

собаковды рекомендуют; главные идеи

Чаще всего такую тему начинают с одной презентации, известной «всем».

Презентация по моделям данных для хранения «деревяшек» от чувака из Percona — непререкаемых лидеров в вопросах sql движков… и что же они (он) рекомендуют?:

чтобы уловить суть смотрите сразу на слайд № 69. — там сравнение описанных ранее способов.

Есть четыре  главных способа:

  • Adjacency List
  • Path Enumeration
  • Nested Sets
  • Closure Table

есть и другие… наиболее полный обзор тут http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database

по сложности операций с данными они имеют разный вес и приходится платить за это разную цену… в этом собственно и дилема — все же лучше прочитать презентацию подробно (для тех кто сразу перелистнул на слайд 69).

о задаче. задача такова: надо быстро выполнять операции:

  • вставка значений в дерево, их перенос в другую ветку
  • получение непосредственных «чилдов»
  • получение родителя и дедушек
  • получение всех вложенных листьев  (возможно, до некоторой глубины)
  • удаление веток в дереве

чтобы делать это быстро структура данных должна способствовать, а ведь мы же в БД….реляционной… вот и суть проблемы. пошли дальше.

ClosureTable выглядит наиболее серьёзно — делает  все необходимые операции быстро, но ! ClosureTable требует чтобы был специальный индекс, объём данных в котором ~N*N, т.е. не линеен (сильно растёт с ростом глубины дерева). Это плата за скорость — иногда ограничивает до полной неприемлемости всего метода.

ClosureTable (CT)

метод с примером описан тут

http://technobytz.com/closure_table_store_hierarchical_data.html

Итак, метод кажется привлекательным, но не все пользуются, например тут http://stackoverflow.com/questions/7497812/hierarchical-data-in-a-database-recursive-query-vs-closure-tables-vs-graph-da читают его избыточным в устройстве и рекомендуют использовать для решения задачи рекурсивные запросы.

вот еще пример запросов к CT

http://stackoverflow.com/questions/23030755/depth-in-mysql-and-closure-table-trees/23134613#23134613

опять рекомендуют иерархические запросы

http://stackoverflow.com/questions/6533742/print-a-complete-transitive-closure-tree/6534336#6534336

рекурсивные запросы — крутая фича БД которая отсутствует в большинстве движков. Она дорого стоит при обработке, хотя меньше чем хранимая процедура с циклами. На ExecutionPlan рекурсивного запроса сложно влиять в процессе оптимизации запроса.

Например, в mysql жалкие попытки работы с деревьями выглядят убого http://stackoverflow.com/questions/1316126/how-can-i-find-all-siblings-to-my-node-and-its-anchestors-in-a-hierarchical-cate

по Mysql есть хорошая книжка «Managing Hierarchical Data in MySQL»

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

и ClosureTable там нет — «геморно».

ORM

ORM = Object Relation Mapper (ing)

Это подмножество решений позволяет отображать наш объектный мир ПО на плоскую реляционную БД. и работать с разными БД в качестве бекендов.

Хранение иерархий может решать на уровне ORM. Так то же имеется ?

PHP

в PHP есть такая шняга штука Doctrine 2. Вот пример кода для ClosureTable

http://stackoverflow.com/questions/29979859/doctrine-2-tree-extension-closure-table/29981688#29981688

и как бы я не ругал PHP — для него есть не плохие либы…

хорошо, что не php единым — Python

прекрасный язык, прекрасные либы, все самое вкусное… не  без магии, но красиво: Peewee http://docs.peewee-orm.com/en/latest/ — мой любимый.

для него есть коллекция расширений, например шикарное расширения для sqlite бекенда:

Querying Tree Structures in SQLite using Python and the Transitive Closure Extension  http://charlesleifer.com/blog/querying-tree-structures-in-sqlite-using-python-and-the-transitive-closure-extension/

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

TODO  пример кода SQL и для peewee

 

Решения на уровне самой БД

сначала напишу, что сам пользовал.

Transact SQL(MS)

hierarchyid — системный тип базы данных в  Transact-SQL

статья http://habrahabr.ru/post/27774/

рекомендация http://stackoverflow.com/questions/17302716/hierarchical-sql-data-recursive-cte-vs-hierarchyid-vs-closure-table/17308114#17308114

коменты к статье на хабре — не хуже самой статьи отражают проблематику.

PostgresSQL

ltree

в PG из коробки есть хорошая основа для метода «Path Enumeration» за счёт работы с GIST индексами и полем ltree.

дока : http://www.postgresql.org/docs/9.1/static/ltree.html

статья на хабре по русски: http://habrahabr.ru/post/130371/

метод хорош (не плох), но без либы специальной юзать это не удобно — нужна либа. я не нашёл, круто было бы если бы pqlib сам бы умел… ээх, мечты.

Рекурсивные запросы PG

в PG есть рекурсивные запросы, а значит можно хоть на ушах ходить обходить в глубину, ширину свои структуры с простыми полями parent… это расхолаживает и радует.

выглядит это примерно так http://stackoverflow.com/questions/28688264/how-to-traverse-a-hierarchical-tree-structure-structure-backwards-using-recursiv/28709934#28709934

Вы скажете: «хорошо,  PG умеет это. а я хочу работать в tornado с БД асинхронно, можно это удобно сделать ?». ответ: ДА.

momoko PG  tornado extention  — пользуйтесь на здоровье. https://github.com/FSX/momoko/blob/master/docs/tutorial.rst

давненько для себя я сделал один вывод: если ты выбрал PG — у тебя все будет. мегаплатформа, он будет расти в твоих глазах вместе с тобой (только не лезь в код, я пробовал… расстроишься).

TODO привести пример рекурсивного запроса по иерархии в PG

Потом напишу что сам НЕ пользовал, но видел глазами: 

MySql

Посмотрите тут примеры

http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/

Oracle

CONNECT BY

http://www.ypl.com/oracle/sql/hierarchical_queries/html_deep/index.html

Послесловие

Напоследок рекомендую посмотреть этот pdf  для саморазвития. https://vadimtropashko.files.wordpress.com/2011/07/ch5.pdf

Как вам матричная форма адресации ? Nested Intervals ?

Исследования в этой области еще имеют потенциал, возможно именно Вы придумаете ещё один самый лучший способ быстро работать с деревом в БД, придумаете свой способ, на базе …. ну не знаю, например на базе математического аппарата теории суперструн 🙂

PS

хорошая либа для питона

https://libtree.readthedocs.org/en/latest/index.html
код с расширением для sqlite

В мои планы входит «сравнить производительность метода recursive select для PG и метода AList из библиотеки tree для Python и метода на ltree поставки PG», но не хватет времени. Тема дляДиплома студенту ? 

Библиотека доступа к иерархическим страктурам, хранимым в реляционных БД.

————

а вот коммент чувака по поводу производительности PG libtree — https://www.reddit.com/r/Python/comments/3qk51f/showcase_libtree_simple_fast_and_powerful_tree/?

Он утрверждает, по реальным тестам , что масштабируемость до миллиона узлов характерна для SELECT, вставка естественно замедляется при росте дерева «в глубину».

 

11 Comments on “Деревья в БД

Роман
09.12.2015 в 18:57

А чем графовые БД не устраивают? Например, TitanDB. Позволяет эффективно хранить структуры произвольной связности. Лично я использую язык запросов Gremlin (под эгидой TinkerPop), но есть ещё SPARQL, который очень похож на SQL. В последней версии Gremlin тоже поддерживает нечто похожее на sparql. 6e+6 вершин и >18e+6 рёбер на одной машине с 16 гб памяти вполне держит. К вершинам можно присандаливать свойства (которые могут иметь сложную структуру). Есть ORM. Правда, лично для меня он не подошел и пришлось сделать порт Gremlin для Python (https://github.com/windj007/python-gremlin-rest).

Ответить
Михаил Павлов
15.12.2015 в 11:55

Ром, привет.
1) TitanDB в первый раз вижу, спасибо. я как-то графовые бд вот не затронл пока. с него начну.
2) если не в реляционной бд хранить, то уже много решений, тут согласен. Можно привести много примеров. а статья про то, как оставаясь в рамках классической реляционной БД, работать эффективно хотябы с дервьями.
статья обзорно описывает со ссылками известные способы предствления дерева в реляционном виде и показывает, как можно средствами rdbms (возможно уникальными средствами для конкретной БД) решать задачи выбора узлов.

3) мы как-то написали свою хранилку древьев с планаризатором (инкрементальная планаризация по мере изменения дерева делалась, без полного обхода, сохраняли дерево планаризованным)
об этом я написал тут
а тут я попробовал его сконвертировать с питона на JS и для этого даже транслятор пришлось доработать
НО! это оказалось фиговой идеей по сравнению с обычной БД.
в продакшене кроме этой штуки нужно:
* бекапы делать консистентные
* масштабировать как-то так, чтобы не учить никого а дать тупо туториал
* у нас в системе хочется иметь связанные данные хранимые в обычной БД бе выкрутасов
* есть представления, оказывается (внезапно), для которых планаризация это не главное
* чтобы делать рапределенную версию , то это иная стоимостьрешения, а мы уже так делать её не хотим.

получается, что в нашем случае проще всё таки посмотреть в сторону типовой RDBMS.

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

Ответить
Роман
17.12.2015 в 12:19

Прошу прощения, не туда комментарий добавился. см. https://srv.nppsatek.ru/blogs/?p=383#comment-163

Ответить
Роман
16.12.2015 в 17:34

Судя по тому, что ты написал, складывается впечатление, что наоборот, РСУБД вам вообще не подходят. РСУБД проще всех остальных только тем, что там есть ОРМ и привычные термины/подход к проектированию. В свою очередь, ОРМ даёт серьёзный выигрыш только в случае более-менее сложных моделей, когда больше 20 таблиц (зависит от квалификации разработчиков). Подход к проектированию в графовой бд хоть и отличается, но вполне усваивается за считанные дни.

joinjoinjoinjoin*join делается суперэффективно и время исполнения таких запросов не зависит от объёма данных (зависит только от количества инциндентных рёбер того же типа). Это достигается за счёт хранения локальных индексов (в графовой бд в каждой вершине есть свой набор индексов, позволяющий эффективно отбирать соседей). Вот тут приведено исследование авторов TitanDB на эту тему и то, как они в своей БД её решают http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/

А какая аналитика тебя интересует?

Ответить
Михаил Павлов
27.12.2015 в 23:09

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

возможно открою для себя после этого целый новый пласт алгоритмов?!

> какая аналитика интересует?
не могу сказать. я бы хотел сделать на основе этой штуки основу и решить на ней свои задачи, создав систему «СУП», мы так её называем. далее я открываю API к системе для внешних сервисов. им понадибится возможно данные в разных формах, не обязательно как я дам.
я бы хотел гибкость здесь.
внешние сервисы будут клепать новые представления и конечно хочется чтобы не они придумывали как сделать индекс и по нему строить. а использовать максимально наш функционал для получения данных.

Ответить
Роман
16.01.2016 в 19:51

Мало что сделанное слишком общим, хорошо работает на всех задачах. Наверное, имеет смысл либо использовать sql-решение, поддерживающее запуск на нескольких узлах (а вообще, каков объём данных предполагается на один сервис в среднем? может быть проще предложить несколько вариантов хранилища, как это делает amazon?), либо предложить разработчикам сервисов конструктор, который будет строить схему БД за них.

Кстати, для кассандры есть ещё какой-то ORM: https://cqlengine.readthedocs.org/en/latest/
Про ничего не могу сказать, я использую официальный драйвер с cql

Ответить
Михаил Павлов
18.01.2016 в 16:35

мне этот «ORM» Серега Алексеев показывал. там промитивно внутри все. не знаю пока я не склонен юзать его. а уж как он — это его дело.
мы тожеифициальный драйвер используем. смотри кстати последний мой пост от вчера/позавчера. про стыковку CQL + Thrift.

Кстати в G+ я постил про выход нового бешеного крутого релиза PG.
который опять не подвел ожидания.

Ответить
Роман
18.01.2016 в 16:54

В том посте про cql+thrift не сказано самое главное: зачем это нужно? Если для интроспекции, то гораздо лучше организовать дополнительное хранилище метаинформации, пусть в той же кассандре. Других идей по поводу применения этого гибрида что то не приходит в голову.

Михаил Павлов
20.01.2016 в 10:31

> В том посте про cql+thrift не сказано самое главное: зачем это нужно?

Мне нравится Low level api, он позволяет поверх внешних по отношению к касандре сервисов организовать «свой CQL».
Родной CQL не имеет Join и вообще ограничен. ORM опять же слаб — не то слово.

Можно конечно строить новый CQL поверх CQL, собст…но. Но Low level API позволяет потенциально куда больше.

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

Реально, я проверил их оба и решил «использовать только CQL, по крайней мере пока. А Low level хоть и гибкий — в таком виде, как он сейчас есть, смысла не имеет для нас»

Ответить
Роман
20.01.2016 в 11:31

Thrift — deprecated, это значит, что его нельзя использовать в новых проектах. А Join в Cassandra — признак плохого дизайна базы. Используй иерархические ключи, это эффективно и естественно для неё. Соединение разных таблиц, если всё-таки оно нужно, гораздо лучше имитировать на клиенте, т.к. есть возможность эффективнее использовать асинхронные возможности драйвера, IMHO.

Ответить
Роман
20.01.2016 в 11:33

CQL очень хорошо спроектирован: он позволяет ровно то, что позволяет внутренее устройство кассандры. Если что-то CQL не позволяет, то это либо знак, что не надо это делать с помощью кассандры, либо надо попробовать перепроектировать БД, вынеся минимальную логику на клиентскую часть.

Ответить

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *