Введение

В 1970-х годах известный программист Эдгар Кодд разработал математически выверенную теорию организации данных в виде таблиц (реляций). С тех пор утекло немало воды — появилось большое количество различных коммерческих и open-source реляционных систем управления базами данных (РСУБД). Скоро стало понятно, что эффективное получение данных из базы — задача далеко не тривиальная. Если говорить прямо, она нелинейная и в общем случае NP-сложная.

Когда SQL-запрос становится немного сложнее: SELECT * FROM table, у нас появляется огромная вариативность его исполнения внутри системы — и не всегда понятно, какой из возможных вариантов эффективнее как по памяти, так и по скорости. Чтобы сократить огромное количество вариантов до приемлемого, обычно используются так называемые эвристики — эмпирические правила, которые придуманы человеком для сокращения пространства поиска на несколько порядков. Понятное дело, эти правила могут отсечь и сам оптимальный план выполнения запроса, но позволяют получить хоть что-то приемлемое за адекватное время.

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

Начнём с трёх моделей:

1. MSCN (2018) — модель для оценки кардинальности запросов

2. DQN (2018) — модель построения плана выполнения запроса

3. NEO (2019) — end-to-end-подход, объединивший в себе как обучаемую функцию оценки скорости выполнения заданного плана, так и само его построение

MSCN

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

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

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

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

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

Идея проста: необходимо натренировать алгоритм обучения с учителем предсказывать по заданному запросу соответствующую этому запросу кардинальность. Однако, по понятным причинам возникает 3 вопроса:

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

2. Какой именно алгоритм обучения с учителем выбрать

3. Где взять датасет из пар запросов и кардинальностей для обучения алгоритма

Фичи запроса

Запрос описывается в терминах теории множеств и представляет собой набор из трёх множеств: , где:

• — множество всех таблиц;

• — множество всех join'ов;

• — множество всех предикатов вида , например, выражение age > 18 записывается как (age, >, 18).

Фича для — это обычный one-hot-вектор, размер которого равен количеству таблиц в базе.
Для join'а вектор также является one-hot, обозначающим таблицы на объединение.
Для предикатов не сильно интереснее — тоже one-hot для категорий вида (column, operator), а value — результат MinMax-нормализации по соответствующему столбцу, лежащему в отрезке .

Схема алгоритма

В итоге получается следующая формальная схема:

То же самое, только с отображением внутренней структуры MLP можно увидеть на модульной схеме:

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

Математическое обоснование

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

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

Датасет

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

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

Результаты

Оценка результатов производилась на датасете IMDb с использованием как синтетически сгенерированных запросов, так и набора готовых (JOB-light), нацеленных на работу с join'ами.

Сравнивали с PostgreSQL 10.3, Random Sampling (RS) и Index-Based Join Sampling (IBJS).

Видно, что у MSCN самый маленький разброс по ошибке предсказания, что даёт чрезвычайно точные оценки с точки зрения среднего значения. По медиане IBJS попадает лучше, но по ресурсам затратнее.

Замечу, что при всём этом скорость работы модели находится в рамках нескольких миллисекунд на предсказание и не превышает 40 минут на обучение. И это всё без использования GPU.

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

DQN

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

Пусть у нас есть 4 таблицы: A, B, C, D и мы хотим их объединить: A⋈B⋈C⋈D. Для начала можем посчитать общее количество комбинаций перестановок данного набора, то есть A⋈B⋈C⋈D, A⋈B⋈D⋈C, A⋈C⋈B⋈D и т. д. Всего их, как известно из комбинаторики, . Но это ещё не всё. Также мы можем получить разный порядок их объединения, по-разному расставляя скобочки, то есть для A⋈B⋈C⋈D получим (((A⋈B)⋈C)⋈D), ((A⋈(B⋈C))⋈D), ((A⋈B)⋈(C⋈D)), (A⋈((B⋈C)⋈D)), (A⋈(B⋈(C⋈D))) — всего 5 штук. Чтобы лучше понять, как именно происходит это объединение, обычно рисуют соответствующие представления в виде деревьев:

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

Здесь — число Каталана, которое и задаёт количество правильных скобочных последовательностей. А теперь ради интереса объединим 10 таблиц (не такая уж и редкая ситуация на больших проектах). Посчитаем количество возможных комбинаций по формуле выше:. 17 миллиардов... Обычный перебор не подходит и, вообще говоря, в подобных задачах прибегают либо к жадному поиску (он будет почти всегда не оптимальным, но быстро выдаст ответ), либо к множеству эвристик в совокупности с динамическим программированием (когда мы запоминаем промежуточные результаты вычислений, чтобы использовать их в дальнейшем). Если мы знаем затраты на объединение (A⋈B), то пересчитывать его несколько раз, например, для выражений ((A⋈B)⋈С), ((A⋈B)⋈D) уже не нужно. Получается, что мы шаг за шагом перебираем множество планов, приходя к субоптимальному. В силу применённых эвристик он почти наверняка не будет лучшим, но даст уже неплохой результат.

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

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

Обучение с подкреплением

Сформулируем саму задачу обучения с подкреплением: 

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

Цель агента — найти такую политику , которая для любого стартового состояния максимизирует следующее выражение:

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

Максимизировать V(s) напрямую вообще говоря не получится, поскольку нам неизвестно правило выбора . Однако, мы можем выписать принцип, в связи с которым будем получать оптимальную политику. В роли этого принципа будет выступать так называемое рекуррентное равенство Беллмана:

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

Таким образом, мы получили условие оптимальности политики — удовлетворение некоторой Q-функции уравнению Беллмана. Но изначально нам неизвестна Q-функция. Она может задаваться либо в виде таблицы размером , где и — количество всевозможных состояний и действий агента соответственно, либо аппроксимацией в виде MLP. Вариант с таблицей — это алгоритм Q-learning, а с MLP — Deep Q-Network (или DQN). По понятным причинам Q-learning нам не подходит — уж очень много существует различных вариантов объединений таблиц между собой, как мы уже подметили ранее. Остаётся DQN. Независимо от представления Q-функции оптимизация будет происходить как обычно — градиентным спуском. Нам чрезвычайно важно удовлетворение Q-функции уравнению Беллмана, без его выполнения политика не оптимальна. В связи с этим шаг оптимизации вполне понятен: у нас есть аппроксимация Q-функции (поначалу она вообще рандомная) и есть Q-функция, полученная через саму же себя в уравнении Беллмана:

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

где — скорость обучения.

Поздравляю! Мы разобрались в основах работы DQN. Осталась лишь пара технических деталей.

Заметим, что в процессе обучения мы не всегда пользуемся Q-функцией для определения следующего действия. На начальных этапах обучения полезно заставлять алгоритм выбирать рандомные, неоптимальные действия, чтобы исследовать множество состояний S. Результаты рандомных исследований и действий агента будут записываться в так называемый Replay Buffer в виде кортежей , на которых затем также будет производиться оптимизация Q-функции. Описанная рандомизация выбора называется -greedy стратегией и выражается следующим образом:

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

Схема обучения ясна, сейчас необходимо понять, в каком формате передавать на вход DQNсостояние и действие для оценки Q-функции. Рассмотрим, что предлагают авторы.

Символом будем обозначать конкатенацию векторов. Входной вектор признаков будет состоять из следующих компонент .

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

Например, у нас есть 3 таблицы A(col1, col2, col3), B(col4, col5, col6), C(col7, col8) и следующий запрос:

SELECT col1, col2, col7 
FROM A, B, C 
WHERE A.col3=B.col4 AND B.col6=C.col7 AND A.col2 > 10;

Пусть также селективность предиката A.col2 > 10 будет равняться 0.2. Тогда.

Перейдём к векторам и . Они обозначают столбцы, стоящие соответственно слева и справа от оператора join. Т. е. в примере выше, если мы для определённости возьмём порядок объединения ((A⋈B)⋈С), где (A⋈B) уже посчитано, то и .

Остаётся вектор — one-hot, который определяет тип производимого join'а. Например, если у нас есть выбор только между HashJoin и IndexJoin, то для HashJoin , а для IndexJoin .

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

Генерация датасета

Датасет получается посредствам прогонки существующего алгоритма Bushy Dynamic Programming (Exhaustive) на наборе запросов. В процессе работы алгоритм генерирует не только оптимальный план для заданного запроса, но и в силу своей динамичности оптимальные субпланы для подзапросов. Здесь остановимся поподробнее. Пусть у нас есть запрос на объединение четырёх таблиц: B⋈A⋈C⋈D. В процессе просчёта всевозможных планов выяснилось, что оптимальным будет объединение ((A⋈B)⋈D), а не ((A⋈B)⋈C), тогда мы вполне легитимно можем добавить в общий обучающий датасет дополнительный пример для запроса A⋈B⋈D, в котором правильным порядком объединения будет ((A⋈B)⋈D). И таких вот дополнительных примеров получится , где N — количество таблиц. Авторы статьи продемонстрировали этот бонус на схеме ниже:

И ещё один нюанс: если в запрос на объединение идёт больше 10 таблиц, то начиная с 11-й происходит переключение на жадный алгоритм, чтобы не тормозить сбор датасета.

Результаты

В статье демонстрируются следующие результаты сравнения DQ с разными оптимизаторами на трёх разных функциях стоимости:

Здесь всё нормировано относительно Exhaustive-оптимизатора, который перебирает все планы, пока не найдёт оптимальный.

Видно, что DQ отрабатывает стабильнее и в большинстве случаев точнее, особенно на нелинейных функциях стоимости (CM2 учитывает использование дискового пространства во время выполнения гибридного HashJoin, CM3 учитывает возможность переиспользования построенных hash-таблиц).

Для CM2 приводится ещё одна таблица, в которой берётся разный memory limit M:

Видно, что чем меньше объём выделенной памяти, тем лучше результаты планирования запроса у DQ.

Отметим и такой параметр, как скорость формирования плана:

Видим, что скорость работы алгоритма не сильно зависит от количества таблиц (в отличие от того же Exhaustive) и начиная с 10 join'ов казалось бы затратная для CPU нейросеть начинает обгонять другие оптимизаторы. В целом данный результат в совокупности с отличными показателями на CM2 и CM3 даёт основание полагать, что применение обучения с подкреплением в совокупности с нейросетями может дать качественный скачок как в скорости работы оптимизатора, так и в скорости выполнения сгенерированных планов. Всё это очень важно при работе с большими объёмами данных в реляционных СУБД. Советую прочесть оригинальную статью, она прекрасно написана и содержит много подробностей и интересных для дальнейшего изучения аспектов.

NEO

В статье о NEO авторы утверждают, что до появления их подхода не существовало полного end-to-end-оптимизатора запросов, применяющего принципы ML на практике. И действительно:

• рассмотренный ранее MSCN оценивает только кардинальность запросов и непонятно, насколько эта оценка реально повлияет на построение и оптимизацию итогового плана;

• DQ реализует схему обучения с подкреплением для оптимизации плана, но при этом ориентируется на существующие эвристические функции стоимости.

NEO совмещает в себе все части реального оптимизатора, которые уже не опираются на придуманные эвристики, а обучаются на основе предоставленных данных. Они в полной мере реализуют свой потенциал, поскольку обучение происходит в end-to-end-пайплайне, где каждый шаг оптимизации учитывает работу сразу всех компонентов и их взаимное влияние друг на друга. Да, NEO всё равно необходимо обучать на конкретной базе данных с конкретными отношениями, но она гораздо ближе к работе реальных коммерческих систем, чем всё, что было до неё.

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

Начнём разбор со следующей схемы:

В верхней части видно, что, как и в случае DQ, в NEO собирается первоначальный датасет запросов с оптимальными планами их выполнения при помощи существующего оптимизатора PostgreSQL (так называемый этап Expertise). Затем собранный датасет помещается в блок Expirience, в котором хранятся обучающие данные. В процессе работы Experience будет пополняться уже сгенерированными планами с соответствующими для них Latency — реальным временем исполнения. Это пополнение позволит системе постоянно дообучаться и поддерживать актуальность производимых оценок:

Дальше на основе собранного датасета обучается центральный элемент всей системы — нейросеть по предсказанию затраченного времени на выполнение предоставленного запроса с соответствующим ему планом, так называемая Value Model.

Value Model

Для начала зафиксируем архитектуру сети:

Тренировка происходит по обычной схеме обучения с учителем: на выходе получаем число, которое сравниваем с реальным временем выполнения запроса и производим градиентную оптимизацию.

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

Фичи запроса

Фичи для запроса могут быть получены как при помощи one-hot-векторов, как уже делали в MSCN и DQ, так и при помощи семантических векторов.

С оne-hot всё понятно, а что такое семантический вектор в нашем случае? Под семантикой понимается вычленение смыслового вектора для заданного предиката при помощи дообученной word2vec, FastText или другой модели по получению текстовых эмбедингов:

Дообучение происходит на обычных текстовых предложениях. В качестве предложений здесь берётся объединение всех столбцов для каждой строки внутри денормализованной таблицы. Это позволяет ориентироваться на контекст внутри конкретной базы данных, что сильно повышает точность метода. Вообще говоря, идея интересная, потому что NEO при принятии решения будет ориентироваться на смысл предиката.

Звучит всё это непросто, поэтому рассмотрим на примере. Возьмём базу данных фильмов IMDb, которой мы отправляем следующий запрос:

SELECT count (*)
FROM title as t,
	movie_keyword as mk,
	keyword as k,
	info_type as it,
	movie_info as mi
WHERE it.id = 3
AND it.id = mi.info_type_id
AND mi.movie_id = t.id
AND mk.keyword_id = k.id
AND mk.movie_id = t.id
AND k.keyword ILIKE '% love %'
AND mi.info ILIKE '% romance %'

Во время обучения алгоритм выявит, что слова love из столбца keyword и romance из столбца info часто встречаются в одном контексте, что и выражается в метрике схожести Similarity:

Поэтому для запроса выше NEO использует не Nested Loop Join'ы, что сделал бы стандартный оптимизатор после оценки кардинальности близкой к 1, а Hash Join'ы, и это в свою очередь даст ускорение на 60%.

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

Сам по себе запрос мы можем представить в виде одного вектора, поскольку там нет упорядоченных данных. Выглядеть этот вектор будет примерно так (семантику здесь авторы не изобразили, уже знакомый составной one-hot):

Фичи плана запроса

А вот план запроса является упорядоченным, все операции представляют из себя узлы некого дерева, а таблицы — его листья: 

Каждый элемент дерева кодируется оne-hot'ами. Тут уже не составишь один сплошной вектор, потому что структура дерева от раза к разу будет отличаться. И как нам его обработать? На общей схеме сети видно, что сначала вектор запроса проходит через несколько полносвязных слоёв и конкатенируется к каждому элементу дерева. Затем это дерево с составными признаками попадает в блок графовой свёртки (если конкретнее, свёртки над бинарным деревом). Подробнее о таком виде свёрток можно почитать в статье. 

Поиск оптимального плана

Как при помощи Value Model можно получить оптимальный план? Схема схожа с DQ, когда мы перебираем все возможные продолжения текущего частичного плана и выбираем наилучшее из них. Только сейчас нейросеть выдаёт значение не Q-функции, а сразу значение стоимости, что делает модель более интерпретируемой и настраиваемой. В остальном оптимальная политика с точностью до знака определяется точно так же:

, где

• — текущий запрос с уже составленным частичным планом;

• — возможное продолжение частичного плана.

Результаты

Сравнение происходило на трёх разных датасетах и четырёх разных СУБД. Значения нормированы относительно скорости стандартного для выбранной СУБД оптимизатора таким образом: чем столбцы меньше единицы, тем лучше (единица — скорость исходного оптимизатора):

Мы видим, что скорость работы NEO в совокупности с исполнением полученного плана либо сравнима, либо превосходит существующие оптимизаторы (включая коммерческие SQL Server и Oracle).

Вывод

Получается весьма занимательная картина: почти везде нейросети обгоняют по качеству и производительности классические эвристические подходы, существовавшие на момент их создания. Однако засилия этих сетей на практике не наблюдается (типичная ситуация для большинства научных работ: результаты великолепные, а пользы никакой). По всей видимости разработка продуктового нейросетевого решения, которое будет удовлетворять всем нюансам работы реальных коммерческих систем, было дорого и сложно в 2018–19 годах. Инертность индустрии никто не отменял, а живём мы без преувеличения в переломное время. Возможно, именно сейчас мы станем свидетелями революции не только в мире языковых моделей, но и в мире реляционных БД. Но об этом уже в следующих статьях :)