Исполнение запросов

Как показывает рис. 1, план выполнения любого запроса XQuery , произведенный компилятором и оптимизатором, передается на дальнейшую обработку исполнителю. Исполнитель интерпретирует план выполнения запроса, представляющий собой дерево физических операций над системой хранения, которые взаимодействуют по данным в конвейерном режиме. Набор поддерживаемых в СУБД Sedna физических операций покрывает функциональность XQuery library [3] и XQuery Core . Однако этот базовый набор операций, соответствующий модели данных XQuery , не обеспечивает возможность поддержки всех разумных планов выполнения запросов. В дополнение к физическим эквивалентам понятий модели данных XQuery на физическом уровне в СУБД Sedna используются кортежи , упорядоченные наборы атомарных значений или указателей на дескрипторы узлов. Использование кортежей позволило расширить используемый набор физическими операциями, подобными операциям соединения и группировки SQL .

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

Конструкторы элементов

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

Проведенные исследования [8] показали, что для представительного класса XQuery -запросов глубокое копирование вообще не требуется. Большинство XQuery -запросов можно перезаписать таким образом, что в плане выполнения запроса выше конструкторов элементов не будут присутствовать операции, анализирующие содержимое элементов.

Различные стратегии выполнения XPath-запросов

Использование описывающей схемы в качестве индексной структуры позволяет избежать обхода дерева и ускорить выполнение запроса. Например, рассмотрим XPath -запрос // title к XML -документу, представленному на рис. 1. Мы называем подобные запросы структурными путевыми запросами , потому что в них используется только информация о структуре XML -документа, и для выполнения запроса не требуется производить какие-либо проверки, связанные с данными. Для выполнения структурных запросов идеально подходит описывающая схема.

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

В качестве еще одного примера, рассмотрим возможные стратегии выполнения запроса / library / book [ issue / year =2004]/ title . Как и в случае предыдущего запроса, можно выбрать элементы / library / book с использованием описывающей схемы, а затем применить предикат и выполнить оставшуюся часть запроса с использованием указателей на данные. Но более эффективным является следующий алгоритм. Сначала вычисляется структурная часть запроса: / library / book / issue / year / text () . Затем применяется предикат (выбираются только те узлы, для которых text =2004 ). И, наконец, к результату этого шага применяется запрос ../../../ title .

Сочетание ленивой и строгой семантики

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

Принимая во внимание функциональную природу языка XQuery , можно относиться к итеративной модели, как к реализации ленивой ( lazy ) семантики. Если же относиться к XQuery и как к языку программирования общего назначения, который может применяться для выражения логики приложений, реализация только ленивой семантики может отрицательно сказаться на общей эффективности исполнителя. Для обеспечения реализации XQuery , достаточно эффективной при обработке и запросов, и логики приложений, в исполнителе СУБД Sedna сочетаются две модели исполнения.

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

содержание       назад       вперед