Заключительные замечания

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

17.5. Статистические показатели базы данных

На стадиях 3 и 4 общего процесса оптимизации (называемых стадиями выбора пути доступа) используются статистические показатели базы данных, сохраняемые в ее каталоге (ниже кратко описаны способы их применения). В демонстрационных целях ниже кратко рассматриваются (с небольшими дополнительными комментариями) некоторые из основных статистических показателей, используемых в двух коммерческих продуктах - СУБД DB2 и INGRES. Приведем некоторые из основных статистических показателей, применяемых в СУБД DB2.

Для каждой базовой таблицы фиксируются следующие показатели:

кардинальность;

количество страниц внешней памяти, занятых таблицей;

доля табличного пространства, занимаемого таблицей.

Для каждого столбца каждой базовой таблицы фиксируются следующие показатели:

количество различных значений в столбце;

второе наибольшее значение в столбце;

второе наименьшее значение в столбце;

десять значений в столбце (только для индексированных столбцов), которые чаще всего встречаются, а также количество вхождений каждого из этих значений.

Для каждого индекса фиксируются следующие показатели:

индикатор, указывающий, является ли индекс кластеризованным (т.е. индексом, в котором логический порядок значений ключа совпадает с физическим порядком их размещения в таблице);

для кластеризованных индексов - доля индексированной таблицы, находящейся в кластеризующей последовательности;

Так как обе названные СУБД поддерживают стандартный язык SQL, при их обсуждении вместо терминов переменная-отношение и атрибут будут использоваться термины таблица и столбец соответственно Также заметим, что в обеих СУБД предполагается, что каждая базовая таблгща должна отображаться в одну хранимую таблицу.

количество листовых страниц в индексе;

количество уровней в индексе.

Замечание. Перечисленные выше статистические показатели не обновляются при каждом обновлении базы данных из-за больших накладных расходов, связанных с их вычислением. Вместо этого статистические показатели обновляются выборочно, с помо-шью системной утилиты RUNSTATS, которая запускается по требованию администратора базы данных, например после реорганизации базы данных. Аналогичное утверждение применимо и к большинству других коммерческих продуктов, в том числе к системе INGRES, где соответствующая утилита называется OPTIMIZEDB.

Перечислим некоторые из основных статистических показателей базы данных, накапливаемых в СУБД INGRES.

Замечание. В системе INGRES индекс рассматривается как частный случай хранимой таблицы. Поэтому приведенные ниже статистические показатели для базовых таблиц и столбцов вычисляются также для индексов.

Для каждой базовой таблицы фиксируются следующие показатели:

кардинальность;

количество первичных страниц для таблицы;

количество страниц переполнения для таблицы.

Для каждого столбца в каждой базовой таблице фиксируются следующие показатели:

количество различных значений в столбце;

максимальное, минимальное и среднее значения для столбца;

реальные значения в столбце и частота их вхождений.

17.6. Стратегая по принципу разделяй и властвуй

Как уже упоминалось выше, в конце раздела 17.4, реляционные выражения рекурсивно определяются в терминах подчиненных выражений, что позволяет оптимизатору применять различные стратегии оптимизации по принципу разделяй и властвуй . Заметьте, что использование подобных стратегий особенно привлекательно в средах, поддерживающих параллельные вычисления, в частности в распределенных системах, в которых различные части запроса могут вычисляться параллельно на разных процессорах [17.58]-[ 17.61]. В данном разделе рассматривается одна из подобных стратегий, получившая название декомпозиция запросов. Впервые она была применена в прототипе системы INGRES [17.36], [17.37].

Замечание. Дополнительную информацию об оптимизации в СУБД INGRES (особенно в ее коммерческой версии, которая в данном контексте несколько отличается от прототипа системы INGRES) можно найти в работе Куи (Kooi) и Франкфорта (Frankforth) [17.2], а также в [17.38].

Основная идея метода декомпозиции запросов строится на разбиении запроса со многими переменными диапазона на последовательность запросов меньшего размера обычно с одной или двумя такими переменными диапазона. Требуемая декомпозиция достигается с помощью методов отделения и подстановки кортежей.

Напомним, что язык запросов QUEL в системе INGRES использует средства реляционного исчисления.

Отделение - это процесс удаления из запроса компонента, который имеет только одну общую переменную с оставщейся частью запроса.

Подстановка кортежа - это процесс подстановки значения одной переменной в запросе (один кортеж за одну операцию).

Использование метода отделения всегда предпочтительней использования метода подстановки кортежей во всех случаях, когда существует возможность выбора (см. пример, приведенный ниже). Тем не менее рано или поздно декомпозиция методом отделения обязательно приведет к разбиению запроса на множество компонентов, которые больще нельзя будет подвергнуть декомпозиции с помощью этого метода, после чего придется обратиться к методу подстановки кортежей.

Ниже рассмотрен пример декомпозиции (основанный на примере из [17.36]). Словесное выражение этого запроса имеет следующий вид: Определить имена поставщиков из Лондона, поставляющих некоторые красные детали весом менее 25 фунтов в количестве более 200 штук . Приведем формулировку этого запроса на языке QUEL, на которую далее будем ссылаться, как на формулировку Q0.

Q0: RETRIEVE ( S.SNAME]

Здесь подразумеваемый диапазон переменных S, Р и SP распространяется на всю одноименную переменную-отношение.

Исходя из последних двух сравнений в выражении запроса можно заключить, что нас интересуют только красные детали весом менее 25 фунтов. Следовательно, можно отделить подзапрос с одной переменной (на самом деле являющийся проекцией выборки), в котором используется переменная Р.

D1: RETRIEVE INTO Р (P.Pl) WHERE P.COLOR = Red

AND P.WEIGHT < 25

Этот запрос с единственной переменной может быть отделен, так как в нем присутствует только одна переменная (а именно - переменная диапазона Р), совместно используемая с оставшейся частью запроса. Так как запрос D1 связывается с остатком исходного запроса по атрибуту Р (в условии SP.Pl = P.Pl), атрибут Р должен входить в кортеж-прототип (см. главу 7) отделенного запроса. Другими словами, отделенный запрос предназначен для выборки номеров только тех красных деталей, которые весят менее 25 фунтов. Отделенный запрос обозначим как запрос D1, результатом выполнения которого является временная переменная-отношение Р. (Назначение предложения INTO состоит в том, чтобы создать новую переменную-отношение Р с единственным атрибутом Р. Эта переменная-отношение создается автоматически и содержит результат выполнения операции RETRIEVE.) И наконец заменим ссылки на переменную-отношение Р в сокращенной версии запроса Q0 ссылками на переменную-отношение Р. Эту новую сокращенную версию исходного запроса обозначим как Q1.