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

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


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

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

    А какую модель используете вы?
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 19
      0
      Мне кажется или определения Nested Sets (NS) / Materialised Path model (MP) в статье перепутаны?
        0
        Спасибо за замечания, исправил.
        +2
        Не поверю, что чтение всего дерева в модели Mptt будет медленнее, чем Raw. В django-mptt при выгрузке всего дерева данные будут упорядочены, т.е. будет применяться сортировка.

        У вас в Raw выгрузка дерева упорядочено или либо произвольное?
          0
          Исходники все в открытом доступе, если укажите в них на ошибку буду только рад. Для получения всего дерева я использую стандартный запрос Django:
          model.objects.all()
          во всех случаях.
            +1
            В случае с MPTT дерево будет отсортировано! А в Raw нет! Если тестируете выгрузку всего дерева, то уж отсортируйте его. А иначе какой смысл этой выгрузки?
              0

              Если постотреть запросы которые идут в базе, то сортировки там нет, или вы имеете ввиду, что mptt сортирует данные при вставке?

                +3
                django-mptt добавляет сортировку по двуь полям ".order_by('tree_id', 'lft')". А если вы тестируете выборку полного дерева без упорядочивание, то какой смысл в таком тесте?

                def get_queryset(self, *args, **kwargs):
                        """
                        Ensures that this manager always returns nodes in tree order.
                        """
                        return super(TreeManager, self).get_queryset(
                            *args, **kwargs
                        ).order_by(
                            self.tree_id_attr, self.left_attr
                        )
                
                  0

                  Спасибо, за то что нашли неточность я перепроверю результат с учетом этого, просто странно что профайлер запросов Джанго не указал сортировку в sql запросе.

                    0
                    Я обновил диаграмму по считыванию дерева, добавлением сортировки ко всем запросам, но Raw все равно оказалась быстрее
                      0
                      Интересно, как вы сортируете в SQL выборку всего дерева в Raw?
                        0
                        .order_by("parent_id")
                          +1

                          И что в итоге вы получите? Набор строк отсортированных по parent_id? Это никак не дерево.

                            0
                            Я был бы вам очень признателен, если бы вы показали какой запрос надо выполнить для Raw дерева. И я бы провел замеры на нем.
                              0

                              Да я не уверен что можно построить полное дерево на одном SQL для формата Raw.

                                0
                                Можно, не не на всех субд… Или по крайней мере не на всех это делается тривиально. По сути нужны рекурсивные запросы. Чем более глубокое и широкое дерево тем все будет хуже с рекурсией.
                                0
                                Согласен с MikeVL: для хоть какого-то приближения к реальным юзкейсам нужно при чтении всего дерева использовать «одинаковые» сортировки для всех 3х вариантов, а сейчас у вас:
                                1. для mptt и ltree сортировки вроде бы похожие и в основном идут «в глубину»
                                2. для raw у вас порядок будет совсем другой: сначала верхние узлы все деревьев, а потом вообще бардак – если при «упорядоченном» создании еще можно описать в каком порядке это всё идёт, то после того как вы поперемещаете деревья между родителям – начнётся полный бардак

                                Думаю вам нужно подумать над тем, чтобы для Raw сделать сортировку хотя бы похожей на порядок в mptt и ltree. Например получить все узлы без родителей, а потом для них вызывать get_descendants, но этоу уже явно не один запрос. Но и в этом случае ничто не гарантирует, что для Raw модели сохранится какой-либо адекватный порядок

                                И еще замечания:
                                1. в реальных ситуациях, когда данных много — вы не будете использовать list(QS), т.к. при таком подходе вы рискуете бесполезно использовать всю доступную память. Скорее в таких случаях вы бутете использовать iterator, или будете считывать небольшими порциями. (http://blog.etianen.com/blog/2013/06/08/django-querysets/). Мне кажется для чтения всего дерева правильнее было бы использовать подобный подход. А для отдельных узлов – вариант с list(QS) – ок
                                2. Методы которыми вы выбираете случайный узел каждый раз считывают всю таблицу – мне кажется это будет как-то влиять на поведение постгреса, но не уверен
                                3. в методе move_node_time, конечную точку вы выбираете случайно, без каких-либо проверок. Из-за этого вполне возможна ситуация, когда вы будете перемещать узел к одному из своих потомков – не особо понимаю как текущая логика Ltree.move_to справится с этим
                                4. Мне кажется, что после «перемешиваний», с помощью перемещений, после вставок узлов в случайные места ситуация может поменяться. И при этом, как по мне, такой набор данных будет ближе к «настоящим», но это уже спорный вопрос
                      0
                      Возможно вы не наследовали модель от класса MPTTModel, и поэтому не будет сортировки.
                      Но а если дерево не упорядочено, то зачем делать тест полной выгрузки? Ведь если этого не делать то скорость выгрузки будет примерно скорости выгрузки из БД. Да и что потом делать с этими данными?
                –1
                Я работаю с .NET и SQL Server, и никогда не сталкивался ни с Python, ни с PostgreSQL, ни с Django. Однако мне крайне странно видеть подобные результаты замера производительности. Ведь вся суть моделей Nested Sets и Materialized Path в том, что они придуманы именно для ускорения чтения (выборка дерева/поддерева, определение количества узлов в поддереве, обход в ширину/глубину), жертвуя скоростью записи/модификации (удаление/добавление узлов/поддеревьев, перемещение узлов/поддеревьев). Будь в общем такие результаты по скорости, и модели Nested Sets и Materialized Path никогда бы не возникли.
                  +1
                  А какую модель используете вы?

                  На самом деле, модель определяется кейсами. У каждой есть свои преимущества и недостатки. Nested sets — практически лучший алгоритм по части выборки (большинство типовых операций на дереве предельно просты), упорядочивание узлов «из коробки», но модификация дерева нетривиальна (поэтому часто используются gaps-модификацию). Adjacency lists — наиболее гибкий и сбалансированный, когда предполагается много операций на дереве, а основная таблица достаточно «широкая» (но только не его рудиментарный вид id+parent, а классический adjacency list в отдельной таблице, особенно хорошо для баз с поддержкой кластерных индексов). Materialized paths — самый убогий по всем показателям. Binary-модификация ещё куда не шло, но типовая строковая реализация… Есть ещё метод nested intervals. Решает те же проблемы, что и nested sets+gaps, но только без гвоздей.

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

                  Самое читаемое