Эффективные алгоритмы выполнения запросов

Оптимизация запросов состоит в выборе оптимального (или близкого к тако­вому) способа выполнения запроса на основе:

• особенностей физической структуры БД и поддерживаемых в ней управляющих структур;

• заложенных в систему знаний о допустимых стратегиях вы­полнения элементарных составляющих запроса;

• той или иной статистической информации, позволяющей оценить эффективность выбранного плана выполнения за­проса.

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

Алгоритмы реляционных соединений. Работы, связанные с созданием эффективных структур данных и алгоритмов выпол­нения реляционных операций, касаются реляционных соедине­ний в связи с распространенностью и важностью операции со­единения. Тем не менее надо повышать эффективность и прочих операций.

Известно, что возможности агрегатных запросов наиболее полно поддерживаются на языке SQL. В списке выборки опера­тора SELECT этого языка наряду с арифметическими выраже­ниями, построенными из имен полей отношений (указанных в списке FROM) и констант, встречаются арифметические выра­жения, включающие агрегатные функции COUNT, AVG, MIN и МАХ, параметрами которых могут быть арифметические выра­жения первого типа. Выполнение запросов с агрегатными функ­циями, как правило, требует сортировок. В этом случае сначала выполняется сортировка, а затем над отсортированным отноше­нием или группами его кортежей вычисляются агрегатные функ­ции. Предлагаемая оптимизация этой процедуры проста – со­вместить, если это возможно, процесс сортировки и вычисления агрегатных функций. Тогда отпадет необходимость повторного сканирования отсортированного отношения.

16