Обзор методов оптимизации запросов в реляционных системах




Слияние вложенных подзапросов


Рассмотрим следующий пример запроса с вложенными подзапросами из [13], где Emp# и Dept# - ключи соответствующих отношений:

SELECT Emp.Name FROM Emp WHERE Emp.Dept# IN SELECT Dept.Dept# FROM Dept WHERE Dept.Loc = 'Denver' AND Emp.Emp# = Dept.Mgr

Если для ответа на запрос используется семантика последовательного просмотра кортежей, то внутренний запрос вычисляется один раз для каждого кортежа отношения Emp. Очевидная оптимизация применима в том случае, когда внутренний блок запроса не содержит переменных из внешнего блока запроса (отсутствует корреляция). В таких случаях внутренний запрос требуется вычислить только один раз. Если во внутреннем блоке присутствует переменная из внешнего блока, мы говорим, что блоки запроса коррелируют. Например, в приведенном выше запросе Emp.Emp# действует как корреляционная переменная. Ким [35] и в последствие другие исследователи [16, 13, 44] выявили методы устранения вложенности в SQL-запросе с корреляцией и "уплощения" его до запроса с одним блоком. Например, приведенный запрос со вложенностью приводится к

SELECT E.Name FROM Emp.E, Dept D WHERE E.Dept# = D.Dept# AND D.Loc = 'Denver' AND E.Emp# = D.Mgr

Дайал [13] был первым, кто предложил алгебраическую трактовку устранения вложенности. Сложность проблемы зависит от структуры вложенности, т.е. от того, содержит ли вложенный запрос кванторы (например, ALL, EXISTS) и агрегаты. В простейшем случае, примером которого является приведенный выше пример, семантика перебора кортежей может моделироваться конструкцией Semijoin (Emp, Dept, Emp.Dept # = Dept.Dept#). Опираясь на этот подход, нетрудно заметить, почему может быть произведено слияние запроса, поскольку:

Semijoin ( Emp, Dept, Emp.Dept# = Dept.Dept# ) = Project ( Join (Emp, Dept), Emp* )

Здесь предикатом соединения для Join (Emp, Dept) является Emp.Dept# = Dept.Dept#. Второй операнд операции Project означает, что должны быть оставлены все столбцы отношения Emp.

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


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