Введение в системы БД (542480), страница 165
Текст из файла (страница 165)
Для каждой низкоуровневой операции (а также, возможно, для нескольких часто встречающихся комбинаций подобных операций) оптимизатор имеет набор низкоуровневых процедур реализации. Например, существует набор процедур для реализации операции выборки: по условию равенства определенному значению потенциального 645 Глава 17. Оптимизация ключа; на основе инлексированного атрибута, по которому выполняется выборка; на основе хешированного атрибута и т.д. Примеры таких процедур приведены ниже, в разделе 17.7 (см, также [! 7.8)-[17.14]). С каждой процедурой связана и параметризованная формула стоимости, позволяющая оценить стоииосшь выполнения процедуры (т.е. уровень затрат, требуемых для ее выполнения). Чаще всего стоимость определяется на основе подсчета количества необходимых дисковых операций ввода-вывода, но некоторые системы учитывают также время использования процессора и другие факторы.
Эти формулы стоимости применяются на стадии 4. В [17.8) — [17.14) обсуждаются и анализируются формулы стоимости для различных процедур реализации при разных исходных предположениях. Далее, используя сохраняемую в каталоге информацию о состоянии базы данных (существующие индексы, текущую кардинальность переменных-отношений и т,п.) и сведения о взаимозависимостях, упоминавшихся выше, оптимизатор выбирает одну или несколько процедур-кандидатов для каждой низкоуровневой операции в запросе. Этот процесс обычно называют выбором пути доступа (см.
также [17.34), [! 7.35)). Заиечание. Следует отметить, что в [17.34), [! 7.35) приведенный термин используется для ссылки на определенные в данной главе стадии 3 и 4, а не только на стадию 3. Действительно, на практике очень трудно разграничить, где заканчивается одна стадия и начинается другая: просто стадия 3 плавно переходит в стадию 4. Стадия 4. Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами На последней стадии процесса оптимизации создается набор потенциальных планов запроса, после чего следует выбор лучшего (т.е.
наименее дорогого) плана выполнения запроса. Каждый план выполнения строится как комбинация некоторого набора процедур реализации, причем каждой низкоуровневой операции в запросе соответствует одна процедура. Заметьте, что обычно для поступившего запроса вырабатывается множество планов выполнения запроса (возможно, даже слишком много). На практике, вероятно, не стоит генерировать все возможные планы запроса, так как одни из ннх могут быть комбинаторными версиями других планов выполнения этого же запроса и сам процесс выбора наиболее дешевого плана может стать чрезмерно дорогостоящим.
При выборе плана с наименьшей стоимостью рекомендуется (возможно, даже необходимо) руководствоваться некоторыми эвристическими правилами, позволяющими ограничить количество анализируемых планов запросов разумными пределами [17.55). Практику ограничения количества запросов разумными пределами иначе называют сокращение.и пространства поиска, поскольку ее можно рассматривать и как уменьшение диапазона (" пространства" ) анализируемых оптимизатором вариантов ("поиск") до контролируемых пределов.
Несомненно, для выбора плана с наименьшей стоимостью необходим метод определения стоимости любого возможного плана. По сути, стоимость плана — это просто сумма стоимостей отдельных процедур, входящих в его состав. Поэтому задача оптимизатора сводится к вычислению формул стоимости для каждой отдельной процедуры. Основная проблема состоит в том, что стоимость выполнения процедуры зависит от размера отношения (или отношений), которое эта процедура обрабатывает.
Так как все запросы, за исключением самых простых, требуют создания некоторых промежуточных ре- 646 Часть г'. Дополнительные аспекты зультатов выполнения, оптимизатор должен суметь оценить размер этих результатов и использовать полученные значения при вычислении формул стоимости. К сожалению, размеры промежуточных наборов данных сильно зависит от конкретных значений хранимых данных, поэтому точная оценка стоимости может оказаться достаточно сложной проблемой. В [!7.3], [!7.4] обсуждаются некоторые подходы к решению этой проблемы и приводятся ссылки на другие направления исследований. 17.4.
Преобразование выражений В этом разделе обсуждаются правила преобразования, которые могут оказаться полезными на стадии 2 процесса оптимизации. Подбор примеров и выяснение, чем именно эти правила могут быть полезны при оптимизации, оставляются в качестве упражнений для читателя. Конечно, читатель должен понимать, что в результате применения к какому-либо выражению одного правила преобразования может быть получено выражение, к которому применимо другое правило преобразования.
Например, среди исходных запросов нечасто встречаются запросы, сформулированные с использованием двух последовательно выполняемых операций проекции (речь об этом пойдет ниже; см. второе правило из подраздела об операциях выборки и проекции). Однако при преобразовании запросов подобные выражения достаточно часто возникают как результат применения других правил преобразования.
(В этом смысле очень важным случаем является обработка представлений. Например, рассмотрим запрос "Выбрать все названия городов в представлении Ч", где представление Ч определено как проекция переменной-отношения поставщиков по атрибутам Н]) и С1гз.) Иначе говоря, начиная с исходного выражения, оптимизатор будет шаг за шагом применять различные правила преобразования до тех пор, пока не будет получено выражение, которое согласно встроенным в оптимизатор эвристическим правилам будет считаться "оптимальным" лля рассматриваемого запроса.
Выборки и проекции Начнем с правил преобразования, которые включают только операции выборки и проекции. !. Последовательность операций выборки из одного и того же отношения может быть заменена единственной операцией выборки из этого отношения (причем условные выражения всех исходных операций с помошью операций АНР объединяются в одно условное выражение). Например, выражение ( а ИНЕЕЕ <виборка1> ) ИНЕНЕ <виборка2> эквивалентно выражению й ИНЕНЕ <виборка1> АКР <виборка2> 2. В последовательности операций проекций для одного и того же отношения можно игнорировать все проекции, кроме последней. Таким образом, выражение ( а ( <лроекция1> ) ) ( <проекция2> ) эквивалентно выражению а ( <цроекция2> ) 647 Глава 1 7.
Оптимизация Конечно, чтобы исходное выражение имело смысл, каждый атрибут, присутствуюшнй в проекции <проекцля2>, обязательно должен присутствовать и в проекции <проекция!>. 3. Операцию выборки из результата операции проекции можно преобразовать в операцию проекции для результата операции выборки. Например, выражение ( а ( <проекция> ) ) ИНЕНЕ <вяборка> эквивалентно выражению ( л МНЕНЕ <либорка> ) ( <проекцля> ) Обратите внимание, что, как правило, операцию выборки целесообразно выполнять перед операцией проекции, поскольку операция выборки обычно приводит к уменьшению объема тех данных, которые будут являться входными для операции проекции. Слеловательно, в этом случае уменьшается количество данных, которые потребуется сортировать для исключения возможных дублирующихся записей, образующихся в процессе выполнения операции проекции.
Распределительный закон Правило преобразования, которое использовано в примере, приведенном выше, в разделе! 7.2 (преобразование операции соединения с послелуюшей операцией выборки в операцию выборки с последуюшей операцией соединения), на самом деле является частным случаем более обшего правила, называемого распределительны н законом. Говорят, что унарный оператор 1 распределяется по бинарной операции О тогда и только тогда, когда для всех А и В выполняется следуюшее тождество.
1 ( А О В ) ж 1 ( А ) О 1 ( В ) Например, в обычной арифметике операция НОНА (извлечение квадратного корня) распределяется по операции умножения, так как для всех А и В выполняется приведенное ниже тождество. ЯННТ ( А Я В ) и ЯЯНТ ( А ] * ВАНТ ( В ) Следовательно, выполняя преобразование выражений, оптимизатор арифметических выражений всегда может заменить одну часть этого равенства другой. В качестве обратного примера можно привести утверждение, что операция Я()НТ не распределяется по операции сложения, так как в большинстве случаев квадратный корень из суммы А + В не равен сумме квадратных корней из А и В. В реляционной алгебре операция выборки распределяется по операциям объединения, пересечения и вычитания. Она также распределяется по операции соединения, но лишь тогда и только тогда, когда условие операции выборки состоит (в самом сложном случае) из двух отдельных условий, соединенных операцией АМ — по одному условию выборки для каждого операнда операции соединения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
