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

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

¶История

¶Ранние СУБД и ручная оптимизация

В первых реляционных СУБД (1970-е — начало 1980-х годов) оптимизация запросов выполнялась вручную. Программист или администратор базы данных должен был явно указывать, какие индексы использовать, в каком порядке соединять таблицы и какие методы доступа применять. Это требовало глубокого понимания внутреннего устройства СУБД и структуры данных.

¶Появление автоматических оптимайзеров

В 1980-х годах, с ростом сложности запросов и объёмов данных, возникла необходимость автоматизации процесса. Первые автоматические оптимайзеры появились в коммерческих СУБД, таких как IBM DB2 (1983), Oracle (1979/1986) и Ingres (1980-е). Они использовали простые эвристики и правила, например, «выполнять соединения в порядке, указанном в запросе» или «использовать индексы, если они существуют».

¶Развитие стоимостных моделей

В 1990-х годах оптимайзеры перешли к стоимостным моделям. Вместо фиксированных правил они начали оценивать стоимость каждого возможного плана выполнения в условных единицах (обычно — количество операций ввода-вывода, время процессора). Для этого СУБД хранит статистику о таблицах (количество строк, распределение значений, размер данных) и использует алгоритмы для оценки селективности предикатов. Первопроходцем в этой области стала СУБД Microsoft SQL Server (версия 6.5, 1996 год).

¶Современные оптимайзеры

Современные оптимайзеры (PostgreSQL, MySQL, Oracle, SQL Server) используют сложные алгоритмы, учитывающие множество факторов: стоимость операций ввода-вывода, загрузку процессора, параллелизм, кэширование, а также динамические свойства данных. Они также поддерживают оптимизацию на основе правил (rule-based) и на основе стоимости (cost-based). В последние годы активно развиваются методы машинного обучения для автоматического подбора планов выполнения.

¶Принцип работы

¶Входные данные

Оптимайзер получает на вход:

Текст SQL-запроса (например, SELECT * FROM users WHERE age > 30).
Статистику базы данных — метаданные о таблицах (количество строк, гистограммы распределения значений, размеры страниц, наличие и типы индексов, фрагментация данных).
Параметры конфигурации СУБД — доступные ресурсы (количество ядер процессора, объём оперативной памяти, настройки кэша).

¶Этапы оптимизации

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

Лексический и синтаксический анализ — проверка корректности запроса и построение абстрактного синтаксического дерева (AST).
Логическая оптимизация — преобразование запроса в эквивалентную, но более эффективную логическую форму. Примеры: переписывание вложенных запросов в соединения, упрощение условий, проталкивание фильтров (predicate pushdown), устранение избыточных операций.
Физическая оптимизация — генерация и оценка множества альтернативных планов выполнения. Для каждого логического шага (например, соединение таблиц) выбирается физический оператор (например, вложенный цикл, хэш-соединение, сортировка слиянием). Оптимайзер перебирает комбинации этих операторов и оценивает стоимость каждой.
Выбор плана — из всех сгенерированных планов выбирается тот, у которого минимальная оценочная стоимость. Этот план передаётся исполнителю запросов.

¶Методы оценки стоимости

Оценка стоимости плана основывается на:

Селективность предикатов — доля строк, удовлетворяющих условию. Оценивается по статистике (гистограммы).
Размер таблиц и индексов — количество страниц данных.
Стоимость операций ввода-вывода — чтение страниц с диска или из кэша.
Стоимость операций процессора — сортировка, хэширование, проверка условий.
Стоимость передачи данных — при распределённых запросах.

¶Классификация

¶По методу принятия решений

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

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

Статические (compile-time) оптимайзеры — строят план один раз при первом выполнении запроса и кэшируют его. Не учитывают изменения данных во время выполнения.
Динамические (runtime) оптимайзеры — могут корректировать план во время выполнения запроса, адаптируясь к реальным условиям (например, к нехватке памяти или изменению селективности). Применяются в некоторых специализированных СУБД.

¶По типу СУБД

Реляционные СУБД (PostgreSQL, MySQL, Oracle, SQL Server) — оптимизируют SQL-запросы.
NoSQL-системы (MongoDB, Cassandra) — имеют свои оптимизаторы, но они работают с другими моделями данных (документная, колоночная, графовая).
Графовые СУБД (Neo4j) — оптимизируют обходы графов.

¶Примеры в популярных СУБД

¶PostgreSQL

PostgreSQL использует стоимостный оптимайзер. Он поддерживает:

Различные методы соединения: вложенный цикл (nested loop), хэш-соединение (hash join), сортировка слиянием (merge join).
Планирование на основе статистики: гистограммы, частоты значений, количество NULL.
Параллельное выполнение: оптимайзер может разбить план на части, выполняемые на нескольких ядрах.
Расширяемость: можно добавлять пользовательские типы данных и операторы с определением стоимости.

¶MySQL

MySQL (с движком InnoDB) использует стоимостный оптимайзер. Особенности:

Выбор индексов: оптимайзер оценивает, какой индекс (или их комбинация) будет наиболее эффективным.
Оптимизация соединений: использует алгоритм «вложенный цикл» для соединений, но может применять хэш-соединение (начиная с версии 8.0.18).
Ограничения: не всегда точно оценивает селективность для сложных предикатов.

¶Oracle

Oracle Database имеет один из самых продвинутых оптимайзеров. Особенности:

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

¶Microsoft SQL Server

SQL Server использует стоимостный оптимайзер. Особенности:

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

¶Значение и критика

¶Значение

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

¶Критика

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

¶Интересные факты

Первый автоматический оптимайзер запросов был реализован в системе System R (IBM, 1979 год). Он использовал стоимостную модель, основанную на статистике.
В некоторых СУБД (например, в Oracle) существует возможность «заморозить» план выполнения для конкретного запроса, чтобы избежать нежелательных изменений при обновлении статистики.
Оптимайзеры запросов являются объектом активных исследований в области баз данных. Современные работы посвящены использованию методов машинного обучения (например, глубокого обучения с подкреплением) для автоматического поиска оптимальных планов.

¶Источники

Ramakrishnan, R., Gehrke, J. (2003). Database Management Systems (3rd ed.). McGraw-Hill. — Главы 12–14, посвящённые оптимизации запросов.
Elmasri, R., Navathe, S. B. (2016). Fundamentals of Database Systems (7th ed.). Pearson. — Глава 19: Query Processing and Optimization.
Документация PostgreSQL: Chapter 14. Performance Tips. Раздел «Using EXPLAIN».
Документация MySQL: Chapter 8. Optimization. Раздел «Optimizing SQL Statements».
Документация Oracle Database: Oracle Database SQL Tuning Guide. Раздел «Query Optimizer».
Документация Microsoft SQL Server: Query Processing Architecture Guide. Раздел «Query Optimizer».

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

На главную BFOmetr →