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

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

Если говорить, например, о базах данных, поддерживаемых 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]. Эвристики основываются на минимизации взвешенной суммы стоимостей семантической оптимизации и выполнения запроса. Примером грубой эвристики может быть следующий: оптимизация производится до тех пор, пока затраты на нее не превзойдут оценочную стоимость наиболее эффективного из всех найденных планов выполнения запроса.

Назад | Содержание | Вперед