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


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


Преобразования запросов с предикатами типа 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 для этого кортежа, поскольку предикат соединения будет ложным.


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



Книжный магазин