Глобальные оптимизации в реляционных системах управления базами данных

Рассматриваемые до сих пор оптимизационные преобразования запросов, улучшенные структуры хранения реляционных данных и стратегии выполнения реляционных операций были направлены на повышение эффективности отдельных запросов к базе данных. Существует другая постановка задачи оптимизации, когда преследуется цель повышения эффективности смеси запросов. Соответствующие оптимизационные приемы относятся к \2глобальной\1 оптимизации физических управляющих структур баз данных и планов выполнения заданного набора запросов.

Имеется два направления глобальной оптимизации, не являющихся взаимно исключающими. Первое направление можно назвать \2статистической глобальной оптимизацией\1. Цель такой оптимизации - автоматическое (или автоматизированное) поддержание в базе данных на основании статистической информации набора управляющих структур, позволяющего эффективно выполнять запросы из имеющегося потока запросов. Фактически, это означает улучшение физической структуры базы данных относительно текущего потока запросов. Этот подход не предполагает априорных знаний о специфике смеси запросов, поскольку основывается только на статистике. Предполагается, что свойства запросов в потоке обладают инерционностью, т.е. на основе информации об уже выполненных запросах можно делать оценивать свойства будущих запросов. На практике это предположение, как правило, подтверждается.

Второе направление в последнее время обычно называют \2оптимизацией набора запросов\1. Соответствующие оптимизации расчитаны на то, что система получает запросы не по одному, а целыми наборами. Эта ситуация невозможна в традиционных реляционных СУБД, интерфейсы которых предполагают поочередное выполнение запросов, но становится жизненной в более сложных системах, использующих СУБД в качестве средства поддержки. К таким системам относятся системы дедуктивных баз данных, системы логического программирования и т.д. Их объединяет то свойство, что наряду с базами данных в них хранятся наборы правил логического вывода, позволяющие порождать новые данные (факты) на основе фактов, хранимых в базе данных.
Запрос, поступающий в такую систему, преобразуется в набор запросов традиционного интерфейса СУБД. Все запросы, составляющие набор, могут быть предоставлены СУБД одновременно и, соответственно, могут обрабатываться совместно. Основным действием при оптимизации набора запросов является выработка \2глобального\1 оптимального плана выполнения запросов этого набора. Основой оптимизации является выявление общих подвыражений, входящих в разные запросы одного набора. Как мы уже отмечали, эти два подхода не являются взаимно исключающими. Можно представить систему, в которой осуществляется оптимизация наборов запросов и одновременно производится улучшение физической структуры базы данных на основе статистической информации о потоке наборов запросов. С другой стороны, при оптимизации набора запросов, вообще говоря, можно учитывать возможности порождения временных управляющих структур (например, индексов) на время выполнения данного набора запросов. | |

Эффективное выполнение операций соединения

При традиционной организации структур хранения и управляющих структур реляционной базы данных и использовании в качестве подсистемы базового доступа к хранимым данным типа RSS System R наиболее эффективно выполняются операции, соответствующие ограничению и проекции одного хранимого отношения. Двуместные операции - объединения, пересечения, соединения отношений специально не поддерживаются структурами данных и операциями нижнего уровня. Особенно болезненно ощущается отсутствие поддержки одного часто употребимого случая соединения - эквисоединения. Это действительно распространенная операция в реляционных системах, причем ее употребление в запросах тем чаще, чем более правильно с точки зрения теории реляционных баз данных спроектирована конкретная база данных. Поэтому естественно стремление исследователей и разработчиков реляционных СУБД к повышению эффективности выполнения этой операции.

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

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

Второй алгоритм предполагает предварительную сортировку обоих отношений в соответствии со значениями полей соединения. После этого соединение выполняется с использованием процедуры, напоминающей процедуру слияния, применяемую в алгоритмах внешней сортировки файлов. Если отношение кластеризовано по полям соединения, и, следовательно, для него определен индекс на этих полях, то исходная сортировка этого отношения не требуется; в цикле слияния используется сканирование отношения по этому кластеризованному индексу.
Как и раньше, производится список пар TID'ов соединяемых кортежей с использованием индексов I2 и I4. Кроме того, на основе индексов I1 и I3 и условий, задаваемых предикатами ограничений, формируются два списка TID'ов L1 и L2 кортежей первого и второго отношений, удовлетворяющих предикатам ограничения. Далее производится своего рода пересечение этих трех списков таким образом, что пара (TID1, TID2) оставляется в результирующем списке пар в том и только том случае, когда TID1 присутствует в списке L1, а TID2 - в списке L2. Такой вариант алгоритма описан в [2], но он не использовался в System R, поскольку RSS не обеспечивает операций пересечения отсортированных временных объектов, а накладные расходы, которые потребуются для выполнения подобных операций выше уровня RSS, очень трудно оценить. В литературе имеются предложения по повышению в этом направлении уровня подсистемы управления доступа к хранимым данным. Например, в [45] предлагается расширить возможности такой подсистемы, включив в число ее функций выполнение теоретико-множественных операций над отсортированными списками TID'ов. В ряде случаев это позволяет произвести все выполнение запроса в терминах идентификаторов кортежей и произвести реальное обращение к кортежам отношения только на завершающей стадии выдачи результата. При этом, поскольку результирующий список TID'ов отсортирован, число обращений к блокам внешней памяти, хранящим кортежи, будет оптимально. Другой путь примерно в том же направлении, но с введением управляющих структур нового типа, предлагается в [38]. Новый тип управляющей структуры - индекс соединения. В общем виде, если f (R.C1, S.C2) - предикат соединения отношений R и S по полям C1 и C2, то индекс соединения R и S по f определяется как бинарное отношение JI = { (TIDi, TIDj) | f (кортеж (TIDi).C1, кортеж(TIDj).C2) = true }. (Поля C1 и C2 могут быть составными, а f - не обязательно предикат эквисоединения.) Индексы соединения предлагается хранить в виде двух B-деревьев, в одном из которых порядок поддерживается по TIDi, а в другом - по TIDj.

Это требуется для того, чтобы можно было эффективно учитывать предикаты ограничения отношений, для которых существуют обычные индексы. В [38] описаны основные алгоритмы поддержания индексов соединения при выполнении операций вставки и удаления кортежей, а также использования этих индексов при выполнении операций полусоединения, соединения и запросов общего вида. Из этого описания следует, что некоторые запросы удается выполнять достаточно эффективно, причем эффективность возрастает при увеличении объема доступной оперативной памяти. Но совершенно очевидно, что как и в случае с обычными индексами, определение слишком большого числа индексов соединения приведет в деградации системы за счет черезчур больших накладных расходов, требуемых при выполнении операций занесения и удаления кортежей. В [48] предлагается иной вид управляющей структуры, позволяющей эффективно реализовывать операции соединения отношений, - частичные отношения. Идея состоит в том, что на стадии проектирования базы данных для каждого отношения принимается решение о наборе полей, на которых могут задаваться предикаты ограничения и соединения. Отношения хранятся как обычно в виде наборов кортежей, содержащих все поля, но, кроме того каждому отношению соответствует частичное отношение, кортежи которого содержат только те поля базового отношения, на которых могут задаваться предикаты, и одно дополнительное поле, хранящее TID соответствующего кортежа базового отношения. Кроме того, для длинных текстовых полей базового отношения можно определить функцию сжатия, приводящую такие значения к значениям соответствующих полей частичного отношения (например, действие функции сжатия может состоять в том, что из текстовой строки берутся несколько первых символов). При таком подходе операции ограничения и соединения выполняются над частичными отношениями, а при формировании окончательного результата по имеющимся ссылкам выбираются значения других полей. Отмечается, что в ряде случаев, определяемых степенью селективности предикатов ограничения, алгоритмы соединения на основе частичных отношений оказываются эффективнее традиционных.


Много внимания в современной литературе уделяется способам физической организации баз данных на внешней памяти на основе идей многоключевого хэширования и соответствующим алгоритмам выполнения реляционных операций. Этот подход хорошо иллюстрирует работа [36]. Каждому полю каждого отношения базы данных соответствует, вообще говоря, своя хэш-функция. При занесении кортежа в отношение номер блока внешней памяти, в который будет помещен этот кортеж, вычисляется как конкатенация вырезок значений хэш-функций, примененных к значениям полей кортежа. В полученной после конкатенации битовой строке допускается перестановка битов, причем правила перестановки, как и набор используемых хэш-функций, являются характеристикой выбранного алгоритма многоключевого хэширования. Понятно, что при неполном указании значений полей искомого кортежа после применения алгоритма хэширования будет получен список страниц, в которых может находиться искомый кортеж. Алгоритм (экви)соединения, основанный на такой организации хранимых отношений, разбивает соединение на последовательность подсоединений. При этом гарантируется, что ни один блок, содержащий кортежи соединяемых отношений, не будет использован в двух подсоединениях. Основная проблема - выбрать такое разбиение соединений на подсоединения, которое минимизирует требуемое число буферов оперативной памяти. В предлагаемом в [36] алгоритме предполагается, что число буферов оперативной памяти достаточно для выполнения каждого подсоединения. Это предположение достаточно естественно, поскольку параметры алгоритма многоключевого хэширования могут варьироваться. Снятие предположения усложняет алгоритм соединения и делает его эффективность сомнительной. В этой работе не рассматриваются проблемы возможных переполнений страниц при расширении отношений. Однако, предложенная техника легко расширяется с использованием идей динамического многоключевого хэширования. Этому предмету в последнее время посвящается очень много работ. Основные концепции подхода изложены, например, в [37].


Интересным примером практически реализованной СУБД, основанной на некоторой вариации метода многоключевого хэширования, является французская система Sabre [34]. Наиболее интересная особенность этой системы - использование предикатных деревьев для мультиатрибутной кластеризации отношений (разновидность многоключевого хэширования). Предикатное дерево задается администратором базы данных при создании отношения и содержит простые предикаты над полями отношения. При занесении кортежа вычисление предикатов, входящих в дерево, позволяет получить номер блока внешней памяти, в которые следует поместить кортеж. При поиске кортежа на основании заданных значений полей находится множество страниц, в которых может располагаться данный кортеж. При такой организации хранимых отношений естественный способ выполнения соединения отношений основывается на хэшировании. Система Sabre интересна еще и тем, что в ней это единственный применяемый алгоритм соединения. Как отмечается в [34], в ранних версиях системы поддерживалось несколько стратегий выполнения соединений. Подобно System R, при обработке запроса с соединиями генерировалось множество альтернативных планов его выполнения, которые затем оценивались на основе статистической информации о базе данных. Однако в ходе эксплуатации ранних версий Sabre было установлено, что, как правило, используется одна стратегия выполнения соединения, естественно соответствующая физической организации отношений. Поэтому была оставлена только эта стратегия, что позволило упростить оптимизатор и ускорить процедуру выработки плана выполнения запроса, не теряя эффективность выполнения. Хотя мы не рассматриваем в этой статье специфику реляционных систем, использующих специализированную аппаратную поддержку, необходимо отметить, что физическая организация реляционных баз данных на основе мультиатрибутного хэширования позволяет легко распараллеливать выполнение операций соединения. Поэтому такая организация хорошо соответствует специфике мультипроцессорных машин баз данных, которые могут реально распараллеливать выполнение запроса. Конкретные предложения по распределению одного отношения между несколькими независимыми дисковыми устройствами приводятся, например, в [35]. В этой работе развивается идея декластеризации отношения, когда отношение разбивается на две или более части, средние характеристики которых примерно одинаковы. Эти части отношения хранятся на разных устройствах внешней памяти, что позволяет, например, производить параллельное сканирование отношения. Понятно, что критерии декластеризации могут быть различны, и, в частности, могут способствовать распараллеливанию соединений. Множество вариаций алгоритмов соединения существует для распределенных реляционных СУБД. Они очень специфичны, хотя некоторые работы близки тематике машин баз данных. Проблемы оптимизации в распределенных системах рассматриваются в следующем разделе. | |

Эффективные алгоритмы выполнения запросов

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

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

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

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

| |

Литература

Astrahan M.M., Blasgen M.W., Chamberlin D.D., Eswaran K.P., Griffits P.P., King W., Lorie R.A., McJones P., Mehl J.W., Putzolu G.R., Traiger I.L., Wade B.W., Watson V. System R: A Relational Approach to Data Base Management // ACM Trans. Database Syst.- 1976.- 1, N 2.- C. 97-137 Blasgen M.W., Eswaran K.P. Storage and Access in Relational Data Bases // IBM Syst. J.- 1977.- 16, N 4.- C. 363-377 Lorie R.A., Nilsson J.F. An Access Specification Language for a Relatiomal Data Base System // IBM J. Res. and Dev.- 1979.- 23, N 3.- C. 1-13 Selinger P.G., Astrahan M.M., Chamberlin D.D., Lorie R.A., Price T.G. Acess Path Selection in a Relational Database Management System // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., May 30 - June 1, 1979. New York, 1979.- C. 23-34 Whang K.-Y. Constructing Cost Formulas for Relational Database Query Optimizers: A Tutorial // TENCON'87: IEEE Reg. 10th Conf., Seoul, Aug. 25-28, 1987. Proc. Vol. 1. New York, 1987.- C. 132-141 Astrahan M.M., Schkolnick M., Kim W. Performance of the System R Acess Selection Mechanism // Inf. Process., 80. Proc. IFIP World Comput. Congr., Melbourne, Sept. 1980. Amsterdam e.a., 1980.- C. 487-492 Chamberlin D.D., Astrahan M.M., Blasgen M.W., Gray J.N., King W.F., Lindsay B.G., Lorie L.A., Mehl J.W., Price T.G., Putzolu G.R., Selinger P.G., Schkolnick M., Slutz D.R., Traiger I.L., Wade B.W., Yost R.A. A History and Evaluation of System R // Commun. ACM.- 1982.- 24, N 10.- C. 632-646 Cheng J.M., Loosley C.R., Shibamiya A., Worthington P.S. IBM Database 2 Performance: Design, Implementation, and Tuning // IBM Syst. J.- 1984.- 23, N 2.- C. 189-210 Stonebraker M. Implementation of Integrity Constraints and Views by Query Modification // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 23-26, 1975. New York, 1975.- C. 65-78 Wong E., Youssefi K. Decomposition - A Strategy for Query Processing // ACM Trans. Database Syst.- 1976.- 1, N 3.C. 223-241 Stonebraker M.R., Wong E., Kreps P., Held G. The Design and Implementation of INGRES // ACM Trans.
Database Syst.- 1976.- 1, N 2.- C. 189-222 Hawthorn P., Stonebraker M.R. Performance Analisys of Relational Data Base Management System // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., May 30 - June 1, 1979. New York, 1979.- C. 1-12 Kooi R., Frankforth D. Query Optimization in INGRES // IEEE Database Eng. Bull.- 1982.- 5, N 3.- C. 2-5 Stonebraker M., Woodfil L., Ranstrom J., Murphy M., Meyer M., Allman E. Performance Enhancements to a Relational Database System // ACM Trans. Database Syst.- 1983.- 8, N 2.C. 189-222 Rowe L.A., Stonebraker M. The Commercial INGRES Epilogue // The INGRES Papers: The Anatomy of a Relational Database Management System. Reading, Mass.: Addison-Wesley.1985.- C. 121-128 Дейт К. Введение в системы баз данных.- М.: Наука.1980.- 463 c. Ульман Д. Основы систем баз данных.- М.: Финансы и статистика.- 1983.- 335 c. Мейер Д. Теория реляционных баз данных.- М.: Мир.1987.- 608 c. Date C.J. An Introduction to Database Systems. V.1. 4th ed.- Reading, Mass.: Addison-Wesley.- 1984.- 639 c. Jarke M., Koch J. Query Optimization in Database Systems // ACM Comput. Surv.- 1984.- 16, N 2.- C. 111-152 Rothnie J.B. An Approach to Implementing a Relational Data Management System // Proc. ACM SIGMOD Workshop on Data Descr., Acc. and Contr., Ann Arbol, Mich., May 1974. New York, 1974.- C. 133-140 Rothnie J.R. Evaluating Inter-Entry Retrieval Expressions in a Relational Data Base Management System // AFIPS Conf. Proc.: Nat. Comput. Conf., Anaheim, Calif., May 1975. Montvale, N.Y., 1975.- C. 152-159 Smith J.M., Chang P.Y.-T. Optimizing the Performance of a Relational Algebra Database Interface // Commun.- 1975.18, N 10.- C. 568-579 Aho A.V., Sagiv Y., Ullman J.D. Equivalence of Relational Expressions // SIAM J. Comput.- 1979.- 8, N 2.- C. 218-246 Chandra A.K., Merlin P.M. Optimal Implementation of Conjuctive Queries in Relational Databases // Proc. 9th Ann. ACM Symp. Theory of Comput., New York, May 1976. New York, 1976.- C. 77-90 Motzkin D. Database Performance Optimization // AFIPS Conf.


Proc.: Nat. Comput. Conf., Chicago, Ill., July 15-18, 1985. Reston, Virg., 1985.- C. 555, 557-566 Bell D.A. Issues in Relational Database Performance // Data and Knowledge Eng.- 1988.- 3, N 1.- C. 46-61 Bloom B.H. Space/Time Trade-offs in Hash Coding with Allowable Errors // Commun. ACM.- 1970.- 13, N 7.- C. 422-426 Gotlieb L.R. Computing Joins of Relations // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 14-16, 1975. New York, 1975.- C. 55-63 Kim W. A New Way to Compute the Product and Join of Relations // Proc. ACM SIGMOD Int. Conf. Manag. Data, New Work, May 1980. New York, 1980.- C. 178-187 Merrett T.H. Why Sort/Merge Gives the Best Implementation of the Natural Join // ACM SIGMOD Record.1983.- 13, N 2, C. 40-51 DeWitt D.J., Katz R.H., Olken F., Shapiro L.D., Stonebraker M.R., Wood D. Implementation Techniques for Main Memory Database Systems // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., June 18-21, 1984. New York, 1984.- C. 1-8 DeWitt D., Gerber R. Multiprocessor Hash-Based Join Algorithms // Proc. 11th Int. Conf. Very Large Data Bases, Stockholm, Sweden, Aug. 1985. Palo Alto, Calif., 1985.- C. 151-164 Abitboul S., Scholl M., Gardarin G., Simon E. Towards DBMSs for Supporting New Applications // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986.- C. 423-435 Fang M.T., Lee R.C.T., Chang C.C. The Idea of De-Clustering and Its Applications // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986.- C. 181-188 Thom J.A., Ramamohanarao K., Naish L. A Superjoin Algorithm for Deductive Databases // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986.- C. 189-196 Hsu M., Yang W.-P. Concurrent Operations in Extendible Hashing // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 25-28, 1986. Los Altos, Calif., 1986.- C. 241-247 Valduriez P. Join Indeces // ACM Trans. Database Syst.- 1987.- 12, N 2.- C. 218-246 Jarke M., Koch J.


Range Nesting: A Fast Method to Evaluate Quantified Queries // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 23-26, 1983. New York, 1983.- C. 198-206 Makinouchi A., Tezuka M., Kitakami H., Adachi S. The Optimization Strategy for Query Evaluation in RDB/V1 // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York, 1981.- C. 518-529 Bergamaschi S., Scales M.R. Choice of the Optimal Number of Blocks for Data Access by an Index // Inf. Syst.1986.- 11, N 3.- C. 199-209 Yu C.T., Jiang T.M. Adaptive Algorithms for Balanced Multidimensional Clustering // Proc. 4th Int. Conf. Data Eng., Los Angeles, Calif., Feb. 1988. Washington, D.C., 1988.- C. 386-391 Cheiney J.-P., Kierman G. A Functional Clustering Method for Optimal Access to Complex Domains in a Relational DBMS // Proc. 4th Int. Conf. Data Eng., Los Angeles, Calif., Feb. 1988. Washington, D.C., 1988.- C. 394-401 Bell D.A., McErlean F.J., Stewart P.M., Arbuckle W.A. Clustering Related Tuples in Databases // Comput. J.- 1988.31, N 3.- C. 253-257 Grazzini E., Pinzani R., Pippolini F. A Physical Structure for Efficient Processing of Relational Queries // Found. Data Organ. Proc. Int. Conf., Kyoto, May 22-24, 1985. New York; London, 1987.- C. 501-514 Astrahan M.M., Schkolnick M., Whang K.Y. Counting Unique Values of an Attribute without Sorting // Inf. Syst.1987.- 12, N 1.- C. 11-16 Pramanik S., Fotouhi F. Optimizing the Cost of Relational Queries Using Partial Relation Schemes // Inf. Syst.- 1988.- 13, N 1.- C. 71-79 Ullmann J.R. Fast Implementation of Relational Operations Via Inverse Projections // Comput. J.- 1988.- 31, N 2.- C. 147-154 Desai B.C., Goyal P., Sardi F. Composite Index in DDBMS // J. of Syst. and Software.- 1988.- 8, N 2.- C. 105-120 Youssefi K., Wong E. Query Processing in a Relational Database Management System // Proc. 5th Int. Conf. Very Large Data Bases, Rio de Janeiro, Brasil, Oct. 3-5, 1979. New York, 1979.- C. 409-417 Palermo F.P. A Data Base Search Problem // Inf.


Syst.: COINS IV. New York: Plenum Press, 1974.- C. 67-101 Pecherer R.M. Efficient Evaluation of Expressions in a Relational Algebra // Proc. ACM Pacific Reg. Conf., New York, Apr. 1975. New York, 1975.- C. 44-49 Hall P.A.V. Optimization of a Single Relational Expression in a Relational Data Base System // IBM J. of Res. and Dev.- 1976.- 20, N 3.- C. 244-257 Yao S.B. Optimization of Query Evaluation Algorithms // ACM Trans. Database Syst.- 1979.- 4, N 2.- C. 133-155 Aho A.V., Sagiv Y., Ullman J.D. Efficient Optimization of a Class of Relational Expressions // ACM Trans. Database Syst.- 1979.- 4, N 4.- C. 435-454 Sagiv Y., Yannakakis M. Equivalences Among Relational Expressions with Union and Difference Operators // J. ACM.1980.- 27, N 4.- C. 633-655 Kim W. On Optimizing an SQL-Like Nested Query // ACM Trans. Database Syst.- 1982.- 7, N 3.- C. 443-469 Rosenthal A., Reiner D. An Architecture for Query Optimization // Proc. ACM SIGMOD Int. Conf. Manag. Data, Orlando, Fl., June 2-4, 1982. New York, 1982.- C. 246-255 IEEE Database Eng.- 1982.- 5, N 3: Special Issue on Query Optimization West V. An Optimizer for a Relational Database Command Language // Software: Pract. and Exper.- 1983.- 13, N 11.- C. 1005-1012 Talbot S. An Invistigation into Optimization of Relational Query Languages // Comput. J.- 1984.- 27, N 4.- C. 301-309 Hiyoshi S., Mizuma M., Watanabe M. Hierarchical Optimization Strategy for Query Evaluation // NEC Res. and Dev.- 1984.- N 12.- 48-55 Ceri S., Gottlob G. Translating SQL into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries // IEEE Trans. on Software Eng.- 1985.- 11, N 4.324-345 Ganski R.A., Wong H.K.T. Optimization of Nested SQL Queries Rivisited // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987. New Work, 1987.- C. 23-33 Dayal U. Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987.


Los Altos, Calif., 1987.- C. 197-208 Freytag J.C., Goodman N. Translating Aggregate Queries into Iterative Programs // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- C. 138-146 Bultzingsloewen G. Translating and Optimizing SQL Queries Having Aggregates // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987. Los Altos, Calif., 1987.- C. 235-244 Subieta K., Rzeczkowski W. Query Optimization by Stored Queries // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987. Los Altos, Calif., 1987.- C. 369-380 Rzeczkowski W., Subieta K. Stored Queries - A Data Organization for Query Optimization // Data and Knowledge Eng.- 1988.- 3, N 1.- C. 29-48 Warren D.H.D. Efficient Processing of Interactive Relational Database Queries Expressed in Logic // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York, 1981.- C. 345-352 Krishnamurthy R., Boyal H., Zaniolo C. Optimization of Nonrecursive Queries // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.C. 128-137 Ceri S., Gottlob G., Lavazza L. Translation and Optimization of Logic Queries: The Algebraic Approach // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- C. 395-402 Yao S.B. An Attribute Based Model for Database Access Cost Analyses // ACM Trans. Database Syst.- 1977.- 2, N 1.- C. 45-67 Yao S.B. Approximating Block Acess in Database Organizations // Commun. ACM.- 1977.- 20, N 4.- C. 260-261 Stockmeyer L.H., Wong C.K. On the Number of Comparisons to Find the Intersection of Two Relations // SIAM J. of Comput.- 1979.- 8, N 3.- C. 388-404 Demolombe R. Estimation of the Number of Tuples Satisfying a Query Expressed in Preducate Calculus Language // Proc. 6th Int. Conf. Very Large Data Bases, Montreal, Oct. 1980. New York, 1980.- C. 55-63 Whang K., Wiederhold G., Sagalowicz D. Estimating Block Accesses in Database Organizations - A Closed Noniterative Formula // Commun.


ACM.- 1983.- 26, N 11.- C. 940-944 Luk W.S. On Estimating Block Accesses in Database Organization // Commun. ACM.- 1983.- 26, N 11.- C. 945-947 Zahorjan J., Bell B.J., Sevcik K.C. Estimating Block Transfers When Record Access Probabilities Are Non-Uniform // Inf. Process. Lett.- 1983.- 16, N 5.- C. 249-252 Christodoulakis S. Estimating Record Selectivities // Inf. Syst.- 1983.- 8, N 2.- C. 105-115 Christodoulakis S. Estimating Block Selectivities // Inf. Syst.- 1984.- 9, N 1.- C. 69-79 Christodoulakis S. Implication of Certain Assumtions in Database Performance Evaluation // ACM Trans. Database Syst.- 1984.- 9, N 2.- C. 163-186 Piatetski-Shapiro G., Connel C. Accurate Estimation of the Number of Tuples Satisfying a Condition // ACM SIGMOD Record.- 1984.- 19, N 2.- C. 256-276 Faloutsos C., Christodoulakis S. Design of a Signature File Method that Accounts for Non-Uniform Occurrance and Query Frequencies // Proc. 11th Int. Conf. Very Large Data Bases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985.C. 165-170 Vander Zanden B.T., Taylor H.M., Bitton D. Estimating Block Accesses When Attributes Are Correlated // Proc. 12th Int.Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- C. 119-127 Hagmann R.B. An Observation on Database Buffering Performance Metrics // Proc. 12th Int.Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- C. 289-293 Kiessling W. Access Path Selection in Databases with Intelligent Disc Subsystems // Comput. J.- 1988.- 31, N 1.- C. 41-50 Rowe N.C. Absolute Bounds on Set Intersection and Union Sizes from Distribution Information // IEEE Trans. Software Eng.- 1988.- 14, N 7.- C. 1033-1048 Lynch C. Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Ca, Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 240-251 Stonebraker M., Neuhold E. A Distributed Data Base Version of INGRES // Proc. 2nd Berkley Workshop Distrib.


Data Manag. and Comput. Networks, Berkley, Calif., May 1977. Berkley, Calif., 1977.- C. 19-36 Lohman G.M., Daniels D., Haas L.M., Kistler R., Selinger P.G. Optimization of Nested Queries in a Distributed Relational Database // Proc. 10th Int. Conf. Very Large Data Bases, Singapore, Aug. 27-31, 1984. New York, 1984.- C. 403-415 Lohman G.M., Mohan C., Haas L.M., Lindsay B.G., Selinger P.G., Wilms P.F., Daniels D. Query Processing in R* // Query Processing in Database Systems. New York: Springer.1985.- C. 31-47 Lu H., Carey M. Some Experimental Results on Distributed Join Algorithms in a Local Network // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985.- C. 425- 432 Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Local Queries // Proc. ACM SIGMOD Int. Conf. Manag. Data, Washington, D.C., May 28-30, 1986. New York, 1986.- C. 173-180 Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Distributed Queries // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- C. 149-159 Ceri S., Gottlob G. Optimizing Joins Between Two Partitioned Relations in Distributed Databases // J. Parall. and Distrib. Comput.- 1986.- 3, N 2.- C. 183-205 Segev A. Optimization of Join Operations in Horizontally Partitioned Database Systems // ACM Trans. Database Syst.- 1986.- 11, N 1.- C. 48-80 Chen J.S.J., Li V.O.K. Optimizing Joins in Fragmented Database Systems on a Broadcast Computer Networks // 7th Int. Conf. Distrib. Comput. Syst., Berlin, Sept. 21-25, 1987. Washington, D.C., 1987.- C. 338-345 Cornell D.W., Yu P.S. A Vertical Partitioning Algorithm for Relational Databases // 3rd Int. Conf. Data Eng., Los Angeles, Ca, Febr. 3-5, 1987. Proc. Washington, D.C., 1987.- C. 30-35 Otoo E.J., Santoro N., Rotem D. Improving Semi-Join Evaluation in Distributed Query Processing // 7th Int. Conf. Distrib. Comput. Syst., Berlin, Sept. 21-25, 1987. Washington, D.C., 1987.- C. 554-561 Yu C.T., Gun K.-C., Zhang W., Templeton M., Brill D., Chen A.L.P.


Algorithms to Process Distributed Queries in Fast Local Networks // IEEE Trans. Comput.- 1987.- 36, N 10.C. 1153-1164 Bodorik P., Riordon J.S. Distributed Query Processing Optimization Objectives // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988.- C. 320-329 Lee M., Freytag J., Lohman G. Implementing an Interpreter for Functional Rules in a Query Optimizers // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 218-229 Jhingram A. A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedural Objects // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 88-99 Rosental A., Helman P. Understanding and Extending Transformation-Based Optimizers // IEEE Database Eng.- 1986.9, N 4.- C. 44-51 Batory D.S. Extensible Cost Models and Query Optimization in GENESIS // IEEE Database Eng.- 1987.- 10, N 4. - C. 27-34 Graefe G., DeWitt D.J. The EXODUS Optimizer Generator // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987. New York, 1987.- C. 160-172 Freytag J.C. A Rule-Based View of Query Optimization // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987. New York, 1987.- C. 173-180 Shan M.C. Optimal Plan Search in a Rule-Base Query Optimizer // Lect. Notes Comput. Sci.- 1988.- 303, C. 92-112 Finkelstein S. Common Expression Analysis in Database Applications // Proc. ACM SIGMOD Int. Conf. Manag. Data, Orlando, Fl, June 2-4, 1982. New York, 1982.- C. 127-133 Jarke M. Common Subexpression Isolation in Multiple Query Optimization // Query Processing in Database Systems. New York: Springer.- 1985.- C. 191-205 Kim W. Global Optimization of Relational Queries: A First Step // Query Processing in Database Systems. New York: Springer.- 1985.- C. 206-216 Whang K.-Y. Index Selection in Relational Databases // Found. Data Organ. Proc. Int. Conf., Kyoto, Japan, May 22-24, 1985.


New York; London, 1987.- C. 487-500 Satoh K., Tsuchida M., Nakamura F., Oomachi K. Local and Global Query Optimization Mechanisms for Relational Databases // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985.- C. 405-417 Sellis T. Global Query Optimization // Proc. ACM SIGMOD Int. Conf. Manag. Data, Washington, D.C., May 28-30, 1986. New York, 1986.- C. 191-205 Chacravarthy U.S., Minker J. Multiple Query Processing in Deductive Databases Using Query Graphs // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.- C. 384-394 Sellis T. Multiple-Query Optimization // ACM Trans. Database Syst.- 1988.- 13, N 1.- C. 23-52 Finkelstein S., Schkolnick M., Tiberio P. Physical Database Design for Relational Databases // ACM Trans. Database Syst.- 1988.- 13, N 1.- C. 91-128 Miyao J., Tominaga K., Kikuno T., Yoshida N. Optimization of Multiple Queries in Relational Database Systems // Syst. and Comput. in Japan.- 1988.- 19, N 4.- C. 56-65 Park J., Segev A. Using Common Subexpressions to Optimize Multiple Queries // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988.- C. 311-319 Rosental A., Chakravarthy U. Anatomy of a Modular Multiple Query Optimizer // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 230-239 King J.J. QUIST: A System for Semantic Query Optimization in Relational Databases // Proc. 7th Int. Conf. Very Large Data Bases, Cannes, France, Sept. 3-11, 1981. New York, 1981.- C. 510-517 Chakravarthy U.S., Fishman D.H., Minker J. Semantic Query Optimization in Expert Systems and Database Systems // Expert Database Syst.: Proc. 1st Int. Workshop, Menlo Park, Calif., Feb. 1986. New York, 1986.- C. 326-341 Chacravarthy U.S., Grant J., Minker J. Semantic Query Optimization: Additional Constraints // Proc. 1st Int. Conf. Expert Database Syst., Charleston, S.C., Apr. 1986. New York, 1986.- C. 259-270 Shenoy S.T., Ozsoyoglu Z.M.A System for Senantic Query Optimization // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Francisco, Calif., May 1987. New York, 1987.- C. 181-195 Sherhar S., Strivastava J., Dutta S. A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization // Proc. 14th Int. Conf. Very Large Data Bases, Los Angeles, Calif., Aug.-Sept. 1988. Los Altos, Calif., 1988.- C. 457-467 Lee S., Han J. Semantic Query Optimization in Recursive Databases 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988.- C. 444-451 Кузнецов С.Д. Развитие идей и приложений реляционной СУБД System R. В этом сборнике.

| |

Логическая оптимизация запросов

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

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

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

Приведение предикатов к каноническому виду оправдано всегда, но сами канонические представления могут быть различными для предикатов, обладающих разными свойствами. Если предикат включает только одно имя поля, то его каноническое представление может, например, иметь вид "имя поля op константное арифметическое выражение" (это наиболее простая форма предиката, которая очень полезна при выполнении следующего этапа оптимизации, - простой предикат селекции). Например, если начальное представление предиката имеет вид (a+5)*A op 36 (мы обозначаем малыми буквами имена объемлющих переменных, а большими - имена полей отношений), то каноническим представлением такого предиката может быть A op 36/(a+5).
Если предикат включает в точности два имени поля разных отношений (или двух разных вхождений одного отношения), то его каноническое представление может иметь, например, вид "имя поля op арифметическое выражение", где арифметическое выражение в правой части включает только константы и второе имя поля (это тоже достаточно простая и полезная форма для выполнения следующего шага оптимизации - предикат соединения; особенно важным случаем является случай эквисоединения, когда op - это равенство). Например, если в начальном представлении предикат имеет вид 5*A-a*B op b, то каноническим представлением может быть A op (b+a*B)/5. Наконец, для рассматриваемых предикатов более общего вида имеет смысл приведение предиката к каноническому представлению вида "арифметическое выражение op константное арифметическое выражение", где выражения правой и левой частей также приведены к каноническому представлению, например, в выражениях полностью раскрыты скобки и произведено некоторое лексикографическое упорядочение. Такие преобразования имеют смысл для того, чтобы в дальнейшем можно было произвести поиск общих арифметических выражений в разных предикатах запроса. Такая работа может быть оправдана, поскольку при реальном выполнении запроса вычисление арифметических выражений будет производиться при выборке каждого очередного кортежа, т.е. потенциально очень большое число раз. Естественно, что при приведении предикатов к каноническому представлению можно и нужно производить вычисления константных выражений там, где это возможно, и избавляться от логических отрицаний. Следующий необходимый класс логических преобразований связан с приведением к каноническому виду логического выражения, задающего условие выборки запроса. Как правило, используются либо дизъюнктивная, либо конъюнктивная нормальные формы. Напомним, что дизъюнктивная нормальная форма - это дизъюнкция предикатов, каждый из которых является конъюнкцией простых предикатов. Конъюнктивная нормальная форма - конъюнкция предикатов, каждый из которых является дизъюнкцией простых предикатов.


Выбор канонической формы зависит от общей организации оптимизатора. Например, специфика оптимизации в СУБД INGRES [13] требует приведения логического условия к конъюнктивной нормальной форме. При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду или в процессе нормализации логического условия), и, кроме того, может быть произведено упрощение логического выражения за счет, например, выявления конъюнкции взаимно противоречащих предикатов. Так, если в логическом выражении встречается фрагмент ...(A>5)AND(A<5)..., то его можно заменить на ...FALSE... Возможны и более "умные" упрощения. Например, фрагмент логического выражения ...(A>B)AND(B=5)... можно заменить на ...(A>5)... Как видно из последнего примера, такие упрощения могут оказаться очень существенными для дальнейшей обработки запроса: в запросе с логическим условием первого вида предполагалось выполнение соединения двух отношений; после преобразования запрос уже не требует соединения. Наконец, в традиционных оптимизаторах распространены логические преобразования, связанные с изменением порядка выполнения реляционных операций. Например, в терминах реляционной алгебры эти преобразования могут основываться на следующих правилах (A и B - имена отношений):

- (A JOIN B) WHERE restriction-on-A AND restriction-on-B эквивалентно выражению (A WHERE restriction-on-A) JOIN (B WHERE restriction-on-B); - (A WHERE restriction-1) WHERE restriction-2 эквивалентно выражению A WHERE restriction-1 AND restriction-2; - (A [attribute-list-1]) [attribute-list-2] эквивалентно выражению A [attribute-list-2]; - (A [attribute-list-1) WHERE restriction-1 эквивалентно выражению (A WHERE restriction-1) [attribute-list-1].

Здесь JOIN обозначает реляционный оператор естественного соединения отношений; A WHERE restriction - оператор ограничения отношения A в соответствии с предикатом restriction (т.е.


A WHERE restriction - это отношение, включающее кортежи, входящие в отношение A и удовлетворяющие предикату restriction); A [arrtibute-list] - проекция отношения A на заданный список атрибутов (т.е. A [attribute-list] - это отношение, состоящее из кортежей, каждый из которых получен выборкой указанных в списке полей из соответствующего кортежа отношения A, причем возможно появляющиеся кортежи-дубликаты уничтожены). Заметим, что хотя немногие реляционные системы имеют языки запросов, основанные в чистом виде на реляционной алгебре (примером такой системы может быть система SQUIRAL [23]), приведенные правила преобразований алгебраических выражений могут быть полезны и в других системах. Довольно часто реляционная алгебра используется в качестве основы внутреннего представления запроса, т.е. запрос в начальном представлении преобразуется к алгебраической форме, и следующие стадии оптимизации производятся над этим представлением. Естественно, что после этого можно выполнять и алгебраические преобразования. В частности, существуют подходы, связанные с преобразованием к алгебраической форме запросов на языке SQL. Широкое распространение этого языка побуждает нас рассмотреть соответствующие вопросы более подробно. Можно выявить две основные побудительные причины преобразований запросов на SQL к алгебраической форме. Первой, на наш взгляд, менее важной причиной может быть стремление к использованию реляционной алгебры в качестве унифицированного внутреннего интерфейса реляционной СУБД. Особенно распространен такой подход при использовании специализированных машин баз данных, на основе которых реализуются различные интерфейсы доступа к базам данных. Тогда, естественно, интерфейс машины баз данных должен быть унифицирован (например, быть алгебраическим), а все остальные интерфейсы, включая интерфейс на основе SQL, приводятся к алгебраическому. Подход к синтаксически ориентированной трансляции ограниченного подмножества SQL в незначительно расширенную реляционную алгебру описан, например, в [63].


Более важной, особенно в контексте проблем оптимизации, причиной является то, что реляционная алгебра более проста, чем язык SQL. Поэтому, если запрос преобразован к алгебраической форме, дальнейшие действия оптимизатора по выборке оптимальных планов выполнения запроса становятся более простыми. Другими словами, вообще говоря, развитый оптимизатор запросов системы, ориентированной на SQL, должен выявить все возможные планы выполнения любого запроса, но при этом "пространство поиска" этих планов в общем случае очень велико, и в каждом конкретном оптимизаторе используются свои эвристики для сокращения пространства поиска. При этом некоторые потенциально возможные планы вообще никогда не будут рассматриваться (а они могут оказаться более оптимальными). Разумное преобразование запроса на SQL к алгебраическому представлению сокращает пространтво поиска планов выполнения запроса с гарантией того, что оптимальные планы потеряны не будут. Как нам кажется, наиболее интересными работами, в которых рассматриваются специфические проблемы преобразований запросов на SQL к алгебраической форме, являются работы [57] и [65]. В [54] В.Ким заложил основу подхода, обосновал его важность и предложил ряд конкретных алгоритмов. Но при этом в некоторых конкретных методах он немного ошибся при согласовании семантики SQL и реляционной алгебры. У.Дайял в [65] показал это, ввел более точные формулировки и рассмотрел все возможные случаи. Основной особенностью языка SQL, отличающей его от языка реляционной алгебры, являются наличие возможности использовать в логическом условии выборки предикаты, содержащие вложенные подзапросы. При этом глубина вложенности не ограничивается языком, т.е., вообще говоря, может быть произвольной. Различные предикаты с вложенными подзапросами при наличии общего синтаксиса могут обладать весьма различной семантикой. Единственным общим для всех возможных семантик вложенных подзапросов алгоритмом выполнения запроса является вычисление вложенного подзапроса всякий раз при вычислении значения предиката.


Естественно поэтому стремиться к такому преобразованию запроса, содержащего предикаты со вложенными подзапросами, которое раскроет семантику подзапроса, т.е. явно отобразит ее в синтаксисе преобразованной формы, предоставив тем самым в дальнейшем оптимизатору возможность выбрать способ выполнения запроса, наиболее соответствующий семантике подзапроса. Следуя [57], будем использовать следующие обозначения: Ri - i-е отношение базы данных; Ck - k-е поле (столбец) отношения. Как отмечается в [57], предикаты, допустимые в запросах языка SQL, можно разбить на следующие четыре группы:

Простые предикаты. Это предикаты вида Ri.Ck op X, где X константа или список констант, и op - оператор скалярного сравнения (=, !=, >, >=, <, <=) или оператор проверки вхождения во множество (IS IN, IS NOT IN). Предикаты со вложенными подзапросами. Это предикаты вида Ri.Ck op Q, где Q - блок запроса^, а op может быть таким же, как для простых предикатов. Предикат может также иметь вид Q op Ri.Ck. В этом случае оператор принадлежности ко множеству заменяется на CONTAINS или DOES NOT CONTAIN. Очевидно, что эти две формы симметричны, так что достаточно рассматривать только одну. (В соответствии с принятыми при описании синтаксиса SQL правилами обозначениями нелитералов блоком запроса (query block) называется допустимая конструкция языка, начинающаяся с ключевого слова SELECT, т.е. в блоке запроса не допускаются теоретико-множественные конструкции с использованием UNION, INTERSECT и MINUS. ) Предикаты соединения. Это предикаты вида Ri.Ck op Rj.Cn, где Ri != Rj и op - оператор скалярного сравнения. Предикаты деления. Это предикаты вида Qi op Qj, где Qi и Qj - блоки запросов, а op может быть оператором скалярного сравнения или оператором проверки вхождения в множество.

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


Более того, для упрощения в [57] рассматриваются только соединения, в которых op - это операция равенства (эквисоединения). Каноническим представлением запроса на n отношениях называется запрос, содержащий n-1 предикат соединения и не содержащий предикатов со вложенными подзапросами (классов 2 и 4). Фактически, каноническая форма - это алгебраическое представление запроса. Пусть запрос имеет глубину вложенности подзапросов - 1, т.е. состоит из внешнего и одного или более вложенных блоков на одном уровне. Предположим также, что логическое условие, указанное в разделе WHERE запроса, содержит в точности один предикат класса 2 или 4. (Как показано в заключении [57], эти предположения не снижают общности). Считается, кроме того, что список выборки внутреннего блока состоит из одного элемента (как утверждает В.Ким, это требование SQL, хотя из известных нам описаний это не следует). Вводится дополнительная классификация предикатов с вложенными подзапросами класса 1. Предикаты со вложенными подзапросами типа A не содержат во вложенном подзапросе предикатов соединения с отношением внешнего блока и в списке выборке внутреннего блока указана агрегатная функция. Примером запроса с предикатом такого типа может быть

SELECT Ri.Ck FROM Ri WHERE Ri.Cn = SELECT MAX (Rj.Cm) FROM Rj WHERE Rj.Cl > a.

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

SELECT Ri.Ck FROM Ri WHERE Ri.Cn IS IN SELECT Rj.Cm FROM Rj WHERE Rj.Cl > a.

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


Именно так и поступает оптимизатор System R, не рассматривая других альтернатив. Однако не всегда этот способ выполнения запроса является оптимальным (все зависит от размеров получаемого списка скалярных значений). Внутренние подзапросы предикатов типа J содержат предикаты соединения с отношением внешнего блока и не содержат агрегатных функций. Пример использования предиката этого типа:

SELECT Ri.Ck FROM Ri WHERE Ri.Cn IS IN SELECT Rj.Cm FROM Rj WHERE Rj.Cr = Ri.Ch AND Rj.Cl > a.

Наконец, у предикатов типа JA внутренний блок содержит предикат соединения с отношением внешнего запроса и в списке выборки указана агрегатная функция. Например:

SELECT Ri.Ck FROM Ri WHERE Ri.Cn = SELECT AVG (Rj.Cm) FROM Rj WHERE Rj.Cr = Ri.Ch AND Rj.Cl > a.

Среди предикатов класса 4 выделяется подкласс таких предикатов, вложенные блоки которых Qi или Qj (или и тот, и другой) содержат предикаты соединения с отношением внешнего запроса. Обозначим этот подкласс - D. Примером запроса с предикатом типа D может быть

SELECT Ri.Ck FROM Ri WHERE (SELECT Rj.Cm FROM Rj WHERE Rj.Cn = Ri.Cl) CONTAINS (SELECT Rp.Cm FROM Rp WHERE Rp.Cr > a).

Предикаты класса 4, не относящиеся к типу D, не представляют интереса, потому что такие предикаты полностью вычисляются независимо от внешнего запроса и могут быть заменены на логическую константу (конечно, во время реального выполнения запроса). Очевидно, что это естественный и наиболее эффективный способ выполнения запроса, содержащего такой предикат. В System R обработка запросов, содержащих предикаты типов J, JA и D, производится таким образом, что внутренний подзапрос, содержащий предикат соединения, вычисляется заново для каждого кортежа внешнего запроса (т.е. для каждого кортежа, для которого проверяется предикат). Других альтернатив оптимизатор System R не рассматривает. Предлагается набор алгоритмов, преобразующих запросы, содержащие предикаты со вложенными подзапросами типов N, J, JA и D, к канонической форме. Эти преобразования, по сути, раскрывают семантику запроса, скрытую за единообразным синтаксисом SQL, путем его приведения к алгебраической форме.


Приведение к канонической форме запросов с предикатами типов N и J, содержащих оператор проверки вхождения в множество IS IN основано на следующей лемме: Пусть запрос Q1 - это

SELECT Ri.Ck FROM Ri, Rj WHERE Ri.Cn = Rj.Cm и запрос Q2 - это SELECT Ri.Ck FROM Ri WHERE Ri.Cn IS IN SELECT Rj.Cm FROM Rj.

Тогда запросы Q1 и Q2 эквивалентны, т.е. дают одинаковый резульат. При этом предполагается, что если каноническое представление запроса на n отношениях получено из запроса с N или J предикатами с операциями сравнения IS IN, то до выполнения соединений производится необходимая фильтрация и проецирование отношений, соответствующих внутреннему подзапросу с удалением возможных дубликатов. Только при таком выполнении преобразованного запроса его семантика будет совпадать с семантикой запроса в начальном виде. Это один из моментов, который критикуется в [65]. Понятно, что при наличии такого ограничения на способ выполнения преобразованного запроса нельзя считать, что в нем появились предикаты соединения общего вида. Необходима дальнейшая детализация предикатов соединения с уточнением семантики, что и предлагается в [65]. Мы кратко остановимся на этом позже. Примером преобразования запроса с предикатом класса J к канонической форме может быть следующий:

SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS IN SELECT Rj.Cm FROM Rj WHERE Ri.Cn = Rj.Cp эквивалентно SELECT Ri.Ck FROM Ri, Rj WHERE Ri.Ch = Rj.Cm AND Ri.Cn = Rj.Cp.

Однако не так просто обстоят дела с предикатами типов N и J, в которых используется оператор проверки невхождения во множество IS NOT IN. Например, запрос

SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS NOT IN SELECT Rj.Ch FROM Rj WHERE Rj.Cn = a не эквивалентен запросу SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS IN SELECT Rj.Ch FROM Rj WHERE Rj.Cn != Rj.Cp.

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


Можно сказать, что Ri и X "антисоединяются" предикатом анисоединения NOT (Ri.Ch = X.Ch). Если допустить наличие предикатов антисоединения в каноническом представлении запроса, то предыдущий запрос эквивалентен следующему:

SELECT Ri.Ck FROM Ri, X WHERE NOT (Ri.Ch = Rj.Ch).

При этом предикаты антисоединения при выполнении запроса должны вычисляться только после выполнения предикатов соединения, полученных из J-предикатов c IS NOT IN. Например, если запрос с J-предикатом

SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS NOT IN SELECT Rj.Cm FROM Rj WHERE Rj.Cn = Ri.Cp

преобразован к псевдоканонической форме

SELECT Ri.Ck FROM Ri, Rj WHERE Ri.Cp = Rj.Cn AND NOT (Ri.Ch = Rj.Cm),

то для сохранения семантики запроса в его исходной формулировки преобразованный запрос нужно понимать следующим образом: для каждого очередного кортежа отношения Ri выполняется соединение с отношением Rj в соответствии с предикатом соединения. При этом производится подотношение R1j, которое заменяет Rj в предикате антисоединения. Несколько забегая вперед, заметим, что гораздо более четко вопрос о преобразовании запросов с предикатами типа J, включающими оператор IS NOT IN, рассмотрен в [65]. Основным наблюдением, на котором основывается это рассмотрение, является связь предиката антисоединения с предикатом полусоединения и теоретико-множественной операцией разности множеств. Рассмотренные возможные преобразования обобщаются в следующем алгоритме NEST-N-J, преобразующем запросы с предикатами типов N и J к "канонической" форме (понятно, что ее можно считать только псевдоканонической, поскольку отсутствует единая семантика предикатов соединения):

Объединить все списки отношений, встречающихся во всех разделах FROM, в один список FROM. Объединить через AND логические условия всех разделов WHERE в одно логическое условие. Заменить предикаты вида Ri.Cn op (SELECT Rj.Cm) на предикаты Ri.Cn op Rj.Cm, если op отлично от IS IN и IS NOT IN; на предикаты Ri.Cn = Rj.Cm, если op - это IS IN; на предикаты NOT( Ri.Cn = Rj.Cm), если op - это IS NOT IN. Оставить список выборки внешнего запроса.



Преобразования запросов с предикатами типа JA основывается на наблюдении, что запрос Q3

SELECT Ri.Ck FROM Ri WHERE Ri.Ch = SELECT AGG (Rj.Cm) FROM Rj WHERE Rj.Cn = Ri.Cp эквивалентен запросу Q4 SELECT Ri.Ck FROM Ri WHERE Ri.Ch = SELECT Rt.C2) FROM Rt WHERE Rt.C1 = Ri.Cp, где Rt (C1, C2) = SELECT Rj.Cn, AGG (Rj.Cm) FROM Rj GROUP BY Rj.Cn.

Поскольку запрос Q4 содержит предикат типа J, он может быть преобразован к канонической форме с помощью алгоритма NEST-N-J. В более общем случае для запроса вида

SELECT R1.Cn+2 FROM R1 WHERE R1.Cn+1 op SELECT AGG (R2.Cn+1) FROM R2 WHERE R2.C1 = R1.C1 AND ... AND R2.Cn=R1.Cn

можно применить алгоритм преобразования NEST-JA:

Генерируется временное отношение Rt(C1,..., Cn, Cn+1), соответствующее запросу

SELECT C1,..., Cn, AGG (Cn+1) FROM R2 GROUP BY C1,..., Cn.

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

Алгоритм естественным образом обобщается на случай произвольной глубины вложенности внутренних подзапросов. Как отмечается в [65], описанный алгоритм не является вполне корректным, поскольку искажает семантику запроса с предикатом, включающим агрегатную функцию COUNT. Например, запрос

SELECT Ri.Ck FROM Ri WHERE Ri.Ch = SELECT COUNT (Rj.Cm) FROM Rj WHERE Rj.Cn = Ri.Cp

на самом деле не эквивалентен запросу

SELECT Ri.Ck FROM Ri, Rt WHERE Ri.Ch = Rt.Cm AND Ri.Cp = Rt.Cn,

где Rt ( Cp, Cn ) = SELECT Rj.Cp, COUNT (Rj.Cn) FROM Rj

GROUP BY Rj.Cp.

Если для некоторого кортежа отношения Ri значение поля Ri.Ch равно 0, а значение поля Ri.Cp таково, что в отношении Rj нет ни одного кортежа с таким же значением поля Rj.Cn, то по запросу в исходной формулировке будет выдано значение Ri.Ck этого кортежа (поскольку по определению функции COUNT она принимает значение 0 на пустом отношении). Преобразованный же запрос не выдаст значение Ri.Ck для этого кортежа, поскольку предикат соединения будет ложным.


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

SELECT Ri.Ck FROM Ri WHERE (SELECT Rj.Ch FROM Rj WHERE Rj.Cn = Ri.Cp) op (SELECT Rk.Cm FROM Rk), а Q6 - запрос SELECT Ri.Ck FROM Ri WHERE Ri.Cp = (SELECT C1 FROM Rt), где Rt (C1) определяется запросом SELECT Rj.Cn FROM Rj Rx WHERE (SELECT Rj.Ch FROM Rj RY WHERE RY.Cn = RX.Cn) op (SELECT Rk.Cm FROM Rk).

Запросы Q5 и Q6 эквивалентны. Заметим, что запрос Q6 содержит предикат типа N, и, следовательно, может быть преобразован к канонической форме. Запрос, определяющий отношение Rt, является формулировкой на SQL реляционной операции деления. (Напомним, что по определению результатом операции реляционного деления отношения R на отношение S арности соответственно r и s, где r > s и S - не пусто, является отношение арности r-s, включающее такие и только такие кортежи t, что для любого кортежа u, принадлежащего S, кортеж tu принадлежит R. Известно, что операция реляционного деления выражается через другие операции реляционной алгебры.) На лемме основан алгоритм NEST-D, приводящий запрос с предикатом типа D к канонической форме. Пусть задан запрос достаточно общего вида:

SELECT R1.C1 FROM R1 WHERE (SELECT R2.C1 FROM R2 WHERE R2.C2 = R1.C2 AND ... AND R2.Cn = R1.Cn) = (SELECT R3.C1 FROM R3 WHERE R3.C2 = R1.C2 AND ... AND R3.Cm = R1.Cm).

Предположим, что n > m. Тогда действие алгоритма NEST-D состоит в следующем:

Образуем два временных отношения Rt1 (C1, ..., Cm) и Rt2 (C1, ..., Cn). Rt1 определяется запросом

SELECT C1, ..., Cm FROM R3, а Rt2 - запросом SELECT C1, ..., Cn FROM R2.

Обозначим через Rt3 (Cm+1, ..., Cn) временное отношение, являющееся частным от реляционного деления Rt2 на Rt1. Преобразуем начальный запрос к каноническому виду. Для этого 3a) Исключим внутренний блок запроса с отношением R3.

3b) Заменим все ссылки на поля отношения R2 на ссылки на соответствующие поля отношения Rt3 во внутреннем блоке запроса с отношением R2.



3c) Уничтожим в этом блоке ключевые слова SELECT и FROM.

3d) Включим Rt3 в список раздела FROM внешнего запроса. В результате работы этого алгоритма запрос будет преобразован к канонической форме

SELECT R1.C1 FROM R1, Rt3 WHERE R1.Cm+1 = Rt3.Cm+1 AND ... AND R1.Cn = Rt3.Cn.

Ким в [57] обосновывает разумность произведения таких преобразований тем, что оптимизатор получает возможность выбора большего числа способов выполнения запросов. Показано, что достаточно часто открывающиеся после преобразований способы выполнения являются более эффективными в соответствии с оценками планов выполнения запросов, применяемыми в System R, чем планы, используемые в традиционном оптимизаторе этой системы. Приводится обобщенный алгоритм преобразования, пригодный для обработки запроса общего вида. Естественно, что при использовании в оптимизаторе запросов подобного подхода совсем не обязательно производить формальные преобразования запросов. Основная идея в том, чтобы оптимизатор в большей степени использовал семантику обрабатываемого запроса, а каким образом она будет распознаваться это уже вопрос применяемой техники. Исправления и уточнения подхода Кима, содержащиеся в [65], и касаются главным образом более корректной семантики запросов, выразимых на языке SQL. По ходу изложения подхода Кима мы уже отмечали некоторые семантические некорректности. Для их исправления в [65] преобразования описываются в терминах расширенной реляционной алгебры, более точно соответствующей специфике SQL. Наряду с базовыми операторами расширенная реляционная алгебра включает оператор проецирования, не устраняющий дубликаты кортежей в результирующем отношении (обычный для реляционной алгебры оператор проецирования, устраняющий дубликаты, называется в [65] оператором дельта-проецирования). Введены также следующие операции: Полусоединение отношений R и S по предикату J (Semijoin (R,S;J)) определяется как подмножество кортежей r, принадлежащих R, для каждого из которых существует кортеж s, принадлежащий S, такой, что предикат J(r,s) - истинен.


Полусоединение выражается через соединение и дельта-проекцию: Semijoin (R,S;J) = Delta-Project (Join (R,S;J);R.*). (R.* - полный набор атрибутов отношения R). Понятно, что использование полусоединения в алгоритме Кима Nest-N- J позволяет снять словестные оговорки по части особенностей трактовки операции соединения в получаемом каноническом запросе. Операция обобщенной агрегации G-Agg (R; X; fnvector), где R - отношение, X - список атрибутов этого отношения, а fnvector - список имен агрегатных функций (COUNT, SUM, MAX, MIN, AVG и их варианты с DISTINCT) с указанием имен атрибутов R, к которым применяется соответствующая функция, вырабатывает отношение, кортежи которого вычисляются по следующим правилам: отношение R разбивается на группы кортежей с одинаковым значением полей из списка X; для каждой такой группы вычисляются все агрегатные функции из списка fnvector (для функций, помеченных ключевым словом DISTINCT, вычисление производится только на кортежах группы с различными значениями атрибутов, к которым применяется функция); кортеж результата соответствует группе и включает значения атрибутов Х и значения функций из fnvector. С применением обобщенной агрегации можно модифицировать алгоритм Кима NEST-JA таким образом, что не потребуется заранее предположение о вычислении временного отношения. Поэтому оптимизатор получит большую гибкость в выборе стратегии выполнения запроса (стратегия Кима остается одним из вариантов). Явно введена операция антисоединения отношений R и S по предикату J (Antijoin (R,S;J)), определяемая как теретико-множественное дополнение отношения R к Semijoin (R,S;J). Такая трактовка также позволяет добиться большей гибкости при преобразованиях и последующей интерпретации запросов с предикатами типа J, содержащими операцию IS NOT IN. Для разрешения трудностей, связанных с искажением при преобразованиях семантики запросов, содержащих агрегатную функцию COUNT, введена операция внешнего соединения отношений R и S по предикату J, определяемая следующим образом:



Outerjoin (R,S;J) = Union (Join (R,S;J), Product (Antijoin (R,S;J), NULL-S)).

Здесь Union - оператор теоретико-множественного объединения, Join - оператор реляционного соединения, Product - оператор декартова произведения, а NULL-S - кортеж из неопределенных значений той же арности, что и S. Попросту говоря, отношение, получаемое в результате внешнего соединения двух отношений, содержит все кортежи, входящие в соединение этих отношений, а если некоторый кортеж первого отношения не соединяется ни с одним кортежем второго отношения, то по нему формируется кортеж результата путем дополнения его неопределенными значениями. Преобразованный запрос выражается в терминах операций расширенной алгебры, порядок исполнения которых, вообще говоря, может изменяться. При этом не все возможные в принципе варианты выразимы через введенные операции. Для обеспечения максимальной гибкости при преобразованиях введены еще две операции - обобщенные соединение и ограничение. Обобщенное соединение отношений R и S по предикату J, сохраняющее атрибуты X отношения R, определяется как

G-Join (R,S;X;J) = Union (Join (R,S;J),

Product (Delta-Project (Antijoin (R,S;J);X), NULL-YS)), где NULL-YS - кортеж из неопределенных значений над множеством атрибутов Y = R.* - X и S. Если R не содержит дубликатов, то G-Join (R,S;0;J) - это обычное соединение, а G-Join (R,S;R.*;J) - внешнее соединение. Оператор обобщенного ограничения отношения R по предикату P с сохранением атрибутов X определяется как

G-Restrict (R;X;P) = Union (Restrict (R;P), Product (Delta-Project((R Minus Restrict (R,P));X), NULL-Y)).

В [65] демонстрируется большое количество возможных преобразований с использованием свойств введенных операторов. Кроме тех сложных предикатов SQL, которые рассматривались Кимом, анализируются и предикаты с кванторами EXISTS и NOT EXIST, введенные в SQL уже после написания Кимом его работы. Для точности заметим, что в [65] не рассматриваются преобразования запросов с предикатами типа D в терминологии Кима. Хотя в [65] предлагается более строгий и последовательный подход, чем в [57], мы сочли необходимым посвятить основную часть этого раздела работе Кима, поскольку, на наш взгляд, она положила начало новому подходу в оптимизации запросов, сформулированных на языке SQL. Пусть эта работа была не вполне корректной и точной, но тем не менее именно она указала новый путь повышения эффективности реляционных СУБД.

| |

Некоторые частные алгоритмы

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

Насколько нам известно, возможности агерегатных запросов наиболее полно поддерживаются в языке SQL. Напомним, что в списке выборки оператора SELECT этого языка наряду с арифметическими выражениями, построенными из имен полей отношений, указанных в списке FROM, и констант, могут встречаться арифметические выражения, включающие агрегатные функции COUNT, AVG, MIN и MAX, параметрами которых могут быть арифметические выражения первого типа. При этом семантика запроса с агрегатными функциями зависит от наличия или отсутствия в запросе статьи GROUP BY. Поясним это на нескольких примерах.

Вернемся к нашей гипотетической базе данных из Раздела 2. Здесь нас будет интересовать только первое отношение этой базы данных - отношение EMP, в котором регистрируются сотудники организации. Пусть схема этого отношения определена следующим образом: EMP (EMP#, EMPNAME, SAL, COMM, DEPT#). Поля SAL и COMM, соответственно, содержат значения оклада и комиссионных, причитающихся данному служащему. Допустимы следующие запросы:

SELECT COUNT (EMP#) FROM EMP или, эквивалентно, (Q1) SELECT COUNT (*) FROM EMP .

Эти два запроса эквивалентны, поскольку EMP# является первичным ключем отношения. Каждый из них выдает общее количество служащих. Запрос

SELECT COUNT (DEPT#) FROM EMP выдает количество отделов в организации и уже, конечно, не эквивалентен запросу Q1. Может быть задан более сложный запрос, например,

SELECT COUNT (*), AVG (SAL + COMM) FROM EMP WHERE DEPT# = 6.

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

(Q2) SELECT DEPT#, AVG (SAL + COMM) FROM EMP GROUP BY DEPT#.

В этом случае в списке выборки разрешается одновременное использование выражений со значениями агрегатных функций над кортежами групп и тех полей, по значениям которых производится группировка. Как правило, при выполнении запросов с агрегатными функциями требуется сортировка отношений. В приведенных примерах сортировка не нужна только при выполнении запроса Q1: чтобы получить общее число сотрудников, достаточно просканировать отношение EMP любым способом и подсчитать количество кортежей. Единственным оптимизационным приемом, используемым при выполнении запросов с агрегатными функциями в System R, является применение в случае возможности индексов. Например, для выполнения запроса Q1, если над отношением EMP определен хотя бы один индекс, достаточно просмотреть список записей, хранящихся в листовых блоках этого индекса, вообще не обращаясь к хранимым кортежам. Возможны и более сложные случаи. Если определен индекс на поле SAL и требуется выполнить запрос SELECT AVG (SAL) FROM EMP, то можно опять обойтись без обращения к кортежам, просматривая только записи индекса. Естественно, индексы помогают и при выполнении запросов с GROUP BY. Если определен индекс на поле DEPT#, то при выполнении запроса Q2 можно обойтись без сортировки отношения EMP в соответствии со значениями поля DEPT# для построения соответствующих групп: группы естественно образуются записями индекса с равными значениями ключа.


Но этот вариант выполнения запроса Q2 совсем необязательно будет эффективнее варианта с сортировкой, поскольку для вычисления агрегатных функций потребуется, по сути дела, просканировать отношение в порядке, предписанном индексом, что может повлечь большое число обменов с внешней памятью. (Конечно, вариант выполнения запроса Q2 c использованием индекса по DEPT# будет самым оптимальным, если отношение EMP кластеризовано по DEPT#.) Таким образом, выполнение запросов с агрегатными функциями, как правило, требует сортировок. В этом случае в System R сначала выполняется сортировка, а затем над отсортированным отношением или группами его кортежей вычисляются агрегатные функции. В [67] предлагается оптимизация этой процедуры, позволяющая сократить требуемые накладные расходы. Основная идея этого предложения проста - совместить, если это возможно, процесс сортировки и вычисления агрегатных функций. Тогда отпадет необходимость повторного сканирования отсортированного отношения. Например, в случае выполнения запроса Q2 путем сортировки отношения EMP по значениям DEPT# в ходе сортировки на самом деле строится отношение (DEPT#, AVG (SAL + COMM)), причем каждый раз, когда по правилам сортировки в существующую группу с данным значением DEPT# должен был быть добавлен очередной кортеж, на самом деле происходит пересчет значения AVG (SAL + COMM). Несмотря на простоту и кажущуюся очевидность идеи, предлагаемый в [67] метод реализации этого подхода достаточно сложен. План выполнения запроса строится в терминах функционального языка высокого уровня. Далее эта программа проходит через две стадии преобразований. На первой стадии производятся преобразования плана в терминах того же языка. Получаемая программа обладает необходимыми совмещениями, но ее прямое выполнение было бы неээфективно за счет возможных рекурсий. Поэтому на второй стадии производится дополнительное преобразование компиляция программы на традиционный язык программирования, и это представление уже свободно от рекурсий и допускает эффективное выполнение.


Неясно, можно ли практически применить этот подход, но идея совмещения процессов сортировки и вычисления агрегатных функций кажется нам очень здравой. Упомянем, наконец, еще одно предложение, касающееся повышения эффективности выполнение выделенного набора запросов [69-70]. Это предложение является очень простым, может иногда резко повысить эффективность системы, но оставляет много вопросов в части реализации. Авторы предлагают хранить в базе данных наряду с базовыми отношениями тексты и результаты выполнения некоторых предписанных администратором запросов. При поступлении запроса в систему прежде всего производится поиск этого запроса среди ранее сохраненных. Если он находится среди них, то, естественно, выполнение запроса очень эффективно. В противном случае выполнение запроса происходит по общим правилам. Возможны расширения этого подхода (не предлагаемые авторами). Можно было бы относиться к хранимым запросам, как к материализованным представлениям базы данных, и разрешать задавать запросы над ними и т.д. Очевидной проблемой, эффективное решение которой неизвестно, является поддержание корректности результатов хранимых запросов при модификациях базы данных. В [69-70] предлагаются некоторые решения этой проблемы, но они не являются полными, а соответствующие действия могут вызывать существенные накладные расходы при выполнении операций вставки, удаления и модификации кортежей в базовые отношения. Отмечается одна область приложений, в которых использование хранимых отношений может резко повысить эффективность системы. Это меню-ориентированные системы со стандартным встроенным набором запросов, в которых изменения базы данных редки.

| |

Оптимизация наборов запросов

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

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

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

Поэтому основным действием при глобальной оптимизации является анализ набора запросов на предмет наличия общих свойств. Как правило, эта задача формулируется и решается в терминах поиска общих подвыражений в реляционных выражениях, соответветствующих запросам группы. Различные подходы описываются в работах [111, 117, 120-121].

Как обычно, в результате глобальной оптимизации могут порождаться различные глобальные планы. Это может следовать и из различных способов декомпозиции набора запросов, и из того, что для каждого декомпозированного представления могут существовать несколько стратегий реального выполнения.
Как и в случае локальной оптимизации изолированного запроса, при выборе глобального плана выполнения набора запросов необходимо применять оценки альтернативных планов и выбирать оптимальный план в соответствии с принятыми в системе критериями. Переборный характер проблемы и следующая из этого сложность ее точного решения вынуждает применять уменьшающие сложность эвристики. Достоверность применяемых эвристик определяет качество глобальной оптимизации. Наиболее систематическая постановка проблемы оптимизации набора запросов и приближенные к практике подходы к ее решению рассмотрены в [118]. В этой статье рассматриваются две возможные архитектуры систем, обеспечивающих оптимизацию наборов запросов (Рис. 6). Первая архитектура предполагает, что каждый запрос, входящий в группу, сначала проходит все стадии локальной оптимизации. После того, как для каждого из запросов из набора Q1, Q2,..., Qn сгенерированы оптимальные в соответствии с критериями локального оптимизатора планы выполнения P1, P2,..., Pn, в действие вступает компонент глобальной оптимизации, осуществляющий слияние локальных планов с образованием глобального плана выполнения набора запросов, в соответствии с которым производится реальное выполнение. Само применение такого подхода является эвристикой при решении проблемы глобальной оптимизации: сокращение пространства поиска при генерации глобального плана происходит за счет того, что рассматриваются фиксированные процедурные представления исходных запросов. Эта архитектура соответствует базовой организации СУБД, в которой после компиляции индивидуального запроса в той или иной форме сохраняется его выполняемый план. Например, этот подход был бы естественным в System R. Если же в системе предполагается непрерывный цикл выполнения запроса, то можно применять вторую архитектуру обработки набора запросов. Эта архитектура, вообще говоря, обеспечивает большие возможности глобальной оптимизации за счет более широкого пространства поиска возможных вариантов. С другой стороны, реальна опасность существенного увеличения сложности алгоритмов и, как следствие этого, увеличения затрат на глобальную оптимизацию.В этом случае более актуальны эвристические алгоритмы. В [118] приводятся несколько возможных алгоритмов оптимизации наборов запросов, ориентированных и на первую, и на вторую архитектуры систем. Приведены также результаты экспериментов, произведенных с использованием разных алгоритмов на основе использования коммерческого варианта СУБД INGRES. В целом, можно заметить, что актуальность глобальных оптимизаций, видимо, будет возрастать, но возникающие проблемы очень сложны и требуют дальнейшего изучения. | |

Оптимизация в распределенных системах управления базами данных

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

В этой работе мы не сможем привести полный анализ проблем оптимизации запросов и структур данных и стратегий выполнения реляционных операций во всем спектре распределенных систем баз данных. В этом мы ограничены и объемом данной статьи, и сложностью задачи. Тем не менее, основные особенности оптимизации в некотором широком классе распределенных систем баз данных мы постараемся рассмотреть. К этому классу мы отнесем распределенные системы управления базами данных, основанные на однородных локальных системах управления базами данных. Такой системой является, например, распределенная СУБД System R* [93].

Дополнительным требованием в System R*, довольно естественным, как нам кажется, для систем этого класса, является требование локальной автономности узлов сети, на которых выполняются локальные представители СУБД (незначительно модифицированная System R). Это требование означает отсутствие централизованного администрирования глобальной базой данных, отсутствие централизованного каталога базы данных и т.д. Должно допускаться локальное порождение и удаление новых отношений и индексов в локальной базе данных, причем уничтожение индекса не должно приводить к невозможности повторного выполнения ранее откомпилированных глобальных запросов. Требование локальной автономности существенно влияет и на допустимые способы оптимизации глобальных запросов (здесь и далее под глобальным запросом мы понимаем запрос, для выполнения которого требуется сетевой доступ к удаленным локальным базам данных).
Заметим, что логические уровни оптимизации запросов, включая семантическую оптимизацию, фактически, не связаны с распределенной или локальной природой баз данных (не считая некоторой специфики обработки запросов через представления). Распределенный характер баз данных затрагивает главным образом "физические" уровни оптимизации, связанные с выбором и оценкой планов выполнения запроса. Другая проблема распределенных систем баз данных касается алгоритмов выполнения двуместных реляционных операций над отношениями, хранящимися в разных узлах распределенной системы. Эта проблема существует и при традиционном хранении каждого отношения целиком в одной локальной базе данных, но становится еще более сложной и допускающей большее число решений в случае так называемых разделенных (partitioned) и раскопированных (replicated) баз данных. Такие нетрадиционные организации распределенных баз данных очень активно обсуждаются в литературе, хотя нам неизвестна какая-либо завершенная система, построенная на этих принципах. (В свое время в начальном проекте System R* предполагалось использование таких организаций, но ни одна из них не была практически реализована). | |

Оптимизация запросов

Прежде, чем перейти к рассмотрению конкретных проблем и решений в области оптимизации запросов, рассмотрим типичный для современных реляционных СУБД путь обработки запроса, поступившего в СУБД на языке запросов, например, SQL или QUEL.

Оптимизаторы с гибкой структурой

Как отмечалось в предыдущем подразделе, традиционные оптимизаторы запросов реляционных СУБД имеют достаточно жесткую организацию. Генерация множества альтернативных планов выполнения запроса производится на основе фиксированного набора стратегий, оценки планов также выполняются по фиксированным правилам (если не считать предложений, упомянутых в конце предыдущего подраздела, которые, как мы отмечали выше, примыкают к теме этого подраздела). Эта жесткость организации оптимизатора с одной стороны оправдана, поскольку направлена на сокращение пространства поиска в оптимизаторе и потому делает его работоспособным, но, с другой стороны, вызывает ряд неудобств.

Не говоря уже о том, что возможны случаи, когда в оптимизаторе по причине фиксированного набора эвристик отвергается план выполнения запроса, который в данном приложении был бы наиболее оптимальным, очень затруднена процедура встраивания в оптимизатор новых стратегий. Как показывает опыт System R, потребность в таких расширениях объективно возникает, поскольку заранее предусмотреть все возможные стратегии невозможно. В следующем разделе мы покажем, что до сих пор появляются все новые и новые алгоритмы выполнения реляционных операций, потенциальная эффективность которых выше тех, которые используются в существующих системах. Естественно, возникает желание использовать. Но при жесткой структуре традиционных оптимизаторов сделать это очень непросто. Каждый раз при внедрении в СУБД новой стратегии выполнения реляционной операции требуется по сути дела переделка оптимизатора, включая и компонент генерации планов запросов, и компонент оценки стоимости плана. В частности, необходимо включение новых оценочных формул. Эти переделки могут быть более или менее серьезными в зависимости от конкретной реализации оптимизатора, но они обязательно требуются.

В то же время, на самом деле единственным по-существу жестким компонентом СУБД является компонент, связанный с физической организацией баз данных на внешней памяти и осуществляющий доступ к данным нижнего уровня (например, RSS в System R).
В принципе СУБД допускает любую стратегию выполнения запроса, не выходящую за пределы возможностей этого компонента. На этом и основана идея подхода, который мы рассмотрим в этом подразделе. Этот подход достаточно новый, публикаций на эту тему пока немного, и мы ограничимся рассмотрением одной работы [104], которая, на наш взгляд, характерна для подхода в целом. При этом мы не будем касаться деталей организации СУБД Starburst, с разработкой которой связана статья, а сосредоточимся исключительно на особенностях оптимизатора запросов этой системы. Основным отличием оптимизатора системы Statburst от традиционных оптимизаторов является разделение выполняющейся части оптимизатора и множества правил, которыми он руководствуется при выполнении. В каком-то смысле оптимизатор становится подобным компилятору, работающему под управлением отдельно заданной табличной грамматики, или интерпретатору логического языка типа Пролога, который функционирует в окружении заданного набора правил. Аналогии, конечно, неполные, но отражают, тем не менее, суть подхода. Для функционирования оптимизатора должно быть задано множество планов, описывающих стратегии выполнения операций, STARs (Strategy Alternative Rules). Правила формулируются на специально разработанном языке. Каждое правило определяет именованный, параметризованный объект в терминах одного или более альтернативных определений. Альтернативные определения выражаются в терминах одного или более других STAR или примитивных предопределенных операторов LOLEPOP (Low-Level-Plan-Operator). В терминах System R LOLEPOP соответствует оператору интерфейса RSS. Примером STAR может быть следующее правило:

¦ ACCESS (Heap, T, C, P) ¦ ¦ IF Storage (T) = 'heap' ¦ ¦ ACCESS (BTree, T, C, P) ¦ TableScan (T, C, P) = + IF Storage (T) = 'Btree' ¦ ¦ ACCESS (RTree, T, C, P) ¦ ¦ IF Storage (T) = 'Rtree' L

Параметры STAR Tablescan T, C и P задают, соответственно, имя отношения, набор выбираемых столбцов и простой предикат выборки. ACCESS - LOLEPOP, соответствующий доступу на физическом уровне к очередному кортежу отношения, организованному одним из допустимых в Starburst способов.


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

TableAccess (T, C, P) = ¦TableScan (T, C, P) ¦ +FOR ALL i IN I(T): GET (TableScan (i, {TID}, P}, T, C, P) ¦ ¦ IF CONDITION1 L

Это правило при том же смысле параметров T, C и P, что и в предыдущем примере, задает множество допустимых стратегий доступа к отношению. Необходимые пояснения: считается, что каждое отношение включает предопределенное поле с именем TID, содержащее уникальные идентификаторы кортежей. GET - это LOLEPOP, обеспечивающая доступ к кортежу отношения по его TID'у. Наконец, вторая альтернатива будет рассматриваться только в том случаю, если к моменту рассмотрения оптимизатором этого правила условие CONDITION1 будет истинным, и при этом будет порождено множество стратегий доступа к отношению на основе всех определенных на его полях индексов. Заметим, что STAR TableScan, используемое в определении STAR TableAccess, не соответствует приведенному ранее определению Tablescan: в этом определении отсутствовала альтернатива сканирования через индекс. Соответствующее расширение определения очевидно. Еще раз подчеркнем, что альтерантивы STAR TableAccess не являются взаимно исключающими. Это правило порождает множество стратегий. В результате работы оптимизатора под управлением заданного набора правил порождается множество планов выполнения запроса (QEP - Query Evaluation Plan). Каждый план представляет собой совокупность вложенных вызовов LOLEPOP. Интерпретация каждого плана соответствует выполнению запроса. При этом правила формулируются таким образом, что при выработке каждого плана автоматически формируется его оценка.


Коротко рассмотрим, как реально обрабатывается запрос в оптимизаторе СУБД Starburst под управлением заданного набора правил. Работа компонента оптимизатора, генерирующего альтернативные планы выполнения запроса и производящего оценки порождаемых планов на основе набора правил (STAR-процессора), основывается на наличии четырех структур памяти: массива, в котором хранятся STAR во внутреннем представлении; области, содержащей сгенерированные "хорошие" планы с разными свойствами (понятие хорошего плана и его свойств мы уточним ниже); дерева вызовов, хранящего структуру вызовов STAR; списка указателей еще не обработанных вызовов. Первые две структуры сохраняются в процессе оптимизации в то время, как две последние создаются в рабочей области, выделяемой при каждом вызове STAR-процессора. Массив STAR - внешний параметр оптимизатора, остающийся неизменным в процессе оптимизации; "хорошие" планы, т.е. наиболее дешевые планы выполнения с разными свойствами, порождаются в ходе оптимизации. Опишем алгоритм, с помощью которого STAR-процессор преобразует вызов STAR в набор альтернативных планов, каждый со своим вектором свойств. Алгоритм состоит из двух фаз: фазы редукции STAR к вложенным LOLEPOP (построение альтернативных планов) и фазы определения свойств каждого плана. На первой фазе производятся действия, аналогичные действиям макропроцессоров: каждый узел в дереве вызовов заменяется на его определение применением соответствующего правила из STAR-массива с подстановкой аргументов старого узла вместо параметров определения. Все аргументы, являющиеся вызовами, обрабатываются таким же образом. Этот процесс продолжается, пока не будут обработаны все вызовы. Порядок обработки узлов определяется приоритетами, присваиваемыми каждому вызову в списке необработанных вызовов. При вызове STAR-процессора с TableAccess (EMP, {NAME, ADDRESS}, {EMP.SAL < 30.000, EMP.AGE > 45}) дерево вызовов инициализируется таким образом, как показано на Рис.4. Далее в STAR-массиве ищется STAR с именем TableAccess.


Пусть, как и раньше, определение TableAccess имеет вид

TableAccess (T, C, P) = ¦TableScan (T, C, P) ¦ +FOR ALL i IN I(T): GET (TableScan (i, {TID}, P}, T, C, P) ¦ ¦ IF CONDITION1 L

Имеются два альтернативных определения: первая альтернатива вызывает STAR с именем TableScan, вторая - LOLEPOP с именем GET. Пусть условие CONDITION1 - истинно, и I (EMP) = {INDEX1, INDEX3}. Вторая альтернатива повторяется для каждого i, принадлежащего I (T). При подстановке параметров для каждого нового узла каждый параметр в определении заменяется на соответствующий аргумент в вызове. Например, параметр T заменяется на EMP. Во втором альтернативном определении первый параметр является вызовом STAR с именем TableScan, на который указывает ссылка из первого аргумента узла GET. Указатель на TableScan получает приоритет и заносится в список необработанных вызовов. Дерево вызовов после выполнения одной итерации первой фазы алгоритма показано на Рис.5. Для выработки плана, т.е. полной редукции всех STAR к LOLEPOP, потребуются еще по крайней мере три итерации, поскольку в дереве имеется STAR TableScan, не сведенное к LOLEPOP. На второй фазе обработка начинается с наиболее вложенного LOLEPOP (обычно это LOLEPOP ACCESS, относящийся к хранимой таблице). Обработка производится "снизу вверх" с вызовом функции свойств каждого LOLEPOP. Каждая функция использует параметры вызова LOLEPOP, включая планы и их свойства. Стоимость рассматривается как часть вектора свойств и считается для каждого LOLEPOP как сумма его собственной стоимости и стоимостей всех его входных параметров-планов. Предположим, что в нашем примере в полностью расширенной форме получаются два альтернативных плана:

ACCESS (HEAP, EMP, {NAME, ADDRESS}, {EMP.SAL < 30.000, EMP.AGE > 45}) и GET (ACCESS (BTree, INDEX1, {TID}, EMP.AGE > 45), EMP, {NAME, ADDRESS}, EMP.SAL < 30.000).

В первой альтернативе нет вложенности, поэтому нужно вызвать только функцию свойств для LOLEPOP ACCESS. Эта функция выработает вектор свойств, характеризующих стоимость и эффект этого плана: из отношения EMP будут выбираться значения полей NAME, ADDRESS и TID (TID выбирается всегда) с применением предикатов на SAL и AGE; при выборе не будет поддерживаться какой-либо порядок кортежей.


Во второй альтернативе наиболее вложенный LOLEPOP ACCESS с INDEX1. Функция свойств этого LOLEPOP выработает вектор свойств, содержащий информацию от том, что выбираются только TID'ы кортежей EMP; применяется только предикат на AGE; кортежи выбираются в порядке возрастания значений поля AGE. Теперь можно вычислить функцию свойств LOLEPOP GET по его входным параметрам и их свойствам (для первого параметра). Функция свойств для GET объединяет имена полей, которые предписано выбирать GET, c именами полей, обеспечиваемых входным потоком (определяемым первым аргументом). То же касается предикатов. Следовательно, в векторе свойств GET будет указано, что выбираются значения полей NAME, ADDRESS, TID под управлением предикатов EMP.SAL < 30.000 и EMP.AGE > 45. Эти свойства идентичны свойствам предыдущей альтернативы. Однако свойства порядка кортежей иные. Поскольку свойства полученных планов различны, оба плана оставляются, если не существует более дешевого плана с теми же свойствами. После завершения обработки всех альтернативных планов управление возвращается на верхний уровень оптимизатора, где производится последующая обработка планов. При таком подходе к организации компонентов оптимизатора, ответственных за выбор и оценку альтернативных планов выполнения запросов, гибкость оптимизатора, естественно, существенно увеличивается. Смена набора стратегий и методов оценки не требует переделки программной части оптимизатора, нужно всего лишь изменить набор правил, под воздействием которых он работает. Для справедливости нужно заметить, что построение системы правил - это тоже нетривиальная задача. Это, по сути дела, тоже программирование, только на другом языке. Можно провести аналогию между оптимизатором, построенным в соответствии с описанным подходом, и синтаксически управляемым компилятором. В среде программистов нет единодушного мнения по поводу достоинств и недостатков таких компиляторов. Одних привлекает этот подход, другие предпочитают традиционные методы разработки компиляторов.Видимо, аналогично будут складываться отношения к построению оптимизаторов, управляемых правилами. Что касается мнения автора, то мне нравится эта идея, позволяющая отделить управляющую часть оптимизатора от специфики выбранных стратегий и оценок. Нам кажется, что при этом подходе увеличивается структурность сложного программного компонента СУБД и облегчаются задачи его модификаций и сопровождения. Следуя [104], мы изложили только общие идеи построения управляемого прпвилами оптимизатора. Интересные проблемы, не отраженные в [104], связаны с построением языка описания правил и проверкой корректности системы правил при формировании их внутреннего представления. Нам неизвестны публикации, в которых рассматривались бы эти проблемы, хотя, поскольку система Starburst функционирует, в ней они каким-то образом решены. | |

Особенности оптимизации запросов в распределенных реляционных СУБД

В самой общей постановке задачей компонента распределенной СУБД, оптимизирующего выполнение глобального запроса, является генерация множества альтернативных планов выполнения запроса и выбора из этого множества на основе некоторых критериев одного плана, на основе которого и производится выполнение запроса. Как видно, в такой общей постановке задача оптимизации глобальных запросов формулируется точно так же, как и в случае локальной СУБД. Однако, решение этой задачи для распределенных систем с локальной автономностью узлов существенно более сложное, чем для локальных СУБД.

Для определенности мы будем рассматривать подход к обработке глобальных запросов, основанный на их предварительной компиляции. Этот подход используется, например, в System R* [93] и состоит в том, что фазы порождения выполняемого плана глобального запроса и его реального выполнения разнесены во времени. Это является естественным развитием подхода System R и позволяет, например, заранее откомпилировать программу с включением глобальных запросов на языке SQL, а затем много раз выполнять ее без необходимости каждый раз вырабатывать планы выполнения запросов.

В результате компиляции запроса в System R*, инициированной в некотором узле сети, на самом деле порождается распределенная программа выполнения этого запроса, причем она и хранится в распределенной форме. В каждом узле сети, локальная база данных которого содержит отношения, затрагиваемые запросом, хранится часть распределенной программы, под управлением которой производятся доступ к локальным данным этого узла и взаимодействия с другими узлами, содержащими части той же распределенной программы. Выполнение запроса начинается с запуска "главной" части распределенной программы, хранящейся в том узле, в котором инициировалась компиляция запроса ("главном" узле). Эта программа путем сетевого взаимодействия вызывает другие части распределенной программы, хранящиеся в "дополинительных" узлах и т.д. Результат выполнения запроса формируется в главном узле, хотя промежуточные результаты могут быть распределены между другими локальными базами данных.
В System R* распределенная программа - это программа в машинных кодах IBM/370, но в данном случае, в контексте оптимизации запросов, для нас это не важно: программа могла бы порождаться и на некотором промежуточном языке и интерпретироваться при своем выполнении. Такой подход также практически применяется. Примером системы может быть распределенный вариант СУБД INGRES [91]. Задача оптимизации запросов остается той же - необходимо построить оптимальный план выполнения запроса в условиях локальной автономности узлов сети. Рассмотрим более подробно, как решается эта задача в System R*. Основой обработки запроса является поддержание распределенного каталога глобальной базы данных. Подробно это описано в [129]. Здесь же заметим лишь то, что за счет наличия правил именования объектов глобальной базы данных и специальных протоколов доступа к локальным каталогам баз данных при обработке запроса можно получить достоверную информацию о всех затрагиваемых запросом объектах базы данных. В принципе после этого можно было бы генерировать полные распределенные планы выполнения запроса и выбирать из них оптимальный в том узле, в котором начата обработка запроса. Но это противоречило бы принципу локальной автономности узлов сети. Действительно, предположим, что в построенном детальном плане выполнения запроса предполагается сканирование некоторого удаленного отношения R с использованием индекса I. Естественно, что во время выполнения это сканирование должно производиться в локальной СУБД, база данных которой содержит отношение R. В соответствии с требованием локальной автономности локальный администратор этой базы данных может уничтожить индекс I, и тогда для того, чтобы привести выполняемый план в корректное состояние, потребуется взаимодействие с главным узлом, что противоречит требованиям локальной автономности. В System R* применяется следующее достаточно естественное решение: При обработке запроса в главном узле генерируются не детальные, а так называемые глобальные планы выполнения запросов.


Каждый глобальный план соответствует отдельной схеме межузловых взаимодействий при выполнении запроса. В нем определяются узлы, в которых должны выполняться соединения удаленных отношений, и определяются методы и порядок передачи кортежей между узлами. Вместе с тем, глобальный план выполнения запроса не предписывает правил выполнения локальных реляционных операций в узлах, включаемых в выполнение запроса. Конечно, как и в случае построения детального плана выполнения запроса, порождается множество альтернативных планов, которые необходимо оценивать. Для оценок используется информация распределенного каталога. По существу, необходимо оценить мощности промежуточных отношений, порождаемых в удаленных узлах при выполнении локальных частей запроса. В отличие от случая локальной СУБД, оценочные формулы глобальных планов в основном базируются на оценках сетевых накладных расходов. После порождения множества альтернативных глобальных планов запроса, вычисления оценок их стоимости и выбора наиболее дешевого завершается первая фаза оптимизации глобального запроса и начинается следующая фаза - построение детального распределенного плана. Для этого прежде всего производится декомпозиция исходного запроса в соответствии с выбранным глобальным планом на компоненты, каждый из которых содержит некоторый локальный подзапрос исходного запроса в непроцедурной форме и процедурную часть, предписывающую порядок сетевых взаимодействий. Полученные компоненты рассылаются по сети в соответствующие локальные СУБД, в каждой из которых осуществляется генерация альтернативных локальных планов выполнения подзапроса и выбор наиболее дешевого из них в соответствии с локальными критериями оценок стоимости. Эта процедура практически совпадает с той, которая выполняется при обработке локального запроса в обычной System R. Заметим, что поскольку порядок сетевых взаимодействий является заранее предписанным, то это является некоторым граничным условиям выбора алтернативных локальных планов. Из этого следует, в частности, что в оценочных формулах локальных СУБД не требуется учитывать стоимость сетевых накладных расходов - оно одна и та же для всех возможных локальных планов.


Вторая фаза оптимизации происходит тем самым в распределенной манере. В ней участвуют в общем случае локальная СУБД главного узла и несколько локальных СУБД дополнительных узлов. Если запрос производится не только над базовыми отношениями, а и над представлениями, то раскрытие этого представления производится в том узле, в котором оно определялось, и в общем случае, если это представление определено над несколькими удаленными отношениями, дополнительный узел выступает для своего подзапроса как главный, т.е. вырабатывает глобальный план выполнения подзапроса и рассылает его компоненты дополнительным узлам следующего уровня. Более подробно обработка запросов над представлениями рассматривается в [129]. Заметим, что в этой существенно более сложной, чем в локальном случае, схеме оптимизации не возникают дополнительные проблемы по части оценок стоимости планов выполнения запросов. Основная проблема остается той же, что и при оптимизации в локальной СУБД,- точность оценок селективности простых предикатов. Поэтому и подходы к решению этой проблемы могут быть такими же, как рассмотренные в Разделе 2. Конечно, если использовать для оценок селективности методы, основанные на гистограммах, то при выборе глобального плана выполнения запроса могут потребоваться дополнительные сетевые накладные расходы. В System R*, как и в System R, оценки селективность основаны на предположениях о равномерности и независимости распределений значений полей отношений. Эти предположения не вполне правомерны, но зато резко упрощают проблемы оценок. Как отмечается в [95], экспериментальные результаты использования System R* показывают достаточную достоверность оценок оптимизатора (здесь, конечно, нужно учитывать экспериментальный характер баз данных), но отмечают недостаточное развитие используемых стратегий выполнения соединений удаленных отношений. Подходы к улучшению стратегий мы рассмотрим в следующем разделе. | |

Путь обработки запроса в реляционной СУБД

Следуя, например, [104], можно представить, что обработка запроса, поступившего в систему представленным на некотором языке запросов, состоит из этапов или фаз, представленных на Рис.1.

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

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

Третий этап обработки запроса состоит в выборе на основе информации, которой располагает оптимизатор, набора альтернативных процедурных планов выполнения данного запроса в соответствии с его внутреннем представлением, полученным на второй фазе.
Кроме того, для каждого плана оценивается предполагаемая стоимость выполнения запроса по этому плану. При оценках используется статистическая информация о состоянии базы данных, доступная оптимизатору. Из полученных альтернативных планов выбирается наиболее дешевый, и именно его внутреннее представление теперь соответствует обрабатываемому запросу. На четвертом этапе по внутреннему представлению наиболее оптимального плана выполнения запроса формируется выполняемое представление плана. Выполняемое представление плана может быть программой в машинных кодах, если, как в случае System R, система ориентирована на компиляцию запросов в машинные коды, или быть машинно-независимым, но более удобным для интерпретации, если, как в случае INGRES, система ориентирована на интерпретацию запросов. В нашем случае это непринципиально, поскольку четвертая фаза обработки запроса уже не связана с оптимизацией. Наконец, на последнем, пятом этапе обработки запроса происходит его реальное выполнение в соответствии с выполняемым планом запроса. Это либо выполнение соответствующей подпрограммы, либо вызов интерпретатора с передачей ему для интерпретации выполняемого плана. Заметим, что для нашего рассмотрения несущественно разделение процесса обработки запроса на подготовительную (включающую фазы 1-4) и исполнительную (фазу 5) части. В нашу схему укладывается и реальное отделение по времени первых четырех фаз от пятой (подход с предварительной компиляцией запроса до реального выполнения), и последовательное выполнение всех пяти фаз при каждом выполнении запроса. Для строгости заметим, что некоторые методы оптимизации (и даже подходы к оптимизации) довольно сильно зависят от общей организации обработки запроса. При отрыве во времени процесса компиляции от реального выполнения запроса оптимизатор располагает меньшей и менее достоверной информацией, чем в том случае, когда этап компиляции тесно привязан к этапу выполнения (выполняется в рамках транзакции пользователя). Далее в этом разделе нас главным образом будут занимать особенности выполнения фаз 2 и 3. | |

Семантическая оптимизация запросов

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

Если говорить, например, о базах данных, поддерживаемых System R, то эти знания хранятся в системных каталогах базы данных в виде ранее сформулированных ограничений целостности. Поскольку СУБД гарантирует целостность базы данных в соответствии с этими ограничениями целостности, то их можно рассматривать как аксиомы, в окружении которых формулируются запросы к базе данных.

В качестве начальных примеров преобразований запросов на основе семантической информации можно рассмотреть подходы известных СУБД System R и INGRES к обеспечению работы с базами данных через представления [1, 9]. Эти преобразования не были ориентированы на оптимизацию запросов, но имеют к ней непосредственное отношение.

Напомним, что представление базы данных в терминах языков SQL и QUEL - это именованный каталогизированный запрос, представляющий собой с точки зрения пользователей такой же объект базы данных, как и отношение. В частности, поля представления

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

Семантика представлений требует только того, чтобы они были точными. Это означает, что в момент выполнения запроса над представлением получаемая информация должна точно соответствовать текущему состоянию хранимой части базы данных.
Говорят, что выполнение запроса над представлением требует его материализации, т.е. вычисления отношения, определяемого запросом, который связан с представлением. В принципе возможны два подхода к материализации представлений. Первый подход предполагает постоянное хранение материализованного представления с поддержкой его согласованности с текущим состоянием базы данных. В этом подходе имеются свои недостатки и преимущества. К недостаткам можно отнести непредсказуемые накладные расходы на модификацию материализованных представлений при модификации хранимых отношений. Очевидное достоинство - отсутствие в потребности материализации при каждом использовании представления. Следует отметить, что этот подход нераспространен в централизованных базах данных, но достаточно интенсивно обсуждается по отношению к распределенным базам данных, в которых материализация представления может стоить очень дорого. Второй подход, который мы и приводим в качестве примера семантических преобразований запросов, состоит в том, что материализация представления с получением реального отношения как правило не производится вообще. Ниже мы уточним смысл этого "как правило". При применении этого подхода представления хранятся в каталогах базы данных во внутренней форме, получаемом после выполнения грамматического разбора запроса, определяющего данное представление. В принципе может оказаться полезным провести и логическую оптимизацию этого запроса, сохраняя уже преобразованное внутреннюю форму. При обработке запроса над представлением до выполнения фазы логической оптимизации производится слияние внутренних форм запроса и представления. При этом образуется некоторая новая преобразованная внутренняя форма, и уже над ней производится вся последующая обработка запроса, включая логическую оптимизацию и выбор оптимального плана выполнения запроса. Теперь мы можем пояснить, почему такой способ обработки запроса над представлением возможен не всегда. Дело в том, что получаемое после слияния внутреннее представление запроса не должно слишком сильно отличаться от тех внутренних представлений, которые могут получиться при обработке запросов на хранимых отношениях.


В противном случае слишком усложняются последующие фазы. Например, если представление определено с использованием SQL как

DEFINE VIEW V (C1, C2) AS SELECT C3, AVG (C4) FROM R GROUP BY C3, а запрос имеет вид SELECT C2, AVG (C1) FROM V GROUP BY C2,

то если бы допустить слияние внутренней формы запроса с внутренней формой представления, мы получили бы внутреннюю форму, не соответствующую никакому запросу на SQL над хранимым отношением. Следовательно, и дальнейшая обработка такого преобразованного запроса должна была бы быть весьма специфической. По этому поводу в System R, например, если распознается такая или аналогичная ситуация, запрос компилируется так, как если бы V было хранимым отношением, а при выполнении запроса производится явная материализация представления с порождением временного отношения. Как мы уже отмечали, такой подход применяется в System R и INGRES в основном для того, чтобы избежать необходимости в явной материализации представления при выполнении запроса. Однако, на самом деле имеется непосредственная связь и с оптимизацией. При слиянии запроса с представлением оптимизатор получает больше информации о данном запросе и потому может принимать более правильные решения. Приведем два простых примера. Пусть представление определено как

DEFINE VIEW V (C2) AS SELECT C1 FROM R WHERE C1 > 6.

Запрос формулируется следующим образом:

SELECT C2 FROM V WHERE C2 < 6.

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

SELECT C1 FROM R WHERE C1 < 6 AND C1 >6.

Уже на фазе логической оптимизации можно было бы установить, что он эквивалентен запросу


SELECT C1 FROM R WHERE FALSE, из чего следовало бы, что результат запроса пуст. Немного более сложный пример. Представление определяется как

DEFINE VIEW V (C3) AS SELECT C2 FROM R WHERE C1 = 6.

Задается запрос

SELECT C3 FROM V WHERE C3 < 16.

Предположим, что отношение R кластеризовано по значениям поля C1. (Понятие и приложения кластеризации отношений мы подробно рассмотрим в следующем подразделе. Пока для нас существенно лишь то, что может быть произведен эффективный доступ на физическом уровне к отношению R при условии, что известно условие равенства значения C1 константе). После слияния запроса с представлением мы получим внутреннюю форму, эквивалентную запросу

SELECT C2 FROM R WHERE C2 < 16 AND C1 = 6.

Для такого запроса имеется способ выполнения, не менее эффективный того, какой был бы выработан для материализованного представления V. Следовательно, явная материализация представления породила бы только дополнительные накладные расходы. Из приведенных простых примеров видно, что в ряде случаев этот способ обработки запросов над представлениями базы данных позволяет добиться более эффективного выполнения запроса за счет предоставления оптимизатору большей информации. Концептуально та же идея лежит и в основе семантической оптимизации запросов: использовать при оптимизации запроса знания, хранящиеся в базе данных независимо от данного запроса. Другим примером аналогичных преобразований запросов, опять же производимых не в целях оптимизации, но имеющих к ней непосредственное отношение, являются преобразования, производимые над запросами на модификацию базы данных для удовлетворения существующих в базе данных ограничений целостности. Этот подход впервые был применен, видимо, в СУБД INGRES [9], но используется и в других системах, например, в System R [1] для учета некоторых ограничений целостности. Напомним, что в терминах языков SQL и QUEL ограничением целостности называется сохраняемое в каталогах базы данных логическое выражение, составленное из допустимых в языке предикатов над объектами базы данных.


База данных находится в целостном состоянии, если удовлетворяются все ранее сформулированные ограничения целостности. Транзакцией называется неделимая с точки зрения целостности базы данных последовательность действий над объектами базы данных, оставляющая базу данных в целостном состоянии. Вообще говоря, допускается нарушение целостности базы данных внутри транзакции. Поясним последнее на примере. Пусть база данных, содержащая информацию о структуре некоторой организации состоит из двух отношений EMP и DEPT. В отношении EMP регистрируются все служащие данной организации. Соответственно, схема этого отношения EMP (EMP#, EMPNAME, DEPT#), где поле EMP# содержит уникальный номер служащего, поле EMPNANE - имя служащего, а DEPT# - номер отдела данной организации, в котором работает данный сотрудник. В отношении DEPT хранится информация об отделах. Это отношение имеет схему DEPT (DEPT#, EMPCOUNT), где в поле EMPCOUNT хранится общее число сотрудников данного отдела. Естественным ограничением целостности для такой базы данных в синтаксисе SQL является следующее:

ASSERT A ON DEPT: EMPCOUNT = SELECT COUNT (*) FROM EMP WHERE EMP.DEPT# = DEPT.DEPT#.

Содержательно это ограничение целостности означает, что значение поля EMPCOUNT любого кортежа отношения DEPT должно быть согласовано с реальным числом сотрудников, зарегистрированных в отношении EMP как работающих в данном отделе. Предположим, что транзакция состоит в регистрации нового сотрудника и включает два оператора

INSERT INTO EMP: <223, Smith, 3>; UPDATE DEPT SET EMPCOUNT = EMPCOUNT + 1 WHERE DEPT# = 3.

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


Во-вторых, в языке SQL и тем самым в System R существуют специальные средства автоматического поддержания целостности, так называемые \2условные воздействия\1 (triggers). В этой статье мы не рассматриваем эти и подобные вопросы, поскольку они не связаны с оптимизацией. Поскольку с одной стороны подобные ограничения целостности относятся к состоянию базы данных, а не к элементарным действиям модификации ее объектов, а с другой стороны могут нарушаться в пределах транзакции, их проверка не может быть привязана к выполнению оператора модификации, а должна производиться при заканчивании транзакции (или при выполнении явного оператора проверки целостности, который существует, например, в SQL). Но имеются и другие ограничения целостности, которые необходимо проверять при каждом выполнении операторов модификации, потенциально нарушающих эти ограничения. Например, для той же базы данных, состоящей из отношений EMP и DEPT, может быть административно наложено ограничение, что прием и увольнение служащих может производиться только в одном отделе, например, в отделе номер 6. Это ограничение невозможно сформулировать как ограничение на состояние базы данных. Формулировка его в виде требования неизменности численности сотрудников во всех отделах, кроме шестого, недостаточна, поскольку в одной транзакции могут быть последовательно выполнены операторы удаления и вставки кортежа в отношении EMP. Тем самым, можно поменять сотрудников других отделов, не нарушая такого ограничения, но не выполняя требований администрации. Для формулировки ограничений целостности такого типа в языке SQL существуют специальные средства. Например, рассмотренное выше ограничение можно сформулировать как

ASSERT B IMMIDIATE ON EMP: EMP.DEPT# = 6.

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

DELETE EMP WHERE EMPNAME = 'Brown'.



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

DELETE EMP WHERE EMPNAME = 'Brown' AND DEPT# = 6.

При выполнении такого запроса уже не понадобятся дополнительные вызовы проверок ограничений целостности второго типа, поскольку они все уже включены в логическое условие выполнения операции удаления. Кроме того, оптимизатор получает большую свободу в выборе способа выполнения запроса. Например, если отделы малочисленны, и для отношения EMP поддерживается индекс на поле DEPT#, то, возможно, наиболее оптимальным способом выполнения запроса будет сканирование отношения через индекс по DEPT# с условием DEPT# = 6 с удалением всякого выбираемого таким образом кортежа со значением поля EMPNAME, равным 'Brown'. Таким образом, и в этом случае преобразующие запрос действия, не направленные специально на оптимизацию, могут способствовать более эффективному выполнению запроса. И здесь, как и в случае обработки запросов над представлениями, удается повысить эффективность выполнения запроса за счет использования знаний, независимо хранящихся в базе данных. Мы рассмотрели эти два примера, когда можно получить более эффективный план выполнения запроса за счет его преобразования с использованием дополнительной семантической информации, чтобы показать, что идея семантической оптимизации в принципе не нова, хотя, конечно, соответствующие преобразования, производимые над запросами в System R и INGRES, никогда не назывались семантической оптимизации.


Но имеется и принципиальная разница между рассмотренными выше преобразованиями запросов и теми, которые производятся при семантической оптимизации. Основное отличие в том, что когда производятся слияния внутренней формы запроса с внутренней формой представления или внутренними формами ограничений целостности, мы обязаны полностью и однозначно использовать внешнюю информацию. В случае обработки запроса над представлением, если запрос, определяющий представление содержит условие выборки, то все это условие целиком должно быть добавлено через AND к условию выборки обрабатываемого запроса. Иначе не будет гарантирована точность представления. В случае обработки запроса на модификацию базы данных к логическому условию модификации должны быть добавлены через AND все логические условия соответствующих ограничений целостности. Иначе не будет гарантировано их соблюдение при выполнении запроса. Т.е. в этих случаях преобразования производятся однозначно и независимо от того, будут ли они способствовать оптимизации запроса. Идея семантической оптимизации в том, что используется набор знаний, которые \2не обязательно\1 использовать при обработке запроса, но использование которых в некоторой комбинации может привести к более оптимальному выполнению запроса. Если считать, например, что семантическая оптимизация имеет дело только со знаниями, представленными в виде ограничений целостности базы данных, то концептуально действия при семантической оптимизации можно понимать следующим образом. Производится множество преобразованных внутренних представлений запроса, причем каждое преобразование использует некоторый поднабор ограничений целостности. Если, например, в базе данных определены два ограничения целостности A и B с логическими условиями F1 и F2, соответственно, и обрабатывается запрос с логическим условием выборки F, то в ходе семантической оптимизации будут получены внутренние представления, эквивалентные запросам с условиями выборки F, F AND F1, F AND F2 и F AND F1 AND F2. Далее каждое из полученных внутренних представлений подвергается полной дальнейшей обработке, включая логическую оптимизацию и выбор оптимального плана выполнения; и из всех полученных таким образом планов (а все они семантически эквивалентны, т.е.


вырабатывают один и тот же результат) выбирается наиболее дешевый, который и становится реальным планом выполнения исходного запроса. Заметим, что условия целостности можно использовать для расширений условия запроса только в том случае, когда они гарантированно являются истинными. Как мы отмечали выше, в System R, например, ограничения целостности первого типа (т.е. ограничения на состояния базы данных) могут, вообще говоря, нарушаться внутри транзакции. Поэтому в общем случае при обработке запросов на языке SQL в СУБД, аналогичной System R, использование семантической оптимизации запросов на основе ограничений целостности может оказаться некорректным. Впрочем, это общее свойство подхода System R: в транзакциях, изменяющих состояние базы данных, запросы на выборку могут выдавать результаты, противоречащие ограничениям целостности базы данных. Например, пусть в транзакции выполняется следующая последовательность операторов SQL:

INSERT INTO EMP: <223, Smith, 3>; SELECT EMPCOUNT FROM DEPT WHERE DEPT# = 3; UPDATE DEPT SET EMPCOUNT = EMPCOUNT + 1 WHERE DEPT# = 3.

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

INSERT INTO EMP: <223, Smith, 3>; SELECT COUNT (*) FROM EMP WHERE EMP.DEPT# = 3; UPDATE DEPT SET EMPCOUNT = EMPCOUNT + 1 WHERE DEPT# = 3.

Если в базе данных по-прежнему существует естественное ограничение целостности A, то после семантической и логической оптимизации второй запрос может быть преобразован ко внутреннему представлению, эквивалентному запросу SELECT EMPCOUNT FROM DEPT WHERE DEPT# = 3. (Мы опускаем детали возможных преобразований). Но тогда, как и в предыдущем примере, результат запроса будет соответствовать ограничению целостности, но будет расходиться с реальным состоянием базы данных к моменту выполнения запроса. Однако, если транзакция является "только читающей", т.е.


в ней выполняются только запросы на выборку, и это известно при компиляции отдельных входящих в транзакцию операторов, то семантическая оптимизация на основе ограничений целостности будет всегда корректной, поскольку каждая транзакция при своем начале имеет гарантированно согласованное состояние базы данных. Видимо, это очень полезное на практике свойство System R - допускать нарушения целостности базы данных внутри транзакции, а также подход к автономной компиляции запросов вне их связи со свойствами транзакции, в которой они будут выполняться, и не позволили применить в этой системе механизма, подобного семантической оптимизации. Отвлекаясь теперь от особенностей SQL и System R, заметим, что для разумного применения семантической оптимизации удобно иметь семантическую информацию об ограничениях целостности базы данных в виде правил, представленных в импликативной форме. Тогда можно добиться более осмысленного порядка преобразований. Пусть, например, в нашей базе данных о структуре организации отношение EPM расширено еще двумя полями STATUS и SALARY. Значения поля STATUS характеризуют должность служащего, а поле SALARY - его оклад. На базу данных может быть наложено ограничение целостности, выражающееся в том, что оклад, превышающий 40.000, может быть назначен только начальникам отделов. С использованием SQL это ограничение может быть сформулировано как

ASSERT A ON EMP: IF SALARY > 40.000 THEN STATUS = 'Manager'.

Предположим, что обрабатывается запрос

SELECT EMPNAME, STATUS FROM EMP WHERE SALARY = 20.000.

Если не учитывать импликативного характера ограничения целостности, то по общим правилам будет произведено слияние внутренних представлений запроса и ограничения целостности, которое заведомо ничего не даст. Если же рассматривать ограничение целостности как правило преобразования, а левую часть импликации как условие применения правила, то слияние производиться и не будет, что в общем случае сэкономит время обработки запроса. Но для запроса SELECT EMPNAME, STATUS FROM EMP WHERE SALARY > 40.000 правило преобразования применимо и приводит к семантически эквивалентному запросу


SELECT EMPNAME, STATUS FROM EMP WHERE STATUS = 'Manager', выполнение которого может быть более эффективным. При применении такого подхода после произведения каждого преобразования в соответствии с некоторым правилом к полученному представлению запроса может стать применимым другое правило и т.д. В принципе возможно появление циклов преобразований. Поэтому проблема построения полного набора семантически эквивалентных представлений запроса на основе заданного набора правил в общем случае является весьма сложной. Более того, точное решение этой проблемы может потребовать затрат, соизмеримых с затратами на выполнение запроса по наиболее оптимальному плану. Это в принципе допустимо по отношению к запросам, встроенным в программу на языке программирования, которые потенциально в будущем будут выполняться много раз, но абсолютно не годится для запросов, обрабатываемых в интерактивном режиме. Поэтому, вообще говоря, необходимо применение эвристических алгоритмов, сокращающих пространство поиска, т.е. задающих условие прекращения генерации новых представлений. Подробный анализ проблемы и некоторые эвристические алгоритмы приведены, например, в [127]. Эвристики основываются на минимизации взвешенной суммы стоимостей семантической оптимизации и выполнения запроса. Примером грубой эвристики может быть следующий: оптимизация производится до тех пор, пока затраты на нее не превзойдут оценочную стоимость наиболее эффективного из всех найденных планов выполнения запроса. | |

Статистическая глобальная оптимизация

Возможности улучшений физической структуры базы данных на основе статистической информации о потоке запросов зависят от специфики конкретной СУБД. Вообще говоря, в число этих возможностей входят и изменения способа хранения отношений (если, как в СУБД INGRES, система поддерживает более одного способа хранения), и заведение новых копий отношения в распределенной базе данных (если в системе обеспечивается поддержка копий), и порождение новых разделов отношения (если система поддерживает разделенное хранение отношение) и т.д. Но если система, подобно System R, допускает сохранение ранее откомпилированных запросов и их повторное многократное выполнение, то естественным ограничением автоматических преобразований физической структуры базы данных является следующее: каковы бы не были эти преобразования, ранее откомпилированные запросы должны оставаться выполняемыми.

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

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

Примером компонента СУБД, поддерживающего оптимальный набор индексов в реляционной базе данных, может служить средство DBDSGN [119], разработанное в рамках СУБД System R. (Как отмечается в [119], на основе этого средства впоследствии был создан коммерческий продукт RDT, используемый в коммерчески доступных СУБД фирмы IBM SQL/DS и DB2.)
DBDSGN обладает двумя основными особенностями. Первой особенностью является то, что это средство не интегрировано с внутренними компонентами System R, в частности, с оптимизатором запросов. В DBDSGN используется информация, которую можно получить от системы через ее стандартный интерфейс. Язык SQL, обеспечивающий этот интерфейс, включает специальный оператор EXPLAIN, позволяющий получить информацию о типе запроса, его структуре, выбранном для выполнения плане и оценках стоимости плана целиком и его составляющих. На основе этой информации в DBDSGN принимаются решения о необходимости создания дополнительных индексов, и индексы создаются также на основе обычного интерфейса SQL (используется динамически выполняемый оператор CREATE IMAGE; подробности о возможностях System R по части динамически выполняемых операторов можно найти в [129]). Принципиальное отделение DBDSGN от оптимизатора запросов позволяет увеличить гибкость этого средства и, в частности, обеспечивает его независимость от применяемых в оптимизаторе стратегий порождения планов и их оценок. При этом, конечно, структура данных, поставляемых оператором EXPLAIN, должна быть унифицированной и однозначно понимаемой. Вторая особенность связана с тем, что задача выбора оптимального набора индексов является NP-полной, и, следовательно, ее точное решение может оказаться слишком накладным. Поэтому для решения применяется набор эвристических правил. Мы не будем описывать применяемые в DBDSGN эвристики, поскольку достаточно сложны и специфичны. Как отмечается в [119], эти эвристики позволяют получить решение, близкое к оптимальному. Заметим, что средство DBDSGN обеспечивает не автоматическое, а лишь автоматизизировнное улучшение физической структуры базы данных. Это средство является диалоговым и использует наряду с информацией от СУБД информацию, поставляемую администратором. В частности, под контролем администратора, производится и поиск решения задачи оптимального набора индексов. Каждый раз эта задача решается для одного указанного запроса, но в процессе последовательного применения DBDSGN образуется оптимальный набор индексов, соответствующий потоку запросов. Возможно, конечно, построение более автоматизированных средств, но пока практика, видимо, не требует этого. По крайней мере, в литературе подобные системы не описываются.

| |

Стратегии выполнения соединений в распределенных базах данных

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

Сначала обратимся к проблемам соединений в распределенных базах данных с традиционной организацией (подобных базам данных System R*). В System R* применяются несколько стратегий выполнения соединений удаленных отношений. Мы рассматриваем их в [129] и не будем здесь повторяться. Однако, в [95] на основе опыта использования System R* и анализа заложенных в эту систему предлагаются несколько улучшенных стратегий. Нам кажется полезным описать их.

Рассматривается соединение двух удаленных отношений S и T, расположенных в узлах 1 и 2, соответственно, под управлением предиката эквисоединения S.C1 = T.C2. Результат соединения должен быть получен в узле 1. Предполагается также следующее: Ни одно из отношений не кластеризовано по полям соединения; отсутствуют индексы на полях, отличных от полей соединения; в запросе не требуется проекция (т.е. кортежи результата включают все поля S и T); в запросе отсутствуют предикаты ограничения отношений S и T; отношения S и T хранятся в отдельных блоках внешней памяти (любой блок базы данных, содержащий кортежи S или T, не содержит кортежей других отношений).

Первый предлагаемый алгоритм заключается в том, что отношение T целиком пересылается в узел 1 и в этом узле для него создается временный индекс на поле C2. После этого в узле 1 выбирается наилучший локальный план выполнения соединения отношения S и временной копии отношения T.

Второй алгоритм основывается на использовании полусоединений. Оба отношения сортируются в соответствии со значениями полей C1 и C2 с образованием временных отсортированных файлов S' и T'.
Производится проекция S' на С1 (уничтожаются дубликаты) и результат посылается в узел 2. В этом узле выполняется полусоединение T' с полученным унарным отсортированным отношением (т.е. выбираются те кортежи T', значение поля C2 которых совпадает с каким-либо значением C1 полученного списка). Полученное промежуточное по-прежнему отсортированное отношение T'' посылается в узел 1, где выполняется соединение S' и T'' методом слияний (оба отношения уже отсортированы) и производится окончательный результат. При наличии индексов на полях отношений S.C1 и T.C2 может быть использован либо этот же алгоритм, либо его модификация, в которой отсутствует сортировка (используются сканирования отношений через индексы). Наконец, третий альтернативный алгоритм соединения двух отношений, предлагаемый в [95], основан на использовании так называемых фильтров Блюма [28]. В соответствии с этим алгоритмом, если индексы на полях S.C1 и T.C2 не определены, сначала в узле 1 для отношения S по полю C1 строится фильтр Блюма. Фильтр представляет собой битовый массив, инициализированный нулями. Для формирования фильтра производится сканирование отношения S, и к значению поля C1 каждого кортежа применяется хэш-функция, ставящая в соответствие этому значению позицию бита в массиве. Этот бит устанавливается в единицу. Сформированный фильтр посылается в узел 2. В этом узле производится сканирование отношения T и к значениям поля C2 применяется та же хэш-функция, задающая позицию соответствующего бита в фильтре. Если значение этого бита равно 1, то кортеж отношения S посылается в узел 1 в потоке кортежей T'. В этом узле выполняется соединение S и T' и формируется результат. Наличие индексов на полях S.C1 и T.C2 позволяет модифицировать алгоритм. В частности, фильтр Блюма для отношения S можно построить в этом случае, сканируя только записи индекса без потребности обращаться к кортежам отношения. В [95] приводятся оценки для каждого из трех алгоритмов и описываются экспериментальные результаты их использования в System R* в высоко- и среднескоростных сетях.


Эти результаты показывают, что альтернативные стратегии выполнения соединений в ряде случаев оказываются более эффективными, чем основные стратегии System R*. Основным, на наш взгляд, выводом из работы [95], безотносительно к проблемам System R*, является то, что исследования стратегий выполнения удаленных соединений продолжают быть актуальными и приносить полезные результаты даже при традиционной организации распределенных баз данных. Что же касается более сложных организаций, то каких-либо общепринятых решений по части оптимизации соединений пока вообще нет. Большинство работ (например, [97-100]) носят теоретический характер, в них ставятся частные проблемы и предлагаются их некоторые решения, но все это недостаточно систематизировано. Поэтому мы ограничимся тем, что покажем возможные выгоды нетрадиционных организаций и сложности, возникающие в оптимизаторах при их использовании. Основной характеристикой нетрадиционной организации распределенной распределенной базы данных является то, что одно отношение не обязано целиком храниться в одном и только одном узле (т.е. в некоторой локальной базе данных). Обсуждаются следующие варианты подобных организаций. В раскопированных (replicated) базах данных одно отношение может располагаться (целиком) в нескольких узлах сети. В этом может быть большой смысл в условиях территориальной сети, когда сетевые расходы на взаимодействие разных узлов существенно различны. Запрос может быть выполнен гораздо эффективнее, если копия требуемого отношения хранится в узле, доступ к которому не очень накладен. Кроме возможного повышения эффективности при выполнении запросов, раскопированные базы данных в принципе обеспечивают доступность к распределенной базе данных при нарушениях связности сети, если копии требуемых данных доступны в пределах образовавшегося связного раздела сети. Конечно, при этом возникает множество проблем, связанных с поддержанием согласованности копий отношения, особенно при нарушениях связности. Этот вопрос не относится к тематике оптимизации, но заметим, что большинство предложений сводится к выделению среди образовавшихся связных разделов сети одного "главного" раздела, в котором и продолжается работа.


Для выбора используются те или иные варианты алгоритмов глосования. Разделенные (partitioned) базы данных подразделяются на горизонтально и вертикально разделенные. В горизонтально разделенных базах данных в нескольких узлах сети могут располагаться подотношения одного отношения, т.е. наборы полных кортежей этого отношения, сформированные по некоторым правилам. Обычно считается, что подотношение соответствует ограничению отношения под управлением некоторого предиката ограничения. Тем самым, допускается наличие у нескольких подотношений общих кортежей. При такой организации увеличение эффективности системы возможно за счет отсутствия потребности в ряде случаев выполнения ограничения отношения на стадии выполнения запроса (если существует соответствующее подотношение). В более общем случае наличие фрагментов отношения в нескольких узлах сети позволяет распараллелить выполнение соединения. Например, если, как в [33], фрагменты отношения получены в результате применения мультиатрибутного хэширования, то удается достичь очень высокой степени распараллеливания. Заметим, что распределенные системы, ориентированные на параллельное выполнение реляционных операций, обычно строятся на основе аппаратуры высокоскоростных локальных сетей и к ним можно относиться как к машинам баз данных. Вопросы оптимизации в таких системах своеобразны и, вообще говоря, отличны от тех, которые свойственны распределенным системам рассматриваемого нами класса. В вертикально разделенных базах данных в разных узлах сети также хранятся подотношения одного отношения, но каждое подотношение представляет собой некоторую проекцию исходного отношения, т.е. состоит не из полных кортежей. Подобно тому, как в случае горизонтального разделения несколько подотношений одного отношения могли включать общие кортежи, при вертикальном разделении подотношения могут включать общие поля исходного отношения. Если учесть, что, как правило, соединения выполняются над предварительно спроецированными отношениями, а операция проекции в своем точном определении требует устранения дубликатов (т.е.


является дорогостоящей), то применение вертикального разделения может существенно повысить эффективность соединений. Заметим для корректности, что вопрос относительно дубликатов так прост только в чистой реляционной алгебре. Как только речь начинает идти о возможности использования встроенных функций таких, как COUNT и AVG, ситуация резко усложняется. Видимо, если бы вертикальное разделение было бы реализовано в System R*, то пришлось бы в подотношениях сохранять дубликаты, что само по себе выглядело бы довольно странно. Возможны различные комбинированные решения, к числу которых можно отнести возможность поддержания в распределенной базе данных материализованных представлений базы данных. Наличие такой возможности, конечно, также способствовало бы повышению эффективности системы при выполнении запросов на выборку. Использованию описанных усложненных организаций распределенных реляционных баз данных препятствуют несколько обстоятельст. Первое (и, видимо, главное) обстоятельство связано с увеличением накладных расходов при выполнении операций занесения, удаления и модификации кортежей. Простое локальное выполнение любой из этих операций в случае традиционной организации превращается в достаточно сложную сетевую процедуру при разнесении отношения тем или иным образом в несколько узлов сети (даже если забыть про возможности нарушений связности сети). При физическом проектировании распределенной базы данных очень трудно учесть оправданность усложненной организации гипотетическим повышением эффективности запросов. Во-вторых, естественно уменьшается, если не исчезает вовсе, локальная автономность узлов сети. Фактически, распределенная база данных становится административно централизованной. Наконец, в-третьих, сложность оптимизатора запросов в системе, поддерживающей нетрадиционную организацию баз данных, непомерно возрастает. Увеличивается и число потенциально возможных стратегий выполнения запросов, и число факторов, которые необходимо оценивать. Если учесть, что оптимизаторы запросов и так являются одними из наиболее сложных компонентов современных реляционных СУБД (класса System R), то их дальнейшее усложнение ставит под сомнение возможность реализации системы. Конечно, это касается универсальных систем управления базами данных. В специализированных системах с заранее известны- ми ограничениями на способы использования и повышенными требованиями к эффективности при выполнении запросов на выборку разумное использование нетрадиционных организаций баз данных вполне возможно. | |

В этой статье мы рассмотрим

В этой статье мы рассмотрим ряд вопросов, связанных с оптимизацией выполнения запросов в реляционных системах управления базами данных (СУБД). Мы рассматриваем проблемы оптимизации именно в контексте реляционных систем, хотя многие аспекты, связанные с оптимизацией организации данных на внешней памяти, распространяются и на не реляционные системы. Тем не менее мы ограничиваемся реляционными системами по двум основным причинам. Во-первых, реляционные системы (и вообще системы, ориентированные на ненавигационный непроцедурный интерфейс) с одной стороны в большей степени нуждаются в оптимизации, а с другой стороны предоставляют большие возможности оптимизации. Поэтому оптимизационные приемы в реляционных СУБД наиболее развиты. Во-вторых (и это связано с первой причиной), оптимизации в реляционных СУБД посвящено громадное количество публикаций, что позволяет произвести достаточно полный анализ проблем и решений в этой области. Заметим, что приводимая в этой статье библиография, хотя и объемна, далеко не полна. Мы не стремились к составлению исчерпывающей библиографии, ограничиваясь наиболее известными и содержательными источниками. Обычно, говоря про оптимизацию в реляционных СУБД, имеют в виду аспект оптимизации запросов, т.е. такой способ выполнения запросов, когда по начальному представлению запроса путем его синтаксических и семантических преобразований вырабатывается процедурный план выполнения запроса, наиболее оптимальный при существующих в базе данных управляющих структурах. Соответствующие преобразования начального представления запроса выполняются специальным компонентом СУБД - оптимизатором, и оптимальность производимого им плана запроса носит достаточно условный характер: план оптимален в соответствии с критериями, заложенными в оптимизатор; при этом, конечно, возможны отклонения от реальной оптимальности. В связи с оптимизацией запросов существует достаточное количество проблем: проблемы преобразований запроса к более эффективному непроцедурному представлению (логическая оптимизация), проблемы выбора набора альтернативных процедурных планов выполнения запроса, проблемы оценок стоимости выполнения запроса по выбранному плану и т.д.
Для каждого класса проблем существует более одного подхода к их решению. Например, проблемы, связанные с логической оптимизацией запросов, породили направление, называемое семантической оптимизацией [123-128].Очень многие исследователи заняты проблемами оценок стоимости процедурных планов выполнения запросов [74-90] (и до сих пор вопрос о достоверности оценок до конца не ясен). Можно рассматривать оптимизацию и в более широком смысле. Оптимизатор запросов выбирает наиболее оптимальный способ выполнения запроса на основе известных в оптимизаторе стратегий выполнения элементарных составляющих запроса и способов композиции более сложных стратегий на основе элементарных. Тем самым, пространство поиска оптимального плана выполнения запроса ограничено заранее фиксированными элементарными стратегиями. Поэтому существенным направлением исследований, непосредственно примыкающим к вопросам оптимизации, является поиск новых, более эффективных элементарных стратегий [28-49]. В контексте реляционных СУБД это более всего относится к разработке эффективных алгоритмов выполнения реляционной операции соединения наиболее накладной реляционной операции. При этом исследуются и возможности выбора более адекватных для эффективного выполнения этой операции управляющих структур базы данных, и возможности повышения эффективности за счет распараллеливания выполнения операции на специализированной аппаратуре (здесь направления исследований примыкают к тематике машин баз данных). Особенно много работ в последние годы посвящается оптимизации запросов и выбору эффективных способов выполнения реляционных операций в распределенных реляционных системах управления базами данных [91-103] (в нашей библиографии присутствует лишь небольшая часть работ, посвященных этой тематике). Здесь, конечно, существует очень много вариантов и физической организации распределенных баз данных (с поддержкой копий отношений в нескольких узлах сети, с горизонтальным или вертикальным разделением отношений в нескольких узлах, с поддержкой мгновенных снимков базы данных и т.д.), и алгоритмов выполнения реляционных операций при каждой такой организации.


Несмотря на то, что реально существуют и функционируют несколько распределенных реляционных СУБД (например, System R* и распределенная INGRES), нельзя считать, что уже найдены адекватные решения этих проблем. Наконец, сравнительно новой, еще недостаточно исследованной, но безусловно очень важной темой является глобальная оптимизация запросов в системах баз данных [111-122]. Под глобальной оптимизацией понимается совместная оптимизация заранее известного набора запросов. Это наиболее актуально в системах логического программирования (и подобных системах, связанных с обработкой правил), реализуемых на основе реляционных баз данных. При таком подходе выполнение логической программы в конечном счете сводится к выполнению большого количества запросов к базе данных, причем, как правило, запросы содержат соединения. Совместная оптимизация этих запросов может резко уменьшить общее время выполнения. Грубо говоря, глобальная оптимизация систем запросов сводится к выявлению общих подвыражений в этих запросах и затем однократному вычислению подвыражений с сохранением результатов во временных отношениях. Имеются предложения и по созданию временных управляющих структур базы данных для оптимизации выполнения системы запросов. Из приведенного (не детализированного) описания направлений исследований и разработок в области оптимизации выполнения запросов в реляционных СУБД следует практическая необъятность этой тематики. Поэтому в этой статье мы не стремимся привести подробное описание каждого направления с характеристиками всех наиболее важных и интересных решений. Мы ограничимся тем, что более точно сформулируем проблемы и приведем примеры решений на основе имеющихся источников. При этом выбор источника, конечно, полностью субъективен; с ним можно и не соглашаться. Мы проанализируем те работы, которые, на наш взгляд, наиболее важны при организации реляционных систем, ориентированных на использование языка SQL (это оправдывается все расширяющейся областью распространения этого языка), а также затронем ряд других работ, являющихся (опять же, на наш взгляд) наиболее интересными и перспективными.


Заметим, что оптимизации запросов в реляционных СУБД посвящены несколько обзорных работ. На русском языке в настоящее время доступны книги Дейта [16], Ульмана [17] и Мейера [18], в которых проблемам оптимизации посвящены отдельные главы. При этом материал в [17-18] излагается на более формальном уровне и касается меньшего количества проблем. Более современные работы рассматриваются в последнем издании книги Дейта [19]. Наконец, наиболее полный, на наш взгляд, обзор подходов и методов оптимизации запросов содержится в статье [20]. Тем не менее, мы считаем полезным написание еще одной обзорной статьи, поскольку в последнее время появился ряд новых и интересных работ, связанных с тематикой оптимизации в реляционных СУБД. Кроме того, как мы уже отмечали, в этой статье рассматривается более широкий класс проблем. Статья имеет следующую структуру. В первом (самом большом) разделе мы рассмотрим проблемы и решения в области локальной оптимизации запросов в реляционных СУБД (далее мы будем называть эту область просто оптимизацией запросов). Здесь мы коснемся следующих проблем: проблемы преобразования запросов в их непроцедурном представлении и, в частности, проблемы семантической оптимизации; проблемы выбора и оценки стоимости альтернативных планов выполнения запросов; наконец, проблемы увеличения гибкости оптимизатора по отношению к внедрению новых стратегий выполнения элементарных запросов. Во втором разделе мы приведем обзор работ, связанных с выработкой более эффективных алгоритмов выполнения реляционных операций. Главным образом нас будут занимать эффективные алгоритмы выполнения соединений, но, кроме того, мы рассмотрим и работы, связанные с оптимизацией алгоритмов вычисления агрегатных функций. Коротко будут рассмотрены предложения по аппаратному распараллеливанию реляционных операций. В третьем разделе мы остановимся на специфике оптимизации в распределенных реляционных СУБД. В каком-то смысле третий раздел является объединением первых двух, но применительно к распределенным системам.При этом, чтобы избежать повторений, мы сконцентрируемся именно на специфических чертах реляционных распределенных СУБД. Наконец, в завершающем, четвертом разделе (самом коротком) мы рассмотрим предпосылки и имеющиеся подходы к глобальной оптимизации систем запросов, затронув при этом специфические черты логической оптимизации в системах баз данных, допускающих рекурсивные определения отношений (дедуктивных базах данных). В заключение мы выделим наиболее важные практически, на наш взгляд, направления, связанные с оптимизацией выполнения запросов в реляционных СУБД. |

Выбор и оценка альтернативных планов выполнения запросов

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

Будем называть процедурным представлением или планом выполнения запроса такое его представление, в котором в детализированной форме отображен порядок выполнения операций доступа к базе данных физического уровня. Как правило, в реляционных СУБД, ориентированных на использования традиционной аппаратуры без использования специализированных процессоров или устройств внешней памяти, выделяется подсистема управления данными на физическом уровне. Например, в System R, такая подсистема называется RSS (Relational Storage System) и обеспечивает простой интерфейс, позволяющий последовательно просматривать кортежи отношений, удовлетворяющие заданным условиям на значения полей, с использованием индексов или простым сканированием страниц базы данных. Кроме того, RSS позволяет производить отсортированные временные файлы и заносить, удалять и модифицировать индивидуальные кортежи. Более подробно интерфейс RSS описывается в [129]. Аналогичные подсистемы явно или неявно выделяются во всех подобных СУБД.

Естественно, что в этих условиях до выполнения запроса необходимо выработать его процедурное представление. Кроме того, поскольку оно, вообще говоря, выбирается неоднозначно, необходимо выбрать среди альтернативных планов запроса один, наиболее удовлетворительный в соответствии с некоторыми критериями. Как правило, критерием выбора плана выполнения запроса является минимизация стоимости выполнения.
Тем самым, при обработке запроса на стадии, следующей за логической оптимизацией (Рис.1), решаются две задачи. Первая задача: Исходя из получаемого после произведения логической оптимизации внутреннего представления запроса и информации, характеризующей управляющие структуры базы данных (например, индексы), выбрать набор потенциально возможных планов выполнения данного запроса. Вторая задача: оценить стоимость выполнения запроса в соответствии с каждым альтернативным планом и выбрать план с наименьшей стоимостью. При традиционном подходе к организации оптимизаторов обе задачи решаются на основе фиксированных встроенных в оптимизатор алгоритмов. (В последнее время появился ряд работ, в которых отмечаются недостатки такого "жесткого" способа организации оптимизаторов и предлагаются альтернативные подходы. Мы рассмотрим более подробно эти предложения в следующем подразделе.) Например, оптимизатор может быть расчитан на то, что ограничение любого отношения в соответствии с заданным предикатом может быть выполнено путем последовательного просмотра отношения с использованием любого из существующих для него индексов и прямым последовательным просмотром. Так, запрос

SELECT EMPNAME FROM EMP WHERE

DEPT# = 6 AND SALARY > 15.000 может выполняться последовательным сканированием отношения EMP с выбором кортежей с DEPT# = 6 и SALARY > 15.000; сканированием отношения через индекс I1, определенный на поле DEPT#, с условием доступа к индексу DEPT# = 6 и условием выборки кортежа SALARY > 15.000; наконец, сканированием отношения через индекс I2, определенный на поле SALARY, с условием доступа к индексу SALARY > 15.000 и условием выборки кортежа DEPT# = 6. Аналогично, фиксированы и стратегии выполнения более сложных операций - реляционных соединений отношений, вычисления агрегатных функций на группах кортежей отношения и т.д. Например, в System R [2] для (экви)соединения двух отношений используются две основные стратегии: метод вложенных циклов и метод сортировок со слияниями.


Если, например, задан запрос

SELECT EMP.EMPNAME, DEPT. DEPTNAME FROM EMP, DEPT WHERE EMP.DEPT# = DEPT.DEPT#

(мы предполагаем, что в нашей базе данных, описывающей структуру организации, отношение DEPT расширено еще одним полем DEPTNAME, содержащим название отдела), то при применении метода вложенных циклов предполагается наличие двух циклов сканирования отношений EMP и DEPT соответственно. Во внешнем цикле (например, для отношения EMP) выбирается очередной кортеж EMP, и для каждого такого кортежа выполняется полное сканирование отношения DEPT с выбором таких кортежей, значения поля DEPT# которых удовлетворяет предикату соединения. При этом, естественно, рассматриваются все возможные способы сканирования отношений. (Мы описали упрощенный вариант алгоритма. Более точное описание можно найти в [129].) При использовании метода сортировок со слияниями сначала производится сортировка обоих отношений в соответствии со значениями поля DEPT# каждого отношения. При этом получаются два отсортированных временных файла EMP1 и DEPT1. Далее производится "параллельное" сканирование обоих файлов, в ходе которого выполняется "слияние" отношений в смысле операции соединения. Более точно, выбирается первый кортеж EMP1. Пусть значение поля DEPT# этого кортежа равно C1. Далее, выбирается первый кортеж из DEPT1 такой, что значение поля DEPT# этого кортежа D1 >= C1. Если удалось найти кортеж DEPT1 с D1 = C1, то это означает, что мы вошли в группу кортежей DEPT1, соединимых с текущим кортежем EMP1. Производится соединение каждого кортежа этой группы с текущем кортежем EMP1, после чего выбирается следующий кортеж EMP1, и если значение поля DEPT# в нем не изменилось, то соединение с текущей группой кортежей DEPT# повторяется. Так происходит до тех пор, пока из EMP1 не будет выбран кортеж со значением поля DEPT# С2 > C1. Тогда производится последующее сканирование DEPT1, начиная с позиции, сле- дующей за текущей группой, пока не будет выбран кортеж со значением поля DEPT# D2 >= C2 и т.д.


Если в DEPT1 найден кортеж со значением поля DEPT# D1 таким, что D1 > C1, то во временном файле EMP1 производится поиск кортежа со значением поля DEPT# C2 >= D1, и в дальнейшем EMP1 и DEPT1 меняются местами. Мы опять описали грубую схему алгоритма; в действительности используются более изощренные варианты, учитывающие возможности буферизации частей отсортированных файлов в оперативной памяти. Мы описали некоторые конкретные алгоритмы выполнения реляционных операций только для того, чтобы проиллюстрировать ранее высказанное утверждение о наличии в традиционных оптимизаторах запросов фиксированных стратегий, на основе которых вырабатываются планы выполнения запросов. Соответствующие компоненты оптимизаторов имеют достаточно сложную организацию; генерация плана выполнения сложного запроса - это многоэтапный процесс, в ходе которого учитываются свойства создаваемых при выполнении запроса по данному плану временных объектов базы данных. Например, пусть запрос задан над тремя отношениями и в нем имеются два предиката соединения:

SELECT R1.C1, R2.C2, R3.C3 FROM R1, R2, R3 WHERE R1.C4 = R2.C5 AND R2.C5 = R3.C6.

Тогда, если в плане запроса выбирается порядок выполнения соединений сначала R1 с R2, а затем полученного временного отношения - с R3, и при этом для выполнения первого соединения выбирается метод сортировок со слиянием, то временное отношение будет заведомо отсортировано по C5, и одна сортировка не потребуется, если и второе соединение будет выполняться тем же методом. Из сказанного выше следует, что компонент оптимизатора, ведающий порождением множества альтернативных планов выполнения запроса, базируется на стратегиях декомпозиции запроса на элементарные составляющие и стратегиях выполнения элементарных составляющих. Первая группа стратегий обеспечивает пространство поиска оптимального плана выполнения запроса, вторая направлена на то, чтобы в этом пространстве действительно находились эффективные планы выполнения запроса. Очевидно, что ключем к обеспечению эффективного выполнения сложного запроса является наличие эффективных стратегий выполнения элементарных составляющих.


Это исключительно важный вопрос, которому уделяется огромное внимание в теории и практике реляционных баз данных. Особенно много работ посвящается выработке эффективных алгоритмов реализации соединений отношений и аналогичных операций. Мы подробно рассмотрим эти вопросы в следующем разделе, а здесь переключимся на другую не менее важную проблему проблему обоснованного выбора плана выполнения запроса из множества альтернативных планов. Действительно, если оптимизатору удалось сгенерировать множество планов выполнения запроса на основе разумных стратегий декомпозиции и эффективных стратегий выполнения элементарных операций, то этого еще мало - нужно суметь выбрать один план, в соответствии с которым будет происходить реальное выполнение запроса. Если этот выбор будет неверным, то запрос будет выполнен неэффективно. Прежде всего необходимо определить, что понимается под эффективность выполнения запроса. Вообще говоря, это понятие неоднозначно и зависит от специфики операционной среды СУБД. В одних условиях можно считать, что эффективность выполнения запроса определяется временем его выполнения, т.е. реактивностью системы по отношению к обрабатываемым ею запросам. В других условиях определяющим является общаяя пропускная способность системы по отношению к смеси параллельно выполняемых запросов. Тогда мерой эффективности запроса можно считать количество системных ресурсов, требуемых для его выполнения: чем меньше ресурсов требуется, тем запрос эффективнее. Если пользователи СУБД работают в условиях бюджетной системы, то разумной мерой эффективности может быть бюджетная стоимость выполнения запроса и т.д. Заметим, что в любом случае оценка эффективности выполнения запроса опирается на ресурсные характеристики соответствующего плана; при использовании разных мер они просто по-разному участвуют в оценке. Далее, следуя принятой терминологии, мы вместо оценки эффективности выполнения запроса будем говорить о стоимости плана выполнения запроса. Основными ресурсами, которые расходуются при выполнении запроса, являются ресурсы процессора, ресурсы устройств внешней памяти и сетевые ресурсы.


Последний вид ресурсов, естественно, задействуется только в распределенных системах, построенных на основе аппаратуры вычислительных сетей. Специфике оптимизации выполнения запросов в таких системах мы посвящаем отдельный раздел этой статьи, а в этом разделе рассматриваются только централизованные СУБД, для выполнения запросов в которых не требуются сетевые взаимодействия. Следовательно, в нашем случае стоимость выполнения запроса определяется на основе требуемых ресурсов процессора и устройств внешней памяти. Мы уже отмечали в этом подразделе, что в традиционных реляционных СУБД, не использующих специализированную аппаратуру, как правило, явно выделяется подсистема управления доступом к данным на внешней памяти (RSS в System R). Данные на внешней памяти традиционно хранятся в блокированном виде так, что база данных занимает некоторый набор блоков одного или нескольких дисковых томов. Здесь для нас несущественно, работает ли СУБД с блоками внешней памяти напрямую через соответствующие драйверы устройств или пользуется услугами той или иной файловой системы, обеспечивающей распределение внешней памяти и доступ к блокам файла по их логическим номерам. В любом случае предполагается, что средства поддержки доступа к блокам внешней памяти порождают лишь пренебрежимо малые накладные расходы. Как правило, подсистемы управления доступом к данным на внешней памяти осуществляют буферизацию блоков базы данных в оперативной памяти. Каждый блок базы данных, прочитанный в оперативную память для выполнения запроса, сохраняется в одном из буферов буферного пула СУБД до тех пор, пока не будет вытеснен из него другим блоком базы данных. Эта особенность СУБД, конечно, очень существенна для повышения общей эффективности системы, но практически не учитывается (за исключением очень частного, но и очень важного случая) при оценках стоимостей планов выполнения запроса. В любом случае тот компонент стоимости выполнения запроса, который связан с ресурсами устройств внешней памяти, монотонно зависит от числа блоков внешней памяти, доступ к которым потребуется при выполнении запроса.


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

SELECT EMP.EMPNAME, DEPT.DEPTNAME WHERE EMP.SALARY = 20.000 AND EMP.DEPT# = DEPT.DEPT#.

Рассмотрим набор планов запроса, в которых сначала выполняется ограничение отношения ЕМР в соответствии с предикатом EMP.SALARY = 20.000 с формированием временного отношения EMP1, а затем производится соединение EMP1 с DEPT в соответствии с предикатом соединения EMP1.DEPT# = DEPT.DEPT#. Это именно множество планов запроса, поскольку мы не детализировали ни способ выполнения ограничения, ни способ выполнения соединения. Ограничение EMP потенциально можно выполнить одним из двух способов. Первый способ - последовательное сканирование отношение EMP с выбором кортежей, удовлетворяющих предикату ограничения. При этом будет произведен доступ ко всем кортежам EMP, и, следовательно, ко всем блокам базы данных, содержащим хотя бы один кортеж из EMP. Второй способ - сканирование EMP с использованием индекса на поле EMP.SALARY с условием EMP.SALARY = 20.000. (Мы предполагаем, что этот индекс существует и, кроме того, обеспечивает последовательный доступ к кортежам в порядке возрастания или убывания значения ключа. Такому условию удовлетворяет, например, общепринятая организация индексов на основе техники B-деревьев.) В этом случае нам потребуется число обращений к блокам внешней памяти, не превышающее число кортежей отношения EMP со значением поля SALARY, равным 20.000. Заметим, что в любом случае временное отношение EMP1 будет содержать ровно столько кортежей, сколько кортежей отношения EMP удовлетворяет предикату ограничения, и, следовательно, ровно столько блоков, сколько потребуется для размещения этих кортежей.


Следовательно, при оценках стоимости выполнения соединения тем или иным методом мы будем иметь достаточно точную информацию о размерах отношения - первого операнда. На этом простом примере мы показали важность показателя предиката ограничения, характеризующего долю кортежей отношения, которые удовлетворяют данному предикату, и называемого степенью селективности предиката. Степени селективности простых предикатов вида R.C op const, где R.C задает имя поля отношения базы данных, op - операция сравнения (=, !=, >, <, >=, <=), а const константа являются основой для оценок стоимости планов запроса. Чем более точно удается определить степени селективности, тем точнее будут и общие оценки и тем, следовательно, правильнее будет выбираться оптимальный план запроса. Конечно, на самом деле степень селективности предиката R.C op const зависит от вида операции сравнения, значения константы и от распределения значений поля C отношения R в базе данных, которой адресуется запрос. Если первые два параметра селективности известны при проведении оценок, то истинные распределения значений полей отношений, как правило, неизвестны. Существует ряд подходов к приближенным определениям распределений на основе статистической информации. Далее мы рассмотрим наиболее интересные из них. Если известна степень селективности предиката ограничения отношения, то тем самым известна и мощность результирующего отношения (обычно мощности хранимых отношений известны при обработке запроса). Но в оценочных формулах учитывается необходимое для выполнения запроса число обменов с внешней памятью. В приведенном выше примере, когда отношение EMP сканируется с использованием индекса на поле SALARY, предполагаемое число кортежей, удовлетворяющих условию SALARY = 20.000, конечно, является верхней оценкой требуемого числа блоков, но эта оценка может быть очень завышенной. В данном случае все зависит от распределения кортежей по блокам внешней памяти. В ряде случаев можно получить более точную оценку числа блоков.


Наконец, для сложных запросов, включающих, например, соединения более двух отношений, требуется оценивать размеры возникающих в процессе выполнения запроса промежуточных временных отношений. Как известно, соединение двух отношений R1 и R2 в соответствии с предикатом соединения R1.C1 op R2.C2, где op операция сравнения, концептуально интерпретируется как ограничение отношения R, полученного в результате декартова произведения отношений R1 и R2, предикатом R1.C1 op R2.C2. Для того, чтобы оценить мощность результирующего отношения, вообще говоря, необходимо знать степень селективности предиката соединения по отношению к прямому произведению отношений-операндов. В общем случае степень селективности такого предиката невозможно определить на основе простой статистической информации. Обычно применяются достаточно грубые эвристические оценки, хотя предлагаются и подходы, обеспечивающие большую точность. Прежде, чем приступить к рассмотрению современных подходов к решению отмеченных проблем, приведем короткий обзор подхода, применяемого для оценок стоимостей планов выполнения запроса в System R. При этом мы преследуем две цели. Во-первых, этот подход является достаточно распространенным и, как утверждают многие (например, [5]), оправданным на практике. Во-вторых, в нашем изложении мы постараемся выделить основные недостатки этого подхода, преодолению которых посвящено много работ. Подход System R базируется на двух основных предположениях о распределениях значений атрибутов отношений. Во-первых, предполагается, что значения полей всех отношений базы данных распределены равномерно. Во-вторых, считается, что значения любых двух полей распределены независимо. Первое предположение позволяет легко оценивать селективность простых предикатов на основе очень скудной статистической информации о базе данных. На втором предположении основываются оценки числа блоков, в которых располагается известное количество кортежей. Заметим сразу, что эти два предположения являются очевидным и наиболее распространенным предметом критики System R, поскольку, на наш взгляд, они сделаны исключительно в целях упрощения оптимизатора и не могут быть теоретически обоснованы.


Можно привести сколь угодно много примеров баз данных, для которых эти предположения не оправданы. В этих случаях, естественно, оптимизатор System R будет заведомо неверно оценивать планы выполнения запросов. В каталогах базы данных для каждого отношения R поддерживается следующая информация: число кортежей в данном отношении (T); число блоков внешней памяти, в которых располагаются кортежи отношения (N); для каждого поля C отношения хранится число различных значений этого поля (CD), минимальное хранимое значение этого поля (CMin) и максимальное значение (CMax). Для более точной оценки доступа к отношению через индексы для каждого индекса хранится число уровней этого индекса и число листовых страниц. (Напомним, что для организации индексов в System R используется техника B-деревьев. Поскольку в B-деревьях допускается наличие недозаполненных страниц, информация о числе уровней индекса и числе листовых страниц не выводится из информации об общем числе кортежей в отношении и числе различных значений поля, на котором определен индекс.) На нашем уровне изложения статистическая информация об индексах несущественна. Заметим, что в ранних версиях System R (например, [2]) статистики о значениях полей поддерживались только для тех полей, на которых определены индексы, но затем были внедрены и для неиндексных полей, чтобы была возможность оценивать мощность временных отношений, полученных ограничением базового отношения в соответствии с простым предикатом на неиндексном поле [6]. При наличии такой информации в условиях базового предположения о равномерности распределения значений любого поля отношения степень селективности простых предикатов вычисляется очень просто (и очень точно, если распределение на самом деле равномерно). Будем обозначать степень селективности предиката P как SEL (P). Тогда SEL (R.C = const) = CD / (CMax - CMin) (естественно, что при равномерном распределении степень селективности такого предиката не зависит от значения константы). SEL (R.C > const) = (CMax - const) / (CMax - CMin).


Аналогично, SEL (R.C < const) = (const - CMin) / (CMax - CMin) ( опять же естественно, что при равномерном распределении значений поля доля кортежей, удовлетворяющих условию попадания значения заданного поля в указанный интервал значений, линейно возрастает при увеличении размера интервала). SEL (R.C <= const) полагается равной SEL (R.C < const), а SEL (R.C >= const) равной SEL (R.C > const). При оценках числа блоков, в которых могут располагаться кортежи, удовлетворяющие предикату R.C op const, различаются два случая: отношение кластеризовано по полю C или не кластерозовано по этому полю. Заметим, что оценивать это число блоков имеет смысл только в том случае, когда сканирование отношения для его ограничения в соответствии с предикатом производится с использованием индекса на поле C. Для варианта сканирования без использования индекса понадобится всегда обратиться ровно к N блокам внешней памяти. Напомним, что под кластеризацией кортежей отношения в соответствии со значениями некоторого поля называется такое физическое размещение кортежей этого отношения в блоках внешней памяти, когда кортежи помещаются в блоки в соответствии с порядком значений выделенного поля. Если отношение кластеризовано, то в каждом блоке, содержащем кортежи этого отношения, находится группа кортежей, значения выделенного поля которых образуют интервал, и ни один кортеж со значением выделенного поля, попадающего внутрь этого интервала, не содержится в другом блоке. В этом случае селективность предиката по отношению к кортежам распространяется и на блоки, занимаемые этими кортежами. Например, если в блоке внешней памяти базы данных размещается K кортежей отношения R (параметр K в System R определяется при создании отношения и не изменяется во все время его существования), то число блоков кластеризованного отношения, содержащих кортежи, удовлетворяющие предикату R.C op const, определяется по формуле T * SEL (R.C op const) / K. (Первый член формулы задает количество кортежей, удовлетворяющих предикату.)


При оценках числа блоков, в которых могут располагаться кортежи отношения, удовлетворяющие предикату R.C op const, в случае, когда отношение не кластеризовано по полю C, при разработке начального варианта оптимизатора исходили из того, что в этом случае кортежи могут быть произвольным образом разбросаны по блокам базы данных, содержащим кортежи данного отношения. Поэтому оценка производилась по формуле T * SEL (R.C op const). Однако впоследствии было замечено, что эта формула дает завышенный результат, если число кортежей отношения, удовлетворяющих предикату, достаточно велико (т.е. селективность предиката низкая) [6]. Записи листовых блоков индекса отношения R на поле C в System R имеют следующую структуру: значение ключа, список уникальных идентификаторов кортежей отношения R, у которых поле C имеет тоже значение, что и ключ. Уникальный идентификатор кортежа (tid) обеспечивает прямой доступ к кортежу и содержит, в частности, номер блока, в котором располагается кортеж (более подробно организация блоков базы данных System R и способ адресации кортежей описываются в [129]). Если при организации списка tid'ов в записи индекса поддерживать в каждом списке упорядоченность tid'ов в соответствии с номерами блоков, содержащих соответствующие кортежи, то при последовательном просмотре кортежей с фиксированным значением ключа появляется некоторый элемент порядка. В уточненном варианте оптимизатора System R для оценки числа блоков, обращения к которым должны произойти при таком просмотре используется формула N * (1 - (1 - 1/N) ** CD). Эта формула была впервые выведена и обоснована Яо [74]. Понятно, что на основе этой формулы можно оценить и число блоков, обращения к которым потребуются при сканировании отношения через индекс для ограничения отношения в соответствии с предикатом с известной (оцененной ранее) селективностью. Заметим, что и в этом подходе к оценке числа блоков с жестким разделением случаев кластеризованности отношения R по полю C и отсутствия такой кластеризованности проявляется некоторая ограниченность System R.


В реальных условиях кластеризованность отношения по одному полю не обязательно означает полное отсутствие кластеризованности того же отношения по другим полям (предположение System R о независимости распределений значений разных полей отношения). Ниже мы рассмотрим один из предложенных в последнее время подходов к более адекватному учету реально существующих кореляций атрибутов отношений. Предположения о равномерности распределений значений атрибутов отношений позволяют достаточно просто оценивать и мощности отношений, являющихся результатами двухместных реляционных и теоретико-множественных операций над отношениями. Рассмотрим, например, как можно оценить степени селективности двух предикатов соединения - R1.C1 = R2.C2 и R1.C1 > R2.C2. Начнем с предиката эквисоединения R1.C1 = R2.C2. Пусть Ti и CDi - число кортежей в отношении Ri и число различных значений поля Ci, соответственно. Тогда в отношении Ri существует Ti/CDi групп кортежей с одинаковыми значениями поля Ci. Очевидно, что при выполнении операции соединения кортежи каждой группы кортежей отношения R1 могут быть соединены с кортежами не более, чем одной группы отношения R2 (и наоборот). Если кортежи двух групп соединяются, то в результирующем отношении образуется (T1/CD1) * (T2/CD2) кортежей. (Оценка числа кортежей в каждой группе в виде Ti/CDi правомерна в соответствии с предположением о равномерности распределения). Очевидно, что соединиться могут не более, чем Min (CD1, CD2) групп. Поэтому верхней оценкой мощности результирующего отношения может быть Min (CD1, CD2) * (T1/CD1) * (T2/CD2). Соответственно, степень селективности предиката эквисоединения можно оценить, как Min (CD1, CD2) / (CD1 * CD2).Заметим, что эта оценка достаточно точна (при соблюдении предположении о равномерности распределения), если отношения "хорошо" соединяются, как, например, отношения EMP и DEPT из нашего примера по полю DEPT#. Формула для оценки степени селективности предиката соединения R1.C1 > R2.C2 выводится немного более сложно.


Обозначим через CiMax и CiMin, соответственно, максимальное и минимальное значения поля Ci.Пусть кортежи из j- ой группы кортежей отношения R1 имеют значение поля C1, равное cj. Тогда число кортежей отношения R2, удовлетворяющих предикату соединения относительно j-ой группы отношения R1 можно оценить как ((C2Max - cj) / (C2Max - C2Min)) * T2. Число кортежей в результирующем отношении, возникающих при соединении j-ой группы кортежей отношения R1 с кортежами отношения R2 оценивается как (T1/CD1) * ((C2Max - cj) / (C2Max - C2Min)) * T2. Для получения оценки общего числа кортежей в результирующем отношении необходимо просуммировать полученную формулу по j для всех групп отношения R1. При этом можно воспользоваться тем, что в силу предположения о равномерности распределения значений поля C1 сумму cj можно оценить как CD1 * AVG (cj) = CD1 * (C1Max C1Min) / CD1 = C1Max - C1Min. Результирующая формула для оценки мощности результирующего отношения имеет вид: T1 * T2 * (C2Max - C1Max + C2Min) / (C2Max - C2Min). Соответственно, селективность предиката оценивается по формуле (C2Max C1Max + C2Min) / (C2Max - C2Min). Аналогично строятся формулы для оценок мощностей результатов других двухместных операций. Оценки селективности предикатов используются в оценочных формулах оптимизатора и для оценки затрат ресурсов процессора. Эти оценки базируются на предположении (подтверждаемом на практике) о том, что основная часть процессорной обработки производится в RSS. Поэтому процессорные затраты измеряются просто числом обращений к RSS, которое в свою очередь определяется числом кортежей, получаемых при сканировании хранимого или временного отношения, т.е. селективностью логического выражения, состоящего из простых предикатов. (Напомним, что при сканировании отношения при каждой операции взятия следующего кортежа RSS получает параметр - логическое выражение, состоящее из простых предикатов и представляющее условие, которому должен удовлетворять следующий кортеж. На самом деле при использовании RSS в System R это логическое условие всегда одно и то же в пределах каждого сканирования и представляет собой предикат ограничения соответствующего отношения [129].) При предположениях о равномерности и независимости значений разных полей отношения селективность логического выражения, составленного из простых предикатов, легко оценить при известных степенях селективности простых предикатов.


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

SELECT EMP.EMPNAME, DEPT.DEPTNAME FROM EMP, DEPT WHERE EMP.SALARY = 20.000 AND DEPT.DEPT# > 4 AND EMP.DEPT# = DEPT.DEPT#

оценивается следующий план выполнения: выполнить ограничение отношения EMP с использованием некластеризованного индекса на поле EMP.SALARY и порождением временного отношения EMP1 (элементарная операция ОП1); выполнить ограничение отношения DEPT с использованием кластеризованного индекса на поле DEPT.DEPT# и порождением временного отношения DEPT1 (элементарная операция ОП2); отсортировать отношение EMP1 в соответствии со значениями поля EMP.DEPT# с порождением отсортированного файла EMP2 (элементарная операция ОП3); отсортировать отношение DEPT1 в соответствии со значениями поля DEPT.DEPT# с порождением отсортированного файла DEPT2 (элементарная операция ОП4); соединить файлы EMP2 и DEPT2 по полю DEPT# (элементарная операция ОП5). Стоимость элементарных операций ОП1 и ОП2 оценивается на основе формул и статистической информации об отношениях EMP и DEPT. Стоимость элементарных операций ОП3, ОП4 и ОП5 оценивается на основе формул и оценок операций ОП1 и ОП2 (мощности отношений EMP1 и DEPT1).


Оценка общей стоимости плана выполнения запроса складывается из оценок для ОП1, ОП2, ОП3, ОП4 и ОП5. Подход к построению альтернативных планов выполнения запроса и вычислению оценок их стоимостей и набор применяемых в System R оценочных формул подробно описан в [4]. В более доступной работе [5] содержится систематическое описание оценочных формул, применимых при тех же предположениях, но не соответствующих точно System R. Последнее, что мы заметим по поводу подхода System R, касается поддержания статистической информации об отношениях базы данных. Естественно, что поддерживать в динамике изменений базы данных точную информацию, например, о числе различных значений полей отношения, было бы слишком накладно (особенно для тех полей, на которых не определены индексы). Поэтому эта информация не корректируется при каждом изменении базы данных. В System R существует специальная утилита сбора статистики, которая и производит соответствующие коррекции либо периодически, либо по явному указанию оператора. Перейдем теперь к рассмотрению предложений, позволяющих более точно оценивать стоимости выполнения планов запроса. Эти предложения можно разбить на два класса. В соответствии с предложениями первого класса оптимизатор сохраняет жесткую структуру, аналогичную структуре оптимизатора System R, но при произведении оценок используются не предположения System R о равномерности распределений значений полей отношений и независимости распределений значений разных полей отношений, а на более точной статистической информации, характеризующей реальные распределения значений. Предложения второго класса более революционны и исходят из того, что для произведения планов выполнения запросов и их оценок оптимизатор должен снабжаться некоторой информацией, характерной для конкретной области приложений. Естественно, что если отказаться от предположения о равномерности распределения значений поля отношения, то необходимо каким-то образом уметь установить реальное распределение значений. Как отмечается, например, в [90], существует два базовых подхода к оценкам распределения значений поля отношения: параметрический и основанный на методе сигнатур.


Подход System R является тривиальным частным случаем метода параметрической оценки распределения - любое распределение оценивается как равномерное. Более развитый подход был предложен Христодолакисом в [81]. Он предложил использовать для оценки реального распределения значений поля отношения серию распределений Пирсона, в которую входят распределения от равномерного до нормального. Выбор распределения из серии производится путем вычисления нескольких параметров на основе выборок реально встречающихся значений. К сожалению, нам неизвестна какая-либо реализованная система, в оптимизаторе которой использовался бы этот подход, и потому мы ничего не можем сказать по поводу его практической применимости на основе экспериментальных результатов. Заметим лишь, что его применение ограничено только числовыми значениями (т.е. на основе этого подхода нельзя, например, оценить распределение поля, значения которого - текстовые строки переменного размера). Метод оценки распределения на основе сигнатур в общих словах можно описать следующим образом. Область значений поля разбивается на несколько интервалов. Для каждого интервала некоторым образом устанавливается число значений поля, попадающих в этот интервал. Внутри интервала значения считаются распределенными по некоторому фиксированному закону (как правило, принимается равномерное приближение). Рассмотрим теперь более точно два альтернативных подхода, связанных с сигнатурным описанием распределений. Традиционный подход, описываемый, например, в [81], состоит в том, что область значений поля разбивается на N интервалов равного размера, и для каждого интервала подсчитывается число значений полей из кортежей данного отношения, попадающих в интервал. Например, предположим, что наше отношение регистрации сотрудников предприятия EMP расширено еще одним полем AGE - возраст сотрудника. Пусть всего в организации работает 60 сотрудников в возрасте от 10 до 60 лет. Тогда гистограмма, изображающая распределение значений поля AGE может иметь вид, показанный на Рис.2.


Гистограмма построена исходя из разбиения диапазона значений поля AGE на 10 интервалов. Рассмотрим, как можно оценивать селективность простых предикатов, задаваемых на поле AGE, с использованием такой гистограммы. Пусть в интервал значений AGE Si попадает Ki значений. Тогда SEL (EMP.AGE = const), если значение константы попадает в интервал значений Si, можно оценить следующим образом: 0 <= SEL (EMP.AGE) <= Ki/T (T - общее число кортежей в отношении EMP). Отсюда средняя оценка степени селективности предиката - Ki / (2 * T). Например, SEL (AGE = 29) оценивается в 40/200 = 0.2, а SEL (AGE = 16) оценивается в 5/200 = 0.025. Это, конечно, существенно более точные оценки, чем те, которые можно получить, исходя из предположений о равномерности распределений. Но не так хорошо обстоят дела с оценками селективности простых предикатов с неравенствами. Например, пусть требуется оценить степень селективности предиката EMP.AGE < const. Если значение константы попадает в интервал Si, и SUMi - суммарное количество значений AGE, попадающих в интервалы S1, S2, ..., Si, то SUMi-1 / T <= SEL (AGE < const) <= SUMi / T. Тогда средняя оценка степени селективности (SUMi-1 + SUMi) / (2 * T), и ошибка оценки может достигать половины веса подобласти, в которую попадает значение константы предиката. Самое неприятное, что ошибка оценки зависит от значения константы и тем больше, чем больше значений поля содержится в соответствующем интервале гистограммы. Например, SEL (AGE < 29) оценивается как 46/100 <= SEL (AGE < 29) <= 86/100, откуда оценка степени селективности (46 + 86) / 200 = 0.66; при этом ошибка оценки может достигать 0.2. В то же время SEL (AGE < 49) оценивается существенно более точно. Для устранения этого дефекта оценок на основе гистограммного описания распределения в [84] был предложен другой подход к описанию распределений значений поля отношения. Основная идея подхода состоит в том, что в отличии от чистого метода гистограмм множество значений поля разбивается на интервалы, размер которых выбирается таким образом, чтобы в каждый интервал (кроме, вообще говоря, последнего) попадало одинаковое число значений поля.


Как и в чистом методе гистограмм, количество интервалов выбирается исходя из ограничений по памяти, и чем оно больше, тем точнее получаемые оценки. При выборе разбиения области значений на десять интервалов получаемая псевдогистограммная картина распределений значений поля AGE показана на Рис.3. На Рис.3 область значений поля AGE отношения EMP разбита на 10 интервалов таким образом, что в каждый интервал попадает ровно по 10 значений поля AGE. При этом, естественно, интервалы имеют разные размеры. Граничные значения интервалов показаны над вертикальными линиями. Особенностью псевдогистограммы является то, что в ней возможны, в частности, интервалы, правая и левая граница которых совпадают. На нашем рисунке таким интервалом является интервал (28,28). Он образовался по причине наличия в отношении EMP большого (большего десяти) числа кортежей со значением AGE = 28. Очевидно, что с использованием такой "псевдогистограммы" ошибки при оценках степеней селективности предикатов с операцией, отличной от равенства, уменьшаются. В [84] приводятся два метода оценок селективности простых предикатов на основе такого способа описания распределения с минимизацией возможной ошибки в худшем случае и в среднем. При этом размер ошибки уже не зависит от значения константы предиката и уменьшается при увеличении числа интервалов. Существенным недостатком метода псевдогистограмм по сравнению с методом гистограмм является необходимость сортировки отношения в соответствии со значениями поля для построения псевдогистограммы распределений значений этого поля. С другой стороны, ситуация ничем не отличается от получения статистик в System R: чтобы получить число различных значений поля, на котором не определен индекс, нужно отсортировать отношение в соответствии со значениями этого поля. Тем не менее, в [84] предлагается некоторый подход, который позволяет получить достоверную псевдогистограмму без необходимости сортировки всего отношения. Подход основывается на статистике Колмогорова, из которой применительно к случаю реляционных баз данных следует, что если из отношения выбирается образец из 1064 кортежей, и b - доля кортежей в образце со значениями поля C < V, то с достоверностью 99% доля кортежей во всем отношении со значениями поля C < V находится в интервале [b-0.05, b+0.05].


При уменьшении мощности образца достоверность, естественно, уменьшается. В системе FASTSCAN, упоминаемой в [84], псевдогистограмма строится точно для отношений, включающих не более 1064 кортежей, иначе для построения псевдогистограммы используется образец из 1064 кортежей. Приведены экспериментальные результаты оценок селективности простых предикатов в FASTSCAN в сравнении с реальной селективностью и оценками System R. Если не учитывать того, что эксперименты производились на специально сгенерированной базе данных, результаты FASTCSAN существенно превосходят результаты System R. Тем не менее, несмотря на все недостатки предположений System R о равномерности распределений значений полей, заметим, что подход этой системы хорошо сбалансирован, и отказ от этого предположения повлек бы далеко идущие последствия. Чтобы учитывать неравномерность распределения значений, в общем случае при оценке селективности простого предиката должно быть известно значение его константы. Но в System R, вообще говоря, это не так. В языке SQL, когда он используется как язык, встроеннный в традиционный язык программирования, допускается использование констант, задаваемых переменными объемлящей программы. Поскольку обработка предложений SQL происходит на стадии прекомпиляции программы (подробно этот процесс описывается в [129]), то значения таких констант, конечно, неизвестны. Тем не менее нужно оценивать планы выполнения запроса. Предположения о равномерности распределений значений позволяют это сделать. Нам неизвестны предложения, которые могли бы при сохранении базового подхода System R к обработке запросов (а он нам кажется очень удачным) позволить воспользоваться в полном объеме информацией о реальных (или оцененных статистически) распределениях значений. Остановимся теперь на предложениях, касающихся более точной оценки числа блоков внешней памяти, обращения к которым потребуются при выполнении запроса. Как мы отмечали, основным предположением, на котором основываются оценки System R, является предположение о независимости распределений значений различных полей отношения.


При этом по- разному оценивается число блоков, обращения к которым потребуются при сканировании отношения без использования индекса, при сканировании через некластеризованный и кластеризованный индексы. Оценки, касающиеся случаев сканирования без индекса и с использованием кластеризованного индекса, достаточно удовлетворительны (при выбранных в System R подходах к организации внешней памяти и оценке селективности простых предикатов). В [86] предлагается подход, позволяющий более точно оценивать число блоков, затрагиваемых при сканировании отношения через некластеризованный индекс. Основная идея состоит в отказе от предположения о независимости распределений значений разных полей отношения. В действительности, достаточно часто всречается случай, когда атрибуты отношения коррелируют. Например, в нашей базе данных, описывающей струтуру организации, в отношении EMP значения полей SALARY и AGE, скорее всего, распределены не независимо: достаточно часто оклад сотрудника возрастает по мере возрастания его возраста. Следовательно, если отношение EMP кластеризовано в соответствии со значениями поля SALARY, то кортежи этого отношения, вообще говоря, не разбросаны произвольно по блокам внешней памяти относительно значений поля AGE. Поэтому, если оценивать число блоков внешней памяти, к которым потребуются обращения при сканировании отношения с использованием индекса на поле AGE для ограничения отношения по предикату AGE op const, с применением подхода System R, то оценки могут оказаться весьма завышенными. Предлагается учитывать зависимость распределений значений полей при оценках числа блоков. Более точно, если отношение R кластеризовано по полю С1 и оценивается число блоков, к которым потребуются обращения при сканировании отношения с использованием индекса на поле C2, то предлагается учитывать зависимость распределений значений полей C1 и C2 (корреляцию атрибутов отношения). Фактически, исходя из фактов кластеризации отношения по полю C1 и зависимости распределений значений C1 и C2, можно оценить степень кластеризации отношения по полю C2.


Эта идея кажется очень интересной и полезной, поскольку неформулизуемая на уровне разного рода зависимостей корреляция атрибутов может быть очень распространенным явлением и, конечно, ее хотелось бы уметь учитывать. Весь вопрос в том, как это делать практически. Алгоритм, предлагаемый в [86], служит только для иллюстрации идеи и не имеет практического значения. Может быть, можно разработать какой-либо метод на основе сигнатурных описаний распределений значений разных полей отношения. На сегодняшний день никакие разработки на эту тему нам неизвестны. Заметим еще по этому поводу, что непосредственной логической связи между методами оценок селективности простых предикатов и методами учета корредяции атрибутов нет. В некоторых работах, например, в [41, 87-88] приводятся критика подхода System R и соответствующие предложения по части более правильного учета стоимости обменов с внешней памяти при выполнении запроса. В оценочных формулах System R участвует оцениваемое число блоков внешней памяти, к которым потребуются обращения при выполнении запроса. При этом неявно подразумевается, что обмен с каждым блоком требует одних и тех же накладных расходов независимо от того, как реально расположены эти блоки на устройстве внешней памяти. Не учитываются те факты, что, во-первых, основное время при выполнении обмена с дисковым устройством с подвижными головками тратится на подвод головок к нужному цилиндру. Если несколько обменов выполняется последовательно с блоками, расположенными на одном цилиндре, то все обмены, кроме первого, занимают существенно меньшее время. Из этого следует, что при распределении блоков внешней памяти для хранения отношения базы данных не произвольным образом, а стремясь расположить блоки одного отношения на одном или близком цилиндрах, оценки System R для последовательного сканирования отношения без использования индекса могут быть весьма завышенными. В [88] приводятся наблюдения, показывающие, что при правильном расположении отношения на устройстве внешней памяти, последовательное сканирование отношения без использования индекса становится настолько эффективным, что преимущества от использования индексов можно получить только в исключительных случаях.


Конечно, для того, чтобы получить преимущество от физической близости блоков внешней памяти, хранящих кортежи одного отношения, требуется непрерываемость последовательного сканирования отношения. Если в цепочку обращений к блокам одного отношения вклинится обращение к блоку другого отношения, хранящегося на другом цилиндре, то позиционирование головок будет нарушено, и следующий обмен с блоком первого отношения потребует большего времени. Наиболее естественно можно применить этот подход в аппаратных или программных процессорах реляционной алгебры, когда элементарным действием процессора является выполнение реляционной операции. Тем не менее, иногда эту особенность аппаратуры можно эффективно использовать даже при использовании такого мало приспособленного для этого интерфейса, как интерфейс RSS System R. Например, в интерфейсе RSS предусмотрена операция, позволяющая за одно обращение к RSS выполнить ограничение указанного отношения и отсортировать получаемое подотношение в соответствии со значениями указанного поля (более подробно это описано в [129]). При выполнении такой операции может оказаться выгодно полностью узурпировать дисковое устройство, на котором располагается отношение, на все время его сканирования. Во-вторых, современные устройства внешней памяти позволяют выполнять обмен с набором физически смежных блоков. Это позволяет выбирать при организации базы данных на внешней памяти размер логического блока больший размера физического блока, и для чтения или записи такого логического блока потребуется один физический обмен с устройством. В принципе можно выбирать размер логического блока для каждого отношения индивидуально, исходя из особенностей предполагаемого потока запросов. В [41] аналогичный подход предлагается по отношений к размерам блоков индексов. Надо сказать, что основным препятствием к гибкому выбору размеров логических блоков является увеличивающаяся сложность при работе с буферами оперативной памяти, которые обычно поддерживаются в СУБД для сокращения числа обменов с внешней памятью.


Последняя тема, которую мы затронем в этом подразделе, тесно смыкается с темой следующего подраздела и касается оценок стоимости выполнения планов запросов на основе информации, предоставляемой пользователями. Мотивировкой этого подхода является тот очевидный факт, что какими бы изощренные универсальные методы оценки селективности простых предикатов не использовались в оптимизаторе, найдется такое приложение, для которого эти оценки не будут адекватными. Примером работы, в которой предлагается такой подход, может служить [90]. В этой работе обозреваются проблемы, возникшие при организации библиографической базы данных с использованием реляционной СУБД. Показано, что в этом приложении универсальные подходы к оценке селективности простых предикатов сравнения с ключевыми словами дают неудовлетворительный результат. Приведен ряд специфических методов оценки селективности и показано, что в контексте библиографического поиска более точные оценки дают такие простые методы, как, например, основанные только на учете длины ключевого слова (допустимые в запросах ключевые слова группируются в соответствии с длинами, и для каждой группы вычисляется средняя селективность). В рассматриваемой системе, основанной на развитии СУБД INGRES, допускается определение пользователем процедур оценки селективности простых предикатов. Допускается определение глобальных и локальных процедур оценки селективности предикатов. Глобальные процедуры связываются с предикатами указанного вида, локальные - с предикатами, задаваемыми для указанного отношения или указанного поля. При выборе процедуры оценки локальные процедуры имеют более высокий приоритет, чем глобальные. Интерфейс всех оценочных процедур фиксирован: на входе к ним поступают реальные параметры предиката и статистическая информация, поддерживаемая СУБД; на выходе процедура выдает оценочное число кортежей, удовлетворяющих предикату. Подчеркивается, что поставляемые пользователями оценочные процедуры могут базироваться на статистике, связанной с реальным потоком запросов, из-за чего точность оценок повышается.К сожалению, в статье не описываются детали реализации, но подход представляется нам очень перспективным. | |

Оптимизаторы реляционных СУБД представляют собой

Оптимизаторы реляционных СУБД представляют собой наиболее сложные компоненты систем. Эффективность системы в целом во многом определяется тем, насколько мощной является оптимизация. Как мы старались показать, во всех существующих направлениях, связанных с оптимизацией, наряду с определенным продвижением остается множество нерешенных проблем. Большинство из них имеют переборный характер и требуют развитых эвристических решений. Большей частью в стороне остались проблемы оптимизации, возникающие при использовании специализированной аппаратуры машин баз данных, где главное внимание уделяется возможностям распараллеливания выполнения запросов. Спектр возможных архитектур машин баз данных достаточно широк, и проблемы оптимизации имеют свою специфику для каждой из конкретных архитектур. Соответствующие вопросы освещены в литературе явно недостаточно. Другая специфическая проблема оптимизации запросов и структур хранения и стратегий доступа относится к системам управления базами данных в оперативной памяти. Такие системы становятся все более актуальными в связи с постоянным увеличением объемов доступной в ЭВМ оперативной памяти и ее удешевлением. Особенно интересны возможности использования оперативной памяти, сохраняющей информацию после выключения питания. Если удастся добиться удешевления и этого вида аппаратуры, могут наступить революционные изменения в подходах к организации и баз данных, и систем управления ими с соответствующим смещением акцентов в области оптимизации. Тем не менее, в ближайшие годы, скорее всего, наиболее распространены будут по-прежнему системы управления базами данных, хранимыми в традиционно организованной внешней памяти. Поэтому и традиционные оптимизаторы еще долго будут сохранять свою актуальность. | |

---

---