В общей постановке задача оптимизации запроса в System R* формулируется так же, как и в System R: необходимо из потенциально возможных способов выполнения данного запроса выбрать такой способ, который обладает минимальной стоимостью в соответствии с выбранной мерой стоимости (т.е. либо является наиболее быстрым, либо наиболее дешевым и т.д.). Однако по сравнению с локальным вариантом системы задача оптимизации запросов в System R* становится гораздо более сложной по причине увеличения числа возможных альтернатив.
Как мы отмечали в предыдущем подразделе, в процессе компиляции запроса оптимизация выполняется на двух уровнях: в главном узле при выборе оптимального глобального плана выполнения запроса и в дополнительных узлах при выборе оптимального локального плана выполнения соответствующего подзапроса. Локальная оптимизация позапросов в дополнительных узлах - это, по сути дела, та оптимизация, которая выполняется в System R, поскольку возможный выбор касается только локальных объектов дополнительного узла - все взаимодействия с удаленными узлами предписаны в выработанном в главном узле глобальном плане выполнения распределенного запроса.
В общем случае в дополнительном узле необходимо выбрать порядок выполнения локальных соединений, способ выполнения этих соединений и метод доступа к каждому индивидуальному отношению. В оценочных функциях участвуют предполагаемые число обменов с внешней памятью и затраты процессорного времени. (Напомним, что ситуация меняется, если при обработке подзапроса в дополнительном узле обнаруживается, что в нем участвуют представления, определенные на удаленных отношениях. В этом случае в дополнительном узле требуется выработка глобального плана выполнения позапроса с применением оптимизации первого уровня).
Основной функцией оптимизации запроса первого уровня стадии выработки глобального плана выполнения запроса является выбор порядка выполнения соединения отношений, находящихся в разных узлах сети, способа выполнения соединения каждых двух таких отношений и узла, в котором должно находиться результирующее отношение. (Как и в System R, выполнение запроса, включающего n соединений отношений, всегда производится как n-1 попарное соединение). При этом в оценочных формулах появляется новый компонент - оценка сетевых накладных расходов, возникающих при выполнении запроса. Этот компонент является составным и включает число сообщений, которые предположительно будут передаваться в сети, и суммарное число байтов, которые эти сообщения будут содержать (вообще говоря, с разными весовыми коэффициентами, что позволяет учитывать особенности среды передачи).
Следуя терминологии System R* (например, [41]), будем называть внешним отношением соединения отношение, фигурирующее в левой части предиката соединения, и внутренним - отношение из правой части. (Как и в публикациях по System R, в публикациях по System R* подробно анализируются только эквисоединения). При выборе способа соединения внутреннего отношения B, находящегося в узле N, с внешним отношением A, находящемся в узле M, в оптимизаторе System R* рассматриваются следующие пять возможностей [41]:
* Кортежи внутреннего отношения B, удовлетворяющее локальному предикату ограничения, посылаются в узел M и хранятся там во временном отношении. Соединение выполняется в узле M.
* Кортежи внешнего отношения A, удовлетворяющие локальному предикату ограничения, по одному (по мере выработки) посылаются в узел N. Из внутреннего отношения выбираются кортежи, удовлетворяющие локальному предикату ограничения и предикату соединения, и соединяются с кортежем внешнего отношения, образуя очередную порцию результирующего отношения.
* Из внешнего отношения выбираются кортежи, удовлетворяющие локальному предикату ограничения. Для каждого такого кортежа в узел N посылается значение поля (полей) соединения. В этом узле из внутреннего отношения B выбираются кортежи, удовлетворяющие локальному предикату ограничения и имеющие соответствующие значения поля (полей) соединения. Эти кортежи посылаются в узел M, в котором выполняется соединение. Этот способ выполнения соединения называют соединением с использованием полусоединения.
* Все кортежи внутреннего соединения, удовлетворяющие локальному предикату ограничения, посылаются в третий узел P, где сохраняются во временном отношении. Кортежи внешнего отношения, удовлетворяющие локальному предикату ограничения, также посылаются в узел P, где и выполняется их соединение с кортежами временного отношения.
* Удовлетворяющие локальному предикату ограничения кортежи внешнего отношения посылаются в третий узел P, и для каждого из этих кортежей посылается запрос в узел N на выборку кортежей, имеющих соответствующие значения поля (полей) соединения. Эти порции кортежей передаются в узел P, где и выполняется соединение.
При выполнении соединения любым из перечисленных способов возможно достижение параллелизма и конвееризации. Чтение кортежей внутреннего и внешнего отношений может производиться параллельно. Во время выполнения соединения в узле N кортежей внутреннего отношения с переданным кортежем внешнего отношения может производиться чтение и передача следующего кортежа внешнего отношения. Однако заметим, что в System R* возможностям распараллеливания выполнения запросов уделяется меньшее внимание, чем, например, в распределенном варианте известной системы баз данных INGRES [74].
Приведенные в [41] способы выполнения соединения удаленных отношений не исчерпывают все возможные способы. В последних публикациях (например, [51]) приводятся другие возможные способы выполнения соединений, основанные на более тонких методах. Появление новых предложений в [51] естественно, поскольку работа авторов [50-51] связаны с изучением поведения системы в реальных условиях потока запросов. В рассматриваемый ими вариант System R* были внедрены средства, позволяющие количественно оценить эффекты, достигнутые в ходе оптимизации запроса, и сравнить их с возможными альтернативными вариантами. Очень ценно, что упомянутые средства доступны, фактически, на уровне пользователя; в SQL были добавлены соответствующие предложения. В [51] приведены интересные экспериментальные данные, на основе которых можно подвергать конструктивной критике употребляемые методы и предлагать их усовершенствования. Эта работа кажется очень полезной, если иметь в виду перспективы выпуска на базе System R* коммерческого продукта.
Назад | Содержание | Вперед
Виртуальные VPS серверы в РФ и ЕС
🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях
