Введение

В этой статье мы рассмотрим ряд вопросов, связанных с оптимизацией выполнения запросов в реляционных системах управления базами данных (СУБД). Мы рассматриваем проблемы оптимизации именно в контексте реляционных систем, хотя многие аспекты, связанные с оптимизацией организации данных на внешней памяти, распространяются и на не реляционные системы. Тем не менее мы ограничиваемся реляционными системами по двум основным причинам. Во-первых, реляционные системы (и вообще системы, ориентированные на ненавигационный непроцедурный интерфейс) с одной стороны в большей степени нуждаются в оптимизации, а с другой стороны предоставляют большие возможности оптимизации. Поэтому оптимизационные приемы в реляционных СУБД наиболее развиты. Во-вторых (и это связано с первой причиной), оптимизации в реляционных СУБД посвящено громадное количество публикаций, что позволяет произвести достаточно полный анализ проблем и решений в этой области. Заметим, что приводимая в этой статье библиография, хотя и объемна, далеко не полна. Мы не стремились к составлению исчерпывающей библиографии, ограничиваясь наиболее известными и содержательными источниками. Обычно, говоря про оптимизацию в реляционных СУБД, имеют в виду аспект оптимизации запросов, т.е. такой способ выполнения запросов, когда по начальному представлению запроса путем его синтаксических и семантических преобразований вырабатывается процедурный план выполнения запроса, наиболее оптимальный при существующих в базе данных управляющих структурах. Соответствующие преобразования начального представления запроса выполняются специальным компонентом СУБД - оптимизатором, и оптимальность производимого им плана запроса носит достаточно условный характер: план оптимален в соответствии с критериями, заложенными в оптимизатор; при этом, конечно, возможны отклонения от реальной оптимальности.

В связи с оптимизацией запросов существует достаточное количество проблем: проблемы преобразований запроса к более эффективному непроцедурному представлению (логическая оптимизация), проблемы выбора набора альтернативных процедурных планов выполнения запроса, проблемы оценок стоимости выполнения запроса по выбранному плану и т.д. Для каждого класса проблем существует более одного подхода к их решению. Например, проблемы, связанные с логической оптимизацией запросов, породили направление, называемое семантической оптимизацией [123-128].Очень многие исследователи заняты проблемами оценок стоимости процедурных планов выполнения запросов [74-90] (и до сих пор вопрос о достоверности оценок до конца не ясен).

Можно рассматривать оптимизацию и в более широком смысле. Оптимизатор запросов выбирает наиболее оптимальный способ выполнения запроса на основе известных в оптимизаторе стратегий выполнения элементарных составляющих запроса и способов композиции более сложных стратегий на основе элементарных. Тем самым, пространство поиска оптимального плана выполнения запроса ограничено заранее фиксированными элементарными стратегиями. Поэтому существенным направлением исследований, непосредственно примыкающим к вопросам оптимизации, является поиск новых, более эффективных элементарных стратегий [28-49]. В контексте реляционных СУБД это более всего относится к разработке эффективных алгоритмов выполнения реляционной операции соединения наиболее накладной реляционной операции. При этом исследуются и возможности выбора более адекватных для эффективного выполнения этой операции управляющих структур базы данных, и возможности повышения эффективности за счет распараллеливания выполнения операции на специализированной аппаратуре (здесь направления исследований примыкают к тематике машин баз данных).

Особенно много работ в последние годы посвящается оптимизации запросов и выбору эффективных способов выполнения реляционных операций в распределенных реляционных системах управления базами данных [91-103] (в нашей библиографии присутствует лишь небольшая часть работ, посвященных этой тематике). Здесь, конечно, существует очень много вариантов и физической организации распределенных баз данных (с поддержкой копий отношений в нескольких узлах сети, с горизонтальным или вертикальным разделением отношений в нескольких узлах, с поддержкой мгновенных снимков базы данных и т.д.), и алгоритмов выполнения реляционных операций при каждой такой организации. Несмотря на то, что реально существуют и функционируют несколько распределенных реляционных СУБД (например, System R* и распределенная INGRES), нельзя считать, что уже найдены адекватные решения этих проблем.

Наконец, сравнительно новой, еще недостаточно исследованной, но безусловно очень важной темой является глобальная оптимизация запросов в системах баз данных [111-122]. Под глобальной оптимизацией понимается совместная оптимизация заранее известного набора запросов. Это наиболее актуально в системах логического программирования (и подобных системах, связанных с обработкой правил), реализуемых на основе реляционных баз данных. При таком подходе выполнение логической программы в конечном счете сводится к выполнению большого количества запросов к базе данных, причем, как правило, запросы содержат соединения. Совместная оптимизация этих запросов может резко уменьшить общее время выполнения. Грубо говоря, глобальная оптимизация систем запросов сводится к выявлению общих подвыражений в этих запросах и затем однократному вычислению подвыражений с сохранением результатов во временных отношениях. Имеются предложения и по созданию временных управляющих структур базы данных для оптимизации выполнения системы запросов.

Из приведенного (не детализированного) описания направлений исследований и разработок в области оптимизации выполнения запросов в реляционных СУБД следует практическая необъятность этой тематики. Поэтому в этой статье мы не стремимся привести подробное описание каждого направления с характеристиками всех наиболее важных и интересных решений. Мы ограничимся тем, что более точно сформулируем проблемы и приведем примеры решений на основе имеющихся источников. При этом выбор источника, конечно, полностью субъективен; с ним можно и не соглашаться. Мы проанализируем те работы, которые, на наш взгляд, наиболее важны при организации реляционных систем, ориентированных на использование языка SQL (это оправдывается все расширяющейся областью распространения этого языка), а также затронем ряд других работ, являющихся (опять же, на наш взгляд) наиболее интересными и перспективными.

Заметим, что оптимизации запросов в реляционных СУБД посвящены несколько обзорных работ. На русском языке в настоящее время доступны книги Дейта [16], Ульмана [17] и Мейера [18], в которых проблемам оптимизации посвящены отдельные главы. При этом материал в [17-18] излагается на более формальном уровне и касается меньшего количества проблем. Более современные работы рассматриваются в последнем издании книги Дейта [19]. Наконец, наиболее полный, на наш взгляд, обзор подходов и методов оптимизации запросов содержится в статье [20]. Тем не менее, мы считаем полезным написание еще одной обзорной статьи, поскольку в последнее время появился ряд новых и интересных работ, связанных с тематикой оптимизации в реляционных СУБД. Кроме того, как мы уже отмечали, в этой статье рассматривается более широкий класс проблем.

Статья имеет следующую структуру. В первом (самом большом) разделе мы рассмотрим проблемы и решения в области локальной оптимизации запросов в реляционных СУБД (далее мы будем называть эту область просто оптимизацией запросов). Здесь мы коснемся следующих проблем: проблемы преобразования запросов в их непроцедурном представлении и, в частности, проблемы семантической оптимизации; проблемы выбора и оценки стоимости альтернативных планов выполнения запросов; наконец, проблемы увеличения гибкости оптимизатора по отношению к внедрению новых стратегий выполнения элементарных запросов.

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

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

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

В заключение мы выделим наиболее важные практически, на наш взгляд, направления, связанные с оптимизацией выполнения запросов в реляционных СУБД.

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