Автореферат (1149730), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

и фиксированного коли¯ = { ≥ 0| ∈ ( ), ∈чества вычислительных ресурсов ∈ R множество ∑︀R} :∈ ( ) ≤ называется распределением ресурсов, определяет количество ресурсов, выделяемое ∈ ( ). Количество ресурсов, выделенное¯(под)дереву с корнем в обозначим через ¯ ∈ R. Через обозначим множеДля заданного дерева плана выполнения запросаство всех возможных распределений ограниченного количества вычислительных ресурсов.Для дерева плана выполнения запроса∈ ¯ (¯ ) = ({()( )| ∈¯и распределения ресурсов его качество определяется следующим образом: ( ), ∈ ¯ }), где -функция агрегирования качества в плане. Для операцийс несколькими аргументами мы предполагаем, что вклад аргумента с меньшимкачеством доминирует при оценке качества поддерева. Более формально, качество поддерева оценивается как произведение относительного качества корневой операции и общего (минимального) качества ее аргументов: для любого¯¯ ∈ ¯¯ ¯ (¯¯ ) = ()( )·min∈() ¯ (¯¯ ), где ∈ ¯¯ , ¯¯ = { | ∈ (),¯ ∈ ¯¯ }.Задача 1 о распределении ресурсов между операциями в плане выполне12ния запроса переформулирована в новых терминах дерева и его вершин: заданного дерева планаи фиксированного количества ресурсов ∈Rнайтиarg max¯ ∈¯ (¯ ).

функцией качества∀ ∈ R ( )( ) = max¯ ∈¯ (¯ ).Для дерева плана выполнения запроса( ) : R → Qтакая, чтоназываетсяМы предполагаем, что функция относительного качества вершин от выделенного объема ресурсов неубывающая непрерывная ограниченная, а также может быть аппроксимирована всюду определенной вRкусочно-линейнойфункцией:⎧ < 0⎨ 0, () + ()( − ), ≤ < ∀ ∈ ( ) ()() =⎩ () + ()(− ), ≤ ∈ [0, ] количество линейных сегментов, () наклон на соответствующем+1сегменте, и () + ()( − ) = ().гдеНеобходимые условия оптимальности распределения ресурсов для ограниченных топологий дерева плана и в условиях жестких предположений о поведении функции качества доказаны в леммах. На базе точного теоретическогорешения, применимого к отдельным фрагментам дерева, построен алгоритмитеративного распределения ресурсов, на каждом шаге которого применениеточного решения будет корректно.После выделения минимального количества ресурсов каждой операции вплане выполнения запроса оставшееся свободное количество ресурсов можетбыть дополнительно распределено между вершинами в дереве, чтобы улучшитькачество всего плана.

Таким образом, имея некоторое распределение ресурсов¯ ∈ ¯ мы будем строить новое расширяющее распределение¯′ такое, что ∀ ∈ ( ) ≤ ′ , где ∈ ¯ , ′ ∈ ¯′ .ресурсов¯′ ∈При распределении дополнительного количества ресурсов дерево плана снова приходит в состояние, когда каждая операция достигла некоторого текущегокачества. Мы работаем с приростами ресурсов и рассматриваем на каждой ите-∀ ∈ ( )− , ∈ [0, ], ирации алгоритма только один линейный сегмент функции качества:()( ) = () + (),() = ()() = () +где ∈ [ , ()( − ). ], =Мы говорим об оптимальном распределении ресурсов, имея ввиду оптимальное распределение между операциями в плане дополнительного количества ресурсов, однозначно определяющее оптимальное расширяющее распределение.Вычислительные ресурсы должны быть выделены только тем операциям,которые оказывают влияние на качество результата и составляют критическое(под)дерево, формальное определение и алгоритм построения которого проработаны в диссертации.Лемма 3 определяет необходимые условия распределения ресурсов между13вершинами, образующими путь, в случае, если их функции качества линейны.Пусть - критический путь, ∈ R количество вычислительных ресурсов, которое необходимо распределить, функция качества каждойвершины ∈ () - линейна, то есть ()() = ()+(), где лежит внутри области определения функции.

При оптимальном распределении ресурсов∃ + () ⊆ () : > 0 тогда и только тогда, когда ∈ + (); иЛемма 3⎛ = max ⎝где⎞1+ ∑︁∈ + ()() () ⎠−,0 ,() () ∈ (), = | + ()|.Лемма 4 определяет оптимальное распределение ресурсов между братьямив критическом (под)дереве.Пусть критическое (под)дерево; ∈ () корневые вершиныподдеревьев-братьев с линейными функциями качества, то есть (¯ )() = (¯ ) + (¯ ), где лежит внутри области определения функции; ∈ Rколичество вычислительных ресурсов, которое должно быть распределеномежду этими поддеревьями. При оптимальном распределении ресурсов ¯ =Лемма 41/(¯ )∑︀.1/(¯ )Леммы 3 и 4 определяют стратегию оптимального распределения ресурсовмежду вершинами в дереве определенной структуры.

Поскольку леммы основаны на линейном поведении функций качества, распределение ресурсов будетпроисходить в несколько этапов, на каждом из которых будет распределятьсянекоторое количество вычислительных ресурсов. Для того, чтобы иметь возможность использовать утверждения лемм, в алгоритме строятся виртуальныегипер-вершины из определенных частей дерева плана, и при работе с каждойотдельной гипер-вершиной применяется соответствующая лемма.Алгоритм распределения ресурсов имеет полиномиальную сложность отчисла операций в плане выполнения запроса и количества линейных сегментов в функциях качества каждой из операций. Результаты экспериментов показали, что предложенный приближенный алгоритм распределения ресурсовдостаточно точный и эффективный.В четвертой главе представлены алгоритмы бикритериальной оптимизации запросов, допускающих контролируемое приближенное выполнение приограничениях на время вычислений и качество ответа.

Алгоритмы основанына компактном приближенном представлении множества Парето, называемомоптимальным составным сегментом. В главе описаны адаптации различных методов оптимизации для построения оптимального составного сегмента и приведены результаты их экспериментальной оценки.14Решаемая задача 3 параметрической оптимизации при ограничениях переформулирована следующим образом: для заданного запроса ∈ Rвозможных значений количества ресурсанайти план ∈ E для всех¯ ∈ () такой,∀ˆ ∈ () (¯)( ) ≥ (ˆ)( ).Составным сегментом для запроса называется неубывающая кусочно¯ : R → Q, каждый интервал которой ассоциирован слинейная функция ¯ () = (), где функция качества планапланом выполнения запроса, и ∈ E, ассоциированного с интервалом, содержащим .

Составной сегмент может быть представлен конечным множеством = {⟨, ⟩ : = [ , )} нечтопересекающихся интервалов значений в пространстве вычислительных ресурсов{[ , )},покрывающих весь диапазон[0, ∞),с ассоциированными с нимипланами и их функциями качества, суженными на рассматриваемый интервал.Составной сегментдоминирует над,если для всех¯ () ≥ ∈ [0, ∞) ¯ (). Для любых сегментов и доминантой называется составной сегмент = dom(, ) такой, что доминирует над и и любой другой составнойсегмент, доминирующий над и , доминирует над .Составной сегмент запроса, который доминирует над всеми составными сегментами запроса, называется оптимальным. Мы используем оптимальный составной сегмент в качестве компактного представления множества Парето взадаче бикритериальной оптимизации.Разработанные алгоритмы построения оптимального составного сегментазапроса на базе известных методов оптимизации запросов основаны на перечислителе планов выполнения запроса, использующем множество доступныхтрансформаций.

Для каждого плана, сгенерированного перечислителем, строится функция качества, представленная составным сегментом; далее эти сегменты (итеративно) сливаются в один составной сегмент, который считаетсяоптимальным при завершении анализа. В работе рассматривалось три основных алгоритма перечисления планов выполнения запроса: полное сканирование пространства планов (full), итеративное улучшение (iterative improvement)и рекурсивное построение (recursive descent).Экспериментальнаячастьработыпосвященапроверкесуществованиянетривиальных составных сегментов сценариев анализа данных и сравнениюпроизводительности предложенных методов их построения.В пятой главе рассматривается архитектура системы анализа данных, вкоторой мы продемонстрировали работу методов, описанных в предыдущихглавах, и соединили воедино несколько частей: алгебра на основе подобия, модели стоимости и качества, методы распределения ресурсов и подходы к решению задачи бикритериальной оптимизации.Система принимает пользовательский запрос и ограничения на его выполнения, оптимизирует и исполняет на вычислителях.

Контекст системы включает в себя разнородные источники данных; различные, возможно распределенные, вычислители; и модуль, в котором пользователь специфицирует конкретный сценарий-запрос на анализ данных.15Архитектура системы отвечает требованиям, сформулированным в диссертации, например, возможность работы в неоднородной среде или добавленияновых операций и исполнителей, ранее не включенных в систему.В работе выделены и проработаны два типа интерфейсов: интерфейсы работы с внешним окружением системы, и интерфейсы расширения системы.Предложенная система оптимизации и приближенного выполнения запросов функционирует среде, включающей в себя внешний модуль, реализующийинтерфейс с пользователем; разнородные источники данных и вычислители.Во-первых, запросы передаются в систему из некоторого внешнего модуляклиента, реализующего интерфейс с пользователем.

Клиент позволяет пользователю формулировать сценарии обработки данных и анализировать результаты их исполнения, в то время как в систему передаются задачи оптимизациии выполнения запросов на алгебраическом уровне.Архитектура системы анализа данных строится на основе расширяемой алгебры операций над Q-множествами. В архитектуре предусмотрено расширение системы анализа данных новыми операциями или алгоритмами, что непозволяет в реализации жестко ограничить набор операций уже специфицированными.Во-вторых, предлагаемая архитектура опирается на систему неоднородных,возможно, распределенных вычислительных модулей, в качестве которых могут выступать существующие СУБД, машины map-reduce или другие внешниепрограммы. Система отвечает за оптимизацию и приближенное выполнениезапросов на алгебраическом уровне, и передает непосредственные вычислительные задачи внешним модулям.

Таким образом поиск оптимального плана приближенного выполнения запроса происходит централизованно, а непосредственное исполнение может быть распределено между вычислительнымимодулями.В-третьих, в системе происходит анализ данных из внешних источников разнородных по типу и методам хранения данных, например, файлов или таблицСУБД. Неоднородность источников данных на алгебраическом уровне скрывается работой с операциями первичной выборки, которые строят представлениеданных в едином формате. Таким образом, так же как и в случае работы свнешними вычислительными модулями, протокол работы с внешним источником данных определяется при реализации и регистрации в системе соответствующей алгебраической операции.Архитектура системы исполнения запросов содержит: парсер, оптимизатори исполнитель.Для поддержки расширяемости алгебры используется оптимизатор, настраиваемый на новые специфические операции алгебры, которые порождают новые алгебраические тождества.

Оптимизатор основан на расширяемом и настраиваемом множестве трансформаций планов (алгебраический выражений).В предложенной архитектуре системы трансформации включают в себя возможные эквивалентные перестроения планов двух типов, неразличимых с точ16ки зрения реализации: основанные на алгебраических тождествах или на различных реализациях одной операции. Такая модель позволяет легко встраиватьв систему новые операции, алгоритмы, их реализующие, и соответствующиетрансформации. Для обеспечения расширяемости пространство трансформаций не должно быть реализовано глубоко внутри оптимизатора; поэтому в архитектуре системы определены единые интерфейсы, позволяющие легко встраивать новые трансформации в систему.Для того, чтобы иметь возможность выбрать эффективный план выполнения запроса, оптимизатор основывается на моделях стоимости и качества,определенных для всех операций, в том числе для пользовательских расширений.

Характеристики

Список файлов диссертации