You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-commits@db.apache.org by ba...@apache.org on 2006/04/28 01:42:04 UTC
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...
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.