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

• Type: Bug
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• 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
• Issue & fix info: Release Note Needed
• Bug behavior facts: Performance
• Assignee: A B
• Reporter: A B
• Created: 31/May/06 03:52
• Updated: 29/Jun/09 14:33
• Resolved: 21/Jul/06 16:54

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.

Issue Links

• relates to: DERBY-3033 select query results in nullpointer exception in skipScan()
• relates to: DERBY-3288 wrong query result in presence of a unique index