Методы синтаксической оптимизации запросов

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

К методам, используемым при синтаксической оптимизации запросов, относятся следующие:

· Логические преобразования запросов. Прежде всего это относится к преобразованию предикатов, входящих в условие выборки. Предикаты, содержащие операции сравнения простых значений. Такой предикат имеет вид арифметическое выражение ОС арифметическое выражение, где ОС — операция сравнения, а арифметические выражения левой и правой частей в общем случае содержат имена полей отношений и константы (в языке SQL среди констант могут встречаться и имена переменных объемлющей программы, значения которых становятся известными только'при реальном выполнении запроса).

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

(n+12)*R.B OC 100

здесь n — переменная языка, R.B — имя столбца В отношения R, ОС - допустимая операция сравнения.

Каноническим представлением такого предиката может быть

R.В ОС 100/(n+12)

В этом случае мы один раз для заданного значения переменной п вычисляем выражение в скобках и правую часть операции сравнения 100/(n +12), а потом каждую строку можем сравнивать с полученным значением.

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

предикат соединения; особенно важен случай эквисоединения, когда ОС — это равенство). Если в начальном представлении предикат имеет вид:

12*(Rl.A)-n*(R2.B) ОС m,

то его каноническое представление:

R1.A ОС (m+n*(R2.B)/12

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

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

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

При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду или в процессе нормализации логического условия) и упрощать логическое выражение за счет, например, выявления конъюнкции взаимно противоречащих предикатов.

· Преобразования запросов с изменением порядка реляционных операций. В традиционных оптимизаторах распространены логические преобразования, связанные с изменением порядка выполнения реляционных операций.

Например, имеем следующий запрос:

R1 NATURAL JOIN R2

WHERE R1.A ОС a AND

R2.B С b

Здесь а и b некоторые константы, которые ограничивают значение атрибутов отношений R1 и R2.

Если мы его рассмотрим в терминах реляционной алгебры, то это естественное соединение отношений R1 и R2, в которых заданы внутренние ограничения на кортежи каждого отношения.

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

предикат соединения; особенно важен случай зквисоединения, когда ОС — это равенство). Если в начальном представлении предикат имеет вид:

12*(Rl.A)-n*(R2.B) ОС m,

то его каноническое представление:

R1.A ОС (m+n*(R2.B)/12

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

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

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

При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду или в процессе нормализации логического условия) и упрощать логическое выражение за счет, например, выявления конъюнкции взаимно противоречащих предикатов.

· Преобразования запросов с изменением порядка реляционных операций. В традиционных оптимизаторах распространены логические преобразования, связанные с изменением порядка выполнения реляционных операций.

Например, имеем следующий запрос:

Rl NATURAL JOIN R2 WHERE R1.A ОС a AND R2.B С b

Здесь а и b некоторые константы, которые ограничивают значение атрибутов отношений R1 и R2.

Если мы его рассмотрим в терминах реляционной алгебры, то это естественное соединение отношений R1 и R2, в которых заданы внутренние ограничения на кортежи каждого отношения.

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

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

R3 =.R1[R1.A ОС а] R4 = R2[R2.B С b] R5 = R3*[ ]*R4

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

В частности, существуют подходы, связанные с преобразованием запросов на языке SQL к алгебраической форме. Особенно важно то, что реляционная алгебра более проста, чем язык SQL. Преобразование запроса к алгебраической форме упрощает дальнейшие действия оптимизатора по выборке оптимальных планов. Вообще говоря, развитый оптимизатор запросов системы, ориентированной на SQL, должен выявить все возможные планы выполнения любого запроса, но «пространство поиска» этих планов в общем случае очень велико; в каждом конкретном оптимизаторе используются свои эвристики для сокращения пространства поиска. Некоторые, возможно, наиболее оптимальные планы никогда не будут рассматриваться. Разумное преобразование запроса на SQL к алгебраическому представлению сокращает пространство поиска планов выполнения запроса с гарантией того, что оптимальные планы потеряны не будут.

· Приведение запросов с вложенными подзапросами к запросам с соединениями. Основным отличием языка SQL от языка реляционной алгебры является возможность использовать в логическом условии выборки предикаты, содержащие вложенные подзапросы. Глубина вложенности не ограничивается языком, то есть, вообще говоря, может быть произвольной. Предикаты с вложенными подзапросами при наличии общего синтаксиса могут обладать весьма различной семантикой. Единственным общим для всех возможных се-мантик вложенных подзапросов алгоритмом выполнения запроса является вычисление вложенного подзапроса всякий раз при вычислении значения предиката. Поэтому естественно стремиться к такому преобразованию запроса, содержащего предикаты со вложенными подзапросами, которое сделает семантику подзапроса более явной, предоставив тем самым в дальнейшем оптимизатору возможность выбрать способ выполнения запроса, наиболее точно соответствующий семантике подзапроса.

Каноническим представлением запроса на п отношениях называется запрос, содержащий n-1 предикат соединения и не содержащий предикатов с вложенными подзапросами. Фактически каноническая форма — это алгебраическое представление запроса.

Например, запрос с вложенным подзапросом:

(SELECT Rl.A

FROM Rl

WHERE Rl.B IN

(SELECT R2.B FROM R2 WHERE Rl.C = R2.D)

)

Эквивалентен

(SELECT Rl.A

FROM Rl. R2

WHERE Rl.A = R2.B AND Rl.C = R2.D)

Второй запрос:

(SELECT Rl.A FROM Rl WHERE Rl.K =

(SELECT AVG (R2.B) FROM R2 WHERE Rl.C = R2.D)

Или

(SELECT Rl.A FROM Rl. R3

WHERE Rl.C = R3.D AND Rl.K = R3.L)

R3 = SELECT R2.D, L AVG (R2.B)

FROM R2

GROUP BY R2.D

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

Заметим, что в кратко описанном нами подходе имеются некоторые тонкие семантические некорректности. Известны исправленные методы, но они слишком сложны технически, чтобы рассматривать их в данном пособии.