Перезапись выражений
В теории реляционных баз данных термин оптимизация используется почти как синоним перезаписи запроса. Работа оптимизатора заключается в следующем: берется дерево, представляющее запрос в том виде, в котором он создан синтаксическим анализатором языка из первоначального текста запроса, и затем оно перестраивается в другое (но эквивалентное) дерево, анализ которого может быть осуществлен более эффективно. Для осуществления этого процесса используются многие стандарты методов, такие как приближение ограничений к листьям дерева. Выбор различных операторов для реализации функциональной возможности реляционного слияния был основной темой для научных журналов в течение почти тридцати лет.
Другим мощным средством, используемым оптимизатором XPath, также является перезапись выражений. Существуют два метода ее реализации. Первый вариант заключается в перезаписи выражения в терминах другого допустимого выражения XPath. Например, выражение a/b/c | a/b/d
может быть переписано в таком виде: a/b / (c|d)
(что является допустимым выражением в XPath 2.0, но не действительно в XPath 1.0).
Другим примером такой перезаписи будет выражение count($x) > 10, которое может быть переписано в виде exists($x [11]). Последнее выражение, вероятно, будет более эффективным, потому что (благодаря конвейерной обработке и отложенному вычислению) объекты, следующие за одиннадцатым по счету, вероятно, никогда не будут прочитаны. Перезаписи, которые удаляют подвыражения из цикла, можно также считать включенными в эту категорию. Например, выражение items[value > $customer/credit-limit]
может быть переписано следующим образом: let $x := $customer/credit-limit return items[value > $x]
И опять этот метод полагается на анализ зависимости, то есть на знании того, что подвыражение $customer/credit-limit не зависит от объекта контекста или положения контекста, которые сделали бы значение различным для различных объектов.
Второй вариант этого метода заключается в перезаписи выражения в терминах внутренних операторов, которые недоступны в формальном языке. Одним из самых выдающихся примеров является выражение $x[position() != last()]
которое может быть переписано как $x[hasNext()]
где hasNext() – это внутренняя функция, которая проверяет, имеются ли еще какие-либо объекты в конвейере. Красота этой перезаписи заключается в том, что в ней избегается обрыв конвейера. Когда в исходном выражении прочитывается первый объект, его положение (1) нужно сравнить с числом узлов в конвейере (возможно, тысячами), а это означает, что узлы должны быть подсчитаны. В переписанном выражении каждый узел просто проверяет, является ли он последним, для чего требуется упреждающее чтение только одного объекта.
В традиции реляционных баз данных наиболее значительными (т. е. наиболее выгодными) являются перезаписи, связанные с оптимизацией слияний, встречающихся в выражении SELECT языка SQL. Поэтому весьма вероятно, что производители программного обеспечения на основе XQuery затратят достаточно усилий на оптимизацию слияний, имеющихся в выражениях FLWOR, которые в XQuery являются эквивалентом выражения SELECT из SQL. Существует определенный риск, что эти усилия могут оказаться напрасными из-за способа, которым пользователи решат написать свои запросы. В реляционной модели все взаимоотношения моделируются с использованием первичных ключей и внешних ключей, и объединение по эквивалентности первичных и внешних ключей встречаются в запросах повсеместно. В отличие от этого в иерархическом мире XML многие взаимоотношения моделируются посредством отношений содержания: для представления порядка обработки порядковые строки не содержат порядковые номера, вместо этого они представлены в виде подэлементов. Поэтому слияние, которое является неизбежным в запросе SQL, заменяется в формулировке XQuery выражением пути.
Вместо
SELECT customer.name, order.date, order-line.value
FROM customer, order, order-line
WHERE customer.id = order.customer-id AND order-line.order-no =
order.order-no
мы, вероятно, увидим
for $c in /customers/customer,
$o in $c/order, $ol in $o/order-line
return $c/name, $ol/date, $o/value
В настоящий момент некоторые системы запросов, вероятно, неявно используют табличное хранение и выполнят этот запрос в виде слияния на основе значений даже при том, что не задается явных ключей слияния в запросе пользователя. Однако процессоры, использующие представление данных на основе структуры дерева, обработают запрос тем же самым способом, как и процессор XSLT – посредством обхода узлов дерева в глубину.
Конечно, оптимизация слияний играет важную роль в XQuery, особенно в тех случаях, когда на различных уровнях иерархии доступно множество индексов, что предоставляет широкий выбор путей доступа для выполнения одного и того же запроса. Слияния, относящиеся к данным, находящимся в разных документах, также могут быть очень важны. Но я подозреваю, что операция слияния будет намного менее важной по сравнению с ее значением в реляционных базах данных, и что оптимизация иерархических путей доступа – фактически выражений XPath – будет по крайней мере настолько же, а возможно, и более значимой.
Насколько мне известно, в процессорах XSLT до сих пор уделялось мало внимания оптимизации слияний. Я считаю, что для этого имеется несколько причин. Дизайн языка (с его вложенными инструкциями xslt:for-each и xslt:apply-templates) не делает запросы, содержащие слияния, легкими для обнаружения. В то же время тот факт, что дерево создается заново для каждого преобразования, означает отсутствие широкого выбора путей доступа. Но главная причина, как я подозреваю, заключается в том, что таблицы стилей, которые были изучены разработчиками XSLT для того, чтобы найти возможности для их оптимизации, выполняют очень небольшое число слияний. Их пути доступа в основ-ном следуют иерархическим отношениям, свойственным модели XML. Разработчики XQuery вступают в игру вооруженные огромным множеством инструментов для оптимизации, которые оказались полезными в мире реляционных данных. Только время покажет, насколько эффективными будут эти инструменты в мире XML.
