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


Некоторые частные алгоритмы - часть 3


Но этот вариант выполнения запроса Q2 совсем необязательно будет эффективнее варианта с сортировкой, поскольку для вычисления агрегатных функций потребуется, по сути дела, просканировать отношение в порядке, предписанном индексом, что может повлечь большое число обменов с внешней памятью. (Конечно, вариант выполнения запроса Q2 c использованием индекса по DEPT# будет самым оптимальным, если отношение EMP кластеризовано по DEPT#.)

Таким образом, выполнение запросов с агрегатными функциями, как правило, требует сортировок. В этом случае в System R сначала выполняется сортировка, а затем над отсортированным отношением или группами его кортежей вычисляются агрегатные функции. В [67] предлагается оптимизация этой процедуры, позволяющая сократить требуемые накладные расходы. Основная идея этого предложения проста - совместить, если это возможно, процесс сортировки и вычисления агрегатных функций. Тогда отпадет необходимость повторного сканирования отсортированного отношения. Например, в случае выполнения запроса Q2 путем сортировки отношения EMP по значениям DEPT# в ходе сортировки на самом деле строится отношение (DEPT#, AVG (SAL + COMM)), причем каждый раз, когда по правилам сортировки в существующую группу с данным значением DEPT# должен был быть добавлен очередной кортеж, на самом деле происходит пересчет значения AVG (SAL + COMM).

Несмотря на простоту и кажущуюся очевидность идеи, предлагаемый в [67] метод реализации этого подхода достаточно сложен. План выполнения запроса строится в терминах функционального языка высокого уровня. Далее эта программа проходит через две стадии преобразований. На первой стадии производятся преобразования плана в терминах того же языка. Получаемая программа обладает необходимыми совмещениями, но ее прямое выполнение было бы неээфективно за счет возможных рекурсий. Поэтому на второй стадии производится дополнительное преобразование компиляция программы на традиционный язык программирования, и это представление уже свободно от рекурсий и допускает эффективное выполнение.




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



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