Логическая оптимизация
Значимость оптимизатора запросов для СУБД трудно переоценить: разница во времени выполнения исходного запроса и оптимизированного запроса может различаться на порядки. В настоящее время во многих промышленных СУБД используется так называемая оценочная оптимизация (cost-based optimization), то есть выбор оптимального плана выполнения запроса из множества возможных планов производится на основе оценки стоимости выполнения операции. Оптимальным считается тот план, совокупная стоимость операций которого является наименьшей. Другой метод оптимизации основан на правилах эквивалентного преобразования запросов на основе эвристик с целью получения нового запроса, который является эффективнее первого. Такой вид оптимизации носит название оптимизации на основе правил (rule-based optimization), или перезаписи запросов (query rewriting). Именно этот подход применяется для оптимизации в BizQuery. Это связано со следующими основными причинами:
-
в виртуальной интеграционной системе отсутствует статистика, на основе которой можно было бы оценить стоимость операций (данные в источниках могут изменяться без ведома системы интеграции);
обычно пользовательский запрос адресуется к виртуальному документу (т.е. к представлению), после выполнения подстановки тела представления содержит много лишней информации и, таким образом, поддается существенному упрощению.
Особенно важен последний пункт, так как в зависимости от сложности виртуального документа размер запроса может отличаться на порядки.
Перечислим список целей, достигаемых посредством перезаписи запросов в системе BizQuery:
-
сокращение объема запроса после подстановки тела представления;
"выталкивание" (push down) предикатов (как можно более раннее применение предикатов) и устранение избыточных вычислений (например, конструирования элементов до обработки путевых выражений);
повышение уровня декларативности запроса (например, путем нахождения конструкций, эквивалентных соединениям);
частичная перезапись запроса, содержащего вызовы рекурсивных функций, в запрос без рекурсии (с использованием схемы данных) с последующей оптимизацией;
преобразование запроса в более "целенаправленную" форму на основе информации из схемы с возможным устранением избыточных просмотров данных (например, замена метасимвола в путевом выражении именем некоторого XML-элемента).
Необходимо заметить, что поскольку в XQuery отсутствует явное понятие соединения, потребовалось ввести такую логическую (и физическую) операцию, что привело к созданию расширенной модели данных XQuery. Обычно соединение выражается через FLWR-выражение (что навязывает конкретный алгоритм выполнения - соединение путем использования вложенных циклов), и поэтому выделение соединения в виде отдельной операции повышает декларативность запроса, так как становится возможным использовать другие, зачастую более эффективные алгоритмы. Тем не менее, наличие упорядоченности в XQuery понижает уровень значимости этой декларативности (например, из-за того, что нельзя произвольным образом изменять порядок выполнения соединений).
Этап логической оптимизации на основе перепизаписи крайне важен еще и по следующей причине. Результатом переписывания запроса является запрос вполне определенного ("нормализованного") вида. Условно, дерево запроса можно поделить на три части: в листьях дерева расположены операции выборки данных с накладываемыми на данные условиями; в центре дерева находятся операции соединения; верхняя часть запроса состоит преимущественно из трансформаций данных (рис. 2a). Подобная нормализация запроса играет важнейшую роль на этапе декомпозиции запросов, который будет рассматриваться ниже.
Рис. 2. Схема XQuery-запроса: (a) - после нормализации; (b) - после декомпозиции запроса
Подробнее правила перезаписи XQuery-запросов обсуждаются в [15].