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