XSLT and XPath Optimization

| 2 Comments | 1 TrackBack

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.
A must reading for those developing or thinking to develop XPath/XQuery/XSLT plumbing.

[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.

Related Blog Posts

1 TrackBack

TrackBack URL: http://www.tkachenko.com/cgi-bin/mt-tb.cgi/240

Take Outs for 13 May 2004 from Enjoy Every Sandwich on May 14, 2004 7:45 AM

Take Outs for 13 May 2004 Read More


Well, unfortunately I share the same thoughts. The only workaround I can imagine is avoiding numerous templates for doing substitutions. I'd try xsl:key loopup instead of template matching may be.

It is too little said in the Internet about how different XSLT processors do match templates. As I deal with large XSLT transformations it was easy to note that .NET XSLT does loop over all templates in priority order to find appropriate template and MSXML does some optimizations to index similiar match with similiar structure (the same attribute checked for different values) or just match for element name. I tis very disappointing that adding 100 templates with match to a stylesheet with 100 templates slows it down twice. The same changes the performance of stylesheet in MSXML just by 1%. The only thing that help is spreading templates into different modes where it is possible, but sometimes it is necessary to run identity transformation handling more than 100 substitutions. Is there anything else that can be done to improve matching performance? Meanwhile, performance degradation is uch more noticable on stylesheet size growing rather than on source XPathDocument growing.

Leave a comment