Диссертация (1149731), страница 8
Текст из файла (страница 8)
Этот подход кажется особенно важным в контексте распределенного выполнения запросов, характеризующегося недостаткоммета-информации о вычислителях и данных.Адаптивное выполнение запросов может осуществляться на несколькихуровнях: на уровне построения плана выполнения запроса и на уровне алгоритмов, реализующих операции алгебры.1.3.1. Методы адаптивного выполнения запросовВ детальном обзоре [70], представлена классификация различных подходов к адаптивному выполнению точных запросов, и проведен глубокий анализнекоторых из них.В отличие от классической схемы последовательных этапов оптимизациии выполнения запросов, в адаптивных подходах оптимизация и выполнение запроса происходят параллельно, этапы взаимосвязаны, и, довольно часто, трудноотделимы.Адаптивное выполнение запросов может быть описано следующим циклом:∙ измерение,∙ анализ и оптимизация,∙ исполнение.35На первом шаге собираются статистики и другая информация о выполняемом плане.
На втором шаге анализируется собранная информация и принимается решение об изменении плана выполнения запроса. На последнем шагестартует выполнение нового плана.Все основные методы оптимизации запросов встраиваются в представленную схему. Например, в классической системе, поддерживающей обычную оптимизацию запроса с последующим выполнением выбранного плана, проходитровно одна итерация адаптивного цикла. Исполнитель запросов в Ingres четкоразделяет компоненты адаптивного цикла, исполняя запросы кортеж за кортежем.Неточность оценок стоимости выполнения операций и других параметров,используемых традиционным оптимизатором, является основной причиной развития методов адаптивного выполнения запросов, в которых обновленные помере выполнения запроса оценки используются для повторной оптимизации.Подход, предложенный в [71], обеспечивает контроль над ошибками оценок,что позволяет значительно повысить эффективность повторной оптимизации.Можно выделить два основных класса методов адаптивного выполнениязапросов с разными типами операций алгебры: маршрутизация данных и использование точек материализации.Большинство традиционных оптимизаторов основано на потоковом выполнении запросов, когда результат выполнения операции, по мере его формирования, кортеж за кортежем непосредственно перенаправляется на вход следующей операции.
В этом случае не происходит материализации промежуточныхрезультатов, и операции внутри одного запроса могут выполняться параллельно. Тем не менее, некоторые алгоритмы и даже операции, называемые блокирующими, не позволяют вычислить ответ до того, как получат все кортежи ихаргумента, и вынуждены материализовать промежуточные результаты.Операция выборки является потоковой, то есть в каждый момент времени обрабатывает ровно один объект. Среди потоковых операций следует выделить операции с состоянием, то есть хранящие некоторое внутреннее состояние,зависящее от процесса выполнения запроса.
Так операция соединения хранитвнутреннее состояние, зависящее от порядка вычисления соединений. Примером блокирующей операции может служить сортировка, в то время как операция соединения не всегда блокирующая: обычный алгоритм соединения на36основе хеширования блокирующий, а симметричный-нет.1.3.1.1. Потоковое выполнение запросовПлан выполнения запроса называется потоковым, если все операции в немявляются потоковыми.
Для этого класса планов адаптивные методы выполнения запросов показывают лучшие результаты; однако большинство методовтребует тесной взаимосвязи между реализацией алгебраических операций и модулем адаптивного выполнения запросов. Для потоковых планов выполнениязапросов перестройка плана происходит на уровне отдельных кортежей на основе их перенаправления между операциями. Однако операции с состояниямитребуют более сложной обработки, и изменение плана может приводить к частичной потере результатов некоторых уже проделанных промежуточных вычислений.Самый простой метод адаптивного выполнения запросов, основанный намаршрутизации кортежей, применим для задачи поиска оптимальной последовательности применения предикатов операции выборки, поскольку она не имеетсостояния.
В [70] рассматриваются адаптивные методы выполнения предикатов выборки, основанные на вихревом (eddy) операторе. Метод, основанный навихревом операторе, является универсальным и не зависит от конкретной стратегии выбора последовательности выполнения предикатов. Вихревой оператор,используется в качестве алгоритма-менеджера, который отслеживает процессвыполнения запроса и делает адаптивные решения о перенаправлении кортежей в тот или иной оператор, вычисляющий предикат.Среди стратегий перенаправления кортежей вихревым оператором рассмотрены: детерминированный алгоритм, жадный алгоритм, метод лотерейныхбилетов и маршрутизация на основе содержания.В детерминированном подходе в процессе выполнения операторов явнооценивается их селективность; на основе таких оценок периодически перестраивается план выполнения запросов.
Жадный алгоритм также используется дляперестройки плана на базе условных оценок селективности операторов, построенных с помощью случайных выборок.В методе лотерейных билетов вихревой оператор, направляя кортеж на обработку, выдает оператору билет; если кортеж возвращается в вихревой оператор, то лотерейный билет аннулируется. Такой подход позволяет неявно отсле-37живать селективность операторов. При маршрутизации кортежа применимыйоператор с большим нормализованным числом лотерейных билетов выигрываетновый билет.Маршрутизация на основе содержания подразумевает анализ пространства условных планов.
Для каждого оператора выбирается классифицирующийатрибут, максимально коррелирующий с селективностью. Для каждого кортежа по значению селективных атрибутов оценивается селективность операторовдля последующей вероятностной маршрутизации.Стратегии адаптивного выполнения запросов с соединениями намногосложнее из-за зависимости поведения операции соединения от уже вычисленных кортежей. Основные адаптивные методы выполнения данного класса запросов можно разделить на три группы: потоковое выполнение независимо отистории маршрутизации; потоковое выполнение, зависимое от истории; не потоковое выполнение. Первая группа методов сводится к методам адаптивноговыполнения предикатов выборки.
Потоковое выполнение, зависимое от истории, основано на тех же методах, но требует от адаптивного алгоритма внимательного отслеживания промежуточных состояний операторов.В [72] рассматривается алгоритм поиска оптимального порядка выполнения соединений в запросе при потоковом выполнении, который позволяет недублировать уже проделанные вычисления при перестройке плана.Метод адаптивного выполнения запросов, основанный на машинном обучении, предложен в [73].Архитектура системы адаптивного выполнения запросов описана в [74]. Воснове предложенной системы лежит понятие брокера запросов, который представляет собой модуль, реализующий определенные стратегии адаптивного выполнения запросов.В [75] рассматривается метод адаптивного выполнения XQuery запросов,основанный на динамических случайных выборках.1.3.1.2.
Промежуточная материализацияАльтернативный класс методов адаптивного выполнения запросов основан на использовании точек материализации. Точки материализации (блокирующие операции) разбивают план на несколько меньших подпланов, которыеоптимизируются и исполняются независимо. Другими словами, как только вы-38полнение плана достигает точки материализации, невыполненные части планаоптимизируются заново на основе более точных статистик, вычисленных вовремя предыдущего этапа выполнения плана.
Задача адаптивного выполнениязапросов с материализацией обсуждается в [76].1.3.2. Адаптивные алгоритмы выполнения операцийАдаптивное выполнение может осуществляться и на более низких уровнях.Так в литературе представлено множество адаптивных алгоритмов, реализующих отдельные операции, которые изменяют свое поведение в зависимости отхарактеристик обрабатываемых данных.Семейство самоадаптивных алгоритмов для операций соединения и агрегирования, предложено в [77].
Алгоритмы сочетают в себе свойства стандартных подходов, основанных на hash-функциях, слиянии и вложенных циклах, испособны подстраиваться под характеристики входных данных.В [78] предлагается адаптивная реализация симметричного соединения поподобию, используемого для выделения точных и нечетких дубликатов в коллекции, на основе hash-таблиц. Важной особенностью алгоритма является поддержка переключения между вычислением точного и приближенного соединения, на основе баланса между полнотой ответа и временем вычислений.Адаптивное выполнение операции симметричного hash-соединения с поддержкой ранжирования рассматривается в [79]. В работе предлагается подход,позволяющий в процессе выполнения запроса изменить план его выполненияв зависимости от изменений вычислительного окружения или характера данных. Главной сложностью переключения между планами является отслеживание внутренних состояний операций.
Основная идея состоит в том, чтобыпромежуточные состояния текущего плана трансформировать в другое, соответствующее новой стратегии выполнения запроса.Также адаптивные алгоритмы встречаются при обработке потоковых данных из внешних источников. Так в [80] описана система соединения потоков,которая подстраивается под потоки данных, поступающие с разной скоростью.Скользящее окно хранится в основной памяти и сохраняется на диск при увеличении скорости потока данных с целью предотвращения потерь результата.На основании этого подхода процессор, выполняющий обработку потоков адаптивно, переключается между алгоритмами, работающими с разными уровнями39памяти.1.4. СистемыВ этом разделе проанализированы системы оптимизации и выполнениясложных сценариев анализа данных в распределенных архитектурах: особоевнимание будет уделено языкам спецификации запросов к системе и их внутреннего представления, а также используемым подходам к оптимизации вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
