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/03/03 22:56:11 UTC
svn commit: r382940 [1/3] - in /db/derby/code/trunk/java:
engine/org/apache/derby/impl/sql/compile/
testing/org/apache/derbyTesting/functionTests/master/
testing/org/apache/derbyTesting/functionTests/suites/
testing/org/apache/derbyTesting/functionTest...
Author: bandaram
Date: Fri Mar 3 13:56:07 2006
New Revision: 382940
URL: http://svn.apache.org/viewcvs?rev=382940&view=rev
Log:
DERBY-805: Implement join-predicate push down into Unions.
This Phase III patch builds on two earlier patches already submitted.
Implement pushdown by pushing optimizable predicates onto both sides of UNION.
If either side fails to push the predicate, stop pushing this predicate.
Submitted by Army Brown (qozinx@sbcglobal.net)
Added:
db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/predicatePushdown.out (with props)
db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/predicatePushdown.sql (with props)
db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/predicatePushdown_derby.properties (with props)
Modified:
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java
db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/suites/derbylang.runall
db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/copyfiles.ant
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?rev=382940&r1=382939&r2=382940&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java Fri Mar 3 13:56:07 2006
@@ -2121,46 +2121,51 @@
protected void addOrLoadBestPlanMappings(boolean doAdd,
Optimizer outerOptimizer) throws StandardException
{
- // First we save this OptimizerImpl's best join order.
- int [] joinOrder = null;
- if (doAdd)
+ // 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)
{
- // 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);
+ 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];
- // 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;
- 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.
+ joinOrder = (int[])savedJoinOrders.get(outerOptimizer);
+ if (joinOrder == null)
+ return;
- // 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];
+ // 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
@@ -2171,6 +2176,54 @@
optimizableList.getOptimizable(i).
addOrLoadBestPlanMapping(doAdd, outerOptimizer);
}
+ }
+
+ /**
+ * 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/trunk/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java?rev=382940&r1=382939&r2=382940&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java Fri Mar 3 13:56:07 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/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java?rev=382940&r1=382939&r2=382940&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java Fri Mar 3 13:56:07 2006
@@ -501,6 +501,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--)
{
@@ -588,9 +593,26 @@
{
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);
+ }
+ else {
+ childResult =
+ (ResultSetNode) ((FromTable) childResult).
+ modifyAccessPath(outerTables);
+ }
}
if (restrictionList != null)
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java?rev=382940&r1=382939&r2=382940&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultSetNode.java Fri Mar 3 13:56:07 2006
@@ -881,6 +881,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);
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java?rev=382940&r1=382939&r2=382940&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java Fri Mar 3 13:56:07 2006
@@ -1558,7 +1558,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,
@@ -1595,6 +1672,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
@@ -1618,6 +1725,34 @@
// 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();
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java?rev=382940&r1=382939&r2=382940&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java Fri Mar 3 13:56:07 2006
@@ -24,7 +24,12 @@
import org.apache.derby.iapi.error.StandardException;
+import org.apache.derby.iapi.sql.compile.AccessPath;
import org.apache.derby.iapi.sql.compile.C_NodeTypes;
+import org.apache.derby.iapi.sql.compile.CostEstimate;
+import org.apache.derby.iapi.sql.compile.Optimizable;
+import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
+import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
import org.apache.derby.iapi.sql.dictionary.DataDictionary;
import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
@@ -34,6 +39,8 @@
import org.apache.derby.iapi.util.JBitSet;
+import java.util.HashMap;
+
/**
* A SetOperatorNode represents a UNION, INTERSECT, or EXCEPT in a DML statement. Binding and optimization
* preprocessing is the same for all of these operations, so they share bind methods in this abstract class.
@@ -54,6 +61,18 @@
OrderByList orderByList;
+ // List of scoped predicates for pushing during optimization.
+ PredicateList leftOptPredicates;
+ PredicateList rightOptPredicates;
+
+ // List of original (unscoped) predicates that we tried to push
+ // during the most recent phase of optimization.
+ PredicateList pushedPredicates;
+
+ // Mapping of original predicates to scoped predicates, used to
+ // avoid re-scoping predicates unnecessarily.
+ HashMap leftScopedPreds;
+ HashMap rightScopedPreds;
/**
* Initializer for a SetOperatorNode.
@@ -86,6 +105,359 @@
}
/**
+ * @see Optimizable#modifyAccessPath
+ *
+ * @exception StandardException Thrown on error
+ */
+ public Optimizable modifyAccessPath(JBitSet outerTables,
+ PredicateList predList) throws StandardException
+ {
+ // When we optimized this node we attempted to push predicates down to
+ // the children, which means the best access path for the children
+ // might depend on those predicates. So now that we're preparing
+ // to generate the best paths, we have to push those same predicates
+ // down again (this is the last time) so that the children can use
+ // them as appropriate.
+ if (predList != null)
+ {
+ for (int i = predList.size() - 1; i >= 0; i--)
+ if (pushOptPredicate(predList.getOptPredicate(i)))
+ predList.removeOptPredicate(i);
+ }
+
+ /*
+ * It's possible that we tried to push a predicate down to this node's
+ * children but failed to do so. This can happen if this node's
+ * children both match the criteria for pushing a predicate (namely,
+ * they reference base tables) but the children's children do not.
+ * Ex.
+ * select * from
+ * (select i,j from t2 UNION
+ * values (1,1),(2,2),(3,3),(4,4) UNION
+ * select i,j from t1
+ * ) x0 (i,j),
+ * t5 where x0.i = t5.i;
+ *
+ * This will yield a tree resembling the following:
+ *
+ * UNION
+ * / \
+ * UNION SELECT (T1)
+ * / \
+ * SELECT (T2) VALUES
+ *
+ * In this case the top UNION ("this") will push the predicate down,
+ * but the second UNION will _not_ push the predicate because
+ * it can't be pushed to the VALUES clause. This means that
+ * after we're done modifying the paths for "this" node (the top
+ * UNION), the predicate will still be sitting in our leftOptPredicates
+ * list. If that's the case, then we have to make sure the predicate,
+ * which was _not_ enforced in the left child, is enforced at this
+ * level. We do that by generating a ProjectRestrictNode above this
+ * node. Yes, this means the predicate will actually be applied
+ * twice to the right child (in this case), but that's okay as it
+ * won't affect the results.
+ */
+
+ // Get the cost estimate for this node so that we can put it in
+ // the new ProjectRestrictNode, if one is needed.
+ CostEstimate ce = getFinalCostEstimate();
+
+ // Modify this node's access paths.
+ ResultSetNode topNode = (ResultSetNode)modifyAccessPath(outerTables);
+
+ // Now see if there are any left over predicates; if so, then we
+ // have to generate a ProjectRestrictNode.
+ if (((leftOptPredicates != null) && (leftOptPredicates.size() > 0)) ||
+ ((rightOptPredicates != null) && (rightOptPredicates.size() > 0)))
+ {
+ // When we generate the project restrict node, we pass in the
+ // "pushedPredicates" list because that has the predicates in
+ // _unscoped_ form, which means they are intended for _this_
+ // node instead of this node's children. That's exactly what
+ // we want.
+ ResultSetNode prnRSN = (ResultSetNode) getNodeFactory().getNode(
+ C_NodeTypes.PROJECT_RESTRICT_NODE,
+ topNode, // Child ResultSet
+ topNode.getResultColumns(), // Projection
+ null, // Restriction
+ pushedPredicates, // Restriction as PredicateList
+ null, // Subquerys in Projection
+ null, // Subquerys in Restriction
+ null, // Table properties
+ getContextManager());
+ prnRSN.costEstimate = ce.cloneMe();
+ prnRSN.setReferencedTableMap(topNode.getReferencedTableMap());
+ topNode = prnRSN;
+ }
+
+ return (Optimizable)topNode;
+ }
+
+ /**
+ * @see org.apache.derby.iapi.sql.compile.Optimizable#pushOptPredicate
+ *
+ * Take a predicate and push it down to both the left AND right result
+ * sets. Return "true" if we successfully pushed it to both sides,
+ * and "false" otherwise. The assumption is that if we return "true",
+ * the caller will take the predicate and remove it from its own list
+ * of predicates to evaluate; if we return false, then the predicate
+ * will be evaluated at the level of the caller. So returning "false"
+ * means that the left and right result sets for this node will be fully
+ * returned, and then the predicate will be evaluated against the
+ * <set-operator> of those result sets (as of DERBY-805, the only set
+ * operator calling this method is UnionNode). If we can push the
+ * predicate down to both children, though, we can evaluate it closer
+ * to store, which means that each child result set returns only the
+ * correctly qualified rows, and thus the calling set operator will
+ * have a smaller result set on which to operate, which can boost
+ * performance.
+ *
+ * That said, if we can't push the predicate to _both_ sides, we don't
+ * push it at all. The reason is that if we push to one side but not
+ * to the other, we would have to ask the question of whether we should
+ * return "true" (meaning that the predicate would be removed from the
+ * caller's list and thus would _not_ be evaluated at the <set-operator>
+ * level) or "false" (meaning that the caller would keep the predicate
+ * and evaluate it at the <set-operator> level). Depending on the query
+ * in question, both answers could end up returning incorrect results.
+ *
+ * For example, if we push it to the right but not to the left, then
+ * leave it in the caller's list, the optimizer for the caller might
+ * decide to use the predicate to do a hash join with some outer result
+ * set (if the predicate is an equijoin predicate). That would result
+ * in materialization of the calling node and of its children--but since
+ * we pushed a predicate that depends on the outer table down into the
+ * right child, materialization of the right child will only return the
+ * rows that join with the _first_ row of the outer result set, which
+ * is wrong.
+ *
+ * If, on the other hand, we push the predicate to one side and then tell
+ * the caller to remove it from its list, the side to which we did _not_
+ * push the predicate could return rows that aren't qualified. Then,
+ * since the caller removed the predicate from its list, it (the caller)
+ * will not evaluate the predicate on its own result set--and thus we
+ * can end up returning rows that we weren't supposed to return.
+ *
+ * So all of that said, only push (and return "true") if we think we
+ * can push the predicate to both sides.
+ *
+ * @exception StandardException Thrown on error
+ */
+ public boolean pushOptPredicate(OptimizablePredicate optimizablePredicate)
+ throws StandardException
+ {
+ // This method was added to SetOperatorNode as part of DERBY-805,
+ // which was only targeted for UnionNodes. So for now, we don't
+ // do anything if "this" isn't a Union. This check can be removed
+ // when support for other SetOperators is added.
+ if (!(this instanceof UnionNode))
+ return false;
+
+ // We only handle certain types of predicates here; if the received
+ // predicate doesn't qualify, then don't push it.
+ Predicate pred = (Predicate)optimizablePredicate;
+ if (!pred.pushableToSubqueries())
+ return false;
+
+ // Check to see if the child nodes reference any base tables; if either
+ // child does not reference at least one base table, then we don't try
+ // to push the predicate.
+ boolean canPush = false;
+
+ JBitSet tableNums = new JBitSet(getReferencedTableMap().size());
+ BaseTableNumbersVisitor btnVis =
+ new BaseTableNumbersVisitor(tableNums);
+
+ // Check the left child.
+ leftResultSet.accept(btnVis);
+ canPush = (tableNums.getFirstSetBit() != -1);
+
+ /* If we can't push it to _both_ children, then we don't push at all.
+ * RESOLVE: We can add the ability to push a predicate to one side
+ * only by putting a ProjectRestrictNode between the union node and
+ * the child as a place to park the predicate. To make things simple,
+ * we might want to always put ProjectRestrictNodes under both sides
+ * of the union during preprocessing (i.e. after binding but before
+ * optimization). In some cases the extra nodes won't be needed, but
+ * PRNs (and the corresponding ProjectRestrictResultSets) are cheap.
+ * Also, we could eliminate unnecessary ProjectRestrictNodes at the
+ * end of optimization (possibly in modifyAccessPaths()). Until all
+ * of that is implemented, though, we only push if we can push to
+ * both sides...
+ */
+ if (!canPush)
+ return false;
+
+ // Check the right child.
+ tableNums.clearAll();
+ rightResultSet.accept(btnVis);
+ canPush = (tableNums.getFirstSetBit() != -1);
+ if (!canPush)
+ return false;
+
+ BinaryRelationalOperatorNode opNode =
+ (BinaryRelationalOperatorNode)pred.getAndNode().getLeftOperand();
+
+ // Note: we assume we only get here for predicates with col refs on
+ // both sides; if that ever changes, the following cast will need
+ // to be updated accordingly.
+ boolean opWasRemapped =
+ ((ColumnReference)opNode.getLeftOperand()).hasBeenRemapped();
+
+ /* If there is a ProjectRestrictNode directly above this node,
+ * then the predicate in question may have been remapped to this
+ * SetOperatorNode before we got here (see pushOptPredicate() in
+ * ProjectRestrictNode). If we leave it mapped when we try to
+ * get scoped predicates for the left and right result sets, the
+ * underlying column references of the scoped predicates will
+ * effectively be doubly-mapped (i.e. mapped more than once), which
+ * can cause problems at code generation time. So we 1) un-remap
+ * the predicate here, 2) get the scoped predicates, and then
+ * 3) remap the predicate again at the end of this method.
+ */
+ RemapCRsVisitor rcrv = null;
+ if (opWasRemapped)
+ {
+ rcrv = new RemapCRsVisitor(false);
+ pred.getAndNode().accept(rcrv);
+ }
+
+ // Get a list of all of the underlying base tables that this node
+ // references. We pass this down when scoping so that we can tell
+ // if the operands are actually supposed to be scoped to _this_
+ // node's children. Note that in order for the predicate to
+ // have been pushed this far, at least one of its operands must
+ // apply to this node--we don't know which one it is, though,
+ // so we use this tableNums info to figure that out.
+ tableNums.clearAll();
+ this.accept(btnVis);
+
+ /* What we want to do here is push the predicate to the left/right
+ * child. That means that we need to find the equivalent column(s)
+ * in each child.
+ * Ex:
+ *
+ * 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;
+ *
+ * In this example, X1.j maps to "t1" for the left side of the
+ * union (X1) and "t2" for the right side of the union. So we have
+ * to get versions of the predicate that are appropriate to each
+ * side. That's what the call to getPredScopedForResultSet()
+ * in the following code does.
+ */
+
+ // See if we already have a scoped version of the predicate cached,
+ // and if so just use that.
+ Predicate scopedPred = null;
+ if (leftScopedPreds == null)
+ leftScopedPreds = new HashMap();
+ else
+ scopedPred = (Predicate)leftScopedPreds.get(pred);
+ if (scopedPred == null)
+ {
+ scopedPred = pred.getPredScopedForResultSet(
+ tableNums, leftResultSet);
+ leftScopedPreds.put(pred, scopedPred);
+ }
+
+ // Add the scoped predicate to our list for the left child.
+ getLeftOptPredicateList().addOptPredicate(scopedPred);
+
+ scopedPred = null;
+ if (rightScopedPreds == null)
+ rightScopedPreds = new HashMap();
+ else
+ scopedPred = (Predicate)rightScopedPreds.get(pred);
+ if (scopedPred == null)
+ {
+ scopedPred = pred.getPredScopedForResultSet(
+ tableNums, rightResultSet);
+ rightScopedPreds.put(pred, scopedPred);
+ }
+
+ // Add the scoped predicate to our list for the right child.
+ getRightOptPredicateList().addOptPredicate(scopedPred);
+
+ // Restore the original predicate to the way it was before we got
+ // here--i.e. remap it again if needed.
+ if (opWasRemapped)
+ {
+ rcrv = new RemapCRsVisitor(true);
+ pred.getAndNode().accept(rcrv);
+ }
+
+ // Add the predicate (in its original form) to our list of predicates
+ // that we've pushed during this phase of optimization. We need to
+ // keep this list of pushed predicates around so that we can do
+ // a "pull" of them later, if needed. We also need this list for
+ // cases where predicates are not pushed all the way down; see
+ // modifyAccessPaths() in this class for more.
+ if (pushedPredicates == null)
+ pushedPredicates = new PredicateList();
+
+ pushedPredicates.addOptPredicate(pred);
+ return true;
+ }
+
+ /**
+ * @see Optimizable#pullOptPredicates
+ *
+ * @exception StandardException Thrown on error
+ */
+ public void pullOptPredicates(
+ OptimizablePredicateList optimizablePredicates)
+ throws StandardException
+ {
+ if (pushedPredicates == null)
+ // we didn't push anything, so nothing to pull.
+ return;
+
+ // It's possible that we tried to push a predicate down to this
+ // SetOperatorNode's children but weren't actually able to do so
+ // (see modifyAccessPaths() in this class for details on when that
+ // can happen). In that case the predicates will still be sitting
+ // in the left/right predicate list; we can ignore them here by
+ // just discarding them. When it comes time to modifyAccessPaths,
+ // though, we'll handle them correctly--i.e. we'll generate a
+ // ProjectRestrictNode over this node to ensure the predicates are
+ // enforced.
+
+ if (leftOptPredicates != null)
+ leftOptPredicates.removeAllElements();
+
+ if (rightOptPredicates != null)
+ rightOptPredicates.removeAllElements();
+
+ /* Note that predicates which have been explicitly scoped should
+ * not be pulled. The reason is that a scoped predicate can only
+ * be pushed to a specific, target result set. When it comes time
+ * to pull the predicate up, there's no need to pull the scoped
+ * predicate because it, by definition, was only intended for this
+ * specific result set and therefore cannot be pushed anywhere else.
+ * So at "pull" time, we can just discard the scoped predicates. We
+ * do, however, need to pull the original, unscoped predicate from
+ * which the scoped predicate was created because we can potentially
+ * push that predicate elsewhere
+ */
+ Predicate pred = null;
+ for (int i = 0; i < pushedPredicates.size(); i++)
+ {
+ pred = (Predicate)pushedPredicates.getOptPredicate(i);
+ if (pred.isScopedForPush())
+ continue;
+ optimizablePredicates.addOptPredicate(pred);
+ }
+
+ // We're done with the pushedPredicates list, so clear it out
+ // in preparation for another phase of optimization.
+ pushedPredicates.removeAllElements();
+ }
+
+ /**
* Convert this object to a String. See comments in QueryTreeNode.java
* for how this should be done for tree printing.
*
@@ -631,4 +1003,41 @@
* @return the operator name: "UNION", "INTERSECT", or "EXCEPT"
*/
abstract String getOperatorName();
+
+ /**
+ * Retrieve the list of optimizable predicates that are
+ * targeted for the left child. Create a new (empty)
+ * list if the list is null.
+ */
+ protected PredicateList getLeftOptPredicateList()
+ throws StandardException
+ {
+ if (leftOptPredicates == null) {
+ leftOptPredicates =
+ (PredicateList) getNodeFactory().getNode(
+ C_NodeTypes.PREDICATE_LIST,
+ getContextManager());
+ }
+
+ return leftOptPredicates;
+ }
+
+ /**
+ * Retrieve the list of optimizable predicates that are
+ * targeted for the right child. Create a new (empty)
+ * list if the list is null.
+ */
+ protected PredicateList getRightOptPredicateList()
+ throws StandardException
+ {
+ if (rightOptPredicates == null) {
+ rightOptPredicates =
+ (PredicateList) getNodeFactory().getNode(
+ C_NodeTypes.PREDICATE_LIST,
+ getContextManager());
+ }
+
+ return rightOptPredicates;
+ }
+
}
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java?rev=382940&r1=382939&r2=382940&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/TableOperatorNode.java Fri Mar 3 13:56:07 2006
@@ -698,14 +698,36 @@
if (leftOptimizer != null)
leftOptimizer.modifyAccessPaths();
else
- leftResultSet = leftResultSet.modifyAccessPaths();
+ {
+ // If this is a SetOperatorNode then we may have pushed
+ // predicates down to the children. If that's the case
+ // then we need to pass those predicates down as part
+ // of the modifyAccessPaths call so that they can be
+ // pushed one last time, in prep for generation.
+ if (this instanceof SetOperatorNode)
+ {
+ SetOperatorNode setOp = (SetOperatorNode)this;
+ leftResultSet = leftResultSet.modifyAccessPaths(
+ setOp.getLeftOptPredicateList());
+ }
+ else
+ leftResultSet = leftResultSet.modifyAccessPaths();
+ }
}
if (!rightModifyAccessPathsDone)
{
if (rightOptimizer != null)
rightOptimizer.modifyAccessPaths();
else
- rightResultSet = rightResultSet.modifyAccessPaths();
+ {
+ if (this instanceof SetOperatorNode) {
+ SetOperatorNode setOp = (SetOperatorNode)this;
+ rightResultSet = rightResultSet.modifyAccessPaths(
+ setOp.getRightOptPredicateList());
+ }
+ else
+ rightResultSet = rightResultSet.modifyAccessPaths();
+ }
}
return this;
}
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java?rev=382940&r1=382939&r2=382940&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/UnionNode.java Fri Mar 3 13:56:07 2006
@@ -213,17 +213,32 @@
*/
/* optimize() both resultSets */
- /* RESOLVE - don't try to push predicates through for now */
+
+ // If we have predicates from an outer block, we want to try
+ // to push them down to this node's children. However, we can't
+ // just push the predicates down as they are; instead, we
+ // need to scope them for the child result sets first, and
+ // then push the scoped versions. This is all done in the
+ // call to pushOptPredicate() here; for more, see that method's
+ // definition in SetOperatorNode.
+ if (predList != null)
+ {
+ for (int i = predList.size() - 1; i >= 0; i--) {
+ if (pushOptPredicate(predList.getOptPredicate(i)))
+ predList.removeOptPredicate(i);
+ }
+ }
+
leftResultSet = optimizeSource(
optimizer,
leftResultSet,
- (PredicateList) null,
+ getLeftOptPredicateList(),
outerCost);
rightResultSet = optimizeSource(
optimizer,
rightResultSet,
- (PredicateList) null,
+ getRightOptPredicateList(),
outerCost);
CostEstimate costEstimate = getCostEstimate(optimizer);