Комментарии 54
Очень полезный модуль. Особенно приятно, что разработчики модуля из России, отечественная разработка.
НЛО прилетело и опубликовало эту надпись здесь
Хорошо бы сравнить произвоительность такого решения. Собтвенно сам давно уже хотел погонять этот модуль, но вот руки ни как не доходят.
Производительность по сравнению с чем?
По теме: хотелось бы увидеть explain analyze запроса, где в where ltree.
И еще вопрос по производительности — индексы на ltree создаются как обычно? //помню, что в ip4r были нюансы.
По теме: хотелось бы увидеть explain analyze запроса, где в where ltree.
И еще вопрос по производительности — индексы на ltree создаются как обычно? //помню, что в ip4r были нюансы.
тоже интересно подобное сравнение! по сравнению, например, с www.sitepoint.com/hierarchical-data-database/
По сути это и есть materialized path, только сбоку.
Плюс автору однозначно. Даже не предполагал о таких продвинутых возможностях postgresql. Относительно предмета разговора, попробую потестировать скорость данного варианта по сравнению с nested sets. В данном обзоре этого сильно не хватает.
Предположу что в Nested Sets время вставки/переноса ноды будет существенно дольше.
Это, в общем-то очевидно. Меня больше интересует сравнение скорости на выборке. У меня есть база KLADR в nested sets. Сейчас ее перегоняю в базу с ltree. Посмотрим, что получится.
Было бы классно, если бы выложили куда-нибудь конвертор. Думаю базу КЛАДР в качестве источника гео-данных используют многие.
Конвертор из netsed sets в ltree? Или тектового KLADR в БД?
Из кладр в бд (ltree).
ps. я несколько лет назад хранил сконвертированный кладр в mysql практически в том виде, в котором он поставляется. Ради удобства обновления. Select был не быстрый.
ps. я несколько лет назад хранил сконвертированный кладр в mysql практически в том виде, в котором он поставляется. Ради удобства обновления. Select был не быстрый.
Такого у меня нет. Я сейчас конвертирую из БД с nested sets в БД с ltree. Но, думаю, что на основе нижеприведенных скриптов все это можно сделать.
Я делал проект связанный с КЛАДРом 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.
В инструкции по установке 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.
Вот конвертер из текстового формата в базу через SQL дамп — andyhost.ru/files/kladr2db.pl
Создание nested sets после формирования базы — andyhost.ru/files/kladr_nested_sets.pl
Создание nested sets после формирования базы — andyhost.ru/files/kladr_nested_sets.pl
Вот какую штуку накопал: habrahabr.ru/blogs/development/47280/
Автору — огромное спасибо, не знал про этот модуль. Пошел тестить.
Средствами бд для такого типа данных как то может быть реализован перенос ветвей. Или же на уровне приложения нужно у всех строк переносимой ветви путь перестраивать?
Химки и Мытищи — не Москва.
Печаль :)
я так понимаю, что минусуют замкадыши :)
Автор имел ввиду иерархию страна — город — регион,
а минусуют прежде всего закомплексованные идтоты.
не знаю как Мытищи, но в Химках — Московская прописка,
но судя по тому, что в Мытищах находится МЛТИ(Московский Лесо Технический Институт), то очевидно что и прописка у близлежащих домов тоже Московская
а минусуют прежде всего закомплексованные идтоты.
не знаю как Мытищи, но в Химках — Московская прописка,
но судя по тому, что в Мытищах находится МЛТИ(Московский Лесо Технический Институт), то очевидно что и прописка у близлежащих домов тоже Московская
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Я в своем текущем проекте начал использовать еще два интересных решения от PostgreSQL: window функции и тип данных hstore. Стоит о них написать?
Если hstore представляет собой банальное key-value поле, то window все же более интересен.
Если hstore представляет собой банальное key-value поле, то window все же более интересен.
Думаю, стоит однозначно. Я-бы лично был благодарен.
Банальное hstore позволяет практически свести к нулю все недостатки реляционной алгебры. Это самое сильное расширение SQL.
Иногда меня посещали мысли о том, что, по сути, любую привычную таблицу можно свести к таблице из одного hstore поля, но все же что-то в нем не так.
Ведь это не альтернатива привычным типам данных, это просто «еще один тип», который позволяет совершать над ним специфичные операции. Т.е. это по сути тот же TEXT с более функциональным оператором LIKE.
А реляционная модель все же устанавливает конкретные связи между сущностями, и глядя на такую модель опытный человек может даже составить для себя представление о бизнес-процессах, для которых эта модель была составлена.
Ведь это не альтернатива привычным типам данных, это просто «еще один тип», который позволяет совершать над ним специфичные операции. Т.е. это по сути тот же TEXT с более функциональным оператором LIKE.
А реляционная модель все же устанавливает конкретные связи между сущностями, и глядя на такую модель опытный человек может даже составить для себя представление о бизнес-процессах, для которых эта модель была составлена.
Без рекурсивных запросов статья не о чем. Рекурсивные данные требуют, чаще всего, рекурсии. Если не умете (postgres делает эти запросы отлично), то это Ваши проблемы.
При чем тут рекурсивные запросы? Вы осознали о чем статья?
Рекусривные запросы — нативный способ обработки иерархических данных. Если я не ошибаюсь он даже стандартизирован SQL2003
Здесь же представлена свистелка, которая призвана облегчить построение материализованного пути — способа, придуманного чтобы как-то компенсировать недостаток средств работы с иерархическими данными в ранних версиях SQL. Мне кажется было бы разумно, если бы были представлены аргументы использования ее против использвания рекусривных запросов и была бы ограничена область применения предлагаемой методики.
Здесь же представлена свистелка, которая призвана облегчить построение материализованного пути — способа, придуманного чтобы как-то компенсировать недостаток средств работы с иерархическими данными в ранних версиях SQL. Мне кажется было бы разумно, если бы были представлены аргументы использования ее против использвания рекусривных запросов и была бы ограничена область применения предлагаемой методики.
На самом деле, подозрительный способ делать древовидные запросы.
Если делать БД-независимый вариант, то этот способ не годится (надо юзать NS, MP и тд и тп). Если привязка к БД допустима — я бы не стал ставить какой-то непонятный контриб, который еще надо исследовать как написан и как перформит, а воспользовался бы CTE (Common Table Expressions), которые Postgre отлично поддерживает. Они даже немного стандартные — есть несколько других СУБД, в которых это реализовано. В результате у вас будет нормальное портируемое решение от авторов СУБД, доступное из коробки, а не кот в мешке.
Если делать БД-независимый вариант, то этот способ не годится (надо юзать NS, MP и тд и тп). Если привязка к БД допустима — я бы не стал ставить какой-то непонятный контриб, который еще надо исследовать как написан и как перформит, а воспользовался бы CTE (Common Table Expressions), которые Postgre отлично поддерживает. Они даже немного стандартные — есть несколько других СУБД, в которых это реализовано. В результате у вас будет нормальное портируемое решение от авторов СУБД, доступное из коробки, а не кот в мешке.
У нас с коллегами есть свой php фреймворк.
Так вот там мы реализовали деревья следующим образом.
Для каждого дерева ведется две таблицы: таблица самих данных и таблица структуры.
Таблица данных не хранит никаких сведений об отношениях между записями.
Таблица же структуры хранит:
1. parented (как я понимаю одного его достаточно для написания рекурсивного запроса)
2. ltree поле «path»
3. rKey и lKey для Nested Sets
Таким образом, если мы делаем продукт на PostgreSQL, мы пользуемся ltree, иначе – другими средствами. И переход с одной СУБД на другую осуществляется без проблем.
Так вот там мы реализовали деревья следующим образом.
Для каждого дерева ведется две таблицы: таблица самих данных и таблица структуры.
Таблица данных не хранит никаких сведений об отношениях между записями.
Таблица же структуры хранит:
1. parented (как я понимаю одного его достаточно для написания рекурсивного запроса)
2. ltree поле «path»
3. rKey и lKey для Nested Sets
Таким образом, если мы делаем продукт на PostgreSQL, мы пользуемся ltree, иначе – другими средствами. И переход с одной СУБД на другую осуществляется без проблем.
В смысле нормализации достаточно одного parentId, т.к. path по идее вычислимое поле.
Переход на другую СУБД подразумевает сохранение колонки path, я правильно понимаю? Только вы в этом случае другими способами ее считаете.
Переход на другую СУБД подразумевает сохранение колонки path, я правильно понимаю? Только вы в этом случае другими способами ее считаете.
С сортировкой по ltree беда. Сортируется оно лексикографически. Составлять ltree из чисел неудобно.
Заполнил базу данными из kladr (с детализацией до улиц — в районе 1 млн. записей) сделанными на основе nested sets. Поле tree сделал со значениями l_r из netsed sets (id большие — типа uuid) и проиндексировал (может и не нужно было — не знаю).
Во первых, индекс по этому полю занял 353 Мб при том что сама таблица в районе 143 Мб.
По первым-же тестам даже на глаз видно что вариант ltree работает существенно медленнее. Хотя, этого следовало ожидать. В nested sets запросы идут по индексируемым числовым полям. Сомневаюсь что быстрее возможно.
Однако, следует отметить что величины времен запросов в варианте ltree вполне приемлимы. Для себя сделал вывод что этот метод вполне заслуживает свое место в разработке. Например в вариантах, когда требуется частное изменение или добавление элементов в дереве.
Во первых, индекс по этому полю занял 353 Мб при том что сама таблица в районе 143 Мб.
По первым-же тестам даже на глаз видно что вариант ltree работает существенно медленнее. Хотя, этого следовало ожидать. В nested sets запросы идут по индексируемым числовым полям. Сомневаюсь что быстрее возможно.
Однако, следует отметить что величины времен запросов в варианте ltree вполне приемлимы. Для себя сделал вывод что этот метод вполне заслуживает свое место в разработке. Например в вариантах, когда требуется частное изменение или добавление элементов в дереве.
В запросах с ltree индексы используются? В мануале они почему-то создают два индекса, кстати:
Можете показать explain analyze запроса с ltree?
CREATE INDEX path_gist_idx ON test USING gist(path);
CREATE INDEX path_idx ON test USING btree(path);
Можете показать explain analyze запроса с ltree?
Конечно. Вот, например:
# 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)
# 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)
Предыдущий пост был с моим индексом. Создал по вашему описанию, получается вот так:
# 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)
# 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)
Спасибо. А добавьте, пожалуйста, analyze, чтобы было видно фактическое время с индексом и без.
Вот с индексом:
# 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)
Вообще, не очень показательно.
Я заметил что неправильно заполнил базу. Сейчас запущу заново ее формирование и завтра смогу сделать тесты с индексами и без них на нормальной базе и более сложных запросах.
# 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)
Вообще, не очень показательно.
Я заметил что неправильно заполнил базу. Сейчас запущу заново ее формирование и завтра смогу сделать тесты с индексами и без них на нормальной базе и более сложных запросах.
Спасибо, было бы интересно
Итак… Сделал более правильную базу. В таблице 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 существенно помогает запросам с ним.
Проверяю 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 существенно помогает запросам с ним.
статья конечно интересная, спасибо автору
деревья инструмент необходимый в разработке.
Комментарии многие тоже полезны.
Работатал с разными деревьями много, последнее время использую комбинированное хранение:
использую id/parent_id, но дополнительно храню уровень вложености и путь к узлу.
деревья инструмент необходимый в разработке.
Комментарии многие тоже полезны.
Работатал с разными деревьями много, последнее время использую комбинированное хранение:
использую id/parent_id, но дополнительно храню уровень вложености и путь к узлу.
спасибо за статью, очень полезно! Сам чуть не начал делать на MySQL, но столкнулся с проблемой — у одного потомка может быть несколько родителей… не подскажете, с пом. ltree получится реализовать такое?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Немного о деревьях