22.05.2017 13:12
kuznetsovin 19 3000 Источник

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


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

Проголосовало 29 человек. Воздержалось 20 человек.

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

Поделиться с друзьями
-->

Комментарии (19)


  1. oxidmod
    22.05.2017 16:19
    #10228426

    Мне кажется или определения Nested Sets (NS) / Materialised Path model (MP) в статье перепутаны?


    1. kuznetsovin
      22.05.2017 16:25
      #10228440

      Спасибо за замечания, исправил.


  1. MikeVL
    22.05.2017 16:45
    #10228478
    +2

    Не поверю, что чтение всего дерева в модели Mptt будет медленнее, чем Raw. В django-mptt при выгрузке всего дерева данные будут упорядочены, т.е. будет применяться сортировка.

    У вас в Raw выгрузка дерева упорядочено или либо произвольное?


    1. kuznetsovin
      22.05.2017 17:27
      #10228570

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

      model.objects.all()
      во всех случаях.


      1. MikeVL
        22.05.2017 17:35
        #10228584
        +1

        В случае с MPTT дерево будет отсортировано! А в Raw нет! Если тестируете выгрузку всего дерева, то уж отсортируйте его. А иначе какой смысл этой выгрузки?


        1. kuznetsovin
          22.05.2017 17:48
          #10228606

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


          1. MikeVL
            22.05.2017 17:51
            #10228612
            +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
        )


            1. kuznetsovin
              22.05.2017 18:01
              #10228634

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


            1. kuznetsovin
              23.05.2017 10:24
              #10229164

              Я обновил диаграмму по считыванию дерева, добавлением сортировки ко всем запросам, но Raw все равно оказалась быстрее


              1. MikeVL
                23.05.2017 13:02
                #10229618

                Интересно, как вы сортируете в SQL выборку всего дерева в Raw?


                1. kuznetsovin
                  23.05.2017 13:06
                  #10229632

                  .order_by("parent_id")


                  1. MikeVL
                    23.05.2017 13:22
                    #10229668
                    +1

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


                    1. kuznetsovin
                      23.05.2017 13:57
                      #10229734

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


                      1. MikeVL
                        23.05.2017 14:00
                        #10229742

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


                        1. oxidmod
                          23.05.2017 14:03
                          #10229746

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


                      1. Imposeren
                        29.05.2017 06:44
                        #10238750

                        Согласен с 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. Мне кажется, что после «перемешиваний», с помощью перемещений, после вставок узлов в случайные места ситуация может поменяться. И при этом, как по мне, такой набор данных будет ближе к «настоящим», но это уже спорный вопрос


          1. MikeVL
            22.05.2017 18:17
            #10228670

            Возможно вы не наследовали модель от класса MPTTModel, и поэтому не будет сортировки.
            Но а если дерево не упорядочено, то зачем делать тест полной выгрузки? Ведь если этого не делать то скорость выгрузки будет примерно скорости выгрузки из БД. Да и что потом делать с этими данными?


  1. Klotos
    22.05.2017 22:58
    #10228876
    -1

    Я работаю с .NET и SQL Server, и никогда не сталкивался ни с Python, ни с PostgreSQL, ни с Django. Однако мне крайне странно видеть подобные результаты замера производительности. Ведь вся суть моделей Nested Sets и Materialized Path в том, что они придуманы именно для ускорения чтения (выборка дерева/поддерева, определение количества узлов в поддереве, обход в ширину/глубину), жертвуя скоростью записи/модификации (удаление/добавление узлов/поддеревьев, перемещение узлов/поддеревьев). Будь в общем такие результаты по скорости, и модели Nested Sets и Materialized Path никогда бы не возникли.


  1. Guderian
    23.05.2017 13:27
    #10229678
    +1

    А какую модель используете вы?

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