Привет, Хабр!

Думаю, каждый хоть раз использовал команду explain или хотя бы слышал про нее. Эта команда демонстрирует план выполнения запроса, но как именно СУБД приходит к нему остается загадкой. Да и как вообще СУБД понимает, что выбранный запрос оптимален? Неужели она проверяет все возможные варианты?
В этой статье я постараюсь дать небольшое представление о том, как работают оптимизаторы запросов с теоретической точки зрения.

Начнем с того, что можно выделить два основных подхода к поиску наиболее эффективного варианта выполнения: эвристический и стоимостной.

Эвристический подход

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

• Выборка и проекции должны быть выполнены как можно раньше в дереве запроса

• При объединении таблиц необходимо в первую очередь выполнять наиболее строгие операции объединения

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

Стоимостной подход

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

Первое, что делает при таком подходе оптимизатор - строит дерево запроса. Разберемся, что это такое.

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

К каждому такому дереву можно применить трансформацию — логическую или физическую. Логические трансформации порождают новые деревья посредством изменения структуры исходных, а физические заменяют логические операторы на их конкретные реализации, называемые физическими операторами, не меняя структуру дерева. Так, например, логический оператор JOIN можно заменить на физические LOOP JOIN или MERGE JOIN.

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

Разобравшись с тем, что такое дерево поиска, введем ещё два определения: логическая эквивалентность и область поиска.

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

Областью поиска называется множество всевозможных логически эквивалентных деревьев запроса. Исходной областью поиска является логическое дерево, полученное в результате парсинга искомого запроса. При замене каждого из узлов дерева на его логические эквиваленты область поиска расширяется. Конечной областью поиска будет таким образом являться множество всех эквивалентных искомому запросу деревьев поиска. А точнее, одно дерево, каждый из узлов которого будет являться полной эквивалентной группой аналогичного узла в первоначальном дереве. Согласен, звучит сложно, но теория — она такая.

Итак, с определениями разобрались, теперь перейдём непосредственно к оценке стоимости плана. Она состоит из трех этапов: оценки кардинальности, применения стоимостной модели и перечисления планов. Рассмотрим каждый в отдельности.

Этап 1. Оценка кардинальности

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

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

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

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

Саму оценку кардинальности проводят в таком случае при помощи другого свойства запросов — селективности. Селективностью называется отношение количества строк, возвращаемых запросом, к общему количеству строк в таблице. То есть, если в таблице user содержатся записи о 100 людях, 25 из которых младше 50, а 75 старше, то селективность запроса SELECT * FROM user WHERE age > 50 будет равняться 75/100=0.75

Вернёмся к оценке кардинальности. Предположим, что таблица user имеет 1000 записей, и согласно гистограмме распределения количество пользователей с параметром age=20 равняется 100, а количество пользователей с параметром sex=“male“ равняется 500.

Тогда запрос SELECT * FROM user WHERE age=20 AND sex='male' будет оценен следующим образом: age=20 даст селективность 100/1000=0.1, а sex='male' соответственно 500/1000=0.5. Итоговая селективность составит 0.1*0.5=0.05. Кардинальность данного запроса в таком случае может быть оценена как 1000*0.05=50 записей.

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

Этап 2. Применение стоимостной модели

Стоимостная модель задает отображение полученного дерева плана на некоторое число, которое будет обозначать его итоговую стоимость.
В свою очередь стоимостью плана называется сумма стоимостей всех входящих в него операторов. Стоимость оператора же может зависеть от множества факторов. Часть из них определена заранее и зависит, к примеру, от оборудования, на котором развернута СУБД. А часть может вычисляться динамически — например, оценка кардинальности оператора, наполненность буферов или наличие свободных потоков для параллельного выполнения.

Этап 3. Перечисление планов

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

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

Первый подход: снизу вверх

Первым алгоритмом, который мы рассмотрим, является прохождение по дереву снизу вверх при помощи динамического программирования. Здесь для вычисления оптимального плана на i-м уровне дерева вычисляются все планы на i-1-м уровне дерева, и из них выбирается наилучший. Очевидно, что при таком подходе выбор оптимального плана выродится в полный перебор всех вариантов, поэтому для использования на практике его нужно модифицировать. Так П.Г.Сэлинджер предложила рассматривать только левосторонние деревья, у которых при этом элементы на левой ветви имеют минимальную оценку кардинальности.

Примерно такие:

Чтобы понять, почему это работает, рассмотрим пример. Предположим, что у нас есть три таблицы B, C и D. Пусть A — таблица, полученная в результате соединения таблиц C и D.

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

Попробуем сначала выполнить соединение A с B, а потом B с A. В первом случае процесс соединения можно описать следующим псевдокодом:

for a in A:
 if (contains(B, a)):
 return a x b

Если предположить, что метод contains для поиска искомого кортежа по очереди проверит каждую запись в таблице B, то приведенная операция очевидно будет иметь квадратичную сложность. Но поскольку B постоянно присутствует в базе данных, для нее можно построить индекс, что позволит быстрее выполнить поиск, и асимптотическая сложность задачи понизится.

Во втором случае процесс можно представить следующим (очень отличающимся) псевдокодом:

 for b in B:
 if (contains(A, b)):
 return b x a

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

Второй подход: сверху вниз

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

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

P.S. Любая критика и исправления только приветствуются :)