Хабрахабр

[Из песочницы] Снова о деревьях

Весна — пора подумать о деревьях. Деревья в DB это один из самых острых вопросов при работе с данными. В данном топике сравним быстродействие Materialized Path и Adjacency List методов с помощью команды «explain analize».
На днях я проходил собеседование в одной хорошей компании и пришел к выводу, что не все готовы изучать предмет с которым работают более досконально. А именно то что порой неявное и неправильное на первый взгляд решение может быть самым верным.

Materialized Paths (MP) и Adjacency List (AL). Я решил разобраться чуть более детально, в чем проблема и провести тест двух самых простых вариантов. А его цель, сравнить выбор parentId_parentId_parentId и выбор :pid числа. Nested Sets я не рассматриваю в виду цели данного топика.

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

Получил чуть меньше миллиона записей. Поэтому я взял несколько разных родительских веток с вложенностью в 5 уровней по 10-30 элементов в каждом узле. Вполне рабочие цифры для не слишком активного блога, почтового клиента и т.д.

Создаем таблицу tree и индексы к ней для двух типов дерева одновременно (для чистоты эксперимента.

-- Table: public.tree -- DROP TABLE public.tree; CREATE TABLE public.tree
( id integer NOT NULL DEFAULT nextval('tree_id_seq'::regclass), name text COLLATE pg_catalog."default", pid integer, btree integer[]
); -- Index: btree_idx -- DROP INDEX public.btree_idx; CREATE INDEX btree_idx ON public.tree USING gin (btree); -- Index: pid_idx -- DROP INDEX public.pid_idx; CREATE INDEX pid_idx ON public.tree USING btree (pid);

Наиболее внимательные заметили странное поле btree. Мы говорим абстрактно, а на делаем оптимизировано.

Добавляем в него данные к примеру так: Итак мы создали условное дерево, два поля для разных методов и уникальный идентификатор.

// Generate ...
func (c *TreeController) Generate() } } } }
} // GenerateRecurse ...
func (c *TreeController) GenerateRecurse(pid int64, treepid string) (int64, error) { v := models.Tree{ Name: "test -- " + treepid, Pid: pid, Btree: "{" + treepid + "}"} return models.AddTree(&v)
}

Здесь я намеренно не хотел замарачиваться с рекурсиями, потому написал так. Изначально хотел рекурсивно сделать, а потом подумал, что это тема для отдельного топика, и оставил как есть.

Открыл pgAdmin4 и запустил EXPLAIN ANALYZE с включенным Cost и timing флагами. Запросы я выполнил проще.

А интересовали нас два запроса.

Для MP:


SELECT * FROM tree
WHERE btree && ARRAY[:pid]
ORDER BY array_length(btree, 1);

Для AL:

WITH RECURSIVE nodes(id,name,pid, btree) AS ( SELECT s1.id, s1.name, s1.pid, s1.btree FROM tree s1 WHERE pid = :pid UNION SELECT s2.id, s2.name, s2.pid, s2.btree FROM tree s2, nodes s1 WHERE s2.pid = s1.id
)
SELECT * FROM nodes
order by pid asc;

Где :pid — id родителя.

А этот запрос придется достаточно часто использовать. Запрос для AL метода весьма и весьма запутанный.

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

Вот красивые картинки:

image

Смотрим запрос для AL: Как то все просто, но это для MP.

image

Но не смотря на это в результате скорость выполнения у MP на порядок выше. Уже красивее, но смотрим, что Total Cost у MP в полтора раза больше… А все потому что у нас индекс хранит не числа а массив чисел. И чем больше вложенностей и количество родительских элементов, том больше разница в скорости.

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

Но даже в пиковых значениях разница в скорости не менее 5 раз (самый медленный MP и самый быстрый AL метод. На скриншотах все данные актуальные, это не пиковые значения, а вполне средние.

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

Теги
Показать больше

Похожие статьи

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

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

Кнопка «Наверх»
Закрыть