Введение в системы БД (542480), страница 164
Текст из файла (страница 164)
Это означает, что если на вычисление исходного варианта реализации запроса потребуется 3 часа, то оптимизированная версия этого же запроса будет выполнена за одну секунду. К тому же, безусловно, возможны и многие другие улучшения. Несмотря на то что приведенный выше пример достаточно прост, он весьма наглядно демонстрирует необхолимость использования оптимизации. Кроме того, он демонстрирует вероятные типы улучшений, которые могут применяться на практике. В следующем разделе используется более систематический подход к решению проблемы оптимизации.
В частности, в нем показано, как общая проблема может быть разделена на последовательность из нескольких более или менее независимых подзадач. Это позволит нам перейти к рассмотрению отдельных стратегий и приемов оптимизации, обсуждаемых в последующих разделах. 17.3. Оптимизация запросов Рассмотрим четыре стадии процесса оптимизации запросов, который схематически представлен на рис. 17.1. 1.
Преобразование запроса во внутреннюю форму. 2. Преобразование запроса в каноническую форму. 3. Выбор потенциальных низкоуровневых процелур. 4. Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами. Перейдем к подробному рассмотрению каждой стадии процесса оптимизации. б42 Часть г'. Дополнипзельные аспекты Сканирование, обработка представлений, трансляция Выражение реляционной алгебры Преобразование выражения, оценка стоимости выполнения и т.д. Оптимизированный код Выполнение Результат )тис, ! 7.
!. Общая схеиа процесса оптимизации зал!роса Стадия 1. Преобразование запроса во внутреннюю форму На этой стадии выполняется преобразование запроса в некоторое внутреннее представление, более удобное для машинных манипуляций. В результате из рассмотрения полностью исключаются конструкции сугубо внешнего уровня (например, разнообразные варианты конкретного синтаксиса используемого языка запросов) и готовится почва для последующих стадий оптимизации, Затгечоиие. Обработка представлений (т.е.
процесс замены ссылок на прелставления выражениями, определяющими соответствующие представления) также выполняется на этом этапе. Возникает очевидный вопрос: "Какое формальное представление должно использоваться для внутреннего представления запросаТ'.
Независимо от того, какой именно вариант формального представления будет выбран, он должен быть лостаточно полным, чтобы допускать представление любых запросов, которые могут быть определены на внешнем языке системы. Кроме того, выбранный способ формального представления должен быть нейтральным, насколько это возможно, в том смысле, что он не должен заранее предопределять последующих оптимизационных решений. Чаше всего для внутреннего представления запросов используется та или иная модификация абстрактного синтаксического дерева, которое в этом случае называется деревом запроса. Например, на рис. 17.2 показано дерево лля запроса, рассматривавшегося выше в этой же главе (" Определить имена поставщиков детали с номером 'Р2"'). б43 Глава 17.
Оппгилгизауил Рис, ! 7.2. Дерево реализации запроса "Определить имена настави(иков детали с номером 'Р2'" Однако для наших целей удобнее всего будет предположить, что для внутреннего представления запросов используется один из тех формальных методов, с которыми мы уже знакомы: реляционная алгебра или реляционное исчисление. В этом случае дерево запроса, подобное представленному на рис. 17.2, можно будет рассматривать просто как альтернативный схематический вариант представления некоторого выражения, записанного в нотации одного из двух предложенных выше формальных методов (реляционная алгебра или реляционное исчисление).
Предположим, что выбранный формальный метод — реляционная алгебра. С этого момента будем считать, что внутренним представлением дерева запроса, показанного на рис. 17.2, является следующее алгебраическое выражение, ( ( БР Ю01Н Б ) ННЕНЕ Р3 и Р(( ( 'Р2' ) ) ( БНАНЕ ) Стадия 2. Преобразование запроса в каноническую форму На этой стадии оптимизатор выполняет несколько операций оптимизации, которые "гарантированно являются хорошими" независимо от реальных значений данных и сушествующих путей доступа к ним. Суть в том, что обычно реляционные языки позволяют сформулировать любые запросы (за исключением разве что простейших) несколькими разными (по крайней мере, внешне) способами. Например, даже простой запрос "Определить имена поставщиков детали с номером 'Р2'" на языке ЯО(, может быть записан буквально десятками способов', не считая таких тривиальных вариантов, как за- мена А = В на В = А или р АНВ и на ц АНР р.
Производительность вычисления запроса не должна зависеть от формы записи запроса, которую выбрал пользователь. Поэтому следующий этап в обработке запроса — преобразование его внутреннего представления в некоторую эквивалентную каноническую форму (см. ниже). Назначением данного преобразования является исключение внешних различий в эквивалентных представлениях запроса и, что более важно, поиск представления запроса, в некотором смысле более эффективного по сравнению с исходным представлением. > Следует заметить, что язык 5ОА исключительно предрасположен к этол~у (ель упр. 7.!2 в главе 7, и также (Д(8)).
Другие языки (ниприлэер, языки реляционной алгебры или исчисления) обычно не позволяют создать такое же количество эквивалентных по результат> выражений. Эта излишняя "гибкость" языка 5ОЛ на салом деле усложняет жизнь разработчикам (а не пользователям), поскольку суичесювенно усложняет алгоритм оптимизатора.
б44 Часть >'. Дополнительные аспекты Замечание о канонической форме, Понятие канонической форны является центральным во многих разделах математики и связанных с ней дисциплинах. Каноническая форма может быть определена следующим образом. Пусть Π— множество объектов (запросов), и пусть существует понятие об их эквивалентности (а именно: запросы о1 и г)2 эквивалентны тогда и только тогда, когда дают идентичные результаты). Тогда подмножество С множества О является подмножеством канонических форм для запросов из множества 9 в смысле определенной выше эквивалентности тогда и только тогда, когда каждому объекту и из множества !) соответствует только один объект с из множества С. В этом случае говорят, что объект с является канонической формой объекта о.
Все "интересуюшие" свойства, которыми обладает объект о, также присуши объекту с. Поэтому, чтобы доказать различные "интересуюшие" результаты, достаточно изучить менее мощное множество объектов С, а не более мощное множество 9. Вернемся к основной теме обсуждения. Чтобы преобразовать результаты выполнения стадии 1 в некоторую эквивалентную, но более эффективную форму, оптимизатор использует определенные и хорошо известные правила преобразования, или законы. Ниже приведен пример такого правила.
Здесь выражение ( А Ю01Н В ) ННЕЕЕ <выборка из> А может быть преобразовано в эквивалентное, но более эффективное выражение ( А ИНЕЕЕ <выборка яз> А ) 101Н В Подобное преобразование кратко рассматривалось в разделе 6.6. Кроме того, оно было приведено несколько выше, при обсуждении примера в разделе 17.2, который ясно продемонстрировал, зачем нужны подобные преобразования. Многие другие правила преобразования описываются ниже, в разделе 17.4. Стадия 3.
Выбор потенциальных низкоуровневых процедур После преобразования внутренней формы запроса в более подходящую (каноническую) форму оптимизатор должен решить, как следует выполнять запрос, представленный в этой канонической форме. На данной стадии принимаются во внимание наличие индексов и других путей доступа, статистическое распределение существующих значений данных, физическая кластеризация хранимых данных и т.п. Обратите внимание, что на стадиях 1 и 2 этим аспектам совсем не уделялось внимания. Основная стратегия состоит в том, чтобы рассматривать выражение запроса как серию низкоуровневых операций (соедннения, выборки и т.п.), которые в определенной степени зависят одна от другой. Ниже приведен пример такой зависимости.
При программной реализации выполнения проекции обычно требуется, чтобы считываемые кортежи следовали в определенном порядке; это позволит исключить дублируюшиеся результирующие кортежи. В свою очередь, это означает, что выполняемая непосредственно перед проекцией операция должна выдавать выходные кортежи именно в такой, требуемой последовательности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
