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

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

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

Заметим, что это отношение не являетсяотношением порядка, в частности одновременно может выполняться следующее: 1 (1 ) ≺ 2 (2 ) и 2 (2 ) ≺ 1 (2 ).2.2.6. Модель стоимостиТочное вычисление оценок эффективности планов и операций невозможно,поскольку требует исполнения плана, поэтому в качестве приближения функций стоимости операций рассматриваются их модели стоимости.Для операции ∈ O с конфигурацией ∈ () модельстоимости это функция ¯(()) : S → R, где S - пространство свойствQ-множеств.Модель стоимости операции по одному критерию это функция (()) :S → R.Определение 2.29.62Пространство свойств Q-множеств S определяет различные свойства аргументов операции, которые влияют на ее стоимость, например, количествообъектов в Q-множестве или их упорядоченность в потоке относительно оценки объектов.

Оценка свойств Q-множеств, передаваемых между операциямив плане, не требует непосредственного исполнения запроса, поскольку это неимеет смысла.Отметим, что для одной функции стоимости могут быть построены разныепо точности и необходимому набору параметров модели стоимости.Таким образом, при оценке эффективности планов вычисление функциистоимости ¯ заменяется вычислением ¯.Поскольку для работы с моделями стоимости важно оценивать статистикиаргументов операции, то при переходе к оценке стоимости плана выполнениязапроса важно знать также и статистики и другие параметры результата выполнения операции.Для операции ∈ O с конфигурацией ∈ () модельоценки данных это функция (()) : S → S.Определение 2.31. Для плана выполнения запроса ∈ E с конфигурацией ∈ () его приближенную стоимость, вычисленную на основе моделей стоимости, будем обозначать через ¯(()) ∈ R, или через (()) ∈ R приработе с одним критерием.Определение 2.30.Проиллюстрируем введенные выше определения и их взаимосвязь на простом примере.

Рассмотрим выражение ∈ E, состоящее из двух операций идвух Q-множеств: = 1 (2 (2 ), 1 ). Для простоты обозначений предположим,что конфигурации операций зафиксированы и не могут повлиять на оценкистоимости. Стоимость операции 2 вычисляется просто на основе ее моделистоимости ¯(2 ) и свойств 2 Q-множества 2 и равна ¯(2 )(2 ). Оценка стоимости операции 1 зависит не только от ее модели стоимости ¯(1 ) и свойств 1Q-множества 1 , но и от свойств Q-множества, возвращаемого 2 (2 ), и равна¯(1 )((2 )(2 ), 1 ).632.3.

Задачи оптимизации запросовУточнение постановки основных возможных задачи оптимизации запросовначнем с обсуждения задач оптимизации абстрактной целевой функции.Любая задача оптимизации состоит в том, чтобы найти значение аргумента, которое минимизирует значение целевой функции, при заданных ограничениях.Если целевая функция принимает скалярные значения, то такая задачаоптимизации называется однокритериальной.Задача оптимизации многокритериальна, если рассматривается одновременно несколько скалярных целевых функций (то есть целевая функция, принимающая значения в векторном пространстве).

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

При оптимизации запросов, например, параметрическая задача возникает в ситуации, когда на этапе выбора плана не известны статистики обрабатываемых в запросе данных или актуальные на момент выполнения запросадоступные вычислительные ресурсы.Задача многокритериальной оптимизации трансформируется в параметрическую, если некоторые критерии оптимизации становятся параметрами.Перейдем к уточнению задач оптимизации запросов.642.3.1. Задача однокритериальной оптимизацииЕсли критерий эффективности один, то целевая функция принимает скалярные значения и оптимальными будут сконфигурированные планы выполнения запроса, на которых достигается ее минимальное значение.Задача 2.1. Задача однокритериальной оптимизации запроса ∈ E формули-руется следующим образом: найти хотя бы один сконфигуриарованный план(¯, ¯) ∈ P() такой, что ∀(ˆ, ˆ) ∈ P() (¯(¯)) ≺ (ˆ(ˆ)) ∈ R.В традиционных оптимизаторах запросов, как правило, задача выбора эффективного плана сводится к однокритериальной оптимизации; и среди множества оптимальных планов, обеспечивающих одинаковую агрегированную стоимость, выбирается один для непосредственного исполнения.2.3.2.

Задача многокритериальной оптимизацииЗадача многокритериальной оптимизации запроса ∈ E ставится следующим образом: найти множество оптимальных (по Парето)планов и их конфигураций {(¯, ¯)|(¯, ¯) ∈ P(), ∀(ˆ, ˆ) ∈ P() ¯(¯(¯)) ≺ ¯(ˆ(ˆ))}.Задача 2.2.Таким образом при оптимизации запроса, строится множество наиболееэффективных планов его выполнения, которое является множеством Парето.2.3.3. Задача параметрической оптимизацииПоведение планов выполнения запроса и, соответственно их стоимость поразным критериям, может зависеть от значений некоторых параметров. Поставим задачу параметрической многокритериальной оптимизации запросов.Задача параметрической многокритериальной оптимизации запроса ∈ E и множества параметров его выполнения P ставится следующим образом: найти функцию : P → P() такую, что если () = (¯, ¯),то ∀(ˆ, ˆ) ∈ P() ¯(¯(¯)()) ≺ ¯(ˆ(ˆ)()), где через (.)() обозначается сконфигурированный план выполнения запроса при фиксированных значениях параметров запроса ∈ P.Задача 2.3.652.4.

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

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

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

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

Вычислительные ресурсыФункция стоимости среди нескольких критериев эффективности можетоценивать количество вычислительных ресурсов, необходимое для выполненияоперации. Когда традиционный оптимизатор минимизирует стоимость выполнения запроса, в действительности происходит минимизация количества вычислительных ресурсов необходимых для его исполнения.Различные типы ресурсов могут быть использованы для оценки эффективности выполнения запросов и для ограничения их приближенного выполнения.Некоторые из них, такие как процессорное время, количество циклов процессора и объемы ввода/вывода, зависят в основном от сложности плана; в товремя как другие, например, размер используемой памяти или время вычислений, также могут зависеть от имеющейся конфигурации вычислителей системы(например, числа процессоров или ядер).

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

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