Содержание к диссертации
Введение
1. Оптимизация и выполнение декларативных сценариев обработки данных 17
1.1 Выполнение точных запросов 17
1.1.1 Языки запросов 18
1.1.2 Оптимизация запросов 19
1.1.3 Многокритериальная оптимизация 21
1.1.4 Параметрическая оптимизация 23
1.2 Нечеткие запросы и приближенное выполнение 24
1.2.1 Языки запросов 24
1.2.2 Приближенное выполнение
1.2.2.1 Понятие качества 29
1.2.2.2 Приближенное выполнение запросов 30
1.2.2.3 Приближенное выполнение операций 30
1.2.3 Оптимизация запросов в расширенных алгебрах 31
1.2.3.1 Алгебраические тождества з
1.2.3.2 Модели стоимости 33
1.3 Адаптивное выполнение запросов 34
1.3.1 Методы адаптивного выполнения запросов 34
1.3.1.1 Потоковое выполнение запросов 36
1.3.1.2 Промежуточная материализация 37
1.3.2 Адаптивные алгоритмы выполнения операций 38
1.4 Системы 39
1.4.1 Распределенные вычисления 39
1.4.1.1 Языки 40
1.4.1.2 Оптимизация 41
1.4.2 Приближенные вычисления 45
1.5 Основные результаты 45
2. Основные понятия 46
2.1 Декларативные языки и расширенная алгебра 46
2.1.1 Функция оценки 47
2.1.2 Множество объектов 49
2.1.3 Q-множества 50
2.1.4 Алгебраические операции
2.1.4.1 Первичная выборка 51
2.1.4.2 Фильтры 52
2.1.4.3 Теоретико-множественные операции 52
2.1.4.4 Соединение 54
2.1.4.5 Агрегирование 54
2.1.4.6 Группирующее соединение
2.1.5 Алгебры 56
2.1.6 Исполнение алгебраических операций 56
2.2 Оптимизация запросов 57
2.2.1 Выражения 57
2.2.2 Алгебраические тождества 58
2.2.3 Запрос и план его выполнения 58
2.2.4 Конфигурация 59
2.2.5 Функция стоимости 59
2.2.6 Модель стоимости 61
2.3 Задачи оптимизации запросов 63
2.3.1 Задача однокритериальной оптимизации 64
2.3.2 Задача многокритериальной оптимизации 64
2.3.3 Задача параметрической оптимизации 64
2.4 Приближенное выполнение 65
2.4.1 Приближенные алгоритмы 65
2.4.2 Вычислительные ресурсы 66
2.4.3 Качество 67
2.4.4 Модель качества 69
2.5 Оптимизация запросов, допускающих приближенное выполнение 70
2.5.1 Задача распределения ресурсов 70
2.5.2 Задача бикритериальной оптимизации 71
2.5.3 Параметрическая задача оптимизации 71
2.5.4 Связь задач 72
2.5.5 Задача оптимизации при ограничениях 72
2.6 Основные результаты 73
3. Распределение ресурсов в плане выполнения запроса 74
3.1 Мотивирующий пример 74
3.2 Вычислительная модель
3.2.1 Дерево плана 76
3.2.2 Качество 77
3.2.3 Уточнение постановки задачи 79
3.2.4 Предположения о функциях качества 80
3.3 Условия оптимальности 81
3.3.1 Критическое поддерево 82
3.3.2 Распределение ресурсов вдоль пути 83
3.3.3 Распределение ресурсов между братьями 86
3.4 Алгоритм распределения ресурсов 87
3.4.1 Алгоритм и структуры данных 87
3.4.2 Горизонтальная гипер-вершина 90
3.4.3 Вертикальная гипер-вершина 91
3.4.4 Вычислительная сложность
3.5 Эксперименты 94
3.6 Основные результаты 97
4. Оптимизация приближенного выполнения запросов 98
4.1 Предварительные рассуждения 98
4.2 Модель: составной сегмент 101
4.3 Алгоритмы
4.3.1 Модель качества плана 102
4.3.2 Доминанта составных сегментов 103
4.3.3 Перечислители: Обход пространства планов
4.3.3.1 Итеративное улучшение 104
4.3.3.2 Рекурсивное построение 104
4.3.4 Сжатие составного сегмента 105
4.4 Эксперименты 105
4.4.1 Нетривиальный оптимальный составной сегмент 106
4.4.2 Итеративное улучшение и рекурсивный спуск 108
4.4.3 Производительность алгоритмов 110
4.4.4 Качество алгоритмов 112
4.5 Основные результаты 112
5. Архитектура системы выполнения запросов 114
5.1 Примеры использования системы 114
5.1.1 Нечеткие запросы 115
5.1.2 Анализ неоднородных данных 117
5.1.3 Извлечение данных
5.2 Основные требования 119
5.3 Архитектура
5.3.1 Окружение системы 120
5.3.2 Оптимизация и исполнение запросов
5.3.2.1 Построение первичного плана 122
5.3.2.2 Оптимизация
5.3.2.2.1 Оптимизация и распределение ресурсов 124
5.3.2.2.2 Оптимизация через построение оптимального составного сегмента 126
5.3.2.3 Исполнение 126
5.4 Расширение системы 127
5.4.1 Трансформации 127
5.4.2 Модели стоимости 128
5.4.3 Модели качества 128
5.4.4 Операции
5.4.4.1 Библиотека операций 130
5.4.4.2 Операции первичной выборки 131
5.4.4.3 Унарные операции 132
5.4.4.4 Бинарные операции 133
5.5 Основные результаты 135
Заключение 136
Библиография
- Адаптивное выполнение запросов
- Оптимизация запросов, допускающих приближенное выполнение
- Условия оптимальности
- Нетривиальный оптимальный составной сегмент
Введение к работе
Актуальность темы исследования. Проблема эффективного анализа больших объемов данных остается актуальной на протяжении десятилетий. В последнее время в связи с ростом объема доступных данных и появлением новых источников информации, например, социальных сетей и сенсоров, эта проблема обострилась. В тоже время возможности обработки данных развиваются медленнее: это относится как к техническим возможностям оборудования и алгоритмам анализа данных, так и к средствам спецификации и программной реализации необходимых вычислений.
Многие исследования в области анализа данных концентрируются вокруг понятия больших данных (big data), которое со временем вобрало в себя широкий спектр значений: большие объемы данных, их разнообразие и качество, а также необходимость их своевременной обработки. В литературе представлено множество примеров систем анализа больших данных: SCOPE, Asterix, Hive.
Разнообразие больших данных связано с множеством типов данных, одновременно задействованных в сложном аналитическом сценарии. Информационные ресурсы, различающиеся по типу хранимых данных и характеру доступа к ним, могут быть использованы в одном процессе обработки данных. Системы анализа данных могут быть неоднородны с точки зрения модели, динамики, надежности и типа данных, а также по типу запросов на их извлечение и анализ. Необходимость совместного анализа данных, извлеченных из разнородных источников, появляется во многих приложениях и прикладных областях, в том числе при расширенном поиске, персонализации и аналитической обработке.
Высокоуровневые декларативные языки являются эффективным инструментом описания сложных аналитических сценариев, поскольку они позволяют скрыть сложность работы в неоднородной среде и организации параллельных вычислений. Системы, интегрирующие в себе разные подходы к анализу данных, как правило, используют промежуточные алгебраические языки, которые в дополнение к базовой выразительности традиционных декларативных языков запросов включают в себя их нечеткие расширения и специализированные операции для определенных классов задач: например, средства анализа естественных языков или изображений.
Скорость генерации и накопления данных, например в социальных сетях и разнообразными сенсорами, ведет к стремительному увеличению объемов анализируемых данных. Это приводит к необходимости решения вопросов, связанных со скоростью анализа. Необходимость увеличения скорости анализа больших объемов данных требует проработки на всех уровнях от аппаратного до языкового, в частности высокая эффективность может быть достигнута использованием декларативных языков запросов.
При решении задачи современного анализа данных возникает необходимость в приближенном выполнении запросов, поскольку все чаще точные вычисления невозможны или бессмысленны. Растущий спрос на обработку боль-
ших объемов данных за ограниченное время, а также современные методы анализа данных на основе подобия вызывают необходимость в приближенных вычислениях. Например, системы Blinkdb, Sciborq поддерживают приближенное параллельное выполнение запросов в реальном времени, предоставляя пользователю статистические гарантии качества неточного результата.
Значительная часть элементов традиционной архитектуры систем выполнения декларативных запросов, включая компиляцию в промежуточный алгебраический язык, оптимизацию и интерпретацию алгебраического выражения, требует пересмотра в контексте новых моделей данных, классов систем хранения и доступа, и вычислительных архитектур.
Таким образом, современные проблемы анализа больших данных требуют создания методов и средств, обеспечивающих реализацию систем, которые позволят единообразно формулировать запросы к разнородным данным и описывать их обработку; реализуют эффективное выполнение сложных сценариев анализа данных на основе их оптимизации; и будут поддерживать приближенное выполнение запросов в реальном времени, то есть будут обеспечивать предсказуемое и контролируемое время ответа на запрос.
Целью исследования являлась разработка методов оптимизации для приближенного выполнения сценариев нечеткого анализа данных.
Для достижения цели были поставлены и решены следующие задачи:
Разработать систему понятий и теоретическую модель оптимизации и контролируемого приближенного выполнения нечетких запросов;
Разработать методы решения задачи распределения ограниченного количества вычислительных ресурсов среди операций в плане приближенного выполнения запроса;
Предложить методы решения задачи многокритериальной оптимизации запросов, допускающих приближенное выполнение, ориентированные на специфические ограничения на количество вычислительных ресурсов и качество ответа.
Положения, выносимые на защиту:
Предложена система понятий, составляющих теоретическую модель, формализующую оптимизацию и контролируемое приближенное выполнение декларативных запросов, на основе модели стоимости и качества операций;
Разработана математическая модель распределения ресурсов среди операций в плане выполнения запроса и решена задача выбора оптимального распределения;
Разработан приближенный алгоритм распределения ограниченного количества вычислительных ресурсов среди операций в плане выполнения запроса на основе моделей качества;
Разработаны алгоритмы бикритериальной оптимизации запросов, ориентированные на специфические в контексте приближенного выполнения, ограничения на количество вычислительных ресурсов и качество ответа.
Методология и методы исследования. Объектом исследования являлась совокупность моделей, методов, инструментов оптимизации и приближенного выполнения сценариев анализа данных. Предметом исследования являлись задачи распределения ресурсов и бикритериальной оптимизации запросов, допускающих контролируемое приближенное выполнение. Методология работы основана на обобщении, индукции и дедукции, математическом моделировании, анализе и синтезе теоретического и практического материала. В работе использовались методы исследования операций; методы теории баз данных; методы теории алгоритмов; принципы построения архитектур программных систем; практика программной инженерии.
Степень разработанности темы. Следующие аспекты темы были проработаны исследовательским сообществом к моменту начала работы над темой диссертации. Алгоритмы контролируемого приближенного выполнения отдельных задач анализа данных и ограниченных классов запросов описаны во многих статьях. Методы оптимизации для точного выполнения запросов проработаны в классической теории баз данных. Модели стоимости реляционных операций используются в оптимизаторах запросов современных СУБД. Концепции качества данных исследованы главным образом для структурированных данных. Задачи многокритериальной и параметрической оптимизации исследованы в контексте точного выполнения запросов. Архитектуры, существующих систем оптимизации и приближенного исполнения сценариев анализа данных, поддерживают работу с ограниченными классами запросов и методов приближенного выполнения.
Научная новизна. Возможности контролируемого приближенного выполнения запросов в системах анализа данных проработаны нами для сценариев общего вида. В контексте приближенного выполнения запросов возникает ряд новых задач оптимизации, которые были решены в этой работе.
Расширенная модель стоимости операций, предложенная в работе, формализует связь между количеством вычислительных ресурсов и качеством результата приближенных вычислений и лежит в основе последующей оптимизации запросов, допускающих приближенное выполнение.
В работе поставлена и решена задача распределения ограниченного количества вычислительных ресурсов между операциями в плане приближенного выполнения сложного сценария анализа данных.
Разработано решение специфической бикритериальной задачи оптимизации запросов, допускающих приближенное выполнение, основанное на компактном представлении зависимости оптимального плана от ограничений на исполнение.
В рамках исследования разработана архитектура системы, которая реали-
зует исполнение сложных сценариев анализа данных при ограничениях на вычислительные ресурсы, отличительной чертой которой является ее расширяемость: алгоритмы и модели не привязаны к конкретным парадигмам анализа данных и специфическим неоднородным распределенным архитектурам.
Теоретическая и практическая значимость работы. Теоретическою ценность для дальнейших исследований представляют обзор и классификация методов и систем оптимизации и приближенного выполнения сценариев анализа данных, алгоритм распределения ресурсов на основе точного теоретического решения задачи и подход к бикритериальной оптимизации запросов, допускающих приближенное исполнение.
Разработанная теоретическая модель и предложенная архитектура системы оптимизации и приближенного выполнения запросов может быть использована для расширения систем анализа данных возможностью контролируемого учета ограничений на вычислительные ресурсы и качество результата. Это позволяет реагировать на потребность аналитиков в своевременном получении результата и в работе в реальном времени.
Разработанные теоретические модели, алгоритмы и экспериментальная среда могут быть использованы для прототипирования прикладных систем анализа больших данных в различных предметных областях, например, при финансовом мониторинге, социологическом и экономическом анализе.
Достоверность и обоснованность результатов работы подтверждается использованием строгого математического аппарата, доказательствами лемм, подтверждением теоретических положений вычислительными экспериментами.
Апробация работы. Материалы работы докладывались и обсуждались на всероссийских и международных конференциях:
15-ая Восточно-европейская конференция "Advances in Databases and Information Systems"(20-23 сентября 2011 г., Вена, Австрия)
Семинар аспирантов в рамках 16-й Восточно-европейской конференции "Advances in Databases and Information Systems"(17-20 сентября 2012 г., Познань, Польша)
16-ая Восточно-европейская конференция "Advances in Databases and Information Systems"(17-20 сентября 2012 г., Познань, Польша)
10-ый Коллоквиум молодых исследователей "Spring Researchers Colloquium on Databases and Information Systems"(30-31 мая 2014 г., Великий Новгород, Россия)
19-ая Восточно-европейская конференция "Advances in Databases and Information Systems"(9-11 сентября 2015 г., Пуатье, Франция)
Полученные результаты прошли апробацию на научном семинаре «Проблемы современных информационно-вычислительных систем» под руководством д. ф.-м. н., проф. В. А. Васенина (25 ноября 2014 года), на семинаре Москов-
ской Секции ACM SIGMOD (26 февраля 2015 года), а также неоднократно на семинарах группы исследования методов организации информации и кафедры информационно-аналитических систем в Санкт-Петербургском Государственном Университете.
Публикации. Все результаты диссертации опубликованы в 9 научных работах [1-8,10] и одном переводе [9]. Из них: 1 публикация [1] представлена в журнале, входящем в утвержденный приказом Минобрнауки России от 25 июля 2014 г. №793 перечень рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук; 3 статьи [2,3,9] есть в индексах Web of Science и 8 работ [2-9] опубликованы в рецензируемых зарубежных изданиях, включенных в индекс Scopus.
Все исследования, результаты которых изложены в диссертационной работе, проведены лично автором в процессе научной деятельности. Из совместных публикаций в результаты диссертационной работы включен лишь тот материал, который непосредственно принадлежит автору.
В статьях [2,3] А.С. Ярыгиной принадлежит анализ литературы, доказательство лемм, идея и реализация алгоритма, проведение вычислительных экспериментов. В статье [4] А.С. Ярыгиной принадлежит сведение общей задачи оптимизации к бикритериальной и параметрической, разработка алгоритма, проведение вычислительных экспериментов. В работе [5] Ярыгиной принадлежит детальная проработка архитектуры системы анализа данных. Б.А. Новикову в работах [2,3,4,5,7] принадлежат общие постановки задач и обоснование их актуальности, формальная модель качества. А.С. Ярыгиной в статье [6] принадлежит проработка алгебраических свойств операций и соотношений между ними; Б.А. Новикову принадлежит концептуальная модель исполнителя декларативных сценариев; Н.С. Васильевой обоснование актуальности задачи в контексте анализа больших данных. В работе [7] А.С. Ярыгиной принадлежит разработка расширенных моделей стоимости и качества для ряда операций; О.А. Долматовой принадлежит реализация моделей и проведение экспериментальной оценки. А.С. Ярыгиной в статье [10] принадлежит общая постановка задачи оптимизации запросов; Б.А. Новикову принадлежит позиционирование задачи в контексте методов исследования операций. В статье [8] А.С. Ярыгиной принадлежит сравнительный анализ методов синтеза и нормализации, реализация алгоритмов, проведение вычислительных экспериментов; Б.А. Новикову принадлежит общая постановка задачи и обоснование ее актуальности, алгебраическая систематизация методов синтеза; Н.С. Васильевой принадлежит реализация методов вычисления оценок подобия изображений.
Структура и объем диссертации. Диссертационная работа состоит из введения, 5 глав, заключения и списка литературы. Общий объем диссертации - 149 страниц. Список литературы содержит 100 названий. Рисунки и таблицы нумеруются по главам.
Адаптивное выполнение запросов
Задача многокритериальной оптимизации запросов рассматривается в [36-39]: среди множества планов выполнения запроса ищутся те, которые минимизирует значение функции стоимости, вычисленной на основе совокупности критериев, таких как время выполнения запроса, денежные затраты, потеря качества в результате.
Задача оптимизации классических SPJ запросов в контексте параллельных вычислений рассматривается в [40]. В работе сформулирована задача оптимизации запроса, в которой строится план оптимизирующий время выполнения запроса при условии ограничений на пропускную способность и производительность. В такой постановке задачи оптимизации не выполняется принцип оптимальности, согласно которому, если два плана отличаются только двумя подпланами, то ниже стоимость того, у которого ниже стоимость подплана. Принцип оптимальности, существенный для алгоритмов оптимизации запросов на основе динамического программирования, не выполняется также и во многих задачах многокритериальной оптимизации запросов.
Авторы [36] предложили два приближенных алгоритма решения задачи многокритериальной оптимизации основанных на принципе приближенной оптимальности, провели анализ их сложности и экспериментально сравнили с точным алгоритмом, основанным на предложенном в [40]. В работе [36] задача оптимизации определяется вектором критериев; функцией стоимости, вычисляемой как взвешенная сумма от значений критериев; и множеством ограничений на значения критериев оптимизации. Множество запросов, рассмотренных в работе, определяется запросами, описываемыми множеством соединяемых таблиц, то есть план выполнения запроса определятся порядком выполнения соединений и алгоритмами вычисления соединений и сканирования таблиц. Предложенные приближенные алгоритмы позволяют строить приближенное решение задачи многокритериальной оптимизации с гарантированным качеством, выбираемым извне. В реализованном прототипе рассмотрены следующие критерии: загрузка ввода-вывода, загрузка процессора, число используемых ядер, загрузка жесткого диска, загрузка буфера, потребление энергии и ошибка кортежей.
В статье [38] представлена среда для параллельного приближенного выполнения запросов на основе случайных выборок. Разработанная система поддерживает приближенное выполнение SPJA запросов в реальном времени, предоставляя статистические гарантии качества результата. В [38] предложено решение специфической задачи многокритериальной оптимизации запросов по времени выполнения и качеству результата: на первом этапе выбирается оптимальное множество выборок из таблиц, затем строится оптимальная последовательность соединений.
В работах, лежащих в основе этого диссертационного исследования, [16, 17, 19] также рассматривается специфическая задача бикритериальной оптимизации по качеству приближенного результата и количеству вычислительных ресурсов. В отличие от методов, описанных в [38], в этих работах рассматривается более широкий класс сценариев анализа данных и учитываются средства приближенных вычислений, не ограничивающиеся использованием случайных выборок.
Авторы [37] решают специфическую задачу многокритериальной оптимизации, строя аддитивную метрику полезности запроса на основе комбинации стоимости и покрытия запроса. Задача оптимизации запросов по времени вычислений и потребляемой энергии рассмотрена в [39]: в предложенном подходе оптимизируется агрегированная стоимость запроса, вычисленная на основе этих критериев. В работах [37-39] рассмотрена задача многокритериальной оптимизации решается для специфической комбинации критериев, для которой выполняется принцип оптимальности.
В статье [41] разделены задача оптимизации порядка выполнения соединений и многокритериальная оптимизация: на первом этапе строится оптимальное по времени вычислений дерево соединений, а затем операторы соединения назначаются вычислителям, оптимизируя остальные критерии в предположении, что построенный порядок соединения оптимален для всех критериев.
Похожая идея была использована наших работах [16,17,19]: сначала строится план выполнения запроса в предположении о возможности точных вычислений; а затем решается задача распределения фиксированного количества вычислительных ресурсов, с тем, чтобы учесть ограничения на приближенное выполнение.
Авторы [42] предложили алгоритмы оптимизации распределения операторов запроса между параллельными вычислителями, но не решают задачу оптимизации дерева выполнения запроса.
Многокритериальная оптимизация сценариев обработки данных, отличных от традиционных реляционных запросов, рассмотрена в [43,44].
Задача параметрической оптимизации запросов, рассмотренная в [45] состоит в том, чтобы построить в момент оптимизации такое множество планов, в котором для всех возможных значений параметров запроса имеется хотя бы один оптимальный план, который выбирается в момент выполнения запроса. Авторы предлагают подход к решению задачи параметрической оптимизации запросов, основанный на последовательном фиксировании значений неизвестных параметров и решении классической задачи оптимизации.
В статье [46] предложено решение задачи параметрической оптимизации в случае, если функция стоимости линейно или кусочно-линейно зависит от значений параметров, неизвестных на этапе оптимизации, таких как селективность предикатов и объемы доступной памяти. Предложенные алгоритмы работают с функциями стоимости, а не их скалярными значениями на этапе построения оптимального плана снизу вверх.
Обобщенный подход к многокритериальной параметрической оптимизации SPJ запросов предложен в [47]. Пространство параметров может быть разделе 24 но на регионы Парето, каждому из которых соответствует доминирующий план исполнения запроса. Родовой алгоритм, предложенный в [47], основан на динамическом программировании: оптимальный план строится на основе своих под-планов. Каждому (под)плану ставится в соответствие регион его релевантности в пространстве параметров, который постепенно сужается по мере сопоставления (под)плана с эквивалентными. Планы с пустыми регионами релевантности исключаются из дальнейшего рассмотрения. Если все функции стоимости кусочно-линейны, то регионы релевантности представляют собой многогранники.
Оптимизация запросов, допускающих приближенное выполнение
Построение алгебры начнем с формального определения базовых понятий. При построении системы исполнения сложных аналитических сценариев необходимо определить, как будут сопоставляться объекты с запросами и друг с другом. Начнем с определения расстояния между парой объектов некоторого множества и воспользуемся базовым определением метрического пространства.
Таким образом над множеством объектов можно определить функцию расстояния, которая будет отражать соотношение между объектами этого множества.
Представленная далее модель использует понятие подобия в качестве основного инструмента, подходящего для сопоставления объектов с запросами и друг с другом. Определение Из определения функции подобия следует, что она обратная по смыслу функции расстояния, и принимает большие значения для более близких объектов.
Функции подобия и расстояния тесно связаны, то есть объекты считаются подобными, если расстояние между ними невелико в определенной метрике. Понятия подобия и расстояния являются проверенным инструментом и основой для многочисленных методов анализа данных. Например, близкие объекты в терминах некоторой функции расстояния кластеризуются вместе. В задачах информационного поиска ранжирование объектов происходит на основе значений функции подобия в пространстве документов между объектом представляющим запрос и объектами-документами (поисковыми образами документов). Таким образом, методы анализа данных на основе подобия зависят от определения функции расстояния или функции подобия, которые являются приближением к семантике конкретной предметной области и задачи.
В случае поиска по образцу запрос представлен объектом в анализируемом пространстве, но понятие подобия переносится и на более широкий класс запросов. В этом случае функция подобия определяется следующим образом:
Определение 2.3. Абстрактной функцией подобия для множества запросов Q и множества объектов X называется S : X х Q — К. такую, что если (X, d) - метрическое пространство, на нем определена функция подобия s, Q = X, то S = s.
В этом определении релевантность объекта запросу выражается оценкой, вычисленной как значение функции подобия между объектом и запросом. Теперь, когда функция подобия определена между запросами и объектами, она также может представлять, например, точные запросы в традиционных базах данных. Отметим, что представленном выше определении множество запросов не специфицировано и может нести различную семантику, например, через абстрактную функцию подобия может быть выражено определение нечеткого множества, где значения функции подобия определяют степень принадлежности объекта множеству. В нашей модели мы требуем, чтобы все значения функции подобия лежали в интервале [0,1], в частности, подразумевая, что они могут быть рассмотрены как вероятности релевантности объекта запросу.
Определение 2.4. Для множества запросов Q и множества объектов X абстрактная функция подобия S : X х Q — [0,1] называется функцией оценки.
Из определения видно, что функция оценки, с которой мы будем работать, по своей семантике совпадает с функцией подобия и отличается от нее лишь областью значений.
Функции подобия позволяют работать с некоторыми объектами, поэтому формализуем и уточним понятие анализируемого объекта:
Определение 2.5. Любой объект из множества X определяется парой (id, А), в которой id - идентификатор объекта, А - множество атрибутов объекта.
Иными словами анализируемый объект определяется своим идентификатором и множеством атрибутов, на основе которых происходит его обработка.
Отметим, что не происходит строгой типизации объектов по набору и типу атрибутов. Несмотря на тот факт, что требования к структуре объектов минимальны, некоторые свойства и атрибуты объекта, в конечном счете необходимы для исполнения любого запроса.
Мы требуем от всех объектов идентифицируемости ( [95-97]). Предполагается, что объект, полученный из первичного источника, может быть извлечен на основе его идентификатора. Природа идентификатора может варьироваться от простого URL до суррогатных значений и зависеть от объекта, что делает его неизменным. Ожидается, что идентификаторы объектов согласованы между источниками данных, то есть, если объект может быть получен из различных первичных источников, ожидается, что он имеет тот же идентификатор, и объекты с разными идентификаторами различны.
Исполнение запроса и даже его спецификация требуют определенного знания мета-информации, связанной с анализируемыми или запрашиваемыми объектами. Как правило, эта информация доступна в некоторой схеме, которой принадлежат объекты. Тем не менее, было бы нереальным предполагать существование глобального определения данных для всех возможных запросов, задач и предметных областей.
Вопросы, связанные с представлением или отображением локальных схем в глобальную или наоборот ( [98-100]), остаются вне рамок этой работы. Вместо этого, мы предполагаем, что внешний источник может предоставить информацию о свойствах данных, и объекты анализируемые в сценарии, обладают всеми необходимыми для исполнения запроса атрибутами.
Понятие Q-множества инкапсулирует запрос и результат его исполнения, представленный в виде функции оценки. Понятие Q-множества можно рассматривать как обобщение наборов результатов, используемых во многих интерфейсах доступа к данным, таких как JDBC или ODBC. Q-множество также можно рассматривать как нечеткое множество, интерпретируя функцию оценки как функцию принадлежности объекта множеству.
Подчеркнем, что в нашей модели нет никаких предположений о представлении запроса. В частности, мы не предполагаем, что запрос сформулирован на конкретном языке запросов и даже имеет какую-либо явную спецификацию. Таким образом, запросы разных Q-множеств могут быть специфицированы на разных языках, таких как исходный декларативный язык, SQL или язык поисковых запросов, что позволяет выполнять алгебраические операции, комбинируя разные типы анализа данных в одном сценарии.
Заметим, что множество X может содержать объекты, атрибутами которых являются Q-множества.
Существует два способа получить Q-множество: Q-множество извлекается из первичного источника данных или получается в результате исполнения некоторой операции (или выражения из нескольких операций) алгебры, определенной над множеством Q ниже в подразделе 2.1.4. Q-множества, извлекаемые из первичных источников, могут быть рассмотрены как обобщение хранимых таблиц в традиционных СУБД.
Условия оптимальности
Проиллюстрируем задачу распределения ресурсов на примере плана исполнения запроса, который выявляет продукты компании с наименьшим рейтингом, на основе оценок нескольких розничных магазинов.
Идея запроса состоит в том, чтобы найти продукты с низким рейтингом, с тем, чтобы в дальнейшем их анализировать. На первый взгляд, ответ на этот запрос может быть получен на основе информации от одного магазина. Однако, чтобы сделать результаты более надежными, мы могли бы объединить информацию от нескольких магазинов.
План выполнения запроса включает в себя операции первичной выборки данных из различных источников, последующее соединение по названию продукта с тем, чтобы построить агрегированный рейтинг, и сортировку:
Распределение ресурсов в плане выполнения запроса-примера ных из обоих источников и заняло много времени. Скорее всего, это не имеет смысла, поскольку аналитик заинтересован в выборе лишь нескольких продуктов, которые требуют дальнейшего детального анализа. Следовательно, выборка данных из источников должна быть ограничена. В этом случае запрос будет выполнен приближенно, поскольку оценки некоторых объектов не будут учтены, что повлияет на качество конечного ответа на запрос. Отметим, что в этом примере, качество приближенного ответа может быть оценено как доля правильно возвращенных объектов в результате выполнения запроса.
Предположим, что источники данных возвращают в операцию выборки объекты со средней скоростью 300 и 500 объектов в секунду, соответственно. Предположим также, что пользователь ожидает ответа через 200 миллисекунд и лучший возможный (неизвестный) ответ на запрос содержит 50 объектов.
Доступное ограниченное количество вычислительных ресурсов (200 миллисекунд в этом примере) может быть распределено между операциями в плане различными способами, влияя на качество результата. Две возможные стратегии распределения ресурсов между операциями в нашем плане проиллюстрированы на рисунке 3.1.
Рассмотрим стратегию распределения ресурсов, в которой выборка из первого источника данных использует 150 мс и возвращает 45 объектов, выборка из второго источника занимает 30 мс и извлекает 15 объектов, а остальные 20 мс необходимы для исполнения операций соединения и сортировки (рисунок 3.1а). Конечный результат вычислений будет содержать не более 15 объектов и, следовательно, оценка качества не может превышать 30%.
Гораздо лучшие результаты могут быть получены, если выборка из первого источника данных будет использовать 100 мс, из второго - 60 мс, в результате чего 40 мс будут выделены последующим операциям (рисунок 3.16). Оба источника данных вернут за выделенное время 30 объектов и качество результата может достигнуть 60%.
Приведенный пример показывает, что не имеет смысла ограничивать некоторые операции (используя приближенные алгоритмы), оставляя точными другие, так как качество результата будет сильно зависеть от операций с наименьшим качеством. Другими словами, распределение ограниченного количества ресурсов между операциями должно быть сбалансировано.
План выполнения запроса может быть представлен деревом, в котором вершины представляют операции, а ребра соединяют операции с их аргументами в выражении плана.
Определение 3.1. Деревом плана выполнения запроса є Є Е называется граф Р = (V(P),E(P)): любой о Є О(е) соответствует вершина 10 Є V; если Оі,02 О(е) и о і является аргументом 0\, то ребро є Є Е(Р) связывает соответствующие вершины 101 и 102.
Отметим, что листьями дерева являются операции первичной выборки, информация о источниках данных, из которых они извлекают Q-множества, далее учитывается внутри листьев дерева-плана. В этой главе в дальнейшем мы будем оперировать только с представлением плана выполнения запроса в Рис. 3.2. Пример дерева плана выполнения запроса виде дерева и использовать понятия плана и дерева, вершины и операции взаимозаменяемо.
Введем несколько обозначений, связанных с определением дерева плана. Определение 3.2. Для дерева плана Р и для вершины І Є V(P) args(l) С V(P) — множество вершин-детей; для не корневой операции parent(/) — родительская вершина; I — поддерево с вершиной в I. Отметим, что (под)деревья однозначно соответствуют (под)планам выполнения запроса. Пример дерева плана выполнения запроса показан на рисунке 3.2. Дерево плана Р содержит все вершины-операции: V(Р) = {/о, hi hi hi hi h} , поддерево с корнем в h определяется как h = { 2, 4, 5}; parent(h) = h и args(h) = {hi hi h} 3.2.2. Качество
В главе 2 по определению 2.38 модель качества операции о Є О показывала, как зависит относительное качество выполнения операции при определенных ограничениях на количество вычислительных ресурсов и знании статистик аргументов операции.
В дальнейшем в этой главе мы предполагаем, что незначительные изменения количества вычислительных ресурсов при приближенном выполнении операций не могут существенно изменить статистики Q-множеств обрабатываемых в плане выполнения запроса. Разработанный нами и описанный далее итеративный алгоритм распределения ресурсов будет на каждом шаге пересчитывать статистики, обеспечивая допустимость этого предположения.
Для вершины в дереве плана на основе модели качества соответствующей операции построим функцию качества.
Качество, достигаемое при приближенном выполнении плана, зависит от конфигурации операций, его составляющих, в том числе распределения ограниченного количества доступных вычислительных ресурсов. Определим распределение ресурсов в новых терминах дерева и его вершин. Определение 3.4. Для заданного дерева плана выполнения запроса Р и фиксированного количества вычислительных ресурсов Т Є Dl множество tp = v(p) M T называется распределением ресурсов, ti определяет количество ресурсов, выделяемое! Є V(P). Количество ресурсов, выделенное (под)дереву с корнем el обозначим через Через Тр обозначим множество всех возможных распределений ограниченного количества вычислительных ресурсов Т. В главе 2 относительное качество плана выполнения запроса определялось качеством его операций, что позволяет перейти к понятию функции качества дерева плана. Определение 3.5. Для дерева плана выполнения запроса Р и распределения ресурсов tp Є Тр его качество определяется следующим образом: Qpitp) = F({q(m)(tm)\m Є V(P),tm Є tp}), где F-функция агрегирования качества в плане (по определению 2.24).
Формализуем один из возможных подходов к оценке качества плана, в терминах его представления в виде дерева и функций качества его вершин, то есть определим конкретную реализацию функции F. Качество плана зависит от качества подпланов и свойств корневой операции. Например, качество (под)плана с бинарной корневой операцией т зависит от трех параметров: качества левого и правого подпланов, Qjn Qf соответственно, и качества корневой операции q(m), где /,г Є args(m).
Нетривиальный оптимальный составной сегмент
Предполагается, что запрос от пользователя формулируется на некотором высокоуровневом языке: расширении SQL, аналогичном предложенному в [13], или некотором графическом. Таким образом, клиент строит алгебраическое представление запроса, специфицированного пользователем, и передает в систему. В модельной реализации первичный запрос представляется в виде XML дерева, в котором вершины и атрибуты описывают операции и их параметры.
Архитектура системы анализа данных строится на основе расширяемой алгебры операций над Q-множествами, описанной в главе 2, которая позволяет декларативно специфицировать запросы на обработку данных. Одним из основных требований к системе, определенных в разделе 5.2, является ее расширяемость, которую необходимо учесть в архитектуре. Таким образом, должно быть предусмотрено расширение системы анализа данных новыми операциями или алгоритмами, что не позволяет в реализации жестко ограничить набор операций уже специфицированными.
Во-вторых, предлагаемая архитектура опирается на систему неоднородных, возможно, распределенных вычислительных модулей, в качестве которых могут выступать существующие СУБД, машины map-reduce или другие внешние программы. Система отвечает за оптимизацию и приближенное выполнение запросов на алгебраическом уровне, и передавать непосредственные вычислительные задачи внешним модулям. Таким образом поиск оптимального плана приближенного выполнения запроса происходит централизованно, а непосредственное исполнение может быть распределено между вычислительными модулями. Реализации отдельных операций в системе определяют, как именно может быть вызвано ее выполнение на том или ином внешнем вычислительном модуле.
В-третьих, в системе происходит анализ данных из внешних источников разнородных по типу и методам хранения данных, например, файлов или таблиц СУБД. Неоднородность источников данных на алгебраическом уровне скрывается работой с операциями первичной выборки, которые строят представление данных в едином формате. Таким образом, так же как и в случае работы с внешними вычислительными модулями, протокол работы с внешним источником данных определяется при реализации и регистрации в системе соответствующей алгебраической операции.
Опишем основные процессы, которые происходят на этапе оптимизации запроса, обращая внимания на то, как требования к системе, влияют на них. Как и в традиционных системах оптимизации реляционных запросов оптимизатор анализирует алгебраические свойства операций, например, ассоциа 123 тивность и дистрибутивность. На основе этих свойств перечислитель реализует обход пространства планов выполнения запроса, используя трансформации для перехода от одного плана к другому (определение 2.17 в главе 2).
Архитектура поддерживает расширяемость алгебры и использует оптимизатор, настраиваемый на новые специфические операции алгебры, которые порождают новые алгебраические тождества и расширяют пространство возможных планов выполнения запросов.
Оптимизатор основан на расширяемом и настраиваемом множестве трансформаций планов (алгебраический выражений), которое реализует пространство планов. Важно отметить, что в предложенной архитектуре системы трансформации включают в себя возможные эквивалентные перестроения планов двух типов, неразличимых с точки зрения реализации: основанные на алгебраических тождествах или на различных реализациях одной операции. Такая модель позволяет легко встраивать в систему новые операции, алгоритмы, их реализующие, и соответствующие трансформации.
По сравнению с традиционными реляционными СУБД пространство трансформаций в расширенной алгебре не столь однородно: например, в ней часто используются операции не ассоциативного соединения и сложные трансформации с операцией выбора лучших объектов.
Особое внимание следует обратить на реализацию трансформаций в системе с учетом ее расширяемости: пространство трансформаций не должно быть реализовано глубоко внутри оптимизатора; поэтому в архитектуре системы определены единые интерфейсы, позволяющие легко встраивать новые трансформации в систему.
Для того, чтобы иметь возможность выбрать эффективный план выполнения запроса, оптимизатор основывается на моделях стоимости и качества, определенных для всех операций, в том числе для пользовательских расширений (подразделы 2.2.6 и 2.4.4 в главе 2). Архитектура системы поддерживает включение новых моделей стоимости и качества операций и настройку уже существующих.
Непосредственная оптимизация запроса, допускающего контролируемое приближенное выполнение, может быть построена на основе разных по сложности и качеству ответа моделях.
Во-первых, может быть использована модель, в которой первоначальный план выполнения запроса, сгенерированный парсером, может быть передан непосредственного исполнителю, минуя этап поиска более эффективного эквивалентного. Оптимизация запроса не происходит, но этот подход может быть эффективен в некоторых специфических ситуациях, например, если по запросу пользователя парсер изначально генерирует план приближенного выполнения запроса.
Во-вторых, в системе может быть использован традиционный оптимизатор точного выполнения запроса. Оптимизатор рассматривает только планы точного выполнения запроса и выбирает наиболее эффективный для исполнения. Эта модель, как и предыдущая, в действительности не учитывает возможность приближенного выполнения запроса, но может быть эффективной, в случаях, когда точное выполнение многих простых сценариев анализа данных требует малого количества вычислительных ресурсов.
Третья модель основана на сочетании оптимизатора точного выполнения запроса и модуля распределения ресурсов, описанного в главе 3. Этот подход детально обсуждается в параграфе 5.3.2.2.1 и позволяет непосредственно учитывать ограничения на количество вычислительных ресурсов и строить планы приближенного выполнения запроса.
В пятой модели первоначальный план выполнения запроса, сгенерированный парсером, минуя этап оптимизации, передается модулю распределения ресурсов. Такой подход может быть использован в системах выполнения специфических сценариев анализа данных, для которых пространство эквивалентных планов тривиально, но возможно их контролируемое приближенное исполнение.
Четвертая модель, описанная в параграфе 5.3.2.2.2, основана на построении оптимального составного сегмента запроса (глава 4) и позволяет выбирать более эффективный план приближенного выполнения запроса по сравнению с предыдущими подходами.