Диссертация (1149731), страница 5
Текст из файла (страница 5)
Модели стоимости позволяютполучать оценку значения реальной функции стоимости плана выполнения запроса. В обзоре [32] обсуждаются методы построения моделей стоимости операций на основе сбора статистики, и анализируется применимость разных типовгистограмм.При оптимизации запросов на основе моделей стоимости можно выделитьдва основных подхода к поиску оптимального плана [29–31]:∙ Снизу вверх:– Алгоритм динамического программирования;– Жадный алгоритм;– Метод ветвей и границ;∙ Сверху вниз:– Метод случайного поиска;– Генетические алгоритмы.Подход сверху-вниз позволяет сокращать пространство просматриваемыхпланов на основе метода ветвей и границ; но эффективные алгоритмы перечисления планов, как правило ограничены внутренними соединениями и простыми21бинарными предикатами.
В статье [33] предложен алгоритм перечисления планов выполнения запроса сверху-вниз, преодолевающий эти ограничения. Подход основан на том, что гиперграфы запросов разбиваются на простые графы,с тем, чтобы избежать анализа неэффективных разбиений.Важно отметить, что приведенные выше алгоритмы поиска оптимальногоплана можно разделить на точные и приближенные. Необходимость использования приближенных алгоритмов оптимизации запросов обусловлена мощностью пространства планов и бессмысленностью поиска точного решения вконтексте приближенных моделей функции стоимости.Идея генерации оптимизаторов запросов на основе набора трансформацийобсуждалась в ранних работах в этой области [34, 35]: такой подход позволяетстроить оптимизаторы для систем на основе расширенного набора операций итождеств на уровне логической (операции) и физической (алгоритмы) алгебры.1.1.3.
Многокритериальная оптимизацияЗадача многокритериальной оптимизации запросов рассматривается в[36–39]: среди множества планов выполнения запроса ищутся те, которые минимизирует значение функции стоимости, вычисленной на основе совокупностикритериев, таких как время выполнения запроса, денежные затраты, потеря качества в результате.Задача оптимизации классических SPJ запросов в контексте параллельных вычислений рассматривается в [40]. В работе сформулирована задача оптимизации запроса, в которой строится план оптимизирующий время выполнения запроса при условии ограничений на пропускную способность и производительность.
В такой постановке задачи оптимизации не выполняется принципоптимальности, согласно которому, если два плана отличаются только двумяподпланами, то ниже стоимость того, у которого ниже стоимость подплана.Принцип оптимальности, существенный для алгоритмов оптимизации запросовна основе динамического программирования, не выполняется также и во многихзадачах многокритериальной оптимизации запросов.Авторы [36] предложили два приближенных алгоритма решения задачимногокритериальной оптимизации основанных на принципе приближенной оптимальности, провели анализ их сложности и экспериментально сравнили сточным алгоритмом, основанным на предложенном в [40].22В работе [36] задача оптимизации определяется вектором критериев; функцией стоимости, вычисляемой как взвешенная сумма от значений критериев; имножеством ограничений на значения критериев оптимизации.
Множество запросов, рассмотренных в работе, определяется запросами, описываемыми множеством соединяемых таблиц, то есть план выполнения запроса определятсяпорядком выполнения соединений и алгоритмами вычисления соединений и сканирования таблиц. Предложенные приближенные алгоритмы позволяют строить приближенное решение задачи многокритериальной оптимизации с гарантированным качеством, выбираемым извне. В реализованном прототипе рассмотрены следующие критерии: загрузка ввода-вывода, загрузка процессора,число используемых ядер, загрузка жесткого диска, загрузка буфера, потребление энергии и ошибка кортежей.В статье [38] представлена среда для параллельного приближенного выполнения запросов на основе случайных выборок.
Разработанная система поддерживает приближенное выполнение SPJA запросов в реальном времени,предоставляя статистические гарантии качества результата. В [38] предложено решение специфической задачи многокритериальной оптимизации запросовпо времени выполнения и качеству результата: на первом этапе выбираетсяоптимальное множество выборок из таблиц, затем строится оптимальная последовательность соединений.В работах, лежащих в основе этого диссертационного исследования, [16,17, 19] также рассматривается специфическая задача бикритериальной оптимизации по качеству приближенного результата и количеству вычислительныхресурсов. В отличие от методов, описанных в [38], в этих работах рассматривается более широкий класс сценариев анализа данных и учитываются средстваприближенных вычислений, не ограничивающиеся использованием случайныхвыборок.Авторы [37] решают специфическую задачу многокритериальной оптимизации, строя аддитивную метрику полезности запроса на основе комбинациистоимости и покрытия запроса.Задача оптимизации запросов по времени вычислений и потребляемойэнергии рассмотрена в [39]: в предложенном подходе оптимизируется агрегированная стоимость запроса, вычисленная на основе этих критериев.В работах [37–39] рассмотрена задача многокритериальной оптимизации23решается для специфической комбинации критериев, для которой выполняетсяпринцип оптимальности.В статье [41] разделены задача оптимизации порядка выполнения соединений и многокритериальная оптимизация: на первом этапе строится оптимальноепо времени вычислений дерево соединений, а затем операторы соединения назначаются вычислителям, оптимизируя остальные критерии в предположении,что построенный порядок соединения оптимален для всех критериев.Похожая идея была использована наших работах [16, 17, 19]: сначала строится план выполнения запроса в предположении о возможности точных вычислений; а затем решается задача распределения фиксированного количествавычислительных ресурсов, с тем, чтобы учесть ограничения на приближенноевыполнение.Авторы [42] предложили алгоритмы оптимизации распределения операторов запроса между параллельными вычислителями, но не решают задачуоптимизации дерева выполнения запроса.Многокритериальная оптимизация сценариев обработки данных, отличных от традиционных реляционных запросов, рассмотрена в [43, 44].1.1.4.
Параметрическая оптимизацияЗадача параметрической оптимизации запросов, рассмотренная в [45] состоит в том, чтобы построить в момент оптимизации такое множество планов,в котором для всех возможных значений параметров запроса имеется хотя быодин оптимальный план, который выбирается в момент выполнения запроса.Авторы предлагают подход к решению задачи параметрической оптимизациизапросов, основанный на последовательном фиксировании значений неизвестных параметров и решении классической задачи оптимизации.В статье [46] предложено решение задачи параметрической оптимизации вслучае, если функция стоимости линейно или кусочно-линейно зависит от значений параметров, неизвестных на этапе оптимизации, таких как селективностьпредикатов и объемы доступной памяти. Предложенные алгоритмы работаютс функциями стоимости, а не их скалярными значениями на этапе построенияоптимального плана снизу вверх.Обобщенный подход к многокритериальной параметрической оптимизацииSPJ запросов предложен в [47].
Пространство параметров может быть разделе-24но на регионы Парето, каждому из которых соответствует доминирующий планисполнения запроса. Родовой алгоритм, предложенный в [47], основан на динамическом программировании: оптимальный план строится на основе своих подпланов. Каждому (под)плану ставится в соответствие регион его релевантностив пространстве параметров, который постепенно сужается по мере сопоставления (под)плана с эквивалентными. Планы с пустыми регионами релевантности исключаются из дальнейшего рассмотрения. Если все функции стоимостикусочно-линейны, то регионы релевантности представляют собой многогранники.1.2. Нечеткие запросы и приближенное выполнениеРазнообразие типов данных, одновременно обрабатываемых в одном аналитическом сценарии, порождает необходимость расширения декларативныхязыков и требует развития методов выполнения нечетких запросов.Во многих случаях, в частности, при анализе потоков сообщений и данных,получаемых с разнообразных источников в реальном времени, и при решениисложных задач информационного поиска точное выполнение запросов недостижимо и не имеет смысла.Необходимость приближенной обработки потоков, например, возникает изза невозможности хранения и анализа всей истории потока.
В основе приближенного выполнения других запросов часто лежит природа данных и самойзадачи, например при поиске изображений по подобию. Поддержка приближенного выполнения запросов становится актуальной и порождает ряд открытыхвопросов и задач.В этом разделе будет рассмотрен не только класс нечетких запросов, но иметоды приближенного выполнения сценариев анализа данных.1.2.1.
Языки запросовРазнообразие типов обрабатываемых данных требует расширения и пересмотра широко используемых языков описания запросов. Предлагаемые высокоуровневые языки, как правило, являются расширением традиционных языков25реляционного типа и поддерживают новые подходы к анализу данных, например, основанные на подобии и вероятностных моделях, что было продиктованотребованиями современных аналитических задач.Многие обогащения языков запросов основаны на выделении среди множества атрибутов объектов или кортежей оценки или ранга [7–10].На основе расширенной модели данных рассматриваются новые операцииалгебры.
Можно выделить несколько характерных ортогональных классов обогащений:∙ языки, поддерживающие пользовательские веса, определяющие степеньзначимости источника данных или подзапроса [9–11];∙ класс расширений реляционной алгебры [9, 10], основанный на понятиинечетких множеств и фиксированной интерпретации оценок объектов, например, оценка кортежа в системе может отражать степень его принадлежности отношению;∙ специфические алгебры, нацеленные на работу с фиксированным классомданных [12, 13].Возможные методы выполнения запросов к системам с разными парадигмами хранения и обработки данных, например, такими как выборка из традиционного реляционного хранилища и информационный поиск в коллекциидокументов, обсуждались в [7].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
