Введение в системы БД (542480), страница 177
Текст из файла (страница 177)
Выдача на естес~асином языке запроса "Хорошо ли оплачивается работа Майка?" может привести к выполнению трех отдельных реляционных запросов. ° Зарабатывает ли Майк больше $75 000? ° Зарабатывает ли Майк больше $60 000, и обладает ли он опытом работы менее 5 лет? И Зарабатывает ли Майк больше $45 000, и обладает ли он опытом работы менее 3 лет? Этот пример демонстрирует, что наборы связанных запросов обычно совместно используют некоторые подчиненные выражения, поэтому подобные наборы запросов приходится оптимизировать глобально.
В работе рассматриваются запросы, в которых используются только конъюнкции выборок и (нлн) соединения по эквивалентности, а также излагаются обнадеживающие результаты и предлагаются направления дальнейших исследований. 17.50.ЬоЬгпап О.М. Огапппаг-Ьйе Рцпсцопа! Кц!ез Гог йергевепг!п8 Оцегу Орйпнхайоп А!сегпайчез д Ргос. 1988 АСМ $!ОМОР 1пгегп. СопГ, оп Мапайешепг ог" Рага.— СЬ!са8о, 1! !., )цпе, 1988. В некоторых случаях реляционные оптимизаторы можно рассматривать как экспертные системы.
Тем не менее исторически сложилось так, что правила, управляющие процессом оптимизации, встраиваются непосредственно в процедурный код, а не записываются отдельно в декларативном виде. Вследствие это~о расширение оптимизатора путем добавления новых приемов оптимизации — непростая задача. Будущие системы баз данных (глава 25), видимо, еше больше усугубят эту проблему, так как явно просматривается необходимость индивидуальной установки дополнительных наборов правил, расширяющих возможности оптимизатора для поддержки определенных пользователем специальных типов данных. Поэтому разные исследователи предложили структурировать оптимизатор как экспертную систему с использованием явно выраженных декларативных правил. Однако эта идея страдает недостаточной производительностью.
В частности, на любой сталин обработки запроса может применяться большое количество правил, и поиск подходящего правила может потребовать достаточно сложных вычислений. В этой работе представлен альтернативный подход (в данный момент используемый в прототипе системы БгагЬцгм !25.14Ь (25.17), !25.21], (25.22)), в котором правила определяются посредством продуктивных правил грамматики, подобной грамматикам формальных языков. Эти правила, называемые правилами БТАй (БТгагейу Айегпаггче Кц)ез — правила альтернативной стратегии), позволяют осуществлять рекурсивное построение планов выполнения запросов из других планов и "операторов плана нижнего уровня" (!озч-!ече! р!ап орега!ог— ЬОЬЕРОР), которые являются базовыми операциями над отношениями, такими 68б Часть р'.
дополнительные аспекты как соединение, сортировка и т.п. Каждый нз ЕОЕЕРОР-операторов имеет свои подвиды. Например, ЕОЕЕРОР-оператор соединения имеет подвиды сортировки- слияния, хеширования и т.д. В работе утверждается, что изложенный выше подход имеет множество преимушеств: правила (БТАК) легко понятны тем, кто будет создавать новые правила; процесс выбора правила, которое нужно применить в конкретной ситуации, проще н эффективнее по сравнению с традиционным подходом, применяемым в экспертных системах; кроме того, достигнута возможность расширяемости. 17.51.Ыакапо К. Тгапа!абоп зн!1Ь Оргшпгайоп (гош Ке!айопа! Са!си!из го Ке!агюпа! А!МеЬга Наи(пй А88ге8аге Рипсйопз /! АСМ ТОРБ. — РесещЬег, 1990.
— 15, № 4. Как показано в главе 7 (раздел 7.4), запросы на языке, базирующемся на реляционном исчислении, можно реализовать посредством преобразования исходного запроса в эквивалентное алгебраическое выражение с последующей оптимизацией полученного алгебраического выражения, которая завершается выполнением этого оптимизированного выражения. Автор предлагает схему объединения первого и второго этапов, т.е. преобразование данного выражения реляционного исчислении непосредственно в оптииальное выражение в реляционной алгебре.
Утверждается, что эта схема "более эффективна и перспективна... так как сложное алгебраическое выражение оптимизировать весьма непросто". В процессе оптимизации используются некоторые эвристические преобразования, построенные на основе уже имеющихся знаний об эквивалентности некоторых выражений в исчислении и алгебре. 17.52.%Ьапй К-У., Кпкйпашшйу К, ()негу Орйп!гайоп (п а Мешогу-КезЫеп! Роща(п Ке!ацопа1 Са!си!иа РагаЬазе Бумеш й АСМ ТОРБ. — Магсй, 1990. — ! 5, № 1, Наиболее дорогой аспект в обработке запросов (в средах с лостаточно большой основной памятью, как предполагается в данной работе) — вычисление логических выражений.
Поэтому в подобных средах целью оптимизации является минимизация количества таких вычислений. 17.53.Ргеугай ЕС., Ооос(шап Ы. Оп йе Тгапз!агюп о( Ке!айопа! Оиепез (пго 1гегаг(ие Ргобгащз й АСМ ТОРБ. — Магсй, 1989. — 14, № 1. Представлены методы непосредственной компиляции реляционных выражений в выполняемый код на таких языках, как С и Рааса!. Заметьте, что этот поход отличается от подхода, изложенного в данной главе, где оптимизатор для создания плана выполнения запроса комбинировал предварительно написанные (параметризованные) фрагменты кода.
17.54.Опо К., Еойшап О.М. Меазиппй йе Сошр!ех!гу ог" 3о(п Епшпегайоп !и Оиегу Орбгпггагюп 0 Ргос. !бй !и!егп, Сопб оп Чету Еаг8е Раса Вазез.— ВпзЬапе, Аизгга!!а, Аи8изг, 1990. Так как операция соединения в своей основе является бинарной, оптимизатор должен разбить соединение М отношений (М > 2) на последовательность бинарных соединений. Большинство оптимизаторов выполняет эту операцию в строго "вложенном" порялке. Оптимизаторы выбирают пару отношений, которые будут соелинены первыми, после чего соединяют результат с третьим отношением и т.д. Другими словами, выражение, подобное й 101М В 001М С 101М О, будет трактоваться как (( 0 101М В ) 001М С ) 001М й, но нн в коем случае не как ( й Л01М 0 ) 001М Глава 17. Опт имизаг(ия 687 ( В 0018 С ) . Более того, тралиционные оптимизаторы разрабатываются так, чтобы вообще исключить выполнение операции декартова произведения.
Показанные приемы можно трактовать как "сужение пространства поиска", поэтому для выбора последовательности соединения все еше нужны эвристические методы. В данной публикации также содержится описание других аспектов оптимизатора прототипа системы 1ВМ БгагЬцгзг [17.50), [25.14), [25.17), [25.21), [25.22). Автор аргументирует это тем, что приведенные тактики в некоторых случаях неуместны, поэтому возникает необходимость в адаптируеиои оптимизаторе, который можно заставить использовать разные тактики для различных запросов.
Заиечание. В отличие от типичных современных коммерческих программных продуктов, система 5!агЬогм способна трактовать выражение вида Е.А = Я.В + с как условие "соелинения". Кроме того, она поддерживает свойство "транзитивной замкнутости предикатов" (см. раздел ! 7.4). 17.55.Чалое В., Ма(ег О. КарЫ Вцьйу !о(п-Огдег Оргптпгаг!оп зч(гЬ саггегйап Ргодцсгз 0 Ргос. 1996 АСМ $1ОМОО 1пг СопГ оп Мапачещепг оГ ()ага. — Мопггеа!, Склада, )цпе, ! 996.
Как сказано в комментарии к предыдущей ссылке, оптимизаторы стремятся "сократить пространство поиска" (помимо всего прочего) за счет исключения планов выполнения запросов, в которых используется декартово произведение. В этой статье показано, что поиск во всем пространстве "допустим в большей степени, чем это признавалось прежде", а исключение декартова произведения не всегда желательно. Согласно утверждениям авторов, основными результатами этой статьи являются полное отделение определения порядка соединения от анализа предикатов и прелставление "новых технологий реализации" для решения проблемы определения порядка соединения. 17.56йоаппЫВ У.Е., ХЕ К.Т., Янш К,, Бей!з Т.К. Рагащеггк Олегу Орйпнка!юп д Ргос.
18!Ь !пгегп. СопГ. оп Чету Еагйе Оа!а Вазез. — Чапсоцчег, Сапада, Ацйцзй 1992. Рассмотрим следующий запрос. ЕКР ИНЕЕЕ БАБАЕВ > <зарплата> Здесь параметр (зарплата> задается во время выполнения запроса. Предположим, что атрибут ЕАЬАЕУ (зарплата) обладает индексом. Тогда получаем следующее.
В Если параметр <зарплата> имеет значение $10 000 в месяц, то лучшим способом реализации запроса является индекс (так как можно предположить, что большинство сотрудников не удовлетворяют условию выборки), И Если параметр <зарллата> имеет значение $1 000 в месяц, то лучшим способом реализации запроса будет последовательный просмотр (так как можно предположить, что практически все сотрудники будут удовлетворять условию выборки).
Данный пример демонстрирует утверждение о том, что некоторые решения об оптимизации лучше принимать во время выполнения, даже в компилирующих системах. В работе исследована возможность генерации наборов планов выполнения запросов во время компиляции (каждый план является "оптимальным" для некоторого подмножества из множества всех возможных значений параметров времени выполнения) и выбора соответствующего плана во время выполнения, когда реальные значения параметров уже известны.
В частности, автор обращает внимание на один конкретный параметр — размер пространства буфера для запроса. Результа- 688 Часть 1'. Дополнительные аспекты ты экспериментов показали, что данный подход незначительно замедляет процесс оптимизации и жертвует немногим в отношении качества генерируемых планов запросов. Поэтому автор утверждает, что данный подход может существенно повысить производительность обработки запросов.
"Значительный выигрыш в производительности можно получить от использования планов запросов, непосредственно связанных с определенными значениями параметров." 17.57.КаЬга Х., Ре%!и Р.). Ей~с!епс МЫ-Оцегу Ке-Орйппкайоп о/ бцЬ-Ор!нпа1 снегу Ехесцйоп Р!апз // Ргос. 1998 АСМ 81ОМОР 1ш. Сопб оп Мапа8ешеп! об Раса,— беац!е, %аэЬ., )цпе, ! 998. 17.58.Оглу 1. Рага!!е) РагаЬазе 5уыешз 10! // Ргос.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
