db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From banda...@apache.org
Subject svn commit: r382935 - in /db/derby/code/trunk/java: engine/org/apache/derby/iapi/sql/compile/ engine/org/apache/derby/impl/sql/compile/ testing/org/apache/derbyTesting/functionTests/master/ testing/org/apache/derbyTesting/functionTests/tests/lang/
Date Fri, 03 Mar 2006 21:28:31 GMT
Author: bandaram
Date: Fri Mar  3 13:28:28 2006
New Revision: 382935

URL: http://svn.apache.org/viewcvs?rev=382935&view=rev
Log:
DERBY-1007: Fix optimizer to make subqueries return correct cost estimates.

More description of the changes:
1. Added the "prepForNextRound()" method that was part of OptimizerImpl
to the Optimizer interface since that seemslike an appropriate place for it.

2. Added a single line to OptimizerImpl.prepForNextRound() to reset the "bestCost"
for the current round of optimization. Note that I do _not_ reset the "foundABestPlan"
 variable nor the "bestJoinOrder" array. This is because it's possible that a 
"best join order" may not exist for the current round, in which case the optimizer
 must know whether or not it found a best join order in a previous round
 (foundABestPlan) and if so what the corresponding join order was (bestJoinOrder).
 That information is required so that a valid query plan can be generated after
 optimization is complete.

3. After making the above changes, I noticed that the optimizer cost
estimates were not always showing up when logQueryPlan was set to true--they 
were sometimes being printed as question marks to represent "Infinity". The reason 
for this was that most of the code in the "modifyAccessPaths" phase of query 
compilation uses the estimates as they sit in the ResultSetNode.costEstimate 
field--which, for nodes above subqueries, will hold the "bestCost" estimates for 
the most recent plan chosen by the OptimizerImpl for the subquery. Since I am now 
(with DERBY-1007) resetting the "bestCost" variable at the start of every round,
 it's possible that "bestCost" will hold an estimate that has been "reset" to 
Double.MAX_VALUE. This can happen if it was reset (in prepForNextRound()) and 
then no valid join order was found for the current round (ex. if no valid join
 order exists or if there was an optimizer "timeout"). That in turn meant that 
the "costEstimate" field for nodes above the OptimizerImpl would have been "reset" 
as well, and hence the "infinity" value (i.e. question mark) was showing up in the 
logged query plan. So I had to find all nodes that use "costEstimate" during 
modifyAccessPaths() and update them to use the final, best cost estimate for 
that node (instead of just using the most recent value of "costEstimate"). This 
touched several of ResultSetNode's subclasses, but the diff in most cases is just 
a few lines. The exceptions are FromTable, SelectNode, UnionNode, 
IntersectOrExceptNode, and JoinNode, where I added new "getFinalCostEstimate" methods
 to correctly figure out the final cost estimate based on the final estimates for 
child nodes, as appropriate.

4. The current optimizer "timeout" mechanism is based on the value in 
OptimizerImpl.bestCost. Since I'm now resetting that value at the start of every
round, the timeout mechanism had to be changed in order to preserve its current 
functionality while removing the dependency on bestCost. So I've added a new 
variable, timeLimit, to OptimizerImpl that plays the same role w.r.t optimizer
 "timeout" that the old bestCost value did.

5. Updated master/derived.out to match new behavior. There's one query in 
derived.sql that is affected by this issue. Before these changes the optimizer 
thought one join order B was cheaper than another join order A and so it chose 
to generate join order B. With these changes, though, it now (correctly) sees that 
join order A and join order B are equivalent, so it just goes with join order A. 
This difference manifests itself in the ordering of two rows in the result set for
that query--so I've updated the masters accordingly.

6. Added a new, simple test case specific to DERBY-1007 to lang/subquery.sql, and 
updated the master file accordingly. The test case is the same one mentioned in the 
description for this issue.

Submitted by Army Brown (qozinx@sbcglobal.net)

Modified:
    db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/derived.out
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery.out
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery.sql

Modified: db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java Fri Mar
 3 13:28:28 2006
@@ -247,6 +247,28 @@
 	public CostEstimate getOptimizedCost();
 
 	/**
+	 * Get the final estimated cost of the optimized query.  This
+	 * should be the cost that corresponds to the best overall join
+	 * order chosen by the optimizer, and thus this method should
+	 * only be called after optimization is complete (i.e. when
+	 * modifying access paths).
+	 */
+	public CostEstimate getFinalCost();
+
+	/**
+	 * Prepare for another round of optimization.
+	 *
+	 * This method is called before every "round" of optimization, where
+	 * we define a "round" to be the period between the last time a call to
+	 * getOptimizer() (on either a ResultSetNode or an OptimizerFactory)
+	 * returned _this_ Optimizer and the time a call to this Optimizer's
+	 * getNextPermutation() method returns FALSE.  Any re-initialization
+	 * of state that is required before each round should be done in this
+	 * method.
+	 */
+	public void prepForNextRound();
+
+	/**
 	 * Set the estimated number of outer rows - good for optimizing nested
 	 * optimizables like subqueries and join nodes.
 	 */

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java Fri
Mar  3 13:28:28 2006
@@ -306,11 +306,8 @@
 		 */
 		assignResultSetNumber();
 
-		// Get the cost estimate from the child if we don't have one yet
-		if (costEstimate == null)
-		{
-			costEstimate = childResult.getFinalCostEstimate();
-		}
+		// Get the final cost estimate based on the child's cost.
+		costEstimate = childResult.getFinalCostEstimate();
 
 		/*
 			create the orderItem and stuff it in.

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromTable.java Fri Mar
 3 13:28:28 2006
@@ -662,6 +662,29 @@
 		return null;
 	}
 
+	/**
+	 * Get the final CostEstimate for this FromTable.
+	 *
+	 * @return	The final CostEstimate for this FromTable, which is
+	 *  the costEstimate of trulyTheBestAccessPath if there is one.
+	 *  If there's no trulyTheBestAccessPath for this node, then
+	 *  we just return the value stored in costEstimate as a default.
+	 */
+	public CostEstimate getFinalCostEstimate()
+		throws StandardException
+	{
+		// If we already found it, just return it.
+		if (finalCostEstimate != null)
+			return finalCostEstimate;
+
+		if (getTrulyTheBestAccessPath() == null)
+			finalCostEstimate = costEstimate;
+		else
+			finalCostEstimate = getTrulyTheBestAccessPath().getCostEstimate();
+
+		return finalCostEstimate;
+	}
+
 	/** @see Optimizable#isBaseTable */
 	public boolean isBaseTable()
 	{

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java Fri Mar
 3 13:28:28 2006
@@ -1183,6 +1183,9 @@
 		int				erdNumber = -1;
 		int				numSet = 0;
 
+		// Get our final cost estimate.
+		costEstimate = getFinalCostEstimate();
+
 		for (int index = 0; index < rclSize; index++)
 		{
 			ResultColumn rc = (ResultColumn) resultColumns.elementAt(index);

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java Fri
Mar  3 13:28:28 2006
@@ -789,11 +789,8 @@
 		 */
 		assignResultSetNumber();
 
-		// Get the cost estimate from the child if we don't have one yet
-		if (costEstimate == null)
-		{
-			costEstimate = childResult.getFinalCostEstimate();
-		}
+		// Get the final cost estimate from the child.
+		costEstimate = childResult.getFinalCostEstimate();
 
 		/*
 		** Get the column ordering for the sort.  Note that

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java Fri
Mar  3 13:28:28 2006
@@ -319,11 +319,8 @@
 			}
 		}
 
-		// Get the cost estimate from the child if we don't have one yet
-		if (costEstimate == null)
-		{
-			costEstimate = childResult.getCostEstimate();
-		}
+		// Get the final cost estimate based on child's cost.
+		costEstimate = childResult.getFinalCostEstimate();
 
 		// if there is no searchClause, we just want to pass null.
 		if (searchClause == null)

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java
Fri Mar  3 13:28:28 2006
@@ -330,6 +330,9 @@
 		 */
 		assignResultSetNumber();
 
+		// Get our final cost estimate based on the child estimates.
+		costEstimate = getFinalCostEstimate();
+
 		// build up the tree.
 
         /* Generate the SetOpResultSet. Arguments:
@@ -367,6 +370,35 @@
                       ClassName.NoPutResultSet, 11);
 	} // end of generate
 
+	/**
+	 * @see ResultSetNode#getFinalCostEstimate
+	 *
+	 * Get the final CostEstimate for this IntersectOrExceptNode.
+	 *
+	 * @return	The final CostEstimate for this IntersectOrExceptNode,
+	 *  which is the sum of the two child costs.  The final number of
+	 *  rows depends on whether this is an INTERSECT or EXCEPT (see
+	 *  getRowCountEstimate() in this class for more).
+	 */
+	public CostEstimate getFinalCostEstimate()
+		throws StandardException
+	{
+		if (finalCostEstimate != null)
+			return finalCostEstimate;
+
+		CostEstimate leftCE = leftResultSet.getFinalCostEstimate();
+		CostEstimate rightCE = rightResultSet.getFinalCostEstimate();
+
+		finalCostEstimate = getNewCostEstimate();
+		finalCostEstimate.setCost(
+			leftCE.getEstimatedCost() + rightCE.getEstimatedCost(),
+			getRowCountEstimate(leftCE.rowCount(), rightCE.rowCount()),
+			getSingleScanRowCountEstimate(leftCE.singleScanRowCount(),
+				rightCE.singleScanRowCount()));
+
+		return finalCostEstimate;
+	}
+
     String getOperatorName()
     {
         switch( opType)
@@ -392,9 +424,10 @@
             return Math.min( leftRowCount, rightRowCount)/2;
 
         case EXCEPT_OP:
-            // The result has at most leftRowCount rows and at least min( 0, leftRowCount
- rightRowCount) rows.
-            // Use the mean of those two as the estimate.
-            return (leftRowCount + Math.min( 0, leftRowCount - rightRowCount))/2;
+            // The result has at most leftRowCount rows and at least
+            // max(0, leftRowCount - rightRowCount) rows.  Use the mean
+            // of those two as the estimate.
+            return (leftRowCount + Math.max(0, leftRowCount - rightRowCount))/2;
         }
         if( SanityManager.DEBUG)
             SanityManager.THROWASSERT( "Invalid intersectOrExcept opType: " + opType);

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java Fri Mar
 3 13:28:28 2006
@@ -1567,16 +1567,8 @@
 		rightResultSet.generate(acb, mb); // arg 3
 		mb.push(rightResultSet.resultColumns.size()); // arg 4
 
-		// Get the cost estimate if we don't have one yet
-		if (costEstimate == null)
-		{
-			costEstimate = getNewCostEstimate();
-			costEstimate.setCost(
-				leftResultSet.getFinalCostEstimate().getEstimatedCost() +
-				rightResultSet.getFinalCostEstimate().getEstimatedCost(),
-				rightResultSet.getFinalCostEstimate().rowCount(),
-				rightResultSet.getFinalCostEstimate().rowCount());
-		}
+		// Get our final cost estimate based on child estimates.
+		costEstimate = getFinalCostEstimate();
 
 		// for the join clause, we generate an exprFun
 		// that evaluates the expression of the clause
@@ -1652,6 +1644,34 @@
 
 		return numArgs;
 
+	}
+
+	/**
+	 * @see ResultSetNode#getFinalCostEstimate
+	 *
+	 * Get the final CostEstimate for this JoinNode.
+	 *
+	 * @return	The final CostEstimate for this JoinNode, which is sum
+	 *  the costs for the inner and outer table.  The number of rows,
+	 *  though, is that for the inner table only.
+	 */
+	public CostEstimate getFinalCostEstimate()
+		throws StandardException
+	{
+		// If we already found it, just return it.
+		if (finalCostEstimate != null)
+			return finalCostEstimate;
+
+		CostEstimate leftCE = leftResultSet.getFinalCostEstimate();
+		CostEstimate rightCE = rightResultSet.getFinalCostEstimate();
+
+		finalCostEstimate = getNewCostEstimate();
+		finalCostEstimate.setCost(
+			leftCE.getEstimatedCost() + rightCE.getEstimatedCost(),
+			rightCE.rowCount(),
+			rightCE.rowCount());
+
+		return finalCostEstimate;
 	}
 
 	protected void oneRowRightSide(ActivationClassBuilder acb,

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java
Fri Mar  3 13:28:28 2006
@@ -107,10 +107,7 @@
 		assignResultSetNumber();
 
 		// Get the cost estimate from the child if we don't have one yet
-		if (costEstimate == null)
-		{
-			costEstimate = childResult.getFinalCostEstimate();
-		}
+		costEstimate = childResult.getFinalCostEstimate();
 
 		// build up the tree.
 

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?rev=382935&r1=382934&r2=382935&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 Fri
Mar  3 13:28:28 2006
@@ -155,6 +155,14 @@
 	// to keep track of them all.
 	private HashMap savedJoinOrders;
 
+	// Value used to figure out when/if we've timed out for this
+	// Optimizable.
+	protected double timeLimit;
+
+	// Cost estimate for the final "best join order" that we chose--i.e.
+	// the one that's actually going to be generated.
+	CostEstimate finalCostEstimate;
+
 	protected  OptimizerImpl(OptimizableList optimizableList, 
 				  OptimizablePredicateList predicateList,
 				  DataDictionary dDictionary,
@@ -232,6 +240,7 @@
 		timeOptimizationStarted = System.currentTimeMillis();
 		reloadBestPlan = false;
 		savedJoinOrders = null;
+		timeLimit = Double.MAX_VALUE;
 	}
 
 	/**
@@ -243,7 +252,7 @@
 	 * of state that is required before each round should be done in this
 	 * method.
 	 */
-	protected void prepForNextRound()
+	public void prepForNextRound()
 	{
 		// We initialize reloadBestPlan to false so that if we end up
 		// pulling an Optimizable before we find a best join order
@@ -251,6 +260,30 @@
 		// round) we won't inadvertently reload the best plans based
 		// on some previous round.
 		reloadBestPlan = false;
+
+		/* Since we're preparing for a new round, we have to clear
+		 * out the "bestCost" from the previous round to ensure that,
+		 * when this round of optimizing is done, bestCost will hold
+		 * the best cost estimate found _this_ round, if there was
+		 * one.  If there was no best cost found (which can happen if
+		 * there is no feasible join order) then bestCost will remain
+		 * at Double.MAX_VALUE.  Then when outer queries check the
+		 * cost and see that it is so high, they will reject whatever
+		 * outer join order they're trying in favor of something that's
+		 * actually valid (and therefore cheaper).
+		 *
+		 * Note that we do _not_ reset the "foundABestPlan" variable nor
+		 * the "bestJoinOrder" array.  This is because it's possible that
+		 * a "best join order" may not exist for the current round, in
+		 * which case this OptimizerImpl must know whether or not it found
+		 * a best join order in a previous round (foundABestPlan) and if
+		 * so what the corresponding join order was (bestJoinOrder).  This
+		 * information is required so that the correct query plan can be
+		 * generated after optimization is complete, even if that best
+		 * plan was not found in the most recent round.
+		 */
+		bestCost = getNewCostEstimate(
+			Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
 	}
 
     public int getMaxMemoryPerTable()
@@ -299,8 +332,7 @@
 			** the current best cost.
 			*/
 			currentTime = System.currentTimeMillis();
-			timeExceeded = (currentTime - timeOptimizationStarted) >
-									bestCost.getEstimatedCost();
+			timeExceeded = (currentTime - timeOptimizationStarted) > timeLimit;
 
 			if (optimizerTrace && timeExceeded)
 			{
@@ -1296,6 +1328,15 @@
 		/* Remember the current cost as best */
 		bestCost.setCost(currentCost);
 
+		// Our time limit for optimizing this round is the time we think
+		// it will take us to execute the best join order that we've 
+		// found so far (across all rounds of optimizing).  In other words,
+		// don't spend more time optimizing this OptimizerImpl than we think
+		// it's going to take to execute the best plan.  So if we've just
+		// found a new "best" join order, use that to update our time limit.
+		if (bestCost.getEstimatedCost() < timeLimit)
+			timeLimit = bestCost.getEstimatedCost();
+
 		/*
 		** Remember the current join order and access path
 		** selections as best.
@@ -1882,6 +1923,39 @@
 	public CostEstimate getOptimizedCost()
 	{
 		return bestCost;
+	}
+
+	/**
+	 * @see Optimizer#getFinalCost
+	 *
+	 * Sum up the cost of all of the trulyTheBestAccessPaths
+	 * for the Optimizables in our list.  Assumption is that
+	 * we only get here after optimization has completed--i.e.
+	 * while modifying access paths.
+	 */
+	public CostEstimate getFinalCost()
+	{
+		// If we already did this once, just return the result.
+		if (finalCostEstimate != null)
+			return finalCostEstimate;
+
+		// The total cost is the sum of all the costs, but the total
+		// number of rows is the number of rows returned by the innermost
+		// optimizable.
+		finalCostEstimate = getNewCostEstimate(0.0d, 0.0d, 0.0d);
+		CostEstimate ce = null;
+		for (int i = 0; i < bestJoinOrder.length; i++)
+		{
+			ce = optimizableList.getOptimizable(bestJoinOrder[i])
+					.getTrulyTheBestAccessPath().getCostEstimate();
+
+			finalCostEstimate.setCost(
+				finalCostEstimate.getEstimatedCost() + ce.getEstimatedCost(),
+				ce.rowCount(),
+				ce.singleScanRowCount());
+		}
+
+		return finalCostEstimate;
 	}
 
 	/** @see Optimizer#setOuterRows */

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java Fri
Mar  3 13:28:28 2006
@@ -396,7 +396,7 @@
 
 		// Get the cost estimate for the child
 		// RESOLVE - we will eventually include the cost of the sort
-		CostEstimate costEstimate = child.getCostEstimate(); 
+		CostEstimate costEstimate = child.getFinalCostEstimate(); 
 
 		mb.push(costEstimate.rowCount());
 		mb.push(costEstimate.getEstimatedCost());

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
Fri Mar  3 13:28:28 2006
@@ -1117,19 +1117,22 @@
 	 * 			the final cost estimate for the child node.
 	 */
 	public CostEstimate getFinalCostEstimate()
+		throws StandardException
 	{
-		/*
-		** The cost estimate will be set here if either optimize() or
-		** optimizeIt() was called on this node.  It's also possible
-		** that optimization was done directly on the child node,
-		** in which case the cost estimate will be null here.
-		*/
-		if (costEstimate == null)
-			return childResult.getFinalCostEstimate();
+		if (finalCostEstimate != null)
+		// we already set it, so just return it.
+			return finalCostEstimate;
+
+		// If the child result set is an Optimizable, then this node's
+		// final cost is that of the child.  Otherwise, this node must
+		// hold "trulyTheBestAccessPath" for it's child so we pull
+		// the final cost from there.
+		if (childResult instanceof Optimizable)
+			finalCostEstimate = childResult.getFinalCostEstimate();
 		else
-		{
-			return costEstimate;
-		}
+			finalCostEstimate = getTrulyTheBestAccessPath().getCostEstimate();
+
+		return finalCostEstimate;
 	}
 
     /**
@@ -1308,11 +1311,8 @@
 			restrictSubquerys.setPointOfAttachment(resultSetNumber);
 		}
 
-		/* Drop our cost estimate if it is uninitialized. */
-		if (costEstimate != null && costEstimate.isUninitialized())
-		{
-			costEstimate = childResult.getFinalCostEstimate();
-		}
+		// Load our final cost estimate.
+		costEstimate = getFinalCostEstimate();
 
 		// if there is no restriction, we just want to pass null.
 		if (restriction == null)
@@ -1417,8 +1417,8 @@
 		mb.push(mapArrayItem);
 		mb.push(resultColumns.reusableResult());
 		mb.push(doesProjection);
-		mb.push(getFinalCostEstimate().rowCount());
-		mb.push(getFinalCostEstimate().getEstimatedCost());
+		mb.push(costEstimate.rowCount());
+		mb.push(costEstimate.getEstimatedCost());
 		closeMethodArgument(acb, mb);
 
 		mb.callMethod(VMOpcode.INVOKEINTERFACE, (String) null, "getProjectRestrictResultSet",

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java Fri
Mar  3 13:28:28 2006
@@ -97,6 +97,11 @@
 	CostEstimate		scratchCostEstimate;
 	Optimizer			optimizer;
 
+	// Final cost estimate for this result set node, which is the estimate
+	// for this node with respect to the best join order for the top-level
+	// query. Subclasses will set this value where appropriate.
+	CostEstimate		finalCostEstimate;
+
 	/**
 	 * Convert this object to a String.  See comments in QueryTreeNode.java
 	 * for how this should be done for tree printing.
@@ -180,17 +185,18 @@
 	 * @return	The final CostEstimate for this ResultSetNode.
 	 */
 	public CostEstimate getFinalCostEstimate()
+		throws StandardException
 	{
 		if (SanityManager.DEBUG)
 		{
-			if (costEstimate == null)
+			if (finalCostEstimate == null)
 			{
 				SanityManager.THROWASSERT(
-					"costEstimate is not expected to be null for " +
+					"finalCostEstimate is not expected to be null for " +
 					getClass().getName());
 			}
 		}
-		return costEstimate;
+		return finalCostEstimate;
 	}
 
 	/**
@@ -1608,7 +1614,7 @@
 								getLanguageConnectionContext());
 		}
 
-		((OptimizerImpl)optimizer).prepForNextRound();
+		optimizer.prepForNextRound();
 		return optimizer;
 	}
 

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java
Fri Mar  3 13:28:28 2006
@@ -653,6 +653,9 @@
 		if (SanityManager.DEBUG)
         SanityManager.ASSERT(resultColumns != null, "Tree structure bad");
 
+		// Get our final cost estimate.
+		costEstimate = getFinalCostEstimate();
+
 		/*
 		** Check and see if everything below us is a constant or not.
 		** If so, we'll let execution know that it can do some caching.

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java Fri
Mar  3 13:28:28 2006
@@ -21,6 +21,7 @@
 
 package	org.apache.derby.impl.sql.compile;
 
+import org.apache.derby.iapi.sql.compile.CostEstimate;
 import org.apache.derby.iapi.sql.compile.Optimizer;
 import org.apache.derby.iapi.sql.compile.Visitable;
 import org.apache.derby.iapi.sql.compile.Visitor;
@@ -1615,6 +1616,9 @@
 		*/
 		optimizer.modifyAccessPaths();
 
+		// Load the costEstimate for the final "best" join order.
+		costEstimate = optimizer.getFinalCost();
+
 		selectSubquerys.modifyAccessPaths();
 
 		if (whereSubquerys != null && whereSubquerys.size() > 0)
@@ -1690,6 +1694,18 @@
 		return genProjectRestrict(origFromListSize);
 	}
 
+	/**
+	 * Get the final CostEstimate for this SelectNode.
+	 *
+	 * @return	The final CostEstimate for this SelectNode, which is
+	 * 			the final cost estimate for the best join order of
+	 *          this SelectNode's optimizer.
+	 */
+	public CostEstimate getFinalCostEstimate()
+		throws StandardException
+	{
+		return optimizer.getFinalCost();
+	}
 
 	/**
 		Determine if this select is updatable or not, for a cursor.

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
Fri Mar  3 13:28:28 2006
@@ -577,6 +577,7 @@
 	 * 			the final cost estimate for the child node.
 	 */
 	public CostEstimate getFinalCostEstimate()
+		throws StandardException
 	{
 		/*
 		** The cost estimate will be set here if either optimize() or

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java Fri
Mar  3 13:28:28 2006
@@ -1822,6 +1822,10 @@
 				mb.conditionalIfNull();
 
 				ResultSetNode materialSubNode = new MaterializeSubqueryNode(subRS);
+
+				// Propagate the resultSet's cost estimate to the new node.
+				materialSubNode.costEstimate = resultSet.getFinalCostEstimate();
+
 				((ProjectRestrictNode) resultSet).setChildResult(materialSubNode);
 
 				/* Evaluate subquery resultset here first.  Next time when we come to

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
Fri Mar  3 13:28:28 2006
@@ -777,7 +777,7 @@
 													(RequiredRowOrdering) null,
 													getCompilerContext().getNumTables(),
 													  lcc);
-			((OptimizerImpl)optimizer).prepForNextRound();
+			optimizer.prepForNextRound();
 
 			if (sourceResultSet == leftResultSet)
 			{

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java Fri Mar
 3 13:28:28 2006
@@ -545,6 +545,9 @@
 		 */
 		assignResultSetNumber();
 
+		// Get our final cost estimate based on the child estimates.
+		costEstimate = getFinalCostEstimate();
+
 		// build up the tree.
 
 		acb.pushGetResultSetFactoryExpression(mb); // instance for getUnionResultSet
@@ -593,6 +596,34 @@
 		closeMethodArgument(acb, mb);
 
 		mb.callMethod(VMOpcode.INVOKEINTERFACE, (String) null, "getUnionResultSet", ClassName.NoPutResultSet,
6);
+	}
+
+	/**
+	 * @see ResultSetNode#getFinalCostEstimate
+	 *
+	 * Get the final CostEstimate for this UnionNode.
+	 *
+	 * @return	The final CostEstimate for this UnionNode, which is
+	 *  the sum of the two child costs.
+	 */
+	public CostEstimate getFinalCostEstimate()
+		throws StandardException
+	{
+		// If we already found it, just return it.
+		if (finalCostEstimate != null)
+			return finalCostEstimate;
+
+		CostEstimate leftCE = leftResultSet.getFinalCostEstimate();
+		CostEstimate rightCE = rightResultSet.getFinalCostEstimate();
+
+		finalCostEstimate = getNewCostEstimate();
+		finalCostEstimate.setCost(leftCE.getEstimatedCost(),
+							 leftCE.rowCount(),
+							 leftCE.singleScanRowCount() +
+							 rightCE.singleScanRowCount());
+
+		finalCostEstimate.add(rightCE, finalCostEstimate);
+		return finalCostEstimate;
 	}
 
     String getOperatorName()

Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/derived.out
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/derived.out?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/derived.out
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/derived.out
Fri Mar  3 13:28:28 2006
@@ -323,12 +323,12 @@
 B          |A          |B          |A          
 -----------------------------------------------
 0          |0          |0          |0          
-0          |10         |0          |0          
 0          |0          |0          |10         
+0          |10         |0          |0          
 0          |10         |0          |10         
 10         |0          |10         |0          
-10         |10         |10         |0          
 10         |0          |10         |10         
+10         |10         |10         |0          
 10         |10         |10         |10         
 ij> select * from (select (select 1 from s where 1 = 0), b.a from s a, s b) a (b, a),
 			  (select (select 1 from s where 1 = 0), b.a from s a, s b) b (b, a) where a.b = b.b;

Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery.out
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery.out?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery.out
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery.out
Fri Mar  3 13:28:28 2006
@@ -869,4 +869,151 @@
 0 rows inserted/updated/deleted
 ij> drop table u;
 0 rows inserted/updated/deleted
+ij> -- DERBY-1007: Optimizer for subqueries can return incorrect cost estimates
+-- leading to sub-optimal join orders for the outer query.  Before the patch
+-- for that isssue, the following query plan will show T3 first and then T1--
+-- but that's determined by the optimizer to be the "bad" join order.  After
+-- the fix, the join order will show T1 first, then T3, which is correct
+-- (based on the optimizer's estimates).
+create table t1 (i int, j int);
+0 rows inserted/updated/deleted
+ij> insert into T1 values (1,1), (2,2), (3,3), (4,4), (5,5);
+5 rows inserted/updated/deleted
+ij> create table t3 (a int, b int);
+0 rows inserted/updated/deleted
+ij> insert into T3 values (1,1), (2,2), (3,3), (4,4);
+4 rows inserted/updated/deleted
+ij> insert into t3 values (6, 24), (7, 28), (8, 32), (9, 36), (10, 40);
+5 rows inserted/updated/deleted
+ij> call SYSCS_UTIL.SYSCS_SET_RUNTIMESTATISTICS(1);
+0 rows inserted/updated/deleted
+ij> maximumdisplaywidth 20000;
+ij> select x1.j, x2.b from
+  (select distinct i,j from t1) x1,
+  (select distinct a,b from t3) x2
+where x1.i = x2.a;
+J          |B          
+-----------------------
+4          |4          
+3          |3          
+2          |2          
+1          |1          
+ij> values SYSCS_UTIL.SYSCS_GET_RUNTIMESTATISTICS();
+1                                                                                       
                                                                                         
                                                                                         
                                                                                         
                                                                                         
                                                                                         
                                                                                         
                                                                                         
                                                                                         
                                                                                         
                                                                                         

                                    
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 -----------------------------------
+Statement Name: 
+	null
+Statement Text: 
+	select x1.j, x2.b from
+  (select distinct i,j from t1) x1,
+  (select distinct a,b from t3) x2
+where x1.i = x2.a
+Parse Time: 0
+Bind Time: 0
+Optimize Time: 0
+Generate Time: 0
+Compile Time: 0
+Execute Time: 0
+Begin Compilation Timestamp : null
+End Compilation Timestamp : null
+Begin Execution Timestamp : null
+End Execution Timestamp : null
+Statement Execution Plan Text: 
+Project-Restrict ResultSet (5):
+Number of opens = 1
+Rows seen = 4
+Rows filtered = 0
+restriction = false
+projection = true
+	constructor time (milliseconds) = 0
+	open time (milliseconds) = 0
+	next time (milliseconds) = 0
+	close time (milliseconds) = 0
+	restriction time (milliseconds) = 0
+	projection time (milliseconds) = 0
+Source result set:
+	Nested Loop Join ResultSet:
+	Number of opens = 1
+	Rows seen from the left = 5
+	Rows seen from the right = 4
+	Rows filtered = 0
+	Rows returned = 4
+		constructor time (milliseconds) = 0
+		open time (milliseconds) = 0
+		next time (milliseconds) = 0
+		close time (milliseconds) = 0
+	Left result set:
+		Distinct Scan ResultSet for T1 using index xxxxFILTERED-UUIDxxxx at read committed isolation
level using instantaneous share row locking: 
+		Number of opens = 1
+		Hash table size = 5
+		Distinct columns are column numbers (0,1)
+		Rows seen = 5
+		Rows filtered = 0
+			constructor time (milliseconds) = 0
+			open time (milliseconds) = 0
+			next time (milliseconds) = 0
+			close time (milliseconds) = 0
+			next time in milliseconds/row = 0
+		scan information: 
+			Bit set of columns fetched=All
+			Number of columns fetched=2
+			Number of pages visited=1
+			Number of rows qualified=5
+			Number of rows visited=5
+			Scan type=heap
+			start position:
+	None
+			stop position:
+	None
+			scan qualifiers:
+None
+			next qualifiers:
+None
+	Right result set:
+		Project-Restrict ResultSet (4):
+		Number of opens = 5
+		Rows seen = 45
+		Rows filtered = 41
+		restriction = true
+		projection = true
+			constructor time (milliseconds) = 0
+			open time (milliseconds) = 0
+			next time (milliseconds) = 0
+			close time (milliseconds) = 0
+			restriction time (milliseconds) = 0
+			projection time (milliseconds) = 0
+		Source result set:
+			Distinct Scan ResultSet for T3 using index xxxxFILTERED-UUIDxxxx at read committed isolation
level using instantaneous share row locking: 
+			Number of opens = 5
+			Hash table size = 9
+			Distinct columns are column numbers (0,1)
+			Rows seen = 45
+			Rows filtered = 0
+				constructor time (milliseconds) = 0
+				open time (milliseconds) = 0
+				next time (milliseconds) = 0
+				close time (milliseconds) = 0
+				next time in milliseconds/row = 0
+			scan information: 
+				Bit set of columns fetched=All
+				Number of columns fetched=2
+				Number of pages visited=1
+				Number of rows qualified=9
+				Number of rows visited=9
+				Scan type=heap
+				start position:
+	None
+				stop position:
+	None
+				scan qualifiers:
+None
+				next qualifiers:
+None
+ij> -- clean up.
+call SYSCS_UTIL.SYSCS_SET_RUNTIMESTATISTICS(0);
+0 rows inserted/updated/deleted
+ij> drop table t1;
+0 rows inserted/updated/deleted
+ij> drop table t3;
+0 rows inserted/updated/deleted
 ij> 

Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery.sql
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery.sql?rev=382935&r1=382934&r2=382935&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery.sql
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery.sql
Fri Mar  3 13:28:28 2006
@@ -408,3 +408,31 @@
 drop table ttt;
 drop table u;
 
+-- DERBY-1007: Optimizer for subqueries can return incorrect cost estimates
+-- leading to sub-optimal join orders for the outer query.  Before the patch
+-- for that isssue, the following query plan will show T3 first and then T1--
+-- but that's determined by the optimizer to be the "bad" join order.  After
+-- the fix, the join order will show T1 first, then T3, which is correct
+-- (based on the optimizer's estimates).
+
+create table t1 (i int, j int);
+insert into T1 values (1,1), (2,2), (3,3), (4,4), (5,5);
+create table t3 (a int, b int);
+insert into T3 values (1,1), (2,2), (3,3), (4,4);
+insert into t3 values (6, 24), (7, 28), (8, 32), (9, 36), (10, 40);
+
+call SYSCS_UTIL.SYSCS_SET_RUNTIMESTATISTICS(1);
+maximumdisplaywidth 20000;
+
+select x1.j, x2.b from
+  (select distinct i,j from t1) x1,
+  (select distinct a,b from t3) x2
+where x1.i = x2.a;
+
+values SYSCS_UTIL.SYSCS_GET_RUNTIMESTATISTICS();
+
+-- clean up.
+call SYSCS_UTIL.SYSCS_SET_RUNTIMESTATISTICS(0);
+drop table t1;
+drop table t3;
+



Mime
View raw message