БАЗЫ ДАННЫХ И ЗНАНИЙ
УДК 681.3.06
МЕТОДЫ ВЫПОЛНЕНИЯ H ОПТИМИЗАЦИИ ПРИБЛИЖЕННЫХ ЗАПРОСОВ В НЕОДНОРОДНЫХ
СИСТЕМАХ
© 2013 г. А. Ярыгина
Санкт-Петербургский Государственный Университет 199034 Санкт-Петербург, Университетская наб., 11 E-mail: anya_safonova@mail.ru Поступила в редакцию 03.04.2013
Высокоуровневые запросы могут использоваться для описания сценариев сложной аналитической обработки в среде распределенных неоднородных информационных ресурсов. Одновременное резкое увеличение объемов и разнообразия типов данных, доступных для массовой обработки в информационных сетях, и ужесточение требований по времени их анализа, привело к необходимости пересмотра известных методов выполнения и оптимизации запросов. В обзоре рассматриваются подходы к выполнению и оптимизации высокоуровневых точных и приближенных запросов; обсуждаются открытые проблемы и возможные направления их решения.
1. ВВЕДЕНИЕ
Проблема эффективной обработки и анализа больших объемов данных в реальном времени остается актуальной на протяжении десятилетий. Около 10 лет назад Gray указывал [1] на то, что объемы хранимых данных значительно превышают возможности их обработки. В последующие годы эта проблема стала значительно острее. С одной стороны, в дополнение к быстрому росту объемов накопленной относительно статической информации, в частности, в Интернет, стремительно возрастают объемы доступной динамической информации, например, в социальных сетях, и потоков данных, генерируемых разнообразными сенсорами. С другой стороны, возможности обработки данных развиваются медленнее. Это относится как к техническим возможностям оборудования и алгоритмам обработки данных, так и к средствам спецификации и программной реализации необходимых вычислений.
Возможный подход к решению проблемы обработки больших объемов данных основан на использовании декларативных языков запросов. Подобные языки используются в традиционных
системах баз данных на протяжении десятилетий. Они обеспечивают не только возможности высокоуровневой спецификации требуемых вычислений, но и высокую эффективность их выполнения, так как открывают широкие возможности для автоматического выбора наиболее эффективных алгоритмов массовой обработки и оптимизации запросов.
Значительная часть элементов традиционной архитектуры обработки декларативных запросов, включая компиляцию в промежуточный алгебраический язык, оптимизацию и интерпретацию алгебраического выражения, требует пересмотра в контексте новых моделей данных, классов систем хранения и доступа, и вычислительных архитектур.
Обзор включает в себя анализ работ исследовательского сообщества, посвященных точному выполнению и оптимизации декларативных запросов в традиционных системах баз данных. В работе рассматриваются существующие подходы к построению и выполнению приближенных запросов. Завершает обзор обсуждение адаптивного выполнения запросов, стратегии, позволяющей естественным образом управлять
неопределенностью в процессе оптимизации и вычислений.
В обзоре, в силу его ограниченности, не освещены такие важные и смежные темы как распределенное выполнение запросов, алгоритмы точного и приближенного выполнения конкретных алгебраических операций и соответствующие модели стоимости, а также вопросы, связанные с качеством данных и точностью ответа на запрос.
2. ВЫПОЛНЕНИЕ ТОЧНЫХ ЗАПРОСОВ
В данном разделе будут обсуждаться реляционные базы данных, ставшие традиционными за последние годы. Лежащая в их основе реляционная алгебра, соответствующий язык запросов, а также методы оптимизации и выполнения запросов стали стартовой точкой в разработке более сложных систем обработки декларативных запросов.
Данный вопрос детально рассматривался в более ранних обзорах, например в [2], тем не менее, анализ существующих методов выполнения и оптимизации точных запросов в данной работе несет не только исторических характер, но и позволяет описать контекст, ввести основные понятия, необходимые для дальнейшего обсуждения.
2.1. Языки запросов
В основе реляционных баз данных лежит реляционная алгебра, представляющая собой замкнутую систему операций над отношениями в реляционной модели данных. Первоначальный набор операций был предложен Коддом [3] и включал теоретико-множественные операции, а также операции перестановки, проекции, соединения, композиции, и деления отношений. В процессе развития реляционной теории и практики были предложены новые операции, например выборка и полусоединение. Поскольку многие операции выразимы друг через друга, в составе реляционной алгебры можно выделить несколько вариантов базиса, например предложенный
в [4].
Таким образом, запрос, сформулированный на некотором декларативном языке, например SQL, в реляционной базе данных преобразуется в выражение в терминах операций реляционной ал-
гебры. Важно отметить, что нетривиальный исходный запрос представим в виде алгебраического выражения многими способами, и большинство алгебраических операций реализуется несколькими различными алгоритмами. Это ведет к тому, что декларативный запрос может быть выполнен несколькими способами, то есть имеет несколько планов выполнения.
В [5] описываются основные этапы выполнения запроса в реляционной базе данных, и выделены следующие модули:
• парсер,
•
Данная схема используется в большинстве систем выполнения декларативных запросов. Пар-сер получает на входе запрос на некотором декларативном языке и преобразует его в выражение в реляционном исчислении. Оптимизатор перебирает пространство эквивалентных планов выполнения запроса и выбирает план, который рассматривается как оптимальный. Генератор кода по выбранному плану строит последовательность команд обращения к исполнителю запроса.
В обзоре [2] обсуждаются основы конструирования систем управления базами данных, включая архитектуру и такие подходы к выполнению запросов, как итеративное вычисление сложных планов, параллельное выполнение и его реализация. Также рассматриваются основные алгоритмы выполнения некоторых базовых реляционных операций. Детально обсуждаются алгоритмы, реализующие реляционные операции агрегирования и соединения на основе вложенных циклов, сортировки, слияния и hash-таблиц.
Важно отметить, что во многих системах при выполнении запроса исполнителем алгебраические операции реализованы как операции над потоками данных. Операция, читает аргументы из отдельного потока данных и записывает результат в выходной поток по мере его формирования. Такой подход позволяет отказаться от материализации данных, передаваемых между операциями внутри одного запроса, если, конечно, этого
не требует реализация операции, например, сортировки.
Мы будем различать потоки данных, приходящие из первичных источников информации, и потоки, возникающие при выполнении запроса. В дальнейшем, если это не будет следовать из контекста, мы будем уточнять, что подразумевается под потоком данных.
2.2. Оптимизация запросов
Обсудим детально этап оптимизации, поскольку он является существенным для систем с декларативными языками, когда в запросе не специфицирован процесс построения ответа, и оптимизация становится возможной и полезной. В обзоре [5] рассматривается задача оптимизации запросов, архитектура оптимизатора, основанного на моделях стоимости, а также основные алгоритмы поиска наилучшего плана.
Оптимизатор выбирает из множества эквивалентных планов выполнения запроса в некотором смысле наилучший. Качество планов может оцениваться разными способами в зависимости от цели оптимизации. Более формально задача оптимизатора состоит в том, чтобы найти план, функция стоимости (например, время выполнения запроса или получения первого кортежа ответа) которого минимальна.
В зависимости от характера функции стоимости выделяют оптимизаторы:
• применяющие правила преобразования плана выполнения запроса в эквивалентный ему, которые заведомо приводят к уменьшению функции стоимости;
имости выполнения запроса.
В оптимизаторах запросов, где явно используется функция стоимости запроса, строятся модели стоимости операций [5,6]. Модели стоимости позволяют строить оценку реальной функции стоимости плана выполнения запроса. В обзоре [7] обсуждаются методы построения моделей стоимости операций на основе сбора статистики, и анализируется применимость разных типов гистограмм.
При оптимизации запросов на основе моделей стоимости можно выделить два основных подхода к поиску оптимального плана [5,6,8]:
— алгоритм динамического программирования,
— жадный алгоритм,
— метод ветвей и границ.
— метод случайного поиска,
— генетические алгоритмы.
Важно отметить, что приведенные выше алгоритмы поиска оптимального плана можно разделить на точные и приближенные. Необходимость использования приближенных алгоритмов оптимизации запросов обусловлена мощностью пространства планов и бессмысленностью поиска точного решения в контексте приближенных моделей функции стоимости.
3. ВЫПОЛНЕНИЕ ПРИБЛИЖЕННЫХ ЗАПРОСОВ
Во многих случаях, в частности, при анализе потоков сообщений и данных, получаемых с разнообразных источников в реальном времени, и при решении сложных задач информационного поиска, точное выполнение запросов недостижимо и не имеет смысла.
Необходимость приближенной обработки потоков возникает из-за невозможности хранения и анализа всей истории потока. В основе приближенного выполнения других запросов часто лежит природа данных и самой задачи, например поиск изображений по подобию.
Поддержка приближенного выполнения запросов становится актуальной и порождает ряд открытых вопросов и задач.
Таким образом, в этом разделе буду рассмотрены не только класс приближенных запросов, но и методы приближенного выполнения запросов.
3.1. Языки запросов
Разнообразие типов обрабатываемых данных требует расширения и пересмотра широко используемых языков описания запросов, таких как реляционная алгебра и исчисление. Предлагаемые высокоуровневые языки, как правило,
являются расширением традиционного реляционного исчисления и поддерживают новые подходы к анализу данных, например, основанные на подобии и вероятностных моделях.
Многие обогащ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.