Я занимаюсь разработкой баз данных с 1999 года и сейчас работаю над YDB — базой данных, которую мы в Яндексе недавно выложили в опенсорс. Это моя шестая база данных и четвертая — массивно-параллельная. И каждый раз, когда основные задачи решены, я сажусь разрабатывать оптимизатор запросов. Под катом я кратко расскажу о том, что такое оптимизаторы запросов в базах данных и почему их непросто делать.
Немного истории
Многие проекты в Яндексе развиваются по похожему сценарию. Команда разработчиков делает новый продукт, показывает его пользователям, проверяет гипотезы, собирает обратную связь. Но если в обычном стартапе органический рост пользователей занимает годы, то с нашими масштабами новый продукт может очень быстро привлечь несколько миллионов пользователей.
Вместо того чтобы пилить фичи и тестировать гипотезы, приходилось заниматься шардированием на уровне приложений. И в 2008 году мы поняли, что нам нужна собственная база данных, которая должна отвечать двум ключевым требованиям:
Хорошо горизонтально масштабироваться. Чтобы можно было начать с нескольких серверов, а по мере увеличения пользовательской базы добавлять новые и получать линейный рост RPS из доступного дискового пространства.
Быть не просто отказоустойчивой, а «катастрофоустойчивой». То есть продолжать работать, если вышел из строя дата-центр, а потом сгорело несколько случайных серверов в стойках. С нашими масштабами серверы выходят из строя постоянно, и это никак не должно влиять на доступность сервисов для пользователей.
Поэтому в 2012 году мы начали разрабатывать собственную базу данных, которую через десять лет выложили в опенсорс как YDB. Вначале база данных работала с транзакционной нагрузкой. Но по мере накопления сотен терабайт данных у бизнеса появлялось больше поводов проводить по ним аналитику. Мы перепробовали много разных способов выполнять аналитические запросы к существующей транзакционной базе и поняли: если хочешь сделать что-то хорошо — сделай это сам. И несколько лет назад начали работу, чтобы в итоге добавить в YDB возможность выполнять аналитические запросы.
OLTP и OLAP: два очень разных типа нагрузки
Транзакционные и аналитические запросы используют одинаковый синтаксис SQL, но это совершенно разные виды нагрузки. Высоконагруженный сервис внутри Яндекса отправляет к базе данных миллионы запросов в секунду и ожидает, что время выполнения каждого из них будет не больше, чем пара сотен миллисекунд. OLTP-запросы похожи друг на друга, они обычно несложные и в основном работают с нормализованными данными, аккуратно разложенными по таблицам.
Аналитических запросов немного, но они значительно отличаются от транзакционных. Отправленный аналитиком OLAP-запрос обычно пишется с нуля, в нем много JOIN'ов и агрегатов, и он часто предназначен для работы с денормализованными данными. И если каждый транзакционный запрос читает и пишет небольшую часть данных, то аналитические запросы обычно обрабатывают огромные таблицы целиком.
Для OLAP нужен быстрый и качественный оптимизатор запросов
Прежде чем SQL-запрос начнет выполняться, для него нужно составить план: в каком порядке и на каких серверах проводить операции. И если транзакционная база с простыми запросами может прожить с несложным оптимизатором, то для сложных аналитических запросов необходим технически сложный оптимизатор. И не только потому, что начинающим аналитикам сложно оптимизировать запросы. Мы проводили тесты и убедились, что уже при 6–7 JOIN'ах у программиста нет шансов самому оптимизировать запросы. Чтобы найти точное решение, придется перебирать все варианты, так как задача поиска оптимального плана является NP-полной.
После того как один из серверов базы данных получает запрос, этот запрос передается оптимизатору. Оптимизатор должен перебрать варианты выполнения запроса и выбрать тот, который потребует меньше ресурсов для выполнения. Что значит «меньше ресурсов»? Давайте я поясню вот на таком примере:
SELECT * FROM deals
JOIN customers ON deal.customer_id = customers.id
JOIN managers ON deal.manager_id = managers.idБаза данных может выполнить такой запрос двумя способами:
Вначале объединить таблицу deals с таблицей customers, а затем получившееся — с таблицей managers.
Или наоборот: вначале объединить deals и managers, а затем получившееся — с customers.
Выбрать нужно тот вариант, при котором после первого JOIN'а в памяти нужно будет держать меньше данных.
Для простого запроса аналитик может руководствоваться здравым смыслом, осмотреть таблицы и данные, оценить количество сообщений, индексы. Может даже воспользоваться дополнительными возможностями YQL — нашего собственного языка, значительно расширяющего синтаксис SQL. Но если JOIN'ов несколько десятков, то единственный способ найти лучший план запроса — это перебрать все возможные комбинации.
Как оптимизатор перебирает комбинации
Есть два популярных подхода к перебору вариантов построения запроса. Оба варианта основываются на принципе динамического программирования, придуманном в 50-х годах математиком Ричардом Беллманом. Любопытно, что, когда автор выбирал название, слово «программирование» еще не использовалось в том значении, в котором мы его употребляем сейчас. Тогда «программирование» было синонимом слова «оптимизация». А термин «динамическое» обозначал, что алгоритм выполняется пошагово и каждый следующий шаг зависит от результатов предыдущего. Так что если бы название давали сейчас, то получился бы «пошаговый оптимизатор».
Для подхода top-down оптимизатор начинает перебор с завершающей («верхней») операции в запросе, рекурсивно перебирая все варианты выполнения для дочерних («нижних») операций. У такого подхода есть сильная сторона: программисты могут просто и понятно описать правила оптимизации, которые будут применяться для известных ситуаций. Правила могут быть произвольными, что позволяет оптимизировать широкий спектр свойств планов. Недостаток подхода — высокие накладные расходы на сравнение, применение правил и перебор ненужных комбинаций. Так как задача перебора экспоненциальная, с этими расходами нельзя оптимизировать сложные планы: в реалистичных условиях подход top-down не позволит построить план, если в запросе больше десяти JOIN'ов.
Мы используем второй популярный подход, который называется bottom-up. Принцип этого подхода и динамического программирования заключается в том, что оптимизатор вначале перебирает все возможные операции над парами таблиц базы данных. Оптимальная комбинация запоминается, после чего оптимизатор переходит к перебору комбинаций из трех таблиц, пока снова не найдет оптимальную комбинацию. Запоминая оптимальные комбинации для двух, трех, четырех и более таблиц, оптимизатор постепенно поднимается по дереву запроса снизу вверх, пока не найдет оптимальную комбинацию для самой верхней операции.
Такой подход работает благодаря принципу оптимальности Беллмана: оптимальное дерево состоит из оптимальных поддеревьев. После того как найдена оптимальная комбинация для двух таблиц и начат поиск комбинации для трех, можно рассматривать только те комбинации, которые содержат уже найденную оптимальную комбинацию. И игнорировать остальные, которых будет большинство. Такое «кеширование» промежуточных результатов — это, по сути, знакомая нам по программированию мемоизация. А удачная мемоизация способна ускорить алгоритм на порядки! Мемоизация также используется и в подходе top-down.
Для того чтобы максимально быстро перебирать только подходящие комбинации, мы используем гиперграфовый алгоритм DPhyp (Dynamic programming hypergraph). Это свежая научная разработка, представляющая JOIN'ы в виде гиперграфа. Алгоритм позволяет оптимизировать очень большие запросы и хорошо подходит для работы со вложенными предикатами и JOIN'ами, отличными от INNER JOIN, например с FULL OUTER JOIN. При переборе комбинаций таблиц для JOIN этот алгоритм даже не рассматривает изначально бесперспективные варианты, где входные множества таблиц не связаны друг с другом или между собой условием JOIN.
Нам, разработчикам баз данных, приходится постоянно следить за публикуемыми научными работами и пытаться понять, какие из теоретических выкладок стоят того, чтобы воплотить их в код.
Кардинальность и оценочная функция: как сравнить два JOIN'а
Рассказывая про перебор вариантов, я упомянул, что наш стоимостной оптимизатор ищет оптимальную комбинацию таблиц. Но что такое оптимальная комбинация? Для базы данных это такая комбинация таблиц, операция над которой (например, JOIN) выполнится за минимальное время, при этом промежуточные данные уместятся в оперативную память.
Чтобы предсказать время выполнения или требования к объёму памяти конкретного запроса, нужно оценить количество записей на выходе каждого оператора плана. Этот модуль оптимизатора называется «Оценка кардинальности». Это, наверное, самая важная и сложная часть оптимизатора. Для оценки количества записей после чтения мы собираем статистику по таблицам: сколько в них строк, какие данные и так далее. Но точность оценки начинает падать с добавлением каждого фильтра и JOIN'а. А после 6–7 JOIN'ов ошибка накапливается и может увеличиться на несколько порядков.
YDB автоматически собирает статистику по таблицам и колоночную статистику. Например, если в запросе есть city = Moscow, то оптимизатор сможет примерно оценить, какой объем данных получится после применения такого фильтра (или, как мы говорим, какая «кардинальность» будет у такой операции). Если для запроса нужна точная статистика, то перед выполнением запроса аналитик может форсировать ее сбор с помощью команды ANALYZE.
Кроме статистики мы также используем знания о схеме базы данных. Очень часто в аналитических запросах используются JOIN'ы по первичному ключу. Например, при соединении таблицы фактов с таблицей измерений JOIN производится по первичному ключу таблицы измерений. Оптимизатор сразу понимает, что кардинальность такого JOIN'а не превысит кардинальность таблицы фактов.
Зная кардинальность операции над таблицами, оптимизатор может рассчитать ее «стоимость» с помощью оценочной функции. Эта функция учитывает не только статистику по таблицам и тип операции, но и используемые алгоритмы. Например, выполняя JOIN на кластере серверов, можно по-разному распределять данные, и от этого будет зависеть итоговая оценка.
При этом точность оценочной функции не очень важна. Главное, чтобы стоимость плохого плана была выше, чем стоимость хорошего. Мы сделали оценочную функцию за неделю, подобрав параметры линейной регрессией по результатам наших бенчмарков.
Сколько JOIN'ов выдерживает оптимизатор
Динамическое программирование дает нам возможность «кешировать» результаты сравнений и просто игнорировать большую часть комбинаций при переборе. А гиперграфовый алгоритм позволяет дополнительно не учитывать заведомо нерабочие комбинации. Но, несмотря на все это, время выполнения NP-полной задачи в нетривиальных случаях растет экспоненциально.
Экспериментальным путем мы определили максимальное время работы нашего оптимизатора, равное примерно одной секунде. Если за этот интервал не удалось составить план запроса, то, скорее всего, его и не получится составить за разумное время. Что мы можем сделать за секунду? Для простой топологии вроде «цепочки» можно перебрать до 150 (!!!) JOIN'ов. Это намного больше, чем 10 JOIN'ов для top-down-оптимизаторов. Для «снежинки» результаты скромнее: порядка 30 JOIN'ов. Любимая аналитиками «звезда» снижает возможности до 18 JOIN'ов, а с полностью связанным графом «клика» оптимизатор сможет справиться с 14–15 JOIN'ами.
Некоторые разработчики пробуют использовать ML в надежде подобрать что-нибудь адекватное для запросов, план которых не удалось посчитать за разумное время. Но такой подход имеет риски: время выполнения запроса становится непредсказуемым. Кому понравится, что тяжелый аналитический запрос, который обычно выполняется за несколько часов ночью, вдруг занял полтора дня, попутно «положив» всю транзакционную нагрузку?
Хабр — для широкой аудитории, поэтому я постарался не перегружать статью терминологией и деталями работы оптимизатора. Но готов подробнее раскрыть тему в комментариях. Если вы давно хотели спросить что-то про работу баз данных, но не было возможности, то самое время воспользоваться таким случаем. А еще недавно я выступил на вебинаре, где рассказал про стоимостной оптимизатор. Для тех, кому комфортнее слушать рассказ или смотреть видео, оставляю запись вебинара.
