Диссертация (1149731), страница 14

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

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

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

Пространство значений, которое может принимать ко-личество вычислительных ресурсов, обозначим через R ⊂ R.Отметим, что вычислительные ресурсы могут рассматриваться в нашеймодели приближенного выполнения запросов одновременно как критерий оценки эффективности выполнения плана и параметр, определяющий его конфигурацию.Для операции ∈ O существует функция отображенияколичества вычислительных ресурсов, выделенных на выполнение операции, впараметры ее конфигурации: : R → ().Для операции ∈ O и количества вычислительных ресурсов ∈ R через() обозначим сконфигурированную операцию при данном количестве ресурсов, то есть () = (()).Определение 2.33.2.4.3. КачествоПоскольку мы говорим о приближенном выполнении запросов и операций,следует обсудить важное понятие качества, которое является вторым ключевымкритерием оценки эффективности планов приближенного выполнения запросов.68Несмотря на то, что понятие качества данных сложное и часто рассматривается в нескольких размерностях, мы предполагаем, что качество набораданных и Q-множества, оценивается одним числом, то есть мы применяем агрегированный критерий.Для Q-множества ∈ Q его абсолютное качество обозначается как ∈ R.Определение 2.34.Качество операций естественно определить исходя из качества данных, которые они генерируют в результате своей работы.

Например, качество среднегозначения может оцениваться точностью, и больший размер выборки приводитк большей стоимости вычислений, но лучшему качеству. С другой стороны, мыможем оценивать качество приближенной операции агрегирования, основаннойна сэмплировании, через относительный размер выборки. Отметим, что в первом случае оценка качества не зависит от способа вычислений, во втором случаемы используем косвенную оценку качества результата на основе информации ометоде получения ответа.Важно отметить, что в дальнейшем для построения моделей стоимости/качества важны оценки относительного качества операций: то есть отношениякачества результирующего Q-множества к качеству аргументов операции, поскольку даже операции с неограниченным количеством ресурсов могут изменять качество данных.Когда мы ограничиваем количество вычислительных ресурсов на исполнение операции, ее относительное качество может оцениваться через отношениеабсолютного качества результата, полученного при ограничениях, к качествудостижимому при неограниченных ресурсах.Пространство значений, которое может приниматьотносительное качество, обозначим через Q ⊂ R.Для приближенной унарной операции ∈ O, которая принимает в качестве аргумента 1 ∈ Q и в качестве результата при неограниченном количестве вычислительных ресурсов строит (∞)(1) = 2 ∈ Q, при ограниченномколичестве вычислительных ресурсов ∈ R строит ()(1) = 3 ∈ Q, ееотносительное качество определяется как ∈ Q.Определение 2.36.

Для операции ∈ O с конфигурацией ∈ () определимее относительное качество как функцию () : Q × R → Q.Определение 2.35.2369Таким образом, относительное качество операции зависит от ее аргументов и количества выделенных вычислительных ресурсов. В дополнение к вычислительным ресурсам качество становится вторым критерием оптимизациизапросов, допускающих приближенное выполнение.Мы определили агрегированные критерии эффективности, актуальные вконтексте приближенного выполнения запросов, а именно понятия вычислительных ресурсов и качества. Отметим, что вычисление стоимости операций ипланов, а также построение моделей стоимости по этим критериям, как и подругим обсуждалось в разделе 2.2.2.4.4.

Модель качестваДля приближенных алгоритмов реализующих операции алгебры определим модель стоимости.Для операции ∈ O с конфигурацией ∈ () бикритериальная модель стоимости это функция ¯(()) : S → R × Q.Определение 2.37.Таким образом, в расширенной модели стоимости связаны два ключевыхкритерия оценки приближенных планов выполнения запросов: качество и вычислительные ресурсы. Напомним, что выбранные нами критерии качества являются агрегированными и включают в себя различное понимание качества иразнообразные вычислительные ресурсы.Определим также модели качества, которые описывают зависимости стоимости и качества для приближенных алгоритмов.Для операции ∈ O модель качества это пара функций : S × R → Q и −1 : S × Q → R.Определение 2.38.Модель качества операции ∈ O строится на основе ее бикритериальноймодели стоимости: ¯(( ()))() = (, (, )), где ∈ S, ∈ R.Примеры моделей стоимости, на основе которых могут быть построены,определенные таким образом модели качества и стоимости рассматриваютсяв [20].702.5.

Оптимизациязапросов,допускающихпри-ближенное выполнениеПри приближенном исполнении запросов, возникает несколько задач оптимизации.2.5.1. Задача распределения ресурсовЗадача распределения ресурсов, состоит в том, чтобы распределить ограниченное количество вычислительных ресурсов между операциями в плане выполнения запроса так, чтобы максимизировать качество ответа.Для заданного плана выполнения запроса ∈ E и фиксированногоколичества ресурсов ∈ R множество ¯ = { ≥ 0| ∈ (), ∈∑︀R} : ∈() ≤ называется распределением ресурсов, определяет количество ресурсов, выделяемое ∈ ().Через ¯ обозначим множество всех возможных распределений вычислительных ресурсов , а через ¯ = {¯| ∈ R}.Определение 2.39.Отметим, что распределение ресурсов определяет конфигурацию приближенного выполнения плана запроса.Различные стратегии распределения ресурсов между операциями в планевыполнения запроса определяют качество ответа.Для плана выполнения запроса ∈ E относительнымкачеством называется функция () : ¯ → Q.Определение 2.40.Поведение относительного качества определяется моделями качества операций, составляющих алгебраическое выражение плана выполнения запроса.Задача 2.4.

Для заданного плана выполнения запроса ∈ E и фиксированногоколичества ресурсов ∈ R задача распределения ресурсов ставится следующим образом: arg max¯ ∈¯ ()(¯).Аналогичным образом может быть поставлена симметричная задача, в которой минимизируется количество вычислительных ресурсов при фиксированном ожидаемом качестве результата выполнения плана.71Предполагая решение задачи распределения для всех возможных значенийколичества ресурсов, можно определить функцию качества плана, показывающую какого качества может достигнуть план при выделении ему фиксированного количества ресурсов.Для плана выполнения запроса ∈ E определим его модель качества : R → Q так, что ( ) = max¯ ∈¯ ()(¯).Определение 2.41.2.5.2. Задача бикритериальной оптимизацииНапомним, что задача многокритериальной оптимизации запроса ∈ Eставится следующим образом: найти множество планов и их конфигураций{(¯, ¯)|(¯, ¯) ∈ P(), ∀(ˆ, ˆ) ∈ P() ¯(¯(¯)) ≺ ¯(ˆ(ˆ))}.В контексте приближенного выполнения мы рассматриваем два критерияоптимизации запроса: количество вычислительных ресурсов и качество результата, поэтому мы можем рассматривать задачу бикритериальной оптимизации.Задача бикритериальной оптимизации запроса ∈ E, допускающего приближенное исполнение, ставится следующим образом: найти множество планов и распределений ресурсов {(¯, ¯)|¯ ∈ (), ¯ ∈ ¯¯ ∈ ¯¯, ∀ˆ ∈ (), ^ ∈ ¯^ (¯)(¯) ≥ (ˆ)(^)}.Задача 2.5.2.5.3.

Параметрическая задача оптимизацииПоскольку мы рассматриваем оптимизацию и контролируемое приближенное выполнение сценариев анализа данных, возникает специфическая постановка задачи параметрической оптимизации.Задача параметрической оптимизации запроса ∈ E, допускающего приближенное исполнение, ставится следующим образом: найти функцию : R → () такую, что если ( ) = ¯, то ∀ˆ ∈ () ¯( ) ≥ ^( ),где ∈ R.Задача 2.6.Таким образом, в задаче параметрической оптимизации для каждого значения количества вычислительных ресурсов ищется план, достигающий максимального качества при оптимальном распределении ограниченного количестваресурсов.72Также как и в задаче распределения ресурсов может быть поставлена симметричная задача оптимизации.Таким образом, для всех возможных ограничений на один из критериев оптимизации ищется план оптимальный по второму критерию. В работе мы будемв качестве целевой рассматривать именно постановку задачи оптимизации прирассмотрении в качестве параметра количество вычислительных ресурсов.Эта задача лежит в основе выполнения запросов в реальном времени, тоесть за фиксированное гарантированное время.

В этой ситуации под вычислительными ресурсами может пониматься время вычислений.2.5.4. Связь задачРешение бикритериальной задачи оптимизации 2.5, сформулированной вразделе 2.5.2, для запроса ¯ ∈ E может быть представлено множеством Паретоˆ, состоящим из троек (, , ()), где ∈ (¯), ∈ R, таких, что для любойпары троек (, , ) и (′ , ′ , ′ ), если ′ ≤ , то ≥ ′ .Решение параметрической задачи, поставленной в 2.6 может быть представлено множеством ¯ таких же троек (, , ()), где ∈ R, () = ∈ (¯)и одно из решений параметрической задачи.Если тройка (, , ()) ∈ ¯ не принадлежит ˆ, то ∃(′ , , ′ ()) ∈ˆ ′ () ≥ (), что противоречит тому, что (, , ()) ∈ ¯; следовательно|любая тройка из решения параметрической задачи лежит в решении бикритериальной.Аналогичным образом доказывается, что любая тройка из решения бикритериальной задачи лежит в решении параметрическойТаким образом, поставленные задачи оптимизации запросов, допускающихприближенное исполнение, эквивалентны.2.5.5.

Задача оптимизации при ограниченияхНа этапе выполнения запросов, допускающих контролируемое приближенное исполнение, само по себе решение бикритериальной/параметрической задачи, представленное множеством планов, часто не имеет смысла, так как в немне учитываются конкретные ограничения.73Конечная задача выбора оптимального плана для последующего исполнения может быть поставлена следующим образом:Для заданного запроса ∈ E и фиксированного количества ресурсов ∈ R задача оптимизации запроса при ограничениях состоит в том,чтобы найти ¯ ∈ () такой, что ∀ˆ ∈ () ¯( ) ≥ ^( ).Задача 2.7.В такой постановке при уже фиксированных ограничениях на один из критериев оптимизации, являющийся одновременно ее параметром, выбирается оптимальный план выполнения запроса.Решение этой задачи может быть получено из решения параметрическойзадачи 2.6.2.6.

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

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