Author: bandaram
Date: Sat Apr 22 20:30:55 2006
New Revision: 396211
URL: http://svn.apache.org/viewcvs?rev=396211&view=rev
Log:
DERBY-805: Merge Phase I and II from trunk.
Merge commands:
svn merge -r 381858:381859 https://svn.apache.org/repos/asf/db/derby/code/trunk
svn merge -r 382199:382200 https://svn.apache.org/repos/asf/db/derby/code/trunk
svn merge -r 382562:382563 https://svn.apache.org/repos/asf/db/derby/code/trunk
Original 10.2 changes submitted by Army Brown(qozinx@sbcglobal.net)
Added:
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BaseTableNumbersVisitor.java
(props changed)
- copied unchanged from r382200, db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BaseTableNumbersVisitor.java
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/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/FromTable.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/Predicate.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/ResultColumn.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/SingleChildResultSetNode.java
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/predicatesIntoViews.out
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=396211&r1=396210&r2=396211&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
Sat Apr 22 20:30:55 2006
@@ -234,14 +234,45 @@
public int convertAbsoluteToRelativeColumnPosition(int absolutePosition);
/**
+ * When remembering "truly the best" access path for an Optimizable, we
+ * have to keep track of which OptimizerImpl the "truly the best" access
+ * is for. In most queries there will only be one OptimizerImpl in
+ * 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
+ * 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.
+ *
+ * @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.
+ */
+ public void addOrLoadBestPlanMapping(boolean doAdd,
+ Optimizer optimizer) throws StandardException;
+
+ /**
* Remember the current access path as the best one (so far).
*
* @param planType The type of plan (one of Optimizer.NORMAL_PLAN
* or Optimizer.SORT_AVOIDANCE_PLAN)
+ * @param optimizer The OptimizerImpl that is telling this Optimizable
+ * to remember its current path as "truly the best".
*
* @exception StandardException thrown on error.
*/
- public void rememberAsBest(int planType) throws StandardException;
+ public void rememberAsBest(int planType, Optimizer optimizer)
+ throws StandardException;
/**
* Begin the optimization process for this Optimizable. This can be
Propchange: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/BaseTableNumbersVisitor.java
------------------------------------------------------------------------------
svn:eol-style = native
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=396211&r1=396210&r2=396211&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
Sat Apr 22 20:30:55 2006
@@ -1116,6 +1116,190 @@
return super.genSQLJavaSQLTree();
}
+
+ /**
+ * Take a ResultSetNode and return a column reference that is scoped for
+ * for the received ResultSetNode, where "scoped" means that the column
+ * reference points to a specific column in the RSN. This is used for
+ * remapping predicates from an outer query down to a subquery.
+ *
+ * For example, assume we have the following query:
+ *
+ * select * from
+ * (select i,j from t1 union select i,j from t2) X1,
+ * (select a,b from t3 union select a,b from t4) X2
+ * where X1.j = X2.b;
+ *
+ * Then assume that this BinaryRelationalOperatorNode represents the
+ * "X1.j = X2.b" predicate and that the childRSN we received as a
+ * parameter represents one of the subqueries to which we want to push
+ * the predicate; let's say it's:
+ *
+ * select i,j from t1
+ *
+ * Then what we want to do in this method is map one of the operands
+ * X1.j or X2.b (depending on the 'whichSide' parameter) to the childRSN,
+ * if possible. Note that in our example, "X2.b" should _NOT_ be mapped
+ * because it doesn't apply to the childRSN for the subquery "select i,j
+ * from t1"; thus we should leave it as it is. "X1.j", however, _does_
+ * need to be scoped, and so this method will return a ColumnReference
+ * pointing to "T1.j" (or whatever the corresponding column in T1 is).
+ *
+ * ASSUMPTION: We should only get to this method if we know that
+ * at least one operand in the predicate to which this operator belongs
+ * can and should be mapped to the received childRSN.
+ *
+ * @param whichSide The operand are we trying to scope (LEFT or RIGHT)
+ * @param parentRSNsTables Set of all table numbers referenced by
+ * the ResultSetNode that is _parent_ to the received childRSN.
+ * We need this to make sure we don't scope the operand to a
+ * ResultSetNode to which it doesn't apply.
+ * @param childRSN The result set node to which we want to create
+ * a scoped predicate.
+ * @return A column reference scoped to the received childRSN, if possible.
+ * If the operand is a ColumnReference that is not supposed to be scoped,
+ * we return a _clone_ of the reference--this is necessary because the
+ * reference is going to be pushed to two places (left and right children
+ * of the parentRSN) and if both children are referencing the same
+ * instance of the column reference, they'll interfere with each other
+ * during optimization.
+ */
+ public ValueNode getScopedOperand(int whichSide,
+ JBitSet parentRSNsTables, ResultSetNode childRSN)
+ throws StandardException
+ {
+ ResultColumn rc = null;
+ ColumnReference cr =
+ whichSide == LEFT
+ ? (ColumnReference)leftOperand
+ : (ColumnReference)rightOperand;
+
+ // The first thing we need to do is see if this ColumnReference
+ // is supposed to be scoped for childRSN. We do that by figuring
+ // out what underlying base table the column reference is pointing
+ // to and then seeing if that base table is included in the list of
+ // table numbers from the parentRSN.
+ JBitSet crTables = new JBitSet(parentRSNsTables.size());
+ BaseTableNumbersVisitor btnVis =
+ new BaseTableNumbersVisitor(crTables);
+ cr.accept(btnVis);
+
+ // If the column reference doesn't reference any tables,
+ // then there's no point in mapping it to the child result
+ // set; just return a clone of the operand.
+ if (crTables.getFirstSetBit() == -1)
+ {
+ return (ValueNode)cr.getClone();
+ }
+
+ /* If the column reference in question is not intended for
+ * the received result set node, just leave the operand as
+ * it is (i.e. return a clone). In the example mentioned at
+ * the start of this method, this will happen when the operand
+ * is X2.b and childRSN is either "select i,j from t1" or
+ * "select i,j from t2", in which case the operand does not
+ * apply to childRSN. When we get here and try to map the
+ * "X1.j" operand, though, the following "contains" check will
+ * return true and thus we can go ahead and return a scoped
+ * version of that operand.
+ */
+ if (!parentRSNsTables.contains(crTables))
+ {
+ return (ValueNode)cr.getClone();
+ }
+
+ // If the column reference is already pointing to the
+ // correct table, then there's no need to change it.
+ if ((childRSN.getReferencedTableMap() != null) &&
+ childRSN.getReferencedTableMap().get(cr.getTableNumber()))
+ {
+ return cr;
+ }
+
+ /* Find the target ResultColumn in the received result set. At
+ * this point we know that we do in fact need to scope the column
+ * reference for childRSN, so go ahead and do it. We get the
+ * target column by column position instead of by name because
+ * it's possible that the name given for the query doesn't match
+ * the name of the actual column we're looking for. Ex.
+ *
+ * select * from
+ * (select i,j from t1 union select i,j from t2) X1 (x,y),
+ * (select a,b from t3 union select a,b from t4) X2
+ * where X1.x = X2.b;
+ *
+ * If we searched for "x" in the childRSN "select i,j from t1"
+ * we wouldn't find it. So we have to look based on position.
+ */
+
+ rc = childRSN.getResultColumns().getResultColumn(cr.getColumnNumber());
+
+ // rc shouldn't be null; if there was no matching ResultColumn at all,
+ // then we shouldn't have made it this far.
+ if (SanityManager.DEBUG)
+ {
+ SanityManager.ASSERT(rc != null,
+ "Failed to locate result column when trying to " +
+ "scope operand '" + cr.getTableName() + "." +
+ cr.getColumnName() + "'.");
+ }
+
+ /* If the ResultColumn we found has an expression that is a
+ * ColumnReference, then that column reference has all of the info
+ * we need, with one exception: the columnNumber. Depending on our
+ * depth in the tree, the ResultColumn's ColumnReference could be
+ * pointing to a base column in the FromBaseTable. In that case the
+ * ColumnReference will hold the column position as it is with respect
+ * to the FromBaseTable. But when we're scoping a column reference,
+ * we're scoping it to a ResultSetNode that sits (either directly or
+ * indirectly) above a ProjectRestrictNode that in turn sits above the
+ * FromBaseTable. This means that the scoped reference's columnNumber
+ * needs to be with respect to the PRN that sits above the base table,
+ * _not_ with respect to the FromBaseTable itself. This is important
+ * because column "1" in the PRN might not be column "1" in the
+ * underlying base table. For example, if we have base table TT with
+ * four columns (a int, b int, i int, j int) and the PRN above it only
+ * projects out columns (i,j), then column "1" for the PRN is "i", but
+ * column "1" for base table TT is "a". On the flip side, column "3"
+ * for base table TT is "i", but if we search the PRN's result columns
+ * (which match the result columns for the ResultSetNode to which
+ * we're scoping) for column "3", we won't find it.
+ *
+ * So what does all of that mean? It means that if the ResultColumn
+ * we found has an expression that's a ColumnReference, we can simply
+ * return that ColumnReference IF we set it's columnNumber correctly.
+ * Thankfully the column reference we're trying to scope ("cr") came
+ * from further up the tree and so it knows what the correct column
+ * position (namely, the position w.r.t the ProjectRestrictNode above
+ * the FromBaseTable) needs to be. So that's the column number we
+ * use.
+ */
+ if (rc.getExpression() instanceof ColumnReference)
+ {
+ // Make sure the ColumnReference's columnNumber is correct,
+ // then just return that reference. Note: it's okay to overwrite
+ // the columnNumber directly because when it eventually makes
+ // it down to the PRN over the FromBaseTable, it will be remapped
+ // for the FromBaseTable and the columnNumber will then be set
+ // correctly. That remapping is done in the pushOptPredicate()
+ // method of ProjectRestrictNode.
+ ColumnReference cRef = (ColumnReference)rc.getExpression();
+ cRef.setColumnNumber(cr.getColumnNumber());
+ return cRef;
+ }
+
+ /* We can get here if the ResultColumn's expression isn't a
+ * ColumnReference. For example, the expression would be a
+ * constant expression if childRSN represented something like:
+ *
+ * select 1, 1 from t1
+ *
+ * In this case we just return the column reference as it is
+ * because it's scoped as far as we can take it.
+ */
+ return cr;
+ }
+
}
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=396211&r1=396210&r2=396211&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
Sat Apr 22 20:30:55 2006
@@ -569,6 +569,18 @@
}
/**
+ * Set the column number for this ColumnReference. This is
+ * used when scoping predicates for pushdown.
+ *
+ * @param colNum The new column number.
+ */
+
+ public void setColumnNumber(int colNum)
+ {
+ this.columnNumber = colNum;
+ }
+
+ /**
* Get the source this columnReference
*
* @return The source of this columnReference
@@ -748,6 +760,17 @@
columnNumber = origColumnNumber;
}
+ /**
+ * Returns true if this ColumnReference has been remapped; false
+ * otherwise.
+ *
+ * @return Whether or not this ColumnReference has been remapped.
+ */
+ protected boolean hasBeenRemapped()
+ {
+ return (origSource != null);
+ }
+
/*
* Get the ResultColumn that the source points to. This is useful for
* getting what the source will be after this ColumnReference is remapped.
@@ -949,7 +972,7 @@
{
if (sourceResultSetNumber < 0)
{
- SanityManager.THROWASSERT("sourceResultSetNumber expected to be >= 0");
+ SanityManager.THROWASSERT("sourceResultSetNumber expected to be >= 0 for " + getTableName()
+ "." + getColumnName());
}
}
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=396211&r1=396210&r2=396211&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
Sat Apr 22 20:30:55 2006
@@ -52,6 +52,7 @@
import java.util.Enumeration;
import java.util.Properties;
import java.util.Vector;
+import java.util.HashMap;
/**
* A FromTable represents a table in the FROM clause of a DML statement.
@@ -99,6 +100,14 @@
private boolean considerSortAvoidancePath;
+ // Set of optimizer->trulyTheBestAccessPath mappings used to keep track
+ // of which of this Optimizable's "trulyTheBestAccessPath" was the best
+ // with respect to a specific outer query; the outer query is represented
+ // by an instance of Optimizer. Each outer query could potentially have
+ // a different idea of what this Optimizable's "best access path" is, so
+ // we have to keep track of them all.
+ HashMap optimizerToBestPlanMap;
+
//this flag tells you if all the columns from this table are projected using * from it.
//Used by replication enabled databases where the target-only view failure is detected
//using this boolean
@@ -123,6 +132,7 @@
this.correlationName = (String) correlationName;
this.tableProperties = (Properties) tableProperties;
tableNumber = -1;
+ optimizerToBestPlanMap = null;
}
/*
@@ -490,8 +500,56 @@
return absolutePosition;
}
+ /** @see Optimizable#addOrLoadBestPlanMapping */
+ public void addOrLoadBestPlanMapping(boolean doAdd,
+ Optimizer optimizer) throws StandardException
+ {
+ AccessPathImpl ap = null;
+ if (doAdd)
+ {
+ // If the optimizerToBestPlanMap already exists, search for an
+ // AccessPath for the target optimizer and use that if we can.
+ if (optimizerToBestPlanMap == null)
+ optimizerToBestPlanMap = new HashMap();
+ else
+ ap = (AccessPathImpl)optimizerToBestPlanMap.get(optimizer);
+
+ // If we don't already have an AccessPath for the optimizer,
+ // create a new one.
+ if (ap == null)
+ ap = new AccessPathImpl(optimizer);
+
+ ap.copy(getTrulyTheBestAccessPath());
+ optimizerToBestPlanMap.put(optimizer, ap);
+ return;
+ }
+
+ // If we get here, we want to load the best plan from our map
+ // 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.
+ if (optimizerToBestPlanMap == null)
+ return;
+
+ ap = (AccessPathImpl)optimizerToBestPlanMap.get(optimizer);
+
+ // 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)
+ return;
+
+ // We found a best plan in our map, so load it into this Optimizable's
+ // trulyTheBestAccessPath field.
+ getTrulyTheBestAccessPath().copy(ap);
+ return;
+ }
+
/** @see Optimizable#rememberAsBest */
- public void rememberAsBest(int planType) throws StandardException
+ public void rememberAsBest(int planType, Optimizer optimizer)
+ throws StandardException
{
AccessPath bestPath = null;
@@ -514,6 +572,12 @@
}
getTrulyTheBestAccessPath().copy(bestPath);
+
+ // Since we just set trulyTheBestAccessPath for the current
+ // 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);
/* 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.
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=396211&r1=396210&r2=396211&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
Sat Apr 22 20:30:55 2006
@@ -48,6 +48,7 @@
import org.apache.derby.iapi.util.StringUtil;
import java.util.Properties;
+import java.util.HashMap;
/**
* This will be the Level 1 Optimizer.
@@ -138,6 +139,22 @@
// max memory use per table
protected int maxMemoryPerTable;
+ // Whether or not we need to reload the best plan for an Optimizable
+ // when we "pull" it. If the latest complete join order was the
+ // best one so far, then the Optimizable will already have the correct
+ // best plan loaded so we don't need to do the extra work. But if
+ // the most recent join order was _not_ the best, then this flag tells
+ // us that we need to reload the best plan when pulling.
+ private boolean reloadBestPlan;
+
+ // Set of optimizer->bestJoinOrder mappings used to keep track of which
+ // of this OptimizerImpl's "bestJoinOrder"s was the best with respect to a
+ // a specific outer query; the outer query is represented by an instance
+ // of Optimizer. Each outer query could potentially have a different
+ // idea of what this OptimizerImpl's "best join order" is, so we have
+ // to keep track of them all.
+ private HashMap savedJoinOrders;
+
protected OptimizerImpl(OptimizableList optimizableList,
OptimizablePredicateList predicateList,
DataDictionary dDictionary,
@@ -213,6 +230,27 @@
/* Get the time that optimization starts */
timeOptimizationStarted = System.currentTimeMillis();
+ reloadBestPlan = false;
+ savedJoinOrders = null;
+ }
+
+ /**
+ * 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_ OptimizerImpl and the time a call to this OptimizerImpl's
+ * getNextPermutation() method returns FALSE. Any re-initialization
+ * of state that is required before each round should be done in this
+ * method.
+ */
+ protected void prepForNextRound()
+ {
+ // We initialize reloadBestPlan to false so that if we end up
+ // pulling an Optimizable before we find a best join order
+ // (which can happen if there is no valid join order for this
+ // round) we won't inadvertently reload the best plans based
+ // on some previous round.
+ reloadBestPlan = false;
}
public int getMaxMemoryPerTable()
@@ -700,6 +738,33 @@
*/
pullMe.pullOptPredicates(predicateList);
+ /*
+ ** When we pull an Optimizable we need to go through and
+ ** load whatever best path we found for that Optimizable
+ ** with respect to _this_ OptimizerImpl. An Optimizable
+ ** can have different "best paths" for different Optimizer
+ ** Impls if there are subqueries beneath it; we need to make
+ ** sure that when we pull it, it's holding the best path as
+ ** as we determined it to be for _us_.
+ **
+ ** NOTE: We we only reload the best plan if it's necessary
+ ** to do so--i.e. if the best plans aren't already loaded.
+ ** The plans will already be loaded if the last complete
+ ** join order we had was the best one so far, because that
+ ** means we called "rememberAsBest" on every Optimizable
+ ** in the list and, as part of that call, we will run through
+ ** and set trulyTheBestAccessPath for the entire subtree.
+ ** So if we haven't tried any other plans since then,
+ ** we know that every Optimizable (and its subtree) already
+ ** has the correct best plan loaded in its trulyTheBest
+ ** path field. It's good to skip the load in this case
+ ** because 'reloading best plans' involves walking the
+ ** entire subtree of _every_ Optimizable in the list, which
+ ** can be expensive if there are deeply nested subqueries.
+ */
+ if (reloadBestPlan)
+ pullMe.addOrLoadBestPlanMapping(false, this);
+
/* Mark current join position as unused */
proposedJoinOrder[joinPosition] = -1;
}
@@ -835,6 +900,11 @@
}
if (finishedCycle)
{
+ // We just set proposedJoinOrder[joinPosition] above, so
+ // if we're done we need to put it back to -1 to indicate
+ // that it's an empty slot. Then we rewind and pull any
+ // other Optimizables at positions < joinPosition.
+ proposedJoinOrder[joinPosition] = -1;
joinPosition--;
if (joinPosition >= 0)
{
@@ -890,6 +960,8 @@
optimizableList.getOptimizable(
proposedJoinOrder[joinPosition]);
pullMe.pullOptPredicates(predicateList);
+ if (reloadBestPlan)
+ pullMe.addOrLoadBestPlanMapping(false, this);
proposedJoinOrder[joinPosition] = -1;
if (joinPosition == 0) break;
}
@@ -1145,7 +1217,14 @@
if ((! foundABestPlan) || currentCost.compare(bestCost) < 0)
{
rememberBestCost(currentCost, Optimizer.NORMAL_PLAN);
+
+ // Since we just remembered all of the best plans,
+ // no need to reload them when pulling Optimizables
+ // from this join order.
+ reloadBestPlan = false;
}
+ else
+ reloadBestPlan = true;
/* Subtract cost of sorting from non-sort-avoidance cost */
if (requiredRowOrdering != null)
@@ -1230,7 +1309,8 @@
}
for (int i = 0; i < numOptimizables; i++)
{
- optimizableList.getOptimizable(bestJoinOrder[i]).rememberAsBest(planType);
+ optimizableList.getOptimizable(bestJoinOrder[i]).
+ rememberAsBest(planType, this);
}
/* Remember if a sort is not needed for this plan */
@@ -1951,4 +2031,72 @@
/** @see Optimizer#useStatistics */
public boolean useStatistics() { return useStatistics && optimizableList.useStatistics();
}
+
+ /**
+ * Remember the current best join order as the best one for
+ * some outer query, represented by another OptimizerImpl. Then
+ * iterate through our optimizableList and tell each Optimizable
+ * to remember its best plan with respect to the outer query.
+ * See Optimizable.addOrLoadBestPlan() for more on why this is
+ * 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.
+ */
+ protected void addOrLoadBestPlanMappings(boolean doAdd,
+ Optimizer outerOptimizer) 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);
+
+ // 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.
+
+ // 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];
+ }
+
+ // Now iterate through all Optimizables in this OptimizerImpl's list
+ // and add/load the best plan "mapping" for each one, as described in
+ // in Optimizable.addOrLoadBestPlanMapping().
+ for (int i = optimizableList.size() - 1; i >= 0; i--)
+ {
+ optimizableList.getOptimizable(i).
+ addOrLoadBestPlanMapping(doAdd, outerOptimizer);
+ }
+ }
+
}
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=396211&r1=396210&r2=396211&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
Sat Apr 22 20:30:55 2006
@@ -74,6 +74,10 @@
*/
private Hashtable searchClauseHT;
+ // Whether or not this predicate has been scoped; see the
+ // getPredScopedForResultSet() method of this class for more.
+ private boolean scoped;
+
/**
* Initializer.
*
@@ -86,6 +90,7 @@
this.andNode = (AndNode) andNode;
pushable = false;
this.referencedSet = (JBitSet) referencedSet;
+ scoped = false;
}
/*
@@ -361,6 +366,20 @@
}
/**
+ * Set whether or not this predicate is pushable. This method
+ * is intended for use when creating a copy of the predicate, ex
+ * for predicate pushdown. We choose not to add this assignment
+ * to copyFields() because the comments for that method say that
+ * it should copy all fields _except_ the two specified at init
+ * time; "pushable" is one of the two specified at init time.
+ *
+ * @param pushable Whether or not the predicate is pushable.
+ */
+ public void setPushable(boolean pushable) {
+ this.pushable = pushable;
+ }
+
+ /**
* Return the referencedSet.
*
* @return JBitSet The referencedSet.
@@ -709,8 +728,8 @@
{
if (SanityManager.DEBUG)
{
- return "referencedSet: " + referencedSet + "\n" +
- "pushable: " + pushable + "\n" +
+ return binaryRelOpColRefsToString() + "\nreferencedSet: " +
+ referencedSet + "\n" + "pushable: " + pushable + "\n" +
super.toString();
}
else
@@ -720,6 +739,58 @@
}
/**
+ * Get a string version of the column references for this predicate
+ * IF it's a binary relational operator. We only print out the
+ * names of the operands if they are column references; otherwise
+ * we just print a dummy value. This is for debugging purposes
+ * only--it's a convenient way to see what columns the predicate
+ * is referencing, especially when tracing through code and printing
+ * assert failure.
+ */
+ public String binaryRelOpColRefsToString()
+ {
+ // We only consider binary relational operators here.
+ if (!(getAndNode().getLeftOperand()
+ instanceof BinaryRelationalOperatorNode))
+ {
+ return "";
+ }
+
+ final String DUMMY_VAL = "<expr>";
+ java.lang.StringBuffer sBuf = new java.lang.StringBuffer();
+ BinaryRelationalOperatorNode opNode =
+ (BinaryRelationalOperatorNode)getAndNode().getLeftOperand();
+
+ // Get left operand's name.
+ if (opNode.getLeftOperand() instanceof ColumnReference)
+ {
+ sBuf.append(
+ ((ColumnReference)opNode.getLeftOperand()).getTableName() +
+ "." +
+ ((ColumnReference)opNode.getLeftOperand()).getColumnName()
+ );
+ }
+ else
+ sBuf.append(DUMMY_VAL);
+
+ // Get the operator type.
+ sBuf.append(" " + opNode.operator + " ");
+
+ // Get right operand's name.
+ if (opNode.getRightOperand() instanceof ColumnReference) {
+ sBuf.append(
+ ((ColumnReference)opNode.getRightOperand()).getTableName() +
+ "." +
+ ((ColumnReference)opNode.getRightOperand()).getColumnName()
+ );
+ }
+ else
+ sBuf.append(DUMMY_VAL);
+
+ return sBuf.toString();
+ }
+
+ /**
* Prints the sub-nodes of this object. See QueryTreeNode.java for
* how tree printing is supposed to work.
*
@@ -787,6 +858,177 @@
public Hashtable getSearchClauseHT() {
return searchClauseHT;
+ }
+
+ /**
+ * 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.
+ *
+ * @return Whether or not this predicate is eligible to be
+ * pushed into subqueries.
+ */
+ protected boolean pushableToSubqueries()
+ throws StandardException
+ {
+ // If the predicate isn't a binary relational operator,
+ // then we don't push it.
+ if (!(getAndNode().getLeftOperand()
+ instanceof BinaryRelationalOperatorNode))
+ {
+ return false;
+ }
+
+ BinaryRelationalOperatorNode opNode =
+ (BinaryRelationalOperatorNode)getAndNode().getLeftOperand();
+
+ return ((opNode.getLeftOperand() instanceof ColumnReference) &&
+ (opNode.getRightOperand() instanceof ColumnReference));
+ }
+
+ /**
+ * If this predicate's operator is a BinaryRelationalOperatorNode,
+ * then look at the operands and return a new, equivalent predicate
+ * that is "scoped" to the received ResultSetNode. By "scoped" we
+ * mean that the operands, which shold be column references, have been
+ * mapped to the appropriate result columns in the received RSN.
+ * This is useful for pushing predicates from outer queries down
+ * into inner queries, in which case the column references need
+ * to be remapped.
+ *
+ * For example, let V1 represent
+ *
+ * select i,j from t1 UNION select i,j from t2
+ *
+ * and V2 represent
+ *
+ * select a,b from t3 UNION select a,b from t4
+ *
+ * Then assume we have the following query:
+ *
+ * select * from V1, V2 where V1.j = V2.b
+ *
+ * Let's further assume that this Predicate object represents the
+ * "V1.j = V2.b" operator and that the childRSN we received
+ * as a parameter represents one of the subqueries to which we
+ * want to push the predicate; let's say it's:
+ *
+ * select i,j from t1
+ *
+ * Then this method will return a new predicate whose binary
+ * operator represents the expression "T1.j = V2.b" (that is, V1.j
+ * will be mapped to the corresponding column in T1). For more on
+ * how that mapping is made, see the "getScopedOperand()" method
+ * in BinaryRelationalOperatorNode.java.
+ *
+ * ASSUMPTION: We should only get to this method if we know that
+ * at least one operand in this predicate can and should be mapped
+ * to the received childRSN. For an example of where that check is
+ * made, see the pushOptPredicate() method in SetOperatorNode.java.
+ *
+ * @param parentRSNsTables Set of all table numbers referenced by
+ * the ResultSetNode that is _parent_ to the received childRSN.
+ * We need this to make sure we don't scope the operands to a
+ * ResultSetNode to which they don't apply.
+ * @param childRSN The result set node for which we want to create
+ * a scoped predicate.
+ * @return A new predicate whose operands have been scoped to the
+ * received childRSN.
+ */
+ protected Predicate getPredScopedForResultSet(
+ JBitSet parentRSNsTables, ResultSetNode childRSN)
+ throws StandardException
+ {
+ // We only deal with binary relational operators here.
+ if (!(getAndNode().getLeftOperand()
+ instanceof BinaryRelationalOperatorNode))
+ {
+ return this;
+ }
+
+ // The predicate must have an AndNode in CNF, so we
+ // need to create an AndNode representing:
+ // <scoped_bin_rel_op> AND TRUE
+ // First create the boolean constant for TRUE.
+ ValueNode trueNode = (ValueNode) getNodeFactory().getNode(
+ C_NodeTypes.BOOLEAN_CONSTANT_NODE,
+ Boolean.TRUE,
+ getContextManager());
+
+ BinaryRelationalOperatorNode opNode =
+ (BinaryRelationalOperatorNode)getAndNode().getLeftOperand();
+
+ // Create a new op node with left and right operands that point
+ // to the received result set's columns as appropriate.
+ BinaryRelationalOperatorNode newOpNode =
+ (BinaryRelationalOperatorNode) getNodeFactory().getNode(
+ opNode.getNodeType(),
+ opNode.getScopedOperand(
+ BinaryRelationalOperatorNode.LEFT,
+ parentRSNsTables,
+ childRSN),
+ opNode.getScopedOperand(
+ BinaryRelationalOperatorNode.RIGHT,
+ parentRSNsTables,
+ childRSN),
+ getContextManager());
+
+ // Bind the new op node.
+ newOpNode.bindComparisonOperator();
+
+ // Create and bind a new AND node in CNF form,
+ // i.e. "<newOpNode> AND TRUE".
+ AndNode newAnd = (AndNode) getNodeFactory().getNode(
+ C_NodeTypes.AND_NODE,
+ newOpNode,
+ trueNode,
+ getContextManager());
+ newAnd.postBindFixup();
+
+ // Categorize the new AND node; among other things, this
+ // call sets up the new operators's referenced table map,
+ // which is important for correct pushing of the new
+ // predicate.
+ JBitSet tableMap = new JBitSet(
+ childRSN.getReferencedTableMap().size());
+ newAnd.categorize(tableMap, false);
+
+ // Now put the pieces together to get a new predicate.
+ Predicate newPred = (Predicate) getNodeFactory().getNode(
+ C_NodeTypes.PREDICATE,
+ newAnd,
+ tableMap,
+ getContextManager());
+
+ // Copy all of this predicates other fields into the new predicate.
+ newPred.clearScanFlags();
+ newPred.copyFields(this);
+ newPred.setPushable(getPushable());
+
+ // Take note of the fact that the new predicate is scoped for
+ // the sake of pushing; we need this information during optimization
+ // to figure out what we should and should not "pull" back up.
+ newPred.markAsScopedForPush();
+ return newPred;
+ }
+
+ /**
+ * Indicate that this predicate is a scoped copy of some other
+ * predicate (i.e. it was created as the result of a call to
+ * getPredScopedForResultSet() on some other predicate).
+ */
+ protected void markAsScopedForPush() {
+ this.scoped = true;
+ }
+
+ /**
+ * Return whether or not this predicate is a scoped copy of
+ * another predicate.
+ */
+ protected boolean isScopedForPush() {
+ return scoped;
}
}
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=396211&r1=396210&r2=396211&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
Sat Apr 22 20:30:55 2006
@@ -198,12 +198,12 @@
/** @see Optimizable#rememberAsBest
@exception StandardException Thrown on error
*/
- public void rememberAsBest(int planType)
+ public void rememberAsBest(int planType, Optimizer optimizer)
throws StandardException
{
- super.rememberAsBest(planType);
+ super.rememberAsBest(planType, optimizer);
if (childResult instanceof Optimizable)
- ((Optimizable) childResult).rememberAsBest(planType);
+ ((Optimizable) childResult).rememberAsBest(planType, optimizer);
}
/* Don't print anything for a PRN, as their
Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ResultColumn.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ResultColumn.java?rev=396211&r1=396210&r2=396211&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ResultColumn.java
(original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/ResultColumn.java
Sat Apr 22 20:30:55 2006
@@ -1769,4 +1769,50 @@
}
}
}
+
+ /**
+ * Search the tree beneath this ResultColumn until we find
+ * the number of the table to which this RC points, and
+ * return that table number. If we can't determine which
+ * table this RC is for, then return -1.
+ *
+ * There are two places we can find the table number: 1) if
+ * our expression is a ColumnReference, then we can get the
+ * target table number from the ColumnReference and that's
+ * it; 2) if expression is a VirtualColumnNode, then if
+ * the VirtualColumnNode points to a FromBaseTable, we can
+ * get that FBT's table number; otherwise, we walk the
+ * VirtualColumnNode-ResultColumn chain and do a recursive
+ * search.
+ *
+ * @return The number of the table to which this ResultColumn
+ * points, or -1 if we can't determine that from where we are.
+ */
+ public int getTableNumber()
+ throws StandardException
+ {
+ if (expression instanceof ColumnReference)
+ return ((ColumnReference)expression).getTableNumber();
+ else if (expression instanceof VirtualColumnNode)
+ {
+ VirtualColumnNode vcn = (VirtualColumnNode)expression;
+
+ // If the VCN points to a FromBaseTable, just get that
+ // table's number.
+ if (vcn.getSourceResultSet() instanceof FromBaseTable)
+ {
+ return ((FromBaseTable)vcn.getSourceResultSet()).
+ getTableNumber();
+ }
+
+ // Else recurse down the VCN.
+ return vcn.getSourceColumn().getTableNumber();
+ }
+
+ // We can get here if expression has neither a column
+ // reference nor a FromBaseTable beneath it--for example,
+ // if it is of type BaseColumnNode.
+ return -1;
+ }
+
}
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=396211&r1=396210&r2=396211&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
Sat Apr 22 20:30:55 2006
@@ -1638,7 +1638,24 @@
getLanguageConnectionContext());
}
+ ((OptimizerImpl)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.");
+ }
+
+ return (OptimizerImpl)optimizer;
}
/**
Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java?rev=396211&r1=396210&r2=396211&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
(original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/SingleChildResultSetNode.java
Sat Apr 22 20:30:55 2006
@@ -166,6 +166,29 @@
}
/**
+ * @see Optimizable#addOrLoadBestPlanMapping
+ *
+ * Makes a call to add/load the plan mapping for this node,
+ * and then makes the necessary call to recurse on this node's
+ * child, in order to ensure that we have a full plan mapped.
+ */
+ public void addOrLoadBestPlanMapping(boolean doAdd,
+ Optimizer optimizer) throws StandardException
+ {
+ super.addOrLoadBestPlanMapping(doAdd, optimizer);
+ if (childResult instanceof Optimizable)
+ {
+ ((Optimizable)childResult).
+ addOrLoadBestPlanMapping(doAdd, optimizer);
+ }
+ else
+ {
+ childResult.getOptimizerImpl().
+ addOrLoadBestPlanMappings(doAdd, optimizer);
+ }
+ }
+
+ /**
* Prints the sub-nodes of this object. See QueryTreeNode.java for
* how tree printing is supposed to work.
*
Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java?rev=396211&r1=396210&r2=396211&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
(original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
Sat Apr 22 20:30:55 2006
@@ -156,6 +156,41 @@
}
/**
+ * @see Optimizable#addOrLoadBestPlanMapping
+ *
+ * Makes a call to add/load the plan mapping for this node,
+ * and then makes the necessary call to recurse on this node's
+ * left and right child, in order to ensure that we have a
+ * full plan mapped.
+ */
+ public void addOrLoadBestPlanMapping(boolean doAdd,
+ Optimizer optimizer) throws StandardException
+ {
+ super.addOrLoadBestPlanMapping(doAdd, optimizer);
+ if (leftResultSet instanceof Optimizable)
+ {
+ ((Optimizable)leftResultSet).
+ addOrLoadBestPlanMapping(doAdd, optimizer);
+ }
+ else
+ {
+ leftResultSet.getOptimizerImpl().
+ addOrLoadBestPlanMappings(doAdd, optimizer);
+ }
+
+ if (rightResultSet instanceof Optimizable)
+ {
+ ((Optimizable)rightResultSet).
+ addOrLoadBestPlanMapping(doAdd, optimizer);
+ }
+ else
+ {
+ rightResultSet.getOptimizerImpl().
+ addOrLoadBestPlanMappings(doAdd, optimizer);
+ }
+ }
+
+ /**
* Convert this object to a String. See comments in QueryTreeNode.java
* for how this should be done for tree printing.
*
@@ -758,6 +793,7 @@
(RequiredRowOrdering) null,
getCompilerContext().getNumTables(),
lcc);
+ ((OptimizerImpl)optimizer).prepForNextRound();
if (sourceResultSet == leftResultSet)
{
Modified: db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/predicatesIntoViews.out
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/predicatesIntoViews.out?rev=396211&r1=396210&r2=396211&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/predicatesIntoViews.out
(original)
+++ db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/predicatesIntoViews.out
Sat Apr 22 20:30:55 2006
@@ -7244,7 +7244,7 @@
next time (milliseconds) = 0
close time (milliseconds) = 0
Left result set:
- Table Scan ResultSet for CLASSIFICATION_VALUES at serializable isolation level using
share table locking chosen by the optimizer
+ Index Scan ResultSet for REPOSITORYOBJECTRESOURCE using constraint ROR_CURRENTVERSION
at serializable isolation level using share table locking chosen by the optimizer
Number of opens = 0
Rows seen = 0
Rows filtered = 0
@@ -7255,11 +7255,13 @@
close time (milliseconds) = 0
scan information:
start position:
-null stop position:
-null qualifiers:
+ None
+ stop position:
+ None
+ qualifiers:
None
Right result set:
- Hash Scan ResultSet for REPOSITORYOBJECTRESOURCE using constraint ROR_CURRENTVERSION
at serializable isolation level using share table locking:
+ Hash Scan ResultSet for CLASSIFICATION_VALUES at serializable isolation level using
share table locking:
Number of opens = 0
Hash table size = 0
Hash key is column number 0
@@ -7271,10 +7273,8 @@
close time (milliseconds) = 0
scan information:
start position:
- None
- stop position:
- None
- scan qualifiers:
+null stop position:
+null scan qualifiers:
None
next qualifiers:
Column[0][0] Id: 0
|