Диссертация (1149731), страница 20
Текст из файла (страница 20)
Составной сегмент запроса, который доминирует надвсеми составными сегментами запроса, называется оптимальным.Мы используем оптимальный составной сегмент в качестве компактногопредставления множества Парето в задаче бикритериальной оптимизации.4.3. АлгоритмыВ этом разделе описаны алгоритмы, необходимые для решения поставленной задачи бикритериальной оптимизации через построения оптимальногосоставного сегмента запроса.4.3.1. Модель качества планаДля построения функции качества плана мы используем модификациюполиномиального алгоритма распределения ресурсов, описанного в главе 3. Инкрементальное распределение ресурсов продолжается до тех пор, пока не будетдостигнуто максимальное качество результата выполнения плана: результат работы алгоритма сохраняется в составном сегменте, представляющем функциюкачества.103Поведение алгоритма зависит от двух параметров, влияющих на точностьмодели качества:∙ верхняя граница на количество вычислительных ресурсов, которое может быть распределено на каждом шаге алгоритма.∙ нижняя граница на значение прироста качества операций на каждомшаге.Меньшие значения этих параметров позволяют строить более точные приближения функций качества планов выполнения запроса, но приводят к большим вычислениям.
В наших экспериментах рассматривались бесконечное значение и ∈ {0, 0.02, 0.2}.4.3.2. Доминанта составных сегментовАлгоритмслияния вычисляет доминанту любых двух сегментов. В реа-лизации интервалы сегментов хранятся отсортированными, что позволяет построить доминанту, за один проход по исходным сегментам.Для оценки числа интервалов в результирующем сегменте рассмотримвходные сегменты, содержащие и интервалов соответственно; тогда число пересечений этих интервалов будет не больше + . Если функции качества кусочно-линейны, то каждое пересечение будет порождать не более двухинтервалов, и, следовательно, общее число интервалов в доминанте не будетпревосходить 2( + ).
Таким образом, сложность алгоритма слияния линейнапо числу интервалов в сегментах.4.3.3. Перечислители: Обход пространства плановРассмотрим возможные алгоритмы построения оптимального составногосегмента запроса на основе известных методов оптимизации запросов. Разработанные нами алгоритмы основаны на перечислителе планов выполнения запроса, использующем множество доступных трансформаций.Для каждого плана, сгенерированного перечислителем, строится функциякачества, представленная составным сегментом; далее эти сегменты (итеративно) сливаются в один составной сегмент, который считается оптимальным при104завершении анализа. Этот алгоритм вычислительно сложнее классической оптимизации со скалярной функцией стоимости, поскольку построение моделикачества и слияние составных сегментов требуют больших вычислений по сравнению с оценкой стоимости выполнения плана, и количество планов-кандидатовхранимых в решении больше одного.В экспериментах рассматривалось три основных алгоритма перечисленияполное (full) - полное сканирование пространствапланов, итеративное улучшение (iterative improvement) и рекурсивное построение (recursive descent).
Полное сканирование пространства планов на практикепланов выполнения запроса:неприменимо из-за большой вычислительной сложности, но использовалось вэкспериментах для построения точного решения задачи поиска оптимальногосоставного сегмента запроса и сравнения с другими алгоритмами.4.3.3.1. Итеративное улучшениеАлгоритм итеративного улучшения начинает свою работу со случайногоплана выполнения запроса и его модели качества в качестве исходного составного сегмента. Далее происходит слияние составного сегмента, представляющего решение, с функциями качества планов достижимых из текущего за однутрансформацию. Если новый план выполнения запроса оказался в составномсегменте, представляющем решение, он выбирается в качестве нового текущегоплана и итеративная процедура повторяется.
Планы, не попавшие в результатслияния, исключаются из дальнейшего рассмотрения.4.3.3.2. Рекурсивное построениеАлгоритм рекурсивного построения применяет все возможные трансформации к корневой операции плана выполнения запроса; затем для всех подпланов (и запросов им соответствующих) рекурсивно строятся оптимальные составные сегменты. Планы ассоциированные с оптимальными составными сегментами подзапросов используются для построения оптимальных составныхсегментов запросов, их включающих.Такая процедура позволяет избежать генерации подпланов, которые немогут быть полезны при построении результирующих планов; поэтому она эффективна при работе с алгеброй операций с ограниченным числом алгебраических тождеств.
Однако, эксперименты, представленные в этой главе далее,105показали, что стоимость вычисления функций качества для подпланов можетоказаться очень высокой.4.3.4. Сжатие составного сегментаЧисло интервалов в составном сегменте, построенном операцией слияния,стремительно растет, что ведет к снижению производительности. Для решенияэтой проблемы можно использовать методы сжатия, то есть замены двух соседних интервалов одним, если: у них одна функция качества (FLAT), у ниходин ассоциированный план выполнения запроса (PLAN), или общее увеличение функции качества невелико (SMALL). В экспериментальной части работыоценивалось влияние этих методов на производительность алгоритмов и качество оптимальных составных сегментов.4.4. ЭкспериментыЭкспериментальная часть работы была посвящена проверке существования нетривиальных составных сегментов сценариев анализа данных и сравнению производительности предложенных методов их построения.Для проведения экспериментов генерировались синтетические запросы наоснове фиксированного множества параметризованных операций (алгоритмов):∙ соединения (JOIN) и не ассоциативные соединения (NA-JOIN): извлекаютданные из двух аргументов и генерируют пары в результате;– алгоритм вложенных циклов (NL-JOIN);– алгоритм на основе хеширования (HASH-JOIN);– приближенный алгоритм вложенных циклов на основе случайныхвыборок (A-JOIN);– приближенный алгоритм вложенных циклов на основе приближенной реализации предиката (APRED-JOIN);∙ фильтры: различные операции обрабатывающие объекты по одному(FILTER);106∙ выборки (SELECT): операции извлечения данных из первичных источников (SRC);– точный алгоритм (E-SELECT);– приближенный алгоритм на основе случайных выборок (A-SELECT);Набор правил трансформации включал следующие тождественные преобразования:∙ замена точной выборки приближенной;∙ замена (не ассоциативного) соединения алгоритмом вложенных циклов насоединение на основе хеширования; приближенное соединение на основеслучайных выборок; приближенное соединение на основе приближеннойреализации предиката;∙ ассоциативность соединений;∙ коммутативность (не ассоциативных) соединений;∙ дистрибутивность (не ассоциативных) соединений и фильтров;∙ линейная ассоциативность фильтров.Представленные выше списки алгебраических операций и трансформацийпозволяют моделировать основные черты расширенных декларативных языковописания сценариев анализа данных, которые влияют на алгоритмы оптимизации и приближенного выполнения запросов.4.4.1.
Нетривиальный оптимальный составной сегментОпишем эксперимент, показывающий что от количества выделенных вычислительных ресурсов может зависеть оптимальный план выполнения дажеочень простого запроса. Иными словами, эксперимент позволяет на примерезапроса проиллюстрировать сценарий, показанный на рисунке 4.1. Рассмотримпростой запрос на соединение данных из двух первичных источников, включающий три операции:107[JOIN 100 400][SELECT][SRC 100][SELECT][SRC 400],то есть первичные источники содержат всего 100 и 400 объектов. Здесь и далеев примерах мы будем обозначать количество объектов в первичном источнике данных и селективность операций константами рядом с короткими именамиопераций и алгоритмов.
Размер результата операции соединения будем оценивать через среднее гармоническое размеров источников, участвующих в предикате.При решении классической задачи однокритериальной оптимизации запроса из небольшого пространства планов в качестве оптимального выбираетсяследующий:[HASH-JOIN 100 400][E-SELECT][SRC 100][E-SELECT][SRC 400].В контексте возможного приближенного выполнения запроса пространство планов расширяется выражениями с участием приближенных алгоритмов,реализующих операции, например:[APRED-JOIN 100 400][A-SELECT][SRC 100][E-SELECT][SRC 400]или[HASH-JOIN 100 400][A-SELECT][SRC 100][A-SELECT] [SRC 400].При контролируемом приближенном выполнении запроса различные планы будут оптимальны при разных ограничениях на количество доступных вычислительных ресурсов и ожидаемое качество результата; поэтому мы можемпостроить для этого простого запроса нетривиальный оптимальный составнойсегмент.
На рисунке 4.1б изображены функции качества нескольких планов выполнения запроса, участвующих в оптимальном составном сегменте, то есть впредставлении множества Парето для задачи бикритериальной оптимизации.1084.4.2. Итеративное улучшение и рекурсивный спускСледующим этапом экспериментального анализа алгоритмов построенияоптимальных составных сегментов запросов является оценка их производительности (в терминах времени необходимого на построения решения) и точности(в терминах качества: насколько приближения к оптимальным составным сегментам отличаются от точных).Рассмотрим достаточно простой запрос:[JOIN 1000 4000][SELECT][SRC 1000][JOIN 4000 16000][SELECT][SRC 4000][SELECT][SRC 16000].Эксперименты с ним показали, что:∙ все 3 алгоритма строят оптимальный составной сегмент, представляющийодну и ту же зависимость между качеством результата приближенноговыполнения запроса и ограничением на количество вычислительных ресурсов;∙ план с использованием приближенного алгоритма соединения на основе случайных выборок ассоциирован в оптимальном составном сегментелишь для достаточно небольшого количества доступных вычислительныхресурсов; при осмысленных ограничениях оптимальный план приближенного выполнения запроса основан на приближенных алгоритмах выборкиданных из первичных источников;∙ в отличие от методов полного просмотра и итеративного улучшения, алгоритм рекурсивного построения использует трансформацию ассоциативности при сильных ограничениях на вычислительные ресурсы.В системе оптимизации и выполнения расширенных сценариев анализаданных на основе подобия высокопроизводительные алгоритмы, реализующиеоперацию соединения по точному предикату, могут быть недоступны; поэтомумы в дальнейшем исключаем из рассмотрения алгоритм на основе хеширования.109При проведении эксперимента с тем же запросом в новом окружении длябольшинства возможных ограничений на количество вычислительных ресурсовоптимальными оказались планы с использованием приближенного алгоритмасоединения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
