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


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


Именно так и поступает оптимизатор 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, путем его приведения к алгебраической форме.




Начало  Назад  Вперед