Pull to refresh

Nested Intervals и их реализация под Yii2

PHP *Algorithms *Yii *
Привет, Хабр!
Большинство разработчиков знает, что такое Nested Sets, их сильные и слабые стороны. Сегодня я хочу представить на суд общественности реализацию модификации этой методики, которая частично решает недостатки оригинального алгоритма, правда имеет и свои отрицательные стороны.

Какие же плюсы и минусы у оригинальных Nested Sets:
+ быстрая выборка родителей и детей простым запросом;
+ быстрая выборка соседних узлов простым запросом;
+ быстрая выборка пустых узлов простым запросом;
+ моментальное получение количества всех детей в узле по формуле;
+ возможность не рекурсивного построения дерева одним циклом;
— очень медленная вставка и обновление.

Каковы же причины медленной вставки/обновления? Так как, значения границ узлов идут непрерывно, то любая вставка, особенно в начало дерева, требует перерасчёта границ всех последующих узлов. Если таблица достаточно большая, то это процесс может затянуться на десятки секунд и даже дольше. На анимации:


Nested Intervals


Первая мысль, которая пришла в голову, рассматривая картинку с визуальным представлением Nested Sets: «так границы же можно не двигать, если представить корневой узел как отрезок на поле вещественных чисел». То есть, если представить, что границы корневого узла имеют значения 0.0 и 1.0, то можно добавлять узлы в любое место не двигая другие, надо просто взять вещественное число между целевыми узлами. Но, так как мы прекрасно знаем, вещественные числа в компьютере имеют свои пределы, то от этой идеи я быстро отказался, в пользу целых чисел.

С целыми числами суть та же, только границы корневого узла сделаем от нуля до INT_MAX. Тогда при вставке нового узла мы просто берём любые два незанятых значения между целевыми узлами, и больше ничего не трогаем, всё было бы быстро и круто, если бы не одно «но» — что делать если свободных значений больше нет? Очевидно, что нужно двигать все значения границ до ближайшего свободного значения, «расчищая» себе пространство для вставки. Только вот поиск такой «дырки» — задача затратная, поэтому результат в таком случае может выйти даже медленнее, чем в классических nested sets.


Немного погуглив, я понял, что не изобрёл велосипед, и эта идея уже давно имеет название Nested Itervals. Только вот реализаций я так и не нашёл, т. к. на большинстве ресурсов данную методику рассматривали в негативном ключе, мол «одно лечим, другое калечим». И это не безосновательно, но мне стало очень интересно, захотелось протестировать в чём данный алгоритм лучше, а в чём хуже, и на сколько.

Реализация


Я начал писать Behavior для Yii2, реализующий идею Nested Intervals. Первая сложность возникла при написании методов вставки — как получить границу соседнего узла или родителя при insertBefore() и insertAfter() и границу первого/последнего узла при prependTo() и appendTo()? Если в Nested Sets она очевидна — +1/-1 к границе текущего узла, то здесь без дополнительно запроса к базе никак. Но благо, что выборки у нас быстрые.

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

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

Но вот перемещение из другого дерева — задача оказалась трудно решаемая, т. к. перемещаемых узлов может оказаться очень много, и вставлять их по одному обычным алгоритмом выходит слишком долго. Сначала я вообще хотел отказаться от этой возможности, списав на сложность реализации. Но чуть позже, осознал необходимость метода optimize(), который бы равномерно распределял границы существующих узлов по диапазону. После этого, возникла идея перемещать узлы другого дерева путём оптимизации исходного дерева с заготовлением «окна» под перемещаемые узлы. Всё это работает очень медленно (на данный момент есть оптимизация этого метода только под MySQL), но стоит отметить, что операция по перемещению из других деревьев требуется редко, куда чаще требуется движения в рамках одного дерева.

Зато реализовывать выборки было достаточно легко — главные методы получения родителей и детей идентичны классическим nested sets. Чуть посложнее с выборками предыдущего/следующего соседа — требуется два запроса: получение родителя, и непосредственный поиск в диапазоне с лимитом. А вот совсем плохо стало с получением пустых узлов getLeaves(), т. к. пришлось его делать с помощью left join, что наверняка скажется на производительности.

Оптимизация вставки


Выполнив первый ряд тестов на производительность, результаты мягко говоря не впечатлили. Дело оказалось в том, что сначала я реализовал выбор границ вставляемого узла просто разбив отрезок на три части. Из-за этого промежуток для новых узлов стремительно сокращался. Так как диапазон 32 битного PHP составляет [0 — 2147483647] (операции с большими числами конвертируются во float), то выполнив вставку через appendTo() всего 19-ти узлов в корень, на 20-й узел уже не останется места (2147483647/3^19 = ~1.9), и приходится выполнять медленные операции по поиску незанятых мест и перемещения. Так дело, конечно, не пойдёт. Нужны какие-то оптимизации по распределению места. Для этого в Behavior есть аж 5 опций:
  • Первая и главная amountOptimize — этот параметр определяет на какое количество узлов запланировать разбиение доступного для вставки отрезка. То есть, при значении 20, мы сможем вставить 20 дочерних узлов, и они равномерно займут диапазон родителя, а дальше — как получится.
    В качестве значения можно использовать массив, тогда значение будет разным для каждого уровня.
  • noPrepend, noAppend, noInsert — эти параметры помогают оптимизировать резервирование места между границами, и положение первого узла. Если у вас, используется в основном только операция appendTo() (например, комментарии), то вы можете выставить noPrepend = true и noInsert = true, и тем самым значительно снизите вероятность возникновения тяжёлого случая с расчисткой пространства под новый узел. Более наглядно влияние этих параметров показано на картинках.
    amountOptimize=3
    amountOptimize=3
    noPrepend=true
    amountOptimize=3
    noAppend=true
    amountOptimize=3
    noInsert=true
    amountOptimize=3
    noInsert=true
    noPrepend=true
    amountOptimize=3
    noInsert=true
    noAppend=true

    Стоит отметить, что если вы задаёте noPrepend = true — это не значит, что вы не сможете выполнить вставку prependTo(), просто с большой долей вероятности множество таких операций будут выполняться медленно.
  • И последний параметр reserveFactor, определяет размер промежутков между границами. При единичке размер промежутка равен размеру вставляемого узла. Если сценарий использования Behavior предполагает большого числа операций insertBefore() и insertAfter(), то этот параметр лучше увеличить

После всех этих манипуляций тесты стали гораздо более «вкусными».

64 бита


Если вы задействуете BIGINT колонки для хранения left и right атрибутов и используете 64-битный PHP, то сможете воспользоваться бесплатной оптимизацией в виде более широкого диапазона. Просто задайте параметр range = [0, 9223372036854775807]. Это позволит сделать более редкими случаи с недостатком места под новые узлы.

Тесты на производительность


В качестве эталона для сравнения, был взят самый популярный Behavior, реализующий Nested Sets от уважаемого Alexander Kochetov (Creocoder) creocoder/yii2-nested-sets. Так же было интересно сравнить результаты с Adjacency List с сохранением возможности сортировки. Подходящей библиотеки я для этого не нашёл, поэтому взял и написал сам (да ещё и с поддержкой JOINов, но сейчас не об этом).

Первые два теста довольно синтетические, т. к. в реальности так заполнять дерево вряд ли кто будет, но мне данная процедура была необходима в первую очередь для генерации более-менее большой базы для дальнейших тестов. В них просто последовательно заполняются уровни фиксированным количеством детей.
Результаты тестов 1 и 2
                                                Запросов    DB время    Выполнение  Память
Тест 1. Заполнение 3 уровня по 12 детей.
    Nested Sets                                 7696        6,961 ms    26,305 ms   135.8 MB
    Itervals default (amount=10)                6377        2,850 ms    11,920 ms   87.3 MB
    Itervals x64 default (amount=10)            5813        1,992 ms    10,963 ms   78.7 MB
    Itervals amount=24                          5813        1,765 ms    10,442 ms   78.7 MB
    Itervals amount=12 noPrepend noInsert       5813        1,750 ms    10,223 ms   78.7 MB
    Adjacency List                              5811        1,567 ms    9,591 ms    71.3 MB
    
Тест 2. Заполнение 6 уровня по 3 детей.
    Nested Sets                                 4735        5,701 ms    19,784 ms   82.2 MB
    Itervals default (amount=10)                3644        1,275 ms    5,976 ms    48.9 MB
    Itervals amount=3 noPrepend noInsert        3644        1,271 ms    5,993 ms    48.9 MB
    Adjacency List                              3642        982 ms      5,812 ms    44.5 MB

Уже в первом тесте видно, как плохо влияет неподходящее значение параметра amountOptimize. В 32-битном тесте появились лишние запросы? связанные с тем, что для некоторых узлов скрипт «расчищал место». Но тем не менее, даже в этом случае всё выполнилось гораздо быстрее. Кстати 64-бита в этом тесте выручили, и не было ни одной «плохой» ситуации.

Тесты 3-5 имитируют вставку 20 узлов в разное место большой таблицы:
Результаты тестов 3-5
                                                Запросов    DB время    Выполнение  Память
Тест 3. Вставка в начало <4% (20 в 19657 узлов)
    Nested Sets                                 100         15,597 ms   16,636 ms   5.0 MB
    Itervals                                    82          21 ms       150 ms      4.7 MB
    Adjacency List                              100         170 ms      439 ms      4.6 MB

Тест 4. Вставка в середину >46% <50% (20 в 19657 узлов)
    Nested Sets                                 100         8,200 ms    8,985 ms    5.0 MB
    Itervals                                    82          269 ms      593 ms      4.7 MB
    Adjacency List                              100         163 ms      454 ms      4.7 MB

Тест 5. Вставка в конец >96% (20 в 19657 узлов)
    Nested Sets                                 100         549 ms      911 ms      5.0 MB
    Itervals                                    83          46 ms       187 ms      4.7 MB
    Adjacency List                              106         159 ms      435 ms      4.7 MB

Тест на вставку в начало базы очень наглядно демонстрирует слабое место классических Nested Sets — для вставки в начало базы требуется обновление границ всей базы. Отсюда и разгромный результат. Лишь результаты вставки в конец базы более-менее конкурирует с Nested Itervals. И кстати, обратите внимание на то, что Adjacency List был медленнее, это связано с тем, что для обеспечения сортировки, ему приходится выполнять SELECT MAX(sort).

Следующий тест удаляет 20 узлов из начала дерева:
Результаты теста 6
                                                Запросов    DB время    Выполнение  Память
Тест 6. Удаление из начала <4% (20 из 19657 узлов)
    Nested Sets                                 100         16,554 ms   17,678 ms   4.8 MB
    Itervals                                    60          164 ms      250 ms      4.2 MB
    Adjacency List parentJoin=0 childrenJoin=0  60          169 ms      257 ms      3.8 MB
    Adjacency List parentJoin=3 childrenJoin=3  60          87 ms       162 ms      3.8 MB

Здесь ситуация аналогичная тесту 3. Есть лишь разница в том, что в Itervals при удалении уже не могут возникнуть «плохих ситуаций».

Тест 7 очень показательный, т. к. хорошо имитирует использование Behavior для комментариев. В цикле 1000 узлов добавляется в случайно выбранный узел, с ограничением уровней. Тест 8 аналогичный, но с ещё более жесткими условиями — разрешено не только добавление, но и любая другая операция.
Результаты тестов 7 и 8
                                                Запросов    DB время    Выполнение  Память
Тест 7. appendTo() в случайный узел (5 уровней, 1000 узлов)
    Nested Sets                                 5002        5,989 ms    17,406 ms   80.7 MB
    Itervals default (amount=10)                8497        23,301 ms   41,060 ms   120.7 MB
    Itervals x64 default (amount=10)            7092        11,330 ms   23,618 ms   97.5 MB
    Itervals amount=200,25 noPrepend noInsert   4009        1,431 ms    6,490 ms    50.2 MB
    Itervals x64 amount=250,30 noPrepend noIns  4003        1,421 ms    6,615 ms    50.0 MB
    Adjacency List                              4001        1,062 ms    5,976 ms    46.1 MB
    
Тест 8. произвольная операция в случайный узел (5 уровней, 1000 узлов)
    Nested Sets                                 5002        9,383 ms    23,502 ms   80.7 MB
    Itervals default (amount=10)                7733        8,123 ms    24,031 ms   107.2 MB
    Itervals x64 default (amount=10)            5663        3,761 ms    14,084 ms   75.6 MB
    Itervals amount=200,25 reserve=2            4175        1,548 ms    7,223 ms    52.8 MB
    Itervals x64 amount=250,30 reserve=2        4003        1,541 ms    6,753 ms    50.0 MB
    Adjacency List                              4395        4,394 ms    12,377 ms   53.4 MB

Тут в глаза бросается то, как важно при задействовании Intervals правильно настроить параметры оптимизации вставки, т. к. в данном примере настройки по умолчанию дали очень печальный результат. Зато с оптимизациями всё работает очень быстро, сопоставимо с Adjacency List. Кстати в 8 тесте он сильно замедлился, т. к. для обеспечения сортировки ему тоже требовалось «расчищать место».

Следующие два теста на перемещение узлов в дереве:
Результаты тестов 9 и 10
                                                Запросов    DB время    Выполнение  Память
Тест 9. Перемещение узлов в начале <4% (20 из 19657 узлов)
    Nested Sets                                 200         24,312 ms   25,479 ms   6.3 MB
    Itervals                                    160         180 ms      573 ms      6.0 MB
    Adjacency List                              111         107 ms      318 ms      4.6 MB

Тест 10. Перемещение узлов из конца в начало <4% >96% (20 из 19657 узлов)
    Nested Sets                                 200         16,999 ms   17,973 ms   6.3 MB
    Itervals                                    160         16,972 ms   17,854 ms   6.0 MB
    Adjacency List                              108         86 ms       325 ms      4.6 MB

В принципе, что у Nested Sets, что у Nested Intervals эта операция должна выполняться за одинаковое время, но в коде у Creocoder это происходит не оптимально, т. к. вместо того, чтобы просто поменять местами пару блоков, в его коде сначала двигается вся база до конца, потом идёт перемещение нужного блока, а затем опять вся база двигается назад. Зато у Creocoder можно использовать unsigned поля для атрибута depth, а в моём Behavior он временно при перемещении становится отрицательным. Результаты перемещения из конца в начало сопоставимы, а вот Adjacency List имеет значительное преимущество.

После написания Behavior мне захотелось узнать, какую выгоду даст использование Trait вместо поведений. Поэтому я портировал его Trait со статическими атрибутами. Дальнейшие тесты на выборки велись также и в вариантах с Trait. Но результаты применения примесей мягко говоря не впечатлили, особенно учитывая то, насколько более уродлив стал код из-за них.
Простая выборка всех элементов Model::find()->all():
Результаты теста 11
                                                Запросов    DB время    Выполнение  Память
Тест 11. Выбор всех узлов (19657 шт.)
    Nested Sets                                 1           40 ms       1,108 ms    215.2 MB
    Itervals                                    1           42 ms       1,247 ms    225.3 MB
    Itervals Trait                              1           41 ms       1,174 ms    207.4 MB
    Adjacency List                              1           33 ms       890 ms      179.1 MB

Этот тест был написан в первую очередь для сравнения потребления памяти Behavior vs. Trait. И как видим разница есть, но незначительная.

Выборка потомков:
Результаты теста 12
                                                Запросов    DB время    Выполнение  Память
Тест 12. Выбор детей и потомков (для 819 узлов в середине дерева из 19657 узлов)
    Nested Sets                                 1641        6,397 ms    7,498 ms    24.9 MB
    Itervals Behavior                           1641        579 ms      1,657 ms    25.0 MB
    Itervals Trait                              1641        615 ms      1,590 ms    24.3 MB
    Adjacency List parentJoin=0 childrenJoin=0  2562        720 ms      1,969 ms    36.9 MB
    Adjacency List parentJoin=3 childrenJoin=3  2461        704 ms      1,966 ms    35.3 MB

Запросы на выборку детей должны быть одинаковыми в Nested Sets и Nested Intervals, но здесь раскрылся ещё один недостаток библиотеки от Creocoder — не оптимально выбираются потомки. Потомков можно было выбрать моментально используя индекс по одному из атрибутов left или right `lft` > :leftValue && `lft` < :rightValue, вместо этого, индекс используется лишь на половину `lft` > :leftValue && `rgt` < :rightValue. Если проанализировать EXPLAINом, становится ясно, что первый вариант гораздо более предпочтителен. Результаты Adjacency List уступают, что неудивительно.

Выборка предков:
Результаты теста 13
                                                Запросов    DB время    Выполнение  Память
Тест 13. Выборка родителей (для 819 узлов в середине дерева из 19657 узлов)
    Nested Sets                                 821         3,344 ms    4,069 ms    20.6 MB
    Itervals Behavior                           821         3,292 ms    4,147 ms    22.0 MB
    Itervals Trait                              821         3,310 ms    4,080 ms    21.1 MB
    Adjacency List parentJoin=0 childrenJoin=0  3180        948 ms      2,304 ms    51.2 MB
    Adjacency List parentJoin=3 childrenJoin=3  1641        486 ms      1,495 ms    30.8 MB

Здесь Nested Sets и Nested Intervals ведут себя одинаково, и достаточно медленно. Дело в отсутствии нормальных индексов и неудачным стечением обстоятельств — оба индекса из середины таблицы имеют много элементов. Adjacency List как не удивительно, отработал быстрее, хоть и за счёт памяти (хотя тут дело ещё в простом 3-х уровневом дереве).

Выборка соседних и пустых узлов:
Результаты теста 14 и 15
                                                Запросов    DB время    Выполнение  Память
Тест 14. Выборка соседних узлов (для 819 узлов в середине дерева из 19657 узлов)
    Nested Sets                                 1641        520 ms      1,424 ms    24.3 MB
    Itervals Behavior                           1641        19,681 ms   21,326 ms   27.5 MB
    Itervals Trait                              1641        19,666 ms   21,251 ms   26.5 MB
    Adjacency List parentJoin=0 childrenJoin=0  1641        535 ms      1,442 ms    23.7 MB
    Adjacency List parentJoin=3 childrenJoin=3  1641        508 ms      1,421 ms    23.6 MB

Тест 15. Выборка пустых узлов (для 819 узлов в середине дерева из 19657 узлов)
    Nested Sets                                 821         3,215 ms    3,814 ms    18.8 MB
    Itervals Behavior                           821         10,450 ms   11,166 ms   18.8 MB
    Itervals Trait                              821         10,425 ms   11,040 ms   18.7 MB
    Adjacency List parentJoin=0 childrenJoin=0  1833        568 ms      1,743 ms    32.6 MB
    Adjacency List parentJoin=3 childrenJoin=3  1732        556 ms      1,891 ms    31.3 MB

Тут, как и предполагалось, мы видим слабые стороны Nested Intervals. Как говорится, без комментариев.


Выводы


Nested Intervals — имеет право на жизнь. У него есть как преимущества, так и недостатки:
+ быстрая вставка (при условии хорошего подбора оптимизирующих параметров);
+ быстрое удаление узла с потомками;
+ такая же скорость как у Nested Sets в выборке предков и потомков;
+ так же, осталась возможность не рекурсивного построения дерева одним циклом;
— медленное получение соседних узлов;
— медленное получение пустых узлов;
— нет возможности моментально подсчитать количество потомков в узле.

Реализация для Yii2


Хочу отметить, что методы немного отличаются от предложенных в поведении Creocoder. Во-первых я изменил именование методов на геттеры getParents() getDescendants(), это позволяет реализовывать доступ к связанным узлам, аналогично Relations, что позволяет не делать вторичных запросов к базе:
$node = Node::findOne(['name' => 'test']);
$children = $node->children; // relation
$children = $node->getChildren()->all(); // query

Кроме того, я не стал протаскивать Yii-шные параметры к save($runValidation, $attributeNames), вместо этого я реализовал методы, как указание на действие (прямо как ->asArray()->):
$node = new Node();
$node->makeRoot()->save(false);
$node->insertAfter($node2)->save();

Реализация Nested Intervals на GitHub.
Реализация Adjacency List на GitHub.
Tags:
Hubs:
Total votes 21: ↑20 and ↓1 +19
Views 13K
Comments 13
Comments Comments 13

Posts