Saxon

Actually the script is compiling and running a set of 43,000 path expressions (a 5% sample of the original).

I found by accident that running these under XPath, the execution time is around 50s, but under XQuery, it is around 5s.

The difference between the two cases appears to be that when many XPath expressions are processed using the same XPathCompiler, the same KeyManager is used each time, whereas under XQuery, a new KeyManager is used each time.

In principle using the same KeyManager ought to be better, because it means that when two searches search on the same thing, the index that is constructed to support the first search can be reused for the second. The problem appears to be that discovering that the index is reusable is taking longer than rebuilding it from scratch. The time is spent comparing expressions for equality, which involves a deep walk of the expression tree.

The main reason that the cost of searching for an existing index exceeds the benefit is that the search usually fails (11540001 out of 11540877 searches are unsuccessful).

The other reason is that comparing expressions is expensive even when it fails.

Finally, it's not at all clear why we are doing quite so many searches.

Two expressions that are actually equal are comparing not equal: the culprit is SubscriptExpression which uses "==" rather than "equals()" on one of the operands.

The effect is that rather than using an existing index, a new one is created. When this is done 1000 times, we have a list of 1000 indexes to search before creating the next one, so the effect is quadratic.

Fixing the equality test on SubscriptExpression brings the XPath execution time down to 9.5s, which is still slower than the XQuery time, but much more acceptable. We are still getting a lot of Expression.equals() activity, but nothing like so much. We now have 74K pattern comparisons of which 66K are unsuccessful, and the number of indexes built is just 28.

It looks as if the search for an index using a particular pattern would benefit from a hash lookup of some kind.

I have fixed the XPath performance issue (it now runs a little faster than XQuery) by the following two changes:

(a) correct the logic for SubscriptExpression.equals()

(b) introduce a lazily-evaluated hashcode on the Expression object and use this when comparing expressions for equality.

The hotspot (30% of execution time) is now AxisExpression.typeCheck(). I improved this slightly (c) by avoiding some of the checks if the contextItemType is a NodeTest. But I can gain pretty well 30% in bottom line execution time by (d) disabling the "checkPlausibility()" method, whose effect is almost entirely to check for "void" path expressions like child::attribute(). This sounds like a useful configuration option.

There are no other obvious hot-spots. The profiling identifies a few opportunities for getting a percentage point off here and there, for example by:

(e) In UnaryExpression and BinaryExpression, avoiding the general iteration over operands() when typechecking, and just typechecking the fixed child expressions explicitly

(f) avoiding scanning the expression tree to look for updating expressions if updating wasn't enabled in the query parser

These changes aren't appropriate in a maintenance release but I'll consider them for the next major release.