unordered {} and fn:unordered()

[Bas de Bakker]

Unordered has gone through a lot of changes: function, expression, now 
both. When I implemented one of the earlier proposals for X-Hive/DB it 
certainly helped a lot in some queries and I'm sure it still does, as 
does the optimization of using unordered evaluation for arguments of 
count() and such.

In X-Hive/DB, queries that scan all data do so in document order, so 
results are created in document order and unordered() does not help. But 
queries that are evaluated with indexes produce results that are not in 
document order and if there are many results sorting them takes a 
significant amount of time. I don't have any performance numbers at 
hand, sorry.

In the now ancient version 3 of X-Hive/DB the nodes belonging to a 
particular index key were maintained in document order in the index. 
This did speed up some queries, but updating the index was so slow that 
we dropped this approach.

Regards,
Bas de Bakker
X-Hive Corporation


Torsten Grust wrote:
> Dear all,
> 
>    the W3C XQuery Candidate Recommendation says (quoting from
> http://www.w3.org/TR/xquery/#id-unordered-expressions):
> 
> ''For expressions where the ordering of the result is not significant, a
> performance advantage may be realized by setting the ordering mode to
> unordered, thereby granting the system flexibility to return the result
> in the order that it finds most efficient.''
> 
> I am wondering whether you have noticed that your favorite XQuery
> processor indeed realizes such an advantage when it processes
> expressions of the form unordered {e} or fn:unordered(e)?
> 
> (There are, of course, a lot more scenarios in XQuery where order
> doesn't matter, e.g., the existential semantics of general comparison
> operators, aggregate functions (fn:max(), ...), other builtin functions
> (fn:empty(), ...), FLWORs whose result is explicitly reordered via
> 'order by', etc.)
> 
> Proper order maintenance can significantly impact query performance -- I
> think this is something we can all agree upon.  (Can we?)  The margin of
> what can be gained from ''unorderedness'' thus should be noticable.
> 
> Curious,
>     --Torsten
> --
>    | Prof. Dr. Torsten Grust                         http://xquery.com/mailman/listinfo/talk |
>    |                                 http://www-db.in.tum.de/~grust/ |
>    |     Database Systems - Technische Universität München (Germany) |
> _______________________________________________
> http://xquery.com/mailman/listinfo/talk
> http://xquery.com/mailman/listinfo/talk
>