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


Выбор и оценка альтернативных планов выполнения запросов - часть 3


Если, например, задан запрос

SELECT EMP.EMPNAME, DEPT.DEPTNAME FROM EMP, DEPT WHERE EMP.DEPT# = DEPT.DEPT#

(мы предполагаем, что в нашей базе данных, описывающей структуру организации, отношение DEPT расширено еще одним полем DEPTNAME, содержащим название отдела), то при применении метода вложенных циклов предполагается наличие двух циклов сканирования отношений EMP и DEPT соответственно. Во внешнем цикле (например, для отношения EMP) выбирается очередной кортеж EMP, и для каждого такого кортежа выполняется полное сканирование отношения DEPT с выбором таких кортежей, значения поля DEPT# которых удовлетворяет предикату соединения. При этом, естественно, рассматриваются все возможные способы сканирования отношений. (Мы описали упрощенный вариант алгоритма. Более точное описание можно найти в [129].)

При использовании метода сортировок со слияниями сначала производится сортировка обоих отношений в соответствии со значениями поля DEPT# каждого отношения. При этом получаются два отсортированных временных файла EMP1 и DEPT1. Далее производится "параллельное" сканирование обоих файлов, в ходе которого выполняется "слияние" отношений в смысле операции соединения. Более точно, выбирается первый кортеж EMP1. Пусть значение поля DEPT# этого кортежа равно C1. Далее, выбирается первый кортеж из DEPT1 такой, что значение поля DEPT# этого кортежа D1 >= C1. Если удалось найти кортеж DEPT1 с D1 = C1, то это означает, что мы вошли в группу кортежей DEPT1, соединимых с текущим кортежем EMP1. Производится соединение каждого кортежа этой группы с текущем кортежем EMP1, после чего выбирается следующий кортеж EMP1, и если значение поля DEPT# в нем не изменилось, то соединение с текущей группой кортежей DEPT# повторяется. Так происходит до тех пор, пока из EMP1 не будет выбран кортеж со значением поля DEPT# С2 > C1. Тогда производится последующее сканирование DEPT1, начиная с позиции, сле- дующей за текущей группой, пока не будет выбран кортеж со значением поля DEPT# D2 >= C2 и т.д.




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



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