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 ka...@apache.org on 2009/04/28 13:43:14 UTC
svn commit: r769344 - in /db/derby/code/branches/10.5/java:
engine/org/apache/derby/impl/sql/compile/
testing/org/apache/derbyTesting/functionTests/tests/lang/
testing/org/apache/derbyTesting/junit/
Author: kahatlen
Date: Tue Apr 28 11:43:13 2009
New Revision: 769344
URL: http://svn.apache.org/viewvc?rev=769344&view=rev
Log:
DERBY-4001: Sequence comparison with "ALL" does not yield correct results
Merged fix from trunk (revisions 765930 and 769273).
Added:
db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/functionTests/tests/lang/SubqueryFlatteningTest.java
- copied unchanged from r765930, db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/SubqueryFlatteningTest.java
Modified:
db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java
db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java
db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java
db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/junit/RuntimeStatisticsParser.java
Modified: db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java?rev=769344&r1=769343&r2=769344&view=diff
==============================================================================
--- db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java (original)
+++ db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java Tue Apr 28 11:43:13 2009
@@ -1679,6 +1679,26 @@
return true;
}
+ /**
+ * Check if all the predicates reference a given {@code FromBaseTable}.
+ *
+ * @param fbt the {@code FromBaseTable} to check for
+ * @return {@code true} if the table is referenced by all predicates,
+ * {@code false} otherwise
+ */
+ boolean allReference(FromBaseTable fbt) {
+ int tableNumber = fbt.getTableNumber();
+
+ for (int i = 0; i < size(); i++) {
+ Predicate p = (Predicate) elementAt(i);
+ if (!p.getReferencedSet().get(tableNumber)) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
/**
* Build a list of pushable predicates, if any,
* that satisfy the referencedTableMap.
Modified: db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java?rev=769344&r1=769343&r2=769344&view=diff
==============================================================================
--- db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java (original)
+++ db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/ProjectRestrictNode.java Tue Apr 28 11:43:13 2009
@@ -570,7 +570,12 @@
OptimizablePredicateList optimizablePredicates)
throws StandardException
{
- if (restrictionList != null)
+ // DERBY-4001: Don't pull predicates if this node is part of a NOT
+ // EXISTS join. For example, in the query below, if we allowed the
+ // predicate 1<>1 (always false) to be pulled, no rows would be
+ // returned, whereas it should return all the rows in table T.
+ // SELECT * FROM T WHERE NOT EXISTS (SELECT * FROM T WHERE 1<>1)
+ if (restrictionList != null && !isNotExists())
{
// Pull up any predicates that may have been pushed further
// down the tree during optimization.
Modified: db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java?rev=769344&r1=769343&r2=769344&view=diff
==============================================================================
--- db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java (original)
+++ db/derby/code/branches/10.5/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java Tue Apr 28 11:43:13 2009
@@ -668,10 +668,7 @@
* so we simply return the BinaryComparisonOperatorNode above
* the new join condition.
*/
- ValueNode rightOperand;
- rightOperand = ((ResultColumn) rrsn.getResultColumns().elementAt(0)).
- getExpression();
- return getNewJoinCondition(leftOperand, rightOperand);
+ return getNewJoinCondition(leftOperand, getRightOperand());
}
/* Select subquery is flattenable if:
@@ -758,16 +755,32 @@
* is if the predicates do not get pulled up. If they get pulled
* up then the single next logic for an EXISTS join does not work
* because that row may get disqualified at a higher level.)
+ * DERBY-4001: Extra conditions to allow flattening to a NOT
+ * EXISTS join (in a NOT EXISTS join it does matter on which
+ * side of the join predicates/restrictions are applied):
+ * o All the predicates must reference the FBT, otherwise
+ * predicates meant for the right side of the join may be
+ * applied to the left side of the join.
+ * o The right operand (in ALL and NOT IN) must reference the
+ * FBT, otherwise the generated join condition may be used
+ * to restrict the left side of the join.
*/
else if ( (isIN() || isANY() || isEXISTS() || flattenableNotExists) &&
((leftOperand == null) ? true :
leftOperand.categorize(new JBitSet(numTables), false)) &&
- select.getWherePredicates().allPushable() &&
- singleFromBaseTable(select.getFromList()))
+ select.getWherePredicates().allPushable())
{
- return flattenToExistsJoin(numTables,
- outerFromList, outerSubqueryList,
- outerPredicateList, flattenableNotExists);
+ FromBaseTable fbt =
+ singleFromBaseTable(select.getFromList());
+
+ if (fbt != null && (!flattenableNotExists ||
+ (select.getWherePredicates().allReference(fbt) &&
+ rightOperandFlattenableToNotExists(numTables, fbt))))
+ {
+ return flattenToExistsJoin(numTables,
+ outerFromList, outerSubqueryList,
+ outerPredicateList, flattenableNotExists);
+ }
}
// restore leftOperand to its original value
@@ -830,30 +843,88 @@
*
* @param fromList The from list from the subquery
*
- * @return Whether or not the from list from the subquery contains a
- * single entry which is a FBT or a PRN/FBT.
- */
- private boolean singleFromBaseTable(FromList fromList)
- {
- boolean retCode = (fromList.size() == 1);
+ * @return the {@code FromBaseTable} if the from list from the subquery
+ * contains a single entry which is a FBT or a PRN/FBT, or {@code null}
+ * if the subquery does not contain a single FBT
+ */
+ private FromBaseTable singleFromBaseTable(FromList fromList)
+ {
+ FromBaseTable fbt = null;
+
+ if (fromList.size() == 1) {
+ FromTable ft = (FromTable) fromList.elementAt(0);
+ if (ft instanceof FromBaseTable) {
+ fbt = (FromBaseTable) ft;
+ } else if (ft instanceof ProjectRestrictNode) {
+ ResultSetNode child =
+ ((ProjectRestrictNode) ft).getChildResult();
+ if (child instanceof FromBaseTable) {
+ fbt = (FromBaseTable) child;
+ }
+ }
+ }
- if (retCode)
- {
- FromTable ft = (FromTable) fromList.elementAt(0);
+ return fbt;
+ }
- if (((ft instanceof ProjectRestrictNode) &&
- ((ProjectRestrictNode) ft).getChildResult() instanceof FromBaseTable) ||
- ft instanceof FromBaseTable)
- {
- }
- else
- {
- retCode = false;
- }
- }
+ /**
+ * <p>
+ * Check if the right operand is on a form that makes it possible to
+ * flatten this query to a NOT EXISTS join. We don't allow flattening if
+ * the right operand doesn't reference the base table of the subquery.
+ * (Requirement added as part of DERBY-4001.)
+ * </p>
+ *
+ * <p>
+ * The problem with the right operand not referencing the base table of the
+ * subquery, is that the join condition may then be used to filter rows
+ * from the right side (outer) table in the NOT EXISTS join. In a NOT
+ * EXISTS join, the join condition can only safely be applied to the
+ * left side (inner) table of the join. Otherwise, it will filter out all
+ * the interesting rows too early.
+ * </p>
+ *
+ * <p>Take the query below as an example:</p>
+ *
+ * <pre><code>
+ * SELECT * FROM T1 WHERE X NOT IN (SELECT 1 FROM T2)
+ * </code></pre>
+ *
+ * <p>
+ * Here, the right operand is 1, and the join condition is {@code T1.X=1}.
+ * If flattened, the join condition will be used directly on the outer
+ * table, and hide all rows with {@code X<>1}, although those are the only
+ * rows we're interested in. If the join condition had only been used on
+ * the inner table, the NOT EXISTS join logic would do the correct thing.
+ * </p>
+ *
+ * <p>
+ * If the join condition references the inner table, the condition cannot
+ * be used directly on the outer table, so it is safe to flatten the query.
+ * </p>
+ *
+ * @param numTables the number of tables in this statement
+ * @param fbt the only {@code FromBaseTable} in this subquery
+ * @return {@code true} if it is OK to flatten this query to a NOT EXISTS
+ * join, {@code false} otherwise
+ */
+ private boolean rightOperandFlattenableToNotExists(
+ int numTables, FromBaseTable fbt) throws StandardException {
- return retCode;
- }
+ boolean flattenable = true;
+
+ // If there is no left operand, there is no right operand. If there is
+ // no right operand, it cannot cause any problems for the flattening.
+ if (leftOperand != null) {
+ JBitSet tableSet = new JBitSet(numTables);
+ getRightOperand().categorize(tableSet, false);
+ // The query can be flattened to NOT EXISTS join only if the right
+ // operand references the base table.
+ flattenable = tableSet.get(fbt.getTableNumber());
+ }
+
+ return flattenable;
+ }
/**
* Can NOT IN, ALL be falttened to NOT EXISTS join? We can't or the flattening doesn't
@@ -866,10 +937,8 @@
boolean result = false;
if (isNOT_IN() || isALL())
{
- ValueNode rightOperand = ((ResultColumn) resultSet.getResultColumns().elementAt(0)).
- getExpression();
result = (! leftOperand.getTypeServices().isNullable() &&
- ! rightOperand.getTypeServices().isNullable());
+ ! getRightOperand().getTypeServices().isNullable());
}
return result;
}
@@ -965,9 +1034,7 @@
}
else
{
- ValueNode rightOperand;
- rightOperand = ((ResultColumn) select.getResultColumns().elementAt(0)).
- getExpression();
+ ValueNode rightOperand = getRightOperand();
/* If the right operand is a CR, then we need to decrement
* its source level as part of flattening so that
* transitive closure will work correctly.
@@ -1044,6 +1111,18 @@
outerSubqueryList, outerPredicateList);
}
+ /**
+ * Get the node that will be the right operand in the join condition if
+ * this ALL/ANY/SOME/(NOT) IN subquery is flattened to a join.
+ *
+ * @return the right operand
+ */
+ private ValueNode getRightOperand() {
+ ResultColumn firstRC =
+ (ResultColumn) resultSet.getResultColumns().elementAt(0);
+ return firstRC.getExpression();
+ }
+
/**
* Check to see if we have a Variant value below us.
* If so, return true. Caches the result so multiple
Modified: db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java?rev=769344&r1=769343&r2=769344&view=diff
==============================================================================
--- db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java (original)
+++ db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java Tue Apr 28 11:43:13 2009
@@ -79,6 +79,7 @@
suite.addTest(SQLAuthorizationPropTest.suite());
suite.addTest(StatementPlanCacheTest.suite());
suite.addTest(StreamsTest.suite());
+ suite.addTest(SubqueryFlatteningTest.suite());
suite.addTest(TimeHandlingTest.suite());
suite.addTest(TriggerTest.suite());
suite.addTest(TruncateTableTest.suite());
Modified: db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/junit/RuntimeStatisticsParser.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/junit/RuntimeStatisticsParser.java?rev=769344&r1=769343&r2=769344&view=diff
==============================================================================
--- db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/junit/RuntimeStatisticsParser.java (original)
+++ db/derby/code/branches/10.5/java/testing/org/apache/derbyTesting/junit/RuntimeStatisticsParser.java Tue Apr 28 11:43:13 2009
@@ -298,6 +298,15 @@
}
/**
+ * Check if an exists join (or a not exists join) was used.
+ *
+ * @return {@code true} if the query used a (not) exists join
+ */
+ public boolean usedExistsJoin() {
+ return statistics.indexOf("Exists Join ResultSet") != -1;
+ }
+
+ /**
* Search the RuntimeStatistics for a string. It must occur
* at least instances times.
* @param stringToFind