Планировщик запросов¶

Планировщик запросов (англ. query planner, query optimizer) — это компонент системы управления базами данных (СУБД), отвечающий за преобразование высокоуровневого запроса, написанного на языке структурированных запросов (SQL), в последовательность низкоуровневых операций, обеспечивающую наиболее эффективное выполнение этого запроса. Планировщик выбирает оптимальный план выполнения из множества возможных альтернатив, руководствуясь статистическими данными о данных, хранящихся в базе, и доступных вычислительных ресурсах.

¶Функции и задачи

Основная задача планировщика — минимизировать стоимость выполнения запроса, которая измеряется в таких единицах, как время выполнения, количество операций ввода-вывода (I/O), загрузка центрального процессора (CPU) и использование памяти. Планировщик решает, в каком порядке соединять таблицы, какие индексы использовать, какие алгоритмы сортировки и агрегации применять, а также как распараллеливать выполнение операций.

Ключевые функции планировщика включают:

Анализ запроса: Разбор синтаксиса SQL-запроса, проверка прав доступа и построение внутреннего представления (например, дерева разбора).
Генерация альтернативных планов: Создание нескольких вариантов планов выполнения, отличающихся порядком соединений, методами доступа к данным (сканирование таблицы, сканирование индекса) и алгоритмами обработки.
Оценка стоимости: Для каждого сгенерированного плана вычисляется его предполагаемая стоимость на основе статистики (количество строк, распределение значений, размер таблиц) и метрик производительности системы.
Выбор оптимального плана: Из всех доступных планов выбирается тот, который имеет наименьшую оценку стоимости.
Выдача плана выполнения: Сформированный план передаётся исполнителю запросов (executor), который выполняет его шаг за шагом.

¶Этапы планирования

Процесс планирования запроса обычно проходит несколько этапов:

¶Логическая оптимизация

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

Проекция и селекция: Перенос операций фильтрации (WHERE) и выбора столбцов (SELECT) как можно ближе к источникам данных, чтобы уменьшить объём обрабатываемых данных.
Перестановка соединений: Изменение порядка соединений таблиц для минимизации промежуточных результатов.
Упрощение условий: Удаление избыточных или тождественно истинных/ложных условий.
Преобразование подзапросов: Замена вложенных запросов на эквивалентные соединения (JOIN) или агрегации, если это возможно.

¶Физическая оптимизация

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

Методы доступа: Выбор между полным сканированием таблицы (sequential scan) и сканированием по индексу (index scan, bitmap scan).
Алгоритмы соединения: Выбор между вложенными циклами (Nested Loop Join), хеш-соединением (Hash Join) и сортировкой-слиянием (Merge Join).
Алгоритмы сортировки: Выбор подходящего алгоритма сортировки (например, быстрая сортировка, внешняя сортировка) в зависимости от объёма данных.
Стратегии агрегации: Выбор между хеш-агрегацией и сортировкой-агрегацией.

¶Классификация планировщиков

Планировщики запросов можно классифицировать по нескольким признакам:

¶По типу оптимизации

Правил-ориентированные (rule-based): Используют фиксированный набор эвристических правил для выбора плана. Например, правило «всегда использовать индекс, если он доступен». Такие планировщики просты и предсказуемы, но не учитывают реальное распределение данных.
Стоимостно-ориентированные (cost-based): Оценивают стоимость каждого плана на основе статистики и выбирают план с наименьшей стоимостью. Это наиболее распространённый тип в современных СУБД (PostgreSQL, Oracle, MySQL, Microsoft SQL Server).

¶По способу генерации планов

Последовательные (iterative): Генерируют и оценивают планы один за другим, постепенно улучшая результат.
Генетические (genetic): Используют эволюционные алгоритмы для поиска оптимального плана, особенно эффективны для запросов с большим количеством соединений (более 10-12 таблиц).
Динамическое программирование: Разбивают задачу на подзадачи, находят оптимальные решения для каждой подзадачи и комбинируют их. Этот метод даёт точные результаты, но требует больших вычислительных затрат.

¶По времени выполнения

Статические (static): План строится до выполнения запроса и не изменяется в процессе. Это характерно для компилируемых запросов (например, в хранимых процедурах).
Динамические (dynamic): План может корректироваться в процессе выполнения на основе промежуточных результатов. Это позволяет адаптироваться к изменениям в данных, но увеличивает накладные расходы.

¶Пример работы планировщика

Рассмотрим простой запрос:

``sql SELECT * FROM users WHERE age > 30; ``

Планировщик может рассмотреть два основных плана:

Полное сканирование таблицы: Считать все строки из таблицы users, проверить условие age > 30 для каждой строки и вернуть подходящие.
Сканирование по индексу: Если на столбце age есть индекс, планировщик может использовать его для быстрого поиска строк, удовлетворяющих условию. Затем для каждой найденной строки выполняется чтение из таблицы.

Планировщик оценит стоимость обоих планов, используя статистику (например, количество строк в таблице, селективность условия). Если в таблице 1000 строк, а условию удовлетворяют 900, полное сканирование может быть эффективнее. Если же условию удовлетворяют только 10 строк, сканирование по индексу будет значительно быстрее.

¶Влияние на производительность

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

Сбор статистики: Регулярное обновление статистики о распределении данных (команды ANALYZE в PostgreSQL, UPDATE STATISTICS в SQL Server).
Создание индексов: Правильно спроектированные индексы дают планировщику больше вариантов для выбора.
Настройка параметров: Изменение конфигурационных параметров, влияющих на оценку стоимости (например, стоимость ввода-вывода, стоимость процессора).
Подсказки (hints): В некоторых СУБД (Oracle, MySQL) разработчик может явно указать планировщику, какой план использовать, если автоматический выбор неудовлетворителен.

¶Планировщики в популярных СУБД

PostgreSQL: Использует стоимостно-ориентированный планировщик с поддержкой динамического программирования и генетических алгоритмов для сложных запросов. Известен своей детальной статистикой и гибкостью.
MySQL: В версиях до 5.7 использовал преимущественно правил-ориентированный подход. Начиная с версии 8.0, активно внедряет стоимостно-ориентированную оптимизацию. Планировщик MySQL также известен использованием вложенных циклов для соединений.
Oracle Database: Использует мощный стоимостно-ориентированный планировщик с поддержкой множества методов доступа, включая битовые карты (bitmap indexes), кластерные индексы и материализованные представления. Широко применяет подсказки (hints) для тонкой настройки.
Microsoft SQL Server: Использует стоимостно-ориентированный планировщик, который анализирует запросы и генерирует планы, хранящиеся в кэше планов. Поддерживает различные алгоритмы соединений и методы доступа.

¶Критика и ограничения

Несмотря на свою важность, планировщики запросов имеют ограничения:

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

¶Источники

Гарсиа-Молина, Г., Ульман, Дж., Уидом, Дж. «Системы баз данных. Полный курс». — М.: Вильямс, 2003.
Дейт, К. Дж. «Введение в системы баз данных». — М.: Вильямс, 2005.
Сайт документации PostgreSQL: «Chapter 14. Performance Tips», раздел «Using EXPLAIN».
Сайт документации MySQL: «Optimization Overview».
Сайт документации Oracle Database: «Query Optimizer Concepts».
Сайт документации Microsoft SQL Server: «Query Processing Architecture Guide».

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →