db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From banda...@apache.org
Subject svn commit: r397682 [1/4] - in /db/derby/code/branches/10.1/java: engine/org/apache/derby/iapi/sql/compile/ engine/org/apache/derby/iapi/store/access/ engine/org/apache/derby/impl/sql/compile/ testing/org/apache/derbyTesting/functionTests/master/ testi...
Date Thu, 27 Apr 2006 23:42:04 GMT
Author: bandaram
Date: Thu Apr 27 16:42:02 2006
New Revision: 397682

URL: http://svn.apache.org/viewcvs?rev=397682&view=rev
Log:
DERBY-805, DERBY-1007 and DERBY-1073: Merge all changes performed under these entries from trunk. They have been present in trunk for sometime.

Please refer to JIRA entries and/or SVN comments made on trunk for detailed descriptions.

Original changes submitted by Army Brown (qozinx@gmail.com)

Added:
    db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/predicatePushdown.out   (with props)
    db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/predicatePushdown.sql   (with props)
    db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/predicatePushdown_derby.properties   (with props)
Modified:
    db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/store/access/BackingStoreHashtable.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BaseTableNumbersVisitor.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/CostEstimateImpl.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/Predicate.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
    db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java
    db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/derived.out
    db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/subquery.out
    db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/suites/derbylang.runall
    db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/copyfiles.ant
    db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery.sql

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizable.java Thu Apr 27 16:42:02 2006
@@ -240,26 +240,31 @@
 	 * question, but in cases where there are nested subqueries, there will be
 	 * one OptimizerImpl for every level of nesting, and each OptimizerImpl
 	 * might have its own idea of what this Optimizable's "truly the best path"
-	 * access path really is.  So whenever we save a "truly the best" path,
-	 * we take note of which Optimizer told us to do so.  Then as each level
-	 * of subquery finishes optimization, the corresponding OptimizerImpl
-	 * can load its preferred access path into this Optimizable's
-	 * trulyTheBestAccessPath field and pass it up the tree, until eventually
-	 * the outer-most OptimizerImpl can choose to either use the best path
-	 * that it received from below (by calling "rememberAsBest()") or else
+	 * access path really is.  In addition, there could be Optimizables
+	 * above this Optimizable that might need to override the best path
+	 * chosen during optimization.  So whenever we save a "truly the best" path,
+	 * we take note of which Optimizer/Optimizable told us to do so.  Then
+	 * as each level of subquery finishes optimization, the corresponding
+	 * OptimizerImpl/Optimizable can load its preferred access path into this
+	 * Optimizable's trulyTheBestAccessPath field and pass it up the tree, until
+	 * eventually the outer-most OptimizerImpl can choose to either use the best
+	 * path that it received from below (by calling "rememberAsBest()") or else
 	 * use the path that it found to be "best" for itself.
 	 *
-	 * This method is what allows us to keep track of which OptimizerImpl
-	 * saved which "best plan", and allows us to load the appropriate plans
-	 * after each round of optimization.
+	 * This method is what allows us to keep track of which OptimizerImpl or
+	 * Optimizable saved which "best plan", and allows us to load the
+	 * appropriate plans after each round of optimization.
 	 * 
-	 * @param doAdd True if we're saving a best plan for the OptimizerImpl,
-	 *  false if we're loading/retrieving the best plan for the OptimizerImpl.
-	 * @param optimizer The OptimizerImpl for which we're saving/loading
-	 *  the "truly the best" path.
+	 * @param doAdd True if we're saving a best plan for the OptimizerImpl/
+	 *  Optimizable; false if we're loading/retrieving the best plan.
+	 * @param planKey Object to use as the map key when adding/looking up
+	 *  a plan.  If it is an instance of OptimizerImpl then it corresponds
+	 *  to an outer query; otherwise it's some Optimizable above this
+	 *  Optimizable that could potentially reject plans chosen by the
+	 *  OptimizerImpl to which this Optimizable belongs.
 	 */
 	public void addOrLoadBestPlanMapping(boolean doAdd,
-		Optimizer optimizer) throws StandardException;
+		Object planKey) throws StandardException;
 
 	/**
 	 * Remember the current access path as the best one (so far).

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java Thu Apr 27 16:42:02 2006
@@ -251,6 +251,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/branches/10.1/java/engine/org/apache/derby/iapi/store/access/BackingStoreHashtable.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/store/access/BackingStoreHashtable.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/store/access/BackingStoreHashtable.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/iapi/store/access/BackingStoreHashtable.java Thu Apr 27 16:42:02 2006
@@ -224,9 +224,36 @@
         }
         else
         {
+            /* We want to create the hash table based on the estimated row
+             * count if a) we have an estimated row count (i.e. it's greater
+             * than zero) and b) we think we can create a hash table to
+             * hold the estimated row count without running out of memory.
+             * The check for "b" is required because, for deeply nested
+             * queries and/or queries with a high number of tables in
+             * their FROM lists, the optimizer can end up calculating
+             * some very high row count estimates--even up to the point of
+             * Double.POSITIVE_INFINITY.  In that case attempts to
+             * create a Hashtable of size estimated_rowcnt can cause
+             * OutOfMemory errors when we try to create the Hashtable.
+             * So as a "red flag" for that kind of situation, we check to
+             * see if the estimated row count is greater than the max
+             * in-memory size for this table.  Unit-wise this comparison
+             * is relatively meaningless: rows vs bytes.  But if our
+             * estimated row count is greater than the max number of
+             * in-memory bytes that we're allowed to consume, then
+             * it's very likely that creating a Hashtable with a capacity
+             * of estimated_rowcnt will lead to memory problems.  So in
+             * that particular case we leave hash_table null here and
+             * initialize it further below, using the estimated in-memory
+             * size of the first row to figure out what a reasonable size
+             * for the Hashtable might be.
+             */
             hash_table = 
-                ((estimated_rowcnt <= 0) ? 
-                     new Hashtable() : new Hashtable((int) estimated_rowcnt));
+                (((estimated_rowcnt <= 0) || (row_source == null)) ?
+                     new Hashtable() :
+                     (estimated_rowcnt < max_inmemory_size) ?
+                         new Hashtable((int) estimated_rowcnt) :
+                         null);
         }
 
         if (row_source != null)
@@ -235,6 +262,22 @@
 
             while ((row = getNextRowFromRowSource()) != null)
             {
+                // If we haven't initialized the hash_table yet then that's
+                // because a Hashtable with capacity estimated_rowcnt would
+                // probably cause memory problems.  So look at the first row
+                // that we found and use that to create the hash table with
+                // an initial capacity such that, if it was completely full,
+                // it would still satisfy the max_inmemory condition.  Note
+                // that this isn't a hard limit--the hash table can grow if
+                // needed.
+                if (hash_table == null)
+                {
+					// Check to see how much memory we think the first row
+                    // is going to take, and then use that to set the initial
+                    // capacity of the Hashtable.
+                    double rowUsage = getEstimatedMemUsage(row);
+                    hash_table = new Hashtable((int)(max_inmemory_size / rowUsage));
+                }
 
                 if (needsToClone)
                 {
@@ -387,13 +430,7 @@
         inmemory_rowcnt++;
         if( max_inmemory_rowcnt <= 0)
         {
-            for( int i = 0; i < row.length; i++)
-            {
-                if( row[i] instanceof DataValueDescriptor)
-                    max_inmemory_size -= ((DataValueDescriptor) row[i]).estimateMemoryUsage();
-                max_inmemory_size -= ClassSize.refSize;
-            }
-            max_inmemory_size -= ClassSize.refSize;
+            max_inmemory_size -= getEstimatedMemUsage(row);
             if( firstDuplicate)
                 max_inmemory_size -= vectorSize;
         }
@@ -464,6 +501,29 @@
         diskHashtable.put( key, row);
         return true;
     } // end of spillToDisk
+
+    /**
+     * Take a row and return an estimate as to how much memory that
+     * row will consume.
+     * 
+     * @param row The row for which we want to know the memory usage.
+     * @return A guess as to how much memory the current row will
+     *  use.
+     */
+    private long getEstimatedMemUsage(Object [] row)
+    {
+        long rowMem = 0;
+        for( int i = 0; i < row.length; i++)
+        {
+            if (row[i] instanceof DataValueDescriptor)
+                rowMem += ((DataValueDescriptor) row[i]).estimateMemoryUsage();
+            rowMem += ClassSize.refSize;
+        }
+
+        rowMem += ClassSize.refSize;
+        return rowMem;
+    }
+
     /**************************************************************************
      * Public Methods of This class:
      **************************************************************************

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BaseTableNumbersVisitor.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BaseTableNumbersVisitor.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BaseTableNumbersVisitor.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BaseTableNumbersVisitor.java Thu Apr 27 16:42:02 2006
@@ -135,14 +135,14 @@
 
 				if (rcExpr instanceof ColumnReference)
 				// we found our column reference; recurse using that.
-					return rcExpr.accept(this);
-
+					rcExpr.accept(this);
+				else {
 				// Else we must have found the table number someplace
 				// other than within a ColumnReference (ex. we may
 				// have pulled it from a VirtualColumnNode's source
 				// table); so just set the number.
-				tableMap.set(baseTableNumber);
-
+					tableMap.set(baseTableNumber);
+				}
 			}
 			else if (node instanceof ColumnReference) {
 			// we couldn't find any other table numbers beneath the

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java Thu Apr 27 16:42:02 2006
@@ -1273,6 +1273,18 @@
 		 * position (namely, the position w.r.t the ProjectRestrictNode above
 		 * the FromBaseTable) needs to be.  So that's the column number we
 		 * use.
+		 *
+		 * As a final note, we have to be sure we only set the column
+		 * reference's column number if the reference points to a base table.
+		 * If the reference points to some other ResultSetNode--esp. another
+		 * subquery node--then it (the reference) already holds the correct
+		 * number with respect to that ResultSetNode and we don't change
+		 * it.  The reason is that the reference could end up getting pushed
+		 * down further to that ResultSetNode, in which case we'll do another
+		 * scoping operation and, in order for that to be successful, the
+		 * reference to be scoped has to know what the target column number
+		 * is w.r.t to that ResultSetNode (i.e. it'll be playing the role of
+		 * "cr" as described here).
 		 */
 		if (rc.getExpression() instanceof ColumnReference)
 		{
@@ -1284,7 +1296,8 @@
 			// correctly.  That remapping is done in the pushOptPredicate()
 			// method of ProjectRestrictNode.
 			ColumnReference cRef = (ColumnReference)rc.getExpression();
-			cRef.setColumnNumber(cr.getColumnNumber());
+			if (cRef.pointsToBaseTable())
+				cRef.setColumnNumber(cr.getColumnNumber());
 			return cRef;
 		}
 
@@ -1294,10 +1307,10 @@
 		 *
 		 *   select 1, 1 from t1
 		 *
-		 * In this case we just return the column reference as it is
+		 * In this case we just return a clone of the column reference
 		 * because it's scoped as far as we can take it.
 		 */
-		return cr;
+		return (ValueNode)cr.getClone();
 	}
 
 }	

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java Thu Apr 27 16:42:02 2006
@@ -1055,4 +1055,52 @@
         }
         return dtd;
     } // end of getTypeServices
+
+	/**
+	 * Determine whether or not this ColumnReference's source comes
+	 * from a FromBaseTable (as opposed to some other ResultSetNode).
+	 * We figure this out by walking the ResultColumn/VirtualColumnNode
+	 * chain until we get to last VirtualColumnNode in the chain
+	 * (if there is one), and then seeing what that VCN's source
+	 * result set is.  If there are no VCNs then we check to see
+	 * if the source is pointing to a BaseColumnNode.
+	 *
+	 * This is useful when scoping predicates for pushing; we
+	 * need to know if the predicate's column references are pointing
+	 * directly to base tables so that we can set the scoped references'
+	 * column numbers correctly.
+	 */
+	protected boolean pointsToBaseTable() throws StandardException
+	{
+		ResultColumn rc = getSource();
+
+		if (rc == null) {
+		// this can happen if column reference is pointing to a column
+		// that is not from a base table.  For example, if we have a
+		// VALUES clause like
+		//
+		//    (values (1, 2), (3, 4)) V1 (i, j)
+		//
+		// and then a column reference to VI.i, the column reference
+		// won't have a source.
+			return false;
+		}
+
+		// Walk the VirtualColumnNode->ResultColumn chain.
+		VirtualColumnNode vcn = null;
+		ValueNode rcExpr = rc.getExpression();
+		while (rcExpr instanceof VirtualColumnNode) {
+			vcn = (VirtualColumnNode)rcExpr;
+			rc = vcn.getSourceColumn();
+			rcExpr = rc.getExpression();
+		}
+
+		// If we've reached the bottom of the chain then see if
+		// the VCN is pointing to a FromBaseTable.
+		if (vcn != null)
+			return (vcn.getSourceResultSet() instanceof FromBaseTable);
+
+		// Else check our source's expression.
+		return (rc.getExpression() instanceof BaseColumnNode);
+	}
 }

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/CostEstimateImpl.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/CostEstimateImpl.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/CostEstimateImpl.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/CostEstimateImpl.java Thu Apr 27 16:42:02 2006
@@ -113,7 +113,53 @@
 			}
 		}
 
-		return this.cost - ((CostEstimateImpl) other).cost;
+		/* Note: if both CostEstimates are infinity, an attempt to
+		 * substract them will result in NaN, which tells us nothing
+		 * and thus makes it impossible to do a comparison.  So in
+		 * that case we fallback and check the row counts as a secondary
+		 * point of comparison, and the singleScanRowCounts as a
+		 * third comparison.  If all three values are infinity
+		 * for both CostEstimates then we just consider the two
+		 * costs to equal (equally as bad?) and so return 0.0d (instead
+		 * NaN).  RESOLVE: Ideally the optimizer could be updated
+		 * to give more reasonable estimates than infinity, but
+		 * until that happens we're forced to deal with such
+		 * comparisons.  Note that we're most likely to end up with
+		 * infinite cost estimates in situations where we have deeply
+		 * nested subqueries and/or FROM lists with a large number of
+		 * FromTables (such as 10 or more). The reason is that each
+		 * FromTable's cost estimate is (potentially) multiplied by
+		 * the row counts of all preceding FromTables, so if the
+		 * row counts for the preceding FromTables are large, we
+		 * can eventually end up going beyond Double.MAX_VALUE,
+		 * which then gives us infinity.
+		 */
+
+		// If at least one of costs is _not_ infinity, then just do
+		// a normal compare (the other side is less).
+		if ((this.cost != Double.POSITIVE_INFINITY) ||
+			(other.getEstimatedCost() != Double.POSITIVE_INFINITY))
+		{
+			return this.cost - ((CostEstimateImpl) other).cost;
+		}
+
+		// If both costs are infinity, then compare row counts.
+		if ((this.rowCount != Double.POSITIVE_INFINITY) ||
+			(other.rowCount() != Double.POSITIVE_INFINITY))
+		{
+			return this.rowCount - other.rowCount();
+		}
+
+		// If both row counts are infinity, try singleScan counts.
+		if ((this.singleScanRowCount != Double.POSITIVE_INFINITY) ||
+			(other.singleScanRowCount() != Double.POSITIVE_INFINITY))
+		{
+			return this.singleScanRowCount - other.singleScanRowCount();
+		}
+
+		// If we get here, all three parts of both cost estimates are
+		// Infinity; for lack of better choice, just say they're "equal".
+		return 0.0d;
 	}
 
 	/** @see CostEstimate#add */

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/DistinctNode.java Thu Apr 27 16:42:02 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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromBaseTable.java Thu Apr 27 16:42:02 2006
@@ -527,7 +527,10 @@
 							predList,
 							outerCost);
 
-		return costEstimate;
+		// The cost that we found from the above call is now stored in the
+		// cost field of this FBT's current access path.  So that's the
+		// cost we want to return here.
+		return getCurrentAccessPath().getCostEstimate();
 	}
 
 	/** @see Optimizable#getTableDescriptor */

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromTable.java Thu Apr 27 16:42:02 2006
@@ -152,6 +152,18 @@
 							RowOrdering rowOrdering)
 			throws StandardException
 	{
+		// It's possible that a call to optimize the left/right will cause
+		// a new "truly the best" plan to be stored in the underlying base
+		// tables.  If that happens and then we decide to skip that plan
+		// (which we might do if the call to "considerCost()" below decides
+		// the current path is infeasible or not the best) we need to be
+		// able to revert back to the "truly the best" plans that we had
+		// saved before we got here.  So with this next call we save the
+		// current plans using "this" node as the key.  If needed, we'll
+		// then make the call to revert the plans in OptimizerImpl's
+		// getNextDecoratedPermutation() method.
+		addOrLoadBestPlanMapping(true, this);
+
 		CostEstimate singleScanCost = estimateCost(predList,
 												(ConglomerateDescriptor) null,
 												outerCost,
@@ -502,25 +514,38 @@
 
 	/** @see Optimizable#addOrLoadBestPlanMapping */
 	public void addOrLoadBestPlanMapping(boolean doAdd,
-		Optimizer optimizer) throws StandardException
+		Object planKey) throws StandardException
 	{
+		AccessPath bestPath = getTrulyTheBestAccessPath();
 		AccessPathImpl ap = null;
 		if (doAdd)
 		{
+			// If we get to this method before ever optimizing this node, then
+			// there will be no best path--so there's nothing to do.
+			if (bestPath == null)
+				return;
+
 			// If the optimizerToBestPlanMap already exists, search for an
-			// AccessPath for the target optimizer and use that if we can.
+			// AccessPath for the received key and use that if we can.
 			if (optimizerToBestPlanMap == null)
 				optimizerToBestPlanMap = new HashMap();
 			else
-				ap = (AccessPathImpl)optimizerToBestPlanMap.get(optimizer);
+				ap = (AccessPathImpl)optimizerToBestPlanMap.get(planKey);
 
-			// If we don't already have an AccessPath for the optimizer,
-			// create a new one.
+			// If we don't already have an AccessPath for the key,
+			// create a new one.  If the key is an OptimizerImpl then
+			// we might as well pass it in to the AccessPath constructor;
+			// otherwise just pass null.
 			if (ap == null)
-				ap = new AccessPathImpl(optimizer);
+			{
+				if (planKey instanceof Optimizer)
+					ap = new AccessPathImpl((Optimizer)planKey);
+				else
+					ap = new AccessPathImpl((Optimizer)null);
+			}
 
-			ap.copy(getTrulyTheBestAccessPath());
-			optimizerToBestPlanMap.put(optimizer, ap);
+			ap.copy(bestPath);
+			optimizerToBestPlanMap.put(planKey, ap);
 			return;
 		}
 
@@ -528,22 +553,21 @@
 		// into this Optimizable's trulyTheBestAccessPath field.
 
 		// If we don't have any plans saved, then there's nothing to load.
-		// This can happen if the optimizer tried some join order for which
-		// there was no valid plan.
+		// This can happen if the key is an OptimizerImpl that tried some
+		// join order for which there was no valid plan.
 		if (optimizerToBestPlanMap == null)
 			return;
 
-		ap = (AccessPathImpl)optimizerToBestPlanMap.get(optimizer);
+		ap = (AccessPathImpl)optimizerToBestPlanMap.get(planKey);
 
-		// Again, might be the case that there is no plan stored for
-		// the optimizer if no valid plans have been discovered for
-		// that optimizer's current join order.
-		if (ap == null)
+		// It might be the case that there is no plan stored for
+		// the key, in which case there's nothing to load.
+		if ((ap == null) || (ap.getCostEstimate() == null))
 			return;
 
 		// We found a best plan in our map, so load it into this Optimizable's
 		// trulyTheBestAccessPath field.
-		getTrulyTheBestAccessPath().copy(ap);
+		bestPath.copy(ap);
 		return;
 	}
 
@@ -577,7 +601,23 @@
 		// join order of the received optimizer, take note of what
 		// that path is, in case we need to "revert" back to this
 		// path later.  See Optimizable.addOrLoadBestPlanMapping().
-		addOrLoadBestPlanMapping(true, optimizer);
+		// Note: Since this call descends all the way down to base
+		// tables, it can be relatively expensive when we have deeply
+		// nested subqueries.  So in an attempt to save some work, we
+		// skip the call if this node is a ProjectRestrictNode whose
+		// child is an Optimizable--in that case the ProjectRestrictNode
+		// will in turn call "rememberAsBest" on its child and so
+		// the required call to addOrLoadBestPlanMapping() will be
+		// made at that time.  If we did it here, too, then we would
+		// just end up duplicating the work.
+		if (!(this instanceof ProjectRestrictNode))
+			addOrLoadBestPlanMapping(true, optimizer);
+		else
+		{
+			ProjectRestrictNode prn = (ProjectRestrictNode)this;
+			if (!(prn.getChildResult() instanceof Optimizable))
+				addOrLoadBestPlanMapping(true, optimizer);
+		}
 		 
 		/* also store the name of the access path; i.e index name/constraint
 		 * name if we're using an index to access the base table.
@@ -655,6 +695,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 */

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java Thu Apr 27 16:42:02 2006
@@ -1193,6 +1193,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/GroupByNode.java Thu Apr 27 16:42:02 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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/HashTableNode.java Thu Apr 27 16:42:02 2006
@@ -322,11 +322,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();
 		acb.pushThisAsActivation(mb);
 
 		// if there is no searchClause, we just want to pass null.

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/IntersectOrExceptNode.java Thu Apr 27 16:42:02 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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java Thu Apr 27 16:42:02 2006
@@ -170,6 +170,18 @@
 	{
 		optimizer.trace(Optimizer.CALLING_ON_JOIN_NODE, 0, 0, 0.0, null);
 
+		// It's possible that a call to optimize the left/right will cause
+		// a new "truly the best" plan to be stored in the underlying base
+		// tables.  If that happens and then we decide to skip that plan
+		// (which we might do if the call to "considerCost()" below decides
+		// the current path is infeasible or not the best) we need to be
+		// able to revert back to the "truly the best" plans that we had
+		// saved before we got here.  So with this next call we save the
+		// current plans using "this" node as the key.  If needed, we'll
+		// then make the call to revert the plans in OptimizerImpl's
+		// getNextDecoratedPermutation() method.
+		addOrLoadBestPlanMapping(true, this);
+
 		/*
 		** RESOLVE: Most types of Optimizables only implement estimateCost(),
 		** and leave it up to optimizeIt() in FromTable to figure out the
@@ -1572,16 +1584,8 @@
 		mb.push(rightResultSet.resultColumns.size()); // arg 4
 		acb.pushThisAsActivation(mb); // arg 5
 
-		// 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
@@ -1649,6 +1653,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/MaterializeResultSetNode.java Thu Apr 27 16:42:02 2006
@@ -109,10 +109,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java Thu Apr 27 16:42:02 2006
@@ -155,6 +155,19 @@
 	// 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;
+
+	// Have we already delayed timeout for the current round of
+	// optimization?  We need this flag to make sure we don't
+	// infinitely delay the timeout for the current round.
+	private boolean alreadyDelayedTimeout;
+	
 	protected  OptimizerImpl(OptimizableList optimizableList, 
 				  OptimizablePredicateList predicateList,
 				  DataDictionary dDictionary,
@@ -232,6 +245,8 @@
 		timeOptimizationStarted = System.currentTimeMillis();
 		reloadBestPlan = false;
 		savedJoinOrders = null;
+		timeLimit = Double.MAX_VALUE;
+		alreadyDelayedTimeout = false;
 	}
 
 	/**
@@ -243,7 +258,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 +266,69 @@
 		// 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);
+
+		/* If we have predicates that were pushed down to this OptimizerImpl
+		 * from an outer query, then we reset the timeout state to prepare for
+		 * the next round of optimization.  Otherwise if we timed out during
+		 * a previous round and then we get here for another round, we'll
+		 * immediately "timeout" again before optimizing any of the Optimizables
+		 * in our list.  This is okay if we don't have any predicates from
+		 * outer queries because in that case the plan we find this round
+		 * will be the same one we found in the previous round, in which
+		 * case there's no point in resetting the timeout state and doing
+		 * the work a second time.  But if we have predicates from an outer
+		 * query, those predicates could help us find a much better plan
+		 * this round than we did in previous rounds--so we reset the timeout
+		 * state to ensure that we have a chance to consider plans that
+		 * can take advantage of the pushed predicates.
+		 */
+		boolean resetTimer = false;
+		if ((predicateList != null) && (predicateList.size() > 0))
+		{
+			for (int i = predicateList.size() - 1; i >= 0; i--)
+			{
+				// If the predicate is "scoped", then we know it was pushed
+				// here from an outer query.
+				if (((Predicate)predicateList.
+					getOptPredicate(i)).isScopedForPush())
+				{
+					resetTimer = true;
+					break;
+				}
+			}
+		}
+
+		if (resetTimer)
+		{
+			timeOptimizationStarted = System.currentTimeMillis();
+			timeExceeded = false;
+		}
+
+		alreadyDelayedTimeout = false;
 	}
 
     public int getMaxMemoryPerTable()
@@ -299,8 +377,7 @@
 			** the current best cost.
 			*/
 			currentTime = System.currentTimeMillis();
-			timeExceeded = (currentTime - timeOptimizationStarted) >
-									bestCost.getEstimatedCost();
+			timeExceeded = (currentTime - timeOptimizationStarted) > timeLimit;
 
 			if (optimizerTrace && timeExceeded)
 			{
@@ -309,6 +386,76 @@
 		}
 
 		/*
+		 * It's possible that we can end up with an uninitialized cost after
+		 * this round of optimization if there's no feasible join order.  In
+		 * that case the following call to "isUninitialized()" will repeatedly
+		 * return true, which could cause us to delay the timeout indefinitely.
+		 * For this reason we have the "alreadyDelayedTimeout" flag, which we
+		 * set the first time through and then, if we get here again for a
+		 * complete join order in the same round, we skip the "delay" and just
+		 * allow the timeout to occur.  The check for "if we get here again"
+		 * is done via the alreadyDelayedTimeout flag, which is reset before
+		 * each round of optimization; the check for "a complete join order"
+		 * is done by looking to see if the current join position is the
+		 * final one.
+		 */
+		if (timeExceeded && bestCost.isUninitialized() &&
+			(!alreadyDelayedTimeout || (joinPosition < numOptimizables - 1)))
+		{
+			/* We can get here if this OptimizerImpl is for a subquery
+			 * that timed out for a previous permutation of the outer
+			 * query, but then the outer query itself did _not_ timeout.
+			 * In that case we'll end up back here for another round of
+			 * optimization, but our timeExceeded flag will be true.
+			 * We don't want to reset all of the timeout state here
+			 * because that could lead to redundant work (see comments
+			 * in prepForNextRound()), but we also don't want to return
+			 * without having a plan, because then we'd return an unfairly
+			 * high "bestCost" value--i.e. Double.MAX_VALUE.  Note that
+			 * we can't just revert back to whatever bestCost we had
+			 * prior to this because that cost is for some previous
+			 * permutation of the outer query--not the current permutation--
+			 * and thus would be incorrect.  So instead we have to delay
+			 * the timeout until we find a complete (and valid) join order,
+			 * so that we can return a valid cost estimate.  Once we have
+			 * a valid cost we'll then go through the timeout logic
+			 * and stop optimizing.
+			 * 
+			 * All of that said, instead of just trying the first possible
+			 * join order, we jump to the join order that gave us the best
+			 * cost in previous rounds.  We know that such a join order exists
+			 * because that's how our timeout value was set to begin with--so
+			 * if there was no best join order, we never would have timed out
+			 * and thus we wouldn't be here.
+			 */
+			if (permuteState != JUMPING)
+			{
+				// By setting firstLookOrder to our target join order
+				// and then setting our permuteState to JUMPING, we'll
+				// jump to the target join order and get the cost.  That
+				// cost will then be saved as bestCost, allowing us to
+				// proceed with normal timeout logic.
+				for (int i = 0; i < numOptimizables; i++)
+					firstLookOrder[i] = bestJoinOrder[i];
+				permuteState = JUMPING;
+
+				// If we were in the middle of a join order when this
+				// happened, then reset the join order before jumping.
+				if (joinPosition > 0)
+					rewindJoinOrder();
+			}
+
+			// Reset the timeExceeded flag so that we'll keep going
+			// until we find a complete join order.  NOTE: we intentionally
+			// do _not_ reset the timeOptimizationStarted value because we
+			// we want to go through this timeout logic for every
+			// permutation, to make sure we timeout as soon as we have
+			// our first complete join order.
+			timeExceeded = false;
+			alreadyDelayedTimeout = true;
+		}
+
+		/*
 		** 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
@@ -1069,6 +1216,38 @@
 										(OptimizablePredicateList) null,
 										currentRowOrdering);
 
+		// If the previous path that we considered for curOpt was _not_ the best
+		// path for this round, then we need to revert back to whatever the
+		// best plan for curOpt was this round.  Note that the cost estimate
+		// for bestAccessPath could be null here if the last path that we
+		// checked was the only one possible for this round.
+		if ((curOpt.getBestAccessPath().getCostEstimate() != null) &&
+			(curOpt.getCurrentAccessPath().getCostEstimate() != null))
+		{
+			// Note: we can't just check to see if bestCost is cheaper
+			// than currentCost because it's possible that currentCost
+			// is actually cheaper--but it may have been 'rejected' because
+			// it would have required too much memory.  So we just check
+			// to see if bestCost and currentCost are different.  If so
+			// then we know that the most recent access path (represented
+			// by "current" access path) was not the best.
+			if (curOpt.getBestAccessPath().getCostEstimate().compare(
+				curOpt.getCurrentAccessPath().getCostEstimate()) != 0)
+			{
+				curOpt.addOrLoadBestPlanMapping(false, curOpt);
+			}
+			else if (curOpt.getBestAccessPath().getCostEstimate().rowCount() <
+				curOpt.getCurrentAccessPath().getCostEstimate().rowCount())
+			{
+				// If currentCost and bestCost have the same cost estimate
+				// but currentCost has been rejected because of memory, we
+				// still need to revert the plans.  In this case the row
+				// count for currentCost will be greater than the row count
+				// for bestCost, so that's what we just checked.
+				curOpt.addOrLoadBestPlanMapping(false, curOpt);
+			}
+		}
+
 		/*
 		** When all the access paths have been looked at, we know what the
 		** cheapest one is, so remember it.  Only do this if a cost estimate
@@ -1213,8 +1392,24 @@
 				** NOTE: If the user has specified a join order, it will be the
 				** only join order the optimizer considers, so it is OK to use
 				** costing to decide that it is the "best" join order.
+				**
+				** For very deeply nested queries, it's possible that the optimizer
+				** will return an estimated cost of Double.INFINITY, which is
+				** greater than our uninitialized cost of Double.MAX_VALUE and
+				** thus the "compare" check below will return false.   So we have
+				** to check to see if bestCost is uninitialized and, if so, we
+				** save currentCost regardless of what value it is--because we
+				** haven't found anything better yet.
+				**
+				** That said, it's also possible for bestCost to be infinity
+				** AND for current cost to be infinity, as well.  In that case
+				** we can't really tell much by comparing the two, so for lack
+				** of better alternative we look at the row counts.  See
+				** CostEstimateImpl.compare() for more.
 				*/
-				if ((! foundABestPlan) || currentCost.compare(bestCost) < 0)
+				if ((! foundABestPlan) ||
+					(currentCost.compare(bestCost) < 0) ||
+					bestCost.isUninitialized())
 				{
 					rememberBestCost(currentCost, Optimizer.NORMAL_PLAN);
 
@@ -1259,7 +1454,8 @@
 							trace(CURRENT_PLAN_IS_SA_PLAN, 0, 0, 0.0, null);
 						}
 
-						if (currentSortAvoidanceCost.compare(bestCost) <= 0)
+						if ((currentSortAvoidanceCost.compare(bestCost) <= 0)
+							|| bestCost.isUninitialized())
 						{
 							rememberBestCost(currentSortAvoidanceCost,
 											Optimizer.SORT_AVOIDANCE_PLAN);
@@ -1296,6 +1492,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.
@@ -1612,6 +1817,15 @@
 														outerCost,
 														optimizable);
 
+		// Before considering the cost, make sure we set the optimizable's
+		// "current" cost to be the one that we found.  Doing this allows
+		// us to compare "current" with "best" later on to find out if
+		// the "current" plan is also the "best" one this round--if it's
+		// not then we'll have to revert back to whatever the best plan is.
+		// That check is performed in getNextDecoratedPermutation() of
+		// this class.
+		optimizable.getCurrentAccessPath().setCostEstimate(estimatedCost);
+
 		/*
 		** Skip this access path if it takes too much memory.
 		**
@@ -1633,6 +1847,7 @@
 		CostEstimate bestCostEstimate = ap.getCostEstimate();
 
 		if ((bestCostEstimate == null) ||
+			bestCostEstimate.isUninitialized() ||
 			(estimatedCost.compare(bestCostEstimate) < 0))
 		{
 			ap.setConglomerateDescriptor(cd);
@@ -1680,6 +1895,7 @@
 
 					/* Is this the cheapest sort-avoidance path? */
 					if ((bestCostEstimate == null) ||
+						bestCostEstimate.isUninitialized() ||
 						(estimatedCost.compare(bestCostEstimate) < 0))
 					{
 						ap.setConglomerateDescriptor(cd);
@@ -1732,15 +1948,21 @@
 			return;
 		}
 
+		// Before considering the cost, make sure we set the optimizable's
+		// "current" cost to be the one that we received.  Doing this allows
+		// us to compare "current" with "best" later on to find out if
+		// the "current" plan is also the "best" one this round--if it's
+		// not then we'll have to revert back to whatever the best plan is.
+		// That check is performed in getNextDecoratedPermutation() of
+		// this class.
+		optimizable.getCurrentAccessPath().setCostEstimate(estimatedCost);
+
 		/*
 		** Skip this access path if it takes too much memory.
 		**
 		** NOTE: The default assumption here is that the number of rows in
 		** a single scan is the total number of rows divided by the number
 		** of outer rows.  The optimizable may over-ride this assumption.
-		**
-		** NOTE: This is probably not necessary here, because we should
-		** get here only for nested loop joins, which don't use memory.
 		*/
         if( ! optimizable.memoryUsageOK( estimatedCost.rowCount() / outerCost.rowCount(),
                                          maxMemoryPerTable))
@@ -1765,6 +1987,7 @@
 		CostEstimate bestCostEstimate = ap.getCostEstimate();
 
 		if ((bestCostEstimate == null) ||
+			bestCostEstimate.isUninitialized() ||
 			(estimatedCost.compare(bestCostEstimate) <= 0))
 		{
 			ap.setCostEstimate(estimatedCost);
@@ -1799,6 +2022,7 @@
 
 					/* Is this the cheapest sort-avoidance path? */
 					if ((bestCostEstimate == null) ||
+						bestCostEstimate.isUninitialized() ||
 						(estimatedCost.compare(bestCostEstimate) < 0))
 					{
 						ap.setCostEstimate(estimatedCost);
@@ -1884,6 +2108,39 @@
 		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 */
 	public void setOuterRows(double outerRows)
 	{
@@ -2041,52 +2298,61 @@
 	 * necessary.
 	 *
 	 * @param doAdd True if we're adding a mapping, false if we're loading.
-	 * @param outerOptimizer OptimizerImpl corresponding to an outer
-	 *  query; we will use this as the key for the mapping.
+	 * @param planKey Object to use as the map key when adding/looking up
+	 *  a plan.  If this is an instance of OptimizerImpl then it corresponds
+	 *  to an outer query; otherwise it's some Optimizable above this
+	 *  OptimizerImpl that could potentially reject plans chosen by this
+	 *  OptimizerImpl.
 	 */
 	protected void addOrLoadBestPlanMappings(boolean doAdd,
-		Optimizer outerOptimizer) throws StandardException
+		Object planKey) throws StandardException
 	{
-		// First we save this OptimizerImpl's best join order.
-		int [] joinOrder = null;
-		if (doAdd)
-		{
-			// If the savedJoinOrder map already exists, search for the
-			// join order for the target optimizer and reuse that.
-			if (savedJoinOrders == null)
-				savedJoinOrders = new HashMap();
-			else
-				joinOrder = (int[])savedJoinOrders.get(outerOptimizer);
+		// First we save this OptimizerImpl's best join order.  If there's
+		// only one optimizable in the list, then there's only one possible
+		// join order, so don't bother.
+		if (numOptimizables > 1)
+		{
+			int [] joinOrder = null;
+			if (doAdd)
+			{
+				// If the savedJoinOrder map already exists, search for the
+				// join order for the target optimizer and reuse that.
+				if (savedJoinOrders == null)
+					savedJoinOrders = new HashMap();
+				else
+					joinOrder = (int[])savedJoinOrders.get(planKey);
 
-			// If we don't already have a join order array for the optimizer,
-			// create a new one.
-			if (joinOrder == null)
-				joinOrder = new int[numOptimizables];
-
-			// Now copy current bestJoinOrder and save it.
-			for (int i = 0; i < bestJoinOrder.length; i++)
-				joinOrder[i] = bestJoinOrder[i];
+				// If we don't already have a join order array for the optimizer,
+				// create a new one.
+				if (joinOrder == null)
+					joinOrder = new int[numOptimizables];
+
+				// Now copy current bestJoinOrder and save it.
+				for (int i = 0; i < bestJoinOrder.length; i++)
+					joinOrder[i] = bestJoinOrder[i];
 
-			savedJoinOrders.put(outerOptimizer, joinOrder);
-		}
-		else
-		{
-			// If we get here, we want to load the best join order from our
-			// map into this OptimizerImpl's bestJoinOrder array.
+				savedJoinOrders.put(planKey, joinOrder);
+			}
+			else
+			{
+				// If we get here, we want to load the best join order from our
+				// map into this OptimizerImpl's bestJoinOrder array.
 
-			// If we don't have any join orders saved, then there's nothing to
-			// load.  This can happen if the optimizer tried some join order
-			// for which there was no valid plan.
-			if (savedJoinOrders == null)
-				return;
-
-			joinOrder = (int[])savedJoinOrders.get(outerOptimizer);
-			if (joinOrder == null)
-				return;
-
-			// Load the join order we found into our bestJoinOrder array.
-			for (int i = 0; i < joinOrder.length; i++)
-				bestJoinOrder[i] = joinOrder[i];
+				// If we don't have any join orders saved, then there's nothing to
+				// load.  This can happen if the optimizer tried some join order
+				// for which there was no valid plan.
+				if (savedJoinOrders != null)
+				{
+					joinOrder = (int[])savedJoinOrders.get(planKey);
+					if (joinOrder != null)
+					{
+						// Load the join order we found into our
+						// bestJoinOrder array.
+						for (int i = 0; i < joinOrder.length; i++)
+							bestJoinOrder[i] = joinOrder[i];
+					}
+				}
+			}
 		}
 
 		// Now iterate through all Optimizables in this OptimizerImpl's list
@@ -2095,8 +2361,56 @@
 		for (int i = optimizableList.size() - 1; i >= 0; i--)
 		{
 			optimizableList.getOptimizable(i).
-				addOrLoadBestPlanMapping(doAdd, outerOptimizer);
+				addOrLoadBestPlanMapping(doAdd, planKey);
 		}
+	}
+
+	/**
+	 * Add predicates to this optimizer's predicateList. This method
+	 * is intended for use during the modifyAccessPath() phase of
+	 * compilation, as it allows nodes (esp. SelectNodes) to add to the
+	 * list of predicates available for the final "push" before code
+	 * generation.  Just as the constructor for this class allows a
+	 * caller to specify a predicate list to use during the optimization
+	 * phase, this method allows a caller to specify a predicate list to
+	 * use during the modify-access-paths phase.
+	 *
+	 * Before adding the received predicates, this method also
+	 * clears out any scoped predicates that might be sitting in
+	 * OptimizerImpl's list from the last round of optimizing.
+	 *
+	 * @param pList List of predicates to add to this OptimizerImpl's
+	 *  own list for pushing.
+	 */
+	protected void addPredicatesToList(PredicateList pList)
+		throws StandardException
+	{
+		if ((pList == null) || (pList == predicateList))
+		// nothing to do.
+			return;
+
+		if (predicateList == null)
+		// in this case, there is no 'original' predicateList, so we
+		// can just create one.
+			predicateList = new PredicateList();
+
+		// First, we need to go through and remove any predicates in this
+		// optimizer's list that may have been pushed here from outer queries
+		// during the previous round(s) of optimization.  We know if the
+		// predicate was pushed from an outer query because it will have
+		// been scoped to the node for which this OptimizerImpl was
+		// created.
+		Predicate pred = null;
+		for (int i = predicateList.size() - 1; i >= 0; i--) {
+			pred = (Predicate)predicateList.getOptPredicate(i);
+			if (pred.isScopedForPush())
+				predicateList.removeOptPredicate(i);
+		}
+
+		// Now transfer all of the received predicates into this
+		// OptimizerImpl's list.
+		pList.transferAllPredicates(predicateList);
+		return;
 	}
 
 }

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OrderByList.java Thu Apr 27 16:42:02 2006
@@ -401,7 +401,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/Predicate.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/Predicate.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/Predicate.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/Predicate.java Thu Apr 27 16:42:02 2006
@@ -864,8 +864,10 @@
 	 * Determine whether or not this predicate is eligible for
 	 * push-down into subqueries.  Right now the only predicates
 	 * we consider to be eligible are those which 1) are Binary
-	 * Relational operator nodes, and 2) have a column reference
-	 * on BOTH sides.
+	 * Relational operator nodes, 2) have a column reference
+	 * on BOTH sides, and 3) have column references such that
+	 * each column reference has a reference to a base table
+	 * somewhere beneath it.
 	 *
 	 * @return Whether or not this predicate is eligible to be
 	 *  pushed into subqueries.
@@ -884,8 +886,35 @@
 		BinaryRelationalOperatorNode opNode =
 			(BinaryRelationalOperatorNode)getAndNode().getLeftOperand();
 
-		return ((opNode.getLeftOperand() instanceof ColumnReference) &&
-				(opNode.getRightOperand() instanceof ColumnReference));
+		// If either side is not a column reference, we don't push.
+		if (!((opNode.getLeftOperand() instanceof ColumnReference) &&
+			(opNode.getRightOperand() instanceof ColumnReference)))
+		{
+			return false;
+		}
+
+		// Make sure both column references ultimately point to base
+		// tables.  If, for example, either column reference points to a
+		// a literal or an aggregate, then we do not push the predicate.
+		// This is because pushing involves remapping the references--
+		// but if the reference doesn't have a base table beneath it,
+		// the notion of "remapping" it doesn't (seem to) apply.  RESOLVE:
+		// it might be okay to make the "remap" operation a no-op for
+		// such column references, but it's not clear whether that's
+		// always a safe option; further investigation required.
+
+		JBitSet tNums = new JBitSet(getReferencedSet().size());
+		BaseTableNumbersVisitor btnVis = new BaseTableNumbersVisitor(tNums);
+		opNode.getLeftOperand().accept(btnVis);
+		if (tNums.getFirstSetBit() == -1)
+			return false;
+
+		tNums.clearAll();
+		opNode.getRightOperand().accept(btnVis);
+		if (tNums.getFirstSetBit() == -1)
+			return false;
+
+		return true;
 	}
 
 	/**

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java Thu Apr 27 16:42:02 2006
@@ -376,6 +376,20 @@
 			Predicate		predicate;
 			predicate = (Predicate) elementAt(index);
 
+			// This method is used by HashJoinStrategy to determine if
+			// there are any equality predicates that can be used to
+			// perform a hash join (see the findHashKeyColumns()
+			// method in HashJoinStrategy.java).  That said, if the
+			// predicate was scoped and pushed down from an outer query,
+			// then it's no longer possible to perform the hash join
+			// because one of the operands is in an outer query and
+			// the other (scoped) operand is down in a subquery. Thus
+			// we skip this predicate if it has been scoped.
+			if (predicate.isScopedForPush())
+			{
+				continue;
+			}
+
 			andNode = (AndNode) predicate.getAndNode();
 
 			ValueNode opNode = andNode.getLeftOperand();

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java Thu Apr 27 16:42:02 2006
@@ -293,6 +293,18 @@
 		// if (childResultOptimized)
 		// 	return costEstimate;
 
+		// It's possible that a call to optimize the left/right will cause
+		// a new "truly the best" plan to be stored in the underlying base
+		// tables.  If that happens and then we decide to skip that plan
+		// (which we might do if the call to "considerCost()" below decides
+		// the current path is infeasible or not the best) we need to be
+		// able to revert back to the "truly the best" plans that we had
+		// saved before we got here.  So with this next call we save the
+		// current plans using "this" node as the key.  If needed, we'll
+		// then make the call to revert the plans in OptimizerImpl's
+		// getNextDecoratedPermutation() method.
+		addOrLoadBestPlanMapping(true, this);
+
 		/* If the childResult is instanceof Optimizable, then we optimizeIt.
 		 * Otherwise, we are going into a new query block.  If the new query
 		 * block has already had its access path modified, then there is
@@ -312,7 +324,16 @@
 							childCost.rowCount(),
 							childCost.singleScanRowCount());
 
-			optimizer.considerCost(this, restrictionList, getCostEstimate(), outerCost);
+
+			// Note: we don't call "optimizer.considerCost()" here because
+			// a) the child will make that call as part of its own
+			// "optimizeIt()" work above, and b) the child might have
+			// different criteria for "considering" (i.e. rejecting or
+			// accepting) a plan's cost than this ProjectRestrictNode does--
+			// and we don't want to override the child's decision.  So as
+			// with most operations in this class, if the child is an
+			// Optimizable, we just let it do its own work and make its
+			// own decisions.
 		}
 		else if ( ! accessPathModified)
 		{
@@ -379,7 +400,25 @@
 		 */
 		if (childResult instanceof Optimizable)
 		{
-			return ((Optimizable) childResult).feasibleJoinStrategy(restrictionList, optimizer);
+			// With DERBY-805 it's possible that, when considering a nested
+			// loop join with this PRN, we pushed predicates down into the
+			// child if the child is a UNION node.  At this point, though, we
+			// may be considering doing a hash join with this PRN instead of a
+			// nested loop join, and if that's the case we need to pull any
+			// predicates back up so that they can be searched for equijoins
+			// that will in turn make the hash join possible.  So that's what
+			// the next call does.  Two things to note: 1) if no predicates
+			// were pushed, this call is a no-op; and 2) if we get here when
+			// considering a nested loop join, the predicates that we pull
+			// here (if any) will be re-pushed for subsequent costing/ 
+			// optimization as necessary (see OptimizerImpl.costPermutation(),
+			// which will call this class's optimizeIt() method and that's
+			// where the predicates are pushed down again).
+			if (childResult instanceof UnionNode)
+				((UnionNode)childResult).pullOptPredicates(restrictionList);
+
+			return ((Optimizable) childResult).
+				feasibleJoinStrategy(restrictionList, optimizer);
 		}
 		else
 		{
@@ -501,6 +540,11 @@
 	{
 		if (restrictionList != null)
 		{
+			// Pull up any predicates that may have been pushed further
+			// down the tree during optimization.
+			if (childResult instanceof UnionNode)
+				((UnionNode)childResult).pullOptPredicates(restrictionList);
+
 			RemapCRsVisitor rcrv = new RemapCRsVisitor(false);
 			for (int i = restrictionList.size() - 1; i >= 0; i--)
 			{
@@ -539,6 +583,7 @@
 		** Do nothing if the child result set is not optimizable, as there
 		** can be nothing to modify.
 		*/
+		boolean alreadyPushed = false;
 		if ( ! (childResult instanceof Optimizable))
 		{
 			// Remember that the original child was not Optimizable
@@ -588,12 +633,41 @@
 			{
 				trulyTheBestAccessPath = (AccessPathImpl) ((Optimizable) childResult).getTrulyTheBestAccessPath();
 			}
-			childResult = 
-				(ResultSetNode)
-					((FromTable) childResult).modifyAccessPath(outerTables);
+
+			// If the childResult is a SetOperatorNode (esp. a UnionNode),
+			// then it's possible that predicates in our restrictionList are
+			// supposed to be pushed further down the tree (as of DERBY-805).
+			// We passed the restrictionList down when we optimized the child
+			// so that the relevant predicates could be pushed further as part
+			// of the optimization process; so now that we're finalizing the
+			// paths, we need to do the same thing: i.e. pass restrictionList
+			// down so that the predicates that need to be pushed further
+			// _can_ be pushed further.
+			if (childResult instanceof SetOperatorNode) {
+				childResult = (ResultSetNode)
+					((SetOperatorNode) childResult).modifyAccessPath(
+						outerTables, restrictionList);
+
+				// Take note of the fact that we already pushed predicates
+				// as part of the modifyAccessPaths call.  This is necessary
+				// because there may still be predicates in restrictionList
+				// that we intentionally decided not to push (ex. if we're
+				// going to do hash join then we chose to not push the join
+				// predicates).  Whatever the reason for not pushing the
+				// predicates, we have to make sure we don't inadvertenly
+				// push them later (esp. as part of the "pushUsefulPredicates"
+				// call below).
+				alreadyPushed = true;
+			}
+			else {
+				childResult = 
+					(ResultSetNode) ((FromTable) childResult).
+						modifyAccessPath(outerTables);
+			}
 		}
 
-		if (restrictionList != null)
+
+		if ((restrictionList != null) && !alreadyPushed)
 		{
 			restrictionList.pushUsefulPredicates((Optimizable) childResult);
 		}
@@ -1119,19 +1193,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;
 	}
 
     /**
@@ -1312,11 +1389,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();
 
 		acb.pushThisAsActivation(mb);
 
@@ -1423,8 +1497,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java Thu Apr 27 16:42:02 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.
@@ -182,17 +187,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;
 	}
 
 	/**
@@ -894,6 +900,23 @@
 		return this;
 	}
 
+	/**
+	 * Modify the access paths according to the decisions the optimizer
+	 * made.  This can include adding project/restrict nodes,
+	 * index-to-base-row nodes, etc.
+	 *
+	 * @param predList A list of optimizable predicates that should
+	 *  be pushed to this ResultSetNode, as determined by optimizer.
+	 * @return The modified query tree
+	 * @exception StandardException        Thrown on error
+	 */
+	public ResultSetNode modifyAccessPaths(PredicateList predList)
+		throws StandardException
+	{
+		// Default behavior is to call the no-arg version of this method.
+		return modifyAccessPaths();
+	}
+
 	ResultColumnDescriptor[] makeResultDescriptors(ExecutionContext ec)
 	{
 	    return resultColumns.makeResultDescriptors(ec);
@@ -1638,23 +1661,25 @@
 								getLanguageConnectionContext());
 		}
 
-		((OptimizerImpl)optimizer).prepForNextRound();
+		optimizer.prepForNextRound();
 		return optimizer;
 	}
 
 	/**
-	 * Get the optimizer for this result set; assumption is that
-	 * this.optimizer has already been created by the getOptimizer()
-	 * method above.
-	 */
-	protected OptimizerImpl getOptimizerImpl() {
-
-		if (SanityManager.DEBUG) {
-			SanityManager.ASSERT(optimizer != null,
-				"Tried to retrieve optimizer for a result set, but no such " +
-				"optimizer existed.");
-		}
-
+	 * Get the optimizer for this result set.
+	 * 
+	 * @return If this.optimizer has has already been created by the
+	 *  getOptimizer() method above, then return it; otherwise,
+	 *  return null.
+	 */
+	protected OptimizerImpl getOptimizerImpl()
+	{
+		// Note that the optimizer might be null because it's possible that
+		// we'll get here before any calls to getOptimizer() were made, which
+		// can happen if we're trying to save a "best path" but we haven't
+		// actually found one yet.  In that case we just return the "null"
+		// value; the caller must check for it and behave appropriately.
+		// Ex. see TableOperatorNode.addOrLoadBestPlanMapping().
 		return (OptimizerImpl)optimizer;
 	}
 

Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/RowResultSetNode.java Thu Apr 27 16:42:02 2006
@@ -667,6 +667,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/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java?rev=397682&r1=397681&r2=397682&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java Thu Apr 27 16:42:02 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;
@@ -1580,7 +1581,84 @@
 		SanityManager.ASSERT(selectSubquerys != null,
 			"selectSubquerys is expected to be non-null");
 
+		/* If this select node is the child of an outer node that is
+		 * being optimized, we can get here multiple times (once for
+		 * every permutation that is done for the outer node).  With
+		 * DERBY-805, we can add optimizable predicates to the WHERE
+		 * list as part of this method; thus, before proceeding we
+		 * need go through and remove any opt predicates that we added
+		 * to our WHERE list the last time we were here; if we don't
+		 * do that, we'll end up with the same predicates in our
+		 * WHERE list multiple times, which can lead to incorrect
+		 * optimization.
+		 */
+
+		if (wherePredicates != null)
+		{
+			// Iterate backwards because we might be deleting entries.
+			for (int i = wherePredicates.size() - 1; i >= 0; i--)
+			{
+				if (((Predicate)wherePredicates.elementAt(i)).isScopedForPush())
+					wherePredicates.removeOptPredicate(i);
+			}
+		}
+
 		/* Get a new optimizer */
+
+		/* With DERBY-805 we take any optimizable predicates that
+		 * were pushed into this node and we add them to the list of
+		 * predicates that we pass to the optimizer, thus allowing
+		 * the optimizer to use them when choosing an access path
+		 * for this SELECT node.  We do that by adding the predicates
+		 * to our WHERE list, since the WHERE predicate list is what
+		 * we pass to the optimizer for this select node (see below).
+		 * We have to pass the WHERE list directly (as opposed to
+		 * passing a copy) because the optimizer is only created one
+		 * time; it then uses the list we pass it for the rest of the
+		 * optimization phase and finally for "modifyAccessPaths()".
+		 * Since the optimizer can update/modify the list based on the
+		 * WHERE predicates (such as by adding internal predicates or
+		 * by modifying the actual predicates themselves), we need
+		 * those changes to be applied to the WHERE list directly for
+		 * subsequent processing (esp. for modification of the access
+		 * path).  Note that by adding outer opt predicates directly
+		 * to the WHERE list, we're changing the semantics of this
+		 * SELECT node.  This is only temporary, though--once the
+		 * optimizer is done with all of its work, any predicates
+		 * that were pushed here will have been pushed even further
+		 * down and thus will have been removed from the WHERE list
+		 * (if it's not possible to push them further down, then they
+		 * shouldn't have made it this far to begin with).
+		 */
+		if (predicateList != null)
+		{
+			if (wherePredicates == null) {
+				wherePredicates = (PredicateList) getNodeFactory().getNode(
+						C_NodeTypes.PREDICATE_LIST,
+						getContextManager());
+			}
+
+			Predicate pred = null;
+			int sz = predicateList.size();
+			for (int i = sz - 1; i >= 0; i--)
+			{
+				// We can tell if a predicate was pushed into this select
+				// node because it will have been "scoped" for this node;
+				// see Predicate.getScopedPredForResultSet() for more on
+				// what scoping is and how it's done.
+				pred = (Predicate)predicateList.getOptPredicate(i);
+				if (pred.isScopedForPush())
+				{
+					// If we're pushing the predicate down here, we have to
+					// remove it from the predicate list of the node above
+					// this select, in order to keep in line with established
+					// push 'protocol'.
+					wherePredicates.addOptPredicate(pred);
+					predicateList.removeOptPredicate(pred);
+				}
+			}
+		}
+
 		optimizer = getOptimizer(fromList,
 								wherePredicates,
 								dataDictionary,
@@ -1617,6 +1695,36 @@
 	}
 
 	/**
+	 * Modify the access paths according to the decisions the optimizer
+	 * made.  This can include adding project/restrict nodes,
+	 * index-to-base-row nodes, etc.
+	 *
+	 * @param predList A list of optimizable predicates that should
+	 *  be pushed to this ResultSetNode, as determined by optimizer.
+	 * @return The modified query tree
+	 * @exception StandardException        Thrown on error
+	 */
+	public ResultSetNode modifyAccessPaths(PredicateList predList)
+		throws StandardException
+	{
+		// Take the received list of predicates and propagate them to the
+		// predicate list for this node's optimizer.  Then, when we call
+		// optimizer.modifyAccessPaths(), the optimizer will have the
+		// predicates and can push them down as necessary, according
+		// the join order that it has chosen.
+
+		if (SanityManager.DEBUG)
+		{
+			SanityManager.ASSERT(optimizer != null,
+				"SelectNode's optimizer not expected to be null when " +
+				"modifying access paths.");
+		}
+
+		((OptimizerImpl)optimizer).addPredicatesToList(predList);
+		return modifyAccessPaths();
+	}
+
+	/**
 	 * Modify the access paths according to the choices the optimizer made.
 	 *
 	 * @return	A QueryTree with the necessary modifications made
@@ -1638,6 +1746,37 @@
 		*/
 		optimizer.modifyAccessPaths();
 
+		// Load the costEstimate for the final "best" join order.
+		costEstimate = optimizer.getFinalCost();
+
+		if (SanityManager.DEBUG)
+		{
+			// When we optimized this select node, we may have added pushable
+			// outer predicates to the wherePredicates list for this node
+			// (see the optimize() method above).  When we did so, we said
+			// that all such predicates should have been removed from the
+			// where list by the time optimization was completed.   So we
+			// check that here, just to be safe.  NOTE: We do this _after_
+			// calling optimizer.modifyAccessPaths(), because it's only in
+			// that call that the scoped predicates are officially pushed
+			// and thus removed from the list.
+			if (wherePredicates != null)
+			{
+				Predicate pred = null;
+				for (int i = wherePredicates.size() - 1; i >= 0; i--)
+				{
+					pred = (Predicate)wherePredicates.getOptPredicate(i);
+					if (pred.isScopedForPush())
+					{
+						SanityManager.THROWASSERT("Found scoped predicate " +
+							pred.binaryRelOpColRefsToString() +
+							" in WHERE list when no scoped predicates were" +
+							" expected.");
+					}
+				}
+			}
+		}
+
 		selectSubquerys.modifyAccessPaths();
 
 		if (whereSubquerys != null && whereSubquerys.size() > 0)
@@ -1711,6 +1850,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.



Mime
View raw message