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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты

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

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

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