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