svn commit: r423754 - /db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java

[ba...@apache.org]

Author: bandaram
Date: Wed Jul 19 21:32:04 2006
New Revision: 423754

URL: http://svn.apache.org/viewvc?rev=423754&view=rev
Log:
DERBY-1357: Fix optimizer short-circuit logic. Here is the note from the contributor.

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.

Submitted by Army Brown (qozinx@gmail.com)

Modified:
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?rev=423754&r1=423753&r2=423754&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java Wed Jul 19 21:32:04 2006
@@ -452,9 +452,30 @@
 		** just pick the next table in the current position.
 		*/
 		boolean joinPosAdvanced = false;
+
+		/* Determine if the current plan is still less expensive than
+		 * the best plan so far.  If bestCost is uninitialized then
+		 * we want to return false here; if we didn't, then in the (rare)
+		 * case where the current cost is greater than Double.MAX_VALUE
+		 * (esp. if it's Double.POSITIVE_INFINITY, which can occur
+		 * for very deeply nested queries with long FromLists) we would
+		 * give up on the current plan even though we didn't have a
+		 * best plan yet, which would be wrong.  Also note: if we have
+		 * a required row ordering then we might end up using the
+		 * sort avoidance plan--but we don't know at this point
+		 * which plan (sort avoidance or "normal") we're going to
+		 * use, so we error on the side of caution and only short-
+		 * circuit if both currentCost and currentSortAvoidanceCost
+		 * (if the latter is applicable) are greater than bestCost.
+		 */
+		boolean alreadyCostsMore =
+			!bestCost.isUninitialized() &&
+			(currentCost.compare(bestCost) > 0) &&
+			((requiredRowOrdering == null) ||
+				(currentSortAvoidanceCost.compare(bestCost) > 0));
+
 		if ((joinPosition < (numOptimizables - 1)) &&
-			((currentCost.compare(bestCost) < 0) ||
-			(currentSortAvoidanceCost.compare(bestCost) < 0)) &&
+			!alreadyCostsMore &&
 			( ! timeExceeded )
 			)
 		{
@@ -480,16 +501,29 @@
 				bestRowOrdering.copy(currentRowOrdering);
 			}
 		}
-		else if (optimizerTrace)
+		else
 		{
-			/*
-			** Not considered short-circuiting if all slots in join
-			** order are taken.
-			*/
-			if (joinPosition < (numOptimizables - 1))
-			{
-				trace(SHORT_CIRCUITING, 0, 0, 0.0, null);
+			if (optimizerTrace)
+ 			{
+				/*
+				** Not considered short-circuiting if all slots in join
+				** order are taken.
+				*/
+				if (joinPosition < (numOptimizables - 1))
+				{
+					trace(SHORT_CIRCUITING, 0, 0, 0.0, null);
+				}
 			}
+
+			// If we short-circuited the current join order then we need
+			// to make sure that, when we start pulling optimizables to find
+			// a new join order, we reload the best plans for those
+			// optimizables as we pull them.  Otherwise we could end up
+			// generating a plan for an optimizable even though that plan
+			// was part of a short-circuited (and thus rejected) join
+			// order.
+			if (joinPosition < (numOptimizables - 1))
+				reloadBestPlan = true;
 		}
 
 		if (permuteState == JUMPING && !joinPosAdvanced && joinPosition >= 0)

Re: svn commit: r423754 - /db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java

[Army <qo...@gmail.com>]

bandaram@apache.org wrote:
> Author: bandaram
> Date: Wed Jul 19 21:32:04 2006
> New Revision: 423754
> 
> 
> Modified:
>     db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
> 
> Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java

Hi Satheesh, thanks for the commit.  It looks like the master update for 
predicatePushdown.out didn't get committed...?

d1357_v1.stat shows:

M      java\engine\org\apache\derby\impl\sql\compile\OptimizerImpl.java
M 
java\testing\org\apache\derbyTesting\functionTests\master\predicatePushdown.out

but the commit message only shows OptimizerImpl.  Can you check this quick?

Thanks,
Army