Оптимизация SQL запросов в реляционных СУБД
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
того, для каждого плана оценивается предполагаемая стоимость выполнения запроса по этому плану. При оценках используется статистическая информация о состоянии базы данных, доступная оптимизатору. Из полученных альтернативных планов выбирается наиболее дешевый, и именно его внутреннее представление теперь соответствует обрабатываемому запросу.
На четвертом этапе по внутреннему представлению наиболее оптимального плана выполнения запроса формируется выполняемое представление плана. Выполняемое представление плана может быть программой в машинных кодах или быть машинно-независимым, но более удобным для интерпретации. В нашем случае это непринципиально, поскольку четвертая фаза обработки запроса уже не связана с оптимизацией.
На последнем, пятом этапе обработки запроса происходит его реальное выполнение в соответствии с выполняемым планом запроса. Это либо выполнение соответствующей подпрограммы, либо вызов интерпретатора с передачей ему для интерпретации выполняемого плана.
2.1Логическая оптимизация запросов
При классическом подходе к организации оптимизаторов запросов на этапе логической оптимизации производятся некоторые эквивалентные преобразования внутреннего представления запроса, которые "улучшают" начальное внутреннее представление по некоторым фиксированным в оптимизаторе плане.
При этом "улучшение" носит достаточно условный характер, т.е. тесно связано со спецификой общей организации оптимизатора, в частности, с тем, как устроена третья фаза обработки запроса.
Довольно часто реляционная алгебра используется в качестве основы внутреннего представления запроса, т.е. запрос в начальном представлении преобразуется к алгебраической форме, и следующие стадии оптимизации производятся над этим представлением. Естественно, что после этого можно выполнять и алгебраические преобразования.
В частности, существуют подходы, связанные с преобразованием к алгебраической форме запросов на языке SQL. Можно выявить две основные побудительные причины преобразований запросов на SQL к алгебраической форме. Первой причиной может быть стремление к использованию реляционной алгебры в качестве унифицированного внутреннего интерфейса реляционной СУБД. Особенно распространен такой подход при использовании специализированных машин баз данных, на основе которых реализуются различные интерфейсы доступа к базам данных. Тогда, естественно, интерфейс машины баз данных должен быть унифицирован (например, быть алгебраическим), а все остальные интерфейсы, включая интерфейс на основе SQL, приводятся к алгебраическому.
Реляционная алгебра более проста, чем язык SQL. Поэтому, если запрос преобразован к алгебраической форме, дальнейшие действия оптимизатора по выборке оптимальных планов выполнения запроса становятся более простыми. Другими словами, вообще говоря, развитый оптимизатор запросов системы, ориентированной на SQL, должен выявить все возможные планы выполнения любого запроса, но при этом "пространство поиска" этих планов в общем случае очень велико, и в каждом конкретном оптимизаторе используются свои эвристики для сокращения пространства поиска. При этом некоторые потенциально возможные планы вообще никогда не будут рассматриваться (а они могут оказаться более оптимальными).
Разумное преобразование запроса на SQL к алгебраическому представлению сокращает пространство поиска планов выполнения запроса с гарантией того, что оптимальные планы потеряны не будут.
Основной особенностью языка SQL, отличающей его от языка реляционной алгебры, являются наличие возможности использовать в логическом условии выборки предикаты, содержащие вложенные подзапросы. При этом глубина вложенности не ограничивается языком, т.е., вообще говоря, может быть произвольной.
Предикаты, допустимые в запросах языка SQL, можно разбить на следующие четыре группы:
1)Простые предикаты. Это предикаты вида Ri.Ck op X, где X константа или список констант, и op - оператор скалярного сравнения (=, !=, >, >=, <, <=) или оператор проверки вхождения во множество (IS IN, IS NOT IN).
2)Предикаты со вложенными подзапросами. Это предикаты вида 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 может быть оператором скалярного сравнения или оператором проверки вхождения в множество.
2.2Семантическая оптимизация запросов
Представление базы данных в терминах языков SQL и QUEL - это именованный каталогизированный запрос, представляющий собой с точки зрения пользователей такой же объект базы данных, как и отношение. В частности, поля представления (элементы списка выборки соответствующего запроса) могут иметь отдельные имена, поскольку поле представления необязательно соответствует полю хранимой таблицы (эл