    Глава 18 

    Оптимизация 

    18.1. Введение 

    Для реляционных систем оптимизация является как проблемой, так и 
возможностью повышения производительности. Проблема оптимизации состоит в том, 
что некоторые системы для достижения определенного уровня производительности 
требуют оптимизации. Оптимизация позволяет улучшить работу системы, так как 
одной из сильных сторон реляционного подхода является то, что первое 
применение оптимизации к реляционному выражению переводит это выражение на 
более эффективный семантический уровень. С другой стороны, в нереляционных 
системах, в которых пользовательские запросы выражаются на более низком 
семантическом уровне, любая "оптимизация" должна выполняться пользователем 
вручную (здесь термин "оптимизация" взят в кавычки, поскольку, как правило, он 
употребляется для обозначения автоматической, а не ручной оптимизации). В 
подобных системах пользователь (а не система) определяет, какие операции 
низкого уровня должны быть выполнены и в какой последовательности. И если 
пользователь принял неправильное реш ение, то система никак не сможет 
исправить положение. (Заметьте также, что для работы в подобных системах 
пользователь должен обладать некоторыми навыками программирования, иначе он не 
сможет достаточно полно использовать эту систему.) Преимущество автоматической 
оптимизации заключается в том, что пользователь может не задумываться над 
наилучшим способом выражения своих запросов (т.е. над тем, как сформулировать 
запрос, чтобы система выполнила его с максимально возможной 
производительностью). Но это далеко не все. Существует реальная возможность, 
что оптимизатор сформулирует запрос лучше, чем программист-пользователь. Для 
подобного утверждения есть ряд причин. Ниже приведены только некоторые из них. 
    1.  Хороший оптимизатор— обратите внимание на слово "хороший"!— обладает 
достаточным количеством информации, которой пользователь может не иметь. 
Точнее, оптимизатор должен обладать некоторыми статистическими данными, такими 
как кардинальное число каждого домена и каждого базового отношения, количество 
различающихся значений для каждого атрибута в отношении, количество вхождений 
каждого значения в атрибутах и т.п. (Такая информация хранится в системном 
каталоге, о чем речь пойдет ниже в этой главе.) Благодаря наличию этих данных 
оптимизатор способен более точно оценивать эффективность любой стратегии 
реализации конкретного запроса. Поэтому оптимизатор сможет выбрать наилучшую 
стратегию реализации запроса. 
    2.  Более того, если с течением времени статистика базы данных значительно 
изменится (например, база данных будет физически реорганизована), то для 
реализации запроса может потребоваться совсем иная стратегия, чем до 
реорганизации; другими словами, может понадобиться повторная оптимизация, или 
реоптими-зация. В реляционных системах процесс реоптимизации достаточно 
тривиален — это просто повторная обработка исходного запроса системным 
оптимизатором. С другой стороны, в нереляционных системах реоптимизация 
требует переписывания программы, и, возможно, вообще не выполнима. 

    474 Часть V. Дополнительные аспекты 

    3.  Оптимизатор — это программа, поэтому он более "настойчив" по сравнению 
с человеком. Оптимизатор вполне способен рассматривать буквально сотни 
различных стратегий реализации данного запроса, в то время как программист 
вряд ли изучает более трех-четырех стратегий (по крайней мере, достаточно глубоко). 
    4.  В оптимизатор встроены знания и опыт "лучших из лучших" программистов, 
что делает эти знания и опыт доступными для всех. Естественно, в противном 
случае широкому кругу пользователей будет предоставлен явно недостаточный 
набор дешевых и неэффективных возможностей. 
    Приведенный список может служить доказательством в поддержку того, что 
оптимизируемость (возможность оптимизации запросов) — является сильной 
стороной реляционных систем. 
    Общее назначение оптимизатора состоит в выборе эффективной стратегии для 
вычисления данного реляционного выражения. В этой главе описаны некоторые 
фундаментальные принципы и приемы, применяемые в процессе оптимизации. Вначале 
предложен обзор работы оптимизатора, обусловленный вступительным примером, 
затем обсуждается важнейший аспект процесса оптимизации — преобразование 
выражений. Потом кратко изложен уже затронутый вопрос о статистиках в базе 
данных. Далее следует описание одного специального подхода к оптимизации, 
известного как декомпозиция запросов. После этого обсуждается вопрос о том, 
как на самом деле реализованы реляционные операторы (например, оператор JOIN). 
Затем кратко описывается использование статистических данных для вычисления 
стоимостных оценок. И наконец, подытоживается весь материал данной главы. 
    Еще одно вводное замечание. Достаточно часто на данную тему ссылаются как 
на оптимизацию запросов. Подобный термин слегка обескураживает, тем не менее, 
поскольку выражение, которое нужно оптимизировать, является запросом, этот 
термин можно иногда употреблять вне сферы интерактивных запросов к базе 
данных: в частности, в контексте операции обновления, а не в контексте самого 
запроса. Более того, сам по себе термин "оптимизация" избыточный, так как не 
существует гарантий, что выбранная стратегия оптимизации действительно 
оптимальна в любом понимании. На практике "оптимизированной" стратегией обычно 
считается та, которая является некоторым улучшением исходной стратегии 
вычисления запроса. (Тем не менее, в ограниченных контекстах можно вполне 
обоснованно утверждать, что выбранная стратегия действительно оптимальна в 
определенном смысле [18.27].) 

    18.2. Вступительный пример 

    Начнем изложение с простого примера, дающего представление о поразительных 
результатах, которые можно получить с помощью оптимизации. Рассмотрим запрос 
"Получить имена поставщиков, которые поставляют деталь Р2". Алгебраическая 
запись этого запроса такова: 
    (   (  SP JOIN S   )   WHERE Pt =   'Р2'   )    [  SNAME  ] 
    Предположим, что база данных содержит информацию о 100 поставщиках и 10000 
партий товаров, только 50 из которых являются партиями с деталями Р2. 
Предположим для простоты, что отношения S и SP представлены на диске как 
"хранимые отношения" (см. главу 4). В таком случае, если система будет 
вычислять выражение прямо (т.е. вообще без оптимизации), то последовательность 
выполняемых действий будет выглядеть так: 
    1. Соединение отношений SP и S (по атрибуту S#). На этом этапе считывается 
информация о 10 000 партий товаров и 10 000 раз считывается информация о 100 
поставщиках (один раз для каждой партии товаров). После этого создается 
промежуточный результат, состоящий из 10 000 соединенных кортежей. 

    Глава 18. Оптимизация	475 

Этот результат записывается на диск (ради примера предположим, что для 
промежуточного результата в основной (оперативной) памяти не хватает места). 
    2.   Выборка кортежей с данными только о детали Р2 из результата, 
полученного на этапе 1. На этом этапе выполняется чтение 10 000 записей 
обратно в оперативную память и создается новое отношение, которое состоит из 
50 кортежей и, по нашему предположению, может поместиться в оперативной памяти. 
    3.  Проекция результата, полученного на этапе 2, по атрибуту SNAME. На 
этом этапе создается требуемый результат (состоящий максимум из 50 кортежей, 
которые могут поместиться в оперативной памяти). 
    Показанная ниже процедура эквивалентна описанной в том смысле, что 
обязательно создаст тот же конечный результат, но более эффективным способом. 
    1.   Выборка кортежей с данными только о детали Р2 из отношения SP. На 
этом этапе выполняется чтение 10000 кортежей и создается результат, состоящий 
только из 50 кортежей, который, как мы предполагали, может поместиться в 
оперативной памяти. 
    2.   Соединение результата, полученного на этапе 1, с отношением S (по 
атрибуту S#). На этом этапе выполняется считывание данных о 100 поставщиках 
(только один раз, а не один раз на одну партию деталей, так как данные обо 
всех партиях деталей Р2 уже находятся в памяти). Результат содержит 50 
кортежей (которые все еще помещаются в память). 
    3.   Проецирование результата, полученного на этапе 2, по атрибуту SNAME 
(аналогично этапу 3 предыдущей последовательности действий). Требуемый 
результат (не более 50 кортежей) помещается в оперативной памяти. 
    Первая из показанных процедур выполняет в общем 1 030 000 операций 
ввода-вывода кортежа, в то время как вторая процедура выполняет только 10 100 
операций ввода-вывода. Следовательно, вполне понятно, что если принять 
"количество операций ввода-вывода кортежа" в качестве меры производительности, 
то вторая процедура в 100 раз эффективнее первой. (На практике мерой 
производительности служит количество операций ввода-вывода страницы, а не 
одного кортежа, но для данного примера эту поправку можно игнорировать.) Кроме 
того, вполне понятно, что пользователи предпочли бы реализовать запрос с 
помощью второй процедуры, а не первой! 
    Таким образом, мы видим, что незначительные изменения в алгоритме 
вычисления (выполнение выборки, а затем соединения, вместо соединения, а затем 
выборки) приводят к значительному увеличению производительности. 
Производительность повысится еще больше, если отношение SP индексировано или 
хешировано по атрибуту Р#. В этом случае количество кортежей, считываемых на 
этапе 1 второй процедуры, уменьшится с 10 000 всего до 50, и полученная 
процедура будет в 7 000 раз эффективнее оригинальной. Аналогично индекс или 
хеш-таблица для атрибута S.S# позволит на этапе 2 уменьшить количество 
операций ввода-вывода кортежей со 100 всего до 50, и процедура вычисления 
запроса станет более чем в 10 000 раз эффективнее своего оригинального 
аналога. Это означает, что если оригинальная процедура вычисления запроса 
выполняется 3 часа, то оптимизированная версия этой процедуры выполнится за 
одну секунду. И конечно, возможны многие другие улучшения. 
    Несмотря на то что приведенный пример достаточно прост, он весьма наглядно 
демонстрирует необходимость оптимизации. Кроме того, этот пример показал типы 
улучшений, которые возможны на практике. В следующем разделе излагается 
систематический подход к проблеме оптимизации. В частности, показано, как 
общая проблема может быть разбита на несколько более или менее независимых 
подчиненных проблем. Приведенный далее обзор создаст удобную среду, в рамках 
которой можно описать и рассмотреть отдельные стратегии и приемы оптимизации, 
обсуждаемые в последующих разделах. 

    476	Часть V. Дополнительные аспекты 


    18.3. Обзор процесса оптимизации 

    Согласно [18.3] рассмотрим четыре стадии процесса оптимизации. 
    1.  Преобразование запроса во внутреннюю форму. 
    2.  Преобразование в каноническую форму. 
    3.  Выбор потенциальных низкоуровневых процедур. 
    4.  Генерация планов вычисления запроса и выбор плана с минимальными затратами. 
    Перейдем к подробному рассмотрению каждой стадии процесса оптимизации. 
    Стадия 1. Преобразование запроса во внутреннюю форму 
    На этой стадии выполняется преобразование запроса в некоторое внутреннее 
представление, более удобное для машинных манипуляций. Это полностью исключает 
из рассмотрения конструкции внешнего уровня (такие как "игра слов" конкретного 
синтаксиса рассматриваемого языка запросов) и готовит почву для последующих 
стадий оптимизации. 
    Возникает очевидный вопрос: "На каком формализме должно базироваться 
внутреннее представление запроса?" Независимо от того, какой формализм выбран, 
он должен быть достаточно полным, чтобы представить все запросы, которые можно 
определить на языке системы. Кроме того, выбранный формализм должен быть 
нейтральным, насколько это возможно, чтобы не предопределять дальнейших 
оптимизационных решений. Обычно внутреннее представление запросов является 
определенной модификацией абстрактного синтаксического дерева, или дерева 
запроса. Например, на рис. 18.1 показано дерево рассматриваемого выше в этой 
главе запроса ("Получить имена поставщиков, которые поставляют деталь Р2"). 

    Окончательный результат 
    t Проекция по атрибуту SNAME 
    t Выборка кортежей, в которых Р# = 'Р2' 
    t Соединение по атрибуту Sit 
    Т	Т 
    SP	s 

    Рис. 18.1. Дерево запроса "Получить имена поставщиков, которые поставляют 
деталь Р2" 

    Предположим, что внутренним представлением является один из формализмов, с 
которыми мы уже познакомились: реляционная алгебра или реляционное исчисление. 
В этом случае дерево запроса, подобное показанному на рис. 18.1, можно 
рассматривать просто как альтернативное кодированное представление некоторого 
выражения в одном из двух формализмов (в реляционной алгебре или в реляционном 
исчислении). Чтобы зафиксировать эти идеи, предположим, что выбранный 
формализм — это реляционная алгебра. Начиная с этого момента, будем считать, 
что внутренним представлением показанного на рис. 18.1 дерева запроса является 
следующее алгебраическое выражение: 
    (   ( SP JOIN S  )   WHERE P# =   'Р2'   )    [  SNAME  ] 
    Стадия 2. Преобразование в каноническую форму 
    На этой стадии оптимизатор выполняет несколько операций оптимизации, 
которые "гарантированно являются хорошими" независимо от реальных данных, 
хранящихся в базе данных, и путей доступа к ним. Суть в том, что все запросы 
(за исключением 

    Глава 18. Оптимизация	477 

    простейших) реляционные языки обычно позволяют выразить несколькими 
разными (по крайней мере внешне) способами. Например, даже простой запрос 
"Получить имена поставщиков, которые поставляют деталь Р2" язык SQL позволяет 
записать буквально дюжиной способов1, не включая тривиальных вариантов, таких 
как замена условий А = В на В = А или условий р то q на q AND p. 
Производительность вычисления запроса не должна зависеть от формы записи 
запроса, которую выбрал пользователь. Поэтому следующий этап в обработке 
запроса — перевод запроса в эквивалентную каноническую форму. Целью этого 
преобразования является исключение внешних различий в эквивалентных 
представлениях2 запроса и, что более важно, поиск представления запроса, в 
некотором смысле более эффективного по сравнению с исходным представлением. 
    Замечание о канонической форме. Понятие канонической формы употребляется 
во многих разделах математики и связанных с ней дисциплин. Каноническая форма 
может быть определена следующим образом. Пусть Q— множество объектов 
(запросов), и пусть существует понятие об эквивалентности этих объектов (а 
именно: запросы ql и q2 эквивалентны тогда и только тогда, когда дают 
идентичные результаты). Говорят, что подмножество С множества Q является 
подмножеством канонических форм для запросов из Q в смысле определенной выше 
эквивалентности тогда и только тогда, когда каждому объекту q из Q 
соответствует только один объект с из С. Тогда говорят, что объект с является 
канонической формой объекта q. Все "интересующие" свойства, которыми обладает 
объект q, также присущи и объекту с. Поэтому, чтобы доказать различные 
"интересующие" результаты, достаточно изучить менее мощное множество объектов 
С, а не более мощное множество Q. 
    Вернемся к основной теме дискуссии. Чтобы преобразовать результаты стадии 
1 в некоторую эквивалентную, но более эффективную форму, оптимизатор 
использует определенные и хорошо известные правила преобразования, или законы. 
Ниже приведен пример таких правил. 
    Выражение 

    ( A JOIN В  )   WHERE выборка-на-А 

    может быть преобразовано в эквивалентное, но более эффективное выражение 

    ( A WHERE выборка-на-А )   JOIN В 

    Такое преобразование кратко рассматривалось в главе 6. Кроме того, это 
преобразование было использовано несколько выше во вступительном примере, 
который ясно показывает, зачем нужны подобные преобразования. 
    Стадия 3. Выбор потенциальных низкоуровневых процедур 
    После преобразования внутренней формы запроса в более подходящую 
(каноническую) форму оптимизатор должен решить, как выполнять запрос, 
представленный в канонической форме. На этой стадии принимается во внимание 
наличие индексов и других путей доступа, распределение хранимых значений 
данных, физическая кластеризация хранимых данных и т.п. Заметьте, что на 
стадиях 1 и 2 этим вопросам совсем не уделялось внимания. 
    Основная стратегия заключается в том, чтобы рассматривать запрос как серию 
низкоуровневых операций (соединения, выборки и т.п.), которые в какой-то мере 
зависимы друг от друга. Ниже показан пример такой зависимости. Код для выполне

    1 Тем не менее, следует заметить, что язык SQL исключительно 
предрасположен к этому. Другие языки (например, алгебра или исчисление) обычно 
не предоставляют возможности создать такое количество эквивалентных по 
результату выражений. Эта излишняя "гибкость" языка SQL на самом деле 
усложняет жизнь разработчикам (а не пользователям), так как это усложняет 
алгоритм оптимизатора. 
    2 В данном случае не следует путать представление запроса (т.е. форму 
записи запроса) и реляционное представление. Здесь термин "представление" 
употребляется как синоним понятия "форма записи". — Прим. ред. 

    478	Часть V. Дополнительные аспекты 

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

    Замечание. С каждой процедурой также связана стоимостная формула, которая 
указывает "стоимость" выполнения процедуры (т.е. уровень требуемых затрат на 
ее выполнение). Обычно стоимость вычисляется в контексте операций ввода-вывода 
с диска, но некоторые системы учитывают также время использования процессора и 
другие факторы. Эти стоимостные формулы используются на стадии 4. В 
[18.4-18.14] обсуждаются и анализируются стоимостные формулы для различных 
процедур реализации при разных исходных предположениях. 

    Следовательно, далее с помощью информации из каталога о состоянии базы 
данных (существующие индексы, кардинальные числа отношений и т.п.) и данных о 
зависимостях, описанных выше, оптимизатор выберет одну или несколько 
процедур-кандидатов для каждой низкоуровневой операции в запросе. Этот процесс 
обычно называют выбором пути доступа. (См. также [18.29, 18.30]. Следует 
отметить, что в этих работах приведенный термин используется для ссылки на 
стадии 3 и 4, определенные в данной главе. Действительно, на практике очень 
трудно разграничить, где заканчивается одна стадия и начинается другая: просто 
стадия 3 плавно переходит в стадию 4.) 
    Стадия 4. Генерация планов вычисления запроса и выбор плана с наименьшей стоимостью 
    На последней стадии процесса оптимизации конструируются потенциальные 
планы запросов, после чего следует выбор лучшего (т.е. наименее дорогого) 
плана выполнения запроса. Каждый план выполнения строится как комбинация 
набора процедур реализации, при этом каждой низкоуровневой операции в запросе 
соответствует одна процедура. Заметьте, что в обычной ситуации для данного 
запроса будет получено множество планов запроса — возможно, даже слишком 
много. На практике, вероятно, не стоит генерировать все возможные планы 
запроса, так как некоторые из них могут быть комбинаторными версиями других 
планов выполнения этого же запроса и процесс выбора наиболее дешевого плана 
может стать чрезмерно дорогостоящим'. Для выбора плана с наименьшей стоимостью 
рекомендуется (возможно, даже необходимо) использовать эвристические алгоритмы 
на достаточно ограниченном наборе планов запросов [18.3]. Понятие "достаточно 
ограниченный набор" обычно используют для уменьшения пространства поиска, так 
как это понятие мо жно рассматривать как уменьшение оптимизатором диапазона 
("пространства") анализируемых ("поиск") возможностей до управляемых пропорций. 
    Для выбора плана с наименьшей стоимостью необходим метод привязки 
стоимости к данному плану. В основном стоимость плана — это просто сумма 
стоимостей отдельных процедур, которые использованы для его выполнения. Таким 
образом, ра

    1 Это не относится (но все еще принимается во внимание) к системам, 
подобным DB2, которые оптимизируют запросы на этапе компиляции, а не во время выполнения. 

    Глава 18. Оптимизация	479 

    бота оптимизатора сводится к вычислению стоимостных формул для каждой 
такой процедуры. Проблема состоит в том, что стоимость выполнения процедуры 
зависит от размера отношения (или отношений), которое выбранная процедура 
обрабатывает. Так как все запросы, за исключением самых простых, требуют 
создания промежуточных результатов в процессе выполнения, оптимизатор должен 
оценить размер промежуточных результатов, чтобы вычислить значения стоимостных 
формул. Следовательно, точная оценка стоимости может быть достаточно сложной 
проблемой. В [18.3] обсуждаются некоторые подходы к решению этой проблемы и 
содержатся ссылки на другие направления исследований. 

    18.4. Преобразование выражений 

    Ниже обсуждаются некоторые правила преобразования, которые можно 
использовать на стадии 2 процесса оптимизации. Разработка примеров и 
выяснение, почему эти правила полезны при оптимизации, оставлены в качестве 
упражнений для читателя. 
    Конечно, читатель должен понимать, что в результате применения к данному 
выражению одного правила преобразования может быть получено выражение, к 
которому применимо другое правило преобразования. Например, среди исходных 
запросов нечасто встречаются такие, которые можно записать с помощью двух 
операций (см. ниже), но в процессе преобразования запроса подобные выражения 
могут возникнуть в результате применения других правил преобразования. 
(Достаточно часто такие выражения появляются в процессе обработки запроса. 
Например, рассмотрим запрос "Получить все города в представлении V", где V 
определено как проекция отношения S по атрибутам S# и CITY.) Другими словами, 
начиная с исходного выражения, оптимизатор будет применять правила 
преобразования до тех пор, пока не будет получено выражение, которое согласно 
встроенным эвристическим правилам является "оптимальным" для рассматриваемого запроса. 

    Выборки и проекции 

    Начнем с правил преобразования, которые затрагивают операции выборки и проекции. 
    1.  Последовательность выборок данного отношения может быть преобразована 
в одну (объединенную операцией AND) выборку этого отношения. Например, выражение 
    ( A WHERE выборка-1 ) WHERE выборка-2 
    эквивалентно выражению 
    A WHERE выборка-1 AND выборка-2 
    2.  В последовательности проекций данного отношения можно игнорировать все 
проекции, кроме последней. Таким образом, выражение 
    ( А [ гроекция-1 ]   )   [ проекция-2 ] эквивалентно выражению 
    А  [ проекция-2 ] 
    Конечно, чтобы первое выражение имело смысл, каждый атрибут, используемый 
в проекции-2, должен присутствовать и в проекции-1. 
    3.  Выборку проекции можно трансформировать в проекцию выборки. Например, выражение 
    ( А  [  проекция ]   )  WHERE выборка 
    эквивалентно выражению 
    ( A WHERE выборка ) [ проекция ] 

    480	Часть V. Дополнительные аспекты 

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

    Распределительный закон 

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

    f ( А О В ) = f  ( А )  О f  ( В ). 

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

    SQRT   (  А *  В )   = SQRT   (  А  )   *  SQRT   (  В ) . 

    Следовательно, в процессе преобразования выражения оптимизатор 
арифметических выражений всегда может заменять одну часть этого равенства на 
другую. Как контрпример утверждается, что операция SQRT не распределяется по 
операции сложения, так как в большинстве случаев квадратный корень суммы А + в 
не равен сумме квадратных корней А и В. 
    В реляционной алгебре операция выборки распределяется по операциям 
объединения, пересечения и вычитания. Операция выборки также распределяется по 
операции соединения, но только тогда, когда условие выборки состоит (в самом 
сложном случае) из объединенных операцией AND двух отдельных условий выборки — 
по одному для каждого операнда операции соединения. Для рассматриваемого выше 
в этой главе примера сформулированное условие соблюдено (условие выборки очень 
простое и относится лишь к одному операнду), и можно использовать 
распределительный закон для замены рассматриваемого в примере выражения его 
более эффективным эквивалентом. Чистый эффект этого закона состоит в том, что 
"можно выполнять раннюю выборку". Выполнение ранней выборки почти всегда себя 
оправдывает, так как приводит к значительному уменьшению количества кортежей, 
которые нужно рассматривать в следующей операции. Кроме того, ранняя выборка 
может привести к уменьшению количества кортежей и на выходе следующей операции. 
    Далее приведено несколько более специфических примеров распределительного 
закона, на этот раз с операцией проекции. Во-первых, операция проекции 
распределяется по операциям объединения и пересечения (но не по операции 
вычитания). Во-вторых, эта операция также распределяется по операции 
соединения, но только в том случае, если в проекцию включены все атрибуты 
соединения. Точнее, выражение 

    ( A JOIN В )   [  проекция ] 

    эквивалентно выражению 

    ( Л [ А-проекщы ]   )   JOIN  (  В [ В-проекция ]   ) 

    тогда и только тогда, когда множество использованных в проекции атрибутов 
равняется объединению множеств атрибутов в А-проекцш и В-проекции и включает 
атрибуты, по которым выполнено соединение. Этот закон можно использовать для 
"выполнения ранних проекций", которые обычно себя оправдывают по тем же 
причинам, что и операции выборки. 

    Глава 18. Оптимизация	481 
    16 Введение в системы баз данных 

    Коммутативность и ассоциативность 

    Законы коммутативности и ассоциативности — это еще два общих правила 
преобразования. Говорят, что бинарная операция О является коммутативной, если 
для всех А и В истинно равенство 

    Л О В = В О Л. 

    Например, в обычной арифметике операции умножения и сложения являются 
коммутативными, а операции деления и вычитания — нет. В реляционной алгебре 
коммутативными являются операции объединения, пересечения и соединения, а 
операции вычитания и деления таковыми не являются. 
    Перейдем к ассоциативности. Принято считать, что бинарная операция О 
является ассоциативной, если для всех А, В и С истинно равенство 

    ДО   (  В О  С }   =   ( А О В )   ОС. 

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

    Идемпотентность 

    Еще одним важным правилом является закон идемпотентности. Идемпотентной 
называют такую бинарную операцию О, для которой для всех А выполняется равенство 

    А О А = А. 

    Можно ожидать, что свойство идемпотентности также может быть полезным в 
процессе трансформации выражений. В реляционной алгебре операции объединения, 
пересечения и соединения являются идемпотентными, а операции деления и 
вычитания — нет. 

    Вычисляемые скалярные выражения 

    Предметом применения законов трансформации являются не только реляционные 
выражения. Например, уже было показано, что некоторые законы трансформации 
применимы и к арифметическим выражениям. Ниже приведен пример. Выражение 

    А * В + А *  С 

    можно трансформировать в выражение 

    А *   (  В + С ) 

    вследствие того, что операция умножения "*" распределяется по операции 
сложения "+". Оптимизатор реляционных выражений должен обладать информацией о 
подобных преобразованиях, так как он учитывает вычисляемые скалярные выражения 
в контексте операций EXTEND и SUMMARIZE. По аналогии следует заметить, что 
данный пример иллюстрирует несколько более общую форму распределительного 
закона. Выше мы определили "распределяемость" в терминах унарной операции, 
распределяемой по бинарной операции. Тем не менее, в данном случае обе 
операции, "*" и "+", являются бинарными. Говорят, что бинарная операция О 
распределяется по бинарной операции U, если для всех А,ВиС истинно равенство 

    А U   (  В  О  С )   =   ( А U В )   О   (A U С) 

    (для приведенного выше арифметического примера замените U на "*", а О на "+"). 

    482	Часть V. Дополнительные аспекты 


    Условия 

    Перейдем к обсуждению условий или выражений, результатами которых могут 
быть истина или ложь. Предположим, что А и В -— атрибуты двух различных 
отношений, тогда условие 

    А > В AND В > 3 

    (которое может быть частью запроса) абсолютно эквивалентно выражению 

    А > В AND В > 3 AND А > 3 

    и потому может быть преобразовано в это выражение. 
    Данная эквивалентность базируется на том, что операция ">" является 
транзитивной. Заметьте, что выполнение подобного преобразования весьма 
полезно, так как позволяет системе создать дополнительную выборку (с помощью 
условия "А > 3") перед выполнением соединения "больше чем", требуемого 
условием "А > В". Повторим сказанное выше. Выполнение ранних выборок в 
основном оправдывает себя, следовательно, оправдает себя и способность системы 
создавать (вводить) ранние выборки (что и реализовано в данном примере). 

    Замечание. Этот прием реализован в различных коммерческих продуктах, 
включая систему DB2, в которой его называют транзитивным замыканием предикатов. 

    А вот другой пример. Условие 

    А > В OR   (   С = D AND Е < F ) 

    можно преобразовать в условие 

    (  А > В OR С = D )   AND   ( А > В OR Е < F ) 

    вследствие того, что операция OR распределяется по операции AND. Этот 
пример демонстрирует другой общий закон: "Любое условие может быть 
преобразовано в эквивалентное условие, называемое конъюнктивной нормальной 
формой (КНФ)." КНФ-выражение имеет вид 

    Cl AND C2 AND   . . .   AND Cn, 

    где CJ, С2, ..., Сп— условия (называемые частичная конъюнкция), в которых 
не используется операция AND. Преимущество КНФ состоит в том, что 
КНФ-выражение истинно, только если истинны все его частичные конъюнкции. 
Аналогично, КНФ-выражение ложно, если ложь является результатом хотя бы одной 
частичной конъюнкции. Так как операция AND коммутативна (A AND В равно В AND 
А), то оптимизатор может вычислять отдельные частичные конъюнкции в любом 
порядке, в частности по возрастанию сложности (сначала простые). И как только 
найдена частичная конъюнкция, результатом которой является ложь, весь процесс 
вычисления КНФ-вы-ражения можно останавливать. 
    Более того, в среде параллельных вычислений возможно параллельное 
вычисление всех частичных конъюнкций. Опять же, как только найдена первая 
частичная конъюнкция, результатом которой является ложь, весь процесс 
вычисления КНФ-выражения можно останавливать. 
    Из сказанного выше следует, что оптимизатор должен "знать", как общие 
свойства, такие как распределяемость, применяются не только к реляционным 
операциям, но и к операциям сравнения, таким как ">", к логическим операциям, 
таким как AND и OR, к арифметическим операциям, таким как "+", и т.п. 

    Семантические преобразования 

    Рассмотрим следующее выражение: 

    ( SP JOIN S   )    [  Р#   ] 

    Данное соединение относится к соединениям типа 
внешниий-к-согласован-пому-потенциальному-ключу. В этом соединении внешнему 
ключу в отношении SP ставится в соответствие потенциальный ключ отношения S. 
Следовательно, кортеж в 

    Глава 18. Оптимизация	483 

отношении SP связан с определенным кортежем в отношении S. Таким образом, 
из каждого кортежа в отношении SP в общий результат поступает только значение 
атрибута Р#. Другими словами, соединение можно не выполнять! Рассматриваемое 
выражение можно заменить выражением 

    SP [ Р# ] 

    Тем не менее, будьте внимательны — данное преобразование применимо только 
в силу семантики (смысла) сложившейся ситуации. В общем, каждый операнд в 
операции соединения вносит в соединение кортежи, которые не обладают 
дополняющими их кортежами в других операндах, поэтому при использовании этого 
преобразования на произвольных отношениях некоторые кортежи не попадут в 
результат. Следовательно, в общем контексте соединения произвольных отношений 
данное преобразование некорректно. Но в рассматриваемом конкретном случае 
каждый кортеж отношения SP должен иметь дополняющий его кортеж в отношении S 
вследствие условия (ограничения) целостности (на самом деле вследствие условия 
корректности ссылок), которое гласит, что каждая партия товаров должна быть 
связана с определенным поставщиком. Следовательно, учитывая сказанное, можно 
утверждать, что в данном случае рассматриваемое преобразование вполне корректно. 
    Преобразование, корректное в силу определенного условия целостности, 
называют семантическим преобразованием [18.23], а оптимизацию, полученную в 
результате подобных преобразований, — семантической оптимизацией. 
Семантическую оптимизацию можно определить как процесс преобразования запроса 
в другой, качественно отличный запрос, который, тем не менее, дает результат, 
идентичный результату исходного запроса, благодаря тому что данные 
удовлетворяют определенному условию целостности. 
    Важно понимать, что в принципе любое условие целостности может быть 
использовано для семантической оптимизации (если это условие не отсрочено и в 
данный момент действует на базу данных). Другими словами, этот прием не 
ограничен использованием только условий целостности. Например, предположим, 
что база данных поставщиков и деталей удовлетворяет условию "Все красные 
детали должны храниться в Лондоне". Рассмотрим запрос: 
    Найти всех поставщиков только красных деталей, которые (поставщики) 
расположены в том же городе, где хранится хотя бы одна деталь, поставляемая 
определенным поставщиком. 
    Это довольно сложный запрос! Но в силу рассмотренного условия целостности 
его можно преобразовать к виду: 
    Найти поставщиков, расположенных в Лондоне и поставляющих только красные детали. 

    Замечание. Многие правила семантических преобразований основаны на знаниях 
о зависимостях и потенциальных ключах [14.7]. 

    Немного современных коммерческих продуктов в должной мере используют идею 
семантической оптимизации. Но в принципе семантическая оптимизация способна 
обеспечивать значительные улучшения производительности, которые могут намного 
превышать полученные с помощью современных более традиционных приемов 
оптимизации. Более подробно идея семантической оптимизации изложена в 
[18.24-18.28] и весьма существенно в [18.23]. 

    Еще одно замечание 

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

    484	Часть V. Дополнительные аспекты 

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

    18.5. Статистики базы данных 

    На стадиях 3 и 4 общего процесса оптимизации (они называются стадиями 
"выбора пути доступа") используются так называемые статистики базы данных, 
которые хранятся в каталоге (ниже кратко описаны способы использования этих 
статистик). В демонстрационных целях ниже кратко рассматриваются (с 
комментариями) некоторые из основных статистик, поддерживаемых двумя 
коммерческими продуктами — DB2 и INGRES. Приведем некоторые основные 
статистики, поддерживаемые системой DB21. 
    •  Для каждой базовой таблицы: 
    • кардинальное число; 
    • количество страниц, занятых этой таблицей; 
    • доля табличного пространства, занимаемого этой таблицей. 
    •  Для каждого столбца каждой базовой таблицы: 
    • количество различных значений в данном столбце; 
    • второе наибольшее значение в данном столбце; 
    • второе наименьшее значение в данном столбце; 
    • десять значений в столбце (только для индексированных столбцов), которые 
чаще всего встречаются, а также количество вхождений каждого из этих значений. 
    •  Для каждого индекса: 
    • индикатор, указывающий, является ли данный индекс "кластеризованным индексом"; 
    • для кластеризованных индексов — доля индексированной таблицы, 
находящейся в кластеризующей последовательности; 
    • количество базовых страниц в данном индексе; 
    • количество уровней в данном индексе. 

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

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

    1 Так как обе названные системы поддерживают стандарт SQL, то в этих 
системах вместо терминов "отношение" и "атрибут" используются термины 
"таблица" и "столбец" соответственно. Также заметьте, что обе системы 
эффективно отображают одну базовую таблицу в одну хранимую. 

    Глава 18. Оптимизация	485 

    •  Для каждой базовой таблицы: 
    • кардинальное число; 
    • количество первичных страниц для данной таблицы; 
    • количество страниц переполнения для данной таблицы. 
    •  Для каждого столбца в каждой базовой таблице: 
    • количество различных значений в данном столбце; 
    • максимальное, минимальное и среднее значение для данного столбца; 
    • реальные значения в этом столбце и частота их вхождений (гистограмма). 

    18.6. Стратегия "разделяй и властвуй" 

    Как уже упоминалось выше в этой главе, реляционные выражения рекурсивно 
определены в контексте подчиненных выражений и это позволяет оптимизатору 
применять различные стратегии типа "разделяй и властвуй". Заметьте, что 
использование подобных стратегий особенно привлекательно в средах параллельных 
вычислений, в частности для распределенных баз данных, где различные части 
запроса могут вычисляться параллельно на разных процессорах. В данном разделе 
рассматривается одна стратегия типа "разделяй и властвуй" — декомпозиция 
запросов, впервые использованная в прототипе системы INGRES [18.31, 18.32]. 

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

    Декомпозиция запросов базируется на разбиении запроса, в результате чего в 
последовательность подчиненных запросов вводится множество 
переменных-кортежей. Подчиненные запросы, в свою очередь, состоят из одной или 
двух подобных переменных. Требуемая декомпозиция достигается с помощью 
отделения и подстановки кортежей. 
    •  Отделение — это процесс удаления из запроса компонента, который имеет 
только одну общую переменную с оставшейся частью запроса. 
    •   Подстановка   кортежа   —   это   процесс   замены   значения   одной  
 переменной-кортежа в запросе (один кортеж за одну операцию). 
    Отделение всегда применяется в ущерб подстановке кортежей, если есть 
возможность выбора (см. пример ниже). Тем не менее, путем отделения в конце 
концов можно разбить запрос (произвести декомпозицию) на множество 
компонентов, которые больше не подлежат декомпозиции посредством отделения, 
после этого в игру вступает подстановка кортежей. 
    Ниже показан единственный пример процесса декомпозиции (базирующийся на 
примере из [18.31]). Рассмотрим запрос: "Получить имена расположенных в 
Лондоне поставщиков, которые поставляют некоторые красные детали весом менее 
25 фунтов, в количестве более 200 штук." Приведем формулировку этого запроса 
на языке QUEL, на которую будем ссылаться как на формулировку QO: 

    QO: RETRIEVE ( S.SNAME) WHERE	S.CITY  =	"London" 
    AND	S.S#    =	SP.S# 
    AND	SP.QTY  >	200 
    AND	SP.P#   =	P.P# 
    AND	P.COLOR =	"Red" 
    AND	P.WEIGHT <	25 

    Здесь переменные-кортежи — это S, P и SP, каждая переменная принимает 
значения кортежей из одноименных отношений. 

    486	Часть V. Дополнительные аспекты 

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

    Dl: RETRIEVE INTO P1 (P.P#) WHERE P.COLOR = "Red" 
    AND  P.WEIGHT < 25 

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

    Ql: RETRIEVE (S.SNAME) WHERE S.CITY = "London" AND  S.S#  = SP.S# AND  
SP.QTY > 200 AND  SP.P# = P'.P# 

    Теперь применим аналогичный прием к запросу Q1, отделяя из него 
однопере-менный запрос, в котором используется переменная SP. Отделенный 
запрос назовем D2, а оставшуюся после отделения часть запроса Q1 назовем Q2. 

    D2: RETRIEVE INTO SP1 (SP.S#, SP.P#) WHERE SP.OJTY > 200 
    Q2: RETRIEVE (S.SNAME) WHERE S.CITY = "London" AND  S.S#  = SP'.S* AND  
SP'.P* = P'.P# 

    После этого аналогично отделим однопеременный запрос с переменной S: 

    D3: RETRIEVE INTO S' (S.S#, S.SNAME) WHERE S.CITY = "London" 
    Q3: RETRIEVE (S'.SNAME) WHERE S'.S# = SP1.S# AND  SP'.P# = P' . P# 

    И наконец, отделим двухпеременный запрос, в котором используются 
переменные SP' и Р': 

    D4: RETRIEVE INTO SP'1 (SP'.Stt) WHERE SP'.P* = P'.Ptt Q4: RETRIEVE 
(S'.SNAME) WHERE S'.Stt = SP" .S# 
    Таким образом, исходный запрос QO разбит на три одновременных запроса, D1, 
D2 и D3 (каждый из которых является проекцией выборки), и два двухпеременных 
запроса, D4 и Q4 (каждый из которых является проекцией соединения). 
Создавшуюся ситуацию можно представить в виде структуры, показанной на рис. 18.2. 

    Окончательный результат 

    Т 
    S' -> Q4	«- SP' ' 
    t	Т 
    D3   Р'	-» D4 <- SP1 
    t    t	t S    Dl         D2 
    t	t 
    P	SP 

    Рис, 18.2. Дерево декомпозиции запроса QO 


    Глава 18. Оптимизация	487 

    Эту схему можно прочитать следующим образом: 
    •  Запросы Dl, D2 и D3 получают на вход отношения Р, SP и S соответственно 
и создают выходные отношения Р', SP' и S' соответственно. 
    •  После этого запрос D4 получает на вход отношения Р' и SP' и создает 
выходное отношение SP". 
    •  И наконец, запрос Q4 получает на вход отношения S и SP" и создает на 
выходе требуемый результат. 
    Заметьте, что запросы Dl, D2 и D3 полностью независимы и их можно 
обрабатывать в любом порядке (предположительно даже параллельно). Более того, 
запросы D3 и D4 также можно обрабатывать в любом порядке после получения 
результатов запросов D1 и D2. Несмотря на это, запросы D4 и Q4 нельзя 
подвергнуть дальнейшей декомпозиции и нужно вычислять с помощью подстановки 
кортежей. В качестве примера рассмотрим запрос Q4. Исходя из обычных пробных 
данных, которые используются в книге, набор номеров поставщиков в атрибуте 
SP".S# будет выглядеть так: {SI, S2, S4}. Каждое из этих значений заменит 
атрибут SP".S#. Таким образом, запрос Q4 примет следующий вид: 

    RETRIEVE   (S'.SNAME)   WHERE S1 .S#	=  "SI" 
    OR        S'.S#	=  "S2" 
    OR        S'.Stt	=  "S4" 

    В [18.31] рассматривается алгоритм разбиения исходного запроса на 
подчиненные и выбор переменной для подстановки кортежей. От этого последнего 
выбора зависит степень оптимизации. Кроме того, в этой работе содержатся 
эвристические алгоритмы выбора оценок стоимости, которые будут управлять 
названным выбором переменной для подстановки кортежей (система INGRES обычно, 
но не всегда, пытается использовать для подстановки переменную отношения, у 
которого меньше кардинальное число). Основная цель процесса оптимизации — 
избежать построения декартовых произведений и поддержать на каждом этапе 
вычислений минимальное количество проверяемых кортежей. 
    В [18.31] не представлены алгоритмы оптимизации однопеременных запросов. 
Тем не менее, информация об этом уровне оптимизации помещена в обзоре системы 
INGRES [8.13]. В основном в системе INGRES для оптимизации однопеременных 
запросов используются функции, подобные аналогичным функциям в других 
системах. Эти функции используют статистические данные, хранящиеся в каталоге, 
и выбирают для просмотра отношения конкретный путь доступа (например, индекс 
или хеш-таблицу). 
    В [18.32] рассматриваются некоторые экспериментальные доказательства— 
измерения производительности вычисления эталонного набора тестов, которые 
позволяют сделать вывод, что описанные приемы оптимизации производят хорошее 
впечатление и достаточно эффективны на практике. Ниже приведены некоторые 
выводы из этой работы. 
    1.  Отделение — это лучшее, что можно сделать на первом этапе оптимизации. 
    2.  Если на первом этапе нужно выполнять подстановку кортежей, то лучше 
всего выбрать переменную-кортеж, по которому выполняется соединение. 
    3.   Если к одной из переменных в двухпеременном запросе применялась 
подстановка кортежей, то наилучшая тактика— построение "на лету" индекса или 
хеш-таблицы (если это еще не сделано) для атрибута другого отношения, по 
которому выполняется соединение. Система INGRES часто применяет эту тактику. 

    488	Часть V. Дополнительные аспекты 


    18.7. Реализация реляционных операторов 

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

    Замечание. Некоторые более сложные приемы реализации описаны в отдельных 
работах, ссылки на которые приведены в конце главы. 

    Далее рассматриваются проекция, соединение и агрегация. В данном случае 
под "агрегацией" будем понимать одну из агрегативных функций (COUNT, SUM, MAX 
и т.п.). Существует два основных типа агрегации: 
    1.  Агрегация без атрибутов. 
    2.  Агрегация, как минимум, с одним атрибутом. 
    Первый случай достаточно прост. Как правило, в этом случае выполняется 
просмотр всего отношения, по которому вычисляется агрегативная функция. 
Единственным исключением является индексированный атрибут. В этом случае 
значение агре-гативной функции вычисляется исключительно по индексу, без 
доступа собственно к отношению [18.30]. Например, запрос 

    SUMMARIZE SP BY ( ) ADD AVG ( QTY ) AS AQ 

    можно вычислить, просмотрев индекс QTY (предполагается, что такой индекс 
существует) и вовсе не касаясь отношения SP. Аналогичные соображения применимы 
и для функций COUNT или зим (для функции COUNT подойдет любой индекс 
отношения). Что касается функций МАХ и MIN, то их результат можно получить за 
одну операцию чтения последней (для функции МАХ) или первой (для функции MIN) 
позиции индекса (здесь вновь предполагается, что индекс для соответствующего 
атрибута уже существует). 
    Далее в этом разделе рассматривается агрегация только второго типа (т.е. 
агрегация хотя бы с одним атрибутом). Ниже показан пример операции агрегации 
второго типа: 

    SUMMARIZE SP BY   (  Р#  )   ADD SUM  ( OTY )   AS TOTQTY 

    С точки зрения пользователя, проекция, соединение и агрегация второго 
типа, конечно, абсолютно не похожи друг на друга. Но с точки зрения реализации 
они имеют некоторые сходства, так как в каждом из случаев система должна 
сгруппировать кортежи на основе значений некоторых атрибутов или комбинаций 
атрибутов. В случае проекции подобная группировка позволяет системе исключить 
дублирующиеся кортежи, в случае соединения — найти соответствующие кортежи, а 
в случае агрегации — вычислить отдельные (например, по группам) агрегативные 
значения. Существует несколько методов подобной группировки. 
    1.  Прямой метод. 
    2.  Поиск по индексу. 
    3.  Поиск по хеш-таблице. 
    4.  Слияние. 
    5.  Хеширование. 
    6.  Комбинация названных методов. 
    На рис. 18.3-18.7 показаны псевдокоды процедур реализации перечисленных 
методов для соединения (проекция и агрегация оставлены в качестве упражнения 
для пользователя). На этих рисунках используются следующие соглашения. Прежде 
всего, R и S— это хранимые отношения, которые должны быть соединены, а С— это 
общий атрибут (возможно, составной) этих отношений. Предполагается, что 
возможен последо-

    Глава 18. Оптимизация	489 

вательный доступ к кортежам обоих отношений R и 5 по одному за одну 
операцию. Эти кортежи в последовательности доступа будут обозначаться R[l], 
Щ2], ..., R[m] и 5[1], 5[2],..., S[n] соответственно. Для соединенного 
кортежа, составленного из кортежей R[i] и ?[/], будет использоваться 
обозначение R[i] * S[/]. И наконец, отношение R будем считать внешним, а 
отношение S— внутренним, как показано на рис. 18.3. 

    Прямой метод 

    Прямой метод (его можно также назвать "плоским") — это метод, согласно 
которому рассматриваются все возможные кортежи (т.е. каждый кортеж отношения R 
в сочетании с каждым кортежем отношения S, как показано на рис. 18.3). 

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

    т 
    	do i := 1 to т ;	/* внешний цикл   */ 
		do j := 1 to n ;  /* внутренний цикл */ 
			if ft[i] .C = S[j] .C then    к результату добавить соединенный кортеж 
				R[i] * 5[j] ; 
		end ; 
	end ; 

    Рис. 18.3. Прямой метод 

    Давайте проанализируем стоимость прямого метода. Этот подход требует всего 
я * т операций чтения кортежа. А как насчет операций записи кортежа? Каково 
кардинальное число соединенного результата? (Количество операций записи 
кортежа будет равным кардинальному числу результата, если последний нужно 
записать на диск.) 
    •   В частном, достаточно важном, случае соединения многие-к-одному 
(например, соединение типа внешний-к-согласованному-потенциальному-ключу) 
кардинальное число результата точно совпадает (в большинстве случаев) с 
величиной т или п в зависимости от того, какое из отношений, R или S, 
представлено на стороне "многие" рассматриваемого соединения. 
    •  Теперь рассмотрим более общий случай соединения многие-ко-многим. Пусть 
dCR — количество различающихся значений атрибута С отношения R, по которому 
выполняется соединение, a dCS определено аналогично на отношении S. Если 
предположить, что значения распределены равномерно (данное значение атрибута С 
может встречаться с той же вероятностью, что и другие значения), то для 
данного кортежа из R существует n/dCS кортежей в отношении S со значением 
атрибута С, равным значению этого атрибута в рассматриваемом кортеже из 
отношения R. Таким образом, общее количество кортежей в соединении (т.е. 
кардинальное число результата) будет равно (т * n)/dCS. Или если повторить 
изложенные рассуждения, начав с кортежа в отношении S, то кардинальное число 
результата составит (п * m)/dCR. Следовательно, две оценки не будут совпадать 
при выполнении условия dCS * dCR, т.е. в отношении R существуют значения, 
которые не встречаются в S и наоборот. В этом случае нужно использовать 
меньшую из оценок. 
    Конечно, как упоминалось ранее, на практике учитывают операции 
ввода-вывода страниц, а не кортежей. Поэтому предположим, что в отношениях R и 
S на странице помещается соответственно pR и pS кортежей (следовательно, 
отношения занимают соответственно m/pR и n/pS страниц). Поэтому легко увидеть, 
что процедура, псевдокод которой показан на рис. 18.3, выполнит (m/pR) + 
(m*ri)/pS операций чтения страницы. С другой стороны, если поменять роли 
отношений R и S (отношение S считать внешним, а R — внутренним), то количество 
операций чтения страницы составит (n/pS) + (n*m)/pR. 

    490	Часть V. Дополнительные аспекты 

    Для примера предположим, что т = 100, п = 10 000, pR = 1 и pS = 10. Тогда 
результатами последних двух формул будут 100 100 и 1 001 000 операций чтения 
страницы соответственно. 

    Заключение. В описанном подходе в качестве внешнего желательно 
использовать меньшее отношение (в данном случае понятие "меньшее" относится к 
количеству страниц). 

    Краткое обсуждение прямого метода завершим замечанием, что этот прием 
является наихудшим выбором процедуры. В этом методе предполагается, что 
отношение S не обладает ни индексами, ни хеш-таблицами для атрибута С, по 
которому выполняется соединение. Эксперименты, проведенные Биттоном (Bitton) 
[18.12], показали, что если предполагаемая ситуация (отсутствие индексов и 
хеш-таблиц) действительно имеет место, то методы обработки можно улучшить, 
построив нужный индекс или хеш-таблицу динамически и продолжив обработку с 
помощью методов поиска по индексу или хеш-таблице (см. ниже). Эта идея 
поддерживается и в [18.32]. 

    Поиск по индексу 

    Теперь рассмотрим ситуацию, в которой для атрибута S. С внутреннего 
отношения S существует индекс X(рис. 18.4). Преимущество этого метода по 
сравнению с прямым состоит в том, что для данного кортежа из внешнего 
отношения R можно переходить "прямо" (благодаря индексу X) к соответствующему 
кортежу во внутреннем отношении S. Общее количество операций чтения кортежа из 
отношений R и S будет равно кардинальному числу результата соединения (см. 
прямой метод выше). Общее количество операций чтения страницы для отношений R 
и S составит (т/рК) + (mn/dCS) при наихудшем предположении, что каждая 
операция чтения кортежа из отношения S требует обращения к отдельной странице. 

    /* использование индекса X по атрибуту S.C */ 
    do 2 := 1 to т ;	/* внешний цикл          */ 
    /* пусть для значения индексированного атрибута Л[^].С        */ 
    /* существует k вхождений индекса: Х[1], ..., X[k]	*/ 
    do j := 1 to k ;	/* внутренний никл       */ 
    /* пусть 5[j] - кортеж из 5, на который указывает индекс X[j] */ 
    к результату добавить соединенный кортеж R[i] * S[j] ; end ; end ; 

    Рис. 18.4. Поиск по индексу 

    Если кортежи отношения S хранятся в порядке значений соединяющего атрибута 
С, то количество операций чтения страницы уменьшится до значения (m/pR) + 
(mn/dCS)/pS. Воспользовавшись теми же пробными значениями, что и выше (от = 
100, п= 10000, pR = 1, pS= 10), и предположив, что dCS= 100, получим значения 
двух последних формул: 10 100 и 200 соответственно. Разница между полученными 
значениями подтверждает, что кортежи хранимых отношений полезно содержать в 
удобной последовательности. 
    Но в вычислениях следует учесть дополнительные расходы производительности, 
внесенные операциями чтения индекса. Наихудшим является предположение, что для 
поиска соответствующего кортежа в отношении S каждому кортежу в отношении R 
требуется "неожиданный" поиск по индексу, который приведет к чтению страницы 
для каждого уровня индекса. Для индекса, обладающего / уровнями, операция 
поиска добавит к общему количеству операций чтения страницы еще т*1 операций. 
На практике значение / составляет 3 или меньше (более того, весьма вероятно, 
что верхний уровень индекса находится в памяти на протяжении всей обработки, и 
это значительно уменьшает количество операций чтения страницы). 

    Глава 18. Оптимизация	491 


    Поиск по хеш-таблице 

    Поиск по хеш-таблице аналогичен поиску по индексу за исключением того, что 
в качестве "быстрого пути доступа" к атрибуту S. С внутреннего отношения S 
вместо индекса используется хеш-таблица (рис. 18.5). Вывод оценок стоимости 
для данного метода оставлен в качестве упражнения для пользователя. 

    f 
    /* использование хеш-таблииь: Н по атрибуту S.C */ 
    /* внешний цикл 
    / 
    do i := 1 to m ; 
    k := hash (ft[j.] .Q 
    /* пусть для H[k] имеется h соответствукших кортежей из S  */ do j: := 1 
to Л ;	/* внутренний цикл   */ if Я[2] .С = S[j] .С then 
    к результату добавить соединенный кортеж R[i] * S[j] ; end ; end ; 

    Рис. 18.5. Поиск по хеш-таблице 


    Слияние 

    Метод слияния предполагает, что кортежи отношений R и S хранятся в 
последовательности значений атрибута С, по которому выполняется соединение. 
Если данное предположение имеет место, то два отношения можно просматривать в 
физической последовательности, обе операции просмотра можно синхронизировать и 
все соединение может быть выполнено за один проход по данным (рис. 18.6). 

    /*	Кортежи обоих отношений, Я и S, хранятся в последовательности	*/ 
    /*	значений атрибута С.	*/ 
    /*	Здесь приведен код для соединения типа многие-ко-многим,	*/ 
    /*	пример для соединения многие-к-одному оставлен для упражнения	*/ 
    г := 1 ; s := 1 ; do while r < т and s < п ;	/* внешний цикл */ 
    v := Я[г] .С ; 
    do j  := s by 1 while S[j] .C<  v ; 
    end ; 
    s := j ; 
    do j := s by 1 while S[j].C = v ; /* внутренний цикл */ 
	do i := r by 1 while R[i] .C = v ; 
    к результату добавить соединенный кортеж R[i] * S[j] ; end ; 
    end ; 
    s := j ; 
    do J. := r by 1 while Л[^] .С = v ; 
    end ; 
    r := -i ; end ; 

    Рис. 18.6. Слияние (для соединений типа многие-ко-многим) 

    Без сомнений, подобные методы оптимальны, так как каждая страница 
считывается один раз (по крайней мере, это утверждение истинно для соединений 
типа один-ко-многим и не всегда истинно для соединений типа многие-ко-многим). 
Другими словами, количество операций чтения страницы составит (т/рК) + (n/pS). 
Из этого следует: 

    492 Часть V. Дополнительные аспекты 

    •   Физическая кластеризация логически связанных данных является одним из 
важнейших факторов, влияющих на производительность, т.е. в высшей степени 
желательно провести кластеризацию данных так, чтобы они соответствовали 
наиболее важным для предприятия соединениям [18.6]. 
    •  Если подобная кластеризация отсутствует, то хорошей идеей может быть 
сортировка какого-либо одного или обоих отношений во время выполнения и 
слияние соединения произвольным способом (конечно, подобная сортировка создает 
нужную кластеризацию динамически). Для ссылки на этот метод используют термин 
(логически достаточный) сортировка-слияние [18.7]. 
    Более подробно эта тема обсуждается в [18.30]. 

    Хеширование 

    Как и слияние, метод хеширования требует одного прохода для каждого из 
двух отношений (рис. 18.7). В результате первого прохода строится хеш-таблица 
для значений атрибута S.С из отношения S. Записи в этой таблице содержат: 
значение соединяемого атрибута, возможно, другие значения атрибутов отношения 
S и указатель на соответствующий кортеж. Во время второго прохода сканируются 
кортежи отношения R и применяется та же самая хеш-функция для соединяемого 
атрибута R.C. Когда кортеж из отношения R сталкивается в хеш-таблице с одним 
или несколькими кортежами из отношения S, то алгоритм проверяет, действительно 
ли равны значения Л.С и S.C, и если это так, то генерируется соответствующий 
кортеж (кортежи) соединения. Основным преимуществом данного метода по 
сравнению с методом слияния является то, что отношения R и S можно хранить в 
произвольной последовательности, а значит, можно не сортировать. 

    /* построение хеш-таблицы И по атрибуту S. С */ 
    do j := 1 to л ;	/* внешний цикл     */ 
    k := hash (S[j} .Q 
    I* добавить для S[j] запись в таблицу H[k] */ end ; 
    /* теперь выполняйте поиск по хеш-таблице на R *I 

    Рис. 18.7. Хеширование 

    Как и в случае метода поиска по хеш-таблице, вывод стоимостных формул для 
хеширования оставлен в качестве упражнения для читателя. 

    18.8. Резюме 

    Эта глава начинается с утверждения, что для реляционных систем оптимизация 
является как проблемой, так и возможностью повышения производительности. 
Фактически оптимизация является сильной стороной таких систем по целому ряду 
причин. Реляционная система с хорошим оптимизатором будет функционировать 
намного лучше, чем нереляционная. Вступительный пример дал представление о 
поразительных результатах, которых можно достичь (в некоторых случаях 
производительность во время выполнения запроса сокращается в соотношении 10 
000:1). Существует четыре общих стадии процесса оптимизации. 
    •   Выражение запроса во внутренней форме (обычно это дерево запроса или 
абстрактное синтаксическое дерево, но такие представления можно рассматривать 
как приспособленную для внутренних задач форму реляционной алгебры). 

    Глава 18. Оптимизация	493 

    •   Преобразование в каноническую форму с помощью различных законов преобразования. 
    •  Выбор потенциальных низкоуровневых процедур для реализации различных 
операторов в каноническом представлении запроса. 
    •   Генерация планов запроса и выбор плана с наименьшей стоимостью с 
помощью стоимостных формул и статистик базы данных. 
    Далее обсуждались общие законы распределения, коммутативности и 
ассоциативности и их применение к реляционным операторам, таким как 
соединение. Кроме того, рассматривалось применение этих законов к 
арифметическим и логическим операторам, а также к операторам сравнения. 
Затрагивая и другой общий закон — идемпотентность. Обсуждались некоторые 
специальные преобразования операторов проекции и выборки. После этого была 
представлена идея семантической оптимизации, т.е. преобразования запросов, 
которое базируется на "знании" системой условий целостности. 
    В демонстрационных целях был сделан беглый очерк статистик баз данных, 
поддерживаемых системами DB2 и INGRES. После чего обсуждалась одна из 
стратегий типа "разделяй и властвуй" — декомпозиция запросов, впервые 
представленная в прототипе системы INGRES. Было также отмечено, что стратегии 
типа "разделяй и властвуй" весьма привлекательны для сред параллельных 
вычислений и распределенных сред. 
    И наконец, рассматривались некоторые методы реализации отдельных 
реляционных операторов, в частности оператора соединения. В этой главе 
представлен псевдокод алгоритмов для пяти методов соединения: прямого метода, 
поиска по индексу, поиска по хеш-таблице, слияния и хеширования. Также кратко 
рассматривались стоимостные характеристики описанных методов. 
    В заключение хотелось бы отметить, что, к сожалению, многие современные 
программные продукты содержат некоторые замедлители оптимизации, о которых 
пользователь должен, по крайней мере, знать (даже если с этим нельзя ничего 
поделать). Замедлитель оптимизации — это свойство определенной системы, не 
позволяющее оптимизатору выполнить свою работу так, как она могла быть 
выполнена (например, при отсутствии данного свойства). К замедлителям 
оптимизации можно, например, отнести возможность вставки в таблицу 
дублирующихся записей [4.11] и трехзначную логику (об этом в следующих главах книги). 

    Упражнения 

    18.1. Некоторые пары выражений в контексте базы данных поставщиков, 
деталей и проектов эквивалентны, некоторые — нет. Какие пары выражений 
действительно эквивалентны? 

    al) S JOIN ( ( P JOIN J } WHERE CITY = 'London' a2) ( P WHERE CITY = 
'London' ) JOIN ( J JOIN S ) 

    61) ( S MINUS ( ( S JOIN SPJ ) WHERE P# = 'P2' ) 
    [ S#, SNAME, STATUS, CITY ] ) [ S#, CITY ] 
    62) S [ S#, CITY ] MINUS 
    { S [ S#, CITY ] JOIN 
    ( SPJ WHERE P# = 'P2' ) ) [ S#, CITY ] Bl) ( S [ CITY ] MINUS P [ CITY ] ) 
MINUS J [ CITY ] B2) { S [ CITY ] MINUS J [ CITY ] ) 
    MINUS ( P [ CITY ] MINUS J [ CITY ] ) rl) ( J [ CITY ] INTERSECT P [ CITY 
] ) UNION ( S [ CITY ] ) 

    494	Часть V. Дополнительные аспекты 

    Г2) J [CITY ] INTERSECT ( S [ CITY ] UNION P [ CITY ] ) 
    Д1) ( ( SPJ WHERE S# = 'SI' ) UNION ( SPJ WHERE P# = 'PI' ) ) 
    INTERSECT  ( ( SPJ WHERE J# = 'Jl1 ) UNION ( SPJ WHERE S# = 'SI' } ) Д2) { SPJ WHERE 
S# = 'SI' ) 
	UNION   ( ( SPJ WHERE P# = 'PI' ) INTERSECT ( SPJ WHERE J# = 'Jl' ) ) el) ( S 
WHERE CITY = 'London' ) UNION ( S WHERE STATUS > 10 ) e2) S WHERE CITY = 
'London' AND STATUS > 10 Ж1) ( S [ S# ] INTERSECT ( SPJ WHERE J# = 'Jl' ) [ S# 
] ) 
    UNION ( S WHERE CITY = 'London' ) [ S# ] 
    Ж2) S [ S# ] INTERSECT ( ( SPJ WHERE J# = ' Jl' ) [ S# ] ) UNION ( S WHERE 
CITY = 'London' ) [ S# ] ) 

    31) ( SPJ WHERE J# = 'Jl' ) [ S# ] 
    MINUS ( SPJ WHERE P# = 'PI' ) [ S# ] 

    32) ( ( SPJ WHERE J# = 'Jl' ) 
    MINUS ( SPJ WHERE P# = 'PI' ) ) [ S# ] 

    18.2. Докажите, что соединение, объединение и пересечение являются 
коммутативными, а вычитание — нет. 
    18.3. Докажите, что соединение, объединение и пересечение являются 
ассоциативными, а вычитание — нет. 
    18.4. Докажите, что: а) объединение распределяется по пересечению; б) 
пересечение распределяется по объединению. 
    18.5. Докажите, что для всех А и В: a) A UNION ( A INTERSECT В) = А; б) A 
INTERSECT ( A UNION В ) = А. Замечание. Этот закон называется законом 
поглощения. Как и законы идемпотентности, коммутативности и т.д., этот закон 
может быть полезен в процессе оптимизации. 
    18.6. Докажите, что: а) выборка безусловно распределяема по объединению, 
пересечению и вычитанию и условно распределяема по соединению; б) проекция 
безусловно распределяема по объединению и пересечению, условно распределяема 
по соединению и нераспределяема по вычитанию. Запишите соответствующие 
критерии для условной распределяемости. 
    18.7. Распространите правила преобразования, изложенные в разделе 18.4, 
так, чтобы учитывались операторы EXTEND и SUMMARIZE. 
    18.8. Можно ли сформулировать какие-либо полезные правила преобразований 
для операции деления? 
    18.9. Запишите соответствующий набор правил преобразования для условий, в 
которых используются операторы AND, OR и NOT. Примером таких правил может 
служить "закон коммутативности для оператора AND", т.е. выражение A AND В 
тождественно выражению б AND Л. 
    18.10. Распространите ответ на предыдущее упражнение, включив в сферу его 
действия условия, в которых используются кванторы EXISTS и FORALL. Примером 
может служить правило, изложенное в главе 7 и позволяющее преобразовать 
выражения, которые используют квантор FORALL, в выражения с отрицаемым 
квантором EXISTS. 

    Глава 18, Оптимизация	495 

    18.11. Ниже приведен список условий целостности для базы данных 
поставщиков, деталей и проектов. 
    • Допустимыми городами являются Лондон (London), Париж (Paris), Рим 
(Rome), Афины (Athens), Осло (Oslo), Стокгольм (Stockholm), Мадрид (Madrid) и 
Амстердам (Amsterdam). 
    • Никакие два проекта не могут быть размещены в одном и том же городе. 
    • В любой момент времени в Афинах может находиться не более одного поставщика. 
    • Ни одна поставка по количеству не может превышать удвоенное среднее 
значение количества для всех поставок. 
    • Поставщик с наибольшим статусом не может находиться в одном городе с 
поставщиком с наименьшим статусом. 
    • Каждый проект должен находиться в городе, в котором есть хотя бы один 
поставщик этого проекта. 
    • Должна существовать по крайней мере одна красная деталь. 
    • Среднее значение статуса поставщика должно быть больше 15. 
    • Каждый поставщик из Лондона должен поставлять товар Р2. 
    • Хотя бы одна красная деталь должна весить меньше 50 фунтов. 
    • Лондонские поставщики поставляют больше различных видов деталей, чем парижские. 
    • Лондонские поставщики поставляют больше деталей (по общему количеству), 
чем парижские. 
    Ниже перечислены простые запросы к этой базе данных: 
    а) получить поставщиков, которые не поставляют деталь Р2; 
    б) получить всех парижских поставщиков, которые поставляют детали для всех 
проектов в Афинах, использующих все детали из Хельсинки; 
    в) получить таких поставщиков, для которых не существует других 
поставщиков, которые поставляют меньше различных видов деталей; 
    г) получить лондонских поставщиков, которые поставляют детали для 
некоторых проектов в Афинах, использующих все детали из Хельсинки; 
    д) получить поставщиков, размещенных в Осло и поставляющих хотя бы два 
различных вида деталей, хранящихся в Париже и использующихся по крайней мере в 
двух различных проектах в Стокгольме; 
    е) получить пары поставщиков, размещенных в одном городе и поставляющих 
пары деталей, которые хранятся в одном городе; 
    ж) получить поставщиков, расположенных в Лондоне и поставляющих для 
некоторых проектов в Афинах некоторые детали, хранящиеся в Хельсинки; 
    з) получить пары поставщиков, размещенных в одном городе и поставляющих 
детали парам размещенных в одном городе проектов; 
    к) получить детали, поставляемые хотя бы для одного проекта только 
поставщиком, размещенным не в том городе, где находится этот проект; 
    л) получить таких поставщиков, что не существует других поставщиков, 
которые поставляют больше различных видов деталей. 
    Используйте условия целостности для преобразования данных запросов в более 
простую форму (все еще на обычном языке; от вас не требуется формально 
выполнять это упражнение). 

    496	Часть V. Дополнительные аспекты 

    18.12. Исследуйте доступную вам СУБД. Выполняет ли эта система 
преобразование выражений (это делают не все СУБД)? Если это так, то какие 
выполняются преобразования? 
    18.13. Попробуйте провести следующий эксперимент. Возьмите простой запрос, 
например: "Получить имена поставщиков, которые поставляют деталь Р2", и 
запишите этот запрос всеми известными вам способами с помощью любого 
доступного языка запросов (возможно, это будет язык SQL). Создайте и заполните 
данными подходящую базу данных, запустите все версии запроса и измерьте время 
выполнения каждой версии. Если полученные значения сильно различаются, то вы 
получили экспериментальное доказательство того, что оптимизатор системы не 
вполне справляется с задачей преобразования выражений. Повторите эксперимент с 
различными исходными запросами. Если возможно, проведите этот же эксперимент в 
разных СУБД. 

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

    18.14. Исследуйте любую доступную вам СУБД. Поддерживает ли эта система 
какие-либо статистики баз данных (это делают не все СУБД) и если да, то какие? 
Как эти статистики обновляются — динамически или с помощью какой-то утилиты? 
Если статистики обновляются с помощью утилиты, то как называется утилита и как 
часто она запускается? Насколько выборочно она действует (в том смысле, что 
при определенном запуске утилитой обновляется определенная статистика)? 
    18.15. В этой главе было показано, что в состав статистик, поддерживаемых 
системой DB2, входят второе наибольшее и второе наименьшее значения каждого 
столбца в каждой базовой таблице. Почему выбраны именно вторые значения? 
    18.16. Разработайте набор процедур реализации для операций выборки и 
проекции (руководствуясь показанным в разделе 18.7 псевдокодом процедур для 
операции соединения). Выведите соответствующий набор стоимостных формул для 
этих процедур, предположив, что в данном случае нас интересует только 
количество операций ввода-вывода, т.е. не пытайтесь учесть стоимость загрузки 
процессора и других компонентов системы в ваших формулах. Запишите и 
подтвердите остальные предположения, сделанные в процессе вывода формул. 

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

    Приведенный ниже список представляет относительно небольшую выборку из 
многочисленных работ по оптимизации и связанным с ней вопросам. Этот список 
условно разбит на группы. Работы [18.1—18.3] содержат обзор общей проблемы 
оптимизации или введение в эту проблему. В [18.4-18.14] рассматриваются 
эффективные методы реализации отдельных реляционных операций, таких как 
соединение или агрегация. В [18.15-18.28] представлены различные приемы 
преобразования выражений, описанных в этой главе, в частности в [18.23-18.28] 
рассматриваются семантические преобразования. В [18.29-18.39] обсуждаются 
приемы, использующиеся в системах System R, DB2 и INGRES, а также общая 
проблема оптимизации вложенных запросов в стиле языка SQL (см. главу 8). 
Работы [18.40-18.49] содержат описания различных приемов, хитростей и идей, 
направления исследований в будущем и т.п. Работа [18.50] —это новый (и весьма 
обширный) учебник. 

    Глава 18. Оптимизация	497 


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

    18.1. Kirn  W.,  Reiner D.S.,  Batory  D.S.  (eds.).  Query  Processing  
In  Database Systems. —New York, N.Y.: Springer-Verlag, 1985. 
    Это антология работ, посвященных общим проблемам обработки запросов (не 
только по оптимизации). Книга состоит из вступительного обозрения Джарка 
(Jarke), Коха (Koch) и Шмидта (Schmidt), которое перекликается, но не 
повторяет публикацию [18.3]; за ним следуют работы, описывающие обработку 
запросов в различных контекстах: распределенные базы данных, гетерогенные 
СУБД, обновление запросов; обсуждается проблема обработки запросов, 
нетрадиционные приложения (например, CAD/CAM), физическое проектирование базы 
данных и др. 
    18.2. Special Issue on Query Optimization // IEEE Database Eng. — 1982. — 
5, № 3. 
    Содержит 13 коротких работ (академического и коммерческого направления), в 
которых описываются различные аспекты оптимизации запросов. 
    18.3. Jarke M., Koch J. Query Optimization in Database Systems // ACM 
Сотр. Surv. — 1984. — 16, №2. 
    Отличное учебное пособие. Представляет общую среду для вычисления 
запросов, подобную среде, представленной в данной главе (написанной во многом 
под влиянием этой работы), но базирующуюся на реляционном исчислении, а не на 
алгебре. После этого в рамках описанной среды обсуждается множество приемов 
оптимизации: синтаксические и семантические преобразования, низкоуровневые 
операции реализации и алгоритмы генерации планов запроса и выбора плана с 
наименьшей стоимостью. Приведен также обширный набор правил синтаксических 
преобразований. Представлен достаточно большой список литературы (без 
аннотаций). Заметьте, что после 1984 года по данной теме было опубликовано на 
порядок больше работ, чем до 1984 года. 
    В работе также кратко обсуждаются другие смежные проблемы, такие как 
оптимизация высокоуровневых языков запросов (например, более мощные по 
сравнению с алгеброй или исчислением языки) и оптимизация в распределенных 
базах данных. 
    18.4. Bing Yao S. Optimization of Query Evaluation Algorithms // ACM 
TODS.— 1979. —4, №2. 
    В работе представлена общая модель вычисления запроса, которая включает 
известные алгоритмы как частный случай. Эта модель содержит перечисленные 
низкоуровневые операции и соответствующие наборы стоимостных формул. 
    1.  Индексирование выборок. 
    2.  Индексирование соединений. 
    3.  Пересечение. 
    4.  Доступ к записям. 
    5.  Последовательный просмотр. 
    6.  Связной просмотр. 
    7.  Фильтрация выборки. 
    8.  Фильтрация соединения. 
    9.  Сортировка. 
    10. Конкатенация. 
    11. Проекция. 

    498	Часть V. Дополнительные аспекты 

    Определенный алгоритм обработки запроса выражается в терминах 
перечисленных низкоуровневых операций, и стоимость этого алгоритма может быть 
вычислена с помощью стоимостных формул. В работе рассмотрены различные классы 
алгоритмов обработки запросов и для каждого класса выработаны стоимостные 
формулы. После чего проблема оптимизации запроса сводится к решению простого 
набора стоимостных уравнений для вычисления минимальной стоимости. Затем 
выбирается класс алгоритмов, соответствующий полученной минимальной стоимости. 
    18.5. Pecherer R.M. Efficient Evaluation of Expressions in a Relational 
Algebra // Proc. ACM Pacific Conf. — 1975. 
    Одна из первых работ, затрагивающая проблему реализации реляционных 
операторов. Начинается с представления несколько пересмотренной версии 
исходной алгебры (данные изменения внесены из соображений эффективности). 
Далее излагается реализация операции новой, пересмотренной, алгебры. Делается 
предположение, что отношения хранятся как сортированные файлы и кортежи из 
отношений можно получать только в той последовательности, в которой кортежи 
были сохранены. Пределы производительности вычислены для каждой операции. В 
работе утверждается, что при изложенных условиях наибольшее внимание следует 
уделять операциям проекции и деления. 
    18.6. Blasgen M.W., Eswaran К.P. Storage and Access in Relational 
Databases // IBM Sys. J. — 1977.—16, №4. 
    Представлены результаты сравнения различных приемов обработки запросов, в 
которых используются операции проекции, выборки и соединения, на базе их 
стоимости в операциях ввода-вывода. 
    18.7. Merrett Т.Н. Why Sort/Merge Gives the Best Implementation of the 
Natural Join // ACM SIGMOD. — 1983. — 13, № 2. 
    Представлен набор интуитивных аргументов в пользу утверждения, что с 
помощью сортировки-слияния можно добиться самых эффективных результатов. В 
основном аргументы сводятся к тому, что операция соединения будет наиболее 
эффективной, если оба отношения будут отсортированы по значениям атрибута, по 
которому выполняется соединение (поскольку в данном случае, как показано выше 
в этой главе, слияние — достаточно эффективный метод оптимизации, а выборка 
каждой страницы выполняется только один раз, что действительно является 
оптимальным); при этом стоимость сортировки отношений в необходимом порядке 
(на больших машинах) будет, вероятно, меньше стоимости схемы, для которой не 
требуется порядок кортежей в обоих отношениях. 
    Тем не менее, автор допускает, что для его радикальной позиции могут 
существовать исключения. Например, одно из отношений может быть настолько 
малым (т.е. оно может быть результатом предыдущей операции выборки), что 
прямой доступ ко второму отношению через индекс или хеш-таблицу может иметь 
меньшую стоимость, чем сортировка второго отношения. В [18.8-18.11] приведены 
дополнительные примеры случаев, для которых метод сортировки-слияния не 
является на практике лучшим приемом обработки. 
    18.8. Sacco G.M. Fragmentation: A Technique for Efficient Query Processing 
// ACM TODS.— 1986. — 11, №2. 
    Представлен один из методов типа "разделяй и властвуй" для выполнения 
операции соединения. Согласно этому методу соединяемые отношения рекурсивно 
разбиваются на подмножества кортежей ("фрагменты") и на этих 

    Глава 18. Оптимизация	499 

фрагментах выполняется серия просмотров. В отличие от метода 
сортировки-слияния, этот метод не требует предварительной сортировки 
отношений. Показано, что фрагментация всегда работает эффективнее 
сортировки-слияния, когда этот метод, требует предварительной сортировки обоих 
отношений, и иногда работает лучше, когда этот метод требует предварительной 
сортировки одного (большего) отношения. Автор утверждает, что данный метод 
можно применять и для других операций, таких как пересечение и вычитание. 
    18.9. Negri M., Pelagatti G. Distributive Join: A new Algorithm for 
Joining Relations // Ibid.—1991.—16, №4. 
    Здесь представлен другой метод соединения типа "разделяй и властвуй", 
который "...базируется на идее о том, что... не нужно полностью сортировать 
оба отношения... Достаточно сортировать одно отношение полностью, а другое — 
частично, избежав, таким образом, расходов производительности на выполнение 
полной сортировки второго отношения." Частичная сортировка разбивает 
рассматриваемое отношение на последовательность неупорядоченных подмножеств 
кортежей SI, S2,... Sn (похоже на метод Сакко (Sacco) [18.8], за исключением 
того что в методе Сакко используется хеширование вместо сортировки), 
обладающих следующим свойством: МАХ(5[/]) < MIN(5[/+1]) для всех /(1, 2,..., 
«-!). Утверждается, что данный метод работает эффективнее сортировки-слияния. 
    18.10. DeWitt D.J. et al. Implementation Techniques for Main Memory 
Database Systems // Proc. ACM SIGMOD Intern. Conf. on Management of Data. — 
Boston, Mass., 1984. 
    18.11. Shapiro L.D. Join Processing in Database Systems with Large Main 
Memories // ACM TODS. — 1986. — 11, № 3. 
    Представлено три новых алгоритма хеширования соединений. Один из этих 
алгоритмов "особенно эффективен при наличии основной памяти в размере, 
значительно превышающем размер одного из соединяемых отношений". Алгоритмы 
работают благодаря разбиению отношений на подмножества кортежей, которые можно 
обрабатывать в основной памяти. Автор заявляет, что исходя из скорости 
снижения цены на память, методы на основе хеширования станут одними из лучших. 
    18.12. Bitton D., DeWitt D.J., Turbyfill С. Benchmarking Database Systems: 
A Systematic Approach // Proc. 9th Intern. Conf. on Very Large Data Bases. — 
Florence, Italy, 1983. 
    Впервые описано то, что сегодня называют "Висконсинский тест" (так как 
этот тест был разработан в университете штата Висконсин). Данный тест включает 
набор отношений с точно указанными значениями атрибутов. Согласно тесту 
определяется производительность предопределенных алгебраических операций на 
указанных отношениях (например, различные виды проекций, использующих атрибуты 
с разной степенью дублирования значений). Таким образом, измеряется 
эффективность работы оптимизатора системы на описанных выше основных операциях. 
    18.13. Bitton D., DeWitt D.J. Duplicate Record Elimination in Large Data 
Files // ACM TODS. —1983. —8, №2. 
    Традиционный метод исключения дублирующихся кортежей состоит в сортировке 
записей и последовательном просмотре. Данная работа предлагает альтернативное 
решение, более эффективное на файлах большого размера. 

    500	Часть V. Дополнительные аспекты 

    18.14. Bitton D, Boral H., DeWitt D.J., Wilkinson K. Parallel Algorithms 
for the Execution of Relational Database Algorithms // Ibid. — 8, № 3. 
    Представлены алгоритмы реализации операций сортировки, проекции, 
соединения, агрегации и обновления в многопроцессорных средах. Представлены 
также общие стоимостные формулы, учитывающие операции ввода-вывода, загрузку 
процессора, выдачу сообщений. Эти формулы можно адаптировать к различным 
многопроцессорным архитектурам. 
    18.15. Palermo P.P. A Data Base Search Problem // J.T. Tou (ed.). 
Information Systems: COINS IV — New York, N.Y.: Plenum Press, 1974. 
    Одна из первых работ по оптимизации. Начиная с произвольного выражения 
реляционного исчисления, как это выражение можно уменьшить до эквивалентного 
алгебраического выражения с помощью алгоритма редукции Кодда (Codd). Кроме 
того, здесь представлено несколько усовершенствований этого алгоритма; вот 
некоторые из них: 
    • Ни один кортеж не считывается больше одного раза. 
    • Ненужные значения отбрасываются из кортежа как только он считан 
("ненужными" называют такие значения, которые не используются в определении 
запроса или в качестве отдельных значений в операциях выборки). Этот процесс 
эквивалентен операции проекции отношения по "нужным" атрибутам, следовательно, 
уменьшает размер пространства, необходимого для хранения входных данных, и, 
возможно, количество кортежей, которые требуют рассмотрения в последующих операциях. 
    • Метод, используемый для построения отношения-результата, базируется на 
принципе наименьшего роста, т.е. результат "растет" медленно. Этот прием 
приводит к уменьшению количества сравнений, а также уменьшает размер 
пространства, необходимого для хранения промежуточных результатов. 
    • Для построения соединений применяется эффективный метод разложения 
значений, используемых в операторе соединения (например, S.S# = SP.S#), в 
полусоединения и внутренние представления каждого соединения (используя 
внутренние номера для идентификации входящих в соединение кортежей). Эти 
приемы уменьшают количество проверок, необходимых для построения соединения. 
Эти приемы также позволяют динамически определять "лучшую" последовательность 
доступа к требуемым отношениям базы данных. 

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

    18.16. Rothnie J.B. (Jr.). An Approach to Implementing a Relational Data 
Management System // Proc. ACM SIGMOD Workshop on Data Description, Access, 
and Control. — Ann Arbor, Mich., 1974. 
    18.17. Rothnie J.B. (Jr.). Evaluating Inter-Entry Retrieval Expressions in 
a Relational Data Base Management System // Proc. NCC 44. — Anaheim, Calif.; 
Montvale, N.J.: AFIPS Press, 1975. 
    Еще две ранние работы по оптимизации. В них описаны некоторые приемы, 
которые используются в экспериментальной системе DAMAS (построенной на основе 
системы MIT) для реализации языка на основе исчисления. В частности, в работы 
включено описание примера реализации того, что в системе INGRES называется 
"двухпеременными запросами" [18.31, 18.32]. Публикация [18.17] больше похожа 
на учебное пособие, а [18.16] предоставляет некоторые экспериментальные 
результаты и больше внутренних деталей. В работах обсуждаются методы 
реализации выражений (исполь-

    Глава 18, Оптимизация	501 

    зующие единственную переменную с квантором существования), в терминах 
более простых выражений известные как примитивные булевы условия (primitive 
Boolean conditions — РВС). РВС — это условие, которое может иметь значение 
истина (true) или ложь (false) на данном кортеже в результате изолированной 
проверки этого кортежа, т.е. РВС является простым условием выборки. Модули 
хранения в системе DAMAS, управляющие хранимыми данными, поддерживают такие операции: 
    1.  Получить следующий кортеж, для которого значение/? будет истинным. 
    2.  Проверить наличие такого кортежа, для которого условие р имеет 
значение истина. 
    3.  Исключить из рассмотрения все кортежи, для которых р имеет значение истина. 
    Здесь р — это РВС. С помощью этих операций, как показано ниже, система 
обрабатывает операции выборки из отношений (или переменных области значений) 
R1 (не квантованного) и R2 (с квантором существования). Заметьте, что 
приемником результата выборки должна быть некоторая проекция отношения R1. 
(Здесь и далее в этом комментарии обозначения R1 и R2 используются для ссылок 
на отношения, соответствующие переменным области значений R1 и R2.) 
    Шаг 1. В исходном условии всем частям, использующим переменную R2, 
присваивается значение истина, и это условие упрощается. Результатом являются 
условия РВС, обозначенные/»/. Кортежи из R1, которые не удовлетворяют 
условию/?/, можно исключить из дальнейшего рассмотрения. 
    Шаг 2. Получить кортеж (не исключенный на предыдущем шаге) из отношения 
R1. Подставив значения из этого кортежа в исходное условие и упростив, получим 
условие РВС р2. Существует ли в R2 кортеж, удовлетворяющий условию р2? 
    Шаг 3,а. (Да.) Получить такой кортеж из R2. Считать выбираемые значения из 
кортежа, полученного из R1, и добавить их в отношение-результат. Построить 
условие рЗ, выбрав из R1 все кортежи, содержащие те же значения в выбираемых 
атрибутах, и использовать это условие для исключения из рассмотрения всех 
кортежей из R1, которые приведут к появлению дублирующихся кортежей. (Это 
исключение может быть выполнено когда бы ни добавлялся кортеж в 
отношение-результат.) После этого заменить значения, полученные из выбранного 
кортежа R2, на исходные условия и упростить выражение, в результате получим 
условие РВС р4. Получить все кортежи из RI, которые удовлетворяют условию р4, 
и добавить эти кортежи в результат. 
    Шаг 3,6. (Нет.) Построить РВС/>5, выбрав все кортежи из R1, которые 
приводят к построению (на шаге 2) такого РВС, что в R2 не существует ни одного 
кортежа, удовлетворяющего данному РВС (так как ни одни кортеж не удовлетворяет 
р2). Исключить указанные кортежи из R1. 
    Шаг 4. Повторять шаги 2-3, пока в R1 остаются кортежи. 
    Изложенный алгоритм базируется на принципе, утверждающем, что от каждого 
доступа к базе данных нужно получать максимальное количество информации. Тем 
не менее, на практике можно доказать, что в некоторых случаях, например, 
исключение кортежей из дальнейшего рассмотрения дороже простой проверки 
кортежа и отказа от него. Поэтому некоторые шаги алгоритма могут либо 
применяться, либо нет в каждой конкретной ситуации. В системе DAMAS этот выбор 
возложен на пользователя, но в руководстве даны некоторые рекомендации по 
автоматизации этого процесса. 

    502	Часть V. Дополнительные аспекты 

    18.18. Smith J.M., Yen-Tang Chang P. Optimizing the Performance of a 
Relational Algebra Database Interface // CACM. — 1975. — 18, № 10. 
    Описан алгоритм, использовавшийся в языке "Smart Query Interface for a 
Relational Algebra" (SQUIRAL). Этот алгоритм включает следующее: 
    • Преобразование исходного алгебраического выражения в эквивалентную, но 
более эффективную последовательность операций (это обсуждалось выше в этой главе). 
    • Привязка отдельных операций в преобразованном выражении к определенным 
процессам и использование параллелизма и конвейерной обработки для выполнения операций. 
    • Координация порядков сортировки в промежуточных результатах, которые 
передаются между процессами. 
    • Использование индексов и попытки локализации страничных ссылок. 
    18.19. Hall P.A.V. Optimization of a Single Relational Expression in a 
Relational Data Base System // IBM J. R&D. — 1976. — 20, № 3. 
    Описаны некоторые методы оптимизации, используемые в системе PRTV, 
которая, как и SQUIRAL [18.18], начинает с преобразования данного 
алгебраического выражения в некоторую более эффективную форму перед 
вычислением. Особенностью PRTV является то, что система не вычисляет 
автоматически каждое выражение, как только оно получено. Вместо этого 
выражения комбинируются с полученными ранее в более сложное выражение и 
вычисление откладывается до последнего момента (см. обсуждение пошаговой 
формулировки запроса в главе 6). Таким образом, отдельное реляционное 
выражение на самом деле представляет всю последовательность операций 
пользователя. Данный метод оптимизации подобен методу SQUIRAL, но в некоторых 
случаях работает лучше. 
    • Выборка выполняется настолько рано, насколько это возможно. 
    • Последовательность проекций комбинируется в одну операцию проекции. 
    • Избыточные операции исключаются. 
    • Выражения, использующие пустые отношения и тривиальные условия, упрощаются. 
    • Общие выражения выносятся за скобки. 
    В заключении работы изложены результаты некоторых экспериментов, а также 
указаны направления дальнейших исследований. 
    18.20. Jarke M., Koch J. Range Nesting: A Fast Method to Evaluate 
Quantified Queries // Proc. 1983 ACM SIGMOD Intern. Conf. on Management of 
Data. — San Jose, Calif, 1983. 
    Определены изменения реляционного исчисления, позволяющие применять 
некоторые дополнительные правила преобразования. Представлены алгоритмы 
вычисления выражений в описанном исчислении, а также обсуждение оптимизации в 
описанном исчислении отдельного класса выражений, называемого "точными 
вложенными выражениями". Изложены методы преобразования в точные выражения 
сложных запросов (в частности, запросов, использующих оператор FORALL). Авторы 
показывают, что в точные выражения можно преобразовать большое количество 
запросов, возникающих на практике. 
    18.21. Makinouchi A., Tezuka M., Kitakami H., Adachi S. The Optimization 
Strategy for Query Evaluation in RDB/V1 // Proc. 7th Intern. Conf. on Very 
Large Data Bases — Cannes, France, 1981. 

    Глава 18. Оптимизация	503 

    Система RDB/V1 является прототипом будущего программного продукта	J 
AIM/RDB компании Fujitsu (это SQL-система). В этой публикации описаны приемы 
оптимизации, которые используются в данном прототипе. Эти приемы коротко 
сравниваются с аналогичными, используемыми в прототипах систем INGRES и System 
R. Один из приемов является новым и состоит в применении динамически 
полученных значений функции МАХ и MIN для выполнения дополнительных выборок. 
Этот прием приводит к упрощению процесса выбора порядка соединения и повышает 
производительность самого соединения. В качестве простого примера для 
последнего утверждения предположим, что нужно соединить отношения S и Р по 
атрибуту CITY. Сначала отношение S сортируется по атрибуту S.CITY. В процессе 
сортировки на атрибуте S.CITY определяются значения функций МАХ и MIN, 
обозначим их соответственно HIGH и LOW. Тогда для уменьшения количества 
кортежей отношения Р, которые нужно проверять в процессе построения 
соединения, можно использовать выборку 

    LCW < P.CITY AND P.CITY < HIGH 

    18.2la. Pirahesh H., Hellerstein J.M., Hasan W. Extensible Rule Based 
Query Rewrite Optimization in Starburst // Proc. 1992 ACM SIGMOD Intern. Conf. 
on Management Data. — San Diego, Calif, 1992. 
    Перезапись запросов (Query Rewrite) — еще одно название процесса 
преобразования выражений. Несколько неожиданно, но современные реляционные 
СУБД, по мнению авторов, немного делают в отношении такого преобразования. В 
работе описан механизм преобразования выражений прототипа системы IBM 
Starburst. Пользователи с соответствующей квалификацией могут в любое время 
добавить в систему новые правила преобразования выражений. 
    18.22. Mumick I.S., Finkelstein S.J., Pirahesh П., Ramakrishnan R. Magic 
is Relevant // Proc. 1990 ACM SIGMOD Intern. Conf. on Management Data. — 
Atlantic City, N.J., 1990. 
    Неудачный термин "magic" (волшебный) используется в данной публикации для 
ссылок на метод оптимизации, который изначально создавался для обработки 
запросов, в частности рекурсивных, записанных на логическом языке баз данных 
Datalog. Работа расширяет этот подход до условно-реляционных систем, утверждая 
на основе экспериментальных измерений, что такой подход часто эффективнее 
традиционных приемов оптимизации (заметьте, что запрос не обязательно должен 
быть рекурсивным, чтобы применить к нему описанный метод). Основная идея 
метода состоит в декомпозиции данного запроса на несколько меньших запросов, 
которые определяют "вспомогательные отношения" (нечто похожее на декомпозицию 
запросов в INGRES [18.31, 18.32]) таким образом, что их можно использовать для 
фильтрации кортежей, не относящихся к данному запросу. Ниже приведен пример 
запроса, который базируется на примере из данной работы: 

    R := EX.ENAME WHERE EX. JOB = 'Clerk' AND EX.SAL > 
    AVG ( EY WHERE EY.DEPTtf = EX.DEPTtt, SAL ) ; 

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

    504	Часть V. Дополнительные аспекты 

    Tl := ( EX.DEPT*, 
    AVG ( EY WHERE EY.DEPTtt = EX.DEPTft, SAL ) AS ASAL ) ; T2 := EMP.ENAME 
WHERE EMP.JOB = 'Clerk1 AND 
    EXISTS Tl ( EMP.DEPT# = T1.DEPT# AND EMP.SALARY > Tl.ASAL ) ; 

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

    /* первое вспомогательное отношение: */ /* имя, отдел и зарплата клерков 
*/ Т1 := ( EMP.ENAME, EMP.DEPT#, EMP.SAL ) 
    WHERE EMP.JOB = 'Clerk' ; /* второе вспомогательное отношение: */ /* 
отделы, в которых работают клерки */ Т2 := T1.DEPT* ; 
    /* третье вспомогательное отношение: */ /* отделы, в которых работают 
клерки, */ /* и средние зарплаты для каждого отдела */ ТЗ := ( T2.DEPT#, 
    AVG ( EMP WHERE EMP.DEPT* = T2.DEPT*, SAL ) AS ASAL ) ; /* 
отношение-результат */ 
    R := Tl.ENAME WHERE EXISTS T3 ( Tl.DEPT* = T3.DEPT# AND 
    Tl.SAL > T3.ASAL ) ; 

    "Волшебство" состоит в том, чтобы определить, какие вспомогательные 
отношения нужно создать. 
    18.23. King J.J. QUIST: A System for Semantic Query Optimization in 
Relational Databases // Proc. 7th Intern. Conf. on Very Large Data Bases. — 
Cannes, France, 1981. 
    Представлена идея семантической оптимизации (это обсуждалось выше в 
главе). Описана экспериментальная система QUIST (query improvement through 
semantic transformation — улучшение запросов посредством семантических 
преобразований), способная выполнять подобные преобразования. 
    18.24. Shenoy S.T., Ozsoyoglu Z.M. A System for Semantic Query 
Optimization // Proc. 1987 ACM SIGMOD Intern. Conf. on Management of Data. — 
San Francisco, Calif, 1987. 
    Эта публикация расширяет работу Кинга (King) [18.23], представляя схему, 
которая динамически из потенциально очень большого множества ограничений 
целостности выбирает только те ограничения, которые будут полезны для 
обработки данного запроса. Рассматриваемые ограничения целостности разделены 
на два типа: ограничения причастности (например, "если партия товаров содержит 
более 300 единиц товара, то поставщик должен быть расположен в Лондоне") и 
ограничения подмножеств (например, "каждый по-

    Глава 18. Оптимизация	505 

ставщик, расположенный в Лондоне, должен поставлять хотя бы одну деталь"). 
Подобные ограничения используются для преобразования запросов путем исключения 
избыточных выборок и соединений и позволяют создавать дополнительные выборки 
на индексированных атрибутах. Случаи получения результата запроса 
непосредственно из ограничений целостности также эффективно обрабатываются с 
помощью изложенного метода. 
    18.25. Siegel M, Sciore E., Salveter S. A Method for Automatic Rule 
Derivation to Support Semantic Query Optimization // ACM TODS. — 1992. — 17, № 4. 
    Как было показано в этой главе, семантическая оптимизация использует 
ограничения целостности для преобразования запросов. Тем не менее, существует 
несколько проблем, связанных с этой идеей. 
    1.   Как оптимизатор может узнать, какое преобразование будет эффективным 
(т.е. какое преобразование сделает запрос более эффективным)? 
    2.  Некоторые ограничения целостности не очень полезны для решения задач 
оптимизации. Например, ограничение, которое требует, чтобы вес детали был 
положительным числом, важно для целостности базы данных, но не применимо для 
оптимизации. Как оптимизатор может распознать полезные и бесполезные 
ограничения целостности? 
    3.   Некоторые ограничения можно использовать в определенных состояниях 
базы данных, даже во всех состояниях, но эти ограничения могут не являться 
ограничениями целостности. Примером может служить ограничение EMP.AGE < 50, 
которое не является ограничением целостности как таковым (сотрудники могут 
быть и старше 50 лет, но в данный момент в компании может не быть сотрудников 
старше 50 лет). 
    Эта публикация описывает архитектуру системы, учитывающую перечисленные проблемы. 
    18.26. Chakravarthy U.S., Grant J., Minker J. Logic-Based Approach to 
Semantic Query Optimization // Ibid. — 1990. — 15, № 2. 
    Цитата из вступления: "В нескольких предыдущих работах авторами была 
описана и доказана правильность метода семантической оптимизации запросов... 
Эта работа обобщает основные результаты из предыдущих работ и обращает особое 
внимание на методы и их применимость к оптимизации реляционных запросов. 
Дополнительно эта работа показывает, каким образом описываемый метод суммирует 
и обобщает результаты более ранних работ по семантической оптимизации, как 
методы семантической оптимизации запросов могут быть распространены на 
рекурсивные запросы и условия целостности, которые содержат дизъюнкцию, 
отрицание и рекурсию". 
    18.27. Aho A.V., Sagiv Y., Ullman J.D. Efficient Optimization of a Class 
of Relational Expressions // Ibid. — 1979. —4, № 4. 
    Класс реляционных выражений содержит выражения, использующие только (на 
основе равенств) выборку, проекцию и естественное соединение. Этот класс 
выражений также называют SPJ-выражениями (от англ, select, projection, join — 
выборка, проекция, соединение). SPJ-выражения соответствуют запросам в 
реляционном исчислении, в которых используются сравнения на равенство, 
операции AND и кванторы EXISTS. В работе приводится определенный вид таблицы 
(табло), представляющей двухмерный массив, в котором столбцы соответствуют 
атрибутам, а строки — условиям, в частности условиям принадлежности, которые 
гласят, что конкретный кортеж значений должен принадлежать конкретному 
отношению. Строки табло логически связаны общими символами в связанных 
строках. Например, табло 

    506	Часть V. Дополнительные аспекты 

    _S#_____STATUS______CITY_________PJ______COLOR______ 
_______al______________________________________ Ы     al         London	- 
отношение S Ы                           Ь2                - отношение SP 
    Ь2     Red        - отношение P 

    представляет запрос "Получить статус (а!) поставщиков (Ы) в Лондоне, 
которые поставляют красные детали (62)". Верхняя строка в табло представляет 
все атрибуты, которые используются в запросе, следующая строка — это "итоги" 
(она соответствует списку атрибутов выборки в запросе, определенном в 
исчислении, или финальной проекции в алгебраическом запросе), а ниже приведены 
строки, описывающие условия принадлежности. В примере отмечены эти строки для 
соответствующих относящихся к запросу отношений. Заметьте, что "Ь" 
используется для ссылок на ограниченные переменные, а "а" — для ссылки на 
свободную переменную. Итоговая строка содержит только переменные "а". 
    Табло — это еще один кандидат на канонический формализм для представления 
запросов, однако оно не является достаточно общим, чтобы представить все 
возможные реляционные запросы. (Фактически табло можно рассматривать как 
синтаксическую разновидность языка Query-By-Example (QBE), хотя и менее 
мощную, чем непосредственно язык QBE.) В работе представлены алгоритмы для 
сжатия одного табло в другое, семантически эквивалентное табло, в котором 
количество строк уменьшено до минимума. Полученное табло представляет 
оптимальную форму запроса, хотя и в очень специальном смысле (минимальное 
количество соединений). (В приведенном выше примере количество соединений уже 
минимально, поэтому подобная оптимизация не имеет никакого эффекта.) 
Минимальное табло после этого можно конвертировать обратно в какое-либо другое 
представление для последующей дополнительной оптимизации. 
    Идея оптимизации количества соединений также применима к запросам, 
сформулированным в терминах представлений, построенных на основе операции 
соединения (в частности, к запросам, сформулированным в терминах 
"универсальных отношений"). Например, предположим, что пользователю предложено 
представление (view) V, определенное как соединение отношений S и SP по 
атрибуту S#, и пользователь вводит запрос 

    V   [   Р#   ] 

    Прямой алгоритм обработки представлений преобразует данный запрос в следующий: 

    (  SP JOIN S   )    [   Р#  ] 

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

    SP   [  Р#  ] 

    Поэтому следует заметить, что, так как алгоритмы сжатия табло, описанные в 
данной работе, учитывают все явно выраженные функциональные зависимости между 
атрибутами, эти алгоритмы являются ограниченным примером семантической оптимизации. 
    18.28. Sagiv Y., Yannakakis M. Equivalences Among Relational Expressions 
with the Union and Difference Operators // JACM. — 1980. — 27, № 4. 
    Распространяет идею [18.27] так, чтобы ее можно было применять к запросам, 
использующим операции объединения и вычитания. 

    Глава 18. Оптимизация	507 

    18.29. Selinger P.G. et al. Access Path Selection in a Relational Database 
System // Proc. 1979 ACM SIGMOD Intern. Conf. on Management of Data.— Boston, 
Mass., 1979. 
    Обсуждены некоторые методы оптимизации, используемые в прототипе системы 
System R. 
    Замечание. Оптимизатор системы System R является прародителем оптимизатора 
системы DB2. В [18.30] дана более подробная информация, специфическая для DB2. 
    В системе System R запрос представляет собой SQL-выражение, поэтому 
состоит из набора блоков SELECT-FROM-WHERE (блоков запроса). Некоторые из 
блоков могут быть вложены в другие блоки. Оптимизатор System R сначала 
определяет порядок, в котором будут вычисляться блоки запроса. После этого 
оптимизатор пытается снизить общую стоимость запроса посредством выбора 
реализации с наименьшей стоимостью для каждого отдельного блока запроса. 
Данная стратегия (сначала выбор порядка блоков, а затем оптимизация отдельных 
блоков) означает, что конкретный план выполнения всего запроса никогда не 
рассматривается, и это приводит к "сужению пространства поиска". 
    Замечание. В случае вложенных блоков оптимизатор вычисляет блоки во 
вложенном порядке, который указал пользователь, т.е. внутренний блок 
выполняется первым. В [18.35-18.39] можно найти критику и дальнейшее 
обсуждение данной стратегии. 
    Для данного блока запроса существует два случая, которые нужно рассмотреть 
(первый из них можно рассматривать как частный случай второго). 
    1.  Для блока, в котором используется только выборка и (или) проекция 
единственного отношения, оптимизатор использует статистические данные из 
каталога совместно с формулами (представленными в этой публикации) для 
немедленной оценки размера результата и стоимости низкоуровневых операций, а 
также для выбора стратегии построения выборки и (или) проекции. 
    2.  Для блоков, в которых используются два или больше отношений, 
соединенных с помощью операции JOIN, возможно, с локальными выборками и (или) 
проекциями отдельных отношений, оптимизатор трактует каждое отдельное 
отношение как случай 1 и определяет последовательность выполнения соединений. 
Эти две операции не являются независимыми друг от друга. Например, может быть 
выбрана определенная стратегия доступа к отдельному отношению А, так как эта 
стратегия позволяет получать кортежи из А в порядке, который удобен для 
выполнения последующего соединения отношения А с другим отношением В. 
    Соединения реализованы с помощью метода сортировки-слияния, поиска по 
индексу или прямого метода. В работе особое значение автор придал тому, что 
при вычислении, например, вложенного соединения (A JOIN В) JOIN С не 
обязательно полностью вычислять вложенное соединение A JOIN В перед 
соединением результата и отношения С. С другой стороны, любой кортеж 
соединения A JOIN В сразу после вычисления передается процессу, соединяющему 
этот кортеж с кортежами из С. Поэтому нет необходимости материализовать 
отношение A JOIN В полностью. (Эта идея кратко обсуждалась в главе 6.) 
    Работа также включает некоторые соображения о стоимости оптимизации. Для 
соединения двух отношений стоимость приблизительно равна стоимо-

    508	Часть V. Дополнительные аспекты 

сти 5-20 операций выборки — небольшие расходы при многократном выполнении 
оптимизированного запроса. (Заметьте, что System R, как и DB2, является 
компилирующей системой, поэтому однажды оптимизированный запрос может 
выполняться сотни и даже тысячи раз.) В работе утверждается, что оптимизация 
сложных запросов требует "всего нескольких тысяч байт пространства для 
хранения и нескольких десятых долей секунды" на компьютере IBM System 370 
Model 158. "Соединение восьми таблиц было оптимизировано за несколько секунд." 
    18.30. Cheng J.M., Loosley C.R., Shibamiya A., Worthington P.S. IBM 
DATABASE 2 Performance: Design, Implementation, and Tuning // IBM Sys. J. — 
1984. — 23, № 2. 
    Содержит краткое описание тактики оптимизации в DB2 (в первой версии этой 
системы): приемы преобразования запросов, обработка вложенных блоков запроса, 
методы соединения, выбор пути доступа и обработка индексов. Работа также 
включает интересный материал о других аспектах системы DB2, влияющих на производительность. 
    18.31. Wong E., Youssefi К. Decomposition— A Strategy foe Query Processing 
// ACM TODS. — 1976. — 1, № 3. 
    18.32. Youssefi K., Wong E. Query Processing in a Relational Database 
Management System // Proc. 5th Intern. Conf. on Very Large Data Bases. — Rio 
De Janeiro, Brazil, 1979. 
    18.33. Epstein R. Techniques for Processing of Aggregates in Relation 
Database Systems. — Berkley: University of California, Electronics Research 
Laboratory Memorandum, 1979. — № UCB/ERL M79/8. 
    Работа описывает алгоритмы, используемые в прототипе системы INGRES для 
работы с агрегативными функциями COUNT, SUM, AVG и т.п. В частности, включает 
несколько алгоритмов, которые можно применять в процессе такой работы. 
    18.34. Rowe L.A., Stonebraker M. The Commercial INGRES Epilogue // M. 
Stonebraker (ed.). The INGRES Papers: The Anatomy of a Relational Database 
Management System. — Reading, Mass.: Addison-Wesley, 1985. 
    Commercial INGRES (коммерческая система) — это программный продукт, 
полученный из прототипа University INGRES (университетская система). Ниже 
перечислены некоторые различия между оптимизаторами систем Commercial INGRES и 
University INGRES. 
    1.  Университетский оптимизатор использует инкрементное планирование, т.е. 
определяет, что нужно сделать сначала, делает это, после чего определяет, что 
делать дальше, исходя из размера полученного промежуточного результата, и т.д. 
Коммерческий оптимизатор определяет полный план перед началом выполнения, 
исходя из оценок размеров промежуточных результатов. 
    2.  Университетский оптимизатор обрабатывает двухпеременные запросы 
(например, соединения) с помощью подстановки кортежей, как было описано в этой 
главе. Коммерческий оптимизатор поддерживает несколько мощных методов 
обработки подобных запросов, включая, в частности, метод сортировки-слияния, 
также описанный в этой главе. 
    3.  Коммерческий оптимизатор поддерживает более сложный набор статистик по 
сравнению с университетским оптимизатором. 
    4.  Университетский оптимизатор выполняет инкрементное планирование (см. 
пункт 1). Коммерческий оптимизатор выполняет более исчерпывающий поиск. Тем не 
менее, поиск прекращается, если на оптимизацию 

    Глава 18, Оптимизация	509 

затрачено время, превышающее наилучшую оценку времени выполнения запроса 
(в противном случае выполнение оптимизации не даст никаких преимуществ), 
    5.   Коммерческий оптимизатор рассматривает все возможные комбинации 
индексов, все возможные последовательности соединения и "все доступные методы 
выполнения соединения — сортировка-слияние, частичная сортировка-слияние, 
поиск по хеш-таблице, поиск по В-дереву и прямой метод". 
    18.35. Kirn W. On Optimizing an SQL-Like Nested Query // ACM TODS, — 1982. — 
    7,№3, 
    CM. [18.39]. 
    18.36. Kiessling W. On Semantic Reefs and Efficient Processing of 
Correlation Queries with Aggregates // Proc. llth Intern. Conf. on Very Large 
Data Bases.— Stockholm, Sweden, 1985. 
    CM. [18.39]. 
    18.37. Ganski R.A., Wong H.K.T. Optimization of Nested SQL Queries 
Revisited // Proc. 1987 ACM SIGMOD Intern. Conf. on Management of Data.— San 
Francisko, Calif, 1987. 
    CM. [18.39]. 
    18.38. Gunter von Bultzingsloewen. Translating and Optimizing SQL Queries 
Having Aggregates // Proc. 13th Intern. Conf. on Very Large Data Bases.— 
Brighton, England, 1987. 
    CM. [18.39]. 
    18.39. Muralikrishna M. Improved Unnesting Algorithms for Join Aggregate 
SQL Queries // Proc. 18th Intern. Conf. on Very Large Data Bases. — 1992, 
    Язык SQL позволяет создавать "вложенные подзапросы", т.е. блоки 
SELECT-FROM-WHERE, вложенные внутрь других подобных блоков. Эта конструкция 
порождает для реализаторов некоторые трудности. Рассмотрим следующий 
SQL-запрос ("Получить имена поставщиков, которые поставляют деталь Р2"), на 
который далее будем ссылаться как на запрос Q1: 

    SELECT S.SNAME FRCM  S WHERE S.S# IN 
    ( SELECT SP.S# FRCM  SP WHERE SP.P# = 'P2' ) ; 

    В системе System R [18.29] этот запрос будет реализован следующим образом. 
Сначала будет вычислен внутренний блок и создано промежуточное отношение R, 
которое содержит номера требуемых поставщиков. После этого кортеж за кортежем 
будет проверено отношение S и для каждого кортежа из отношения S будет 
проверяться отношение R на предмет, содержит ли это отношение соответствующий 
номер поставщика. Эта стратегия достаточно неэффективна (особенно если 
отношение R не индексировано). 
    Теперь рассмотрим запрос Q2: 

    SELECT	S.SNfiME 
    FRCM	S, SP 
    WHERE	S.S# = SP.S# ; 

    510	Часть V. Дополнительные аспекты 

    Легко установить, что этот запрос семантически идентичен предыдущему, но 
система System R рассмотрит дополнительную стратегию для реализации данного 
запроса. В частности, если отношения S и SP окажутся физически сохраненными в 
последовательности номеров поставщиков, то система применит слияние, которое 
будет весьма эффективно. Предположив, что два рассмотренных запроса логически 
эквивалентны, но второй более удобен для эффективной реализации, мы придем к 
выводу, что возможность преобразования запросов, подобных Q1, в запросы, 
подобные Q2, требует более глубокого изучения. Эта возможность и является 
предметом обсуждения в [18.35-18.39]. 
    Ким (Kirn) [18.35] был первым, кто обратил внимание на эту проблему. В его 
работе идентифицировано пять типов вложенных запросов и описаны 
соответствующие алгоритмы. Работа содержит некоторые результаты экспериментов, 
которые показывают, что предложенные алгоритмы повышают производительность 
обработки вложенных запросов обычно на один-два порядка. 
    В свою очередь, Кесслинг (Kiessling) [18.36] показал, что алгоритмы Кима 
работают некорректно, если вложенный запрос (на любом уровне) содержит в 
списке атрибутов выборки агрегативную функцию COUNT (алгоритм Кима некорректно 
обрабатывает случаи, когда аргументы функции COUNT являются пустыми 
отношениями). Термин "семантические рифы" в названии работы Кесслинга 
указывает на сложности, с которыми сталкивается пользователь при попытке 
получить корректные и непротиворечивые результаты подобных запросов. Более 
того, Кесслинг показал, что алгоритмы Кима непросто усовершенствовать 
(поскольку должен существовать единый способ выполнить данное преобразование 
эффективно и корректно при любых условиях). Если взглянуть со стороны, то в 
данной работе показано, что в общей области язык QUEL превосходит язык SQL 
(см. [18.33]). 
    Работа Ганского и Вонга (Ganski and Wong) [18.37] описывает решение 
проблемы, обнаруженной Кесслингом. Решение можно получить, использовав в 
преобразованной версии запроса вместо обычного внутреннего соединения внешнее 
соединение (это обсуждается далее в настоящей книге). Данная работа описывает 
еще одну ошибку в оригинальной работе Кима, которая устраняется аналогичным 
способом. Тем не менее, работа не лишена собственных ошибок. Одни связаны с 
проблемой дублирующихся строк (печально известные "семантические рифы" 
[18.36]), другие— с изъянами в реализации квантора EXISTS в языке SQL. 
    В [18.38] сделана попытка сформулировать всю проблему на теоретической 
основе (основной проблемой предыдущих работ являлось то, что, как обнаружили 
различные авторы, поведение — семантическое и синтаксическое — вложений и 
агрегативных функций не совсем понятно). В [18.38] также определены 
расширенные версии реляционного исчисления и реляционной алгебры (расширения 
касались действий над агрегациями и пустыми значениями (nulls)) и доказана 
эквивалентность этих расширенных формализмов (при этом использовался более 
элегантный, по сравнению с ранее опубликованным, метод доказательства). После 
этого семантика SQL определена с помощью отображения конструкций языка на 
расширенное исчисление, определенное ранее в этой работе. Тем не менее, 
необходимо отметить следующее: 
    1.  Обсуждаемый в работе диалект языка SQL ближе к диалектам, используемым 
в коммерческих продуктах, по сравнению с диалектами SQL, которые используются 
в [18.35-18.37]. Но этот диалект еще не стал пол-

    Глава 18. Оптимизация	511 


ностью общепринятым. Он не обладает оператором UNION и прямой поддержкой 
кванторов типа ALL, а трактовка значения неопределенности unknown отличается 
от обусловленной стандартом SQL (на самом деле эта трактовка даже лучше). 
    2,  Данная работа в целях "технического упрощения" не рассматривает методы 
контроля исключения дублирующихся кортежей. Но влияние такого пропуска не 
совсем ясно просматривается, исходя из того, что (как было показано ранее) 
наличие или отсутствие дублирующихся кортежей может значительно повлиять на 
корректность некоторых преобразований. 
    И наконец, автор работы [18.39] утверждает, что в некоторых случаях 
оригинальные алгоритмы Кима [18.35], несмотря на некорректность, могут быть 
эффективнее "общей стратегии", изложенной в [18.37]. Поэтому автор [18.39] 
предлагает альтернативный способ исправления ошибок в алгоритмах Кима. Кроме 
того, в работе представлены некоторые улучшения рассматриваемых алгоритмов. 
    18.40. Warren D.H.D. Efficient Processing of Interactive Relational 
Database Queries Expressed in Logic // Proc. 7th Intern. Conf. on Very Large 
Data Bases. — Cannes, France, 1981. 
    Представлен взгляд на оптимизацию запросов с точки зрения формальной 
логики. Описаны приемы, используемые в экспериментальной СУБД, базирующейся на 
языке Prolog. Эти приемы по-видимому очень похожи на приемы, используемые в 
System R, хотя разработаны достаточно независимо и с несколько различающимися 
целями. В работе указывается, что в отличие от обычных языков запросов, таких 
как QUEL и SQL, языки, основанные на логике, такие как Prolog, позволяют 
записывать запросы так, чтобы выделить следующее: 
    • логические цели, которые являются основными компонентами запроса; 
    • логические переменные, связывающие вместе эти компоненты; 
    • порядок достижения логических целей, который является критическим для реализации. 
    Из этого следует, что подобные языки весьма удобны в качестве базы для 
оптимизации. Действительно, этот язык можно рассматривать в качестве еще 
одного кандидата для формализма, используемого для внутреннего представления 
запроса, ранее представленного с помощью какого-либо другого формализма. 
    18.41. loannidis Y.E., Wong E. Query Optimization by Simulated Annealing 
// Proc. 1987 ACM SIGMOD Intern. Conf. on Management of Data. — San Francisco, 
Calif, 1987. 
    С ростом числа отношений, используемых в запросе, количество планов 
запроса растет экспоненциально. В традиционных коммерческих приложениях число 
отношений в запросе обычно небольшое и, следовательно, количество 
потенциальных планов запроса ("пространство поиска") остается в разумных 
пределах. Тем не менее, в будущих приложениях, таких как системы CAD/CAM, или 
дедуктивных СУБД количество отношений в запросе может быть достаточно большим. 
Более того, подобные приложения требуют "глобальной" (т.е. многозапросной) 
оптимизации [18.43] и поддержки рекурсивных запросов. Эти возможности 
значительно увеличивают пространство поиска. Исчерпывающий поиск в таких 
условиях становится неэффективным, и возникает настоятельная необходимость в 
методах сужения пространства поиска. 

    512	Часть V. Дополнительные аспекты 

    Публикация содержит ссылки на более ранние работы по проблеме оптимизации 
запросов с большим количеством отношений и многозапросной оптимизации. Однако 
в данной работе утверждается, что для оптимизации рекурсивных запросов не 
разработано ни одного алгоритма, после чего приводится алгоритм, который, как 
утверждают авторы, применим даже на пространствах поиска большого размера. В 
частности, показано, как применять изложенный алгоритм в случае рекурсивных 
запросов. Данный алгоритм (называемый "моделирование прокаливания", так как 
этот алгоритм моделирует процесс прокаливания, с помощью которого выращивают 
кристаллы, сначала прогревая жидкий раствор, а затем постепенно охлаждая его) 
является высокоэффективным алгоритмом, который успешно применяется для решения 
проблемы оптимизации в других контекстах. 
    См. также [18.42]. 
    18.42. Swami A., Gupta A. Optimization of Large Join Queries // Proc. 1988 
ACM SIGMOD Intern. Conf. on Management of Data. — Chicago, 111., 1988. 
    Основная проблема определения порядка выполнения соединения в запросах, 
использующих большое количество отношений (что характерно для дедуктивных баз 
данных), является комбинаторно сложной. В работе представлен сравнительный 
анализ нескольких алгоритмов, предназначенных для решения этой проблемы: 
возмущенный проход, псевдослучайная генерация образцов, последовательные 
улучшения, последовательные эвристики и моделирование прокаливания (названия 
добавляют немного "поэзии" в предмет обсуждения, который выглядит достаточно 
прозаично). Согласно результатам проведенного анализа алгоритм 
последовательных улучшений превосходит все остальные алгоритмы, в частности 
алгоритм моделирования прокаливания нельзя использовать на больших запросах-соединениях. 
    18.43. Sellis Т.К. Multiple-Query Optimization // ACM TODS. — 1988. — 13, 
№ 1. 
    Классическое исследование оптимизации, в котором автор сосредоточился на 
проблеме оптимизации отдельных изолированных реляционных выражений. В будущем 
возможность оптимизации различных отдельных запросов как одного модуля станет 
весьма важной. Одной из побудительных причин такой оптимизации стало то, что 
единственный запрос на верхнем уровне может быть преобразован в несколько 
запросов на реляционном уровне. В работе приведен следующий пример. Запрос на 
естественном языке "Хорошо ли оплачивается работа Майка?" может привести к 
выполнению трех отдельных запросов: 
    • "Зарабатывает ли Майк больше 40 000 долларов?" 
    • "Зарабатывает ли Майк больше 35 000 долларов, и обладает ли он опытом 
работы менее 5 лет?" 
    • "Зарабатывает ли Майк больше 30 000 долларов, и обладает ли он опытом 
работы менее 3 лет?" 
    Этот пример демонстрирует, что наборы связанных запросов обычно совместно 
используют некоторые подвыражения, поэтому приходится глобально оптимизировать 
эти наборы запросов. 
    В работе рассматриваются запросы, в которых используются только конъюнкции 
выборок и (или) соединения по эквивалентности, а также изложены некоторые 
обескураживающие результаты и направления дальнейших исследований. 

    Глава 18. Оптимизация	513 
    1 7 Введение в системы баз данных 

    18.44. Lohman G.M, Grammar-Like Functional Rules for Representing Query 
Optimization Alternatives // Proc. 1988 ACM SIGMOD Intern. Conf. on Management 
of Data, — Chicago, 111., 1988. 
    В некоторых случаях реляционные оптимизаторы можно рассматривать как 
экспертные системы. Тем не менее, правила, управляющие процессом оптимизации, 
встраиваются в процедурный код, а не отдельно и декларативно записываются. 
Вследствие этого расширение оптимизатора путем добавления новых приемов 
оптимизации —• непростая задача. Будущие "расширяемые" базы данных только 
усугубят эту проблему, так как возникнет необходимость установки 
дополнительных наборов правил, расширяющих оптимизатор. Эти правила 
предоставляют возможность, например, поддержки специфических типов данных, 
определенных пользователем. Поэтому разные исследователи предложили 
структурировать оптимизатор как экспертную систему с явно выраженными 
декларативными правилами. 
    Тем не менее, эта проблема страдает от недостатка производительности. 
Большое количество правил можно применять на любой стадии обработки запроса, и 
определение подходящего правила может потребовать достаточно сложных 
вычислений. В работе представлен альтернативный подход (в данный момент 
используемый в прототипе системы Starburst), в котором правила выражаются как 
продуктивные правила грамматики, подобной грамматикам формальных языков. Эти 
правила, называемые правилами STAR (strategy alternative rules — правила 
альтернативной стратегии), позволяют выполнять рекурсивное построение планов 
запросов из других планов и "операторов плана низкого уровня" (low-level plan 
operator — LOLEPOP), которые являются базовыми операциями для таких отношений, 
как соединение, сортировка и т.п. Каждый из операторов LOLEPOP имеет свои 
особенности. Например, оператор LOLEPOP соединения обладает возможностью 
сортировки-слияния, хеширования и т.д. 
    В работе утверждается, что изложенный выше подход имеет множество 
преимуществ: правила (STAR) легко понятны тем, кто будет создавать новые 
правила; процесс выбора правила, которое нужно применить в данной ситуации, 
более прост и эффективен по сравнению с традиционным подходом, применяемым в 
экспертных системах; кроме того, достигнуты цели расширяемости. 
    18.45. Nakano R. Translation with Optimization from Relational Calculus to 
Relational Algebra Having Aggregate Functions // ACM TODS. — 1990. — 15, № 4. 
    Как показано в главе 7, запросы на языке, базирующемся на исчислении, 
можно реализовать следующими образом: а) посредством преобразования 
рассматриваемого запроса в эквивалентное алгебраическое выражение; б) путем 
оптимизации полученного алгебраического выражения; в) реализацией этого 
оптимизированного выражения. Автор предлагает схему объединения шагов (а) и б) 
в один шаг, т.е. преобразование данного выражения в реляционном исчислении 
непосредственно в оптимальное выражение в реляционной алгебре. Утверждается, 
что эта схема "более эффективна и перспективна... так как весьма непросто 
оптимизировать сложное алгебраическое выражение". В процессе оптимизации 
используются некоторые эвристические преобразования, полученные на основе 
человеческого опыта относительно эквивалентности некоторых выражений в 
исчислении и алгебре. 
    18.46. Whang K.-Y., Krishnarnurthy R. Query Optimization in a 
Memory-Resident Domain Relational Calculus Database System // Ibid. — 1990. — 
15, № 1. 
    Наиболее дорогой аспект в обработке запросов (в средах с достаточно 
большой основной памятью, как предполагается в данной работе) — это 

    514	Часть V, Дополнительные аспекты 

вычисление условий. Поэтому в подобных средах целью оптимизации является 
минимизация количества операций вычисления условий. 
    18.47. Freytag J.C., Goodman N. On the Translation of Relational Queries 
into Iterative Programs // Ibid. — 1989. — 14, № 1. 
    Представлены методы для непосредственной компиляции реляционных выражений 
в выполняемый код на таких языках, как С или Pascal. Заметьте, что этот поход 
отличается от подхода, изложенного в данной главе, где оптимизатор 
комбинировал предварительно написанные (параметризованные) участки кода для 
построения плана запроса. 
    18.48. Опо К., Lohman G.M. Measuring the Complexity of Join Enumeration in 
Query Optimization // Proc. 16th Intern. Conf. on Very Large Data Bases. — 
Brisbane, Australia, 1990. 
    Так как операция соединения в основном является бинарной, оптимизатор 
должен разбить соединение N отношений (N> 2) на последовательность бинарных 
соединений. Большинство оптимизаторов выполняет эту операцию в строго 
"вложенном" порядке. Оптимизаторы выбирают пару отношений, которые будут 
соединены первыми, после этого соединяют результат с третьим отношением и т.д. 
Другими словами, выражение, такое как A JOIN В JOIN С JOIN D, будет 
трактоваться как (( D JOIN В ) JOIN С ) JOIN А, но ни в коем случае не как « A 
JOIN D ) JOIN ( В JOIN С ). Более того, традиционные оптимизаторы 
разрабатываются так, чтобы избегать операции декартова произведения вообще. 
Показанные тактики можно трактовать как "сужение пространства поиска", поэтому 
для выбора последовательности соединения все еще нужны эвристические методы. 
    Данная публикация также содержит описание других аспектов оптимизатора 
прототипа системы IBM Starburst. Автор аргументирует, что приведенные тактики 
в некоторых случаях неуместны, поэтому возникает необходимость в адаптируемом 
оптимизаторе, который можно заставить использовать разные тактики для 
различных запросов. 

    Замечание. В отличие от современных коммерческих программных продуктов, 
Starburst способна трактовать выражение вида R.A = S.B + с как условие 
соединения. Кроме того, эта система поддерживает свойство транзитивной 
замкнутости предикатов. 

    18.49. loannidis Y.E., Ng R.T., Shim К., Sellis Т.К. Parametric Query 
Optimization // Proc. 18th Intern. Conf. on Very Large Data Bases. — 
Vancouver, Canada, 1992. 
    Рассмотрим следующий запрос: 

    EMP WHERE SALARY > salary 

    Здесь salary (зарплата) — это параметр, действительный во время выполнения 
запроса. Предположим, что атрибут SALARY (зарплата) обладает индексом. Тогда: 
    • Если salary имеет значение 10 000 долларов в месяц, то лучшим способом 
реализации запроса является индекс (так как предположительно большинство 
сотрудников не удовлетворяют условию выборки). 
    • Если зарплата имеет значение 1 000 долларов в месяц, то лучшим способом 
реализации запроса является последовательный просмотр (так как 
предположительно все сотрудники удовлетворяют условию выборки). 
    Данный пример демонстрирует утверждение о том, что некоторые решения об 
оптимизации лучше принимать во время выполнения, даже в компилирующих 
системах. В работе исследована возможность генерации наборов 

    Глава 18. Оптимизация	515 

планов запросов во время компиляции (каждый план является "оптимальным" 
для некоторого подмножества множества всех возможных значений параметров 
времени выполнения) и выбора соответствующего плана во время выполнения, когда 
реальные значения параметров уже известны. В частности, автор обращает 
внимание на один конкретный параметр — размер пространства буфера для запроса. 
Результаты экспериментов показали, что данный подход незначительно замедляет 
процесс оптимизации и жертвует немногим в отношении качества генерируемых 
планов запросов. Поэтому автор утверждает, что данный подход может значительно 
повысить производительность запросов. "Значительный выигрыш в 
производительности можно получить от использования планов запроса, специально 
связанных с определенными значениями параметров." 
    18.50, Graefe G. Query Evaluation Techniques for Large Databases // ACM 
Сотр. Surv. — 1993.— 25, №2. 

    Ответы к некоторым упражнениям 

    18.1. а) Эквивалентны; б) эквивалентны; в) эквивалентны; г) не 
эквивалентны; д) эквивалентны; е) не эквивалентны (эти выражения будут 
эквивалентными, если заменить операцию AND на OR); ж) не эквивалентны; з) не эквивалентны. 
    18.2. В демонстрационных целях покажем, что соединение является 
коммутативным. Соединение A JOIN В отношений А{Х, Y] и A{Y, Z} — это отношение 
с заголовком {X, Y, Z} и кортежами {Х:х, Y:y, Z:z} такими, что кортеж из 
значений х и у должен присутствовать в отношении А, а кортеж из значений у и z 
должен присутствовать в отношении В. Это определение абсолютно симметрично 
относительно А и В. Поэтому A JOIN В тождественно В JOIN A. 
    18.3. Для примера покажем ассоциативность операции объединения. 
Объединение A UNION В двух отношений А и В совместимых типов — это отношение с 
тем же заголовком, что А и В, и телом, состоящим из всех кортежей /, 
принадлежащих отношению А или В или им обоим. Таким образом, если С — еще одно 
совместимое по типу отношение, то: 
    • объединение ( A UNION В ) UNION С — это отношение с тем же заголовком и 
телом, состоящим из всех кортежей t, которые принадлежат отношению A UNION В, 
отношению С или обоим; 
    • объединение A UNION ( В UNION С ) — это отношение с тем же заголовком и 
телом, состоящим из всех кортежей t, которые принадлежат отношению В UNION С, 
отношению А или им обоим. 
    Эти два отношения имеют одинаковые заголовки, а тело в каждом случае 
состоит из всех кортежей, принадлежащих хотя бы одному из отношений А, В или 
С, Поэтому приведенные отношения тождественны. 
    18.4. Покажем, что объединение распределяется по пересечению. 
    • ЕСЛИ /  е A   UNION   (   В  INTERSECT С  ), ТО t  е А ИЛИ t е В  
INTERSECT С. 
    • Если /   е  А, то t   е   A   UNION  В и t   е   A   UNION  С, 
следовательно t е 
    ( A  UNION В  )   INTERSECT   ( A  UNION С  ). 
    • ЕСЛИ t   е   В   INTERSECT  С, ТО t   е   В И t   6   С, ТОГДЗ t   е    
( A  UNION В  )   И   t е 
    ( A UNION С ). Следовательно, / е ( A UNION В ) INTERSECT ( A UNION С ). 
    • И в обратном направлении, если t е ( A UNION В > INTERSECT ( A UNION С ), 
    ТО t  €   (A   UNION В   ) И  t  е   (A   UNION С   ). Из ЭТОГО СЛСДуСТ, 
ЧТО t  е А ИЛИ t 

    516	Часть V, Дополнительные аспекты 

    принадлежит обоим отношениям В и С. Следовательно, t e A UNION  ( В 
    INTERSECT С  ). 
    18.5. Покажем, что A UNION ( A INTERSECT В ) = А. Если ; е Л, то ясно, что 
? е А UNION ( Л INTERSECT В ). И в обратном направлении, если / е Л UNION ( А 
INTERSECT В ), то t <= А или / принадлежит обоим отношениям А и б. В любом 
случае получим, что t e А. 
    18.6. В качестве примера рассмотрим распределяемость проекции по 
соединению. Проекция (A JOIN В) [X] эквивалентна соединению A[Y] JOIN B[Z] 
тогда и только тогда, когда множество атрибутов Xравно объединению множеств 
атрибутов У и Z и включает атрибуты, общие для А и В. 
    18.9. Хороший набор правил можно найти в [18.3]. 
    18.10. Хороший набор правил можно найти в [18.3]. 
    18.11. а) Получить поставщиков, расположенных не в Лондоне и не 
поставляющих деталь Р2; 
    б) получить поставщиков, которые расположены в Париже; 
    в) получить не лондонских поставщиков, таких, для которых не существует 
других поставщиков, которые поставляют меньше различных видов деталей; 
    г) получить лондонских поставщиков; 
    д) получить пустое множество поставщиков; 
    е) упрощение невозможно; 
    ж) получить пустое множество поставщиков; 
    з) получить пустое множество пар поставщиков; 
    к) получить пустое множество деталей; 
    л) получить не парижских поставщиков, таких, что не существует других 
поставщиков, которые поставляют больше различных видов деталей. 
    Заметьте, что результаты некоторых запросов (если быть точным, то 
результаты запросов (д), (ж), (з) и (к)) можно получить непосредственно из 
условий целостности. 
    18.15. Исходя из методов обработки, настоящие максимальное и минимальное 
значения иногда являются в некотором роде фиктивными. Например, максимальным 
значением атрибута "employee name" (имя сотрудника) будет строка из букв Z, а 
минимальным значением этого атрибута будет строка, составленная из пробелов. 
Оценка, например, среднего расстояния между разными значениями атрибута в 
таблице может быть вычислена некорректно, если исходить из этих значений. 

    Глава 18. Оптимизация	517 

