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 rh...@apache.org on 2006/08/23 20:14:12 UTC
svn commit: r434111 [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/tests/lang/
Author: rhillegas
Date: Wed Aug 23 11:14:11 2006
New Revision: 434111
URL: http://svn.apache.org/viewvc?rev=434111&view=rev
Log:
DERBY-1633: Commit Army's d1633_v3 patches, fixing the regression introduced by DERBY-805 in the behavior of views that involve joins.
Modified:
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/Predicate.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/ResultColumnList.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/testing/org/apache/derbyTesting/functionTests/master/predicatePushdown.out
db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/predicatePushdown.sql
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java?rev=434111&r1=434110&r2=434111&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java Wed Aug 23 11:14:11 2006
@@ -1267,7 +1267,7 @@
* 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
+ * exactly 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)
@@ -1277,6 +1277,10 @@
* ResultSetNode to which it doesn't apply.
* @param childRSN The result set node to which we want to create
* a scoped predicate.
+ * @param whichRC If not -1 then this tells us which ResultColumn
+ * in the received childRSN we need to use for the scoped predicate;
+ * if -1 then the column position of the scoped column reference
+ * will be stored in this array and passed back to the caller.
* @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
@@ -1286,8 +1290,8 @@
* during optimization.
*/
public ValueNode getScopedOperand(int whichSide,
- JBitSet parentRSNsTables, ResultSetNode childRSN)
- throws StandardException
+ JBitSet parentRSNsTables, ResultSetNode childRSN,
+ int [] whichRC) throws StandardException
{
ResultColumn rc = null;
ColumnReference cr =
@@ -1295,24 +1299,29 @@
? (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.
+ /* When we scope a predicate we only scope one side of it--the
+ * side that is to be evaluated against childRSN. We figure out
+ * if "cr" is that side by using table numbers, as seen below.
+ * This means that for every scoped predicate there will be one
+ * operand that is scoped and one operand that is not scoped.
+ * When we get here for the operand that will not be scoped,
+ * we'll just return a clone of that operand. So in the example
+ * mentioned above, the scoped predicate for the left child of
+ * X1 would be
+ *
+ * T1.j <scoped> = X2.b <clone>
+ *
+ * That said, 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
@@ -1325,113 +1334,153 @@
* 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;
- }
+ return (ColumnReference)cr.getClone();
/* 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.
+ * reference for childRSN, so go ahead and do it. The way in
+ * which we get the scope target column differs depending on
+ * if childRSN corresponds to the left or right child of the
+ * UNION node. Before explaining that, though, note that it's
+ * not good enough to just search for the target column by
+ * name. The reason is that it's possible the name provided
+ * for the column reference to be scoped doesn't match the
+ * name of the actual underlying column. 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.
+ * If we were scoping "X1.x" and we searched for "x" in the
+ * childRSN "select i,j from t1" we wouldn't find it.
+ *
+ * It is similarly incorrect to search for the target column
+ * by position (DERBY-1633). This is a bit more subtle, but
+ * if the child to which we're scoping is a subquery whose RCL
+ * does not match the column ordering of the RCL for cr's source
+ * result set, then searching by column position can yield the
+ * wrong results, as well. For a detailed example of how this
+ * can happen, see the fix description attached to DERBY-1633.
+ *
+ * So how do we find the target column, then? As mentioned
+ * above, the way in which we get the scope target column
+ * differs depending on if childRSN corresponds to the left
+ * or right child of the parent UNION node. And that said,
+ * we can tell if we're scoping a left child by looking at
+ * "whichRC" argument: if it is -1 then we know we're scoping
+ * to the left child of a Union; otherwise we're scoping to
+ * the right child.
*/
-
- rc = childRSN.getResultColumns().getResultColumn(cr.getColumnNumber());
+ if (whichRC[0] == -1)
+ {
+ /*
+ * For the left side we start by figuring out what the source
+ * result set and column position for "cr" are. Then, since
+ * a) cr must be pointing to a result column in the parentRSN's
+ * ResultColumnList, b) we know that the parent RSN is a
+ * SetOperatorNode (at least for now, since we only get here
+ * for Union nodes), and c) SetOpNode's RCLs are built from the
+ * left child's RCL (see bindResultColumns() in SetOperatorNode),
+ * we know that if we search the child's RCL for a reference
+ * whose source result column is the same as cr's source result
+ * column, we'll find a match. Once found, the position of the
+ * matching column w.r.t childRSN's RCL will be stored in the
+ * whichRC parameter.
+ */
+
+ // Find the source result set and source column position of cr.
+ int [] sourceColPos = new int[] {-1};
+ ResultSetNode sourceRSN = cr.getSourceResultSet(sourceColPos);
+
+ if (SanityManager.DEBUG)
+ {
+ /* We assumed that if we made it here "cr" was pointing
+ * to a base table somewhere down the tree. If that's
+ * true then sourceRSN won't be null. Make sure our
+ * assumption was correct.
+ */
+ SanityManager.ASSERT(sourceRSN != null,
+ "Failed to find source result set when trying to " +
+ "scope column reference '" + cr.getTableName() +
+ "." + cr.getColumnName());
+ }
+
+ // Now search for the corresponding ResultColumn in childRSN.
+ rc = childRSN.getResultColumns()
+ .getResultColumn(sourceColPos[0], sourceRSN, whichRC);
+ }
+ else
+ {
+ /*
+ * For the right side the story is slightly different. If we were
+ * to search the right child's RCL for a reference whose source
+ * result column was the same as cr's, we wouldn't find it. This
+ * is because cr's source result column comes from the left child's
+ * RCL and thus the right child doesn't know about it. That said,
+ * though, for set operations like UNION, the left and right RCL's
+ * are correlated by position--i.e. the operation occurs between
+ * the nth column in the left RCL and the nth column in the right
+ * RCL. So given that we will already have found the scope target
+ * in the left child's RCL at the position in whichRC, we know that
+ * that scope target for the right child's RCL is simply the
+ * whichRC'th column in that RCL.
+ */
+ rc = childRSN.getResultColumns().getResultColumn(whichRC[0]);
+ }
// 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 " +
+ "Failed to locate scope target 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.
- *
- * 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).
+ * ColumnReference, then that column reference has all of the
+ * info we need.
+ *
+ * It is, however, possible that the ResultColumn's expression
+ * is NOT a ColumnReference. For example, the expression would
+ * be a constant expression if childRSN represented something
+ * like:
+ *
+ * select 1, 1 from t1
+ *
+ * In this case the expression does not directly reference a
+ * column in the underlying result set and is therefore
+ * "scoped" as far as it can go. This means that the scoped
+ * predicate will not necessarily have column references on
+ * both sides, even though the predicate that we're scoping
+ * will. That's not a problem, though, since a predicate with
+ * a column reference on one side and a non-ColumnReference
+ * on the other is still valid.
*/
+
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();
- if (cRef.pointsToBaseTable())
- cRef.setColumnNumber(cr.getColumnNumber());
+ /* We create a clone of the column reference and mark
+ * the clone as "scoped" so that we can do the right
+ * thing when it comes time to remap the predicate;
+ * see Predicate.remapScopedPred() for more.
+ */
+ ColumnReference cRef = (ColumnReference)
+ ((ColumnReference)rc.getExpression()).getClone();
+ cRef.markAsScoped();
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 a clone of the column reference
- * because it's scoped as far as we can take it.
+ /* Else just return rc's expression. This means the scoped
+ * predicate will have one operand that is _not_ a column
+ * reference--but that's okay, so long as we account for
+ * that when pushing/remapping the scoped predicate down
+ * the query tree (see esp. "isScopedToSourceResultSet()"
+ * in Predicate.java).
*/
- return (ValueNode)cr.getClone();
+ return rc.getExpression();
}
/**
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java?rev=434111&r1=434110&r2=434111&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ColumnReference.java Wed Aug 23 11:14:11 2006
@@ -81,6 +81,16 @@
private int nestingLevel = -1;
private int sourceLevel = -1;
+ /* Whether or not this column reference been scoped for the
+ sake of predicate pushdown.
+ */
+ private boolean scoped;
+
+ /* List of saved remap data if this ColumnReference is scoped
+ and has been remapped multiple times.
+ */
+ private java.util.ArrayList remaps;
+
/**
* Initializer.
* This one is called by the parser where we could
@@ -105,6 +115,7 @@
this.setBeginOffset(((Integer) tokBeginOffset).intValue());
this.setEndOffset(((Integer) tokEndOffset).intValue());
tableNumber = -1;
+ remaps = null;
}
/**
@@ -119,6 +130,7 @@
this.columnName = (String) columnName;
this.tableName = (TableName) tableName;
tableNumber = -1;
+ remaps = null;
}
/**
@@ -299,6 +311,7 @@
nestingLevel = oldCR.getNestingLevel();
sourceLevel = oldCR.getSourceLevel();
replacesAggregate = oldCR.getGeneratedToReplaceAggregate();
+ scoped = oldCR.isScoped();
}
/**
@@ -642,15 +655,35 @@
return;
}
+ /* Scoped column references are a special case: they can be
+ * remapped several times (once for every ProjectRestrictNode
+ * through which the scoped ColumnReference is pushed before
+ * reaching its target result set) and will be un-remapped
+ * several times, as well (as the scoped predicate is "pulled"
+ * back up the query tree to it's original location). So we
+ * have to keep track of the "orig" info for every remap
+ * operation, not just for the most recent one.
+ */
+ if (scoped && (origSource != null))
+ {
+ if (remaps == null)
+ remaps = new java.util.ArrayList();
+ remaps.add(new RemapInfo(
+ columnNumber, tableNumber, columnName, source));
+ }
+ else
+ {
+ origSource = source;
+ origName = columnName;
+ origColumnNumber = columnNumber;
+ origTableNumber = tableNumber;
+ }
+
/* Find the matching ResultColumn */
- origSource = source;
source = getSourceResultColumn();
- origName = columnName;
columnName = source.getName();
- origColumnNumber = columnNumber;
columnNumber = source.getColumnPosition();
- origTableNumber = tableNumber;
if (source.getExpression() instanceof ColumnReference)
{
ColumnReference cr = (ColumnReference) source.getExpression();
@@ -679,12 +712,28 @@
// "Trying to unremap a ColumnReference that was not remapped.");
}
- source = origSource;
- origSource = null;
- columnName = origName;
- origName = null;
- tableNumber = origTableNumber;
- columnNumber = origColumnNumber;
+ if ((remaps == null) || (remaps.size() == 0))
+ {
+ source = origSource;
+ origSource = null;
+ columnName = origName;
+ origName = null;
+ tableNumber = origTableNumber;
+ columnNumber = origColumnNumber;
+ }
+ else
+ {
+ // This CR is multiply-remapped, so undo the most
+ // recent (and only the most recent) remap operation.
+ RemapInfo rI = (RemapInfo)remaps.remove(remaps.size() - 1);
+ source = rI.getSource();
+ columnName = rI.getColumnName();
+ tableNumber = rI.getTableNumber();
+ columnNumber = rI.getColumnNumber();
+ rI = null;
+ if (remaps.size() == 0)
+ remaps = null;
+ }
}
/**
@@ -982,50 +1031,142 @@
} // 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.
+ * Find the source result set for this ColumnReference and
+ * return it. Also, when the source result set is found,
+ * return the position (within the source result set's RCL)
+ * of the column referenced by this ColumnReference. The
+ * position is returned vai the colNum parameter.
+ *
+ * @param colNum Place to store the position of the column
+ * to which this ColumnReference points (position is w.r.t
+ * the source result set).
+ * @return The source result set for this ColumnReference;
+ * null if there is no source result set.
*/
- protected boolean pointsToBaseTable() throws StandardException
+ protected ResultSetNode getSourceResultSet(int [] colNum)
+ throws StandardException
{
+ if (source == 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 null;
+ }
+
+ ValueNode rcExpr = null;
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();
+ // Walk the ResultColumn->ColumnReference chain until we
+ // find a ResultColumn whose expression is a VirtualColumnNode.
+
+ rcExpr = rc.getExpression();
+ colNum[0] = getColumnNumber();
+
+ while ((rcExpr != null) && (rcExpr instanceof ColumnReference))
+ {
+ colNum[0] = ((ColumnReference)rcExpr).getColumnNumber();
+ rc = ((ColumnReference)rcExpr).getSource();
+
+ /* If "rc" is redundant then that means it points to another
+ * ResultColumn that in turn points to the source expression.
+ * This can happen in cases where "rc" points to a subquery
+ * that has been flattened into the query above it (flattening
+ * of subqueries occurs during preprocessing). In that case
+ * we want to skip over the redundant rc and find the
+ * ResultColumn that actually holds the source expression.
+ */
+ while (rc.isRedundant())
+ {
+ rcExpr = rc.getExpression();
+ if (rcExpr instanceof VirtualColumnNode)
+ rc = ((VirtualColumnNode)rcExpr).getSourceResultColumn();
+ else if (rcExpr instanceof ColumnReference)
+ {
+ colNum[0] = ((ColumnReference)rcExpr).getColumnNumber();
+ rc = ((ColumnReference)rcExpr).getSource();
+ }
+ else
+ {
+ /* If rc isn't pointing to a VirtualColumnNode nor
+ * to a ColumnReference, then it's not pointing to
+ * a result set. It could, for example, be pointing
+ * to a constant node or to the result of an aggregate
+ * or function. Break out of both loops and return
+ * null since there is no source result set.
+ */
+ rcExpr = null;
+ break;
+ }
+ }
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);
+ // If we found a VirtualColumnNode, return the VirtualColumnNode's
+ // sourceResultSet. The column within that sourceResultSet that
+ // is referenced by this ColumnReference is also returned, via
+ // the colNum parameter, and was set above.
+ if ((rcExpr != null) && (rcExpr instanceof VirtualColumnNode))
+ return ((VirtualColumnNode)rcExpr).getSourceResultSet();
+
+ // If we get here then the ColumnReference doesn't reference
+ // a result set, so return null.
+ colNum[0] = -1;
+ return null;
+ }
+
+ /**
+ * Mark this column reference as "scoped", which means that it
+ * was created (as a clone of another ColumnReference) to serve
+ * as the left or right operand of a scoped predicate.
+ */
+ protected void markAsScoped()
+ {
+ scoped = true;
+ }
+
+ /**
+ * Return whether or not this ColumnReference is scoped.
+ */
+ protected boolean isScoped()
+ {
+ return scoped;
+ }
+
+ /**
+ * Helper class to keep track of remap data when a ColumnReference
+ * is remapped multiple times. This allows the CR to be UN-
+ * remapped multiple times, as well.
+ */
+ private class RemapInfo
+ {
+ int colNum;
+ int tableNum;
+ String colName;
+ ResultColumn source;
+
+ RemapInfo(int cNum, int tNum, String cName, ResultColumn rc)
+ {
+ colNum = cNum;
+ tableNum = tNum;
+ colName = cName;
+ source = rc;
+ }
+
+ int getColumnNumber() { return colNum; }
+ int getTableNumber() { return tableNum; }
+ String getColumnName() { return colName; }
+ ResultColumn getSource() { return source; }
- // Else check our source's expression.
- return (rc.getExpression() instanceof BaseColumnNode);
+ void setColNumber(int cNum) { colNum = cNum; }
+ void setTableNumber(int tNum) { tableNum = tNum; }
+ void setColName(String cName) { colName = cName; }
+ void setSource(ResultColumn rc) { source = rc; }
}
}
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?rev=434111&r1=434110&r2=434111&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 Wed Aug 23 11:14:11 2006
@@ -2449,7 +2449,7 @@
}
/**
- * Add predicates to this optimizer's predicateList. This method
+ * Add scoped 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
@@ -2465,7 +2465,7 @@
* @param pList List of predicates to add to this OptimizerImpl's
* own list for pushing.
*/
- protected void addPredicatesToList(PredicateList pList)
+ protected void addScopedPredicatesToList(PredicateList pList)
throws StandardException
{
if ((pList == null) || (pList == predicateList))
@@ -2490,9 +2490,22 @@
predicateList.removeOptPredicate(i);
}
- // Now transfer all of the received predicates into this
- // OptimizerImpl's list.
- pList.transferAllPredicates(predicateList);
+ // Now transfer scoped predicates in the received list to
+ // this OptimizerImpl's list, where appropriate.
+ for (int i = pList.size() - 1; i >= 0; i--)
+ {
+ pred = (Predicate)pList.getOptPredicate(i);
+ if (pred.isScopedToSourceResultSet())
+ {
+ // Clear the scoped predicate's scan flags; they'll be set
+ // as appropriate when they make it to the restrictionList
+ // of the scoped pred's source result set.
+ pred.clearScanFlags();
+ predicateList.addOptPredicate(pred);
+ pList.removeOptPredicate(i);
+ }
+ }
+
return;
}
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/Predicate.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/Predicate.java?rev=434111&r1=434110&r2=434111&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/Predicate.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/Predicate.java Wed Aug 23 11:14:11 2006
@@ -914,9 +914,12 @@
BinaryRelationalOperatorNode opNode =
(BinaryRelationalOperatorNode)getAndNode().getLeftOperand();
- // If both sides are column references then this is a join pred.
+ // If both sides are column references AND they point to different
+ // tables, then this is a join pred.
return ((opNode.getLeftOperand() instanceof ColumnReference) &&
- (opNode.getRightOperand() instanceof ColumnReference));
+ (opNode.getRightOperand() instanceof ColumnReference) &&
+ (((ColumnReference)opNode.getLeftOperand()).getTableNumber() !=
+ ((ColumnReference)opNode.getRightOperand()).getTableNumber()));
}
/**
@@ -965,12 +968,16 @@
* ResultSetNode to which they don't apply.
* @param childRSN The result set node for which we want to create
* a scoped predicate.
+ * @param whichRC If not -1 then this tells us which ResultColumn
+ * in the received childRSN we need to use for the scoped predicate;
+ * if -1 then the column position of the scoped column reference
+ * will be stored in this array and passed back to the caller.
* @return A new predicate whose operands have been scoped to the
* received childRSN.
*/
protected Predicate getPredScopedForResultSet(
- JBitSet parentRSNsTables, ResultSetNode childRSN)
- throws StandardException
+ JBitSet parentRSNsTables, ResultSetNode childRSN,
+ int [] whichRC) throws StandardException
{
// We only deal with binary relational operators here.
if (!(getAndNode().getLeftOperand()
@@ -999,11 +1006,13 @@
opNode.getScopedOperand(
BinaryRelationalOperatorNode.LEFT,
parentRSNsTables,
- childRSN),
+ childRSN,
+ whichRC),
opNode.getScopedOperand(
BinaryRelationalOperatorNode.RIGHT,
parentRSNsTables,
- childRSN),
+ childRSN,
+ whichRC),
getContextManager());
// Bind the new op node.
@@ -1062,4 +1071,232 @@
return scoped;
}
+ /**
+ * When remapping a "normal" (i.e. non-scoped) predicate both
+ * of the predicate's operands are remapped and that's it.
+ * But when remapping a scoped predicate, things are slightly
+ * different. This method handles remapping of scoped predicates.
+ *
+ * We know that, for a scoped predicate, exactly one operand has
+ * been scoped for a specific target result set; the other operand
+ * is pointing to some other instance of FromTable with which the
+ * target result set is to be joined (see getScopedOperand() in
+ * BinaryRelationalOperatorNode.java). For every level of the
+ * query through which the scoped predicate is pushed, we have
+ * to perform a remap operation of the scoped operand. We do
+ * *not*, however, remap the non-scoped operand. The reason
+ * is that the non-scoped operand is already pointing to the
+ * result set against which it must be evaluated. As the scoped
+ * predicate is pushed down the query tree, the non-scoped
+ * operand should not change where it's pointing and thus should
+ * not be remapped. For example, assume we have a query whose
+ * tree has the following form:
+ *
+ * SELECT[0]
+ * / \
+ * PRN PRN
+ * | |
+ * SELECT[4] UNION
+ * | / \
+ * PRN SELECT[1] SELECT[2]
+ * | | |
+ * <FBT:T1> PRN PRN
+ * | |
+ * SELECT[3] <FromBaseTable:T2>
+ * |
+ * PRN
+ * |
+ * <FromBaseTable:T3>
+ *
+ * Assume also that we have some predicate "SELECT[4].i = <UNION>.j".
+ * If the optimizer decides to push the predicate to the UNION
+ * node, it (the predicate) will be scoped to the UNION's children,
+ * yielding something like "SELECT[4].i = SELECT[1].j" for the
+ * left child and "SELECT[4].i = SELECT[2].j" for the right child.
+ * These scoped predicates will then be pushed to the PRNs above
+ * SELECT[3] and T2, respectively. As part of that pushing
+ * process a call to PRN.pushOptPredicate() will occur, which
+ * brings us to this method. So let's assume we're here for
+ * the scoped predicate "SELECT[4].i = SELECT[1].j". Then we want
+ * to remap the scoped operand, "SELECT[1].j", so that it will
+ * point to the correct column in "SELECT[3]". We do NOT, however,
+ * want to remap the non-scoped operand "SELECT[4].i" because that
+ * operand is already pointing to the correct result set--namely,
+ * to a column in SELECT[4]. That non-scoped operand should not
+ * change regardless of how far down the UNION subtree the scoped
+ * predicate is pushed.
+ *
+ * If we did try to remap the non-scoped operand, it would end up
+ * pointing to result sets too low in the tree, which could lead to
+ * execution-time errors. So when we remap a scoped predicate, we
+ * have to make sure we only remap the scoped operand. That's what
+ * this method does.
+ *
+ * @return True if this predicate is a scoped predicate, in which
+ * case we performed a one-sided remap. False if the predicate is
+ * not scoped; the caller can then make the calls to perform a
+ * "normal" remap on this predicate.
+ */
+ protected boolean remapScopedPred()
+ {
+ if (!scoped)
+ return false;
+
+ /* Note: right now the only predicates we scope are those
+ * which are join predicates and all scoped predicates will
+ * have the same relational operator as the predicates from
+ * which they were scoped. Thus if we get here, we know
+ * that andNode's leftOperand must be an instance of
+ * BinaryRelationalOperatorNode (and therefore the following
+ * cast is safe).
+ */
+ BinaryRelationalOperatorNode binRelOp =
+ (BinaryRelationalOperatorNode)andNode.getLeftOperand();
+
+ ValueNode operand = null;
+
+ if (SanityManager.DEBUG)
+ {
+ /* If this predicate is scoped then one (and only one) of
+ * its operands should be scoped. Note that it's possible
+ * for an operand to be scoped to a non-ColumnReference
+ * value; if either operand is not a ColumnReference, then
+ * that operand must be the scoped operand.
+ */
+ operand = binRelOp.getLeftOperand();
+ boolean leftIsScoped =
+ !(operand instanceof ColumnReference) ||
+ ((ColumnReference)operand).isScoped();
+
+ operand = binRelOp.getRightOperand();
+ boolean rightIsScoped =
+ !(operand instanceof ColumnReference) ||
+ ((ColumnReference)operand).isScoped();
+
+ SanityManager.ASSERT(leftIsScoped ^ rightIsScoped,
+ "All scoped predicates should have exactly one scoped " +
+ "operand, but '" + binaryRelOpColRefsToString() +
+ "' has " + (leftIsScoped ? "TWO" : "NONE") + ".");
+ }
+
+ // Find the scoped operand and remap it.
+ operand = binRelOp.getLeftOperand();
+ if ((operand instanceof ColumnReference) &&
+ ((ColumnReference)operand).isScoped())
+ {
+ // Left operand is the scoped operand.
+ ((ColumnReference)operand).remapColumnReferences();
+ }
+ else
+ {
+ operand = binRelOp.getRightOperand();
+ if ((operand instanceof ColumnReference) &&
+ ((ColumnReference)operand).isScoped())
+ {
+ // Right operand is the scoped operand.
+ ((ColumnReference)operand).remapColumnReferences();
+ }
+
+ // Else scoped operand is not a ColumnReference, which
+ // means it can't (and doesn't need to) be remapped. So
+ // just fall through and return.
+ }
+
+ return true;
+ }
+
+ /**
+ * Return true if this predicate is scoped AND the scoped
+ * operand is a ColumnReference that points to a source result
+ * set. If the scoped operand is not a ColumnReference that
+ * points to a source result set then it must be pointing to
+ * some kind of expression, such as a literal (ex. 'strlit'),
+ * an aggregate value (ex. "count(*)"), or the result of a
+ * function (ex. "sin(i)") or operator (ex. "i+1").
+ *
+ * This method is used when pushing predicates to determine how
+ * far down the query tree a scoped predicate needs to be pushed
+ * to allow for successful evaluation of the scoped operand. If
+ * the scoped operand is not pointing to a source result set
+ * then it should not be pushed any further down tree. The reason
+ * is that evaluation of the expression to which the operand is
+ * pointing may depend on other values from the current level
+ * in the tree (ex. "sin(i)" depends on the value of "i", which
+ * could be a column at the predicate's current level). If we
+ * pushed the predicate further down, those values could become
+ * inaccessible, leading to execution-time errors.
+ *
+ * If, on the other hand, the scoped operand *is* pointing to
+ * a source result set, then we want to push it further down
+ * the tree until it reaches that result set, which allows
+ * evaluation of this predicate to occur as close to store as
+ * possible. This method doesn't actually do the push, it just
+ * returns "true" and then the caller can push as appropriate.
+ */
+ protected boolean isScopedToSourceResultSet()
+ throws StandardException
+ {
+ if (!scoped)
+ return false;
+
+ /* Note: right now the only predicates we scope are those
+ * which are join predicates and all scoped predicates will
+ * have the same relational operator as the predicates from
+ * which they were scoped. Thus if we get here, we know
+ * that andNode's leftOperand must be an instance of
+ * BinaryRelationalOperatorNode (and therefore the following
+ * cast is safe).
+ */
+ BinaryRelationalOperatorNode binRelOp =
+ (BinaryRelationalOperatorNode)andNode.getLeftOperand();
+
+ ValueNode operand = binRelOp.getLeftOperand();
+
+ /* If operand isn't a ColumnReference then is must be the
+ * scoped operand. This is because both operands have to
+ * be column references in order for scoping to occur (as
+ * per pushableToSubqueries()) and only the scoped operand
+ * can change (esp. can become a non-ColumnReference) as
+ * part of the scoping process. And since it's not a
+ * ColumnReference it can't be "a ColumnReference that
+ * points to a source result set", so return false.
+ */
+ if (!(operand instanceof ColumnReference))
+ return false;
+
+ /* If the operand is a ColumnReference and is scoped,
+ * then see if it is pointing to a ResultColumn whose
+ * expression is either another a CR or a Virtual
+ * ColumnNode. If it is then that operand applies
+ * to a source result set further down the tree and
+ * thus we return true.
+ */
+ ValueNode exp = null;
+ ColumnReference cRef = (ColumnReference)operand;
+ if (cRef.isScoped())
+ {
+ exp = cRef.getSource().getExpression();
+ return ((exp instanceof VirtualColumnNode) ||
+ (exp instanceof ColumnReference));
+ }
+
+ operand = binRelOp.getRightOperand();
+ if (!(operand instanceof ColumnReference))
+ return false;
+
+ cRef = (ColumnReference)operand;
+ if (SanityManager.DEBUG)
+ {
+ // If we got here then the left operand was NOT the scoped
+ // operand; make sure the right one is scoped, then.
+ SanityManager.ASSERT(cRef.isScoped(),
+ "All scoped predicates should have exactly one scoped " +
+ "operand, but '" + binaryRelOpColRefsToString() +
+ "has NONE.");
+ }
+
+ exp = cRef.getSource().getExpression();
+ return ((exp instanceof VirtualColumnNode) ||
+ (exp instanceof ColumnReference));
+ }
}
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java?rev=434111&r1=434110&r2=434111&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 Wed Aug 23 11:14:11 2006
@@ -547,8 +547,17 @@
/* Remap all of the ColumnReferences to point to the
* source of the values.
*/
- RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
- ((Predicate) optimizablePredicate).getAndNode().accept(rcrv);
+ Predicate pred = (Predicate)optimizablePredicate;
+
+ /* If the predicate is scoped then the call to "remapScopedPred()"
+ * will do the necessary remapping for us and will return true;
+ * otherwise, we'll just do the normal remapping here.
+ */
+ if (!pred.remapScopedPred())
+ {
+ RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
+ pred.getAndNode().accept(rcrv);
+ }
return true;
}
@@ -613,7 +622,14 @@
// Remember that the original child was not Optimizable
origChildOptimizable = false;
- childResult = childResult.modifyAccessPaths();
+ /* When we optimized the child we passed in our restriction list
+ * so that scoped predicates could be pushed further down the
+ * tree. We need to do the same when modifying the access
+ * paths to ensure we generate the same plans the optimizer
+ * chose.
+ */
+ childResult = childResult.modifyAccessPaths(restrictionList);
+
/* Mark this node as having the truly ... for
* the underlying tree.
*/
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultColumnList.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultColumnList.java?rev=434111&r1=434110&r2=434111&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultColumnList.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ResultColumnList.java Wed Aug 23 11:14:11 2006
@@ -221,6 +221,52 @@
}
/**
+ * Take a column position and a ResultSetNode and find the ResultColumn
+ * in this RCL whose source result set is the same as the received
+ * RSN and whose column position is the same as the received column
+ * position.
+ *
+ * @param colNum The column position (w.r.t rsn) for which we're searching
+ * @param rsn The result set node for which we're searching.
+ * @return The ResultColumn in this RCL whose source is column colNum
+ * in result set rsn. That ResultColumn's position w.r.t to this RCL
+ * is also returned via the whichRC parameter. If no match is found,
+ * return null and leave whichRC untouched.
+ */
+ public ResultColumn getResultColumn(int colNum, ResultSetNode rsn,
+ int [] whichRC) throws StandardException
+ {
+ if (colNum == -1)
+ return null;
+
+ ResultColumn rc = null;
+ ColumnReference colRef = null;
+ int [] crColNum = new int[] { -1 };
+
+ for (int index = size() - 1; index >= 0; index--)
+ {
+ rc = (ResultColumn) elementAt(index);
+ if (!(rc.getExpression() instanceof ColumnReference))
+ {
+ // If the rc's expression isn't a column reference then
+ // it can't be pointing to rsn, so just skip it.
+ continue;
+ }
+
+ colRef = (ColumnReference)rc.getExpression();
+ if ((rsn == colRef.getSourceResultSet(crColNum)) &&
+ (crColNum[0] == colNum))
+ {
+ // Found a match.
+ whichRC[0] = index+1;
+ return rc;
+ }
+ }
+
+ return null;
+ }
+
+ /**
* Get a ResultColumn from a column position (1-based) in the list,
* null if out of range (for order by).
*
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SelectNode.java?rev=434111&r1=434110&r2=434111&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 Wed Aug 23 11:14:11 2006
@@ -1621,11 +1621,10 @@
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.
+ // node because it will have been "scoped" for this node
+ // or for some result set below this one.
pred = (Predicate)predicateList.getOptPredicate(i);
- if (pred.isScopedForPush())
+ if (pred.isScopedToSourceResultSet())
{
// If we're pushing the predicate down here, we have to
// remove it from the predicate list of the node above
@@ -1652,6 +1651,26 @@
}
}
+ /* When we're done optimizing, any scoped predicates that
+ * we pushed down the tree should now be sitting again
+ * in our wherePredicates list. Put those back in the
+ * the list from which we received them, to allow them
+ * to be "pulled" back up to where they came from.
+ */
+ if (wherePredicates != null)
+ {
+ Predicate pred = null;
+ for (int i = wherePredicates.size() - 1; i >= 0; i--)
+ {
+ pred = (Predicate)wherePredicates.getOptPredicate(i);
+ if (pred.isScopedForPush())
+ {
+ predicateList.addOptPredicate(pred);
+ wherePredicates.removeOptPredicate(pred);
+ }
+ }
+ }
+
/* Get the cost */
costEstimate = optimizer.getOptimizedCost();
@@ -1698,7 +1717,7 @@
"modifying access paths.");
}
- ((OptimizerImpl)optimizer).addPredicatesToList(predList);
+ ((OptimizerImpl)optimizer).addScopedPredicatesToList(predList);
return modifyAccessPaths();
}
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SetOperatorNode.java?rev=434111&r1=434110&r2=434111&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 Wed Aug 23 11:14:11 2006
@@ -305,33 +305,6 @@
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_
@@ -359,6 +332,10 @@
* in the following code does.
*/
+ // For details on how this whichRC variable is used, see the
+ // comments in BinaryRelationalOperatorNode.getScopedOperand().
+ int [] whichRC = new int[] { -1 };
+
// See if we already have a scoped version of the predicate cached,
// and if so just use that.
Predicate scopedPred = null;
@@ -369,7 +346,7 @@
if (scopedPred == null)
{
scopedPred = pred.getPredScopedForResultSet(
- tableNums, leftResultSet);
+ tableNums, leftResultSet, whichRC);
leftScopedPreds.put(pred, scopedPred);
}
@@ -384,21 +361,13 @@
if (scopedPred == null)
{
scopedPred = pred.getPredScopedForResultSet(
- tableNums, rightResultSet);
+ tableNums, rightResultSet, whichRC);
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
@@ -453,11 +422,22 @@
* push that predicate elsewhere
*/
Predicate pred = null;
+ RemapCRsVisitor rcrv = new RemapCRsVisitor(false);
for (int i = 0; i < pushedPredicates.size(); i++)
{
pred = (Predicate)pushedPredicates.getOptPredicate(i);
if (pred.isScopedForPush())
+ {
+ /* We don't need to pull the predicate if it's scoped, but
+ * since scoped predicates are cached between rounds of
+ * optimization, it's possible that we'll reuse the scoped
+ * predicate again in a later round. So to make sure we
+ * get a "fresh start" in later rounds, we un-remap the
+ * predicate here.
+ */
+ pred.getAndNode().accept(rcrv);
continue;
+ }
optimizablePredicates.addOptPredicate(pred);
}