автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Оптимизация запросов в слабоструктурированной модели данных

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

2 7 АЫ 2Ш

На правах рукописи

м

Лукичёв Максим Сергеевич

Оптимизация запросов в слабострукт^/рированной модели

данных ^

05.13.11 -- Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

003475855

Санкт-Петербург 2009

003475855

Работа выполнена на кафедре информатики математико-механического факультета Санкт-Петербургского государственного университета.

доктор физико-математических наук, профессор НОВИКОВ Борис Асенович

доктор технических наук,

КУЗНЕЦОВ Сергей Дмитриевич

(Институт системного программирования РАН)

кандидат физико-математических наук, КУРАЛЁНОК Игорь Евгеньевич (ЗАО "Яндекс")

Южно-Уральский государственный университе

Защита диссертации состоится "¿9" баиглУрл 2009 года в/^^асов на заседании совета Д212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., 28, математико-механичсский факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан "/£ " 2009 года.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Ученый секретарь

диссертационного совета

доктор физико-математических наук,

профессор

Даугавет И.К.

Общая характеристика работы

Актуальность темы. Высокоуровневые языки запросов принято рассматривать как одно из наиболее важных средств, предоставляемых СУБД. Обладая очень большой выразительностью, декларативные языки допускают высокоэффективное выполнение запросов, достигаемое в процессе оптимизации.

Наиболее полно методы оптимизации развиты для СУБД, основанных на реляционной модели данных, и, в частности, ее промышленного аналога SQL. Оптимизаторы современных промышленных СУБД способны генерировать планы очень высокого качества. Однако, для применения в контексте слабоструктурированной модели данных, в частности, XML, эти методы должны быть существенно пересмотрены. Учитывая неизменно возрастающую интенсивность использования XML в качестве модели данных и постоянно растущий объём таких данных, задача оптимизации запросов к XML выходит на первый план. В качестве языка XML-запросов в диссертации рассматривается XQuery, в силу наибольшей распространённости этого стандарта.

Цель работы. Исследование и разработка методов высокоэффективного выполнения запросов к слабоструктурированным данным, представленных на языке XQuery. Для достижения этой цели в диссертации решаются следующие задачи:

• Разработка гибкой алгебры, обладающей необходимыми свойствами для предоставления достаточно широкого пространства допустимых планов запроса.

• Разработка эффективного метода поиска оптимального (субоптимального) плана в терминах разработанной алгебры.

• Разработка прототипа с целью экспериментальной верификации полученных результатов

Основные результаты. В работе получены следующие основные результаты:

• Предложена новая алгебра XQuery-запросов, удовлетворяющая требованиям, сформулированным на основе анализа существующих подходов к оптимизации XQuery-запросов, которым должна отвечать алгебра для построения высокопроизводительных систем выполнения запросов.

• Доказано, что операции предложенной алгебры обладают необходимыми алгебраическими свойствами, такими как ассоциативность и коммутативность. А также, доказано, что в терминах этой алгебры можно получить более эффективные планы, чем при использовании ранее известных алгебр.

• Сформулированы ограничения на пространство допустимых планов, позволяющих применять алгоритмы блочной оптимизации. Доказано, что данные ограничения не приводят к потере оптимального плана.

• Экспериментально продемонстрировано, что при использовании предложенной алгебры могут быть получены значительно более эффективные планы, чем в известных XML СУБД.

Научная новизна. Научной новизной обладают следующие результаты работы:

1. Критерии и требования к алгебре, необходимой для построения высокопроизводительных исполнителей запросов.

2. Алгебра XQuery-запросов, удовлетворяющая этим требованиям.

3. Конкретизация блочного алгоритма для оптимизации XQuery-запросов на основе предложенной алгебры.

Теоретическая ценность и практическая значимость. С теоретической точки зрения в работе формально определены операции, формирующие базис алгебры, и доказаны тождества, обосновывающие допустимость оптимизирующих преобразований. Формализация понятий гарфа

частичных планов и блоков в нём позволяют использовать предложенный блочный метод для оптимизации на основе различных алгебр.

Практическая значимость работы состоит в том, что, разработанная алгебра может служить основой для построения стоимостных оптимизаторов как для XML СУБД, так и для автономных исполнителей запросов промышленных систем. Предложенный метод оптимизации поблочно может существенно ускорить процесс оптимизации, что особенно важно, учитывая возможную сложность XQuery-запросов. Экспериментально показано, что применение предложенных методов может существенно повысить эффективность выполнения запросов в XML СУБД.

Апробация работы. Результаты работы докладывались:

• на Двенадцатой Восточно-Европейской конференции "Advances in Databases and Information Systems" (Пори, Финляндия, сентябрь 2008),

• на Четвёртом коллоквиуме "Spring Colloquium for Young Researchers in Databases and Information Sytems (SYRCoDIS)" (Москва, июнь 2007),

• на семинарах группы теории баз данных при лаборатории исследования операций НИИММ,

• на семинаре Московской секции ACM SIGMOD (Москва, январь 2009).

• на семинаре в Институте системного программирования РАН (Москва, январь 2009).

Публикация результатов. Основные результаты представлены в работах [1-3]. Статья [1] опубликована в журнале, входящем в перечень ВАК. В статье [2] соискателю принадлежат определения компонент алгебры, соавтору - техническое оформление и примеры. В статье [3] соискателю принадлежит метод группировки по соседям (NG), соавтору - метод группировки в порядке документа (DG).

Структура и объем диссертации.

Работа состоит из шести глав, включая введение и заключение, и списка литературы. Общий объём диссертации составляет 120 страниц машинописного текста. Список литературы содержит 73 наименования. Рисунки и таблицы нумеруются по главам.

Основное Содержание работы.

Введение содержит предварительную информацию о предмете исследования.

Первая глава демонстрирует актуальность оптимизации запросов в СУБД, основанных на слабоструктурированной модели данных, в частности XML. За последнее десятилетие XML приобрёл значительное распространение как универсальное средство обмена данными, став одним из основных стандартов обмена информации между информационными системами. В результате существенного роста размера XML-данных появилась острая необходимость в создании эффективных и удобных методов извлечения данных. Это стало предпосылкой для появления таких языков, как Lorel, Quilt, XQL, XML-QL, XPath и XQuery. Наибольшую популярность среди них получили XQuery и его подмножество XPath, являющиеся результатом работы XML Query Working Group в World Wide Web Consortium (W3C). Первая часть первой главы диссертации посвящена краткому описанию модели данных XML и языка запросов XQuery.

Вторая часть посвящена основным принципам оптимизации. Для одного и того же запроса существуют различные способы выполнения (физические планы), вырабатывающие одинаковые результаты, но значительно различающиеся по стоимости выполнения. Эти планы формируют пространство поиска. Задача оптимизации состоит в том, чтобы выбрать среди них обладающий наименьшей стоимостью. При этом, в качестве метрики стоимости обычно используют приблизительную оценку времени выполнения плана. Задача поиска оптимального плана относится к классу задач дискретного математического программирования. Существует множество алгоритмов для решения таких задач, например, метод ветвей и границ, стохастический поиск и др. Во второй части приводится краткое описание

основных компонент оптимизатора и краткий обзор наиболее распространённых алгоритмов, используемых для поиска или построения оптимальных планов. Несмотря на то, что эти алгоритмы были разработаны в контексте оптимизации реляционных запросов, они являются универсальными и могут быть использованы для оптимизации XML-запросов.

В третьей части приводится обзор наиболее важных алгоритмов, используемых при выполнении запросов, к которым относятся универсальные алгоритмы сортировки и хэширования для больших объёмов данных, альтернативные алгоритмы для операций соединения и некоторые алгоритмы реализации операций, специфичных для XML баз данных.

Четвёртая часть посвящена алгебрам запросов. Алгебра является одной из наиболее важных компонент оптимизатора, формируя пространство поиска планов, эквивалентных исходному. Наличие в алгебре операций, допускающих эффективную реализацию, и достаточно большого количества эквивалентных трансформаций потенциально создают условия для построения плана лучшего качества. Для реляционных баз данных существует общепринятая алгебра, чего нельзя сказать об XML базах данных. Это обусловлено относительной новизной данной области и, особенно, использованием различных подходов к организации баз данных (XML-прирождённые или XML-приспособленные СУБД).

В четвёртой части первой главы на основе анализа существующих XML-алгебр формулируются критерии, которым должна удовлетворять алгебра, необходимая для построения высококачественного оптимизатора, использующего стоимостные оценки:

1. Операции алгебры определены над структурами, позволяющими группировать элементы.

2. Все операции алгебры атомарны и определены над множествами кортежей (ST-операции). Результат вычисляется только на основе входных множеств кортежей и может быть использован в качестве операндов других операций.

3. Наличие тождеств, позволяющих преобразовывать операции со слож-

ными предикатами к комбинациям операций с простыми предикатами.

4. Наличие тождеств, позволяющих изменять порядок следования операций, представляющих xpath и FLWOR-конструкции.

Также в данном разделе демонстрируется, что существующие XML-алгебры не в полной мере удовлетворяют этим требованиям.

Во второй главе представлена новая XQuery-алгебра, именуемая XAnswer, разработанная автором и показано, что она удовлетворяет обозначенным требованиям. В первой и второй частях описаны структуры данных алгебры, а также определены основные операции, формирующие базис алгебры.

Операции XAnswer определены над структурой, называемой подборкой (envelop).

Определение 1. Подборка (< he\be\re >) представляет собой тройку из заголовка (he), тела (be) и результирующего атрибута (re). Заголовок (he) - это неупорядоченное множество уникальных (в рамках этого заголовка) имен, называемых атрибутами. Результирующий атрибут (re) - это некоторый атрибут заголовка. Тело подборки - это упорядоченное множество кортежей (т), а каждый кортеж - неупорядоченное множество пар {a,v), по одной паре для каждого a G he; v - либо элемент (то

есть атомарное значение или узел), либо последовательность элементов (<)■

Базис алгебры составляют 11 основных операций:

1. Вычисление функции (//): //(< Ь\т{е{). ,.т{еп)\г >) = =< h,i = пех1Ы()\т(еи f(ei))... т(еп, f(en))\i > .

2. Выборка (сгрг): <трг(< h\r(e{)... т(е„)\г >) =< h\r{e[)... |г >, где (e')i — (e)i и Priei) — true. В качестве предиката рг может быть любое логическое выражение.

3. Проекция (7Tft<): щ>(< h\r(ei)... r(e„)|r >) =< h'\r(ei |ft<)... |r |ft->, где h' С h.

4. Сортировка (sortu): sorth,>{< /i|r(ei).. . r(e„)|r >) = =< Ы\т{е\)... \r >, где (e')i = Sorth>(e)i.

5. Нумерация (indexi): indexi{< h\r(ei)... r(en)|r >) = =< h, г|т(еь 1) • • • т(еп> n)|r > .

6. Копирование (dup/¡J: dup^K Ъ\т{е\)... т(е„)|г >) = =< /i,nexi/d()|r(ei,ei \h.)... |r >, где hi £ h.

7. Объединение (U): < /i|r(ei)... |r > U < h\r{ell)... \r >= =< A|r(ei).. • r(e„),r(ei)... r(e'm)|r > .

8. прямое произведение (x): < /i|r(ei)... |г > x < к'\т(е[).. .\r' >= =< h, h'\r{e\, e[)... r(ei, е'п),т(е2,е'1)... |r' > .

9. Левое внешнее соединение (м^): < h\r(ei)... |r >Mlpr

< h'\T(e[)...\r' >=< h,h'\T(e1,e'l)...T(e1,e';),r(e2,e'l)...\r' >, где e" = e-, если pr(ej, e-) = true, иначе e" = ().

10. Группировка (nest^): nest},<(< h\r(ei)... |r >) =

=< h\r(pil s'1 ... s'm)... |r >, где h' С h, Pij - уникальные кортежи

me), 4wmwh e h\h!.

11. Операции разгрушшровки (unnest^<): unnestht(< /г]т(е|, ef)... |r >) =

=< h\r(e\, «j'1, ef ), r(e{, uj1, ef )... |r >, где Ы S h, a) = ç(«ïJ' ...

Основные тождества алгебраических операций, определяющие пространство эквивалентных планов (пространство поиска), описаны и доказаны в третьей части.

В четвертой части описывается процесс построения алгебраических выражений для запросов, содержащих основные конструкции XQuery, не

включая рекурсивные функции. Процесс состоит из двух фаз. На первой фазе, называемой нормализацией, производится преобразование XQuery-запроса в эквивалентный запрос, но удовлетворяющий определённым требованиям. На второй фазе (фазе трансляции) производится непосредственное построение алгебраического выражения, путём последовательного обхода конструкций нормализованного запроса в порядке их следования и применения описанных правил для каждой из них.

В пятой части главы описываются оптимизации, позволяющие повысить качество планов, получаемых в результате построения. Повышение качества достигается за счёт переупорядочивания, исключения и замещения избыточных операций. Целью переупорядочивания является уменьшение размеров промежуточных результатов за счёт выполнения операций, сокращающих размеры результатов, как можно раньше (опускание селективных операций). Учитывая алгебраические свойства, опускание селективных операций зачастую возможно только наряду с опусканием других, связанных с ними. Для этого предложен алгоритм, позволяющий переупорядочивать (опускать) блоки операций.

Для формализации преобразований вводится понятие графа плана запроса, с помощью которого, в свою очередь, определяются блоки операций, являющихся ключевым элементом при оптимизации. Вершинами графа являются операции, а дуги соединяют операции с операндами, имея направление от первых к последним.

Определение 2. Блок операций - это подграф, который имеет не более одной вершины (результирующей вершины,), соединённой входящими дугами с вершинами вне подграфа, а все вершины, имеющие исходящие дуги, которые ведут вне подграфа, соединены этими дугами с единственной вершиной. Такие вершины, называются входными вершинами.

Если блок оперирует с атрибутами, которые были добавлены в заголовок результирующей подборки другого блока, такой блок зависит от последнего. Блоки независимы, если они не зависят друг от друга. Блоки операций, соответствующие for, let, where и др. конструкциям, будем именовать блоками конструкций. Заметим, что два блока конструкций неза-

висимы, если одна конструкция нормализованного запроса не зависит от переменной, определённой в другой.

Алгоритм опускания блоков заключается в следующем. Представим план Р = Bs{Br), где Bs и Вг блоки операций и Bs - блок, который требуется опустить.

1. Найти блок конструкции Вт, Вг = Ве(Вт(Вь)): Bs зависит от Вт. Если такого Вт нет, тогда Ве = Вг.

2. Рекурсивно выполнить алгоритм для Вт, получив в результате В'т,В'ь,В'е.

3. Поменять местами Bs и В'с, получив: Р = B't{Bs{B'm(B'b))).

Частным случаем преобразований, направленных на опускание блоков операций, является поддержка ленивых вычислений, которые необходимы для эффективной обработки кванторных выражений, позиционных предикатов, условий в where, if-then-else и typeswitch конструкциях. Эти оптимизации имеют специфику, связанную со структурой полученного в результате построения плана, и так же описаны в пятой части второй главы.

Третья глава описывает предложенный алгоритм поиска оптимального плана. Чрезмерно широкое пространство допустимых планов существенно усложняет задачу поиска оптимального или субоптимального плана, в особенности для сложных запросов. Можно ожидать, что при использовании XQuery доля сложных запросов будет выше, чем в системах, использующих SQL, поскольку выразительные средства XQuery, такие, как навигационные выражения а также вложенные for- и let-конструкции позволяют скрыть фактическую сложность реализации.

Сложность задачи оптимизации можно значительно понизить, преобразовав задачу в блочную, так как сложность оптимизации каждого из блоков существенно ниже, чем исходная оптимизационная задача. В силу однородности модели данных и языка запросов выделение блоков в реляционных системах практически невозможно и, поэтому, блочные алгоритмы оптимизации неприменимы и ранее не рассматривались в контексте оптимизации запросов.

В первой части главы вводятся основные понятия и показываестя, что задача оптимизации может быть решена поблочно, если пространство эквивалентных алгебраических преобразований запроса удовлетворяет определённым условиям. Для формализации блочной задачи оптимизации и ограничений на пространство поиска вводится граф классов частичных планов.

Рассмотрим множество V классов эквивалентности частичных планов для некоторого запроса. На множестве V можно определить структуру графа: пусть у € V - некоторый класс эквивалентности, р € у : р = а(р1,р2,... - некоторый представитель этого класса, а р; 6 ^ - частичные планы. Тогда в графе содержатся дуги V —>

Вершина, соответствующая полному плану выполнения запроса, имеет только выходящие дуги. Любому плану соответствует некоторый набор путей в этом графе, начинающихся в корневой вершине и заканчивающихся в классах операций выборки хранимых данных, из которых дуги выходить не могут. Заметим, что каждой вершине из V соответствует некоторый запрос (не обязательно являющийся подзапросом исходного запроса).

Определение 3. Подмножество В С V называется блоком графа, если существует вершина Ув £ В такая, что для любой вершины Ь € В любой путь, проходящий через Ь, проходит также через у в-

Важность понятия блока графа связана с тем, что любой план, содержащий какую-нибудь вершину из блока, обязательно содержит вершину Ув, поэтому оптимизация подзапроса, соответствующего блоку, может быть выполнена в некотором смысле независимо от других частей запроса.

Неформально, блочный алгоритм состоит в применении некоторого другого алгоритма оптимизации но отдельности к разным частям запроса. При этом, не имеет значения, применяется ли один и тот же алгоритм для всех блоков или нет. Также не имеет значения, является ли этот алгоритм точным (например, алгоритмом динамического программирования или ветвей и границ) или приближенным (основанным на эвристиках или стохастическим). Конечно, качество получаемого плана будет зависеть от используемых алгоритмов, по это не оказывает влияния на нршщшшаль-

ную схему блочного алгоритма.

Во второй части третьей главы приводится описание блочного алгоритма. Неформально, блочный алгоритм состоит в применении некоторого другого алгоритма оптимизации по отдельности к разным частям запроса.

Предположим, что в пространстве планов выделены некоторые блоки В\,В2, ■ ■ ■ Вт. Стоит отметить, что блоки могут быть как листовыми, то есть не имеющими вершин, связанных с вершинами других блоков исходящими дугами, так и промежуточными, обладающими такими вершинами.

Тогда для решения задачи оптимизации может быть применен следующий алгоритм:

1. Найти (суб)оптимальный план для каждого блока, применяя выбранный алгоритм оптимизации. Возможно, что при вычислении блока используются подвыражения, оценки стоимости и кардинальности которых еще не вычислены. В таких случаях используются грубые оценки для подвыражений. Например, можно применить оценки, полученные по произвольному плану из класса эквивалентности.

2. Выполнить алгоритм оптимизации для исходного запроса, в котором каждый блок заменен на одну неделимую операцию (с оценками стоимости, полученными при оптимизации блоков).

3. Если исчерпан лимит времени на оптимизацию, закончить работу.

4. Если в результате шага 2 изменились оценки стоимости операций, на основе которых выполнялась оптимизация промежуточных блоков, повторить шаг 1 для тех блоков, для которых изменились оценки, и перейти к шагу 2, иначе (если оценки не изменились) закончить работу.

Корректность этого алгоритма непосредственно следует из леммы 1.

Лемма 1. Пусть р - оптимальный план и существует путь, построенный по плану р, проходящий через вершину V € V. Тогда подпланру плана р является оптимальным планом для V.

Поиск блоков в пространстве планов сам по себе вычислительно сложен, поэтому предлагается использовать априорное выделение блоков, соответствующих подвыражениям специального вида в исходном запросе. Для того, чтобы эти подзапросы действительно образовывали блоки, необходимо ввести некоторые ограничения на применение алгебраических соотношений. По определению, блок характеризуется отсутствием путей, ведущих в него не через его корневую вершину, то есть отсутствием дуг, ведущих в другие вершины блока извне. Поскольку мы будем выделять блоки априорно, запрет па использование таких дуг эквивалентен запрету на использование выражений, лежащих вне блока и использующих его внутренние вершины, но не корень. Исключение таких выражений, в свою очередь, означает запрет на использование эквивалентных трансформаций, приводящих к появлению нежелательных дуг.

В третьей части главы описывается применение блочного алгоритма для оптимизации XQuery-запросов с использованием алгебры XAnswer. Предлагается выделять в качестве блоков множества планов, соответствующих навигационным выражениям let и /ог-конструкций нормализованного запроса. В терминах алгебры такое выделение блоков означает запрет на ассоциативное преобразование между операциями соединения, имеющими предикаты разной природы (то есть структурный предикат и предикат по значению). Далее показывается что запрет таких преобразований не приводит к потере оптимального плана для широкого класса запросов. В остальных случаях это оказывает влияние на выделение блоков, что учитывается на следующих итерациях алгоритма, тем самым, сохраняя возможность получения субоптимальных планов высокого качества.

Четвертая глава посвящена описанию экспериментов. Для экспериментальной верификации предложенной техники выполнения запросов был реализован прототип исполнителя на основе СУБД eXist. В рамках прототипа были реализованы и использованы следующие элементы: синтаксический анализатор с открытым исходным кодом (eXist), преобразователь, транслятор, планировщик без стоимостной оптимизации, исполнитель и драйвер для хранилища eXist. Общая архитектура исполнителя запросов описывается в первой части главы.

Некоторые из подходов, основанных на существующих XQueiy-алгебрах, за счёт применения специальных оптимизаций позволяют использовать атомарные операции над множествами (ST) вместо итеративных (NT), для относительно простых вложенных подзапросов. Это, в свою очередь, может значительно повысить производительность за счёт возможности использования алгоритма хэширующего соединения вместо вложенных циклов. Тем не менее, они не могут использовать ST-вычисления вместо NT для тех запросов, которые содержат кванторы, сложные условные (if-then-else, typeswitch) или кЛеге-конструкции с вложенными подзапросами. Такие запросы будем называть усложнёнными. При этом, при использовании ST-операций для вычисления усложнённых запросов, появляется необходимость поддержки ленивых вычислений.

Усложнённые запросы часто возникают, например, в задачах анализа больших объёмов XML-данных, имея в качестве операндов условных выражений и логических операций выражения большой вычислительной сложности. Одним из примеров таких задач является анализ информации в Wikipedia, представленной в виде XML, объёмом более 20 гигабайт, и содержащей несколько миллионов связанных друг с другом статей сложной структуры.

В экспериментах анализируется производительность различных подходов выполнения запросов: основанных на использовании алгебры W3C, генерируемые в СУБД cXist; использующие ST-операции наряду с NT-операциями для условных выражений (аналогично подходам, основанным на существующих XQuery-алгсбрах; использование алгебры XAnswer и предложенных оптимизаций. Для экспериментов использовался эталонный набор данных и запросов XMark, включая дополнительно усложнённые запросы.

Показаио, что планы для относительно простых запросов, получаемые при помощи XAnswer, сопоставимы по производительности с планами, которые можно получить, используя существующие алгебры, а для сложных запросов - значительно превосходят их.

Заключение содержит список основных результатов, полученных в работе.

Публикации автора по теме диссертации

Статьи в журналах, рекомендованных ВАК:

1. Лукичсв М.С. Оценка Селективности XPath-запросов в XML-СУБД. Программные продукты и системы, Выпуск номер 2. ■— Тверь, июнь 2009. - стр. 20-22.

Другие публикации:

2. M.Lukichev, D.Barashcv. XML Query Algebra for Cost-based optimization. Spring Young Researchers Colloquium on Databases and Information Systems (SYRCoDIS). — Москва, июнь 2007. — стр. 17-26.

3. Y.Soldak, M.Lukichev. Enabling XPath Optional Axes Cardinality Estimation Using Path Synopses. Proceedings of the 12-th East-European Conference on Advances in Databases and Information Systems. Пори, Финляндия, сентябрь 2008. — стр. 279-294.

Подписано к печати 09.06.09. Формат 60 х 84 Vie. Бумага офсетная. Гарнитура Times. Печать цифровая. Печ. л. 1,0. Тираж 100 экз. Заказ 4473.

Отпечатано в Отделе оператинной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург. Стирый Петергоф, Университетский пр., 26 Тел : (812) 428-4043, 428-6919

1. Методы и средства обработки запросов

1.1. Модель данных XML и язык запросов XQuery.

1.1.1. Модель данных XML.

1.1.2. Язык XQuery.

1.1.2.1. Навигационные выражения.

1.1.2.2. Элементарные операции.

1.1.2.3. FLWOR выражения.

1.1.2.4. Условные и кванторные выражения.

1.2. Основные принципы оптимизации запросов.

1.2.1. Основные понятия.

1.2.2. Основные элементы оптимизатора.

1.2.3. Алгоритмы поиска оптимального плана.

1.2.3.1. Алгоритм динамического программирования.

1.2.3.2. Стохастические алгоритмы поиска.

1.3. Основные методы выполнения.

1.3.1. Методы сортировки и хэширования для больших объёмов данных.

1.3.1.1. Сортировка.

1.3.1.2. Хэширование.

1.3.2. Алгоритмы соединения.

1.3.2.1. Алгоритм вложенных циклов.

1.3.2.2. Алгоритм сортировки и слияния.

1.3.2.3. Алгоритм хэшируюгцего соединения.

1.3.3. Прямое и обратное вычисление навигационного выражения.

1.3.4. Структурное соединение.

1.3.5. Целостное соединение.

1.4. XQuery-алгебры

1.4.1. Обзор и классификация XQuery-алгвбр.

1.4.2. Анализ требований к алгебре для высокопроизводительного оптимизатора.

1.5. Выводы.

2. Алгебра XQuery-запросов XAnswer

2.1. Структуры данных алгебры.

2.2. Основные операции алгебры

2.2.1. Базисные операции.

2.2.2. Дополнительные операции.

2.3. Основные тождества операций.

2.4. Построение алгебраического выражения.

2.4.1. Нормализация запроса.

2.4.2. Трансляция в выражения алгебры.

2.5. Оптимизация.

2.5.1. Изменение порядка блоков.

2.5.2. Исключение избыточных операций.

2.5.3. Преобразования, обеспечивающие ленивые вычисления.

2.6. Обсуждение.

2.7. Выводы.

3. Эффективные методы поиска оптимального плана

3.1. Основные понятия.

3.1.1. Модель стоимости.

3.1.2. Граф классов частичных планов.

3.1.3. Блочный алгоритм.

3.2. Оптимизация для XQuery.

3.3. Выводы.

4. Прототип исполнителя запросов и численные эксперименты

4.1. Прототип исполнителя запросов XAnswer.

4.1.1. Организация хранилища данных и исполнителя запросов СУБД eXist.

4.2. Постановка экспериментов

4.2.1. Эталонный набор данных и запросов XMark.

4.2.2. Описание экспериментов.

4.3. Выводы.

Актуальность темы

Высокоуровневые языки запросов принято рассматривать как одно из наиболее важных средств, предоставляемых системами управления базами данных. Обладая очень большой выразительностью, декларативные языки допускают высокоэффективное выполнение запросов, достигаемое в процессе оптимизации. По существу, работа оптимизатора сводится к выбору одного из алгебраических выражений, эквивалентных исходному запросу, но обладающих различной стоимостью выполнения.

Наиболее полно методы оптимизации развиты для СУБД, основанных на реляционной модели данных, и, в частности, ее промышленного аналога SQL. Оптимизаторы современных промышленных СУБД способны генерировать планы очень высокого качества. Однако, для применения в контексте слабоструктурированной модели данных, в частности, XML, эти методы должны быть существенно пересмотрены. Учитывая неизменно возрастающую интенсивность использования XML в качестве модели данных и постоянно растущий объём таких даннных, задача оптимизации запросов к XML выходит на первый план. В качестве языка XML-запросов в диссертации рассматривается XQuery [72], в силу наибольшей распространённости этого стандарта.

Цели и задачи работы

Целью диссертационной работы является исследование и разработка методов эффективного выполнения XQuery-запросов. Для достижения этой цели поставлены следующие задачи:

1. Разработка гибкой алгебры, обладающей необходимыми свойствами для предоставления достаточно широкого пространства допустимых планов запроса.

2. Разработка эффективного метода поиска оптимального (субоптимального) плана в терминах разработанной алгебры.

3. Разработка прототипа с целью экспериментальной верификации полученных результатов.

Основные результаты

1. Предложена новая алгебра XQuery-запросов, удовлетворяющая требованиям, сформулированным на основе анализа существующих подходов к оптимизации XQuery-запросов, которым должна отвечать алгебра для построения высокопроизводительных систем выполнения запросов.

2. Доказано, что операции предложенной алгебры обладают необходимыми алгебраическими свойствами, такими как ассоциативность и коммутативность. А также, доказано, что в терминах этой алгебры можно получить более эффективные планы, чем при использовании ранее известных алгебр.

3. Сформулированы ограничения на пространство допустимых планов, позволяющих применять алгоритмы блочной оптимизации. Доказано, что данные ограничения не приводят к потере оптимального плана.

4. Экспериментально продемонстрировано, что при использовании предложенной алгебры могут быть получены значительно более эффективные планы, чем в известных XML СУБД.

Научная новизна подхода

Научной новизной обладают следующие результаты работы:

1. Критерии и требования к алгебре, необходимой для построения высокопроизводительных исполнителей запросов.

2. Алгебра XQuery-запросов, удовлетворяющая этим требованиям.

3. Конкретизация блочного алгоритма для оптимизации XQuery-запросов на основе предложенной алгебры.

Практическая значимость

Разработанная алгебра может служить основой для построения стоимостных оптимизаторов как для XML СУБД, так и для автономных исполнителей запросов промышленных систем [7].

Предложенный метод оптимизации поблочно может существенно ускорить процесс оптимизации, что особенно важно, учитывая возможную сложность XQuery-запросов.

Экспериментально показано, что применение предложенных методов может существенно повысить эффективность выполнения запросов в XML СУБД.

Структура диссертации

Работа состоит из шести глав, включая введение и заключение, и списка литературы. Общий объём диссертации 120 страницы, список литературы содержит 74 наименования.

4.3. Выводы

Описана, архитектура прототипа исполнителя запросов на основе алгебры XAnswer, описана экспериментальная среда, проведены эксперименты и произведён их анализ. Показано, что планы для простых запросов, получаемые при помощи XAnswer, сопоставимы по производительности с планами, которые можно получить, используя существующие алгебры, а для сложных запросов - значительно превосходят их.

Заключение

В диссертации получены следующие основные результаты:

1. Предложена новая алгебра XQuery-запросов, удовлетворяющая требованиям, сформулированным на основе анализа существующих подходов к оптимизации XQuery-запросов, которым должна отвечать алгебра для построения высокопроизводительных систем выполнения запросов.

2. Доказано, что операции предложенной алгебры обладают необходимыми алгебраическими свойствами, такими как ассоциативность и коммутативность. А также, доказано, что в терминах этой алгебры можно получить более эффективные планы, чем при использовании ранее известных алгебр.

3. Сформулированы ограничения на пространство допустимых планов, позволяющих применять алгоритмы блочной оптимизации. Доказано, что данные ограничения не приводят к потере оптимального плана.

4. Экспериментально продемонстрировано, что при использовании предложенной алгебры могут быть получены значительно более эффективные планы, чем в известных XML СУБД.

1. Романовский . Алгоритмы решения экстремальных задач. — Москва, 1977.

2. Balmin A., et al. Cost-based optimization in db2 xml // IBM Syst. J.— 2006. Vol. 45, no. 2. - Pp. 299-319.

3. Beeri C., Tzaban Y. Sal: An algebra for semistructured data and xml // WebDB (Informal Proceedings). — 1999. Pp. 37-42.

4. Bennett K., Ferris M. Ioannidis Y. A genetic algorithm for database query-optimization //In Proceedings of the fourth International Conference on Genetic Algorithms. — Morgan Kaufinann Publishers, 1991.— Pp. 400407.

5. Berkley DB Home Page, http://www.oracle.com/technology/products/berkeley-db/index.html. — Berkley DB Home Page.

6. Blasgen M., Eswaran K. Storage and access in relational databases // IBM Systems Journal. — 1977. — Vol. 16, no. 4. — Pp. 363-377.

7. Borkar V., et al. Query processing in the aqualogic data services platform // Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment, 2006. — Pp. 1037-1048.

8. Bratbergsen K. Hashing methods and relational algebra operations // Proceedings of Conferece on Very Large Data Bases. — 1984. — Pp. 323-333.

9. Chean, et al. From tree patterns to generalized tree patterns: On efficient evaluation of xquery // VLDB. — 2003. Pp. 237-248.

10. Choi В., Fernandez M., Simeon J. The xquery formal semantics: A foundation for implementation and opitmization. — 2002.

11. Codd E. A relational model of data for large shared data banks // CACM.- 1970,- Vol. 13, no. 6.

12. Deutsch A., et al. The next framework for logical xquery optimization // VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases. — VLDB Endowment, 2004. — Pp. 168-179.

13. Dewitt D., et al. Implementation techniques for main memory database systems // Proceedings of ACM SIGMOD conference. — 1984.

14. DeWitt D., Gerber В. Multiprocessor hash-based join algorithms // Proceedings of Conferece on Very Large Data Bases. — 1985. — Pp. 151-164.

15. El-Masri R., et al. Fundamentals of database systems. —■ 1989.

16. Exist DBMS Home Page, http://exist-db.org/. — Exist DBMS Home Page.

17. Extensible Markup Language (XML) 1.0 (Second Edition). — 6 October 2000. — W3C Recommendation.

18. Fankhauser P. Xquery formal semantics state and challenges // SIGMOD Rec. 2001. - Vol. 30, no. 3. — Pp. 14-19.

19. Fernandez M., et al. Xml query languages: Experiences and exemplars.— 1999.

20. Gerber R. Dataflow query processing using multiprocessor hash partitioned algorithms. — 1986. — Technical Report. Computer Sciences Department, University of Wisconsin.

21. Goldberg D. Genetic algorithms in search, optimization and machine learning. addison-wesley. — 1989.

22. Goodman J. An investigation of multiprocessor structures and algorithms for database management. — 1981. — Technical Report. University of California.

23. Graefe G. Query evaluation technques for large databases // ACM Computing Surveys. — 1993. — Vol. 25, no. 2. — Pp. 121-123.

24. Graefe G., DeWitt D. The exodus optimizer generator // Proceedings of the 1987 ACM SIGMOD International Conference on Management of Data. 1987. — Pp. 160-172.

25. Graefe G., McKenna B. The volcano optimizer generator: Extensibility and efficient search // IEEE Data Engineering Conference. — 1993.

26. Grinev M., Kuznetsov S. Towards an exhaustive set of rewriting rules for xquery optimization: Bizquery experience // ADBIS.— 2002,— Pp. 340345.

27. Grust T. Accelerating xpath location steps // SIGMOD Conference. — 2002.

28. Haas L., et al. Starburst mid-flight: As the dust clears // IEEE Transactions on Knowledge and Data Engineering. — 1990. — Pp. 143-160.

29. Ioannidis Y. Query optimization // ACM Comput. Surv.— 1996.— Vol. 28, no. 1,- Pp. 121-123.

30. Ioannidis Y. The history of histograms // VLDB '2003: Proceedings of the 29th international conference on Very large data bases. — VLDB Endowment, 2003. Pp. 19-30.

31. Ioannidis Y., Kang Y. Randomized algorithms for optimizing large join queries // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data. — 1990. — Pp. 312-321.

32. Ioannidis Y., Wong E. Query optimization by simulated annealing // Proceedings of the 1987 ACM SIGMOD International Conference on Management of Data. — 1987. — Pp. 9-22.

33. Jagadish H., et al. Tax: A tree algebra for xml // DBPL '01: Revised Papers from the 8th International Workshop on Database Programming Languages. — London, UK: Springer-Verlag, 2002.

34. Jagadish H., et al. Timber, a native xml database // The VLDB Journal. — 2002, — Vol. 11, no. 4. — Pp. 274-291.

35. Jiang H., et al. Holistic twig joins on indexed xml documents // Proceedings of International Conference on Very Large Data Bases. — 2003. — Pp. 273-284.

36. Josifovski V., et al. Querying xml streams // The VLDB Journal.— 2005. Vol. 14, no. 2. - Pp. 197-210.

37. Kang Y. Randomized Algorithms for Query Optimization: Ph.D. thesis / University of Wisconsin, Madison. — 1991.

38. Khalifa S., et al. Structural joins: A primitive for efficient xml query pattern matching // icde.— 2002.

39. Kirkpatrick S., Gelatt C., Vecchi M. Optimization by simulated annealing // Science. 1983. - Vol. 220. - Pp. 671-680.

40. Kitsuregawa M., Nakayama M., Takagi M. The effecy of bucket size tuning in the dynamic hybrid grace hash join method // Proceedings of the International Conference on Very Large Data Bases. — 1989.

41. Kitsuregawa M., Tanaka H.} Motooka T. Application of hash to database machine and its architecture // New Generation Computing. — 1983.

42. Kitsuregawa M., Yang W., Fushimi S. Application of hash to database machine and its architecture // Proceedings of the 6th International Workshop on Database Machines. — 1989.

43. Knuth D. The Art of Computer Programming. — Addison-Wesley, 1973.

44. Lohman G. Grammar-like functional rules for representing query optimiza,-tion alternatives // Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data. — 1988. — Pp. 18-27.

45. Lukichev M., Barashev D. Xml query algera for cost-based optimization // Proceedings of the SYRCoDIS 2007 Colloquium on Databases and Information Systems. — 2007.

46. May N., et al. Nested queries and quantifiers in an ordered context // Proc. ICDE Conference, Boston, USA. — 2004. Pp. 239-250.

47. McHugh J., Widom J. Query optimization for xml // Proceedings of 25th International Conference on Very Large Data Bases. — 1999.— Pp. 315326.

48. Meir W. Index-driven xquery processing in the exist xml database. — 2006.

49. Michiels P. Xquery optimization. — 2003.

50. Mishra P., Eich M. Join processing in relational databases // ACM Com-put. Surv. 1992. - Vol. 24, no. 1.- Pp. 63-113.

51. Nahar S., Sahni S., Shragowitz E. Simulated annealing and combinatorial optimization // DAC '86: Proceedings of the 23rd ACM/IEEE conference on Design automation. — 1986. — Pp. 293-299.

52. Nakayama M., et al. Hash partitioned join method using dynamic destaging strategy // Proceedings of the International Conference on Very Large Data Bases. 1988.

53. Naughton J., et al. The niagara internet query system // IEEE Data Engineering Bulletin. — 2001. — Vol. 24, no. 2. — Pp. 27-33.

54. Novak L., et al. Efficient implementation of xquery constructor expressions // Proceedings of the SYRCODIS 2008 Colloquium on Databases and Information Systems. — 2008.

55. Re C., et al. A complete and efficient algebraic compiler for xquery // ICDE '06: Proceedings of the 22nd International Conference on Data Engineering. — Washington, DC, USA: IEEE Computer Society, 2006. P. 14.

56. Sartiani С., Albano A. Yet another query algebra for xml data // IDEAS '02: Proceedings of the 2002 International Symposium on Database Engineering and Applications. — IEEE Computer Society, 2002. — Pp. 106-115.

57. Schmidt A., et al. Xmark: A benchmark for xml data management // Proceedings of International Conference on Very Large Data Bases. — 2002. — Pp. 974-985.

58. Schneider D., DeWitt D. Tradeoffs in processing complex join queries via hashing in multiprocessor database machines // Proceedings of the International Conference on Very Large Data Bases. — 1990.

59. Sedna DBMS Home Page, http://modis.ispras.ru/sedna/. — Sedna DBMS Home Page.

60. Selinger P., et al. Access path selection in a relational database management system // ACM-SIGMOD Conf. on the Management of Data. — 1979. Pp. 23-34.

61. Shapiro L. Join processing in database systems with large main memories // ACM Transaction Database Systems. — 1986.— Vol. 11, no. 3.— P. 239.

62. Su S. Database computers: Principles, architectures, and techniques. — 1988.

63. Swami A. Optimization of large join queries: Combining heuristic and combinatorial techniques // Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data. — 1989. — Pp. 367-376.

64. Swami A., Gupta A. Optimization of large join queries // Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data. 1988. - Pp. 8-17.

65. Wang S., et al. Optimization of nested xquery expressions with order by clauses // ICDEW '05: Proceedings of the 21st International Conference on Data Engineering Workshops. — IEEE Computer Society, 2005.

66. Weiner A., Mathis C., Haerder T. Towards cost-based query optimization in native xml database management systems // Proceedings of the SYRCoDIS 2007 Colloquium on Databases and Information Systems. — 2008.67