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

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

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

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

Приведение предикатов к каноническому виду оправдано всегда, но сами канонические представления могут быть различными для предикатов, обладающих разными свойствами. Если предикат включает только одно имя поля, то его каноническое представление может, например, иметь вид "имя поля op константное арифметическое выражение" (это наиболее простая форма предиката, которая очень полезна при выполнении следующего этапа оптимизации, - простой предикат селекции). Например, если начальное представление предиката имеет вид (a+5)*A op 36 (мы обозначаем малыми буквами имена объемлющих переменных, а большими - имена полей отношений), то каноническим представлением такого предиката может быть A op 36/(a+5).

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

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

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

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

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

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

	- (A JOIN B) WHERE restriction-on-A AND restriction-on-B
эквивалентно выражению
	(A WHERE restriction-on-A) JOIN (B WHERE restriction-on-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, причем возможно появляющиеся кортежи-дубликаты уничтожены).

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

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

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

Как нам кажется, наиболее интересными работами, в которых рассматриваются специфические проблемы преобразований запросов на SQL к алгебраической форме, являются работы [57] и [65]. В [54] В.Ким заложил основу подхода, обосновал его важность и предложил ряд конкретных алгоритмов. Но при этом в некоторых конкретных методах он немного ошибся при согласовании семантики SQL и реляционной алгебры. У.Дайял в [65] показал это, ввел более точные формулировки и рассмотрел все возможные случаи.

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

Следуя [57], будем использовать следующие обозначения: Ri - i-е отношение базы данных; Ck - k-е поле (столбец) отношения.

Как отмечается в [57], предикаты, допустимые в запросах языка SQL, можно разбить на следующие четыре группы:

1. Простые предикаты. Это предикаты вида Ri.Ck op X, где X константа или список констант, и op - оператор скалярного сравнения (=, !=, >, >=, <, <=) или оператор проверки вхождения во множество (IS IN, IS NOT IN).
2. Предикаты со вложенными подзапросами. Это предикаты вида Ri.Ck op Q, где Q - блок запроса^, а op может быть таким же, как для простых предикатов. Предикат может также иметь вид Q op Ri.Ck. В этом случае оператор принадлежности ко множеству заменяется на CONTAINS или DOES NOT CONTAIN. Очевидно, что эти две формы симметричны, так что достаточно рассматривать только одну. (В соответствии с принятыми при описании синтаксиса SQL правилами обозначениями нелитералов блоком запроса (query block) называется допустимая конструкция языка, начинающаяся с ключевого слова SELECT, т.е. в блоке запроса не допускаются теоретико-множественные конструкции с использованием UNION, INTERSECT и MINUS. )
3. Предикаты соединения. Это предикаты вида Ri.Ck op Rj.Cn, где Ri != Rj и op - оператор скалярного сравнения.
4. Предикаты деления. Это предикаты вида Qi op Qj, где Qi и Qj - блоки запросов, а op может быть оператором скалярного сравнения или оператором проверки вхождения в множество.

Заметим, что приведенная классификация является некоторым упрощением реальной ситуации в SQL. Не рассматриваются предикаты соединения наиболее общего вида, включающие арифметические выражения с полями более чем двух отношений. Более того, для упрощения в [57] рассматриваются только соединения, в которых op - это операция равенства (эквисоединения).

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

Пусть запрос имеет глубину вложенности подзапросов - 1, т.е. состоит из внешнего и одного или более вложенных блоков на одном уровне. Предположим также, что логическое условие, указанное в разделе WHERE запроса, содержит в точности один предикат класса 2 или 4. (Как показано в заключении [57], эти предположения не снижают общности). Считается, кроме того, что список выборки внутреннего блока состоит из одного элемента (как утверждает В.Ким, это требование SQL, хотя из известных нам описаний это не следует). Вводится дополнительная классификация предикатов с вложенными подзапросами класса 1.

Предикаты со вложенными подзапросами типа A не содержат во вложенном подзапросе предикатов соединения с отношением внешнего блока и в списке выборке внутреннего блока указана агрегатная функция. Примером запроса с предикатом такого типа может быть

	SELECT Ri.Ck FROM Ri WHERE Ri.Cn =
	SELECT MAX (Rj.Cm) FROM Rj WHERE Rj.Cl > a.

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

Предикаты со вложенными подзапросами типа N такие же, как предикаты типа A, но без агрегатной функции. Примером соответствующего запроса может быть

	SELECT Ri.Ck FROM Ri WHERE Ri.Cn IS IN
	SELECT Rj.Cm FROM Rj WHERE Rj.Cl > a.

Как и в предыдущем случае внутренний подзапрос может быть полностью вычислен независимо от внешнего с получением списка скалярных значений и сведением предиката к простому. Именно так и поступает оптимизатор System R, не рассматривая других альтернатив. Однако не всегда этот способ выполнения запроса является оптимальным (все зависит от размеров получаемого списка скалярных значений).

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

	SELECT Ri.Ck FROM Ri WHERE Ri.Cn IS IN
	SELECT Rj.Cm FROM Rj WHERE Rj.Cr = Ri.Ch AND Rj.Cl > a.

Наконец, у предикатов типа JA внутренний блок содержит предикат соединения с отношением внешнего запроса и в списке выборки указана агрегатная функция. Например:

	SELECT Ri.Ck FROM Ri WHERE Ri.Cn =
	SELECT AVG (Rj.Cm) FROM Rj WHERE
	Rj.Cr = Ri.Ch AND Rj.Cl > a.

Среди предикатов класса 4 выделяется подкласс таких предикатов, вложенные блоки которых Qi или Qj (или и тот, и другой) содержат предикаты соединения с отношением внешнего запроса. Обозначим этот подкласс - D. Примером запроса с предикатом типа D может быть

	SELECT Ri.Ck FROM Ri WHERE
	(SELECT Rj.Cm FROM Rj WHERE Rj.Cn = Ri.Cl) CONTAINS
	(SELECT Rp.Cm FROM Rp WHERE Rp.Cr > a).

Предикаты класса 4, не относящиеся к типу D, не представляют интереса, потому что такие предикаты полностью вычисляются независимо от внешнего запроса и могут быть заменены на логическую константу (конечно, во время реального выполнения запроса). Очевидно, что это естественный и наиболее эффективный способ выполнения запроса, содержащего такой предикат.

В System R обработка запросов, содержащих предикаты типов J, JA и D, производится таким образом, что внутренний подзапрос, содержащий предикат соединения, вычисляется заново для каждого кортежа внешнего запроса (т.е. для каждого кортежа, для которого проверяется предикат). Других альтернатив оптимизатор System R не рассматривает.

Предлагается набор алгоритмов, преобразующих запросы, содержащие предикаты со вложенными подзапросами типов N, J, JA и D, к канонической форме. Эти преобразования, по сути, раскрывают семантику запроса, скрытую за единообразным синтаксисом SQL, путем его приведения к алгебраической форме.

Приведение к канонической форме запросов с предикатами типов N и J, содержащих оператор проверки вхождения в множество IS IN основано на следующей лемме:

Пусть запрос Q1 - это

	SELECT Ri.Ck FROM Ri, Rj WHERE Ri.Cn = Rj.Cm и запрос Q2 - это
	SELECT Ri.Ck FROM Ri WHERE Ri.Cn IS IN
	SELECT Rj.Cm FROM Rj. 

Тогда запросы Q1 и Q2 эквивалентны, т.е. дают одинаковый резульат.

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

Это один из моментов, который критикуется в [65]. Понятно, что при наличии такого ограничения на способ выполнения преобразованного запроса нельзя считать, что в нем появились предикаты соединения общего вида. Необходима дальнейшая детализация предикатов соединения с уточнением семантики, что и предлагается в [65]. Мы кратко остановимся на этом позже.

Примером преобразования запроса с предикатом класса J к канонической форме может быть следующий:

	SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS IN
	SELECT Rj.Cm FROM Rj WHERE Ri.Cn = Rj.Cp 
эквивалентно
	SELECT Ri.Ck FROM Ri, Rj WHERE
	Ri.Ch = Rj.Cm AND Ri.Cn = Rj.Cp.

Однако не так просто обстоят дела с предикатами типов N и J, в которых используется оператор проверки невхождения во множество IS NOT IN. Например, запрос

	SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS NOT IN
	SELECT Rj.Ch FROM Rj WHERE Rj.Cn = 
a не эквивалентен запросу
	SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS IN
	SELECT Rj.Ch FROM Rj WHERE Rj.Cn != Rj.Cp.

Потенциально лучшим способом выполнения такого запроса является выработка временного отношения X, соответствующего внутреннему подзапросу, сортировка обоих отношений по Ch и затем одновременное сканирование отсортированных файлов с тем, чтобы найти кортеж отношения Ri, не входящий в X. Можно сказать, что Ri и X "антисоединяются" предикатом анисоединения NOT (Ri.Ch = X.Ch). Если допустить наличие предикатов антисоединения в каноническом представлении запроса, то предыдущий запрос эквивалентен следующему:

	SELECT Ri.Ck FROM Ri, X WHERE NOT (Ri.Ch = Rj.Ch).

При этом предикаты антисоединения при выполнении запроса должны вычисляться только после выполнения предикатов соединения, полученных из J-предикатов c IS NOT IN. Например, если запрос с J-предикатом

	SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS NOT IN
	SELECT Rj.Cm FROM Rj WHERE Rj.Cn = Ri.Cp 

преобразован к псевдоканонической форме

	SELECT Ri.Ck FROM Ri, Rj WHERE
	Ri.Cp = Rj.Cn AND NOT (Ri.Ch = Rj.Cm),

то для сохранения семантики запроса в его исходной формулировки преобразованный запрос нужно понимать следующим образом: для каждого очередного кортежа отношения Ri выполняется соединение с отношением Rj в соответствии с предикатом соединения. При этом производится подотношение R1j, которое заменяет Rj в предикате антисоединения. Несколько забегая вперед, заметим, что гораздо более четко вопрос о преобразовании запросов с предикатами типа J, включающими оператор IS NOT IN, рассмотрен в [65]. Основным наблюдением, на котором основывается это рассмотрение, является связь предиката антисоединения с предикатом полусоединения и теоретико-множественной операцией разности множеств.

Рассмотренные возможные преобразования обобщаются в следующем алгоритме NEST-N-J, преобразующем запросы с предикатами типов N и J к "канонической" форме (понятно, что ее можно считать только псевдоканонической, поскольку отсутствует единая семантика предикатов соединения):

1. Объединить все списки отношений, встречающихся во всех разделах FROM, в один список FROM.
2. Объединить через AND логические условия всех разделов WHERE в одно логическое условие.
3. Заменить предикаты вида Ri.Cn op (SELECT Rj.Cm) на предикаты Ri.Cn op Rj.Cm, если op отлично от IS IN и IS NOT IN; на предикаты Ri.Cn = Rj.Cm, если op - это IS IN; на предикаты NOT( Ri.Cn = Rj.Cm), если op - это IS NOT IN.
4. Оставить список выборки внешнего запроса.

Преобразования запросов с предикатами типа JA основывается на наблюдении, что запрос Q3

	SELECT Ri.Ck FROM Ri WHERE Ri.Ch =
	SELECT AGG (Rj.Cm) FROM Rj WHERE Rj.Cn = Ri.Cp эквивалентен запросу Q4
	SELECT Ri.Ck FROM Ri WHERE Ri.Ch =
	SELECT Rt.C2) FROM Rt WHERE Rt.C1 = Ri.Cp, где Rt (C1, C2) =
	SELECT Rj.Cn, AGG (Rj.Cm) FROM Rj GROUP BY Rj.Cn.

Поскольку запрос Q4 содержит предикат типа J, он может быть преобразован к канонической форме с помощью алгоритма NEST-N-J. В более общем случае для запроса вида

	SELECT R1.Cn+2 FROM R1 WHERE R1.Cn+1 op
	SELECT AGG (R2.Cn+1) FROM R2 WHERE
	R2.C1 = R1.C1 AND ... AND R2.Cn=R1.Cn 

можно применить алгоритм преобразования NEST-JA:

1. Генерируется временное отношение Rt(C1,..., Cn, Cn+1), соответствующее запросу

   	SELECT C1,..., Cn, AGG (Cn+1) FROM R2
   	GROUP BY C1,..., Cn.

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

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

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

	SELECT Ri.Ck FROM Ri WHERE Ri.Ch =
	SELECT COUNT (Rj.Cm) FROM Rj WHERE Rj.Cn = Ri.Cp 

на самом деле не эквивалентен запросу

SELECT Ri.Ck FROM Ri, Rt WHERE
	Ri.Ch = Rt.Cm AND Ri.Cp = Rt.Cn, 

где Rt ( Cp, Cn ) = SELECT Rj.Cp, COUNT (Rj.Cn) FROM Rj

	GROUP BY Rj.Cp.

Если для некоторого кортежа отношения Ri значение поля Ri.Ch равно 0, а значение поля Ri.Cp таково, что в отношении Rj нет ни одного кортежа с таким же значением поля Rj.Cn, то по запросу в исходной формулировке будет выдано значение Ri.Ck этого кортежа (поскольку по определению функции COUNT она принимает значение 0 на пустом отношении). Преобразованный же запрос не выдаст значение Ri.Ck для этого кортежа, поскольку предикат соединения будет ложным. Это еще одно соображение в пользу того, что семантика запросов при их преобразованиях должна выражаться более точно.

Преобразования запросов, содержащих предикаты типа D, основаны на следующей лемме:

Пусть Q5 есть запрос

	SELECT Ri.Ck FROM Ri WHERE
	(SELECT Rj.Ch FROM Rj WHERE Rj.Cn = Ri.Cp) op
	(SELECT Rk.Cm FROM Rk), а Q6 - запрос
	SELECT Ri.Ck FROM Ri WHERE Ri.Cp = (SELECT C1 FROM Rt), 
где Rt (C1) определяется запросом
	SELECT Rj.Cn FROM Rj Rx WHERE
	(SELECT Rj.Ch FROM Rj RY WHERE RY.Cn = RX.Cn) op
	(SELECT Rk.Cm FROM Rk).

Запросы Q5 и Q6 эквивалентны.

Заметим, что запрос Q6 содержит предикат типа N, и, следовательно, может быть преобразован к канонической форме. Запрос, определяющий отношение Rt, является формулировкой на SQL реляционной операции деления. (Напомним, что по определению результатом операции реляционного деления отношения R на отношение S арности соответственно r и s, где r > s и S - не пусто, является отношение арности r-s, включающее такие и только такие кортежи t, что для любого кортежа u, принадлежащего S, кортеж tu принадлежит R. Известно, что операция реляционного деления выражается через другие операции реляционной алгебры.)

На лемме основан алгоритм NEST-D, приводящий запрос с предикатом типа D к канонической форме. Пусть задан запрос достаточно общего вида:

	SELECT R1.C1 FROM R1 WHERE
	(SELECT R2.C1 FROM R2 WHERE
	R2.C2 = R1.C2 AND ... AND R2.Cn = R1.Cn) =
	(SELECT R3.C1 FROM R3 WHERE
	R3.C2 = R1.C2 AND ... AND R3.Cm = R1.Cm).

Предположим, что n > m. Тогда действие алгоритма NEST-D состоит в следующем:

1. Образуем два временных отношения Rt1 (C1, ..., Cm) и Rt2 (C1, ..., Cn). Rt1 определяется запросом

   	SELECT C1, ..., Cm FROM R3, а Rt2 - запросом
   	SELECT C1, ..., Cn FROM R2.

2. Обозначим через Rt3 (Cm+1, ..., Cn) временное отношение, являющееся частным от реляционного деления Rt2 на Rt1.
3. Преобразуем начальный запрос к каноническому виду. Для этого

   3a) Исключим внутренний блок запроса с отношением R3.
   3b) Заменим все ссылки на поля отношения R2 на ссылки на соответствующие поля отношения Rt3 во внутреннем блоке запроса с отношением R2.
   3c) Уничтожим в этом блоке ключевые слова SELECT и FROM.
   3d) Включим Rt3 в список раздела FROM внешнего запроса.

   В результате работы этого алгоритма запрос будет преобразован к канонической форме

   	SELECT R1.C1 FROM R1, Rt3 WHERE
   	R1.Cm+1 = Rt3.Cm+1 AND ... AND R1.Cn = Rt3.Cn.

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

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

Наряду с базовыми операторами расширенная реляционная алгебра включает оператор проецирования, не устраняющий дубликаты кортежей в результирующем отношении (обычный для реляционной алгебры оператор проецирования, устраняющий дубликаты, называется в [65] оператором дельта-проецирования). Введены также следующие операции: Полусоединение отношений R и S по предикату J (Semijoin (R,S;J)) определяется как подмножество кортежей r, принадлежащих R, для каждого из которых существует кортеж s, принадлежащий S, такой, что предикат J(r,s) - истинен. Полусоединение выражается через соединение и дельта-проекцию:

Semijoin (R,S;J) = Delta-Project (Join (R,S;J);R.*). (R.* - полный набор атрибутов отношения R). Понятно, что использование полусоединения в алгоритме Кима Nest-N-J позволяет снять словестные оговорки по части особенностей трактовки операции соединения в получаемом каноническом запросе.

Операция обобщенной агрегации G-Agg (R; X; fnvector), где R - отношение, X - список атрибутов этого отношения, а fnvector - список имен агрегатных функций (COUNT, SUM, MAX, MIN, AVG и их варианты с DISTINCT) с указанием имен атрибутов R, к которым применяется соответствующая функция, вырабатывает отношение, кортежи которого вычисляются по следующим правилам: отношение R разбивается на группы кортежей с одинаковым значением полей из списка X; для каждой такой группы вычисляются все агрегатные функции из списка fnvector (для функций, помеченных ключевым словом DISTINCT, вычисление производится только на кортежах группы с различными значениями атрибутов, к которым применяется функция); кортеж результата соответствует группе и включает значения атрибутов Х и значения функций из fnvector. С применением обобщенной агрегации можно модифицировать алгоритм Кима NEST-JA таким образом, что не потребуется заранее предположение о вычислении временного отношения. Поэтому оптимизатор получит большую гибкость в выборе стратегии выполнения запроса (стратегия Кима остается одним из вариантов).

Явно введена операция антисоединения отношений R и S по предикату J (Antijoin (R,S;J)), определяемая как теретико-множественное дополнение отношения R к Semijoin (R,S;J). Такая трактовка также позволяет добиться большей гибкости при преобразованиях и последующей интерпретации запросов с предикатами типа J, содержащими операцию IS NOT IN.

Для разрешения трудностей, связанных с искажением при преобразованиях семантики запросов, содержащих агрегатную функцию COUNT, введена операция внешнего соединения отношений R и S по предикату J, определяемая следующим образом:

	Outerjoin (R,S;J) =
	Union (Join (R,S;J), Product (Antijoin (R,S;J), NULL-S)).

Здесь Union - оператор теоретико-множественного объединения, Join - оператор реляционного соединения, Product - оператор декартова произведения, а NULL-S - кортеж из неопределенных значений той же арности, что и S. Попросту говоря, отношение, получаемое в результате внешнего соединения двух отношений, содержит все кортежи, входящие в соединение этих отношений, а если некоторый кортеж первого отношения не соединяется ни с одним кортежем второго отношения, то по нему формируется кортеж результата путем дополнения его неопределенными значениями.

Преобразованный запрос выражается в терминах операций расширенной алгебры, порядок исполнения которых, вообще говоря, может изменяться. При этом не все возможные в принципе варианты выразимы через введенные операции. Для обеспечения максимальной гибкости при преобразованиях введены еще две операции - обобщенные соединение и ограничение. Обобщенное соединение отношений R и S по предикату J, сохраняющее атрибуты X отношения R, определяется как

	G-Join (R,S;X;J) = Union (Join (R,S;J),

Product (Delta-Project (Antijoin (R,S;J);X), NULL-YS)), где NULL-YS - кортеж из неопределенных значений над множеством атрибутов Y = R.* - X и S. Если R не содержит дубликатов, то G-Join (R,S;0;J) - это обычное соединение, а G-Join (R,S;R.*;J) - внешнее соединение.

Оператор обобщенного ограничения отношения R по предикату P с сохранением атрибутов X определяется как

	G-Restrict (R;X;P) = Union (Restrict (R;P), Product 
	(Delta-Project((R Minus Restrict (R,P));X), NULL-Y)).

В [65] демонстрируется большое количество возможных преобразований с использованием свойств введенных операторов. Кроме тех сложных предикатов SQL, которые рассматривались Кимом, анализируются и предикаты с кванторами EXISTS и NOT EXIST, введенные в SQL уже после написания Кимом его работы. Для точности заметим, что в [65] не рассматриваются преобразования запросов с предикатами типа D в терминологии Кима.

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

Назад | Содержание | Вперед