Немного о деревьях

[ewgRa]

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

[alekciy]

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

[dovg]

Производительность по сравнению с чем?
По теме: хотелось бы увидеть explain analyze запроса, где в where ltree.

И еще вопрос по производительности — индексы на ltree создаются как обычно? //помню, что в ip4r были нюансы.

[alekciy]

По сравнению с реализацией materialized path (как верно заметил brook) в приложении.

[KingOfNothing]

тоже интересно подобное сравнение! по сравнению, например, с www.sitepoint.com/hierarchical-data-database/

[brook]

По сути это и есть materialized path, только сбоку.

[alekciy]

Поэтому и возникает вопрос, на сколько указанное решение может быть быстрее чем реализацию MA в самом приложении.

[UncleAndy]

Плюс автору однозначно. Даже не предполагал о таких продвинутых возможностях postgresql. Относительно предмета разговора, попробую потестировать скорость данного варианта по сравнению с nested sets. В данном обзоре этого сильно не хватает.

[Fesor]

Предположу что в Nested Sets время вставки/переноса ноды будет существенно дольше.

[UncleAndy]

Это, в общем-то очевидно. Меня больше интересует сравнение скорости на выборке. У меня есть база KLADR в nested sets. Сейчас ее перегоняю в базу с ltree. Посмотрим, что получится.

[dovg]

Было бы классно, если бы выложили куда-нибудь конвертор. Думаю базу КЛАДР в качестве источника гео-данных используют многие.

[UncleAndy]

Конвертор из netsed sets в ltree? Или тектового KLADR в БД?

[dovg]

Из кладр в бд (ltree).

ps. я несколько лет назад хранил сконвертированный кладр в mysql практически в том виде, в котором он поставляется. Ради удобства обновления. Select был не быстрый.

[UncleAndy]

Такого у меня нет. Я сейчас конвертирую из БД с nested sets в БД с ltree. Но, думаю, что на основе нижеприведенных скриптов все это можно сделать.

[ewgRa]

Я делал проект связанный с КЛАДРом github.com/ewgRa/kladr

В инструкции по установке github.com/ewgRa/kladr/blob/master/install.postgresql.txt есть команды которые из DBF в csv базу перегоняют, потом csv загоняется в базу и дальше уже можно делать что хочется.

Непосредственно скрипт перевода из DBF в csv находится здесь github.com/ewgRa/lib/blob/master/scripts/dbf2csv.sh

Как протестируете отпишитесь, тоже есть мысль вместо parent_id использовать ltree.

[UncleAndy]

Вот конвертер из текстового формата в базу через SQL дамп — andyhost.ru/files/kladr2db.pl
Создание nested sets после формирования базы — andyhost.ru/files/kladr_nested_sets.pl

[dovg]

Спасибо.

[alekciy]

Вот какую штуку накопал: habrahabr.ru/blogs/development/47280/

[Isopropil]

Автору — огромное спасибо, не знал про этот модуль. Пошел тестить.

[pav]

Средствами бд для такого типа данных как то может быть реализован перенос ветвей. Или же на уровне приложения нужно у всех строк переносимой ветви путь перестраивать?

[ewgRa]

можно одним запросом по идее, примерно такого вида:

update tree_table set tree=('2.'||ltree2text(subpath(tree, 1)))::ltree where «tree» ~ '1.2.*';

[tick]

Химки и Мытищи — не Москва.

[dovg]

Печаль :)

[tick]

я так понимаю, что минусуют замкадыши :)

[akalend]

Автор имел ввиду иерархию страна — город — регион,
а минусуют прежде всего закомплексованные идтоты.

не знаю как Мытищи, но в Химках — Московская прописка,
но судя по тому, что в Мытищах находится МЛТИ(Московский Лесо Технический Институт), то очевидно что и прописка у близлежащих домов тоже Московская

[dovg]

>в Химках — Московская прописка
В Химках — прописка МО. Там еще есть Куркино и Новоподрезково, которые хоть и находятся географически севернее Химок, но являются Москвой.

[akalend]

Ну я не в курсе таких подробностей, у меня знакомая в Химках живет…
у нее Моск прописка, возможно она живет в одном из этих районов.
А сам я Мытищинский Лес-Тех заканчивал.

[shuler]

Я в своем текущем проекте начал использовать еще два интересных решения от PostgreSQL: window функции и тип данных hstore. Стоит о них написать?

Если hstore представляет собой банальное key-value поле, то window все же более интересен.

[UncleAndy]

Думаю, стоит однозначно. Я-бы лично был благодарен.

[bya]

Банальное hstore позволяет практически свести к нулю все недостатки реляционной алгебры. Это самое сильное расширение SQL.

[shuler]

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

Ведь это не альтернатива привычным типам данных, это просто «еще один тип», который позволяет совершать над ним специфичные операции. Т.е. это по сути тот же TEXT с более функциональным оператором LIKE.

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

[bya]

Без рекурсивных запросов статья не о чем. Рекурсивные данные требуют, чаще всего, рекурсии. Если не умете (postgres делает эти запросы отлично), то это Ваши проблемы.

[ewgRa]

При чем тут рекурсивные запросы? Вы осознали о чем статья?

[ztxn]

Рекусривные запросы — нативный способ обработки иерархических данных. Если я не ошибаюсь он даже стандартизирован SQL2003

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

[malexejev]

На самом деле, подозрительный способ делать древовидные запросы.
Если делать БД-независимый вариант, то этот способ не годится (надо юзать NS, MP и тд и тп). Если привязка к БД допустима — я бы не стал ставить какой-то непонятный контриб, который еще надо исследовать как написан и как перформит, а воспользовался бы CTE (Common Table Expressions), которые Postgre отлично поддерживает. Они даже немного стандартные — есть несколько других СУБД, в которых это реализовано. В результате у вас будет нормальное портируемое решение от авторов СУБД, доступное из коробки, а не кот в мешке.

[shuler]

У нас с коллегами есть свой php фреймворк.
Так вот там мы реализовали деревья следующим образом.

Для каждого дерева ведется две таблицы: таблица самих данных и таблица структуры.
Таблица данных не хранит никаких сведений об отношениях между записями.

Таблица же структуры хранит:
1. parented (как я понимаю одного его достаточно для написания рекурсивного запроса)
2. ltree поле «path»
3. rKey и lKey для Nested Sets

Таким образом, если мы делаем продукт на PostgreSQL, мы пользуемся ltree, иначе – другими средствами. И переход с одной СУБД на другую осуществляется без проблем.

[malexejev]

В смысле нормализации достаточно одного parentId, т.к. path по идее вычислимое поле.
Переход на другую СУБД подразумевает сохранение колонки path, я правильно понимаю? Только вы в этом случае другими способами ее считаете.

[UncleAndy]

rKey и lKey в данном случае вполне переносимы на другие субд, т.к. это обычные числовые поля. Комбинация parentid, rKey и lKey позволяет делать очень быстрые относительно сложные выборки, которые при наличии только parentid делались-бы и медленнее и неудобнее.

[malexejev]

Конечно, ведь это части Nested Sets. Выше написали про переезд поля «path» на другую СУБД без ltree. Решил уточнить, что именно имелось в виду.

[andy128k]

С сортировкой по ltree беда. Сортируется оно лексикографически. Составлять ltree из чисел неудобно.

[UncleAndy]

Заполнил базу данными из kladr (с детализацией до улиц — в районе 1 млн. записей) сделанными на основе nested sets. Поле tree сделал со значениями l_r из netsed sets (id большие — типа uuid) и проиндексировал (может и не нужно было — не знаю).

Во первых, индекс по этому полю занял 353 Мб при том что сама таблица в районе 143 Мб.

По первым-же тестам даже на глаз видно что вариант ltree работает существенно медленнее. Хотя, этого следовало ожидать. В nested sets запросы идут по индексируемым числовым полям. Сомневаюсь что быстрее возможно.

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

[dovg]

В запросах с ltree индексы используются? В мануале они почему-то создают два индекса, кстати:

CREATE INDEX path_gist_idx ON test USING gist(path);
CREATE INDEX path_idx ON test USING btree(path);

Можете показать explain analyze запроса с ltree?

[UncleAndy]

Конечно. Вот, например:

# explain select * from «world» where «tree» ~ '*{1}';
QUERY PLAN
— Seq Scan on world (cost=0.00..32690.29 rows=1039 width=123)
Filter: (tree ~ '*{1}'::lquery)
(2 rows)

[UncleAndy]

Предыдущий пост был с моим индексом. Создал по вашему описанию, получается вот так:

# explain select * from «world» where «tree» ~ '*{1}';
QUERY PLAN
— Bitmap Heap Scan on world (cost=109.28..3479.25 rows=1037 width=123)
Recheck Cond: (tree ~ '*{1}'::lquery)
-> Bitmap Index Scan on world_gist_idx (cost=0.00..109.02 rows=1037 width=0)
Index Cond: (tree ~ '*{1}'::lquery)
(4 rows)

[dovg]

Спасибо. А добавьте, пожалуйста, analyze, чтобы было видно фактическое время с индексом и без.

[UncleAndy]

Вот с индексом:

# explain analyze select * from «world» where «tree» ~ '*{1}';
QUERY PLAN
— Bitmap Heap Scan on world (cost=109.28..3479.25 rows=1037 width=123) (actual time=446.029..446.031 rows=1 loops=1)
Recheck Cond: (tree ~ '*{1}'::lquery)
-> Bitmap Index Scan on world_gist_idx (cost=0.00..109.02 rows=1037 width=0) (actual time=445.999..445.999 rows=1 loops=1)
Index Cond: (tree ~ '*{1}'::lquery)
Total runtime: 446.072 ms
(5 rows)

Вот БЕЗ индекса world_gist_idx (удален):

# explain analyze select * from «world» where «tree» ~ '*{1}';
QUERY PLAN
— Seq Scan on world (cost=0.00..32672.88 rows=1037 width=123) (actual time=178.695..486.991 rows=1 loops=1)
Filter: (tree ~ '*{1}'::lquery)
Total runtime: 487.025 ms
(3 rows)

Вообще, не очень показательно.

Я заметил что неправильно заполнил базу. Сейчас запущу заново ее формирование и завтра смогу сделать тесты с индексами и без них на нормальной базе и более сложных запросах.

[akalend]

Спасибо, было бы интересно

[UncleAndy]

Итак… Сделал более правильную базу. В таблице 1037350 строк — база КЛАДР до уровня улиц.

Проверяю 3 запроса:
1. Запрос для нахождения пути к элементу по id
2. Проверка вхождения одного элемента в другой по 2-м id
3. Нахождение всех детей данного элемента

Без индекса:

1. # explain analyze select w1.* from world w1, world w2 where w2.id='12b4603e-c0d4-11e0-a74e-9039b8fc67c8' and w1.tree @> w2.tree order by w1.tree;
QUERY PLAN
— Sort (cost=42339.34..42341.85 rows=1002 width=123) (actual time=1563.414..1563.414 rows=4 loops=1)
Sort Key: w1.tree
Sort Method: quicksort Memory: 17kB
-> Nested Loop (cost=0.00..42289.40 rows=1002 width=123) (actual time=278.245..1563.387 rows=4 loops=1)
Join Filter: (w1.tree @> w2.tree)
-> Index Scan using world_pkey on world w2 (cost=0.00..8.59 rows=1 width=83) (actual time=0.020..0.023 rows=1 loops=1)
Index Cond: (id = '12b4603e-c0d4-11e0-a74e-9039b8fc67c8'::uuid)
-> Seq Scan on world w1 (cost=0.00..29759.25 rows=1001725 width=123) (actual time=0.034..710.075 rows=1037350 loops=1)
Total runtime: 1563.470 ms
(9 rows)

2. # explain analyze select w1.* from world w1, world w2 where w2.id='12b4603e-c0d4-11e0-a74e-9039b8fc67c8' and w1.id='05bb280e-c0d4-11e0-bd30-c89f5da7af3e' and w1.tree @> w2.tree;
QUERY PLAN
— Nested Loop (cost=0.00..17.19 rows=1 width=123) (actual time=0.043..0.048 rows=1 loops=1)
Join Filter: (w1.tree @> w2.tree)
-> Index Scan using world_pkey on world w1 (cost=0.00..8.59 rows=1 width=123) (actual time=0.021..0.022 rows=1 loops=1)
Index Cond: (id = '05bb280e-c0d4-11e0-bd30-c89f5da7af3e'::uuid)
-> Index Scan using world_pkey on world w2 (cost=0.00..8.59 rows=1 width=83) (actual time=0.009..0.011 rows=1 loops=1)
Index Cond: (w2.id = '12b4603e-c0d4-11e0-a74e-9039b8fc67c8'::uuid)
Total runtime: 0.089 ms
(7 rows)

3. # explain analyze select w1.* from world w1, world w2 where w2.id='05bb280e-c0d4-11e0-bd30-c89f5da7af3e' and w1.tree <@ w2.tree;
QUERY PLAN
— Nested Loop (cost=0.00..42289.40 rows=1002 width=123) (actual time=1.099..1585.661 rows=11136 loops=1)
Join Filter: (w1.tree <@ w2.tree)
-> Index Scan using world_pkey on world w2 (cost=0.00..8.59 rows=1 width=83) (actual time=0.021..0.024 rows=1 loops=1)
Index Cond: (id = '05bb280e-c0d4-11e0-bd30-c89f5da7af3e'::uuid)
-> Seq Scan on world w1 (cost=0.00..29759.25 rows=1001725 width=123) (actual time=0.042..711.731 rows=1037350 loops=1)
Total runtime: 1591.608 ms
(6 rows)

Те-же запросы с индексом gist:

1. # explain analyze select w1.* from world w1, world w2 where w2.id='12b4603e-c0d4-11e0-a74e-9039b8fc67c8' and w1.tree @> w2.tree order by w1.tree;
QUERY PLAN
— Sort (cost=3550.78..3553.37 rows=1037 width=123) (actual time=0.803..0.806 rows=4 loops=1)
Sort Key: w1.tree
Sort Method: quicksort Memory: 17kB
-> Nested Loop (cost=109.27..3498.83 rows=1037 width=123) (actual time=0.732..0.784 rows=4 loops=1)
-> Index Scan using world_pkey on world w2 (cost=0.00..8.59 rows=1 width=83) (actual time=0.078..0.080 rows=1 loops=1)
Index Cond: (id = '12b4603e-c0d4-11e0-a74e-9039b8fc67c8'::uuid)
-> Bitmap Heap Scan on world w1 (cost=109.27..3477.28 rows=1037 width=123) (actual time=0.645..0.689 rows=4 loops=1)
Recheck Cond: (w1.tree @> w2.tree)
-> Bitmap Index Scan on world_gist_idx (cost=0.00..109.01 rows=1037 width=0) (actual time=0.639..0.639 rows=4 loops=1)
Index Cond: (w1.tree @> w2.tree)
Total runtime: 0.865 ms
(11 rows)

2. # explain analyze select w1.* from world w1, world w2 where w2.id='12b4603e-c0d4-11e0-a74e-9039b8fc67c8' and w1.id='05bb280e-c0d4-11e0-bd30-c89f5da7af3e' and w1.tree @> w2.tree;
QUERY PLAN
— Nested Loop (cost=0.00..17.19 rows=1 width=123) (actual time=0.041..0.046 rows=1 loops=1)
Join Filter: (w1.tree @> w2.tree)
-> Index Scan using world_pkey on world w1 (cost=0.00..8.59 rows=1 width=123) (actual time=0.021..0.022 rows=1 loops=1)
Index Cond: (id = '05bb280e-c0d4-11e0-bd30-c89f5da7af3e'::uuid)
-> Index Scan using world_pkey on world w2 (cost=0.00..8.59 rows=1 width=83) (actual time=0.010..0.012 rows=1 loops=1)
Index Cond: (w2.id = '12b4603e-c0d4-11e0-a74e-9039b8fc67c8'::uuid)
Total runtime: 0.090 ms
(7 rows)

3. # explain analyze select w1.* from world w1, world w2 where w2.id='05bb280e-c0d4-11e0-bd30-c89f5da7af3e' and w1.tree <@ w2.tree;
QUERY PLAN
— Nested Loop (cost=109.27..3498.83 rows=1037 width=123) (actual time=4.184..26.625 rows=11136 loops=1)
-> Index Scan using world_pkey on world w2 (cost=0.00..8.59 rows=1 width=83) (actual time=0.020..0.023 rows=1 loops=1)
Index Cond: (id = '05bb280e-c0d4-11e0-bd30-c89f5da7af3e'::uuid)
-> Bitmap Heap Scan on world w1 (cost=109.27..3477.28 rows=1037 width=123) (actual time=4.155..12.353 rows=11136 loops=1)
Recheck Cond: (w1.tree <@ w2.tree)
-> Bitmap Index Scan on world_gist_idx (cost=0.00..109.01 rows=1037 width=0) (actual time=4.083..4.083 rows=11136 loops=1)
Index Cond: (w1.tree <@ w2.tree)
Total runtime: 33.261 ms
(8 rows)

В общем, по этим результатам представляется достаточно очевидным, что использование gist индекса на поле типа ltree существенно помогает запросам с ним.

[zen]

Можете мне скинуть dump базы, я сейчас тестирую новые индексы для ltree, хочу производительность померять.

[akalend]

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

[rootkit]

спасибо за статью, очень полезно! Сам чуть не начал делать на MySQL, но столкнулся с проблемой — у одного потомка может быть несколько родителей… не подскажете, с пом. ltree получится реализовать такое?