⏱️ T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees
#tum #redshift #execution #pipeline #decisiontree #lleaves

🥼 Article

В статье описан механизм оценки времени выполнения запроса, еще до его непосредственного выполнения.

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

🪨 Intro

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

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

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

Когда запрос прилетает в БД, он проходит через несколько важных фаз:
* Parsing, запрос разбивается на AST дерево
* Построение и оптимизация Logic Plan, где используется информация о таблицах и линейная алгебра чтобы определить в каком порядке узлы графа стоит исполнять и какие можно оптимизировать.
* Execution Plan можно сказать что это непосредственный план выполнения запросов. Даже 1 логический план можно сконвертировать в несколько разных вариантов исполнения, например используя разные алгоритмы для Join (HashJoin vs SortJoin / Memory Join vs Disk Join)
* Execution или непосредственное исполнение.

Execution Plan выглядит как дерево с Pipelines, это участки исполнения запроса на критическом пути между Pipeline Breakers (когда нельзя начать следующий pipeline, не завершив предыдущий). (pic 1)


💡Idea №1: Давайте оценивать каждый отдельный Pipeline, а суммарно запрос как сумму этих Predicted Times.

Прямое и корректное решение, следующий вопрос -- как быстро и корректно оценивать эти отдельные pipelines?
Для каждого запроса они могут сильно отличаться, они отличаются как по набору данных (на вход, на join, на выход, так и по применяемым преобразованиям).


💡 Idea №2: Давайте для каждого pipeline создадим Feature Vector, который будет хранить в себе описание и научим ML оценивать время этой части.

Выглядит это примерно как на (pic 2), вектор довольно большой, под сотню параметров для описания.
Если так получается что конкретный Pipeline мы плохо оцениваем, то можно всегда углубляться и добавлять новых feature для описания и дообучать систему.
Благодрая этому получается оценивать pipelines как генерализированную сущность, которая не зависит от самих таблиц / данных.
Т.е. не надо дообучаться на данных, чтобы корректно оценивать время.


💡 Idea №3: Теперь для каждого из feature-vector нужно оценить примерное время, для этого попробуем натренировать Decision Tree на feature-vector's от синтетических запросов.

Decision Tree это клевый способ, потому что для некоторых задач позволяет написать очень эффективный и быстрый inference на cpu.
Он отлично подходит для задач категоризации/оценки когда есть подготовленный feature-vector.
Автор гонял обучение на ноуте ночью, и на утро у него было много деревьев которые хорошо могли оценивать время исполнения запросов.


💡 Idea №4: Q-Error as Error Function: Q-Error(predicted, observed) = max( predicted / observed, observed / predicted)

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

💡 Idea №5: Компиляция DecisionTree с помощью lleaves

Используемый LightGBM позволил построить несколько DT, и пробегаться по ним чтобы оценивать время и в среднем это занимало ~22us.
Но есть замечательный https://github.com/siboehm/lleaves, который позволяет скомпилировать дерево в код, который будет исполняться заметно шустрее.
⚡ Читать его конечно станет невозможно, но это и ненужно, а время работы 4us. (pic 3)


📝 Conclusions