Логическая оптимизация запросов — до 20 мин

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

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

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

Приведение предикатов к каноническому виду оправдано всегда, но сами канонические представления могут быть различными для предикатов, обладающих разными свойствами. Если предикат включает только одно имя поля, то его каноническое представление может, например, иметь вид "имя поля [знак операции] константное арифметическое выражение" (это наиболее простая форма предиката, которая очень полезна при выполнении следующего этапа оптимизации, — простой предикат селекции). Будем в дальнейших примерах обозначать малыми латинскими буквами имена переменных, а большими — имена полей отношений. Например, если начальное представление предиката имеет вид: (a+3)*A>10, то каноническим представлением такого предиката может быть: A>10/(a+3).

Если предикат включает в точности два имени поля разных отношений (или двух разных вхождений одного отношения), то его каноническое представление может иметь, например, вид "имя поля [знак операции] арифметическое выражение", где арифметическое выражение в правой части включает только константы и имя второго поля (это тоже достаточно простая и полезная форма для выполнения следующего шага оптимизации — предикат соединения; особенно важным случаем является случай эквисоединения, когда операция — это равенство). Например, если в начальном представлении предикат имеет вид: A*10-a*B<b, то каноническим представлением может быть A<(b+a*B)/10.

Наконец, для рассматриваемых предикатов более общего вида имеет смысл приведение предиката к каноническому представлению вида "арифметическое выражение [знак операции] константное арифметическое выражение", где выражения правой и левой частей также приведены к каноническому представлению, например, в выражениях полностью раскрыты скобки и произведено некоторое лексикографическое упорядочение. Такие преобразования имеют смысл для того, чтобы в дальнейшем можно было произвести поиск общих арифметических выражений в разных предикатах запроса. Такая работа может быть оправдана, поскольку при реальном выполнении запроса вычисление арифметических выражений будет производиться при выборке каждого очередного кортежа, т.е. потенциально очень большое число раз.

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

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

При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду или в процессе нормализации логического условия), и, кроме того, может быть произведено упрощение логического выражения за счет, например, выявления конъюнкции взаимно противоречащих предикатов. Так, если в логическом выражении встречается фрагмент...(A>5)AND(A<5)..., то его можно заменить на...FALSE... Возможны и более "умные" упрощения. Например, фрагмент логического выражения...(A>B)AND(B=5)... можно заменить на...(A>5)... Как видно из последнего примера, такие упрощения могут оказаться очень существенными для дальнейшей обработки запроса: в запросе с логическим условием первого вида предполагалось выполнение соединения двух отношений; после преобразования запрос уже не требует соединения.

Наконец, в традиционных оптимизаторах распространены логические преобразования, связанные с изменением порядка выполнения реляционных операций. Например, в терминах реляционной алгебры эти преобразования могут основываться на следующих правилах (A и B — имена отношений):

(A JOIN B) WHERE условие-для-A AND условие-для-B

эквивалентно выражению

(A WHERE условие-для-A) JOIN (B WHERE условие-для-B);

(A WHERE restriction—1) WHERE restriction—2

эквивалентно выражению

A WHERE restriction—1 AND restriction—2;

(A [attribute—list—1]) [attribute—list—2]

эквивалентно выражению

A [attribute—list—2];

(A [attribute—list—1) WHERE restriction—1

эквивалентно выражению

(A WHERE restriction—1) [attribute—list—1].

Здесь JOIN обозначает реляционный оператор естественного соединения отношений; A WHERE restriction — оператор ограничения отношения A в соответствии с предикатом restriction (т.е. A WHERE restriction — это отношение, включающее кортежи, входящие в отношение A и удовлетворяющие предикату restriction); A [arrtibute—list] — проекция отношения A на заданный список атрибутов (т.е. A [attribute—list] — это отношение, состоящее из кортежей, каждый из которых получен выборкой указанных в списке полей из соответствующего кортежа отношения A, причем возможно появляющиеся кортежи—дубликаты уничтожены).

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

В частности, существуют подходы, связанные с преобразованием к алгебраической форме запросов на языке SQL. Широкое распространение этого языка побуждает нас рассмотреть соответствующие вопросы более подробно. Можно выявить две основные побудительные причины преобразований запросов на SQL к алгебраической форме. Первой, на наш взгляд, менее важной причиной может быть стремление к использованию реляционной алгебры в качестве унифицированного внутреннего интерфейса реляционной СУБД. Особенно распространен такой подход при использовании специализированных машин баз данных, на основе которых реализуются различные интерфейсы доступа к базам данных. Тогда, естественно, интерфейс машины баз данных должен быть унифицирован (например, быть алгебраическим), а все остальные интерфейсы, включая интерфейс на основе SQL, приводятся к алгебраическому.

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

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

Дата добавления: 2014-01-11