Example of XQuery expression evaluation is not sequential

Question

I am looking for an example which shows that XQuery expression evaluation is not sequential. It is always mentioned when comparing the functional nature of XQuery with procedural languages.

E.g. in XQuery, 2nd edition, in the section below:

The FLWOR expression with its for clause is similar to loops in procedural languages such as C. However, one key difference is that in XQuery, because it is a functional language, the iterations are considered to be in no particular order. They do not necessarily occur sequentially, one after the other.

score 6 · Accepted Answer · answered Oct 18 '19 at 13:52

In general, the language is designed so that you can't tell what the order of evaluation is, which makes it difficult to demonstrate that it's not what you expect. To observe the actual order of evaluation, you need to do something that has side-effects, which generally means straying outside the language specification and using vendor extensions. For example you could use the EXPath file module and issue calls to file:append-text(), and then examine the order of entries added to the external text file.

Of course, it wouldn't prove anything if the entries in the file are in exactly the order you expect. Query processors aren't going to use a non-obvious order of execution just for the fun of it. They will only do so if there is something to be gained by changing the order. Saxon, for example, will delay evaluating variables until they are used, and will lift expressions out of a loop if it can. But you then have the problem, that if you use functions with side-effects like file:append-text() to observe this behaviour, Saxon might detect that your code has side-effects and suppress the optimization.

Martin Honnen · Answer 2 · 2019-10-18T12:22:30.930

In some implementations you can experience that the order of the result in more complex FLOWR expressions is arbitrary, for instance taking an example from Priscilla Walmsley's book http://www.datypic.com/books/xquery/ a grouping of item elements ('order.xml' in http://www.datypic.com/books/xquery/chapter01.html) with

<order num="00299432" date="2015-09-15" cust="0221A">
  <item dept="WMN" num="557" quantity="1" color="navy"/>
  <item dept="ACC" num="563" quantity="1"/>
  <item dept="ACC" num="443" quantity="2"/>
  <item dept="MEN" num="784" quantity="1" color="white"/>
  <item dept="MEN" num="784" quantity="1" color="gray"/>
  <item dept="WMN" num="557" quantity="1" color="black"/>
</order>

in Saxon 9.8 HE with the code (7.11 in http://www.datypic.com/books/xquery/chapter07.html)

declare namespace output = "http://www.w3.org/2010/xslt-xquery-serialization";

declare option output:method 'xml';
declare option output:indent 'yes';

for $item in //item
group by $d:= $item/@dept, $n:= $item/@num
return <group dept="{$d}" num="{$n}" count="{count($item)}"/>

gives the output

<?xml version="1.0" encoding="UTF-8"?>
<group dept="ACC" num="563" count="1"/>
<group dept="MEN" num="784" count="2"/>
<group dept="WMN" num="557" count="2"/>
<group dept="ACC" num="443" count="1"/>

while for instance with BaseX you might get a different output order (I think based on the input order of items if I remember it correctly) for the group elements, for instance in BaseX 9 I get

<group dept="WMN" num="557" count="2"/>
<group dept="ACC" num="563" count="1"/>
<group dept="ACC" num="443" count="1"/>
<group dept="MEN" num="784" count="2"/>

Note that this is a slightly different situation. With the expression `for $x in 1 to 5 return $x+1` you are guaranteed to get the result (2,3,4,5,6) in that order; but it's undefined what order the additions are done in to achieve that result. With grouping, the spec not only leaves the internal order of evaluation up to the implementation, it also gives the implementation discretion on the order of the final results. — Michael Kay, Oct 18 '19 at 13:54
Thank you Martin Honnen for the answer and @Michael Kay for the comment, these further clarify the behavior. — TFuto, Oct 21 '19 at 12:17

Example of XQuery expression evaluation is not sequential

2 Answers2