Оптимизация запросов в реляционных базах данных

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

Реляционная алгебра

Алгеброй называется множество с набором операций. Операции, которые используются в запросах реляционных баз данных, определяют реляционную алгебру. На этом понятии основывается обработка запросов, поэтому разберемся подробнее, что в него входит. Реляционная алгебра содержит восемь операций над отношениями (неформально – таблицами):

• Выборка. WHERE p
• Проекция. SELECT x, y, z FROM a
• Декартово произведение. a CROSS JOIN b
• Соединение. a JOIN b. Операция добавлена в алгебру для удобства использования. Она избыточна, так как выражается через декартово произведение и выборку: (a CROSS JOIN b) WHERE p
• Объединение. a UNION b
• Пересечение. a INTERSECT b
• Вычитание. a EXCEPT b
• Деление. В промышленных СУБД не используется.

Синтаксис операций взят из Transact-SQL.

Эквивалентные выражения

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

• a WHERE (p OR q) <=> (a WHERE p) UNION (a WHERE q)
• a WHERE (p or not q) <=> (a WHERE p) EXCEPT (a WHERE q)
• (a CROSS JOIN b) WHERE p(a) <=> (a WHERE p(a)) CROSS JOIN b
• Ассоциативность, дистрибутивность, коммутативность теоретико-множественных операций.

Обработка запроса

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

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

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

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

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

Алгоритмы доступа к данным

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

• Полное сканирование таблицы. Самый простой алгоритм. Он не требует наличия индекса и каких-либо условий на атрибуты выборки. Каждая запись таблицы проверяется на условия оператора селекции. Сложность алгоритма линейно зависит от количества блоков памяти, занятых таблицей. В большинстве случаев работает медленнее других методов доступа к данным.
• Полное сканирование индекса. Если на атрибуте выборки построен индекс, нужно искать по нему. При полном сканировании для каждого ключа индекса извлекается блок памяти с диска. Получаем сложность, линейно зависящую от количества уникальных значений атрибута.
• Просмотр диапазона по индексу. Если в условиях выборки есть сравнения, то используется этот алгоритм. Так как индексы обычно представляют собой B*-деревья, найти нужный диапазон значений из условия выборки можно за логарифмическое время. После того, как лист найден, поочередно добавляем записи в результат. Почитать про B-деревья можно в википедии.

Алгоритмы соединения

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

• Вложенные циклы. Самый интуитивно понятный алгоритм. Внешний цикл обходит записи одной таблицы, внутренний — другой. Пары строк, удовлетворяющие условию соединения, добавляются к результату. Хоть этот алгоритм и самый медленный, он незаменим. На него не накладываются никакие ограничения, поэтому любое соединение может быть реализовано с его помощью.
• Merge-Sort Join. Отсортированные по нужному атрибуту таблицы — главное условие использования этого алгоритма. Суть метода проще всего понять, если посмотреть на пример ниже. Соединение слиянием выполняется всего за один проход по каждой из таблиц, чем выгодно отличается от предыдущего алгоритма. Тем не менее, оно имеет достаточно сильное ограничение и применимо далеко не всегда.
• Hash Join. Значения меньшей из таблиц помещается в хеш-таблицу. По другой таблице производится поиск. Главное ограничение такого подхода в том, что условие соединения должно быть равенством. На небольших размерах одной из таблиц алгоритм работает быстрее других, но есть минус: результат начнет формироваться только после окончания обработки первой таблицы. Поэтому, если нужна только первая строка результата, алгоритм вложенных циклов отработает быстрее.

Оптимизатор запросов

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

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

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

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

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

1. Найти оптимальный план для каждого отдельного отношения. Использовать для этого алгоритмы доступа к данным.
2. Для каждого под-плана длины k найти оптимальный план длины k+1, присоединив одно из оставшихся отношений.
3. Повторять, пока все отношения не будут присоединены.

Заключение

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

Written on January 7th, 2018 by Alexey Kalina