Корпоративные базы данных - статьи

       

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



Оптимизация выполнения 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 PPXWEIGHT
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 выбирает план выполнения запроса на основе
вычисления затрат на выполнение целого ряда операций, которые помимо простого
использования процессора и подсистемы ввода/вывода включают следующие факторы:

Операции сравнения


  • Перемещение данных
  • Повторный доступ к той же таблице
  • Методы объединения данных
  • Использование буферов ввода/вывода
  • Распределение предикатов

Учет всех вышеприведенных факторов делает реальные формулы оптимизатора весьма сложными
и не позволяет привести их в рамках данной статьи.


Содержание раздела