• Разработка веб-сайтов
• Python
• PostgreSQL
• Django

Добрый день, уважаемые читатели.

Сегодняшняя статья будет посвящена сравнению моделей работы с иерархическими данными в PostgreSQL, через Django приложение. В статья я специально не использую чистую реализацию в базе данных, т. к. меня интересует именно производительность в среде, приближенной к боевой.

Все тесты проводились на моих данных и результаты являются актуальными именно для этих данных, на ваших данных результат может отличаться от полученных в статье.

Модели реализации иерархических структур в БД

Для работы с такими структурами в PostgreSQL могут использоваться следующие модели:

1. Adjacency model (AM) — модель, когда в колонке хранится родитель;
2. Nested Sets (NS) — модель, когда в паре колонок хранится диапазон всех вложенных элементов;
3. Materialised Path model (MP) — модель, когда в колонке хранится полный путь до элемента.

Также подробней об реализации иерархических структур в реляционной БД можно почитать здесь.

Для их реализации в Django выбраны следующе инструменты:

1. AM — штатная рекурсия Django на основе ForeignKey;
2. NS — модуль django-mptt;
3. MP — модуль ltree PostgreSQL с оберткой LtreeField;

Методика тестирования

Тестирование будет проводится на наборе данных из 150 тыс компаний. Время будет замеряться для
следующих запросов:

1. Чтение всего дерева
2. Чтение произвольного узла
3. Вставка узла
4. Перемещение поддерева между уровнями

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

Аппаратное обеспечение тестового стенда

• CPU Core i5 2,5 GHz
• RAM 1600 MHz DDR3
• SSD Samsung 850 EVO 500GB

Программное обеспечение тестового стенда

• Python 2.7
• Postgres 9.6
• Django 1.8
• psycopg2

Описание инструмента тестирования

Для тестирования создано отдельное Django приложение. В нем создано по 3 модели, по одной на каждую схему хранения описанные выше. Это сделано для того, чтобы в любой момент можно было провести аналогичное тестирование на различных наборах данных.

В данном приложении реализовано две команды:

• load_tree — загружает данные для теста
• analize — выполняет сбор и анализ данных исходя из заданного количества запросов

Для запуска приложения и сбора статистики нужно выполнить последовательность команд:

python manage.py migrate
python manage.py load_tree <путь до файла с данными>
python manage.py load_tree analize <кол-во запросов для анализа>

Результаты команды analize хранятся в папке report.

Результаты

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

• Raw — adjacency model
• Mptt — nested sets
• Ltree — materialised path

Чтение всего дерева

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

Чтение произвольного узла

В данном тесте, в отличии от предыдущего пункта, модель Mptt сравнялась по скорости со стандартной реализацией, а вот Ltree напротив ухудшил свой результат. Надо отметить что в модели Raw для получения потомков используется рекурсивный запрос (WITH RECURSION), и, не смотря на это, он отработал быстрее всех.

Вставка узла

При вставке узла опять отстала модель Ltree, но в данном случае это скорее всего связано с тем, что поле пути в котором хранится дерево состояло из id записей, поэтому мне пришлось делать 2 запроса (insert, а потом update поля path), что соответственно сказалось на производительности.

Перемещение поддерева между уровнями

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

Итоги

Почтав сравенния реализации иерархических струтктур я ожидал, что лучший результат покажет реализация модели MP(Ltree), но, к моему удивлению, она показала лишь второй результат, уступив нативной реализации модели AM(Raw). Ну а реализации модели NS(Mptt) досталось 3-е место, так как в 2 тестах из 4 он проиграл с большим отрывом от конкурентов.

Сводная таблица с результатами:

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

Используемые статьи:

1. Representing Trees in PostgreSQL
2. Trees in SQL: Nested Sets and Materialized Path
3. Хранение деревьев в базе данных.
4. Benchmark tree structure for Django
5. Иерархические структуры данных и Doctrine
6. Ltree
7. Django-mptt
8. LtreeFiled

P.S. Это кросс-пост оригинальной статьи с моего блога