SQL Trees (finished)

ладно, кажется мои "страсти по деревьям" подходят к завершению.
с механизмом я вроде бы определился, и окончательный выбор меня на самом деле немало удивил.
попробую обобщить здесь накопившуюся инфу о проведённых тестах.

чтоб не было потом лишнего пиздежа:
<disclaimer>
все нижеприведённые тесты некорректны априори!
сравнивались разные механизмы на двух совершенно разных СУБД, которые несравнимы.
единственное, что совпадало -- набор данных и структура дерева.
так или иначе, тесты я делал для себя, нужную мне информацию я получил, а всё остальное -- фпесду и ниибёт.
если появятся злоебучие крохоборы и борцы за Вселенскую Правду™, буду говорить лишь: "OMG STFU, don't bitch and get a life, dork!"
</disclaimer>

целью данных тестов было найти подходящий механизм хранения и обработки информации, структурированной в виде дерева, в СУБД PostgreSQL. механизм должен работать приемлемо быстро (кто как хочет, так и интерпретирует это определение) на деревьях в несколько тысяч нод, а также должен быть достаточно удобным на момент изменения содержимого дерева.

ладно, прежде всего -- общая картина -- графики с результатами. помимо обычного, привожу график с логарифмической шкалой, чтобы лучше была видна разница:

INSERT	PATH
DESCENDANTS	DELETE

вот так расположены графики следующих тестов:


INSERT - вставить необходимое кол-во нод в дерево.
набор данных и структура генерируются случайным образом однажды в самом начале тестов. поле "полезной нагрузки" в отдельной таблице лишь одно и содержит текст "node<N>", где <N> -- порядковый номер ноды.

PATH - для каждой ноды дерева получить её "путь" до корня дерева.

DESCENDANTS - для каждой ноды первого уровня получить всех её потомков.

DELETE - последовательно удалять каждую ноду первого уровня вместе со всеми её потомками.

вот теперь -- самое вкусное: описания графиков различных механизмов. хотя, описанием это назвать будет трудно, поэтому наверное лучше таки использовать термин обоснование.
гы, будет смешно, если потом окажется, что в тестах были грубые ошибки, и придётся точно так же всё обосновывать на противоположное. =)

---

ADJ-M - Adjacency List (MySQL)
несомненно, самый быстрый механизм.

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

на операции PATH уже даёт себя знать геморрой в коде, т.к. для каждого уровня мы должны сделать отдельный запрос:



и тем не менее, разница по PATH с другими механизмами на MySQL исчезающе мала!
всё это потому, что MySQL прямо таки резок как понос на простейших выборках по PRIMARY KEY и сделает на них любую другую "взрослую" СУБД.

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

на DELETE все остальные немножко обосрались по сравнению с ADJ-M, даже несмотря на то, что удаление шло в две стадии -- точно так же, как и выборка в DESCENDANTS -- сначала получить список нод, а потом уже их удалить.

---

NST-M - Nested Sets (MySQL)
очень хороший механизм! прямо таки самый-самый, если не брать во внимание жутчайшие тормоза на операции INSERT, где время работы растёт экспоненциально.

INSERT: пиздец-какие-тормоза! ноу комментс.
PATH: супер быстро. быстрее работает только RAL-M, потому что там запросы проще.
DESCENDANTS: круче нас тока йайца! выборка по уникальному индексу -- что может быть быстрее.
DELETE: то же, что и в DESCENDANTS -- очень даже хорошо

---

RAL-M - Redundant Adjacency List (MySQL)
механизм такой же, как и ADJ-M, только в таблице со структурой дерева храним ссылки не только на прямого потомка ноды, но и на всех её потомков.

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

---

RAL-P - Redundant Adjacency List (PgSQL)
ADJ-P - Adjacecncy List (PgSQL)
да-да, я там наебался маленько в агенде к графикам. то, что обозначено RAL-P следует читать как ADJ-P (потом может быть поменяю, сейчас не могу). почему я отказался от RAL-P я уже пояснил в предыдущем параграфе.

итак, переходим на другую платформу -- PostgreSQL, для которой всё и делается.
теперь в БД я усиленно использую хранимые процедуры и триггеры, ессно постоянно думая о скорости работы, но и давая себе отчёт в том, что все эти фишки так или иначе будут тормознее, чем голый король MySQL.
важно: дефолтный конфиг PostgreSQL я поменял, выдав ему то ли 64М, то ли 128М памяти для работы. то, что ему даётся по умолчанию -- просто смешно.

ADJ-P показал себя на самом деле просто суперски.

INSERT: линейный рост и скорость сравнима с ADJ-M, хотя на каждое добавление ноды идёт один лишний SELECT (получить кол-во существующих детей у родителя) и UPDATE (инкремент счётчика детей для родителя). это делается потому, что SELECT COUNT(*) в PostgreSQL сканирует всю таблицу (сравнить с MySQL, где эти данные берутся напрямую из дескриптора таблицы), поэтому получается дешевле поддерживать этот счётчик во время работы, чем пересчитывать его каждый раз по мере надобности.

PATH: да, пришлось реализовать рекурсию на процедуре, и выборка пути теперь производится красиво:



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

DESCENDANTS: тормоза-тормоза! но зато хоть рост практически линейный, да и выборка идёт с помощью рекурсии в хранимой процедуре, как это сделано в PATH, что очень и очень удобно для клиентского кода.

DELETE: в клиентском коде опять сплошные удобства -- удаляем только одну запись, а об остальном позаботится FOREIGN KEY. небыстро, но всё ж лучше, чем...

---

INT-P Nested Intervals
да, у меня получилось таки имплементировать Вложенные Интервалы. ну и поеботень же!
теория красива донельзя: смесь Nested Sets и Redundant Adjacency List, всё хранится в двух целых числах.
проблемы вылазят лишь на момент жёсткого использования механизма.

прежде всего, ограничение на кол-во нод в дереве. числа растут неприемлемо быстро, и обычного INT'а начинает нехватать, а переход на BIGINT, боюсь, ещё более затормозит, да и всё равно проблемы это не решит.

к тому же выборки потомков и предков производятся либо по функции с двумя умножениями и одним вычитанием (что жутко грузит процессор и дико тормозит), либо по числам с плавающей точкой (что не гарантирует точность).

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

---

---

в заключение только скажу, что я выбрал ADJ-P, т.к. всё остальное либо неудобно, либо тормозит. добавлю ещё пару хранимых процедур, чтобы максимально облегчить себе работу с кодом на стороне клиента, и будет мне щасье.