Этапы оптимизации запросов в реляционных СУБД

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

Пример 7.1. Список сотрудников 4-го отдела не старше 25 лет с «чистой» зар-платой не менее 30000 рублей" («чистой» называется зарплата после уплаты подоходного налога, в настоящее время – 13%).

SELECT *FROM EmpWHERE depNo=4 AND born>'1985/01/01'AND salary*0.87>=30000;

В этом запросе к таблице Emp (Сотрудники) указаны условия на поля depNo (Номер отдела), born (Дата рождения) и salary (Зарплата). Если по этим полям есть индексы, то способы выполнения этого запроса могут быть такими:

1. Найти по индексу INDEX(depNo) записи, удовлетворяющие первому условию, и проверить для найденных записей второе условие.
2. Найти по индексу INDEX(born) записи, удовлетворяющие второму усло-вию, и проверить для найденных записей первое условие.
3. Последовательно считать все записи таблицы Emp и проверить для каждой записи оба условия.

Индексом по полю salary система воспользоваться не может, т.к. это поле находится внутри выражения.

Цель СУБД – выполнить запрос, причём сделать это как можно более эффективным способом. Итак, под оптимизациейпонимается построение квазиоптимального процедурного плана выполнения декларативного запроса.

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

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

Обработка запроса, поступившего в РСУБД и представленного на декларативном языке запросов, состоит из этапов (фаз), представленных на рис. 7.1.

Рис. 7.1. Последовательность выполнения запросов в реляционных СУБД

На первой фазе запрос, представленный на языке запросов, подвер-гается лексическому и синтаксическому анализу. Лексический анализатор разбивает запрос на лексические единицы – лексемы (наименования полей и таблиц, константы, знаки операций и т.д.). Синтаксический анализатор проверяет синтаксическую правильность запроса. В результате вырабатывается внутреннее представление запроса. Оно отражает структуру запроса и содержит информацию, которая характеризует объекты базы данных, упомянутые в запросе (таблицы, поля, константы). Информация об объектах базы данных выбирается из словаря-справочника данных. Внутреннее представление запроса используется и преобразуется на следующих стадиях обработки запроса.

На второй фазе запрос в своём внутреннем представлении подвергается логической оптимизации. При этом могут применяться различные преобразования, "улучшающие" начальное представление запроса. Среди этих преобразований могут быть эквивалентные преобразования (см. раздел 7.2). После проведения эквивалентных преобразований получается внутреннее представление, семантически эквивалентное начальному запросу.

Преобразования могут также использовать информацию об ограни-чениях целостности, существующих в БД. Такие преобразования являются семантическими, т.е. они основаны на семантике (смысле) предметной области. В этом случае получаемое представление не является семантически эквивалентным начальному запросу. Но система гарантирует, что результат выполнения преобразованного запроса совпадает с результатом запроса в начальной форме при соблюдении ограничений целостности, существующих в базе данных. Например, если для таблицы Emp определено такое ограничение целостности:

(CHECK (salary>9500 AND salary<80000),

то система к запросу из примера 7.1 могла бы добавить эти условия в часть WHERE, чтобы иметь возможность использовать индекс по полю salary.

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

Третий этап обработки запроса состоит в выборе альтернативных процедурных планов выполнения данного запроса в соответствии с его внутренним представлением, полученным на второй фазе. Для этого оптимизатор использует информацию из словаря-справочника данных, в первую очередь, о существующих путях доступа к данным. Единственный путь доступа, который возможен в любом случае, – это последовательное чтение (FULL). Возможность использования других путей доступа зависит от способов размещения данных в памяти (например, кластеризация или хеширование данных), от наличия индексов и формулировки самого за-проса.

Также на третьем этапе для каждого из выбранных планов оценивается предполагаемая стоимость выполнения запроса по этому плану. При оценках используется либо доступная оптимизатору статистическая информация о распределении данных, либо информация о механизмах реализации путей доступа. Из альтернативных планов выбирается наиболее оптимальный с точки зрения некоторого (заранее выбранного или заданного) критерия.

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

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

9.2 Преобразования операций реляционной алгебры

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

В качестве примера приведём отношения R1 и R2, содержащие по 1000 кортежей, причём только 10 кортежей в каждом отношении удовлетворяют условию F. Если выполнять следующую последовательность операций:

s_F(R1 U R2),

то после выполнения объединения получится 2000 кортежей (если отношения не содержат одинаковых кортежей), а после селекции останется 20 записей. Если изменить последовательность выполнения операций:

s_F(R1)U s_F(R2)

то после селекции останется по 10 записей из каждого отношения, объеди-нение которых даст 20 требуемых кортежей. Если учитывать, что объединение выполняется путем сортировки данных (для удаления одинаковых кортежей) и промежуточный результат надо хранить, то выигрыш и по объёму памяти, и по времени очевиден: гораздо быстрее отсортировать 20 кортежей, а не 2000.

Оптимизация выполнения запросов реляционной алгебры основана на понятии эквивалентности реляционных выражений. Операндами выражений являются переменные-отношения R_i и константы. Каждое выражение реляционной алгебры определяет отображение кортежей переменных-отношений R_i (i=1,…,n) в кортежи единственного отношения, которое получается в результате подстановки кортежей каждого R_i и выполнения всех определяемых выражением вычислений.

Два выражения реляционной алгебры считаются эквивалентными, если они описывают одно и то же отображение.

Существуют законы, которые в соответствии с этим определением позволяют выполнять эквивалентные преобразования выражений реляционной алгебры:

1. Закон коммутативности для декартовых произведений:

R1×R2=R2×R1

1. Закон коммутативности для соединений (F – условие соединения):

R1><_FR2= R2><_FR1

1. Закон ассоциативности для декартовых произведений:

(R1×R2)×R3=R1×(R2×R3)

1. Закон ассоциативности для соединений (F1, F2 – условия соединения):

(R1><_F1R2) ><_F2R3= R1><_F1(R2><_F2R3)

1. Комбинация селекций (каскад селекций):

s_F1(s_F2(R))= s_F1vF2(R)

1. Комбинация проекций (каскад проекций):

p_A1,A2,...Am(p_B1,B2,...Bn(R))=p_A1,A2,...Am(R), где {A_m}d{B_n}

1. Перестановка селекции и проекции:

s_Fp_A1,A2,...,Am(R))= p_A1,A2,...,Am(s_F(R))

1. Перестановка селекции с объединением:

s_F(R1UR2)=s_F(R1)Us_F(R2)

1. Перестановка селекции с декартовым произведением:
• s_F(R1×R2)= (s_F1(R1))×(s_F2(R2))

(если F = F1vF2, где F1 содержит атрибуты, присутствующие только в R1, а F2 содержит атрибуты, присутствующие только в R2);

• s_F(R1×R2)=(s_F(R1))×R2

(если F содержит атрибуты, присутствующие только в R1);

• s_F(R1×R2)=R1×(s_F(R2))

(если F содержит атрибуты, присутствующие только в R2);

• s_F(R1×R2)= s_F2(s_F1(R1)×R2)

(если F = F1vF2, где F1 содержит атрибуты, присутствующие только в R1, а F2 содержит атрибуты, присутствующие и в R1, и в R2).

1. Перестановка селекции с разностью:

s_F(R1-R2)=s_F(R1)-s_F(R2)

1. Перестановка проекции с декартовым произведением:

p_A1,A2,...,Am(R1×R2)= (p_B1,B2,...,Bn(R1))×(font face=symbol>p_C1,C2,...,Cr(R2))

где атрибуты {B_n} d{A_m}, {С_r}d{A_m} и атрибуты B₁,B₂,...,B_n представлены в отношении R1, а атрибуты С₁,С₂,...,С_r – в R2.

1. Перестановка селекции с пересечением:

s_F(R1 ∪ R2)=s_F(R1) ∪ s_F(R2)

Методы оптимизации

Существуют два принципиально разных подхода к оптимизации запро-сов. Если оптимизатор основывается только на информации о механизмах реализации путей доступа, то метод оптимизации основан на синтаксисе (на правилах, RULE). Если же помимо этого используется статистическая информация о распределении данных, то это метод оптимизации, основанный на стоимости (на издержках, COST). Рассмотрим эти подходы подробнее.