что оптимизатор системы не полностью справляется с задачей преобразования выражений. Повторите этот эксперимент с различными исходными запросами. Если возможно, повторите этот же эксперимент в разных СУБД.

Замечание. Безусловно, разные версии запроса должны давать идентичные результаты. Если же результаты различаются, то, возможно, вы совершили ошибку или ошибка сушествует в оптимизаторе рассматриваемой СУБД. Если обнаружена ошибка в оптимизаторе, сообщите об этом разработчику СУБД!

17.14. Исследуйте любую доступную вам СУБД. Поддерживает ли она какие-либо статистические показатели базы данных (это делают не все СУБД)? И если поддерживает, то какие именно? Как эти статистические показатели обновляются - динамически или с помошью какой-либо утилиты? Если статистические показатели обновляются с помошью утилиты, то как называется утилита и как часто она запускается? Насколько выборочно ее действие (в том смысле, что при запуске утилиты со специфическими параметрами обновляется только определенная статистика)?

17.15. В разделе 17.5 было сказано, что в состав статистических показателей, поддерживаемых СУБД DB2, входят второе наибольшее и второе наименьшее значения каждого столбца в каждой базовой таблице. Почему выбраны именно вторые значения?

17.16.В некоторых коммерческих продуктах пользователю разрешается создавать указатели для оптимизатора. Например, в СУБД DB2 спецификация OPTIMIZE FOR п ROWS в объявлении SQL-курсора означает, что пользователь предполагает извлечь с помощью данного курсора не более п строк (т.е. оператор FETCH будет выполнен для данного курсора не более л раз). Такая спецификация иногда может позволить оптимизатору выбрать более эффективный путь доступа, по крайней мере в случае, когда пользователь действительно выполняет оператор FETCH не более л раз. Оправдано ли, по вашему мнению, применение таких указателей? Обоснуйте свой ответ.

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

Список литературы

Оптимизация представляет собой чрезвычайно большую и постоянно развивающуюся область исследований. Важность этих исследований становится значительнее, чем когда-либо прежде в связи с все возрастающим интересом к системам поддержки принятия решений, речь о которых пойдет в главе 21. Достаточно сказать, что за последние несколько лет около 50% докладов на ежегодных конференциях АСМ SIGMOD в той или иной мере были посвящены именно вопросам оптимизации. Приведенный ниже список представляет собой относительно небольшую выборку из обширной литературы по оптимизации и связанным с ней вопросам. Условно он разбит на следующие фуппы.

В [17.1]-[17.7] содержится обзор общих проблем оптимизации или введение в эту тему.

в [17.8]-[17.17] рассматриваются эффективные методы реализации отдельных реляционных операций, таких как соединение и обобщение.

В [17.18]-[17.33] представлены различные приемы преобразования выражений, описанные в разделе 17.4. В частности в [17.27]-[17.30] рассматриваются семантические преобразования.

В [17.34]-[ 17.45] обсуждаются приемы, использованные в System R, СУБД DB2 и СУБД INGRES, а также общая проблема оптимизации вложенных запросов в стиле языка SQL.

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

Замечание. Публикации, в которых рассматривается оптимизация в распределенных системах, умышленно исключены из данного списка (см. главу 20).

17.1. Kim W., Reiner D.S., Batory D.S. (eds.). Query Processing In Database Systems.- New York, N.Y.: Springer-Verlag, 1985.

Это антология работ, посвященных общим проблемам обработки запросов (не только по оптимизации). Книга состоит из вступительного обозрения Джарка (Jarke), Коха (Koch) и Шмидта (Schmidt), которое перекликается с публикацией [17.3], но не повторяет ее. Далее следуют работы, описывающие обработку запросов в различных контекстах: распределенные базы данных, гетерогенные СУБД, проблемы обновления представлений (работа [9.11] является одной из статей в этом разделе), нетрадиционные приложения (например, CAD/CAM), оптимизация многооператорных запросов [17.49], машины баз данных и физическое проектирование базы данных.

17.2. Special Issue on Query Optimization IEEE Database Eng. - September, 1982. - 5, № 3. Это сборник из 13 коротких статей (академического и коммерческого направлений), в которых описываются различные аспекты оптимизации запросов.

17.3. Jarke М., Koch J. Query Optimization in Database Systems ACM Сотр. Surv. - June, 1984. - 16, №2.

Отличное учебное пособие. Включает обобщенную систему взглядов по проблеме вычисления запросов, подобную представленной в разделе 17.3 данной главы, но базирующуюся на реляционном исчислении, а не на апгебре. После этого в рамках описанной системы взглядов обсуждается множество приемов оптимизации: синтаксические и семантические преобразования, низкоуровневые операции реализации и алгоритмы генерации планов запроса и выбора плана с наименьшей стоимостью. Приводится также обширный набор правил синтаксических преобразований. Имеется достаточно большой список литературы (без аннотаций). Заметьте, однако, что после 1984 года по данной теме было опубликовано на порядок больше работ, чем до 1984 года [17.4].

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

17.4. Graefe G. Query Evaluation Techniques for Large Databases ACM Сотр. Surv. - June, 1993. -25, №2.

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

17.5. PaleiTHO P.P. А Data Base Search Problem J.T. Todd (ed.). Information Systems: COINS IV. - New York, N,Y,: Plenum Press, 1974.

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

Никакой кортеж не может извлекаться дважды.

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

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

Для создания соединений применяется эффективный метод, основанный, во-первых, на динамическом разложении значений, используемых в соединяемых членах (например таких, как S.SI = SP.SI), на полусоединения, которые фактически являются некоторой разновидностью динамически создаваемого вторичного индекса (полусоединения Палермо отличаются от полусоединений, описанных в главе 6), и, во-вторых, на использовании внутреннего представления каждого соединения, называемого косвенным соединением (indirect join), в котором для идентификации кортежей - участников соединения используются внутренние идентификаторы кортежей. Эти методы предназначены для сокращения количества просмотров, необходимых для выполнения соединения, за счет получения гарантии, что соединяемые кортежи каждого члена соединения логически упорядочены в соответствии со значениями атрибутов соединения. Благодаря этому допускается динамическое определение наилучшей последовательности операций доступа к нужным отношениям.

17.6. Gray J. (ed.). The Benchmark Handbook for Database and Transaction Processing Systems (2nd edition). - San Francisco, Calif: Morgan Kaufmann, 1993.

Совет no обработке транзакций (Transaction Processing Council - TPC) является независимой организацией, которая на протяжении ряда лет разработала несколько тестов, фактически принятых в качестве промышленного стандарта. В данной книге содержит-