В этой статье мы рассмотрим ряд вопросов, связанных с оптимизацией
выполнения запросов в реляционных системах управления базами данных (СУБД). Мы
рассматриваем проблемы оптимизации именно в контексте реляционных систем, хотя
многие аспекты, связанные с оптимизацией организации данных на внешней памяти,
распространяются и на не реляционные системы. Тем не менее
мы ограничиваемся реляционными системами по двум основным причинам. Во-первых,
реляционные системы (и вообще системы, ориентированные на ненавигационный
непроцедурный интерфейс) с одной стороны в большей степени нуждаются в
оптимизации, а с другой стороны предоставляют большие возможности оптимизации.
Поэтому оптимизационные приемы в реляционных СУБД наиболее развиты. Во-вторых
(и это связано с первой причиной), оптимизации в реляционных СУБД посвящено
громадное количество публикаций, что позволяет произвести достаточно полный
анализ проблем и решений в этой области. Заметим, что приводимая в этой статье
библиография, хотя и объемна, далеко не полна. Мы не стремились к составлению
исчерпывающей библиографии, ограничиваясь наиболее известными и содержательными
источниками. Обычно, говоря про оптимизацию в реляционных СУБД, имеют в виду
аспект оптимизации запросов, т.е. такой способ выполнения запросов, когда по
начальному представлению запроса путем его синтаксических и семантических
преобразований вырабатывается процедурный план выполнения запроса, наиболее
оптимальный при существующих в базе данных управляющих структурах.
Соответствующие преобразования начального представления запроса выполняются
специальным компонентом СУБД - оптимизатором, и оптимальность
производимого им плана запроса носит достаточно условный характер: план
оптимален в соответствии с критериями, заложенными в оптимизатор; при этом,
конечно, возможны отклонения от реальной оптимальности.
В связи с оптимизацией запросов существует достаточное количество проблем:
проблемы преобразований запроса к более эффективному непроцедурному
представлению (логическая оптимизация), проблемы выбора набора альтернативных
процедурных планов выполнения запроса, проблемы оценок стоимости выполнения
запроса по выбранному плану и т.д. Для каждого класса проблем существует более
одного подхода к их решению. Например, проблемы, связанные с логической
оптимизацией запросов, породили направление, называемое семантической
оптимизацией [123-128].Очень многие исследователи заняты проблемами оценок
стоимости процедурных планов выполнения запросов [74-90] (и до сих пор вопрос о
достоверности оценок до конца не ясен).
Можно рассматривать оптимизацию и в более широком смысле. Оптимизатор
запросов выбирает наиболее оптимальный способ выполнения запроса на основе
известных в оптимизаторе стратегий выполнения элементарных составляющих запроса
и способов композиции более сложных стратегий на основе элементарных. Тем
самым, пространство поиска оптимального плана выполнения запроса ограничено
заранее фиксированными элементарными стратегиями. Поэтому существенным
направлением исследований, непосредственно примыкающим к вопросам оптимизации,
является поиск новых, более эффективных элементарных стратегий [28-49]. В
контексте реляционных СУБД это более всего относится к разработке эффективных
алгоритмов выполнения реляционной операции соединения наиболее накладной
реляционной операции. При этом исследуются и возможности выбора более
адекватных для эффективного выполнения этой операции управляющих структур базы
данных, и возможности повышения эффективности за счет распараллеливания
выполнения операции на специализированной аппаратуре (здесь направления
исследований примыкают к тематике машин баз данных).
Особенно много работ в последние годы посвящается оптимизации запросов и
выбору эффективных способов выполнения реляционных операций в распределенных
реляционных системах управления базами данных [91-103] (в нашей библиографии
присутствует лишь небольшая часть работ, посвященных этой тематике). Здесь,
конечно, существует очень много вариантов и физической организации
распределенных баз данных (с поддержкой копий отношений в нескольких узлах
сети, с горизонтальным или вертикальным разделением отношений в нескольких
узлах, с поддержкой мгновенных снимков базы данных и т.д.), и алгоритмов
выполнения реляционных операций при каждой такой организации. Несмотря на то,
что реально существуют и функционируют несколько распределенных реляционных
СУБД (например, System R* и распределенная INGRES),
нельзя считать, что уже найдены адекватные решения этих проблем.
Наконец, сравнительно новой, еще недостаточно исследованной, но безусловно очень важной темой является глобальная
оптимизация запросов в системах баз данных [111-122]. Под глобальной
оптимизацией понимается совместная оптимизация заранее известного набора
запросов. Это наиболее актуально в системах логического программирования (и
подобных системах, связанных с обработкой правил), реализуемых на основе
реляционных баз данных. При таком подходе выполнение логической программы в конечном счете сводится к выполнению большого
количества запросов к базе данных, причем, как правило, запросы содержат
соединения. Совместная оптимизация этих запросов может резко уменьшить общее
время выполнения. Грубо говоря, глобальная оптимизация систем запросов сводится
к выявлению общих подвыражений в этих запросах и затем однократному вычислению
подвыражений с сохранением результатов во временных отношениях. Имеются
предложения и по созданию временных управляющих структур базы данных для
оптимизации выполнения системы запросов.
Из приведенного (не детализированного) описания направлений исследований и
разработок в области оптимизации выполнения запросов в реляционных СУБД следует
практическая необъятность этой тематики. Поэтому в этой статье мы не стремимся
привести подробное описание каждого направления с характеристиками всех
наиболее важных и интересных решений. Мы ограничимся тем, что более точно
сформулируем проблемы и приведем примеры решений на основе имеющихся
источников. При этом выбор источника, конечно, полностью субъективен; с ним
можно и не соглашаться. Мы проанализируем те работы, которые, на наш взгляд,
наиболее важны при организации реляционных систем, ориентированных на
использование языка SQL (это оправдывается все расширяющейся областью
распространения этого языка), а также затронем ряд других работ, являющихся
(опять же, на наш взгляд) наиболее интересными и перспективными.
Заметим, что оптимизации запросов в реляционных СУБД посвящены несколько
обзорных работ. На русском языке в настоящее время доступны книги Дейта [16],
Ульмана [17] и Мейера [18], в которых проблемам оптимизации посвящены отдельные
главы. При этом материал в [17-18] излагается на более формальном уровне и
касается меньшего количества проблем. Более современные
работы рассматриваются в последнем издании книги Дейта [19]. Наконец, наиболее
полный, на наш взгляд, обзор подходов и методов оптимизации запросов содержится
в статье [20]. Тем не менее, мы считаем полезным написание еще одной обзорной
статьи, поскольку в последнее время появился ряд новых и интересных работ,
связанных с тематикой оптимизации в реляционных СУБД. Кроме того, как мы уже
отмечали, в этой статье рассматривается более широкий класс проблем.
Статья имеет следующую структуру. В первом (самом большом) разделе мы
рассмотрим проблемы и решения в области локальной оптимизации запросов в
реляционных СУБД (далее мы будем называть эту область просто оптимизацией
запросов). Здесь мы коснемся следующих проблем: проблемы преобразования
запросов в их непроцедурном представлении и, в частности, проблемы
семантической оптимизации; проблемы выбора и оценки стоимости альтернативных
планов выполнения запросов; наконец, проблемы увеличения гибкости оптимизатора
по отношению к внедрению новых стратегий выполнения элементарных запросов.
Во втором разделе мы приведем обзор работ, связанных с выработкой более
эффективных алгоритмов выполнения реляционных операций. Главным образом нас
будут занимать эффективные алгоритмы выполнения соединений, но, кроме того, мы
рассмотрим и работы, связанные с оптимизацией алгоритмов вычисления агрегатных
функций. Коротко будут рассмотрены предложения по аппаратному распараллеливанию
реляционных операций.
В третьем разделе мы остановимся на специфике оптимизации в распределенных
реляционных СУБД. В каком-то смысле третий раздел является объединением первых
двух, но применительно к распределенным системам. При этом,
чтобы избежать повторений, мы сконцентрируемся именно на специфических чертах
реляционных распределенных СУБД.
Наконец, в завершающем, четвертом разделе (самом коротком) мы рассмотрим
предпосылки и имеющиеся подходы к глобальной оптимизации систем запросов,
затронув при этом специфические черты логической оптимизации в системах баз
данных, допускающих рекурсивные определения отношений (дедуктивных базах
данных).
В заключение мы выделим наиболее важные практически, на наш взгляд,
направления, связанные с оптимизацией выполнения запросов в реляционных СУБД.
Прежде, чем перейти к рассмотрению конкретных проблем и решений в области
оптимизации запросов, рассмотрим типичный для современных реляционных СУБД путь
обработки запроса, поступившего в СУБД на языке запросов, например, SQL или
QUEL.
Следуя, например, [104], можно представить, что обработка запроса,
поступившего в систему представленным на некотором языке запросов, состоит из
этапов или фаз, представленных на Рис.1.
На первой фазе запрос, представленный на языке запросов, подвергается
лексическому и синтаксическому анализу. При этом вырабатывается его внутреннее
представление, отражающее структуру запроса и содержащее информацию, которая
характеризует объекты базы данных, упомянутые в запросе (отношения, поля и
константы). Информация о хранимых в базе данных объектах выбирается из
каталогов базы данных. Внутреннее представление запроса используется и преобразуется
на следующих стадиях обработки запроса. В этой работе нас не будут занимать
вопросы синтаксического анализа запроса, поскольку они не связаны с
оптимизацией. Заметим лишь, что существенным является выбор внутреннего
представления, которое должно быть достаточно удобным для последующих
оптимизационных преобразований.
На второй фазе запрос в своем внутреннем представлении подвергается
логической оптимизации. При этом могут применяться различные преобразования,
"улучшающие" начальное представление запроса. Среди этих
преобразований могут быть эквивалентные преобразования, после проведения
которых получается внутренне представление, семантически эквивалентное
начальному (например, приведение запроса к некоторой канонической форме),
Преобразования могут быть и семантическими , когда
получаемое представление не является семантически эквивалентным начальному, но
гарантируется, что результат выполнения преобразованного запроса совпадает с
результатом запроса в начальной форме при соблюдении ограничений целостности,
существующих в базе данных. В любом случае после выполнения второй фазы
обработки запроса его внутреннее представление остается непроцедурным, хотя и
является в некотором смысле более эффективным, чем начальное.
Третий этап обработки запроса состоит в выборе на основе
информации, которой располагает оптимизатор, набора альтернативных процедурных
планов выполнения данного запроса в соответствии с его внутреннем
представлением, полученным на второй фазе. Кроме того, для каждого плана
оценивается предполагаемая стоимость выполнения запроса по этому плану. При
оценках используется статистическая информация о состоянии базы данных,
доступная оптимизатору. Из полученных альтернативных планов выбирается наиболее
дешевый, и именно его внутреннее представление теперь соответствует
обрабатываемому запросу.
На четвертом этапе по внутреннему представлению наиболее оптимального плана
выполнения запроса формируется выполняемое представление плана. Выполняемое
представление плана может быть программой в машинных кодах, если, как в случае System R, система ориентирована на компиляцию запросов в
машинные коды, или быть машинно-независимым, но более удобным для
интерпретации, если, как в случае INGRES, система ориентирована на
интерпретацию запросов. В нашем случае это непринципиально, поскольку четвертая
фаза обработки запроса уже не связана с оптимизацией.
Наконец, на последнем, пятом этапе обработки запроса происходит его реальное
выполнение в соответствии с выполняемым планом запроса. Это либо выполнение
соответствующей подпрограммы, либо вызов интерпретатора с передачей ему для
интерпретации выполняемого плана.
Заметим, что для нашего рассмотрения несущественно разделение процесса
обработки запроса на подготовительную (включающую фазы 1-4) и исполнительную
(фазу 5) части. В нашу схему укладывается и реальное
отделение по времени первых четырех фаз от пятой (подход с предварительной
компиляцией запроса до реального выполнения), и последовательное выполнение
всех пяти фаз при каждом выполнении запроса. Для строгости заметим, что
некоторые методы оптимизации (и даже подходы к оптимизации) довольно сильно
зависят от общей организации обработки запроса. При отрыве во времени процесса
компиляции от реального выполнения запроса оптимизатор располагает меньшей и
менее достоверной информацией, чем в том случае, когда этап компиляции тесно
привязан к этапу выполнения (выполняется в рамках транзакции пользователя).
Далее в этом разделе нас главным образом будут занимать особенности
выполнения фаз 2 и 3.
В Разделе 2 мы рассматривали вопросы, связанные с оптимизацией запросов в
реляционных СУБД. Как мы подчеркивали в начале этого раздела,
оптимизация запросов состоит в выборе оптимального (или близкого к
оптимальному) способа выполнения запроса на основе особенностей физической структуры
базы данных и поддерживаемых в ней управляющих структур; заложенных в систему
знаний о допустимых стратегиях выполнения элементарных составляющих запроса;
наконец, на основе той или иной статистической информации, позволяющей оценить
эффективность выбранного плана выполнения запроса.
Для оптимизатора запроса все эти данные являются внешними, т.е. оптимизация
ограничена внешними факторами. В предыдущем разделе мы касались проблем повышения достоверности оценок планов выполнения запроса за
счет более правильного учета статистической информации. Конечно, если оценки
более соответствуют реальности, то вероятность выбора для выполнения запроса
неоптимального плана уменьшается. Но тем не менее
возможности оптимизатора ограничены первыми двумя факторами.
Поэтому, на наш взгляд, работы, связанные с выработкой более эффективных
структур хранения баз данных, новых управляющих структур и новых алгоритмов
выполнения реляционных операций, имеют непосредственную связь с оптимизацией
запросов. В этом разделе мы рассмотрим некоторые из них. При этом в основном мы
будем рассматривать предложения, позволяющие улучшить работу традиционно
организованных реляционных систем управления базами данных, не затрагивая
специфику систем, функционирующих при поддержке специализированной аппаратуры
(машин баз данных).
Следует отметить, что работы, относящиеся к теме данного раздела, достаточно
трудно классифицировать. Конечно, все их объединяет общая идея - повышение
эффективности реляционных систем, но предлагаемые подходы очень разнообразны.
Поэтому материал раздела разбивается на подразделы не в соответствии со
спецификой методов, а исходя из их предназначений. Мы остановимся на
предложениях, направленных на более эффективное выполнение операций соединения,
вычисление агрегатных функций, а также повышение эффективности выполнения
выделенных наборов запросов.
При традиционной организации структур хранения и управляющих структур
реляционной базы данных и использовании в качестве
подсистемы базового доступа к хранимым данным типа RSS System
R наиболее эффективно выполняются операции, соответствующие ограничению и
проекции одного хранимого отношения. Двуместные операции - объединения,
пересечения, соединения отношений специально не поддерживаются структурами
данных и операциями нижнего уровня. Особенно болезненно ощущается отсутствие
поддержки одного часто употребимого случая соединения
- эквисоединения. Это действительно распространенная операция в реляционных
системах, причем ее употребление в запросах тем чаще, чем более правильно с
точки зрения теории реляционных баз данных спроектирована конкретная база
данных. Поэтому естественно стремление исследователей и разработчиков
реляционных СУБД к повышению эффективности выполнения этой операции.
Предлагаемые решения отличаются разной степенью радикальности - от повышения
уровня интерфейса подсистемы доступа к данным нижнего уровня до полного
пересмотра физической организации данных на внешней памяти.
Для начала коротко напомним основные алгоритмы выполнения операций
эквисоединения в System R. В этой системе
употребляются три алгоритма. Первый алгоритм основан на множественных
сканированиях двух соединяемых отношений. Для каждого кортежа первого отношения
производится полное сканирование второго отношения с выделением соединяемых
кортежей и произведением очередной порции результата. Этот алгоритм не требует
наличия какого-либо порядка при сканировании кортежей, следовательно,
сканирование может производиться любым допустимым образом.
Второй алгоритм предполагает предварительную сортировку обоих отношений в
соответствии со значениями полей соединения. После этого соединение выполняется
с использованием процедуры, напоминающей процедуру слияния, применяемую в
алгоритмах внешней сортировки файлов. Если отношение кластеризовано
по полям соединения, и, следовательно, для него определен индекс на этих полях,
то исходная сортировка этого отношения не требуется; в цикле слияния
используется сканирование отношения по этому кластеризованному
индексу.
Базовый подход System R, допускающий размещение в
одном блоке внешней памяти кортежей нескольких отношений, позволяет еще более
оптимизировать этот алгоритм для выделенной операции эквисоединения двух или
более отношений. Эти отношения можно совместно кластеризовать
в соответствии со значениями полей соединения и завести "мультииндекс", позволяющий определить список TID'ов соединяемых кортежей. Эта идея развита и реализована
в системе XSQL, ориентированной на использование в приложениях САПР и
являющейся развитием System R. Более подробно это
описывается в [129].
Наконец, третий алгоритм основывается на использовании некластеризованных
индексов обоих отношений на полях соединения. Путем сканирования только
индексов производится список пар (TID1, TID2) таких, что TID1 и TID2
определяют, соответственно, соединяемые кортежи первого и второго отношений.
Далее этот список сортируется (по TID1, а в пределах группы пар с совпадающим TID1 - по TID2). Доступ к кортежам отношений и
реальное выполнение соединения производится с использованием отсортированного
списка пар.
Легко видеть, что единственным гарантированно эффективным является второй
алгоритм, если соединяемые отношения кластеризованы
по полям соединения. Этот алгоритм более всего употребим и в том случае, когда
требуется исходная сортировка, а мощность соединяемых отношений достаточно
велика. (Для небольших отношений хорошо работает и первый алгоритм за счет
буферизации подотношений в оперативной памяти.)
Применимость третьего алгоритма ограничена недостаточно высоким уровнем
интерфейса RSS. Действительно, пусть перед выполнением соединения отношений
необходимо выполнить их ограничение. Предположим, что соединяются отношения R и
S, причем для отношения R имеются индексы I1 и I2 такие, что I1 соответствует
предикату ограничения, а I2 - предикату соединения, и аналогично обстоит дело с
отношением S (индекс ограничения I3, индекс соединения - I4). Тогда было бы
естественно развить алгоритм следующим образом. Как и раньше, производится
список пар TID'ов соединяемых кортежей с использованием
индексов I2 и I4. Кроме того, на основе индексов I1 и I3 и условий, задаваемых
предикатами ограничений, формируются два списка TID'ов
L1 и L2 кортежей первого и второго отношений, удовлетворяющих предикатам
ограничения. Далее производится своего рода пересечение этих трех списков таким
образом, что пара (TID1, TID2) оставляется в результирующем списке пар в том и
только том случае, когда TID1 присутствует в списке L1, а TID2 - в списке L2.
Такой вариант алгоритма описан в [2], но он не использовался в System R, поскольку RSS не обеспечивает операций
пересечения отсортированных временных объектов, а накладные расходы, которые
потребуются для выполнения подобных операций выше уровня RSS, очень трудно
оценить. В литературе имеются предложения по повышению в этом направлении
уровня подсистемы управления доступа к хранимым данным. Например, в [45]
предлагается расширить возможности такой подсистемы, включив в число ее функций
выполнение теоретико-множественных операций над отсортированными списками TID'ов. В ряде случаев это позволяет произвести все
выполнение запроса в терминах идентификаторов кортежей и произвести реальное
обращение к кортежам отношения только на завершающей стадии выдачи результата.
При этом, поскольку результирующий список TID'ов отсортирован,
число обращений к блокам внешней памяти, хранящим кортежи, будет оптимально.
Другой путь примерно в том же направлении, но с введением управляющих
структур нового типа, предлагается в [38]. Новый тип управляющей структуры -
индекс соединения. В общем виде, если f (R.C1, S.C2)
- предикат соединения отношений R и S по полям C1 и C2, то индекс соединения R
и S по f определяется как бинарное отношение JI = { (TIDi, TIDj)
| f (кортеж (TIDi).C1,
кортеж(TIDj).C2) = true }. (Поля C1 и C2 могут быть составными, а f - не обязательно предикат эквисоединения.) Индексы
соединения предлагается хранить в виде двух B-деревьев, в одном из которых
порядок поддерживается по TIDi, а в другом - по TIDj. Это требуется для того, чтобы можно было эффективно
учитывать предикаты ограничения отношений, для которых существуют обычные
индексы. В [38] описаны основные алгоритмы поддержания индексов соединения при
выполнении операций вставки и удаления кортежей, а также использования этих
индексов при выполнении операций полусоединения,
соединения и запросов общего вида. Из этого описания следует, что некоторые
запросы удается выполнять достаточно эффективно, причем эффективность
возрастает при увеличении объема доступной оперативной памяти. Но совершенно
очевидно, что как и в случае с обычными индексами,
определение слишком большого числа индексов соединения приведет в деградации
системы за счет черезчур больших накладных расходов,
требуемых при выполнении операций занесения и удаления кортежей.
В [48] предлагается иной вид управляющей структуры, позволяющей эффективно
реализовывать операции соединения отношений, - частичные отношения. Идея
состоит в том, что на стадии проектирования базы данных для каждого отношения
принимается решение о наборе полей, на которых могут задаваться предикаты
ограничения и соединения. Отношения хранятся как обычно в виде наборов
кортежей, содержащих все поля, но, кроме того каждому
отношению соответствует частичное отношение, кортежи которого содержат только
те поля базового отношения, на которых могут задаваться предикаты, и одно
дополнительное поле, хранящее TID соответствующего кортежа базового отношения.
Кроме того, для длинных текстовых полей базового отношения можно определить
функцию сжатия, приводящую такие значения к значениям соответствующих полей
частичного отношения (например, действие функции сжатия может состоять в том,
что из текстовой строки берутся несколько первых символов).
При таком подходе операции ограничения и соединения выполняются над
частичными отношениями, а при формировании окончательного результата по
имеющимся ссылкам выбираются значения других полей. Отмечается, что в ряде
случаев, определяемых степенью селективности предикатов ограничения, алгоритмы
соединения на основе частичных отношений оказываются эффективнее традиционных.
Много внимания в современной литературе уделяется способам физической
организации баз данных на внешней памяти на основе идей многоключевого
хэширования и соответствующим алгоритмам выполнения
реляционных операций. Этот подход хорошо иллюстрирует работа [36]. Каждому полю
каждого отношения базы данных соответствует, вообще говоря, своя хэш-функция.
При занесении кортежа в отношение номер блока внешней памяти, в который будет
помещен этот кортеж, вычисляется как конкатенация вырезок значений хэш-функций,
примененных к значениям полей кортежа. В полученной после конкатенации битовой
строке допускается перестановка битов, причем правила перестановки, как и набор
используемых хэш-функций, являются характеристикой выбранного алгоритма многоключевого хэширования.
Понятно, что при неполном указании значений полей искомого кортежа после
применения алгоритма хэширования будет получен список
страниц, в которых может находиться искомый кортеж.
Алгоритм (экви)соединения,
основанный на такой организации хранимых отношений, разбивает соединение на
последовательность подсоединений. При этом гарантируется, что ни один блок,
содержащий кортежи соединяемых отношений, не будет использован в двух
подсоединениях. Основная проблема - выбрать такое разбиение соединений на
подсоединения, которое минимизирует требуемое число буферов оперативной памяти.
В предлагаемом в [36] алгоритме предполагается, что число буферов оперативной
памяти достаточно для выполнения каждого подсоединения. Это предположение
достаточно естественно, поскольку параметры алгоритма многоключевого
хэширования могут варьироваться. Снятие предположения
усложняет алгоритм соединения и делает его эффективность сомнительной.
В этой работе не рассматриваются проблемы возможных переполнений страниц при
расширении отношений. Однако, предложенная техника
легко расширяется с использованием идей динамического многоключевого
хэширования. Этому предмету в последнее время
посвящается очень много работ. Основные концепции подхода изложены, например, в
[37].
Интересным примером практически реализованной СУБД, основанной на некоторой
вариации метода многоключевого хэширования,
является французская система Sabre [34]. Наиболее
интересная особенность этой системы - использование предикатных деревьев для мультиатрибутной кластеризации отношений (разновидность многоключевого хэширования).
Предикатное дерево задается администратором базы данных при создании отношения
и содержит простые предикаты над полями отношения. При занесении кортежа
вычисление предикатов, входящих в дерево, позволяет получить номер блока
внешней памяти, в которые следует поместить кортеж. При поиске кортежа на
основании заданных значений полей находится множество страниц, в которых может
располагаться данный кортеж. При такой организации хранимых отношений
естественный способ выполнения соединения отношений основывается на хэшировании.
Система Sabre интересна еще и тем, что в ней это
единственный применяемый алгоритм соединения. Как отмечается в [34], в ранних
версиях системы поддерживалось несколько стратегий выполнения соединений.
Подобно System R, при обработке запроса с соединиями генерировалось множество альтернативных планов
его выполнения, которые затем оценивались на основе статистической информации о
базе данных. Однако в ходе эксплуатации ранних версий Sabre
было установлено, что, как правило, используется одна стратегия выполнения
соединения, естественно соответствующая физической организации отношений.
Поэтому была оставлена только эта стратегия, что позволило упростить
оптимизатор и ускорить процедуру выработки плана выполнения запроса, не теряя
эффективность выполнения.
Хотя мы не рассматриваем в этой статье специфику реляционных систем,
использующих специализированную аппаратную поддержку, необходимо отметить, что
физическая организация реляционных баз данных на основе мультиатрибутного
хэширования позволяет легко распараллеливать
выполнение операций соединения. Поэтому такая организация хорошо соответствует
специфике мультипроцессорных машин баз данных, которые могут реально
распараллеливать выполнение запроса.
Конкретные предложения по распределению одного отношения между несколькими
независимыми дисковыми устройствами приводятся, например, в [35]. В этой работе
развивается идея декластеризации отношения, когда отношение разбивается на две или
более части, средние характеристики которых примерно одинаковы. Эти части
отношения хранятся на разных устройствах внешней памяти, что позволяет,
например, производить параллельное сканирование отношения. Понятно, что
критерии декластеризации могут быть различны, и, в частности, могут
способствовать распараллеливанию соединений.
Множество вариаций алгоритмов соединения существует для распределенных
реляционных СУБД. Они очень специфичны, хотя некоторые работы близки тематике
машин баз данных. Проблемы оптимизации в распределенных системах
рассматриваются в следующем разделе.
С развитием аппаратуры и программного обеспечения сетей ЭВМ (локальных и
территориальных) проблема интеграции разобщенных баз данных становится все
более актуальной. Существует много подходов к решению этой проблемы, начиная от
обеспечения удаленного сетевого доступа к локальным базам данных и кончая
построением сложных распределенных систем управления базами данных,
обеспечивающими для пользователя прозрачность местоположения интересующих его данных.
В последнем случае пользователи взаимодействуют с глобальной распределенной
базой данных на основе ее глобальной схемы.
В этой работе мы не сможем привести полный анализ проблем оптимизации
запросов и структур данных и стратегий выполнения реляционных операций во всем
спектре распределенных систем баз данных. В этом мы ограничены и объемом данной
статьи, и сложностью задачи. Тем не менее, основные особенности оптимизации в
некотором широком классе распределенных систем баз данных мы постараемся рассмотреть.
К этому классу мы отнесем распределенные системы управления базами данных,
основанные на однородных локальных системах управления базами данных. Такой
системой является, например, распределенная СУБД System
R* [93].
Дополнительным требованием в System R*, довольно
естественным, как нам кажется, для систем этого класса, является требование
локальной автономности узлов сети, на которых выполняются локальные
представители СУБД (незначительно модифицированная System
R). Это требование означает отсутствие централизованного администрирования
глобальной базой данных, отсутствие централизованного каталога базы данных и
т.д. Должно допускаться локальное порождение и удаление новых отношений и
индексов в локальной базе данных, причем уничтожение индекса не должно
приводить к невозможности повторного выполнения ранее откомпилированных
глобальных запросов. Требование локальной автономности существенно влияет и на
допустимые способы оптимизации глобальных запросов (здесь и далее под
глобальным запросом мы понимаем запрос, для выполнения которого требуется
сетевой доступ к удаленным локальным базам данных).
Заметим, что логические уровни оптимизации запросов, включая семантическую
оптимизацию, фактически, не связаны с распределенной или локальной природой баз
данных (не считая некоторой специфики обработки запросов через представления).
Распределенный характер баз данных затрагивает главным образом
"физические" уровни оптимизации, связанные с выбором и оценкой планов
выполнения запроса.
Другая проблема распределенных систем баз данных касается алгоритмов
выполнения двуместных реляционных операций над отношениями, хранящимися в
разных узлах распределенной системы. Эта проблема существует и при традиционном
хранении каждого отношения целиком в одной локальной базе данных, но становится
еще более сложной и допускающей большее число решений в случае так называемых
разделенных (partitioned) и раскопированных
(replicated) баз данных. Такие нетрадиционные
организации распределенных баз данных очень активно обсуждаются в литературе,
хотя нам неизвестна какая-либо завершенная система, построенная на этих
принципах. (В свое время в начальном проекте System
R* предполагалось использование таких организаций, но ни одна из них не была
практически реализована).
В самой общей постановке задачей компонента распределенной СУБД,
оптимизирующего выполнение глобального запроса, является генерация множества
альтернативных планов выполнения запроса и выбора из этого множества на основе
некоторых критериев одного плана, на основе которого и производится выполнение
запроса. Как видно, в такой общей постановке задача оптимизации глобальных
запросов формулируется точно так же, как и в случае локальной СУБД. Однако,
решение этой задачи для распределенных систем с локальной автономностью узлов
существенно более сложное, чем для локальных СУБД.
Для определенности мы будем рассматривать подход к обработке глобальных
запросов, основанный на их предварительной компиляции. Этот подход
используется, например, в System R* [93] и состоит в
том, что фазы порождения выполняемого плана глобального запроса и его реального
выполнения разнесены во времени. Это является естественным развитием подхода System R и позволяет, например, заранее откомпилировать
программу с включением глобальных запросов на языке SQL, а затем много раз
выполнять ее без необходимости каждый раз вырабатывать планы выполнения
запросов.
В результате компиляции запроса в System R*,
инициированной в некотором узле сети, на самом деле порождается распределенная
программа выполнения этого запроса, причем она и хранится в распределенной
форме. В каждом узле сети, локальная база данных которого содержит отношения,
затрагиваемые запросом, хранится часть распределенной программы, под
управлением которой производятся доступ к локальным данным этого узла и
взаимодействия с другими узлами, содержащими части той же распределенной
программы. Выполнение запроса начинается с запуска "главной" части
распределенной программы, хранящейся в том узле, в котором инициировалась
компиляция запроса ("главном" узле). Эта программа путем сетевого
взаимодействия вызывает другие части распределенной программы, хранящиеся в
"дополинительных" узлах и т.д. Результат
выполнения запроса формируется в главном узле, хотя промежуточные результаты
могут быть распределены между другими локальными базами данных.
В System R* распределенная программа - это
программа в машинных кодах IBM/370, но в данном случае, в контексте оптимизации
запросов, для нас это не важно: программа могла бы порождаться и на некотором
промежуточном языке и интерпретироваться при своем выполнении. Такой подход
также практически применяется. Примером системы может быть распределенный
вариант СУБД INGRES [91]. Задача оптимизации запросов остается той же -
необходимо построить оптимальный план выполнения запроса в условиях локальной
автономности узлов сети.
Рассмотрим более подробно, как решается эта задача в System
R*. Основой обработки запроса является поддержание распределенного каталога
глобальной базы данных. Подробно это описано в [129]. Здесь же заметим лишь то,
что за счет наличия правил именования объектов глобальной базы данных и
специальных протоколов доступа к локальным каталогам баз данных при обработке
запроса можно получить достоверную информацию о всех
затрагиваемых запросом объектах базы данных. В принципе после
этого можно было бы генерировать полные распределенные планы выполнения запроса
и выбирать из них оптимальный в том узле, в котором начата обработка запроса.
Но это противоречило бы принципу локальной автономности узлов сети.
Действительно, предположим, что в построенном детальном плане выполнения
запроса предполагается сканирование некоторого удаленного отношения R с
использованием индекса I. Естественно, что во время выполнения это сканирование
должно производиться в локальной СУБД, база данных которой содержит отношение
R. В соответствии с требованием локальной автономности локальный администратор
этой базы данных может уничтожить индекс I, и тогда для того, чтобы привести
выполняемый план в корректное состояние, потребуется взаимодействие с главным
узлом, что противоречит требованиям локальной автономности.
В System R* применяется следующее достаточно
естественное решение: При обработке запроса в главном узле генерируются не
детальные, а так называемые глобальные планы выполнения запросов. Каждый
глобальный план соответствует отдельной схеме межузловых
взаимодействий при выполнении запроса. В нем определяются узлы, в которых
должны выполняться соединения удаленных отношений, и определяются методы и
порядок передачи кортежей между узлами. Вместе с тем, глобальный план
выполнения запроса не предписывает правил выполнения локальных реляционных операций
в узлах, включаемых в выполнение запроса.
Конечно, как и в случае построения детального плана выполнения запроса,
порождается множество альтернативных планов, которые необходимо оценивать. Для
оценок используется информация распределенного каталога. По существу,
необходимо оценить мощности промежуточных отношений, порождаемых в удаленных
узлах при выполнении локальных частей запроса. В отличие от случая локальной
СУБД, оценочные формулы глобальных планов в основном базируются на оценках
сетевых накладных расходов.
После порождения множества альтернативных глобальных планов запроса,
вычисления оценок их стоимости и выбора наиболее дешевого завершается первая
фаза оптимизации глобального запроса и начинается следующая фаза - построение
детального распределенного плана.
Для этого прежде всего производится декомпозиция
исходного запроса в соответствии с выбранным глобальным планом на компоненты,
каждый из которых содержит некоторый локальный подзапрос исходного запроса в
непроцедурной форме и процедурную часть, предписывающую порядок сетевых
взаимодействий. Полученные компоненты рассылаются по сети в соответствующие
локальные СУБД, в каждой из которых осуществляется генерация альтернативных локальных
планов выполнения подзапроса и выбор наиболее дешевого из них в соответствии с
локальными критериями оценок стоимости.
Эта процедура практически совпадает с той, которая выполняется при обработке
локального запроса в обычной System
R. Заметим, что поскольку порядок сетевых взаимодействий является заранее
предписанным, то это является некоторым граничным условиям выбора алтернативных локальных планов. Из этого следует, в
частности, что в оценочных формулах локальных СУБД не требуется учитывать
стоимость сетевых накладных расходов - оно одна и та же для всех возможных
локальных планов.
Вторая фаза оптимизации происходит тем самым в распределенной манере. В ней
участвуют в общем случае локальная СУБД главного узла и несколько локальных
СУБД дополнительных узлов. Если запрос производится не только
над базовыми отношениями, а и над представлениями, то раскрытие этого
представления производится в том узле, в котором оно определялось, и в общем
случае, если это представление определено над несколькими удаленными
отношениями, дополнительный узел выступает для своего подзапроса как главный,
т.е. вырабатывает глобальный план выполнения подзапроса и рассылает его
компоненты дополнительным узлам следующего уровня. Более подробно
обработка запросов над представлениями рассматривается в [129].
Заметим, что в этой существенно более сложной, чем в локальном случае, схеме
оптимизации не возникают дополнительные проблемы по части оценок стоимости
планов выполнения запросов. Основная проблема остается той же, что и при
оптимизации в локальной СУБД,- точность оценок селективности простых
предикатов. Поэтому и подходы к решению этой проблемы могут быть такими же, как
рассмотренные в Разделе 2. Конечно, если использовать для оценок селективности
методы, основанные на гистограммах, то при выборе глобального плана выполнения
запроса могут потребоваться дополнительные сетевые накладные расходы.
В System R*, как и в System
R, оценки селективность основаны на предположениях о равномерности и
независимости распределений значений полей отношений. Эти предположения не
вполне правомерны, но зато резко упрощают проблемы оценок. Как отмечается в
[95], экспериментальные результаты использования System
R* показывают достаточную достоверность оценок оптимизатора (здесь, конечно,
нужно учитывать экспериментальный характер баз данных), но отмечают недостаточное
развитие используемых стратегий выполнения соединений удаленных отношений.
Подходы к улучшению стратегий мы рассмотрим в следующем разделе.
Рассматриваемые до сих пор оптимизационные преобразования запросов,
улучшенные структуры хранения реляционных данных и стратегии выполнения
реляционных операций были направлены на повышение эффективности отдельных
запросов к базе данных. Существует другая постановка задачи оптимизации, когда
преследуется цель повышения эффективности смеси запросов. Соответствующие
оптимизационные приемы относятся к \2глобальной\1 оптимизации физических
управляющих структур баз данных и планов выполнения заданного набора запросов.
Имеется два направления глобальной оптимизации, не являющихся взаимно
исключающими. Первое направление можно назвать \2статистической глобальной
оптимизацией\1. Цель такой оптимизации - автоматическое (или
автоматизированное) поддержание в базе данных на основании статистической
информации набора управляющих структур, позволяющего эффективно выполнять
запросы из имеющегося потока запросов. Фактически, это означает улучшение
физической структуры базы данных относительно текущего потока запросов. Этот
подход не предполагает априорных знаний о специфике смеси запросов, поскольку
основывается только на статистике. Предполагается, что свойства запросов в
потоке обладают инерционностью, т.е. на основе информации об уже выполненных
запросах можно делать оценивать свойства будущих запросов. На практике это
предположение, как правило, подтверждается.
Второе направление в последнее время обычно называют \2оптимизацией набора
запросов\1. Соответствующие оптимизации расчитаны на
то, что система получает запросы не по одному, а целыми наборами. Эта ситуация
невозможна в традиционных реляционных СУБД, интерфейсы которых предполагают
поочередное выполнение запросов, но становится жизненной в более сложных
системах, использующих СУБД в качестве средства поддержки. К таким системам
относятся системы дедуктивных баз данных, системы логического программирования
и т.д. Их объединяет то свойство, что наряду с базами данных в них хранятся
наборы правил логического вывода, позволяющие порождать новые данные (факты) на
основе фактов, хранимых в базе данных. Запрос, поступающий в такую систему,
преобразуется в набор запросов традиционного интерфейса СУБД. Все запросы,
составляющие набор, могут быть предоставлены СУБД одновременно и,
соответственно, могут обрабатываться совместно.
Основным действием при оптимизации набора запросов является выработка
\2глобального\1 оптимального плана выполнения запросов этого набора. Основой
оптимизации является выявление общих подвыражений, входящих в разные запросы
одного набора.
Как мы уже отмечали, эти два подхода не являются взаимно исключающими. Можно
представить систему, в которой осуществляется оптимизация наборов запросов и
одновременно производится улучшение физической структуры базы данных на основе
статистической информации о потоке наборов запросов. С другой стороны, при
оптимизации набора запросов, вообще говоря, можно учитывать возможности
порождения временных управляющих структур (например, индексов) на время
выполнения данного набора запросов.
Оптимизаторы реляционных СУБД представляют собой наиболее сложные компоненты
систем. Эффективность системы в целом во многом определяется тем, насколько
мощной является оптимизация. Как мы старались показать, во всех существующих
направлениях, связанных с оптимизацией, наряду с определенным продвижением
остается множество нерешенных проблем. Большинство из них имеют переборный
характер и требуют развитых эвристических решений.
Большей частью в стороне остались проблемы оптимизации, возникающие при
использовании специализированной аппаратуры машин баз данных, где главное
внимание уделяется возможностям распараллеливания выполнения запросов. Спектр
возможных архитектур машин баз данных достаточно широк, и проблемы оптимизации
имеют свою специфику для каждой из конкретных архитектур. Соответствующие
вопросы освещены в литературе явно недостаточно.
Другая специфическая проблема оптимизации запросов и структур хранения и
стратегий доступа относится к системам управления базами данных в оперативной
памяти. Такие системы становятся все более актуальными в связи с постоянным
увеличением объемов доступной в ЭВМ оперативной памяти и ее удешевлением. Особенно
интересны возможности использования оперативной памяти, сохраняющей информацию
после выключения питания. Если удастся добиться удешевления и этого вида
аппаратуры, могут наступить революционные изменения в подходах к организации и
баз данных, и систем управления ими с соответствующим смещением акцентов в
области оптимизации.
Тем не менее, в ближайшие годы, скорее всего, наиболее распространены будут
по-прежнему системы управления базами данных, хранимыми в традиционно
организованной внешней памяти. Поэтому и традиционные оптимизаторы еще долго
будут сохранять свою актуальность.