17.2. Пример выполнения оптимизации

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

( ( SP JOIN S ) WHERE Pi = Р# ( Р2 ) ) { SNAME }

Предположим, что в базе данных содержится информация о 100 поставщиках и 10 ООО поставках деталей, из которых только 50 включают партии деталей с номером Р2. Предположим для простоты, что переменные-отнощения S и SP сохраняются на диске, как два отдельно хранимых файла, в каждой записи которых помещается по одному кортежу данных. В этом случае, если система будет вычислять данное выражение прямо (т.е. вообще без оптимизации), последовательность выполняемых операций будет такой.

1. Соединение переменных-отношений SP и S (по атрибуту 8#). При выполнении этой операции потребуется считать информацию о 10 000 поставках партий деталей и 10 ООО раз считать информацию о 100 поставщиках (один раз для каждой поставки деталей). В результате будет получен промежуточный набор данных, содержащий 10 ООО соединенных кортежей. Этот набор данных записывается на диск (предположим, что для размещения промежуточного результата в основной (оперативной) памяти не хватает места).

2. Выборка из полученного на этапе 1 результата кортежей с данными о детали с номером Р2. На этом этапе выполняется чтение 10 ООО соединенных кортежей обратно в оперативную память, причем полученный результат состоит только из 50 кортежей, которые, по нашему предположению, вполне могут поместиться в оперативной памяти.

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

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

1. Выборка из переменной-отношения SP кортежей с данными только о детали с номером Р2. На этом этапе выполняется чтение 10 ООО кортежей и создается результирующий набор, состоящий только из 50 кортежей, который, как мы предполагаем, может поместиться в оперативной памяти.

2. Соединение полученного на этапе 1 результата с переменной-отношением S (по атрибуту S#). На этом этапе выполняется считывание данных обо всех 100 поставщиках (но только один раз, а не по одному разу для каждой поставки партии деталей, так как данные обо всех поставленных партиях деталей с номером Р2 уже находятся в оперативной памяти). Результат содержит 50 соединенных кортежей (которые также помещаются в оперативной памяти).

3. Выполнение проекции по атрибуту SNAME результата, полученного на этапе 2

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

В первой из показанных процедур в целом выполняется 1 030 ООО операций ввода-вывода кортежей, в то время как во второй процедуре выполняется только 10 100 операций ввода-вывода. Следовательно, совершенно очевидно, что если принять в качестве меры оценки производительности количество выполненных операций ввода-вывода кортежей, то вторая процедура в 100 раз эффективнее первой. (На практике мерой оценки производительности служит количество операций ввода-вывода страниц, а не отдельных кортежей, но для данного примера это уточнение можно игнорировать.) Кроме того, вполне понятно, что предпочтительнее реализовать данный запрос именно с помощью второй процедуры, а не первой!

Приведенный пример показывает, что следствием даже незначительных изменений в алгоритме реализации (выполнения выборки, а затем соединения вместо соединения и последующей выборки) может быть существенное увеличение производительности. Производительность повысится еще больше, если переменная-отношение SP будет индексирована или хеширована по атрибуту Р. В этом случае количество кортежей, считываемых на этапе 1 второй процедуры, уменьшится с 10 ООО до всего лишь 50, в результате чего вся процедура окажется в 7 ООО раз эффективнее ее исходного варианта. Аналогично этому наличие индекса или хеш-таблицы для атрибута S.Sl позволит уменьшить количество операций ввода-вывода кортежей на этапе 2 со 100 до 50, в результате чего процедура вычисления запроса окажется более чем в 10 ООО раз эффективнее исходного варианта. Это означает, что если на вычисление исходного варианта реализации запроса потребуется 3 часа, то оптимизированная версия этого же запроса будет выполнена за одну секунду. К тому же, безусловно, возможны и многие другие улучшения.

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

17.3. Оптимизация запросов

Рассмотрим четыре стадии процесса оптимизации запросов, который схематически представлен на рис. 17.1.

1. Преобразование запроса во внутреннюю форму.

2. Преобразование запроса в каноническую форму.

3. Выбор потенциальных низкоуровневых процедур.

4. Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами.

Перейдем к подробному рассмотрению каждой стадии процесса оптимизации.

(Исходный запрос )

Сканирование, обработка представлений, трансляция

Откомпилированный Выражение

реляционной алгебры

етаданны-

Преобразование выражения, оценка стоимости выполнения и т.д.

База ланныху

---- План

выполнения запроса Оптимизированный код

Данны

Выполнение

езульт

Рис. 17.1. Общая схема процесса оптимизации запроса

Стадия 1. Преобразование запроса во внутреннюю форму

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

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

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