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

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

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

18.3.1. Преобразования запросов на основе семантической информации

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

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

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

Подход 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,

из чего следовало бы, что результат запроса пуст.

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

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

Ограничением целостности называется сохраняемое в каталогах базы данных логическое выражение, составленное из предикатов над объектами базы данных. База данных находится в целостном состоянии, если удовлетворяются все заданные ограничения целостности.

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

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

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

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

DELETE EMP WHERE EMPNAME = 'Brown'.

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

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

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

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

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

18.3.2. Использование семантической информации при оптимизации запросов

Семантическая оптимизация основана на наличии в базе данных семантической информации, которую не обязательно использовать при обработке запроса, но использование которой может привести к его более оптимальному выполнению. Если семантическая оптимизация имеет дело только со знаниями, представленными в виде ограничений целостности базы данных, то при семантической оптимизации производится множество преобразованных внутренних представлений запроса; при каждом преобразовании используется некоторый поднабор ограничений целостности. Если, например, в базе данных определены два ограничения целостности A и B с логическими условиями F1 и F2 и обрабатывается запрос с условием выборки F, то в ходе семантической оптимизации будут получены внутренние представления, эквивалентные запросам с условиями F, F AND F1, F AND F2 и F AND F1 AND F2.

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

Для разумного применения семантической оптимизации удобно представлять ограничения целостности базы данных в импликативной форме. Тогда можно добиться более осмысленного порядка преобразований. Пусть, например, в нашей базе данных о структуре организации отношение EPM расширено полями STATUS и SALARY. Значения поля STATUS характеризуют должность служащего, а поле SALARY - его оклад. Может быть наложено ограничение целостности, выражающееся в том, что оклад, превышающий 40.000, может быть назначен только начальникам отделов:

   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',

выполнение которого может быть более эффективным.

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

Предыдущая глава || Оглавление || Следующая глава