Pull to refresh

Сравнение производительности иерархических моделей Django и PostgreSQL

Reading time 3 min
Views 9.8K

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


Сегодняшняя статья будет посвящена сравнению моделей работы с иерархическими данными в 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

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


read_tree_chart


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


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


read_node_chart


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


Вставка узла


insert_node_chart


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


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


move_node_chart


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


Итоги


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


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


model insert_node move_node read_node read_tree
Ltree 0.001955 0.010375 0.008745 0.025522
Mptt 0.001006 0.855293 0.00104 0.115597
Raw 0.001002 0.001 0.001012 0.021957

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


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


  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. Это кросс-пост оригинальной статьи с моего блога

P.S. Обновлен график чтения дерева, после добавления сортировок
Only registered users can participate in poll. Log in, please.
А какую модель используете вы?
43.14% Adjacency model 22
33.33% Nested sets 17
23.53% Materialised path 12
51 users voted. 33 users abstained.
Tags:
Hubs:
+8
Comments 19
Comments Comments 19

Articles