Конвейерная обработка и отложенное вычисление
Часто кажется, что мир функциональных языков программирования, таких как Schema и Haskell, и мир систем управления базами данных имеют мало общего. Но теория в обеих областях имеет нечто общее: идею конвейерной обработки. Терминология может различаться, но сама идея остается одной и той же.
В реляционной модели запрос SQL может быть переведен в выражения реляционной алгебры с использованием таких операций, как ограничение, проекция, объединение, сортировка и слияние. Все эти операции работают в режиме последовательной обработки наборов записей: каждое действие принимает на входе множества кортежей и производит множества (или иногда последовательности) кортежей в качестве своего результата. Фактическое размещение в памяти всех этих множеств кортежей было бы очень ресурсоемким методом. Динамическое распределение памяти является ресурсоемким процессом, а память – ограниченным ресурсом: если использовать больший объем памяти для промежуточных результатов, то меньший ее объем будет доступен для других целей, таких как кэширование. Те же самые факторы применимы к функциональным языкам про-граммирования, основанным на манипуляциях со списками, и одинаково справедливы для XPath, семантика которого определена в терминах множеств узлов. Размещение этих наборов в памяти является очень дорогостоящим процессом.
Технология, используемая для избежания выделения памяти под промежуточные результаты, называется конвейерной обработкой. Способ действия конвейерной обработки заключается в том, что любая операция, например, ограничение, реализована таким образом, чтобы на запрос другой операции возвращался только один объект, и в свою очередь один объект запрашивался бы от зависимых операторов. Дерево операторов, которое составляет выражение SQL или XPath, таким образом представлено во время выполнения последовательностью так называемых итераторов, каждый из которых поддерживает операцию get-next, возвращающую следующий объект в потоке. В реляционной системе объекты являются кортежами, и конвейер описан в терминах движения потока кортежей, поставляемых одним узлом в дереве выражения своему родительскому узлу в дереве выражения.
Не все операции XPath могут быть включены в конвейер. Очевидным примером является функция last(): чтобы определить значение функции last() в выражении типа $x[last() idiv 2] (которое возвращает объект в середине последовательности), вы должны знать, сколько объектов возвращает текущая операция, и единственный путь определения этого количества состоит в том, чтобы прочитать их все. Это нарушает конвейер и поэтому является затратным по использованию ресурсов действием. На практике существуют две стратегии реализации функции last(). Первая заключается в вычислении содержащегося выражения (в данном случае – $x) один раз и сохранении результата в памяти. Вторая заключается в том, что содержащееся выражение вычисляется дважды: первый раз для подсчета узлов и второй раз для передачи их следующему оператору в конвейере. Иногда лучше ис-пользовать первый вариант, иногда – второй: это является тем решением, при приня-тии которого имеет значение качество оптимизатора.
Другим обычным действием, нарушающим конвейер, является сортировка. Одна из технологий, часто используемых оптимизаторами, заключается в перезаписи выражения таким образом, чтобы сортировка выполнялась в последнюю очередь. Это часто может уменьшить число объектов, которые будут отсортированы, и может устранить необходимость многократных сортировок. Например, для выражениий XPath, записанных в форме a/b/c, семантика языка гарантирует, что результаты будут находиться в порядке документа. Но нет никакой необходимости сортировать промежуточные результаты выражения a/b (или b/c, в зависимости от стратегии вычисления). Полное выражение пути может быть вычислено в одном конвейере и отсортировано в самый последний момент.
Выражение пути часто может быть вычислено вообще без выполннения сортировки. Процессоры XSLT, подобные Saxon, имеют по крайней мере три метода, позволяющие избежать сортировки:
- Выполнение статического анализа выражения пути для определения того, что результаты «естественным образом» отсортированы: то есть при вычислении с использованием «очевидной» стратегии вычисления результаты будут автоматически находиться в порядке документа. Правила для этой технологии являются весьма тонкими; не всегда очевидно, например, что в то время как оба выражения //b и a/b/c являются естественным путем отсортированными, выражение //b/c таковым не является.
- Вычисление инвертированных осей в прямом порядке, чтобы сделать выражение естественным образом отсортированным, когда иначе оно таковым бы не являлось.
- Обнаружение контекста, в котором используется выражение пути для того, чтобы осознать, что хотя семантика языка требует сортировать результаты, в некоторых контекстах это никак не влияет на результат. Очевидными примерами являются выражения, в которых выражение пути используется в качестве аргумента таких функций, как count(), sum() или boolean(). В XQuery такое положение также возникает в том случае, когда выражение пути используется в пределах выражения FLWOR, которое имеет оператор ORDER BY для определения порядка результатов. Однако здесь имеется и другая тонкость: для некоторых функций, таких как count(), требуется удаление дубликатов узлов из результата, тогда как для других, таких как boolean(), это не требуется.
- Выполнение статического анализа выражения пути для определения того, что результаты «естественным образом» отсортированы: то есть при вычислении с использованием «очевидной» стратегии вычисления результаты будут автоматически находиться в порядке документа. Правила для этой технологии являются весьма тонкими; не всегда очевидно, например, что в то время как оба выражения //b и a/b/c являются естественным путем отсортированными, выражение //b/c таковым не является.
Часто кажется, что мир функциональных языков программирования, таких как Schema и Haskell, и мир систем управления базами данных имеют мало общего. Но теория в обеих областях имеет нечто общее: идею конвейерной обработки. Терминология может различаться, но сама идея остается одной и той же.
В реляционной модели запрос SQL может быть переведен в выражения реляционной алгебры с использованием таких операций, как ограничение, проекция, объединение, сортировка и слияние. Все эти операции работают в режиме последовательной обработки наборов записей: каждое действие принимает на входе множества кортежей и производит множества (или иногда последовательности) кортежей в качестве своего результата. Фактическое размещение в памяти всех этих множеств кортежей было бы очень ресурсоемким методом. Динамическое распределение памяти является ресурсоемким процессом, а память – ограниченным ресурсом: если использовать больший объем памяти для промежуточных результатов, то меньший ее объем будет доступен для других целей, таких как кэширование. Те же самые факторы применимы к функциональным языкам про-граммирования, основанным на манипуляциях со списками, и одинаково справедливы для XPath, семантика которого определена в терминах множеств узлов. Размещение этих наборов в памяти является очень дорогостоящим процессом.
Технология, используемая для избежания выделения памяти под промежуточные результаты, называется конвейерной обработкой. Способ действия конвейерной обработки заключается в том, что любая операция, например, ограничение, реализована таким образом, чтобы на запрос другой операции возвращался только один объект, и в свою очередь один объект запрашивался бы от зависимых операторов. Дерево операторов, которое составляет выражение SQL или XPath, таким образом представлено во время выполнения последовательностью так называемых итераторов, каждый из которых поддерживает операцию get-next, возвращающую следующий объект в потоке. В реляционной системе объекты являются кортежами, и конвейер описан в терминах движения потока кортежей, поставляемых одним узлом в дереве выражения своему родительскому узлу в дереве выражения.
Не все операции XPath могут быть включены в конвейер. Очевидным примером является функция last(): чтобы определить значение функции last() в выражении типа $x[last() idiv 2] (которое возвращает объект в середине последовательности), вы должны знать, сколько объектов возвращает текущая операция, и единственный путь определения этого количества состоит в том, чтобы прочитать их все. Это нарушает конвейер и поэтому является затратным по использованию ресурсов действием. На практике существуют две стратегии реализации функции last(). Первая заключается в вычислении содержащегося выражения (в данном случае – $x) один раз и сохранении результата в памяти. Вторая заключается в том, что содержащееся выражение вычисляется дважды: первый раз для подсчета узлов и второй раз для передачи их следующему оператору в конвейере. Иногда лучше ис-пользовать первый вариант, иногда – второй: это является тем решением, при приня-тии которого имеет значение качество оптимизатора.
Другим обычным действием, нарушающим конвейер, является сортировка. Одна из технологий, часто используемых оптимизаторами, заключается в перезаписи выражения таким образом, чтобы сортировка выполнялась в последнюю очередь. Это часто может уменьшить число объектов, которые будут отсортированы, и может устранить необходимость многократных сортировок. Например, для выражениий XPath, записанных в форме a/b/c, семантика языка гарантирует, что результаты будут находиться в порядке документа. Но нет никакой необходимости сортировать промежуточные результаты выражения a/b (или b/c, в зависимости от стратегии вычисления). Полное выражение пути может быть вычислено в одном конвейере и отсортировано в самый последний момент.
Выражение пути часто может быть вычислено вообще без выполннения сортировки. Процессоры XSLT, подобные Saxon, имеют по крайней мере три метода, позволяющие избежать сортировки:
Хотя устранение сортировки полезно хотя бы потому, что сортировка является ресурсоемким процессом, основной пользой от ее устранения является улучшение конвейерной обработки.
С конвейерной обработкой тесно связана другая технология, известная из литературы по функциональному программированию: отложенное вычисление. Принципом отложенного вычисления является избежание выполнения действий до тех пор, пока их результаты не станут действительно необходимы. Такой подход имеет следующие преимущества. Во-первых, вам не требуется память для хранения результатов. Во-вторых, вы можете обнаружить, что результаты могут вообще не потребоваться на практике.
В листинге 3.3 приведен простой пример работы отложенного вычисления в XSLT.
Листинг 3.3. Пример отложенного вычисления в XSLT <xslt:param name="account-nr"/> <xslt:template match="/"> <xslt:variable name="transactions" select="/*/transaction[account=$account-nr]"/> <xslt:choose> <xslt:when test="starts-with($account-nr, 'Z’)"> <xslt:value-of select="closing-balance"/> </xslt:when> <xslt:otherwise> <xslt:value-of select="opening-balance + sum($transactions/value)"/> </xslt:otherwise> </xslt:choose> </xslt:template>
Инструкция xslt: variable потенциально является трудоемкой для вычисления: она включает выбор всех транзакций для данного счета, что, вероятно, означает необходимость просмотра всего исходного документа. А теперь посмотрите, как используется результат. В одной ветви условия xslt:choose переменная вообще не используется. В другой ветви она используется только в качестве аргумента функции sum(). Это означает, что путем задержки вычисления переменной до тех пор, пока она фактически не будет использована, мы могли бы вообще избежать вычисления ее значения; и даже если нам потребуется такое вычисление, мы можем включить его в конвейер таким образом, чтобы не было необходимости хранить в памяти список элементов transaction, и мы, конечно, можем избежать сортировки результатов.
Хитроумной частью отложенного вычисления является тот факт, что значение выражения XPath зависит от контекста, в котором оно появляется (текущий узел, значения других переменных, пространства имен, которые находятся в области видимости), поэтому значимые части контекста должны быть сохранены, так же как и само выражение. Это означает, что важной ролью оптимизатора XPath является определение зависимостей выражения – частей контекста, от которых оно зависит и которые должны быть сохранены при выполнении отложенного вычисления.
Конвейерная обработка и отложенное вычисление, вероятно, будут столь же важными для процессора XQuery, как и для процессоров XSLT и XPath.
Хотя устранение сортировки полезно хотя бы потому, что сортировка является ресурсоемким процессом, основной пользой от ее устранения является улучшение конвейерной обработки.
С конвейерной обработкой тесно связана другая технология, известная из литературы по функциональному программированию: отложенное вычисление. Принципом отложенного вычисления является избежание выполнения действий до тех пор, пока их результаты не станут действительно необходимы. Такой подход имеет следующие преимущества. Во-первых, вам не требуется память для хранения результатов. Во-вторых, вы можете обнаружить, что результаты могут вообще не потребоваться на практике.
В листинге 3.3 приведен простой пример работы отложенного вычисления в XSLT.
Листинг 3.3. Пример отложенного вычисления в XSLT <xslt:param name="account-nr"/> <xslt:template match="/"> <xslt:variable name="transactions" select="/*/transaction[account=$account-nr]"/> <xslt:choose> <xslt:when test="starts-with($account-nr, 'Z’)"> <xslt:value-of select="closing-balance"/> </xslt:when> <xslt:otherwise> <xslt:value-of select="opening-balance + sum($transactions/value)"/> </xslt:otherwise> </xslt:choose> </xslt:template>
Инструкция xslt: variable потенциально является трудоемкой для вычисления: она включает выбор всех транзакций для данного счета, что, вероятно, означает необходимость просмотра всего исходного документа. А теперь посмотрите, как используется результат. В одной ветви условия xslt:choose переменная вообще не используется. В другой ветви она используется только в качестве аргумента функции sum(). Это означает, что путем задержки вычисления переменной до тех пор, пока она фактически не будет использована, мы могли бы вообще избежать вычисления ее значения; и даже если нам потребуется такое вычисление, мы можем включить его в конвейер таким образом, чтобы не было необходимости хранить в памяти список элементов transaction, и мы, конечно, можем избежать сортировки результатов.
Хитроумной частью отложенного вычисления является тот факт, что значение выражения XPath зависит от контекста, в котором оно появляется (текущий узел, значения других переменных, пространства имен, которые находятся в области видимости), поэтому значимые части контекста должны быть сохранены, так же как и само выражение. Это означает, что важной ролью оптимизатора XPath является определение зависимостей выражения – частей контекста, от которых оно зависит и которые должны быть сохранены при выполнении отложенного вычисления.
Конвейерная обработка и отложенное вычисление, вероятно, будут столь же важными для процессора XQuery, как и для процессоров XSLT и XPath.