Диссертация (1149731), страница 21
Текст из файла (страница 21)
Будем использовать короткие буквенные метки для запросов с операциями выборки и соединения: S, J и N обозначают, соответственно, SELECT,JOIN и NA-JOIN. В таблице 4.1 приведены (смотреть SSSJJ) среднее времяпостроения оптимального составного сегмента.Таблица 4.1. Производительность алгоритмов построения оптимальных составных сегментов простых запрсоовЗапрос АлгоритмОбщееВремя построенияЧисловремя (мс) функций качества (мс) плановFull562271576SSSJJRecursive246119441Iterative17156259Full367192267317280SSSSJJJ Recursive262314282952Iterative752325911Все 3 алгоритма также ассоциировали одно множество планов с оптимальным составным сегментом более сложного запроса:[JOIN 1000 4000][JOIN 4000 16000][JOIN 16000 64000][SELECT][SRC 64000][SELECT][SRC 16000][SELECT][SRC 4000][SELECT][SRC 1000].Временные замеры в эксперименте с этим запросом отражены в таблице 4.1(смотреть SSSSJJJ).
Отметим, что алгоритм рекурсивного построения требуетбольше времени на построение оптимального составного сегмента сопоставимого по качеству с генерируемым алгоритмом итеративного улучшения. Этообъясняется сильным сокращением пространства планов выполнения запроса.Как и ожидалось, время, необходимое для построения оптимального составного сегмента на основе перечисления всего пространства планов, неприемлемовелико.1104.4.3. Производительность алгоритмовЗадача построения оптимального составного сегмента запроса, как решения задачи многокритериальной оптимизации, намного сложнее задачи однокритериальной оптимизации.Честное сравнение нашей реализации с промышленными оптимизаторами осложнено тем, что алгебраические свойства расширенных операций могутотличаться от реляционных, что делает невозможным, например, применениемногих эвристик.
В связи с этим для моделирования задачи однокритериальнойоптимизации мы заменили модели качества и стоимости всех алгоритмов тривиальными. Это позволило свести задачу построения оптимального составногосегмента к решению задачи оптимизации запроса по одному критерию. Дляболее честного сопоставления мы проводили эксперименты с одним пространством планов (сопоставимыми по размеру) в точном и приближенном случае.Цель эксперимента состояла в том, чтобы сравнить производительностьалгоритмов поиска оптимального плана по одному критерию и алгоритмов построения оптимального составного сегмента при увеличении числа операций неассоциативного соединения и фильтров в случайно сгенерированных запросах.Начиная с запроса с одной операцией соединения и двумя фильтрами, на каждом шаге запрос дополнялся операцией соединения и фильтром. Для каждоготипа запроса (по числу операций соединения) случайным образом генерировалось 5 запросов с различными уровнями селективности фильтров и с увеличением числа объектов в первичных источниках.На рисунке 4.2а показана относительная производительность алгоритмовпостроения оптимального составного сегмента по сравнению с соответствующими решениями задачи оптимизации запроса по одному критерию: время построения решения; время вычисления функций качества планов; число просмотренных планов выполнения запроса.На рисунке 4.2б показано увеличение числа просмотренных планов приусложнении запроса в том же эксперименте.Как и ожидалось, число просмотренных для построения оптимального составного сегмента планов существенно больше по сравнению с решением задачи однокритериальной оптимизации.
Тем не менее, рост отношения умеренный,что делает возможным применения алгоритмов многокритериальной оптимизации для достаточно сложных сценариев анализа данных.111350Relative Performance300Recursive ConstructionFull Time250Recursive ConstructionQuality Function Time200Recursive ConstrctionPlans150Iterative ImprovementFull Time10050Iterative ImprovementQuality Function Time0Iterative ImprovementPlans12345678910Number of Non-Associative Joinsа45004000Number of Plans35003000Recursive ConstructionSkyline2500Recursive ConstructionExact2000Iterative ImprovementSkyline1500Iterative ImprovementExact1000500012345678910Number of Non-Associative JoinsбРис. 4.2. Производительность алгоритмов итеративного улучшения и рекурсивного построения1124.4.4.
Качество алгоритмовПредыдущие эксперименты показали, что для одного запроса предложенные алгоритмы строят отличающиеся оптимальные составные сегменты. В этомподразделе описана серия экспериментов по оценке точности приближений коптимальному составному сегменту, построенных разными алгоритмами.Для оценки точности составного сегмента мы использовали площадь надграфиком его функции качества: меньшая площадь отражает большее качество.При проведении экспериментов проводился анализ того, как связаны качестворешения, размер запроса, и используемые методы сжатия.На рисунке 4.3а отражена зависимость производительности алгоритма построения оптимального составного сегмента (среднее время в миллисекундах)от сложности запроса и метода сжатия.Отметим, что качество оптимальных составных сегментов, построенныхразными алгоритмами, практически не отличается.
Небольшая разница в качестве отражена на рисунке 4.3б, демонстрирующем относительное качество (отношение площади над графиком к максимальной для данного типа запроса).На рисунке видно, что вычислительно более сложный алгоритм рекурсивногопостроения приводит к более точному решению.4.5. Основные результатыВ главе проведен анализ разработанных алгоритмов решения задачи бикритериальной оптимизации запросов, допускающих контролируемое приближенное выполнение при ограничениях на время вычислений и качество ответа.Предложенные алгоритмы позволяют строить компактное приближенное представление множества Парето. Результаты работы, описанные в главе, опубликованы в [23].1138000Full Time70006000Recursive ConstructionFLAT5000Recursive ConstructionPLANRecursive ConstructionSMALL 0.0240003000Iterative ImprovementFLAT2000Iterative ImprovementPLAN1000Iterative ImprovementSMALL 0.020012345Number of Added Non-Associative Joinsа1.000.99Recursive ConstructionFLATRelative Quality Area0.980.97Recursive ConstructionPLAN0.96Recursive ConstructionSMALL 0.020.950.94Iterative ImprovementFLAT0.93Iterative ImprovementPLAN0.920.91Iterative ImprovementSMALL 0.020.90012345Number of Added Non-Associative JoinsбРис.
4.3. Время и точность построения оптимального составного сегмента с использованием сжатия114Глава 5. Архитектура системы выполнениязапросовВ этой главе рассматривается архитектура системы анализа данных, которая реализует идеи и методы оптимизации и приближенного выполнения декларативных сценариев.На основе архитектуры мы продемонстрировали работу методов, описанных в предыдущих главах, и соединили воедино несколько частей: алгебра наоснове подобия, модели стоимости и качества (глава 2), методы распределенияресурсов (глава 3) и подходы к решению задачи бикритериальной оптимизации(глава 4).В рамках исследования на основе предложенной архитектуры также была разработана модельная реализация системы оптимизации и приближенноговыполнения запросов.5.1.
Примеры использования системыОсновной задачей, решаемой в этой главе, является разработка архитектуры системы контролируемого приближенного выполнения сценариев анализа данных. Система принимает пользовательский запрос и ограничения на еговыполнения, оптимизирует и исполняет на вычислителях. На рисунке 5.3 отражена архитектура системы в окружении внешних модулей, составляющихконтекст. Контекст системы включает в себя разнородные источники данных;различные, возможно распределенные, вычислители; и модуль в котором пользователь специфицирует конкретный сценарий-запрос на анализ данных.В этом разделе приведена серия примеров аналитических сценариев, иллюстрирующих задачи, которые необходимо решать внутри системы выполненияи оптимизации запросов в целевом контексте.1155.1.1. Нечеткие запросыПервый пример запроса к системе основан на анализе данных из коллекции OpinRank.
Коллекция содержит описания отелей в 10 городах мира. Длякаждого отеля в коллекции хранится название, адрес и оценки по чистоте, дизайну и качеству обслуживания.Рассмотрим следующий запрос: найти 10 лучших отелей в Лондоне наоснове оценок по качеству обслуживания и чистоте. Запрос формулируется втерминах высокоуровневого декларативного языка запросов, подобного предложенному в [13], а затем транслируется в выражение в терминах алгебраическихопераций (исходный план выполнения запроса), как показано на рисунке 5.1а.Отметим, что в данном запросе декларативно специфицируется сценарийобработки данных, включающий в себя анализ данных из различных источников. Таким образом, архитектура системы должна опираться на единый декларативный язык, позволяющий сочетать в одном запросе разные типы анализаразнородных данных.Операции первичной выборки извлекают из информационных ресурсовотели с оценками определенного типа.
Последующие операции выбора лучшихприменяются для сокращения количества объектов для дальнейшего анализа.Следующая операция, обогащающий фильтр, расширяет объект представляющий отель атрибутом хранящим цену за двухместный номер на заданную дату.Фильтр по городу сохраняет в анализируемых данных только отели в Лондоне.Операция синтеза (теоретико-множественная) строит агрегированные оценкиотелей на основе исходных. Наконец, последняя операций выбора лучших применяется для получения только 10 лучших отелей на основе новых агрегированных оценок.Отметим, что в этом запросе есть несколько возможностей для оптимизации.
Например, мы можем поменять местами унарные операции. Система такжеможет использовать совместную эффективную реализацию операции синтеза ивыбора лучших объектов [61]. Фильтрация отелей по адресу на уровне первичной выборки также может оказаться более эффективной.
Таким образом, в системе, во-первых, должна решаться задача поиска эффективного плана выполнения запроса; во-вторых, должна быть реализована возможность интеграции всистему новых операций, алгоритмов и исполнителей, без которых невозможныэффективные вычисления. Рисунок 5.1б демонстрирует альтернативный план116а Пример плана выполнения за- б Альтернативный план выпол- в План выполнения запроса допросанения запросапускающий приближенное выполнениеРис. 5.1. Пример сценария анализа данныхвыполнения исходного запроса (не обязательно оптимальный).Поскольку мы говорим приближенном анализе данных, система должнареализовывать эту возможность и решать связанные с этим задачи; например,решать задачу оптимизации на основе разнородных критериев (время вычислений, качество результата) и распределения доступных вычислительных ресурсов между исполнителями.Как уже говорилось, качество результата исполнения запроса зависит отколичества вычислительных ресурсов (времени), выделенного пользователем.Рисунок 5.1в показывает план выполнения запроса, в котором операции, допускающие приближенное выполнение, отмечены пунктирными границами.Таким образом, как только на этапе оптимизации запроса будет построендостаточно хороший план, система должна распределить фиксированное количество ресурсов, заданных пользователем, между операциями в плане.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
