Диссертация (1149731), страница 19
Текст из файла (страница 19)
Для каждой пары (, )для эксперимента строилось 100 случайных планов, для каждого плана генерировалось 10 функций качества (для каждой операции) с тем, чтобы получить96абРис. 3.5. Зависимость между вычислительной сложностью и точностью приближенного алгоритма распределения ресурсовдостаточное количество примеров планов с редкими топологиями. Для каждогоплана распределялось количество ресурсов равное = +0.5*( − ).На рисунке 3.5а по оси ординат показано относительное качество плана, полученное при приближенном распределении ресурсов, по сравнению с качеством,достижимым при использовании алгоритма, приближающего точный с ограничением равным 5% от максимального количества ресурсов для плана.
По осиабсцисс показана разветвленность деревьев планов выполнения запросов, оцениваемая как отношение числа бинарных операций в плане к максимальномучислу бинарных операций в плане с операциями. Отметим, что относительное качество уменьшается при увеличении числа бинарных операций в плане. Вэтом случае дерево плана содержит достаточное количество путей и вертикальных гипер-вершин для того, чтобы при распределении ресурсов использовалисьлинейные приближения функций качества, и достаточное количество бинарныхопераций, чтобы приближения повлияли на распределение ресурсов.Рисунок 3.5б показывает относительное число итераций приближенногоалгоритма по сравнению с его условно точной версией.
Число итераций приближенного алгоритма уменьшается с ростом числа бинарных операций в планевыполнения запроса. Это объясняется тем, что горизонтальные гипер-вершинына каждой итерации распределения ресурсов принимают большие порции ресурсов по сравнению с вертикальными.Результаты экспериментов показали, что предложенный приближенныйалгоритм распределения ресурсов достаточно точный и эффективный.973.6. Основные результатыВ главе описана разработанная математическая модель задачи распределения ресурсов; предложен и проанализирован пошаговый приближенный алгоритм распределения вычислительных ресурсов среди операций в плане выполнения запроса.
Изложенные в главе результаты исследования опубликованыв [17, 19].98Глава 4. Оптимизация приближенноговыполнения запросовВ главе представлены алгоритмы бикритериальной оптимизации запросов,допускающих контролируемое приближенное выполнение при ограничениях навремя вычислений и качество ответа.Алгоритмы основаны на компактном приближенном представлении множества Парето, называемом оптимальным составным сегментом. В главе описаны адаптации различных методов оптимизации для построения оптимальногосоставного сегмента и решения специфической бикритериальной задачи и приведены результаты их экспериментальной оценки.4.1. Предварительные рассужденияВ контексте контролируемого приближенного анализа данных пользователь вместе со сценарием-запросом предоставляет определенные ограничения,например, максимальное время вычислений или минимальное качество результата.
Эти ограничения на выполнение запроса должны быть удовлетворены.В этой главе мы рассматриваем следующий целевой сценарий обработкизапроса. Оптимизатор анализирует запрос пользователя и строит множествооптимальных планов его выполнения для всех осмысленных ограничений. Затем пользователь может выбрать фактические значения для ограничений наприближенное исполнение запроса, находя подходящий компромисс между качеством результата и затраченными вычислительными ресурсами.
На основеэтих дополнительно заданных ограничений выбирается конкретный план выполнения запроса. Таким образом, описанная в этой главе модель оптимизациии приближенного исполнения сценариев анализа данных позволяет в интерактивном режиме влиять на ограничения на вычисления.В главе 2 была сформулирована целевая задача 2.7 поиска оптимального99плана при ограничениях, но мы на этапе оптимизации запроса будем строитьрешение задачи 2.6, поскольку конечные значения ограничений и параметровне известны.Решаемая задача 2.6 параметрической оптимизации при ограничениях была формально поставлена в главе 2 и может быть переформулирована следующим образом: для заданного запроса ∈ E для всех возможных значенийколичества ресурса ∈ R найти план ¯ ∈ () такой, что ∀ˆ ∈ () (¯)( ) ≥(ˆ)( ).В подразделе 2.5.4 была доказана эквивалентность задачи 2.6 параметрической оптимизации и задачи 2.5 бикритериальной оптимизации.
Мы решаемэту специфическую задачу оптимизации запросов, допускающих приближенноевыполнение, как параметрическую и строим множество оптимальных плановвыполнения запроса при неизвестных на этапе оптимизации значениях параметров (ограничениях).Таким образом, мы решаем специфическую задачу оптимизации сценариеванализа данных, в контексте их приближенного контролируемого исполнения.Мы построим компактное представление множества Парето для задачи оптимизации, называемое, как структуру данных, которая для любого количества вычислительных ресурсов содержит план,обеспечивающий максимально возможное ожидаемое качества результата призаданных ограничениях. Симметрично, для фиксированного ожидаемого качества результата оптимальный составной сегмент хранит план запроса, которыйобеспечивает такое качество при использовании минимального количества вычислительных ресурсов.
Таким образом, на этапе оптимизации запроса мы неминимизируем количество необходимых вычислительных ресурсов и не максимизируем качество, а ищем множество возможных компромиссов между этимикритериями оптимизации.Возможные подходы к решению задачи многокритериальной оптимизации запросов основаны на последовательной оптимизации отдельных критериев ( [38, 41]) или построении агрегированного критерия ( [37, 39]). Сведениезадачи к однокритериальной может работать в некоторых случаях, но следующие рассуждения показывают, что это происходит не всегда. Приближенныеалгоритмы, например на основе случайных выборок, могут изменить важныестатистические свойства обрабатываемых данных и привести к различным оп-оптимальным составным сегментом1001Quality0.80.6A0.4BOCS0.20123456Resource789а10.9[APRED_JOIN][A_SELECT] [SRC 100.0][A_SELECT] [SRC 200.0]0.8Quality0.7[APRED_JOIN][A_SELECT] [SRC 100.0][E_SELECT] [SRC 200.0]0.60.5[HASH_JOIN] [E_SELECT][SRC 100.0] [A_SELECT][SRC 200.0]0.40.3[HASH_JOIN] [A_SELECT][SRC 100.0] [E_SELECT][SRC 200.0]0.20.10020004000Resources6000[HASH_JOIN] [E_SELECT][SRC 100.0] [E_SELECT][SRC 200.0]бРис.
4.1. Нетривиальные оптимальные составные сегментытимальным по Парето планам.Прямолинейная стратегия, описанная в [16], состоит в том, что сначаластроится оптимальный план выполнения запроса по одному критерию (минимизируется количество вычислительных ресурсов при точном исполнении плана),а затем учитываются ограничения на его приближенное исполнение на основе решения задачи распределения ресурсов, описанного в главе 3. Однако этотподход строит решение, работающее в ограниченном числе случаев.Давайте рассмотрим запрос с двумя планами его контролируемого приближенного выполнения и с моделями качества (определение 2.41) изображенными на рисунке 4.1а. Далее в этой главе мы будем использовать термины"модель качества"и "функция качества"взаимозаменяемо.План оптимален, если количество доступных вычислительных ресурсов101больше 5; в противном случае план обеспечивает за сопоставимое количестворесурсов большее качество.
Решение бикритериальной задачи основывается нафункции качества, обозначенной как OCS на рисунке 4.1а, и позволяет выбирать разные оптимальные планы в зависимости от ограничений на вычислительные ресурсы на этапе непосредственного выполнения запроса.4.2. Модель: составной сегментВ главе 2 мы упоминали, что при оптимальном распределении различногоколичества ресурсов между операциями в плане выполнения запроса достигаются разные уровни качества результата. Пусть : R → Q - функция качестваплана ∈ E по определению 2.41.
Обратная функция определяет какое количество ресурсов необходимо распределить между операциями в плане, чтобыдостигнуть заданного качества.Мы предполагаем, что относительное качество (под)плана описываетсянеубывающей ограниченной функцией. Далее в этой главе мы работаем скусочно-линейными приближениями функций качества.Ограниченная функция качества плана определена на замкнутом интервале [ , ]. Для упрощения обозначений расширим множество значений аргумента функции качества до [0, ∞) следующим образом: для < () = 0 и для > () = ( ).Модели качества показывают, как качество результата зависит от количества выделенных вычислительных ресурсов.
Однако, при оптимизации запросавыбор оптимального плана зависит от ограничения на вычислительные ресурсы, поэтому модель качества должна быть обобщена и ассоциирована одновременно с несколькими планами.Теперь мы не будем связывать модель качества с единственным планомвыполнения запроса, а будем ассоциировать отдельные интервалы функции качества с различными эквивалентными планами.Составным сегментом для запроса называется неубывающая кусочно-линейная функция ¯ : R → Q, каждый интервал которойассоциирован с планом выполнения запроса (не обязательно одним и тем жедля различных интервалов), и ¯ () = (), где функция качества плана ∈ E, ассоциированного с интервалом, содержащим .Определение 4.1.102Отметим, что функция качества любого плана может быть представленасоставным сегментом, все интервалы которого ассоциированы с этим планом.Составной сегмент может быть представлен конечным множеством ={⟨, ⟩ : = [ , )} не пересекающихся интервалов значений в пространстве вычислительных ресурсов {[ , )}, покрывающих весь диапазон [0, ∞),с ассоциированными с ними планами и их функциями качества, суженнымина рассматриваемый интервал.
В целях эффективности работы с такими составными сегментами интервалы хранятся отсортированными. Для запроса срисунка 4.1а мы можем построить, например, следующий составной сегмент: = {⟨[0, 2), ⟩, ⟨[2, 5), ⟩, ⟨[5, 6), ⟩, ⟨[5, ∞), ⟩}.Определение 4.2.Составной сегмент доминирует над , если для всех¯ () ≥ ¯ (). ∈ [0, ∞) Для любых сегментов и доминантой называется составной сегмент = dom(, ) такой, что доминирует над и и любой другой составнойсегмент, доминирующий над и , доминирует над .Определение 4.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
