Short-circuit logic in optimizer appears to be incorrect...

• Key: DERBY-1357
• Type: Bug
• Status: Closed
• Resolution: Fixed
• Priority: Minor
• Assignee: A B
• Reporter: A B
• Affects Version/s: 10.0.2.0, 10.0.2.1, 10.1.1.0, 10.1.2.1, 10.1.3.1, 10.2.1.6
• Fix Version/s: 10.2.1.6

Description

When considering different join orders for the FROM tables in a query, the optimizer will decide to give up on a join order midway through if the cost of that (partial) join order is already higher than the cost of some other *complete* join order that the optimizer previously found. This "short-circuiting" of a join order can save compilation time.

That said, the logic to perform this "short-circuit" of a join order is currently as follows (from OptimizerImpl.java):

  /*
  ** Pick the next table in the join order, if there is an unused position
  ** in the join order, and the current plan is less expensive than
  ** the best plan so far, and the amount of time spent optimizing is
  ** still less than the cost of the best plan so far, and a best
  ** cost has been found in the current join position. Otherwise,
  ** just pick the next table in the current position.
  */
  boolean joinPosAdvanced = false;
  if ((joinPosition < (numOptimizables - 1)) &&
    ((currentCost.compare(bestCost) < 0) ||
    (currentSortAvoidanceCost.compare(bestCost) < 0)) &&
    ( ! timeExceeded )
    )
  {
    ...
  }

There are two "current costs" in this statement: one for the cost if the optimizer is calculating a "sort avoidance" plan (which it does if there is a required row ordering on the results) and one if it is calculating a plan for which row order is not important.

I admit that I'm not all that familiar with what goes on with the costing of a sort-avoidance plan, but inspection of the code shows that, when there is no required row ordering--i.e. when we aren't looking for a sort-avoidance plan--the cost field of currentSortAvoidanceCost will always be 0.0d. That in turn means that in the above "if" statement, the check for

  ((currentCost.compare(bestCost) < 0) ||
    (currentSortAvoidanceCost.compare(bestCost) < 0))

will always return true (because bestCost should--in theory--always be greater than 0.0d). Thus, in the case where we don't have a required row ordering, the short-circuit logic will fail even if currentCost is actually greater than bestCost.

Comments

[A B]

Attaching a patch, d1357_v1.patch, to address the incorrect logic as noted in the description.

I also had to update the lang/predicatePushdown.out master file because with the d1357_v1.patch the order of a couple of qualifiers has changed. Note that the query plans themselves are exactly the same--the only thing that's changed is the the qualifier ordering for one query. This change of order occurs because as part of the costing code in FromBaseTable.estimateCost() the optimizer transfers predicates from one predicate list to another, gets an estimated cost, then puts the predicates back into the original list. The methods to do this transferring are in NestedLoopJoinStrategy.java and HashJoinStrategy.java. In the former, the predicates are transferred away in front-to-back order and then transferred back in back-to-front order, which leads to a reversal of the relevant predicate ordering. Ex. If we have a list L1 of preds A,B,C and we transfer them to L2 in front-to-back order, L2 will end up with A,B,C. Then, when we transfer the predicates back to L1, if we process L2 in back-to-front order, L1 will end up with C,B,A. That said, with d1357_v1 applied the short-circuit logic prevents the optimizer from trying to optimize a join order that is known to be bad. This means that we skip an unnecessary round of optimization and therefore skip one round of order reversal, which means the order of the predicate qualifiers in the final plan is now different.

I ran derbyall on Red Hat with sane jars and ibm142, and saw no new failures.

Review/commit would be appreciated.

[Bryan Pendleton]

Hi Army,

Your change looks very good to me. I like the way you named the boolean temp variable; it makes the code substantially easier to read. And thanks for adding the good comments in the code.

One question, though: what is the actual symptom of this bug? If I am understanding it correctly, the symptom is that the optimizer may pointlessly continue to investigate a possible query plan which it should already be able to reject as being too expensive.

Does that mean that the only symptom here is that the optimizer may waste some resources?

I guess the thing I'm still struggling with is the bit of the change which adds "reloadBestPlan = true" at about line 530. Does that part of the patch have any actual user-visible impact on which query plan would be chosen, such that we need to have a release note here? Or is that just another bit of resource wastage that we're improving?

Possible RELEASE NOTE for this fix is as follows, based on suggestions from Bryan in the following thread:

http://article.gmane.org/gmane.comp.apache.db.derby.devel/23875

<begin_release_note>

DERBY-1357: Short-circuit logic in optimizer appears to be incorrect.

Changes have been made to prevent the optimizer from spending time optimizing/evaluating join orders that it already knows are bad.

WHAT CHANGED

The optimizer will now abandon sub-optimal join orders as soon as it realizes that they cost more than the best join order so far.

This fix also ensures that, in the case of short-circuited join orders, Derby will still generate (and execute) an overall plan that matches the "best path" decisions made by the optimizer--which was not always the case prior to these changes.

SYMPTOM

Execution performance of large queries (esp. those with nested subqueries and/or with large FROM clauses) may change. The expectation is that the new (10.2) query plans will show improved performance over the old ones.

CAUSE

Since the optimizer is now spending less time evaluating sub-optimal join orders, it is possible that it will be able to try out more join orders before optimizer "timeout" occurs. As a result the optimizer can sometimes find better plans than it did in earlier versions of Derby.

SOLUTION

This was an intentional change to fix behavior that was not working correctly in earlier versions of Derby. The expectation is that the new behavior--and the subsequent query plans--will lead to improved performance over the old ones, so no further solution is required.

WORKAROUND

There is no way to disable/workaround this new behavior since the symptom as described above is a good one for Derby.

That said, any user who notices a negative performance change after moving to Derby 10.2, and who believes that the difference in performance is related to this optimizer change, is encouraged to visit the following "performance diagnosis" page and to follow up with his/her findings on the Derby mailing lists:

http://wiki.apache.org/db-derby/PerformanceDiagnosisTips

<end_release_note>

[Satheesh Bandaram]

Submitted this patch. Thanks for documenting the changes very well!

Sending compile\OptimizerImpl.java
Transmitting file data .
Committed revision 423754.

[A B]

Resolving issue as the patch was committed by Satheesh with svn #423754. I'll wait a couple of days to see if anything comes up and then will close this next week if all is well.

[A B]

Changes have been committed for almost 2 months, so closing the issue.