Диссертация (1149731), страница 23
Текст из файла (страница 23)
Оптимизация и исполнение запросовАрхитектура системы исполнения запросов содержит модули, представ-парсер; оптимизатор, опирающийся на трансформации,модели стоимости и модели качества; и исполнитель.ленные на рисунке 5.3:5.3.2.1. Построение первичного планаПарсер транслирует запрос, получаемый от клиента, в первичный планего выполнения, то есть алгебраическое выражение, представленное деревом(определение 2.19 в главе 2).Первичный план выполнения запроса из парсера передается в оптимизатор, для построения более эффективного эквивалентного плана.5.3.2.2.
ОптимизацияОпишем основные процессы, которые происходят на этапе оптимизациизапроса, обращая внимания на то, как требования к системе, влияют на них.Как и в традиционных системах оптимизации реляционных запросов оптимизатор анализирует алгебраические свойства операций, например, ассоциа-123тивность и дистрибутивность. На основе этих свойствперечислитель реализуетобход пространства планов выполнения запроса, используя трансформации дляперехода от одного плана к другому (определение 2.17 в главе 2).Архитектура поддерживает расширяемость алгебры и использует оптимизатор, настраиваемый на новые специфические операции алгебры, которыепорождают новые алгебраические тождества и расширяют пространство возможных планов выполнения запросов.Оптимизатор основан на расширяемом и настраиваемом множестве трансформаций планов (алгебраический выражений), которое реализует пространство планов.
Важно отметить, что в предложенной архитектуре системы трансформации включают в себя возможные эквивалентные перестроения плановдвух типов, неразличимых с точки зрения реализации: основанные на алгебраических тождествах или на различных реализациях одной операции. Такаямодель позволяет легко встраивать в систему новые операции, алгоритмы, ихреализующие, и соответствующие трансформации.По сравнению с традиционными реляционными СУБД пространствотрансформаций в расширенной алгебре не столь однородно: например, в нейчасто используются операции не ассоциативного соединения и сложные трансформации с операцией выбора лучших объектов.Особое внимание следует обратить на реализацию трансформаций в системе с учетом ее расширяемости: пространство трансформаций не должнобыть реализовано глубоко внутри оптимизатора; поэтому в архитектуре системы определены единые интерфейсы, позволяющие легко встраивать новыетрансформации в систему.Для того, чтобы иметь возможность выбрать эффективный план выполнения запроса, оптимизатор основывается на моделях стоимости и качества,определенных для всех операций, в том числе для пользовательских расширений (подразделы 2.2.6 и 2.4.4 в главе 2).
Архитектура системы поддерживаетвключение новых моделей стоимости и качества операций и настройку уже существующих.Непосредственная оптимизация запроса, допускающего контролируемоеприближенное выполнение, может быть построена на основе разных по сложности и качеству ответа моделях.Во-первых, может быть использована модель, в которой первоначальный124план выполнения запроса, сгенерированный парсером, может быть переданнепосредственного исполнителю, минуя этап поиска более эффективного эквивалентного.
Оптимизация запроса не происходит, но этот подход может бытьэффективен в некоторых специфических ситуациях, например, если по запросупользователя парсер изначально генерирует план приближенного выполнениязапроса.Во-вторых, в системе может быть использован традиционный оптимизаторточного выполнения запроса. Оптимизатор рассматривает только планы точного выполнения запроса и выбирает наиболее эффективный для исполнения.Эта модель, как и предыдущая, в действительности не учитывает возможностьприближенного выполнения запроса, но может быть эффективной, в случаях,когда точное выполнение многих простых сценариев анализа данных требуетмалого количества вычислительных ресурсов.Третья модель основана на сочетании оптимизатора точного выполнениязапроса и модуля распределения ресурсов, описанного в главе 3.
Этот подходдетально обсуждается в параграфе 5.3.2.2.1 и позволяет непосредственно учитывать ограничения на количество вычислительных ресурсов и строить планыприближенного выполнения запроса.В пятой модели первоначальный план выполнения запроса, сгенерированный парсером, минуя этап оптимизации, передается модулю распределения ресурсов. Такой подход может быть использован в системах выполнения специфических сценариев анализа данных, для которых пространство эквивалентныхпланов тривиально, но возможно их контролируемое приближенное исполнение.Четвертая модель, описанная в параграфе 5.3.2.2.2, основана на построении оптимального составного сегмента запроса (глава 4) и позволяет выбиратьболее эффективный план приближенного выполнения запроса по сравнению спредыдущими подходами.5.3.2.2.1.
Оптимизация и распределение ресурсов Этот подход основанна разделении этапов оптимизации запроса и распределения ресурсов междуоперациями в выбранном плане. На рисунке 5.4 изображена архитектура системы, основанная на этой идее.Оптимизатор точного выполнения запроса по первичному плану строитэквивалентный ему, возможно оптимальный, и передает его в модуль распре-125Рис. 5.4. Оптимизация и распределение ресурсовделения ресурсов, для определения стратегии его приближенного выполненияна основе ограничений от пользователя. Таким образом, архитектура системы основана на приближенном решении задачи 2.7: ограниченное количестворесурсов распределяется между операциями в плане выполнения запроса, оптимального при максимальном ожидаемом качестве ответа.
Идея этого подходасостоит в том, что в архитектуре разделяются модуль распределения ресурсови оптимизатор, что позволяет использовать традиционные методы оптимизации точных запросов. Поскольку в архитектуре системы модули оптимизациизапросов, распределения ресурсов и исполнения плана разделены, для поиска оптимального плана точного выполнения запроса может быть использованлюбой эффективный алгоритм [29–31].Именно этот подход к оптимизации запросов поддерживает модельная реализация системы.
В модельной реализации системы оптимизатор основан наограниченном спуске по стоимости планов выполнения запросов. Начиная снекоторого стартового плана выполнения запроса, оптимизатор последовательно применяет трансформации, переходя от текущего плана к эквивалентномус меньшей стоимостью.В главе 4 в разделе 4.1 было показано, что такое разделение этапов оптимизации и учета ограничений на доступные вычислительные ресурсы можетпривести к построению не оптимального плана выполнения запроса. Например,приближенное выполнение операций может изменять мощность анализируемых126Q-множеств, приводя к тому, что план, выбранный на этапе точной оптимизации, будет не эффективен при ограничениях на количество вычислительныхресурсов. Другое ограничение на применимость метода состоит в том, что наэтапе точной оптимизации из рассмотрения исключаются приближенные алгоритмы, которые не допускают контроль приближенных вычислений за счетограничения вычислительных ресурсов.5.3.2.2.2.
Оптимизация через построение оптимального составногосегмента Альтернативный подход основан на интеграции модуля распределения ресурсов и оптимизатора, а именно на построении оптимального составногосегмента запроса. На рисунке 5.5 изображена архитектура системы, реализующая эту идею: на первом этапе строится оптимальный составной сегмент запроса, а затем на основе ограничений от пользователя выбирается единственныйплан, который передается на исполнение.Рис. 5.5. Оптимизация через построение оптимального составного сегментаТаким образом, оптимизатор отвечает за построение оптимального составного сегмента запроса, который передает модулю ответственному за выбор оптимального плана на основе ограничений и его подготовку к исполнению.5.3.2.3. ИсполнениеИсполнитель основан на потоковой модели исполнения запросов. Таким образом промежуточные результаты вычислений передаются между операциями127без материализации; хотя реализация некоторых операций, допускает внутреннюю материализацию.
При необходимости внешняя материализация выполняется отдельными операциями.Как уже упоминалось, непосредственное исполнение операций происходитв вычислительных модулях, а исполнитель генерирует обращения к ним и перенаправляет потоки обрабатываемых данных между различными вычислителями на основе полученного плана выполнения запроса.5.4. Расширение системыОсновные требования к системе заключаются в поддержке ее расширяемости и прозрачной работы с приближенным выполнением запросов и должныбыть учтены в ее архитектуре.Множество операций в системе может быть расширено за счет реализацииновых:∙ функций, параметризующих родовые алгоритмы операций, например,функций предиката;∙ родовых алгоритмов базовых операций, например, приближенных;∙ операций, например, ранжирующего соединения.Новые точные и приближенные операции и алгоритмы, их реализующие,могут быть легко встроены в систему вместе с новыми алгебраическими тождествами и моделями стоимости и качества.5.4.1.
ТрансформацииВажной чертой рассматриваемой архитектуры является необходимостьподдержки расширяемого множества настраиваемых трансформаций, по сравнению с ограниченным набором трансформаций, реализованных в традиционных оптимизаторах.Трансформации (интерфейс 3) реализуют методы check, который оценивает применимость трансформации к корню (под)плана выполнения запроса, и128Интерфейс 3 Интерфейс трансформацииi n t e r f a c e Transformation {b o o l e a n check ( Plan e ) {// r e t u r n True i f t r a n s f o r m a t i o n// i s a p p l i c a b l e t o e x p r e s s i o n e ;}Plan apply ( Plan e ) {// r e t u r n new e x p r e s s i o n// g e n e r a t e d from e x p r e s s i o n e ;}}apply, который строит новый (под)план выполнения запроса применяя трансформацию к исходному, и регистрируются в списке доступных трансформаций.В архитектуре системы есть базовые реализации некоторых универсальных трансформаций плана, например, трансформация смены алгоритма, реализующего операцию, или свойства дистрибутивности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
