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