Введение

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

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

Bao

Bao можно воспринимать как логическое продолжение и развитие идей, заложенных в Neo. Более того, создатели Bao и Neo — одни и те же люди!

Эта модель хоть и появилась 4 года назад, но до сих пор фигурирует в сравнениях, и на её основе делают большое количество модификаций. Именно Bao взялась за исправление недостатков, которые останавливали индустрию от внедрения нейрооптимизаторов в продуктовые решения. Например:

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

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

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

4. Очень плохая работа на малом числе запросов (так называемая проблема хвостовых примеров). Дело в том, что в среднем обученный нейрооптимизатор генерирует план качественнее, чем стандартные оптимизаторы. Если взять наиболее типичный запрос — на нём всё отработает хорошо. Однако на редких, уникальных по своей структуре запросах, качество нейросети может сильно падать (вплоть до 100 раз) — это просто неприемлемо в большинстве реальных задач. Что если именно на таком запросе будет выстроена важная логика работы системы? Есть хорошая иллюстрация для понимания концепции хвоста на нашем примере:

Таким образом, на «Coffe» и Coffe« Beans» всё будет хорошо, потому что именно они создают основной костяк обучающих примеров (на схеме трамплин распределения начинается именно с них, поэтому их количество будет подавляющим). А вот для примера, типа «Medium Roast Coffee Beans Vacuum Pack» выйдет катастрофа. Этот пример почти не вписывается в общую канву, да их и не так чтобы много — поэтому модель просто предпочтёт игнорировать ошибку, возникающую при обработке подобных хвостовых элементов, даже если она будет колоссальной. 

Чтобы превзойти как open-source, так и коммерческие оптимизаторы, обучение Bao (Bandit optimizer) может занять до нескольких часов. При всём этом он не будет допускать сильных ошибок на хвостовых запросах, как это делали предыдущие подходы. Также Bao продолжает хорошо выполнять свои функции при изменении схемы БД, рабочей нагрузки и данных в таблицах. Он не отменяет все предшествующие наработки вручную настроенных оптимизаторов — как бы не хотелось признавать, в них вложена мудрость нескольких поколений умнейших программистов. Так почему бы не использовать её вместе с нашими обучающимися машинами? 

Разбор алгоритма

Основная идея Bao — встать над базовым оптимизатором и давать ему грубые подсказки, ориентируясь на текущий запрос и то, есть ли сейчас какая-то информация в кэше. Например, модель решит, что лучше не применять loop join'ы в определённой ситуации или отказаться от последовательного сканирования таблиц в пользу использования индекса и т.д. Посмотрим на схему алгоритма:

Сначала на вход поступает SQL-запрос, он прогоняется через существующий оптимизатор, который генерирует множество разных планов — по одному на каждое множество подсказок (Hint set). Далее планы поступают на вход уже знакомой нам графовой свёртке, после которой на основе выделенных признаков предсказываются награды, полученные за выполнение планов. Здесь и замечаем основное сходство с Neo: схема выделения признаков, обучения и дообучения предсказательной модели по сути своей идентичны. Однако отличие в том, что Bao не генерирует весь план выполнения запроса с нуля, а лишь выбирает, по его мнению, лучший из уже сгенерированных базовым оптимизатором.

Но не может ведь Bao сразу применять необученную политику на старте своей работы? Каждая такая подсказка — отдельная рука в схеме контекстуального многорукого бандита.

Контекстуальный многорукий бандит

В контекстуальном многоруком бандите (Contextual multi-armed bandit — CMAB), как и в обучении с подкреплением (RL), есть некий агент. Он должен выбрать одно из нескольких доступных действий (рук) в каждом раунде на основе наблюдаемого контекста. Агенту нужно найти баланс между исследованием (exploration) и использованием (exploitation) доступных действий для максимизации накопленной награды. Таким образом, CMAB — это упрощённая версия RL, где агенту не нужно строить долгосрочную стратегию выбора множества последовательных действий, ведущих к финальной награде. Здесь всего одно действие сразу приносит конечный фидбек, что позволяет решать задачу методами с более быстрой сходимостью. Среди таких — сэмплирование Томсона, который авторы Bao и взяли за основу.

Cэмплирование Томсона

Крайне интересный способ решения задачи многорукого бандита. Он связан с вероятностной методологией выбора действия относительно уже прожитого опыта — мы случайно выбираем план, а не просто берём самый оптимальный как в большинстве ML алгоритмов. Если модель сильно уверена, что какой-то план выполнится быстрее остальных — он будет выбран с большей вероятностью, но не наверняка. Всегда остаётся шанс выбрать не самый оптимальный план по оценке модели. Но сделав это, она исследует пространство планов и, возможно, обнаружит, что положение дел изменилось и стоит начать выбирать именно этот, недооценённый ею вариант. 

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

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

Векторизация признаков

Осталось посмотреть, как именно векторизуется план в разбираемом алгоритме. Ведь мы помним, что Bao как-то решает проблему адаптации к изменяющимся таблицам базы данных.

Здесь всё проще, чем кажется — Bao при векторизации вообще не учитывает ни конкретные таблицы, ни конкретные столбцы, как было в предыдущих подходах. Взглянем на сравнение векторизации в Bao и Neo:

Bao, в отличие от Neo, кодирует только сами операторы. В остальном всё так же — one-hot для типа оператора (с учётом null, чтобы всегда получалось бинарное дерево) и 2 числовых значения в конце для кардинальности и стоимости соответственно. Для учёта большего количества динамики можно добавить one-hot значение для имеющегося кэша, что, конечно, будет подсказкой для оценки фактического времени исполнения плана в реальных продуктовых базах.

Результаты

Что отличает статью о Bao от уже рассмотренных мной, так это объём практических экспериментов на реальных продуктовых задачах.

1. Сравнения проводили на PostgreSQL (с Bao и без), а также на неназванной коммерческой СУБД (с Bao и без).

2. В качестве бенчмарков использовали IMDb, Stack и Corp датасеты — каждый со своей спецификой под конкретный кейс (изменение схемы БД/изменение рабочей нагрузки/изменение данных).

3. И вишенка на торте — использовали реальные облачные серверы от Google Cloud разной конфигурации (от 2 до 16 ядер CPU + T4 GPU). Измеряли, как затраченные деньги на все использованные мощности, так и качество/скорость модели.

Посмотрим на детальные показатели для датасета IMDb:

Графики слева указывают на зависимость стоимости в центах от конфигурации сервера и оптимизатора. Справа — совокупное время работы каждого оптимизатора в минутах, включая время на формирование плана, обучение и выполнение запросов (опять же в зависимости от конфигурации). Общая тенденция очевидна — Bao везде выигрывает по стоимости и скорости, независимо от конфигурации облачного сервера (2/4/8/16 ядер).

Аналогичная картина будет наблюдаться на остальных датасетах (везде конфигурация для 16 ядер):

Ещё у нас произошло снижение времени, затраченного на хвостовые примеры (в статистике бы их назвали выбросами):

Видим, что на перцентиле 99.5% сильно снижается общее время построения и исполнения запроса.

Остаётся ещё одна финальная схватка со своим концептуальным прародителем — Neo. Посмотрим на суммарное количество выполненных запросов при прогонке IMDb датасета 20 раз подряд на 16 ядрах CPU:  

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

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

Balsa

Оставим дивный мир совмещения существующих оптимизаторов с ML-моделями. Наш следующий подход, Balsa — это чисто нейросетевой оптимизатор. Его схема выглядит следующим образом:

Он схож как с Neo, так и с DQ, но, тем не менее, принципиально отличается:

Из таблицы видно, что Balsa вобрала в себя все самые продуктивные идеи предыдущих подходов, но избавилась от их существенного недостатка — использования результатов работы экспертных систем. Как же Balsa удаётся справиться с построением плана, не прибегая к человеческим наработкам? Ведь обучение политики с нуля вместе с исполнением каждого плана — катастрофически долго сходящийся процесс.

Здесь и возникает так называемый Minimal Simulator.

Minimal Simulator

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

где - оцениваемая кардинальность таблицы или join'а в плане с учётом фильтраций.

Конечно, в общем случае это предположение просто неверно. Однако, если модель научится следовать этому принципу перед тем как столкнётся с реальной средой, она не будет на старте генерировать слишком плохие планы, которые на несколько порядков дольше экспертных. Таким образом, мы как бы ускоряем сходимость метода и не даём создавать планы, уходящие в timeout, что особенно критично в продуктовой среде. В таблице выше уже упоминали, что майнинг датасета для симулятора аналогичен DQ и состоит из следующих троек: (запрос, план, стоимость выполнения запроса).

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

Результаты

Посмотрим, насколько Balsa лучше предыдущих подходов. Машинка для тестов — 8 CPU, 64GB RAM, SSD и GPU Tesla M60 для обучения.

Во-первых, идут сравнения с оптимизаторами PostgreSQL 12.5 и не названной коммерческой CommDB:

Единица в данном случае — результат работы стандартного оптимизатора, а по столбцам — результаты для Balsa на train и ранее не виданном test соответственно. Видим 3 разных группы бенчмарков:

1. JOB — скорость на всём бенчмарке JOB

2. JOB Slow — скорость на медленных (краевых) запросах в бенчмарке JOB

3. TPC-H — бенчмарк для тестирования на искусственно сгенерированных данных, взятых на основе равномерного распределения (параметр scale factor, отвечающий за объём генерации, у авторов равен 10)

Везде результат на train, очевидно, лучше чем на test. В любом случае сеть учится обобщать найденные закономерности и практически везде обходит экспертные системы.

Однако, мы с вами помним, что сходимость у RL-подходов очень долгая и Neo, например, нужно было порядка суток, чтобы обогнать существующий оптимизатор. У Balsa, в связи с пройденным симулятором, такой проблемы не возникает, и он выходит на неплохой уровень уже через 2-3 часа работы на всех бенчмарках:

А что по сравнению с Neo? Как-никак Balsa отличает только использование симулятора и переход на on-policy RL-схему, когда текущая политика постепенно дообучается на основе своих же принятых решений.

Получается очень интересная картина. Во-первых, Balsa на первых итерациях генерирует планы примерно в 5 раз быстрее благодаря обучению на симуляторе. Далее на train они вроде бы сравниваются, но на тесте видно, что Balsa гораздо более стабильна и не позволяет себе строить катастрофически долгие планы выполнения запросов, что указывает на лучшую способность к обобщению. И ещё — поскольку Neo быстро копит Experience-датасет, на котором в процессе полностью переобучает модель, он постепенно замедляется. И, например, чтобы прогнать 100 итераций, Balsa потребовалось всего 2.6 часа, а Neo — 25 часов! Вот так казалось бы незначительные модификации заметно улучшают перформанс выбранной архитектуры.

Авторы метода не поленились и произвели завершающее сравнение с Bao:

Не удивительно, что Balsa почти везде превосходит Bao, это следствие большего количества степеней свобод у RL-моделей, необходимых для поиска оптимума. Однако сохраняется естественный в этой связи недостаток Balsa, а именно невозможность быстро адаптироваться под изменения в БД.

AQO (Adaptive Query Optimization)

Раз уж мы разбираем production-ready решения в области нейросетей и всего машинного обучения в целом, не могу не упомянуть удачный пример адаптации и применения классического ML-алгоритма K ближайших соседей к задаче оценки кардинальности запросов. AQO, или адаптивный оптимизатор запросов, разработали мои коллеги из Postgres Professional ещё в 2017 году, и он до сих пор развивается в рамках СУБД Postgres Pro и отдельного репозитория на GitHub. 

Если вкратце, в данном подходе формируется выборка объектов, признаками которых являются значения селективностей по каждому предикату выполняемого SQL-запроса (эти значения берутся из гистограмм, которые строит postgresql). Для всех таких объектов имеются истинные итоговые значения селективностей, собранные после выполнения соответствующих запросов. Вот и получаем задачу построения регрессионной предсказательной модели, способной неплохо улучшить работу базового оптимизатора с учётом уже прожитого опыта. Были опробованы разные архитектуры — и на основе бустингов, и на основе нейросетей, но на практике лучше себя показал именно KNN. Вообще, весь смысл в идее представления самой модели в виде некоторой неизвестной функции, а как именно её искать — вопрос имплементации.

На Хабре уже была статья, где детально разобраны все аспекты AQO 1.0 — для его изучения советую обращаться туда. На текущий момент актуальным является AQO 2.0, который был выпущен год назад. В нём улучшены производительность и удобство пользования в связи с оптимизацией и упрощением многих сложных элементов системы (соответствующие изменения можно посмотреть в презентации).

Вывод

Итог прост — ML в общем и нейросети в частности могут успешно справляться с вызовами, которые возникают у реального бизнеса. Многие из рассмотренных подходов уже развиваются как в open-source, так и в коммерческих СУБД, что не может не радовать. Остаётся разобрать несколько уникальных по своей природе моделей, которые делают ещё один важный шаг в развитии нейросетевых оптимизаторов запросов — об этом расскажем в новой статье.