Saxon

Running with -repeat:50 and ignoring query analysis time, I'm seeing the following timings for the larger input file. Where there are two figures, I measured it twice to check consistency:

9.0 421ms

9.2 406ms

9.3 395ms 410ms

9.4 524ms

9.5 555ms

9.6 547ms

9.7 770ms 757ms

9.8 663ms 672ms

So yes, for this particular query there's been a fair bit of variation between releases, with 9.7 definitely showing regression, and some of this being pulled back in 9.8.

I'm going to focus on 9.8 for investigation. While we are still supporting 9.7, we are managing that release for maximum stability and a fairly minor performance issue like this one would not justify intervention unless we discover from the 9.8 study that there's something that's very simple to correct.

The Java profile for 9.8 shows that the performance is heavily dominated by sorting - probably sorting nodes into document order. There is also a fair bit of sorting happening in the 9.3 trace, but it is far less dominant. (General observation about this query: none of the functions declare the types of their arguments, so there's no type information for the optimizer to work with. So the generated code is always going to assume the worst case.)

Internal tracing in Saxon shows that we are doing exactly 4000 sort operations, each of exactly 1000 or 2000 items.

The sorting seems to be happening at line 4

for $out_root_outloop_outloop_1_c at $out_root_outloop_outloop_1_c_i in 
  let $inVar := $top/root/inloop/inloop_1 return  $inVar

which Saxon has simplified to

for $out_root_outloop_outloop_1_c at $out_root_outloop_outloop_1_c_i in 
  $top/root/inloop/inloop_1

Internally this appears as

for $out_root_outloop_outloop_1_c at $out_root_outloop_outloop_1_c_i in 
   docOrder((docOrder((ConditionalSorter(exists(tail(($top) treat as node())), docOrder((($top) treat as node())/child::element(Q{}root))))/child::element(Q{}inloop)))/child::element(Q{}inloop_1))

The ConditionalSorter is an internal expression which effectively says "if $top is a singleton then return $top!root!inLoop!inLoop1 else return sort($top!root!inLoop!inLoop1) - it's designed to avoid the sort in the case where $top is a singleton node -- which is expressly designed to deal with queries like this one in which users haven't taken the trouble to declare the static type of the variable. However, this is then thwarted by the result being wrapped in a call of docOrder(), which does the sort anyway. This outer call of docOrder should be eliminated as unnecessary, so we need to see why this isn't happening.

At an intermediate stage of optimization, we have an expression such as

Sort (
    ConditionalSort( $var/child::x ) / child::y
)

and the optimizer is not recognizing that the outer Sort is unnecessary. In fact, if $var returns multiple nodes and they are not a peer node-set (one node is an ancestor of another), then the outer sort might indeed be necessary.

We should be rewriting this expression as

ConditionalSort($var / (child::x/child::y) )

Either that, or we should avoid creating it in the first place, but that's probably more difficult. The performance regression is probably because at at earlier release the path expression x/y/z was held in left-associative rather than right-associative form, both of which have their merits for different purposes).

I've implemented this rewrite and it brings the execution time down to 12ms

The same improvement can be achieved in Saxon 9.7 by modifying the query to declare the first function with "$top as node()" (thus saving the optimizer a lot of effort).

This is outstanding. Thank you! As a side note, your web site mentions "Saxon 9.7 is currently considered the most stable and reliable release", is this still accurate?

9.8 is getting there, but the bug rate is still a bit higher than I would like before recommending people to move forward unless they actually need something in the new version (the best reason for moving forward is because you are using XSLT 3.0 or XQuery 3.1). Furthermore, as this issue demonstrates, we are still prepared to take a few risks in making inessential changes on this release branch, which we will stop doing once it becomes the recommended most stable release.