Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

#662 Failing to optimize joins in SA

v8.9
closed
Michael Kay
5
2012-10-08
2007-02-28
Michael Kay
No

There are some cases of queries where Saxon-SA 8.9 should optimize a join to avoid O(n^2) performance, but fails to do so: including some cases where version 8.8 succeeded in the optimization.

Some of these cases occur because the optimizer relies on parent pointers in the expression tree to determine whether a filter expression occurs in a loop (because otherwise, it's not worth building an index); but there are some paths in the optimizer that leave an expression in the tree pointing to the grandparent rather than the parent, which means that the loop is not detected. It's difficult to be precise about the conditions that cause this: two situations that have been identified are (a) where some but not all the conditions for using a document-level index have been satisfied, and (b) where a "where" clause in a FLOWR expression cannot for some reason be replaced by a filter expression, but where the attempt to do so identifies other changes that can be made such as removing subexpressions from inner loops.

Another case where join optimization fails to occur is where the join condition involves variables - either explicit variables, or internal variables introduced by the optimizer while removing subexpressions from a loop. Some variables in the join condition should indeed prevent the rewrite taking place, but the current code is over-sensitive in this regard.

Fixing these problems requires patches to both the Saxon-B and Saxon-SA source code. The changes to the Saxon-B code are being placed in Subversion under this bug number. They affect modules Expression.java (a new method repairParentPointers()) and ForExpression.java (a call on that method).

Discussion

  • Michael Kay
    Michael Kay
    2007-03-15

    Logged In: YES
    user_id=251681
    Originator: YES

    Fixed in 8.9.0.3