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


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


Приведение к канонической форме запросов с предикатами типов 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.


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