Введение

Ранжирование — это уникальная разновидность задач в машинном обучении, обособленная как от классификации, так и регрессии. Заключительная статья по нейрооптимизаторам в РСУБД, как ни странно, связана именно с ней. Бум в развитии подобных моделей произошёл совсем недавно — в 2023 году, что мы с вами подробно разберём. Сначала погрузимся в ранжирование в целом, а затем увидим, как в соответствии с новой постановкой задачи адаптировались методы поиска оптимального плана исполнения запроса.

Создатели подхода LTR (Learning-To-Rank) предположили, что строить регрессионную ML-модель для предсказания стоимости выполнения плана запроса избыточно. По итогу всё сводится к выбору одного лучшего по оценке плана относительно других эквивалентных планов для заданного запроса. Т.е. на самом деле нам достаточно решить задачу ранжирования и, опираясь на признаковые описания планов, строить такую модель, которая начнёт предсказывать ранг (относительный порядок) для каждого плана для их дальнейшей сортировки и выбора наилучших. Преимущество здесь в том, что происходит упрощение модели и вместо аппроксимации сложной функции стоимости, которая оперирует масштабами абсолютных значений реального времени выполнения запросов, мы получаем простой ответ на следующий вопрос: «Лучше ли план относительно плана ?».  Какая нам разница, выполняется план 10 или 100000 миллисекунд, нам нужно знать лишь факт — лучше или хуже план , чем ? Этот подход позаимствован из рекомендательных систем, в которых важен сам порядок товаров в выдаче, а не их оценка по выбранной шкале релевантности. Собственно с этого мы и начнём.

Задача ранжирования

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

Метрики ранжирования 

Перед разбором основных методик нам нужна база, от которой мы сможем отталкиваться. В качестве базы возьмём метрики оценки качества сортировки объектов, полученной в результате работы модели:

DCG@k (Discounted Cumulative Gain at k) — дисконтированная сумма релевантностей первых k элементов отсортированного списка

Что такое релевантность? Задать её можно по-разному, но обычно берут либо — релевантен/нерелевантен, либо целочисленное значение от до какого-то , где — наименьшая релевантность, а — наибольшая. Дисконтирование — стандартный приём, когда нам нужно обращать больше внимания на первые объекты, нежели на последние. В случае дисконтирование вводится при помощи умножения на обратный логарифм позиции. Таким образом, получаем следующую формулу:

Ещё часто числитель модифицируют, чтобы больше внимания уделялось релевантным объектам:

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

NDCG@k (Normalized DCG@k) — нормализованный

где — максимальное возможное значение для имеющегося списка элементов.

P@k(q) (Precision at k) — точность по первым элементам отсортированного списка по запросу

Очень простая метрика, которая буквально выражает процент релевантных объектов в выдаче, т.е.:

где , если i-й элемент релевантен для запроса и наоборот — для нерелевантных элементов.

Очевидный минус этой метрики — она не учитывает позицию релевантных документов, как, например, делает DCG при помощи логарифмического дисконтирования. Следовательно, нужно эту метрику немного усложнить. 

AP@k(q) (Average Precision at k) — усреднённая точность по первым элементам отсортированного списка по запросу

Усложнение вводится так: каждому релевантному объекту в выдаче на позиции мы будем назначать вес :

Т.е., если i-й объект релевантен и предыдущие объекты тоже релевантны (P@i(q) высокий), то он будет вносить большой вклад в AP@k(q). Если же вдруг среди первых объектов будет много нерелевантных (P@i(q) низкий), то и вклад i-го объекта будет также низким. Таким образом, нам важно, чтобы вначале выдачи было как можно больше релевантных объектов, поскольку после каждого нерелевантного P@i(q) будет падать и тем самым тянуть вниз все оставшиеся элементы списка.

Пример:  для (1 1 0) > для (1 0 1) > для (0 1 1)
А везде будет одинаковым и равным

MAP (Mean AP) — среднее от усреднённых точностей по всем запросам

Название этой метрики звучит как тарабарщина — к сожалению, «mean» и «average» переводятся одинаково :)

Считается MAP буквально, как среднее от AP по каждому запросу:

где — количество всех запросов.

Как же научить модель сортировать множество заданных объектов по их относительной релевантности? Для этого существует несколько основных подходов:

Pointwise 

Подход, который учится присваивать каждому объекту по отдельности некую истинную оценку и затем использует её для сортировки элементов списка. В общем-то это и есть регрессия, которая адаптирована под ранжирование, только не оптимизирует ранжирующие метрики напрямую и не учитывает взаимное расположение объектов между собой. Короче, это направление нас не сильно интересует.

Pairwise 

Подход, работающий с парами объектов:

1. В процессе обучения берётся два объекта из примера: ,

2. Для каждого объекта оценивается скор: и , где — результат работы модели с тензором параметров на объектах , соответственно

3. Считаем разность

4. Далее вводим логистическую функцию потерь и считаем, что — это вероятность события , т.е. что объект окажется выше, чем

5. Таким образом, всё свелось к бинарной классификации, которая может решаться огромным спектром параметризованных моделей, начиная логистической регрессией с бустингами и заканчивая нейросетями (RankNet/DirectRanker):

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

Listwise

Подход, который оптимизирует метрики ранжирования напрямую, что является весьма нетривиальной задачей.

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

LambdaRank

Одним из таких подходов является LambdaRank, который использует ту же методику обучения, что и рассмотренный ранее pairwise, однако в дополнение ко всему в нём оптимизируемый функционал для пары объектов , домножается на — изменение метрики при перестановке пары объектов между собой:

где истинный скор такой, что .

Таким образом, во время оптимизации мы как бы придаём больше значения тем парам объектов, изменение относительного местоположения которых будет сильнее всего влиять на желаемую метрику . К сожалению, такой трюк — всего лишь эвристика, эффективность которого доказывается только эмпирически.

SoftRank

Дальнейшие разработки в этой области концентрируются на более теоретически обоснованном способе внедрения метрик ранжирования в оптимизируемый функционал, прибегая к использованию вероятностных распределений над истинным скором наших объектов. Например, создатели SoftRank вместо предсказания детерминированных оценок для элементов списка вводят нормальное распределение следующего вида:

где стандартное отклонение — это просто гиперпараметр, а — результат работы модели с тензором параметров на объекте .

Теперь мы можем посчитать вероятность того, что объект окажется выше в ранжировании объекта :

И, наконец, магический шаг, после которого получим дифференцируемый аналог — необходимо оценить вероятность того, что объект будет иметь ранг после добавления элемента под номером к уже имеющемуся списку. Сделаем это рекурсивно:

1. Очевидно, что когда , то , т.е. вероятность
   получить лучший ранг для -го элемента равна единице.

2. Пусть у нас имеется элементов списка и добавляется -й. Тогда по формуле полной вероятности имеем следующее соотношение:
   
   

   Формула получилось громоздкой, но не сильно сложной. Разберём её по частям:

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

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

Авторы очень чётко показывают произведённый переход от детерминированного ранжирования к стохастическому следующим рисунком:

Осталось только выписать новый SoftNDCG, полученный после замены дисконтирования, требующего сортировки, на мат ожидание дисконтирования по всем возможным рангам для j-го элемента:

Можно это выражение переписать и в обобщённом виде, как обычно принято делать:

где — скор объекта, а — введённый метод дисконтирования.

Понятное дело, что теперь можно прикручивать к любой параметризированной ML-модели, как уже было показано в случае pairwise-подходов и задачи бинарной классификации. Ещё замечу, что для получения listwise-функции потерь, нужно не забыть в алгоритме градиентного спуска использовать со знаком минус, поскольку минимизация даст максимизацию самого , а, следовательно, максимизацию , что нам и нужно.

Посмотрим теперь на зависимость от применения выведенных Listwise-функций потерь:

В отличие от pairwise-подхода на графике заметна прямая зависимость метрики ранжирования от значения лосс-функции.

LambdaLoss

LambdaLoss — ещё один подход, который обобщает LambdaRank, вводя вероятностное распределение над всеми возможными перестановками объектов в списке относительно предсказанного для них скора:

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

Затем, основываясь на принципе максимальной правдоподобности, вводится следующая лосс-функция:

Путём подстановки соответствующих вероятностей и можно получать разный лосс для разных моделей, включая RankNet-loss, SoftRank-loss, LambdaRank-loss и, наконец, LambdaLoss. Затем вводится итеративный EM-алгоритм для поиска наилучшей модели :

где — выражение, полученное применением неравенства Йенсена.

Давайте теперь посмотрим, как в этой форме можно представить loss, связанный с метрикой :

Для начала авторы определяют , как:

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

Далее вводится в некотором смысле обратная функция — :

Таким образом, чем больше , тем меньше . Теперь производится её верхняя оценка:

где — гиперпараметр, — пороговый loss, равный единице в случае, когда и нулю во всех остальных. Пороговый loss аппроксимируется сверху гладкой логистической функцией, что и показано в выведенной выше оценке, графически же это выглядит так:

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

где — так называемое «hard assignment distribution», не равное нулю только для перестановки , элементы в которой отсортированы в убывающем порядке по скорам .

И остался последний чисто технический шаг — авторы преобразуют полученное уравнение в более гибкий вид:

На этом с ранжированием закончим — именно в такой форме LambdaLoss используется в рассматриваемом LTR-оптимизаторе, к разбору которого мы сейчас и приступим.

Схема LTR-подхода

По сравнению с выводом LambdaLoss суть самого пайплайна довольно проста:

Сначала на вход поступает SQL-запрос, который затем попадает в цикл построения плана при помощи модификации стандартного оптимизатора. Модификация заключается во встраивании LTR-модели в процесс сравнения эквивалентных планов между собой. Но обо всё по порядку — начнём с того, как в принципе сформировать датасет для обучения модели задаче ранжирования:

Формирование датасета

Может показаться, что разметить планы перед обучением ранжированию достаточно просто — сортируем планы по времени выполнения и получаем их ранг в виде соответствующих позиций элементов списка. Однако в одних случаях разница в 5 миллисекунд может быть несущественной (например, в OLAP-запросах), а в других колоссальной (например, в OLTP-запросах). Поэтому для первого случая мы бы хотели назначить элементам одинаковый ранг, а во втором — разный. Для решения этой проблемы авторы применяют иерархическую кластеризацию, отсекая выбросы по времени и задавая количество кластеров в качестве регулируемого гиперпараметра:

Затем планы распределяются по кластерам, которые в дальнейшем сортируются по минимальному времени выполнения плана в рамках каждого кластера. По итогу все планы, входящие в -й кластер, получат .

Кодирование признаков

Аналогично Bao, в дереве плана кодируются только физические операторы при помощи one-hot, что позволяет модели не зависеть от конкретных таблиц в базе данных:

Для векторизации самого запроса используются 2 one-hot значения, обозначающие наличие операций ORDER BY и GROUP BY, а также 4 числовых признака: количество join'ов, оцененное количество строк в итоговом результате, максимальное и минимальное количество строк во всех таблицах, участвующих в запросе.

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

Инференс ранжирования

После шага с кодированием всё поступает на вход, можно сказать, несменяемым графовым свёрткам, тенденцию к использованию которых ввёл Neo:

В самом верху схемы Sub-Model 1 выделяет признаки из закодированного вектора запроса. Затем эти признаки присоединяются к дереву плана аналогично Neo.

Видим, что текущий план в схеме рассматривается отдельно и поступает в свой собственный расширенный пайплайн Sub-Model 2 для выделения признаков. Остальные эквивалентные планы идут на вход одной и той же Sub-Model 3, урезанной версии Sub-Model 2 для формирования усреднённого вектора контекста, который затем объединяется с вектором текущего плана и, проходя через Sub-Model 4, редуцируется до одного единственного числа — скора текущего плана. Проделав это вычисление для каждого плана из списка, получаем скоры, которые на трейне используются для оптимизации LambdaLoss'а, а на инференсе — для выбора самых быстрых планов из списка эквивалентных.

Остаётся последний вопрос — как в принципе встроить такой нетипичный LTR-подход в существующий пайплайн поиска плана? Ведь большая часть алгоритмов основана на попарном сравнении двух планов и выборе наилучшего. Вследствие этого авторам пришлось модифицировать существующий bottom-up алгоритм DPccp. Изначально в нём происходит последовательное наращивание подграфов с использованием pairwise-сравнений, приводящих к построению оптимального графа выполнения запроса. Модификация же предполагает не огромное количество попарных сравнений всех возможных вариаций эквивалентных планов, а их первоначальное накопление до некоторого заданного количества , а затем выбора топ-k наилучших в результате работы разобранного LTR. 

Результаты

Свою LTR-модель авторы сравнивают с 4 равными подходами:

1. Bao

2. Neo

3. Baseline model — pairwise LTR модель, чья архитектура схожа с Bao

4. DB X — по традиции неназванная хорошо настроенная коммерческая база данных

Всего в сущности было проведено 3 теста:

1. На датасете TCP-H 1GB с тренировкой на нём же

2. На датасете TCP-H 5GB с тренировкой на TCP-H 1GB

3. На датасете IMDB/JOB с тренировкой на TCP-H 1GB

Третий тест в особенности интересен, поскольку покажет способность модели работать в произвольной БД без необходимости в дообучении.

Запросы для TCP-H генерировали с использованием DataFarm — инструмента для аугментации ограниченного набора запросов.

Посмотрим на результаты первых двух тестов:

В первом тесте (график слева) видно, что LTR, будучи обученной на той же БД с теми же данными, обгоняет нейросетевые подходы и сравнима с DB X.

Во втором тесте (график справа), в случае когда данных в БД больше и они не использовались в процессе обучения, ситуация схожа, но также становится заметно доминирование по скорости на длинных запросах, включая примечательный обгон DB X.

В третьем тесте демонстрируется производительность моделей, обученных на TCP-H, но прогоняемых на IMDB/JOB. При этом отмечается, что в JOB присутствуют запросы, производящие вплоть до 11 join'ов, тогда как на обучении максимально было 7 join'ов — это покажет способность модели экстраполировать свои знания на общий случай произвольного числа join'ов. Картина получается следующая:

Neo здесь заочно проигрывает и не берётся в сравнение, поскольку он не адаптируется под изменение схемы БД. Bao почти везде уходит в таймаут, оно и не удивительно — Bao нужно периодически дообучать на новой нагрузке с новыми данными, чего по всей видимости не делалось. В конкурентах остаются только DB X и baseline pairwise-подход. По графику видно, что baseline pairwise везде либо сравним, либо проигрывает LTR-модели, следовательно, он проигрывает и в этом раунде. А вот с коммерческой БД уже не всё так однозначно — на быстрых запросах модель ранжирования либо проигрывает, либо сравнивается с DB X, однако на медленных обгон по скорости может быть более, чем в два раза. В любом случае ситуация для LTR отличная — она не только не посыпалась при смене БД вместе с рабочей нагрузкой, а выстояла и смогла состязаться с коммерческими системами.

Вывод

Рассмотренная LTR-модель и правда уникальна — она впитала в себя как существующие лучшие практики уже рассмотренных нейросетевых оптимизаторов (Часть 1, Часть 2), так и массу других трудов из теории оптимизации, рекомендательных систем и классического ML. По итогу такой кропотливой работы был изобретён совершенно новый подход, результаты которого говорят сами за себя.

Позже появилось ещё несколько схожих алгоритмов, такие как LEON и COOOL, но рассмотренный в этой статье метод все-таки был первым. Конечно, нужно время, чтобы сделать окончательные выводы об эффективности и применимости этого класса подходов к решению задачи поиска оптимального плана выполнения запроса. Однако уже сейчас можно сказать, что переход к постановке задачи ранжирования выглядит более естественным и может дать свои плоды в коммерческих продуктах уже в ближайшее время.