17.18.Smith J.M., Yen-Tang Chang P. Optimizing the Performance of a Relational Algebra Database Interface CACM. - October, 1975. - 18, № 10.

Описан алгоритм, использовавшийся в языке Smart Query Interface for a Relational Algebra (SQUIRAL). Этот алгоритм включает следующее.

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

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

Координация порядка сортировки в промежуточных результатах, передаваемых между процессами.

Использование индексов и попытки локализации страничных ссылок.

Эта статья была одной из первых работ, посвященных преобразованиям выражений. 17.19.Hall P.A.V. Optimization of а Single Relational Expression in a Relational Data Base System IBM J. R&D. - May, 1976. - 20, № 3.

Описаны некоторые методы оптимизации, используемые в системе PRTV [6.9], которая, как и язык SQUIRAL [17.18], начинает обработку запроса с преобразования данного алгебраического выражения в некоторую более эффективную форму. Особенностью системы PRTV является то, что она не вычисляет каждое выражение автоматически, как только оно будет получено. Вместо этого выражения комбинируются с полученными ранее в более сложное выражение и вычисление откладывается до последнего момента (см. обсуждение пошаговой формулировки запроса в главе 6, раздел 6.5). Таким образом, отдельное реляционное выражение (из заголовка статьи) на самом деле представляет целую последовательность операций пользователя. Данный метод оптимизации подобен методу языка SQUIRAL, но в некоторых перечисленных ниже случаях работает лучше.

Выборка выполняется настолько рано, насколько это возможно.

Последовательность проекций комбинируется в одну операцию проекции.

Избыточные операции исключаются.

Выражения, использующие пустые отношения и тривиальные условия, упрощаются.

Общие выражения выносятся за скобки.

В заключении работы изложены результаты некоторых экспериментов, а также указаны направления дальнейших исследований. 17.20. Jarke М., Koch J. Range Nesting: A Fast Method to Evaluate Quantified Queries Proc. 1983 ACM SIGMOD Intem. Conf on Management of Data. - San Jose, Calif, May, 1983. Предложен вариант реляционного исчисления, в котором допускается применение некоторых дополнительных (и полезных) правил синтаксического преобразования. Представлены алгоритмы вычисления выражений в описанном исчислении. (Это исчисление очень напоминает исчисление кортежей, упомянутое в главе 7.) Кроме того, описана оптимизация в предложенном исчислении отдельного класса выражений, называемых точными вложенными выражениями . Изложены методы преобразования в точные выражения относительно сложных за-

просов (в частности, запросов, использующих квантор FORALL). Авторы показывают, что в точные выражения можно преобразовать большое количество запросов, используемых на практике.

17.21.Chaudhari S., Shim К. Including Group-By in Query Optimization Proc. 20th Int.

Conf. on Very Large Data Bases. - Santiago, Chile, September, 1994. 17.22.Makinouchi A., Tezuka M., Kitakami H., Adachi S. The Optimization Strategy for Query

Evaluation in RDB/Vl Proc. 7th Intern. Conf on Very Large Data Bases- Cannes,

France, September, 1981.

Система RDB/Vl является прототипом будущего профаммного продукта AIM/RDB компании Fujitsu (это SQL-система). В публикации описаны приемы оптимизации, используемые в данном прототипе. Они кратко сравниваются с аналогичными приемами, используемыми в прототипах систем INGRES и System R. Один из приемов является новым и состоит в применении динамически полученных значений функции МАХ и MIN для выполнения дополнительных выборок. Подобный прием приводит к упрощению процесса выбора порядка соединения и повышает производительность самой операции соединения. В качестве простого примера для последнего утверждения предположим, что нужно соединить отношения поставщиков S и деталей Р по атрибуту CITY. Сначала отношение S сортируется по атрибуту S.CITY. В процессе сортировки для атрибута S.CITY определяются значения функций МАХ и MIN; обозначим их через HIGH и LOW соответственно. Тогда для уменьшения количества кортежей отношения Р, которые потребуется проверять в процессе выполнения соединения, можно использовать следующую выборку.

1. LOW < Р.CITY AND P.CITY < HIGH

17.23.Pirahesh H., Hellerstein J.M., Hasan W. Extensible Rule Based Query Rewrite Optimization in Starburst Proc. 1992 ACM SIGMOD Intern. Conf on Management Data. - San Diego, Calif, June, 1992.

Как отмечалось в разделе 17.1, для преобразования выражений используется еще одно название - перезапись запросов (query rewrite). По мнению авторов, несколько неожиданно то, что в современных реляционных СУБД мало внимания уделяется такому преобразованию (по крайней мере, по состоянию на 1992 год). В работе описан механизм преобразования выражений прототипа системы Starburst корпорации IBM [17.50], [25.14], [25.17], [25.21], [25.22]. Пользователи с соответствующей квалификацией могут в любое время добавить в систему новые правила преобразования выражений (вот почему в заголовке статьи указано слово расширяемый - extensible ). 17.24. Mumick I.S., Finkelstein S.J., Pirahesh Н., Ramakrishnan R. Magic is Relevant Proc. 1990 ACM SIGMOD Intern. Conf on Management Data. - Atlantic City, N.J., May, 1990. Неудачный термин magic ( волшебный ) используется в данной публикации для ссылок на метод оптимизации, который изначально создавался для обработки запросов (в частности, рекурсивных), записанных на языке логических баз данных Datalog (глава 23). Данная работа расширяет этот подход до условно-реляционных систем, утверждая на основе экспериментальных измерений, что он часто эффективнее традиционных приемов оптимизации (заметьте, что запрос не обязательно должен быть рекурсивным, чтобы можно было применить к нему описанный

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

R := EX.ENAME WHERE EX.JOB = Clerk AND EX.SAL >

AVG { EY WHERE EY.DEPTi = EX.DEPTi, SAL ) ;

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

Т1 := ( EX.DEPTI,

AVG ( EY WHERE EY.DEPTi = EX.DEPTi, SAL ) AS ASAL ) ;

T2 := EMP.ENAME WHERE EMP.JOB = Clerk AND

EXISTS Tl { EMP.DEPTI = Tl.DEPTi AND EMP.SALARY > Tl.ASAL ) ;

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

/* Первое вспомогательное отношение: */ /* Имена, отцепы и зарплата клерков */ Т1 := ( ЕМР.ENAME, ЕМР.DEPTi, ЕМР.SAL )

WHERE ЕМР.JOB = Clerk ;

/* Второе вспомогательное отношение: */ /* Отделы, в которых работают клерки */ Т2 := Т1.DEPTI ;

/* Третье вспомогательное отношение: */ /* Отделы, в которых работают клерки, */ /* и средняя зарплата для каждого отдела */ ТЗ := ( Т2.DEPTI,

AVG { ЕМР WHERE ЕМР.DEPTi = Т2.DEPTI, SAL ) AS ASAL ) ;

/* Отношение-результат */

R := Tl.ENAME WHERE EXISTS ТЗ { Tl.DEPTI = T3.DEPTi AND

Tl.SAL > T3.ASAL ] :