This is an archived snapshot of W3C's public bugzilla bug tracker, decommissioned in April 2019. Please see the home page for more details.

Bug 10651 - Optimisation avoiding sorts (K2-OrderbyExprWithout-10 & K2-OrderbyExprWithout-40)
Summary: Optimisation avoiding sorts (K2-OrderbyExprWithout-10 & K2-OrderbyExprWithout...
Status: CLOSED FIXED
Alias: None
Product: XML Query Test Suite
Classification: Unclassified
Component: XML Query Test Suite (show other bugs)
Version: unspecified
Hardware: PC All
: P2 normal
Target Milestone: ---
Assignee: Benjamin Nguyen
QA Contact: Mailing list for public feedback on specs from XSL and XML Query WGs
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-09-18 21:00 UTC by Martin Probst
Modified: 2010-10-19 15:10 UTC (History)
0 users

See Also:


Attachments

Description Martin Probst 2010-09-18 21:00:39 UTC
K2-OrderbyExprWithout-10 looks like this:

  for $a in (1, 4, 2)
  let $i := (1, 3, 2)
  order by $i
  return $i

The test tries to cause an order by with an order spec that is a sequence of items, and thus expects XPTY0004.

However, an XQuery engine might find out that the order spec expression $i is constant over the whole tuple sequence. Thus, the engine can evaluate the whole query without doing any sort, thus avoiding the error at all and yielding (1, 3, 2, 1, 3, 2, 1, 3, 2) as the result. Or actually, those values in any order because the ordering of the sequence is undefined as the order spec will always give identical values.

I think that is a legal optimisation according to the dreaded "Errors and Optimizations" section. While the implementation has to evaluate $i to yield the return value, in the context of the order by expression it does not need to evaluate the sequence at all, so it is free to swallow the error and give a result. Also, apart from legalese, I think this is the kind of optimisation that section wants to allow.

I suggest changing the query so that the $i part depends on $a, which means the sort factor for the tuple sequence is not constant over the whole query:

  for $a in (1, 4, 2)
  let $i := (1, $a, 2)
  order by $i
  return $i

The same applies to K2-OrderbyExprWithout-40, which is a more complicated expression but has the exact same problem and solution.
Comment 1 Andrew Eisenberg 2010-09-27 20:42:58 UTC
You say:

"Thus, the engine can evaluate the whole
query without doing any sort, thus avoiding the error at all and yielding (1,
3, 2, 1, 3, 2, 1, 3, 2) as the result. Or actually, those values in any order
because the ordering of the sequence is undefined as the order spec will always
give identical values."


I understand your argument that the order by does not need to be evaluated, as its argument is unchanging. I don't see the justification for any result other than (1, 3, 2, 1, 3, 2, 1, 3, 2) if an error is not returned.
Comment 2 Martin Probst 2010-09-28 06:51:49 UTC
The query processor can statically determine that the order by specification will always yield an identical value for each iteration of the loop. This means the order by doesn't influence the order of the result.

However according to the specification, for a non-stable order, the relative order of two tuples in the tuple stream is undefined if their order by specs are identical (i.e., not < or >).

That means, the processor is free to return the sequence of tuples in any order.

Of course with this query, there isn't any reason to do that, but if you had a complicated path expression that would require intermediate sorting, this could very well happen.

In any case, this is just a silly query. Making the let clause depend on the for binding will fix the issue and test what the author originally wanted to test, so we should just fix it.
Comment 3 Benjamin Nguyen 2010-10-18 11:16:34 UTC
Tests K2-OrderbyExprWithout-10 and K2-OrderbyExprWithout-40 have been modified in the test suite. Test -10 is the same as the one proposed by Martin, and I wrote -40 like this : 

for $a in (3, 2, 1)
let $a := ($a, 1),
$b := (2, 1),
$c := (2, 1),
$d:= (2, 1)
order by $a
return $a

I think that this fixes the bug.
Comment 4 Martin Probst 2010-10-18 11:22:22 UTC
Confirmed.
Comment 5 Martin Probst 2010-10-19 15:10:37 UTC
Closing.