Оптимизация и выбор плана выполнения запроса
Оптимизация выполнения SQL запросов и модули поддержки подобной оптимизации
(оптимизаторы или optimizers) играют крайне важную роль в реляционных СУБД. SQL запросы
определяют какие данные необходимо передать пользователю, но не говорят РСУБД о том, как
этот запрос обработать эффективно. Обычно существует большое количество возможностей
выполнения запроса. Оптимизаторы серверов баз данных отвечают за выбор наилучшей стратегии
выполнения. Поэтому скорость выполнения запросов в ведущей степени зависит от качества
оптимизатора данной РСУБД.
Результатом работы оптимизатора SQLBase является план выполнения запроса (execution plan).
Говоря упрощенно, execution plan - это последовательность шагов, которая указывает программе
серверу SQLBase, как выполнить запрос. В плане каждый шаг может быть однотабличным (single
table) или двухтабличным (two table). Все шаги производят результирующие таблицы (result tables).
Результирующая таблица не обязательно должна иметь материальное воплощение в виде
физического объекта. Для любого шага плана результирующая таблица может быть
пользовательской (user-defined), временной (temporary) или концептуальной (conceptual).
Однотабличный шаг плана
Однотабличный шаг плана выполнения запроса определяет исходную таблицу, метод доступа к
данным, используемый для извлечения строк таблицы, и имя результирующей таблицы (чаще
всего, концептуальной). В настоящее время SQLBase поддерживает следующие методы доступа к
данным:
- Последовательное сканирование (Sequential Scan) - Это наиболее простой
из всех методов доступа. В этом считывается методе каждая страница данных,
принадлежащая исходной таблице. (Следует отметить, что все страницы базы
данных для данной таблицы связаны между собой, поэтому не требуется
сканирование всего файла базы данных).
- Доступ по индексу (Index Access) - Существуют два способа использования
индекса. При первом, значение индекса известно, и индекс может быть
использован для позиционирования на индексной странице БД и последующего
извлечения данных непосредственно из индексной страницы. При втором
способе индексные страницы сканируются в возрастающем или убывающем
порядке для поиска положения индекса. Если запрос включает колонки
таблицы, не входящие в индекс, потребуются дополнительные операции для
считывания информации из страниц данных таблицы.
- Хэшированный доступ (Hash Access) - В этом методе ключевое значение
используется для прямого извлечения информации из страницы данных,
которая содержит строки, удовлетворяющие значению ключа. Метод
преобразования ключа в адрес страницы, на которой он находится, носит
название "хэширование". Хэшированный доступ может быть использован
только в том случае, если для ключа создан хэшированный индекс и
предикатом является равенство "=".
Двухтабличный шаг плана
Двухтабличный шаг плана выполнения запроса определяет все исходные таблицы, метод доступа к
данным, используемый для извлечения строк из этих таблиц, метод объединения строк данных и
имя результирующей таблицы. Одна из исходных таблиц называется внешней, а другая -
внутренней. SQLBase поддерживает следующие методы объединения данных:
- Вложенный цикл (Nested loop) и его вариации
- Слияние индексов (Index merge)
- Гибридное хэшированное объединение (Hybrid hashed join)
Пример схемы выполнения
В качестве примера рассмотрим базу данных типа поставщик-товар-поставка. База содержит 3
таблицы: S для поставщика, P для товара и SP - для поставок. Таблица S имеет уникальный
первичный ключ S#. Таблица P имеет уникальный первичный ключ P#. Таблица SP имеет
уникальный первичный ключ на колонках S#P#. Дополнительно, эта таблица содержит индексы
для колонок City, Color и Weight. Схема базы приведена на рис.5.
Рис. 5. Схема демонстрационной базы данных
| S | S#, SName, Status, City | SXS#(S#), SXCITY(City) |
| P | P#, PName, Color, Weight, City | PXP#(P#), PXCOLOR(Color), PXWEIGHT(Weight) |
| SP | S#, P#, QTY | SPXS#P#(S#, P#) |
Запрос 1: Select * from P where color = 'Red' and weight =19;
План выполнения
| 1 | P | PXWEIGHT | RESULT |
Для выполнения данного запроса у оптимизатора есть три варианта: 1) последовательное
сканирование, 2) индексный доступ с помощью индекса PXCOLOR и 3) индексный доступ с
помощью индекса PXWEIGHT. В данном случае, оптимизатор выбрал индекс PXWEIGHT.
Поэтому программа сервера будет использовать ключ weight (значение 19) для извлечения всех
строк, которые удовлетворяют условию "weight =19" и отфильтровывать те из них которые не
удовлетворяют второму условию (color = 'Red'). Оптимизатор предпочел индекс PXWEIGHT
индексу PXCOLOR, поскольку он посчитал, что в таблице существует меньше строк,
удовлетворяющих критерию выбора по ключу weight. Иными словами, индекс PXCOLOR является
более "плохим" и потребует больше операций ввода/вывода и команд процессора для выполнения
запроса. Результат запроса представляется в виде концептуальной таблицы RESULT.
Стоимостная модель оптимизации
Оптимизатор SQLBase использует так называемый стоимостной метод (cost-based technique) для
определения наилучшего плана выполнения запроса, в отличие от методов, основанных на анализе
синтаксиса (syntax-based) запроса или жестко установленных правилах выбора (rule-based).
Оптимизатор оценивает стоимость или затраты на работу процессора и операции ввода/вывода для
различных методов доступа к данным и операций над ними. Стоимость процессора оценивается в
миллисекундах. Стоимость ввода/вывода, которая представляет собой количество операций
ввода/вывода в секунду, также преобразуется в миллисекунды. Такой подход позволяет проводить
сравнение нагрузки на процессор и подсистему ввода/вывода. Производительность методов
доступа к данным и операций объединения зависит от размера и распределения данных.
Информация о данных представлена в виде статистики таблиц и индексов. Запрос разбивается на
ряд небольших индивидуальных шагов.
Наименьший шаг - это доступ к данным одной таблицы,
который выбирается из всех возможным методов доступа. При этом исследуются все возможности
выбора данных из таблицы, а также методы объединения между любыми двумя таблицами или
таблицей и промежуточным результатом. Оптимизатор выбирает наиболее простой и
эффективный план выполнения.
В реальной обстановке оптимизатор SQLBase выбирает план выполнения запроса на основе
вычисления затрат на выполнение целого ряда операций, которые помимо простого
использования процессора и подсистемы ввода/вывода включают следующие факторы:
Операции сравнения
- Перемещение данных
- Повторный доступ к той же таблице
- Методы объединения данных
- Использование буферов ввода/вывода
- Распределение предикатов
Учет всех вышеприведенных факторов делает реальные формулы оптимизатора весьма сложными
и не позволяет привести их в рамках данной статьи.
