[xquery-talk] performance figures for xquery processors

[Michael Kay]

 > Also the
> > memory it consumes for the evaluation seems to be less
> > compared to Java5 xpath. For the same document and
> > same xpath expressions that lead to a large number of
> > results, the  java5 xpath expression evaluation was
> > eating up all the heap while saxon xquery processor
> > yielded the results. Since java5 does not support
> > xquery, i could not evaluate FLWOR expressions and
> > other xquery specific stuff. 
> 
> I think this is because Saxon does iterative execution.

With path expressions, it is generally true that Saxon adopts a pipelined
nested-loop evaluation strategy. For the vast majority of everyday path
expressions, I believe this is the best approach available. Note that in
most cases the total cost is linear, for example the cost of evaluating
a/b/c this way is proportional to the number of c descendants, and without
specialized access paths I don't think there is any way of doing it that is
better than linear. 

The main exception is probably an expression involving more than one "//"
operator (for example a//b//c where the b element is actually recursive --
because in this case the same c element will be visited more than once). But
I believe that such expressions are rare. There are a few other similar
expressions where better strategies are possible in theory, for example one
that arises in positional grouping algorithms is
following-sibling::x/preceding-sibling::y. It's always hard to know how much
effort to put into achieving a 100-fold speed-up of something that only
occurs in 0.1% of queries. (XSLT 2.0 handles positional grouping very
efficiently using for-each-group, and recursive solutions to positional
grouping also tend to be linear, but I guess we'll still see such constructs
from recursion-averse users in XQuery).

Some path expressions can be speeded up by creating specialized access paths
(indexes etc). For a processor that's designed to operate on transient
in-memory documents this is a strategy that can easily backfire - it can
easily take longer to construct the access path than to find the data "the
hard way". The main case where Saxon does this is with "//x", where in
effect Saxon evaluates the construct as a memo function. There's a net loss
if you only evaluate the expression once.

> (While iteration breaks at fs:distict-doc-order, and so on.)

Saxon goes to considerable lengths to identify path expressions where
sorting is not needed, which is true for the vast majority of path
expressions. Where sorting is needed, it is done once, at the end. Clearly
in this case you have to break the pipeline and allocate memory.
> 
> Iterative execution requires more memory spaces in total,

I don't understand this comment. What is the memory used for, and what
strategy are you comparing with?

> but the required memory size for intermediate result is 
> relatively small.
> 
> Iterative execution space efficient, but time inefficient
> (It is actually nested-loop).

Except in unusual cases like those outlined where a nested loop finds
duplicates that then need to be eliminated, I don't believe that nested loop
evaluation of path expressions is less efficient than other strategies. Of
course a lot depends on your data structure.
> 
> Last year, I was tried to benchmark several (free)
> XQuery processors using XMark.

XMark is all about optimizing relational-style joins, it tells you very
little about evaluation of path expressions. Saxon-B is definitely inferior
to some other XQuery engines in its relational join capabilities: this is
because of its XSLT history, where people tackle join problems using
explicitly-declared keys. But there are substantial improvements in
Saxon-SA. Interestingly this has brought considerable benefits in XSLT
processing as well, especially for stylesheets that haven't been carefully
tuned.

Michael Kay
http://www.saxonica.com/