Введение в системы БД (542480), страница 167
Текст из файла (страница 167)
Семантическую оптимизацию можно определить как процесс преобразования одного запроса в другой, качественно отличный запрос, который, тем не менее, дает результат, идентичный результату исходного запроса, благодаря тому, что обрабатываемые данные удовлетворяют определенному ограничению целостности.
Важно понимать, что, в принципе, любое ограничение целостности может быть использовано для семантической оптимизации. Другими словами, этот прием не ограничен использованием только ограничений целостности. Например, предположим, что в базе данных поставщиков и деталей установлено ограничение, утверждающее, что все красные детали должны храниться в Лондоне. Рассмотрим следующий запрос. Определить всех поставщиков только красных детазей которые !поставщики) на- ходятся в там же городе, где хранится хотя бы одна поставзлеиая иии детазь. Это довольно сложный запрос! Но в силу рассмотренного ограничения целостности его можно привести к такому виду. Опредезнть всех поставщиков из Лондона, поставляющих только красные детали.
Замечание. Насколько известно автору, лишь немногие современные коммерческие продукты в должной мере используют идею семантической оптимизации. Однако, в принципе, семантическая оптимизация способна обеспечивать значительное улучшение производительности (весьма вероятно, намного превышающее то, которое в настоящее время может быть достигнуто с помощью любых традиционных приемов оптимизации). Более подробно идея семантической оптимизации изложена в 117.16], !17.281 — !17.30) и особенно — в !17.27).
652 Часть К Дополнительные аспекты Заключительные замечания В завершение хотелось бы подчеркнуть фундаментальную важность свойства реляционной замкнутости в отношении всех аспектов, обсуждавшихся в этом разделе. Наличие реляционной замкнутости означает, что можно писать вложенные выражения, а это, в свою очередь, означает, что единственный запрос может быть представлен единственным выражением вместо некоторой процедуры, состоящей из нескольких выражений, и поэтому нет необходимости в анализе потоков. Вложенные выражения рекурсивно определяются в терминах подчиненных выражений, что позволяет оптимизатору использовать множество стратегий вычисления по принципу "разделяй и властвуй" (подробности приводятся ниже, в этой же главе).
И конечно же, при отсутствии свойства реляционной замкнутости не имели бы смысла общие законы, такие как правило дистрибутивности и т.п. 17.5. Статистические показатели базы данных На стадиях 3 и 4 общего процесса оптимизации (называемых стадиями выбора пути доступа) используются статистические показатели базы данных, сохраняемые в ее каталоге (ннже кратко описаны способы их применения). В демонстрационных целях ниже кратко рассматриваются (с небольшими дополнительными комментариями) некоторые из основных статистических показателей, используемых в двух коммерческих продуктах — СУБД РВ2 и )ХПКЕБ.
Приведем некоторые из основных статистических показателей, применяемых в СУБД (лВ2з. ° Для каждой базовой таблицы фиксируются следующие показатели: ° кардинальность; ° количество страниц внешней памяти, занятых таблицей; ° доля табличного пространства, занимаемого таблицей. ° Для кажлого столбца каждой базовой таблицы фиксируются следующие показатели: ° количество различных значений в столбце; ° второе наибольшее значение в столбце; ° второе наименьшее значение в столбце; ° десять значений в столбце (только для индексированных столбцов), которые чаше всего встречаются, а также количество вхождений каждого из этих значений.
° Для каждого индекса фиксируются следующие показатели: ° индикатор, указывающий, является ли индекс кластеризованным (т.е. индексом, в котором логический порядок значений ключа совпадает с физическим порядком их размещения в таблице); ° лля кластеризованных индексов — доля индексированной таблицы, находящейся в кластеризующей последовательности; ~ Так как обе названные СУБД поддержиоают стандартныб язык Бйь, при ил обсуждении вместо тер нинов "переменная-отношение" и "атрибут *' будут использоааться термины "таблица" и "столбец" соответственно Также запетом, цто в обе~се СУБД предполагается, цто калсдая базовая таблшцо дол,ясна ол1одра жаться в одну хранимую таблицу. 653 Глава 17. Одтиицэация ° количество листовых страниц в индексе; ° количество уровней в индексе. Замечание.
Перечисленные выше статистические показатели не обновляются при каждом обновлении базы данных из-за больших накладных расходов, связанных с их вычислением. Вместо этого статистические показатели обновляются выборочно, с помощью системной утилиты ЯВМВТйТЯ, которая запускается по требованию администратора базы данных, например после реорганизации базы данных. Аналогичное утверждение применимо и к большинству других коммерческих продуктов, в том числе к системе !ХОКЕБ, где соответствующая утилита называется ОРТ1М18ВВВ. Перечислим некоторые из основных статистических показателей базы данных, накапливаемых в СУБД !ЖОКЕЯ.
Замечание. В системе 1)ч(ОКЕЙ индекс рассматривается как частный случай хранимой таблицы. Поэтому приведенные ниже статистические показатели для базовых таблиц и столбцов вычисляются также для индексов. ° Для каждой базовой таблицы фиксируются следующие показатели: ° кардинальность; ° количество первичных страниц для таблицы; ° количество страниц переполнения для таблицы. ° Для каждого столб~!а в каждой базовой таблице фиксируются следующие показатели: ° количество различных значений в столбце; ° максимальное, минимальное и среднее значения для столбца; ° реальные значения в столбце и частота их вхождений.
17.6. Стратегия по принципу "разделяй и властвуй" Как уже упоминалось выше, в конце раздела!7.4, реляционные выражения рекурсивно определяются в терминах подчиненных выражений, что позволяет оптимизатору применять различные стратегии оптимизации по принципу "разделяй и властвуй".
Заметьте, что использование подобных стратегий особенно привлекательно в средах, поддерживающих параллельные вычисления, в частности в распределенных системах, в которых различные части запроса ма~уз вычисляться параллельно на разных процессорах [17.58] — [17.61]. В данном разделе рассматривается одна из подобных стратегий, получившая название декомпозиции запросов. Впервые она была применена в прототипе системы 1ХОКЕЗ [17.36], [17.37]. Замечание. Дополнительную информацию об оптимизации в СУБД 11чОКЕБ (особенно в ее коммерческой версии, которая в данном контексте несколько отличается от прототипа системы ИЧОКЕэ) можно найти в работе Куи (Коо]) и Франкфорта (ГгапИопп) [17.2], а также в [17.38].
Основная идея метода декомпозиции запросов строится на разбиении запроса со многими переменными диапазоназ на последовательность запросов меньшего размера обычно с одной или двумя такими переменными диапазона. Требуемая декомпозиция достигается с помощью методов отделения и подстановки кортежей. З Напалгним, чта язык запросов ЬЗ(1ЕЕ в системе 1КСйЕЗ использует средства реляционного исчисления.
654 Часть [г. Дополнительные аспекты ° Отделение — это процесс удаления из запроса компонента, который имеет только одну общую переменную с оставшейся частью запроса. ° Подстановка кортежа — это процесс подстановки значения одной переменной в запросе (один кортеж за одну операцию). Использование метода отделения всегда предпочтительней использования метода подстановки кортежей во всех случаях, когда существует возможность выбора (см.
пример, приведенный ниже). Тем не менее рано или поздно декомпозиция методом отделения обязательно приведет к разбиению запроса на множество компонентов, которые больше нельзя будет подвергнуть декомпозиции с помощью этого метода, после чего придется обратиться к методу подстановки кортежей. Ниже рассмотрен пример декомпозиции (основанный на примере из (17Э6)).
Словесное выражение э~ого запроса имеет следующий вид; "Определить имена поставщиков из Лондона, поставляющих некоторые красные детали весом менее 25 фунтов в количестве более 200 штук". Приведем формулировку этого запроса на языке О()ЕЬ, на которую далее будем ссылаться, как на формулировку 00. 00: КЕТК1ЕЧЕ ( Я.ЯИАНЕ) ННЕКЕ Я.С1ТУ = 'Ьопбол' ЕИО Я.Б$ = БР.Б$ йИО БР.ЦТУ > 200 ЕИО ЯР.Р$ = Р.Р$ йИО Р.СОЬОК = 'Кед' йИО Р.НЕ1ОНТ < 25 Здесь подразумеваемый диапазон переменных Б, Р и БР распространяется на всю одноименную переменную-отношение. Исходя из последних двух сравнений в выражении запроса можно заключить, что нас интересуют только красные детали весом менее 25 фунтов. Следовательно, можно отделить подзапрос с одной переменной (на самом деле являющийся проекцией выборки), в котором используется переменная Р.
01: КЕТК1ЕЧЕ 1ИТО Р' (Р.Р$) ИНЕКЕ Р.СОЬОК = 'Кеб' йИО Р ИЕ16НТ < 25 Этот запрос с единственной переменной может быть отделен, так как в нем присутствует только одна переменная (а именно — переменная диапазона Р), совместно используемая с оставшейся частью запроса. Так как запрос 01 связывается с остатком исходного запроса по атрибуту Р$ (в условии БР.Р$ = Р.Р$), атрибут Р$ должен входить в "кортеж-прототип" (см. главу 7) отделенного запроса. Другими словами, отделенный запрос предназначен для выборки номеров ~олько тех красных де~алей, которые весят менее 25 фунтов. Отделенный запрос обозначим как запрос 01, результатом выполнения которого является временная переменная-отношение Р'.
(Назначение предложения 1ИТО состоит в том, чтобы создать новую переменную-отношение Р' с единственным атрибутом Р$. Эта переменная-отношение создается автоматически и содержит результат выполнения операции КЕТК1ЕЧЕ.) И наконец заменим ссылки на переменную-отношение Р в сокращенной версии запроса 00 ссылками на переменную-отношение Р'. Эту новую сокращенную версию исходного запроса обозначим как 01. 655 Глава 17.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
