db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kahat...@apache.org
Subject svn commit: r769273 - in /db/derby/code/trunk/java: engine/org/apache/derby/impl/sql/compile/ testing/org/apache/derbyTesting/functionTests/tests/lang/
Date Tue, 28 Apr 2009 07:48:10 GMT
Author: kahatlen
Date: Tue Apr 28 07:48:10 2009
New Revision: 769273

URL: http://svn.apache.org/viewvc?rev=769273&view=rev
Log:
DERBY-4001: Sequence comparison with "ALL" does not yield correct results

There are three essential changes in the patch:

1) ProjectRestrictNode.pullOptPredicates()

Don't pull any predicates if the from table is marked as a not exists
table. This way the flattening of queries like the ones below will
work, because the predicate 1<>1 is not pulled out and applied on the
outer table.

  SELECT * FROM T WHERE NOT EXISTS (SELECT * FROM T WHERE 1<>1)
  SELECT * FROM T WHERE X < ALL (SELECT X FROM T WHERE 1<>1)
  SELECT * FROM T WHERE X NOT IN (SELECT X FROM T WHERE 1<>1)

2) SubqueryNode.preprocess()

Don't allow not exists flattening unless all the predicates in the
subquery reference the base table of the inner query. When all the
predicates reference that table, none of them will be used in the
outer query, so they won't cause any trouble for the flattening. This
makes queries like the one below work:

  SELECT * FROM T T1 WHERE NOT EXISTS (SELECT * FROM T T2 WHERE T1.X > 100)

No flattening will happen in this case, though.

Although it may sound like (2) would prevent the example queries in
(1) from being flattened, that's not the case. This is because simple
predicates like 1<>1 are pushed down before SubqueryNode.preprocess()
gets to the flattening, so it doesn't see those predicates. The
flattening is still safe, since we have made sure that those
predicates won't be pulled out again.

3) SubqueryNode.preprocess()

If an ALL subquery or a NOT IN subquery is flattened, a new join
condition is created, for instance

   WHERE X < ALL (SELECT Y ...) results in the join condition X >= Y
and
   WHERE X NOT IN (SELECT Y ...) results in the join condition X = Y

The patch adds a check so that the flattening only happens if the
right side of the join condition references the base table of the
subquery. If it does, we know that the join condition cannot be used
to filter rows from the outer table, so it's safe to do the
flattening. This prevents queries like the ones below from being
flattened, and they now work as expected:

  SELECT * FROM T WHERE X < ALL (SELECT 100 FROM T)
  SELECT * FROM T T1 WHERE X = ALL (SELECT T1.X FROM T)
  SELECT * FROM T WHERE X NOT IN (SELECT 100 FROM T)
  SELECT * FROM T T1 WHERE X NOT IN (SELECT T1.X+100 FROM T)

Modified:
    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/SubqueryNode.java
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/PredicateList.java?rev=769273&r1=769272&r2=769273&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 Tue
Apr 28 07:48:10 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/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=769273&r1=769272&r2=769273&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
Tue Apr 28 07:48:10 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/trunk/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java?rev=769273&r1=769272&r2=769273&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/SubqueryNode.java Tue
Apr 28 07:48:10 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/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java?rev=769273&r1=769272&r2=769273&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/_Suite.java
Tue Apr 28 07:48:10 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());



Mime
View raw message