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

Зарабатывает ли Майк больше $75 ООО?

Зарабатывает ли Майк больше $60 ООО, и обладает ли он опытом работы менее 5 лет?

Зарабатывает ли Майк больше $45 ООО, и обладает ли он опытом работы менее 3 лет?

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

В работе рассматриваются запросы, в которых используются только конъюнкции выборок и (или) соединения по эквивалентности, а также излагаются обнадеживающие результаты и предлагаются направления дальнейших исследований. 17.50,Lohman G.M. Grammar-Like Functional Rules for Representing Query Optimization Alternatives Proc. 1988 ACM SIGMOD Intem. Conf on Management of Data.- Chicago, 111., June, 1988.

В некоторых случаях реляционные оптимизаторы можно рассматривать как экспертные системы. Тем не менее исторически сложилось так, что правила, управляющие процессом оптимизации, встраиваются непосредственно в процедурный код, а не записываются отдельно в декларативном виде. Вследствие этого расширение оптимизатора путем добавления новых приемов оптимизации - непростая задача. Будущие системы баз данных (глава 25), видимо, еще больше усугубят эту проблему, так как явно просматривается необходимость индивидуальной установки дополнительных наборов правил, расширяющих возможности оптимизатора для поддержки определенных пользователем специальных типов данных. Поэтому разные исследователи предложили структурировать оптимизатор как экспертную систему с использованием явно выраженных декларативных правил. Однако эта идея страдает недостаточной производительностью. В частности, на любой стадии обработки запроса может применяться большое количество правил, и поиск подходящего правила может потребовать достаточно сложных вычислений. В этой работе представлен альтернативный подход (в данный момент используемый в прототипе системы Starburst [25.14], [25.17], [25.21], [25.22]), в котором правила определяются посредством продуктивных правил грамматики, подобной грамматикам формальных языков. Эти правила, называемые правилами STAR (STrategy Alternative Rules - правила альтернативной стратегии), позволяют осуществлять рекурсивное построение планов выполнения запросов из других планов и операторов плана нижнего уровня (low-level plan operator - LOLEPOP), которые являются базовыми операциями над отношениями, такими

как соединение, сортировка и т.п. Каждый из LOLEPOP-операторов имеет свои подвиды. Например, LOLEPOP-оператор соединения имеет подвиды сортировки-слияния, хеширования и т.д.

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

17.51.Nakano R. Translation with Optimization from Relational Calculus to Relational Algebra Having Aggregate Functions ACM TODS. - December, 1990. - 15, 4. Как показано в главе 7 (раздел 7.4), запросы на языке, базирующемся на реляционном исчислении, можно реализовать посредством преобразования исходного запроса в эквивалентное алгебраическое выражение с последующей оптимизацией полученного алгебраического выражения, которая завершается выполнением этого оптимизированного выражения. Автор предлагает схему объединения первого и второго этапов, т.е. преобразование данного выражения реляционного исчислении непосредственно в оптимальное выражение в реляционной алгебре. Утверждается, что эта схема более эффективна и перспективна... так как сложное алгебраическое выражение оптимизировать весьма непросто . В процессе оптимизации используются некоторые эвристические преобразования, построенные на основе уже имеющихся знаний об эквивалентности некоторых выражений в исчислении и алгебре.

17.52. Whang K-Y., Krishnamurthy R. Query Optimization in a Memory-Resident Domain Relational Calculus Database System ACM TODS. - March, 1990. - 15, Kq i. Наиболее дорогой аспект в обработке запросов (в средах с достаточно большой основной памятью, как предполагается в данной работе) - вычисление логических выражений. Поэтому в подобных средах целью оптимизации является минимизация количества таких вычислений.

17.53,Freytag J.C., Goodman N. On the Translation of Relational Queries into Iterative Programs ACM TODS. - March, 1989. - 14, 1.

Представлены методы непосредственной компиляции реляционных выражений в выполняемый код на таких #1зыках, как С и Pascal. Заметьте, что этот поход отличается от подхода, изложенного в данной главе, где оптимизатор для создания плана выполнения запроса комбинировал предварительно написанные (параметризованные) фрагменты кода.

17.54.Ono К., Lohman G.M. Measuring the Complexity of Join Enumeration in Query Optimization Proc. 16th Intern. Conf on Very Large Data Bases.- Brisbane, Australia, August, 1990.

Так как операция соединения в своей основе является бинарной, оптимизатор должен разбить соединение N отношений (N > 2) на последовательность бинарных соединений. Большинство оптимизаторов выполняет эту операцию в строго вложенном порядке. Оптимизаторы выбирают пару отношений, которые будут соединены первыми, после чего соединяют результат с третьим отношением и т.д. Другими словами, выражение, подобное А JOIN В JOIN С JOIN D, будет трактоваться как (( D JOIN В ) JOIN С ) JOIN А, но ни в коем случае не как ( А JOIN D ) JOIN

( в JOIN С ). Более того, традиционные оптимизаторы разрабатываются так, чтобы вообще исключить выполнение операции декартова произведения. Показанные приемы можно трактовать как сужение пространства поиска , поэтому для выбора последовательности соединения все еще нужны эвристические методы. В данной публикации также содержится описание других аспектов оптимизатора прототипа системы IBM Starburst [17.50], [25.14], [25.17], [25.21], [25.22]. Автор аргументирует это тем, что приведенные тактики в некоторых случаях неуместны, поэтому возникает необходимость в адаптируемом оптимизаторе, который можно заставить использовать разные тактики для различных запросов.

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

17.55. Vance В., Maier D. Rapid Bushy Join-Order Optimization with cartesian Products Proc. 1996 ACM SIGMOD Int Conf, on Management of Data. - Montreal, Canada, June, 1996. Как сказано в комментарии к предыдущей ссылке, оптимизаторы стремятся сократить пространство поиска (помимо всего прочего) за счет исключения планов выполнения запросов, в которых используется декартово произведение. В этой статье показано, что поиск во всем пространстве допустим в большей степени, чем это признавалось прежде , а исключение декартова произведения не всегда желательно. Согласно утверждениям авторов, основными результатами этой статьи являются полное отделение определения порядка соединения от анализа предикатов и представление новых технологий реализации для решения проблемы определения порядка соединения.

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

EMP WHERE SALARY > <зарплата>

Здесь параметр <зарплата> задается во время выполнения запроса. Предположим, что атрибут SALARY (зарплата) обладает индексом. Тогда получаем следующее.

Если параметр <зарплата> имеет значение $10 ООО в месяц, то лучшим способом реализации запроса является индекс (так как можно предположить, что большинство сотрудников не удовлетворяют условию выборки).

Если параметр <зарплата> имеет значение $ 1 ООО в месяц, то лучшим способом реализации запроса будет последовательный просмотр (так как можно предположить, что практически все сотрудники будут удовлетворять условию выборки).

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