Особенности оптимизации запросов в распределенных реляционных СУБД
В самой общей постановке задачей компонента распределенной СУБД, оптимизирующего выполнение глобального запроса, является генерация множества альтернативных планов выполнения запроса и выбора из этого множества на основе некоторых критериев одного плана, на основе которого и производится выполнение запроса. Как видно, в такой общей постановке задача оптимизации глобальных запросов формулируется точно так же, как и в случае локальной СУБД. Однако, решение этой задачи для распределенных систем с локальной автономностью узлов существенно более сложное, чем для локальных СУБД.
Для определенности мы будем рассматривать подход к обработке глобальных запросов, основанный на их предварительной компиляции. Этот подход используется, например, в 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* показывают достаточную достоверность оценок оптимизатора (здесь, конечно, нужно учитывать экспериментальный характер баз данных), но отмечают недостаточное развитие используемых стратегий выполнения соединений удаленных отношений. Подходы к улучшению стратегий мы рассмотрим в следующем разделе.
| |
