Два подхода к вычислению выражений при обработке запросов

Рассмотрим, как выполняются выражения из нескольких операторов. Пусть БД содержит следующие отношения.

Клиент банка (код клиента, ФИО) и счет (номер, сумма, код клиента). Пусть существует запрос, транслированный в следующее выражение реляционной алгебры. pклиент.ФИО(sсумма<250(счет)><клиент). При этом строится следующее дерево операторов. Вычисление происходит с самого нижнего уровня и до корня дерева. {см. сильно ниже } Вычисление может вестись параллельно по разным поддеревьям.

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

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

Конвейерная обработка может идти двумя путями:

1 Движение по запросу. В этом случае нижний уровень передает кортеж на верхний только после того, как получит от него запрос.

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

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

Правила эквивалентности выражений: приведение комплексной селекции к каскадной; коммутативность селекции; преобразование селекции декартового произведения; коммутативность тета-соединения; ассоциативность натурального и тета-соединения; дистрибутивность селекции относительно тета-соединения, объединения, пересечения и разности.

Пусть в БД есть отношения банк (код, название банка, город), клиент (номер клиента, имя) и счет в банке(номер счета, номер клиента, номер банка).

Рассмотрим запрос «Найти имена всех покупателей, которые имеют счета в банках, расположенных в Москве».

П(Проекция) имя(s(селекция)город=Москва

(банк >< (счет >< клиент))), что соответствует плану 1.

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

П(Проекция) имя((s(селекция) город=Москва(банк)) ><(счет >< клиент)), что соответствует плану 2.

При этом результирующий набор кортежей не измениться.

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

Правила эквивалентности.

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

Рассмотрим основные правила эквивалентности и выгоду, которую они могут дать при оптимизации запроса, но нужно помнить, что в принципе правила эквивалентности не утверждают, что одно выражение заведомо лучше другого.

1.Операция селекции по конъюнкции условий эквивалентна последовательности селекций по индивидуальным условиям.

S(селекция)q1&q2(E) = Sq1(S q2(E))

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

2. Операция селекции коммутативна.

S(селекция)q1(S q2(E))= Sq2(S q1(E))

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

В последовательности проекций достаточно учитывать последнюю, остальные пропускаются.

П(проекция)L1(ПL2(…(ПLn(E))…))= ПL1(E)

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

Селекцию декартова произведения можно преобразовать в тета-соединение по тому же условию.

S(селекция)q(E1xE2)= E1 ><q(декартово произведение)E2

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

Это правило эквивалентности может быть распространено на селекцию тета-соединения.

Sq1(E1><qЕ2)=Е1><q1&q2Е2

Операция тета-соединения коммутативна.

E1><qЕ2= E2><qЕ1

Так как операция натурального соединения является частным случаем тета-соединения, то операция натурального соединения так же комутативна.

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

Натуральное соединение ассоциативно.

(E1><Е2) >< Е3 =E1>< (Е2 >< Е3)

Тета-соединение ассоциативно по в следующей форме.

(E1 ><q1 Е2) >< q2 & q3Е2=Е1><q1&q3Е2 (E1><q2Е2)

Это правило верно, если q2 построено только на атрибутах отношений Е2 и Е3. При этом условия могут быть пустыми, что позволяет распространить ассоциативность на декартово произведение.

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

Селекция дистрибутивна по отношению к тета-соединению, при следующих условиях.

а) Sq0(Е1 ><q Е2) = (Sq0(Е1)) ><q Е2

Это правило верно, если все атрибуты условия q0 селекции принадлежат исходному отношению Е1.

б) Sq1 or q2(Е1><q Е2)=(Sq1(Е1))><q(Sq2(Е2))

Это правило верно, если атрибуты условия q1 принадлежат только исходному отношению Е1, а атрибуты условия q2 принадлежат только исходному отношению Е2.

Вначале производится селекция, что уменьшает объем исходных данных для соединения.

Операция проекции дистрибутивна относительно тета-соединения.

а) Пусть L1 – атрибуты отношения Е1, а L2 – атрибуты отношения Е2. Если условие тета-соединения включают только атрибуты, принадлежащие L1+L2, то имеет место равенство.

П(проекция)L1+L2(E1><qE2) = (П L1(E1))><(П L2(E2))

б) Пусть существует соединение вида E1><qE2 и L1 и L2 – атрибуты отношений Е1 и Е2 соответственно. L3 – атрибуты, участвующие в условии q и принадлежащие Е1, но не принадлежащие L1+L2. Аналогично L4 – атрибуты, участвующие в условии qи принадлежащие Е2, но не принадлежащие L1+L2. Тогда

П L1+L2(E1><qE2) =pL1+L2((П L1+L3(E1))><q(ПL2+L4(E2)))

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

Объединение и пересечение коммутативны.

Е1 - Е2 = Е2 - Е1

Объединение и пересечение ассоциативны.

(Е1 + Е2) + Е3 = Е1 + (Е2 + Е3)

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

Операция селекции дистрибутивна относительно операций объединения, пересечения и разности.

Sq(Е1-Е2)=Sq(Е1)-Sq(Е2)

Позволяет уменьшить размер отношений, с которыми производится основная операция. Особенно может оказаться важным, когда Е1 и Е2 не отсортированы.

Операция проекции дистрибутивна по отношению к объединению

П L(E1+E2)=(П L(E1)) + (П L(E2)).

Это далеко не весь список правил эквивалентности.

Рассмотрим, почему применение правила эквивалентности не всегда приводит к снижению стоимости выполнения запроса. Пусть имеется выражение Sq(r><s). При этом атрибуты условия q принадлежат только отношению s. Казалось бы нужно выполнить селекцию отношения s до того, как выполнять соединение. Если же отношение r мало по относительно s и есть индекс в отношении s по атрибутам соединения, но нет индекса по атрибутам q, то предложенное преобразование не уменьшит стоимости выполнения запроса.