Signs on the Sand

Here is interesting paper "XSLT and XPath Optimization" by Michael Kay. That's materials of Michael's talk at recent XML Europe conference. In this paper Michael reveals details of the XSLT and XPath optimizations performed internally by SAXON (XSLT and XQuery processor):

This paper describes the main techniques used by the Saxon XSLT and XQuery processor (http://saxon.sf.net/) to optimize the execution of XSLT stylesheets and XPath expressions, and reviews some additional XSLT and XPath optimization techniques that are not (yet) used in Saxon.

[Via XML.com]

Interesting quotes:

Parsing of XQuery is considerably more complex than XPath parsing, because of the need to switch between the different grammatical styles used in the query prolog, in conventional expressions, and in the XML-like element constructors. XSLT parsing, of course, is trivial, because the difficult part is done by an XML parser.

Most of the important static optimizations are done during the second phase, analyze(). These fall into a number of categories:

Early evaluation of constant sub-expressions (known, for some curious reason, as "constant folding"). This is another optimization that cannot be done if the result is sensitive to node identity. Constant sub-expressions are surprisingly common in XSLT, because global variables often have a constant value; and it is often possible to get rid of large chunks of stylesheet code by pre-evaluating a condition such as <xsl:if test="(system-property('xsl:vendor')='Xalan')">.

Local rewrites such as replacing count(X) = 0 by empty(X). (This avoids the need to distinguish a sequence with a thousand items from one with a thousand and one). These rewrites are local in the sense that they only require looking in the immediate vicinity of a node in the abstract syntax tree.

Early binding of polymorphic operators (especially comparison operators such as "=" and arithmetic operators such as "+") based on the types of their operands.

Adding code to do run-time type-checking and type conversion (such as atomization and numeric promotion) if static analysis shows that it is necessary. If static analysis shows that the supplied value will always have the required type, then this code is not generated.

Non-local rewrites. The most significant of these in Saxon is moving an expression out of a loop if it does not depend on any variables (range variables or context variables) that are set within the loop. A "loop" here can be a predicate, the right-hand side of the "/" operator, or the action part of a "for" expression. (Saxon does not at present do this optimization at the XSLT level, only at the XPath/XQuery level). This optimization too needs to be aware that creative expressions cannot always be safely moved.

Ordering rewrites. These fall into two categories: adding a sort, and removing it. This relates primarily to the requirement to deliver the results of certain expressions in document order. Saxon first adds a sort operator to the tree if the semantics require it and the expression is not "naturally sorted" (as determined using rules such as the peer/subtree rule given earlier). Then it removes the sort operator if the expression is used in a context where ordering is immaterial, for example an argument of one of the functions count(), max(), or of course unordered(). However, the scope for this is limited because in many contexts where there is no dependency on ordering, there is still a requirement to eliminate duplicates, and the simplest way to eliminate duplicates is by sorting.

Elimination of common subexpressions. Saxon currenly does this in only a few special cases, for example it rewrites the expression A/B/C | A/B/D as A/B/*[self::C or self::D]. In general, elimination of common subexpressions is greatly complicated by the need to consider dependencies on the context.

Firstly, there's a range of techniques that come under the heading of parallelism. Xalan, for example, has the parser and tree builder for the source document running in parallel with the transformation engine: if the stylesheet needs access to nodes that aren't there yet, the transformation engine waits until the parser has delivered them. The real saving here would come if it was also possible to discard parts of the tree once the stylesheet has finished with them. Unfortunately no-one seems close to solving this problem, even though many stylesheets do process the source document in a broadly sequential way.