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

Основная часть работ, связанных с выработкой эффективных структур данных и алгоритмов выполнения реляционных операций, посвящена реляционным соединениям. Как мы уже отмечали, это оправдано распростаненностью и важностью операции соединения. Однако, естественно, необходимо повышать эффективность и прочих операций. Соответствующие работы очень разнородны, в них трудно выделить общие направления. В качестве примера мы рассмотрим две работы, одна из которых содержит предложения по части эффективного вычисления агрегатных функций, а другая касает повышения эффективности выполнения запросов из выделенного набора.

Насколько нам известно, возможности агерегатных запросов наиболее полно поддерживаются в языке SQL. Напомним, что в списке выборки оператора SELECT этого языка наряду с арифметическими выражениями, построенными из имен полей отношений, указанных в списке FROM, и констант, могут встречаться арифметические выражения, включающие агрегатные функции COUNT, AVG, MIN и MAX, параметрами которых могут быть арифметические выражения первого типа. При этом семантика запроса с агрегатными функциями зависит от наличия или отсутствия в запросе статьи GROUP BY. Поясним это на нескольких примерах.

Вернемся к нашей гипотетической базе данных из Раздела 2. Здесь нас будет интересовать только первое отношение этой базы данных - отношение EMP, в котором регистрируются сотудники организации. Пусть схема этого отношения определена следующим образом: EMP (EMP#, EMPNAME, SAL, COMM, DEPT#). Поля SAL и COMM, соответственно, содержат значения оклада и комиссионных, причитающихся данному служащему. Допустимы следующие запросы:

	SELECT COUNT (EMP#) FROM EMP
или, эквивалентно, 
	(Q1) SELECT COUNT (*) FROM EMP .

Эти два запроса эквивалентны, поскольку EMP# является первичным ключем отношения. Каждый из них выдает общее количество служащих. Запрос

SELECT COUNT (DEPT#) FROM EMP выдает количество отделов в организации и уже, конечно, не эквивалентен запросу Q1. Может быть задан более сложный запрос, например,

	SELECT COUNT (*), AVG (SAL + COMM) FROM EMP
	WHERE DEPT# = 6.

Результатом выполнения такого запроса является кортеж, содержащий число сотрудников шестого отдела и средний размер их заработка. Общим свойством запросов с агрегатными функциями, не содержащих статьи GROUP BY, является то, что результатом любого такого запроса является один кортеж, полученный применением агрегатных функций к группе кортежей, сформированных под управлением логического условия, заданного в разделе WHERE. С использованием статьи GROUP BY можно формулировать более сложные запросы. Например, можно получить информацию о средних доходах сотрудников всех отделов, задав запрос

	(Q2) SELECT DEPT#, AVG (SAL + COMM) FROM EMP
	GROUP BY DEPT#.

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

Как правило, при выполнении запросов с агрегатными функциями требуется сортировка отношений. В приведенных примерах сортировка не нужна только при выполнении запроса Q1: чтобы получить общее число сотрудников, достаточно просканировать отношение EMP любым способом и подсчитать количество кортежей.

Единственным оптимизационным приемом, используемым при выполнении запросов с агрегатными функциями в System R, является применение в случае возможности индексов. Например, для выполнения запроса Q1, если над отношением EMP определен хотя бы один индекс, достаточно просмотреть список записей, хранящихся в листовых блоках этого индекса, вообще не обращаясь к хранимым кортежам. Возможны и более сложные случаи. Если определен индекс на поле SAL и требуется выполнить запрос

SELECT AVG (SAL) FROM EMP, то можно опять обойтись без обращения к кортежам, просматривая только записи индекса.

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

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

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

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

Упомянем, наконец, еще одно предложение, касающееся повышения эффективности выполнение выделенного набора запросов [69-70]. Это предложение является очень простым, может иногда резко повысить эффективность системы, но оставляет много вопросов в части реализации. Авторы предлагают хранить в базе данных наряду с базовыми отношениями тексты и результаты выполнения некоторых предписанных администратором запросов.

При поступлении запроса в систему прежде всего производится поиск этого запроса среди ранее сохраненных. Если он находится среди них, то, естественно, выполнение запроса очень эффективно. В противном случае выполнение запроса происходит по общим правилам. Возможны расширения этого подхода (не предлагаемые авторами). Можно было бы относиться к хранимым запросам, как к материализованным представлениям базы данных, и разрешать задавать запросы над ними и т.д.

Очевидной проблемой, эффективное решение которой неизвестно, является поддержание корректности результатов хранимых запросов при модификациях базы данных. В [69-70] предлагаются некоторые решения этой проблемы, но они не являются полными, а соответствующие действия могут вызывать существенные накладные расходы при выполнении операций вставки, удаления и модификации кортежей в базовые отношения.

Отмечается одна область приложений, в которых использование хранимых отношений может резко повысить эффективность системы. Это меню-ориентированные системы со стандартным встроенным набором запросов, в которых изменения базы данных редки.

Назад | Содержание | Вперед