Замечание. Оптимизатор системы System R является предшественником оптимизатора СУБД DB2. В [17.35] дана более подробная информация, специфическая для СУБД DB2.

В системе System R запрос представляет собой SQL-выражение, поэтому состоит из набора блоков SELECT-FROM-WHERE (блоков запроса). Одни блоки могут быть вложены в другие. Оптимизатор System R сначала определяет порядок, в котором будут вычисляться блоки запроса, а затем пытается снизить общую стоимость запроса посредством выбора реализации с наименьшей стоимостью для каждого отдельного блока запроса. Обратите внимание, что данная стратегия (сначала - выбор порядка блоков, а затем - оптимизация отдельных блоков) означает, что конкретный план выполнения всего запроса никогда не рассматривается, и это приводит к сужению пространства поиска (см. замечания по этому поводу почти в конце раздела 17.3). Замечание. В случае вложенных блоков оптимизатор вычисляет блоки во вложенном порядке, который указал пользователь, т.е. внутренний блок выполняется первым. В [17.39]-[ 17.45] можно найти критику и дальнейшее обсуждение данной стратегии.

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

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

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

Соединения реализуются с помощью метода сортировки-слияния, поиска по индексу или метода последовательного просмотра. В работе особое значение автор придал тому, что при вычислении, например, вложенного соединения (А JOIN В) JOIN С необязательно полностью вычислять вложенное соединение А JOIN В перед соединением его результата и отношения С. Наоборот, каждый кортеж соединения А JOIN В сразу после вычисления передается процессу, соединяющему этот кортеж с кортежами из отношения С. Поэтому нет необходимости материализовать отношение А JOIN В полностью. (Эта идея конвейерной обработки кратко обсуждалась в главе 3, раздел 3.2. См. также [17.18], [17.60].)

Эта работа включает и некоторые соображения о стоимости самого процесса оптимизации. Для соединения двух отношений стоимость приблизительно равна стоимости 5-20 операций выборки. При многократном выполнении оптимизированного запроса это довольно незначительные расходы. (Отметим, что система System R, как и

СУБД DB2, является компилирующей, поэтому однажды оптимизированный запрос может выполняться сотни и даже тысячи раз.) В работе утверждается, что оптимизация сложных запросов требует всего нескольких тысяч байтов пространства для хранения и нескольких десятых долей секунды на компьютере IBM System 370 Model 158. Соединение восьми таблиц было оптимизировано за несколько секунд.

17.35.Cheng J.M., Loosley C.R., Shibamiya а., Worthington P.S. IBM DATABASE 2 Performance: Design, Implementation, and Tuning IBM Sys. J. - 1984. - 23, № 2. Здесь содержится краткое описание тактики оптимизации в СУБД DB2 (в первой версии этой системы): методы преобразования запросов, обработка вложенных блоков запроса, методы соединения, выбор пути доступа и обработка индексов. Замечание. В эту работу также включен интересный материал о других аспектах работы СУБД DB2, влияющих на ее производительность.

17.36.Wong е., Youssefi к. Decomposition- а Strategy foe Query Processing ACM TODS. - September, 1976. - 1, № 3.

17.37. Youssefi K., Wong E. Query Processing in a Relational Database Management System Proc. 5th Intern. Conf on Very Large Data Bases. - Rio De Janeiro, Brazil, September, 1979.

17.38.Rowe L.A., Stonebraker M. The Commercial INGRES Epilogue M. Stonebraker (ed.). The INGRES Papers: The Anatomy of a Relational Database Management System. - Reading, Mass.: Addison-Wesley, 1986.

Коммерческая СУБД Commercial INGRES - это программный продукт, полученный из прототипа University INGRES (Университетская система). Ниже перечислены некоторые различия между оптимизаторами систем Commercial INGRES и University INGRES.

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

2. Университетский оптимизатор обрабатывает запросы с двумя переменными (например, соединения) с помощью метода подстановки кортежей, обсуждавшегося в разделе 17.6. Коммерческий оптимизатор поддерживает несколько мощных методов обработки подобных запросов, включая, в частности, метод сортировки-слияния, описанный в разделе 17.7.

3. Коммерческий оптимизатор поддерживает более сложный набор статистических показателей по сравнению с университетским оптимизатором.

4. Университетский оптимизатор выполняет инкрементное планирование (см. п. 1). Коммерческий оптимизатор выполняет более обширный поиск. Тем не менее поиск прекращается, если на оптимизацию будет затрачено время, превышающее наилучшую оценку времени выполнения запроса (в противном случае выполнение оптимизации не даст никаких преимуществ).

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

17.39.Kim W. On Optimizing an SQL-Like Nested Query ACM TODS. - September,

1982. -7, Xo3.

Cm. комментарий к [17.43]. 17.40.Kiessling W. On Semantic Reefs and Efficient Processing of Correlation Queries with

Aggregates Proc. 11th Intern. Conf on Very Large Data Bases.- Stockholm,

Sweden, August, 1985.

Cm. комментарий к [17.43]. 17.41. Ganski R.A., Wong H.K.T. Optimization of Nested SQL Queries Revisited Proc. 1987

ACM SIGMOD Intern. Conf on Management of Data. - San Francisko, Calif, May, 1987.

Cm. комментарий к [17.43]. 17.42.Gunter von Btiltzingsloewen. Translating and Optimizing SQL Queries Having

Aggregates Proc. 13th Intem. Conf on Very Large Data Bases. - Brighton, England,

September, 1987.

Cm. комментарий к [17.43]. 17.43. Muralikrishna M. Improved Unnesting Algorithms for Join Aggregate SQL Queries Proc. 18th Intem. Conf on Very Large Data Bases. - Vancouver, Canada, August, 1992. Язык SQL позволяет создавать вложенные подзапросы , т.е. блоки SELECT-FROM-WHERE, вложенные внутрь других подобных блоков. Эта конструкция порождает некоторые трудности при реализации. Рассмотрим следующий SQL-запрос ( Определить имена поставщиков детали с номером Р2 ), на который далее будем ссылаться, как на запрос QL

SELECT S.SNAME FROM S WHERE S.St IN

( SELECT SP.St FROM SP

WHERE SP.Pi = P2 ) ;

В системе System R [17.34] этот запрос будет реализован следующим образом. Сначала будет вычислен внутренний блок и создана временная таблица Т, содержащая номера требуемых поставщиков. После этого кортеж за кортежем будет проверена вся таблица S и для каждого выбранного из нее кортежа будет просматриваться таблица Т с целью определения, содержится ли в ней соответствующий номер поставщика. Эта стратегия достаточно неэффективна (поскольку таблица Т не имеет индекса).

Теперь рассмотрим запрос Q2.

SELECT S.SNAME FROM S, SP WHERE S.St = SP.St AND SP.Pt = P2 ;

Легко установить, что он семантически идентичен предыдущему, но система System R проанализирует дополнительную стратегию реализации данного запроса. В частности, если таблицы S и SP окажутся физически сохраненными в последовательности номеров поставщиков, то система применит слияние, которое будет вы-