db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From abr...@apache.org
Subject svn commit: r619932 - in /db/derby/code/branches/10.3/java: engine/org/apache/derby/impl/sql/compile/ testing/org/apache/derbyTesting/functionTests/master/ testing/org/apache/derbyTesting/functionTests/tests/lang/
Date Fri, 08 Feb 2008 16:31:48 GMT
Author: abrown
Date: Fri Feb  8 08:31:44 2008
New Revision: 619932

URL: http://svn.apache.org/viewvc?rev=619932&view=rev
Log:
DERBY-3288: Fix optimizer dependency tracking logic so that it
correctly enforces join order dependencies between Optimizables,
even when plan "short-circuiting" occurs.  This patch also fixes
a bug in FromVTI's referenced table map (which affects dependencies)
and does a slight refactoring of the "pull Optimizable" code for
the sake of clarity.  And finally, it adds an appropriate test
case to the existing lang/subqueryFlattening.sql test.

Port from trunk to 10.3.  The "svn merge" command failed due to
changes in FromVTI which were made in 10.4 (as part of DERBY-716)
but which were not ported back to 10.3.  So this is a commit of the
manually-merged patch 'd3288_10_3_merge.patch', as attached to
the Jira.

Modified:
    db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
    db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
    db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out
    db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql

Modified: db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java?rev=619932&r1=619931&r2=619932&view=diff
==============================================================================
--- db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
(original)
+++ db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
Fri Feb  8 08:31:44 2008
@@ -1040,17 +1040,25 @@
 		/* Generate the referenced table map */
 		referencedTableMap = new JBitSet(numTables);
 		referencedTableMap.set(tableNumber);
-		newInvocation.categorize(referencedTableMap, false);
 
-		// Create the dependency map
+		/* Create the dependency map.  This FromVTI depends on any
+		 * tables which are referenced by the method call.  Note,
+		 * though, that such tables should NOT appear in this node's
+		 * referencedTableMap, since that field is really meant to
+		 * hold the table numbers for any FromTables which appear
+		 * AT OR UNDER the subtree whose root is this FromVTI.  That
+		 * said, the tables referenced by newInvocation do not appear
+		 * "under" this FromVTI--on the contrary, they must appear
+		 * "above" this FromVTI within the query tree in order to
+		 * be referenced by the newInvocation.  So newInvocation table
+		 * references do _not_ belong in this.referencedTableMap.
+		 * (DERBY-3288)
+		 */
 		dependencyMap = new JBitSet(numTables);
-		for (int index = 0; index < numTables; index++)
-		{
-			if ((index != tableNumber) && referencedTableMap.get(index))
-			{
-				dependencyMap.set(index);
-			}
-		}
+		newInvocation.categorize(dependencyMap, false);
+
+		// Make sure this FromVTI does not "depend" on itself.
+		dependencyMap.clear(tableNumber);
 
 		// Get a JBitSet of the outer tables represented in the parameter list
 		correlationMap = new JBitSet(numTables);

Modified: db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?rev=619932&r1=619931&r2=619932&view=diff
==============================================================================
--- db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
(original)
+++ db/derby/code/branches/10.3/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
Fri Feb  8 08:31:44 2008
@@ -596,7 +596,21 @@
 		*/
 		while (joinPosition >= 0)
 		{
-			int nextOptimizable = 0;
+			int nextOptimizable = proposedJoinOrder[joinPosition] + 1;
+			if (proposedJoinOrder[joinPosition] >= 0)
+			{
+				/* We are either going to try another table at the current
+				 * join order position, or we have exhausted all the tables
+				 * at the current join order position.  In either case, we
+				 * need to pull the table at the current join order position
+				 * and remove it from the join order.  Do this BEFORE we
+				 * search for the next optimizable so that assignedTableMap,
+				 * which is updated to reflect the PULL, has the correct
+				 * information for enforcing join order depdendencies.
+				 * DERBY-3288.
+				 */
+				pullOptimizableFromJoinOrder();
+			}
 
 			if (desiredJoinOrderFound || timeExceeded)
 			{
@@ -737,8 +751,6 @@
 			else
 			{
 				/* Find the next unused table at this join position */
-				nextOptimizable = proposedJoinOrder[joinPosition] + 1;
-
 				for ( ; nextOptimizable < numOptimizables; nextOptimizable++)
 				{
 					boolean found = false;
@@ -755,281 +767,58 @@
 						}
 					}
 
-					/* Check to make sure that all of the next optimizable's
-					 * dependencies have been satisfied.
+					/* No need to check the dependencies if the optimizable
+					 * is already in the join order--because we should have
+					 * checked its dependencies before putting it there.
 					 */
-					if (nextOptimizable < numOptimizables)
+					if (found)
 					{
-						Optimizable nextOpt =
-								optimizableList.getOptimizable(nextOptimizable);
-						if (! (nextOpt.legalJoinOrder(assignedTableMap)))
+						if (SanityManager.DEBUG)
 						{
-							if (optimizerTrace)
-							{
-								trace(SKIPPING_JOIN_ORDER, nextOptimizable, 0, 0.0, null);
-							}
-
-							/*
-							** If this is a user specified join order then it is illegal.
-							*/
-							if ( ! optimizableList.optimizeJoinOrder())
+							// Doesn't hurt to check in SANE mode, though...
+							if ((nextOptimizable < numOptimizables) &&
+								!joinOrderMeetsDependencies(nextOptimizable))
 							{
-								if (optimizerTrace)
-								{
-									trace(ILLEGAL_USER_JOIN_ORDER, 0, 0, 0.0, null);
-								}
-
-								throw StandardException.newException(SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
+								SanityManager.THROWASSERT(
+									"Found optimizable '" + nextOptimizable +
+									"' in current join order even though " +
+									"its dependencies were NOT satisfied.");
 							}
-							continue;
 						}
-					}
 
-					if (! found)
-					{
-						break;
+						continue;
 					}
-				}
-
-			}
 
-			/*
-			** We are going to try an optimizable at the current join order
-			** position.  Is there one already at that position?
-			*/
-			if (proposedJoinOrder[joinPosition] >= 0)
-			{
-				/*
-				** We are either going to try another table at the current
-				** join order position, or we have exhausted all the tables
-				** at the current join order position.  In either case, we
-				** need to pull the table at the current join order position
-				** and remove it from the join order.
-				*/
-				Optimizable pullMe =
-					optimizableList.getOptimizable(
-											proposedJoinOrder[joinPosition]);
-
-				/*
-				** Subtract the cost estimate of the optimizable being
-				** removed from the total cost estimate.
-				**
-				** The total cost is the sum of all the costs, but the total
-				** number of rows is the number of rows returned by the
-				** innermost optimizable.
-				*/
-				double prevRowCount;
-				double prevSingleScanRowCount;
-				int prevPosition = 0;
-				if (joinPosition == 0)
-				{
-					prevRowCount = outermostCostEstimate.rowCount();
-					prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount();
-				}
-				else
-				{
-					prevPosition = proposedJoinOrder[joinPosition - 1];
-					CostEstimate localCE = 
-						optimizableList.
-							getOptimizable(prevPosition).
-								getBestAccessPath().
-									getCostEstimate();
-					prevRowCount = localCE.rowCount();
-					prevSingleScanRowCount = localCE.singleScanRowCount();
-				}
-
-				/*
-				** If there is no feasible join order, the cost estimate
-				** in the best access path may never have been set.
-				** In this case, do not subtract anything from the
-				** current cost, since nothing was added to the current
-				** cost.
-				*/
-				double newCost = currentCost.getEstimatedCost();
-				double pullCost = 0.0;
-				CostEstimate pullCostEstimate =
-								pullMe.getBestAccessPath().getCostEstimate();
-				if (pullCostEstimate != null)
-				{
-					pullCost = pullCostEstimate.getEstimatedCost();
-
-					newCost -= pullCost;
-
-					/*
-					** It's possible for newCost to go negative here due to
-					** loss of precision--but that should ONLY happen if the
-					** optimizable we just pulled was at position 0.  If we
-					** have a newCost that is <= 0 at any other time, then
-					** it's the result of a different kind of precision loss--
-					** namely, the estimated cost of pullMe was so large that
-					** we lost the precision of the accumulated cost as it
-					** existed prior to pullMe. Then when we subtracted
-					** pullMe's cost out, we ended up setting newCost to zero.
-					** That's an unfortunate side effect of optimizer cost
-					** estimates that grow too large. If that's what happened
-					** here,try to make some sense of things by adding up costs
-					** as they existed prior to pullMe...
-					*/
-					if (newCost <= 0.0)
-					{
-						if (joinPosition == 0)
-							newCost = 0.0;
-						else
-							newCost = recoverCostFromProposedJoinOrder(false);
-					}
-				}
-
-				/* If we are choosing a new outer table, then
-				 * we rest the starting cost to the outermostCost.
-				 * (Thus avoiding any problems with floating point
-				 * accuracy and going negative.)
-				 */
-				if (joinPosition == 0)
-				{
-					if (outermostCostEstimate != null)
-					{
-						newCost = outermostCostEstimate.getEstimatedCost();
-					}
-					else
-					{
-						newCost = 0.0;
-					}
-				}
-
-				currentCost.setCost(
-					newCost,
-					prevRowCount,
-					prevSingleScanRowCount);
-				
-				/*
-				** Subtract from the sort avoidance cost if there is a
-				** required row ordering.
-				**
-				** NOTE: It is not necessary here to check whether the
-				** best cost was ever set for the sort avoidance path,
-				** because it considerSortAvoidancePath() would not be
-				** set if there cost were not set.
-				*/
-				if (requiredRowOrdering != null)
-				{
-					if (pullMe.considerSortAvoidancePath())
+					/* Check to make sure that all of the next optimizable's
+					 * dependencies have been satisfied.
+					 */
+					if ((nextOptimizable < numOptimizables) &&
+						!joinOrderMeetsDependencies(nextOptimizable))
 					{
-						AccessPath ap = pullMe.getBestSortAvoidancePath();
-						double	   prevEstimatedCost = 0.0d;
-
-						/*
-						** Subtract the sort avoidance cost estimate of the
-						** optimizable being removed from the total sort
-						** avoidance cost estimate.
-						**
-						** The total cost is the sum of all the costs, but the
-						** total number of rows is the number of rows returned
-						** by the innermost optimizable.
-						*/
-						if (joinPosition == 0)
-						{
-							prevRowCount = outermostCostEstimate.rowCount();
-							prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount();
-							/* If we are choosing a new outer table, then
-							 * we rest the starting cost to the outermostCost.
-							 * (Thus avoiding any problems with floating point
-							 * accuracy and going negative.)
-							 */
-							prevEstimatedCost = outermostCostEstimate.getEstimatedCost();
-						}
-						else
+						if (optimizerTrace)
 						{
-							CostEstimate localCE = 
-								optimizableList.
-									getOptimizable(prevPosition).
-										getBestSortAvoidancePath().
-											getCostEstimate();
-							prevRowCount = localCE.rowCount();
-							prevSingleScanRowCount = localCE.singleScanRowCount();
-							prevEstimatedCost = currentSortAvoidanceCost.getEstimatedCost() -
-													ap.getCostEstimate().getEstimatedCost();
+							trace(SKIPPING_JOIN_ORDER, nextOptimizable, 0, 0.0, null);
 						}
 
-						// See discussion above for "newCost"; same applies here.
-						if (prevEstimatedCost <= 0.0)
+						/*
+						** If this is a user specified join order then it is illegal.
+						*/
+						if ( ! optimizableList.optimizeJoinOrder())
 						{
-							if (joinPosition == 0)
-								prevEstimatedCost = 0.0;
-							else
+							if (optimizerTrace)
 							{
-								prevEstimatedCost =
-									recoverCostFromProposedJoinOrder(true);
+								trace(ILLEGAL_USER_JOIN_ORDER, 0, 0, 0.0, null);
 							}
-						}
 
-						currentSortAvoidanceCost.setCost(
-							prevEstimatedCost,
-							prevRowCount,
-							prevSingleScanRowCount);
-
-						/*
-						** Remove the table from the best row ordering.
-						** It should not be necessary to remove it from
-						** the current row ordering, because it is
-						** maintained as we step through the access paths
-						** for the current Optimizable.
-						*/
-						bestRowOrdering.removeOptimizable(
-													pullMe.getTableNumber());
+							throw StandardException.newException(
+								SQLState.LANG_ILLEGAL_FORCED_JOIN_ORDER);
+						}
 
-						/*
-						** When removing a table from the join order,
-						** the best row ordering for the remaining outer tables
-						** becomes the starting point for the row ordering of
-						** the current table.
-						*/
-						bestRowOrdering.copy(currentRowOrdering);
+						continue;
 					}
-				}
-
-				/*
-				** Pull the predicates at from the optimizable and put
-				** them back in the predicate list.
-				**
-				** NOTE: This is a little inefficient because it pulls the
-				** single-table predicates, which are guaranteed to always
-				** be pushed to the same optimizable.  We could make this
-				** leave the single-table predicates where they are.
-				*/
-				pullMe.pullOptPredicates(predicateList);
-
-				/*
-				** When we pull an Optimizable we need to go through and
-				** load whatever best path we found for that Optimizable
-				** with respect to this OptimizerImpl.  The reason is that
-				** we could be pulling the Optimizable for the last time
-				** (before returning false), in which case we want it (the
-				** Optimizable) to be holding the best access path that it
-				** had at the time we found bestJoinOrder.  This ensures
-				** that the access path which is generated and executed for
-				** the Optimizable matches the the access path decisions
-				** made by this OptimizerImpl for the best join order.
-				**
-				** NOTE: We we only reload the best plan if it's necessary
-				** to do so--i.e. if the best plans aren't already loaded.
-				** The plans will already be loaded if the last complete
-				** join order we had was the best one so far, because that
-				** means we called "rememberAsBest" on every Optimizable
-				** in the list and, as part of that call, we will run through
-				** and set trulyTheBestAccessPath for the entire subtree.
-				** So if we haven't tried any other plans since then,
-				** we know that every Optimizable (and its subtree) already
-				** has the correct best plan loaded in its trulyTheBest
-				** path field.  It's good to skip the load in this case
-				** because 'reloading best plans' involves walking the
-				** entire subtree of _every_ Optimizable in the list, which
-				** can be expensive if there are deeply nested subqueries.
-				*/
-				if (reloadBestPlan)
-					pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this);
 
-				/* Mark current join position as unused */
-				proposedJoinOrder[joinPosition] = -1;
+					break;
+				}
 			}
 
 			/* Have we exhausted all the optimizables at this join position? */
@@ -1118,23 +907,6 @@
 				/* Go back up one join position */
 				joinPosition--;
 
-				/* Clear the assigned table map for the previous position 
-				 * NOTE: We need to do this here to for the dependency tracking
-				 */
-				if (joinPosition >= 0)
-				{
-					Optimizable pullMe =
-						optimizableList.getOptimizable(
-											proposedJoinOrder[joinPosition]);
-
-					/*
-					** Clear the bits from the table at this join position.
-					** This depends on them having been set previously.
-					** NOTE: We need to do this here to for the dependency tracking
-					*/
-					assignedTableMap.xor(pullMe.getReferencedTableMap());
-				}
-
 				if (joinPosition < 0 && permuteState == WALK_HIGH) //reached peak
 				{
 					joinPosition = 0;	//reset, fall down the hill
@@ -1192,15 +964,6 @@
 			optimizableList.getOptimizable(nextOptimizable).
 				getBestAccessPath().setCostEstimate((CostEstimate) null);
 
-			/* Set the assigned table map to be exactly the tables
-			 * in the current join order. 
-			 */
-			assignedTableMap.clearAll();
-			for (int index = 0; index <= joinPosition; index++)
-			{
-				assignedTableMap.or(optimizableList.getOptimizable(proposedJoinOrder[index]).getReferencedTableMap());
-			}
-
 			if (optimizerTrace)
 			{
 				trace(CONSIDERING_JOIN_ORDER, 0, 0, 0.0, null);
@@ -1209,6 +972,29 @@
 			Optimizable nextOpt =
 							optimizableList.getOptimizable(nextOptimizable);
 
+			/* Update the assigned table map to include the newly-placed
+			 * Optimizable in the current join order.  Assumption is that
+			 * this OR can always be undone using an XOR, which will only
+			 * be true if none of the Optimizables have overlapping table
+			 * maps.  The XOR itself occurs as part of optimizable "PULL"
+			 * processing.
+			 */
+			if (SanityManager.DEBUG)
+			{
+				JBitSet optMap =
+					(JBitSet)nextOpt.getReferencedTableMap().clone();
+
+				optMap.and(assignedTableMap);
+				if (optMap.getFirstSetBit() != -1)
+				{
+					SanityManager.THROWASSERT(
+						"Found multiple optimizables that share one or " +
+						"more referenced table numbers (esp: '" +
+						optMap + "'), but that should not be the case.");
+				}
+			}
+
+			assignedTableMap.or(nextOpt.getReferencedTableMap());
 			nextOpt.startOptimizing(this, currentRowOrdering);
 
 			pushPredicates(
@@ -1297,6 +1083,274 @@
 		}
 
 		return recoveredCost;
+	}
+
+	/**
+	 * Check to see if the optimizable corresponding to the received
+	 * optNumber can legally be placed within the current join order.
+	 * More specifically, if the optimizable has any dependencies,
+	 * check to see if those dependencies are satisified by the table
+	 * map representing the current join order.
+	 */
+	private boolean joinOrderMeetsDependencies(int optNumber)
+		throws StandardException
+	{
+		Optimizable nextOpt = optimizableList.getOptimizable(optNumber);
+		return nextOpt.legalJoinOrder(assignedTableMap);
+	}
+
+	/**
+	 * Pull whatever optimizable is at joinPosition in the proposed
+	 * join order from the join order, and update all corresponding
+	 * state accordingly.
+	 */
+	private void pullOptimizableFromJoinOrder()
+		throws StandardException
+	{
+		Optimizable pullMe =
+			optimizableList.getOptimizable(proposedJoinOrder[joinPosition]);
+
+		/*
+		** Subtract the cost estimate of the optimizable being
+		** removed from the total cost estimate.
+		**
+		** The total cost is the sum of all the costs, but the total
+		** number of rows is the number of rows returned by the
+		** innermost optimizable.
+		*/
+		double prevRowCount;
+		double prevSingleScanRowCount;
+		int prevPosition = 0;
+		if (joinPosition == 0)
+		{
+			prevRowCount = outermostCostEstimate.rowCount();
+			prevSingleScanRowCount = outermostCostEstimate.singleScanRowCount();
+		}
+		else
+		{
+			prevPosition = proposedJoinOrder[joinPosition - 1];
+			CostEstimate localCE = 
+				optimizableList.
+					getOptimizable(prevPosition).
+						getBestAccessPath().
+							getCostEstimate();
+			prevRowCount = localCE.rowCount();
+			prevSingleScanRowCount = localCE.singleScanRowCount();
+		}
+
+		/*
+		** If there is no feasible join order, the cost estimate
+		** in the best access path may never have been set.
+		** In this case, do not subtract anything from the
+		** current cost, since nothing was added to the current
+		** cost.
+		*/
+		double newCost = currentCost.getEstimatedCost();
+		double pullCost = 0.0;
+		CostEstimate pullCostEstimate =
+						pullMe.getBestAccessPath().getCostEstimate();
+		if (pullCostEstimate != null)
+		{
+			pullCost = pullCostEstimate.getEstimatedCost();
+
+			newCost -= pullCost;
+
+			/*
+			** It's possible for newCost to go negative here due to
+			** loss of precision--but that should ONLY happen if the
+			** optimizable we just pulled was at position 0.  If we
+			** have a newCost that is <= 0 at any other time, then
+			** it's the result of a different kind of precision loss--
+			** namely, the estimated cost of pullMe was so large that
+			** we lost the precision of the accumulated cost as it
+			** existed prior to pullMe. Then when we subtracted
+			** pullMe's cost out, we ended up setting newCost to zero.
+			** That's an unfortunate side effect of optimizer cost
+			** estimates that grow too large. If that's what happened
+			** here,try to make some sense of things by adding up costs
+			** as they existed prior to pullMe...
+			*/
+			if (newCost <= 0.0)
+			{
+				if (joinPosition == 0)
+					newCost = 0.0;
+				else
+					newCost = recoverCostFromProposedJoinOrder(false);
+			}
+		}
+
+		/* If we are choosing a new outer table, then
+		 * we rest the starting cost to the outermostCost.
+		 * (Thus avoiding any problems with floating point
+		 * accuracy and going negative.)
+		 */
+		if (joinPosition == 0)
+		{
+			if (outermostCostEstimate != null)
+			{
+				newCost = outermostCostEstimate.getEstimatedCost();
+			}
+			else
+			{
+				newCost = 0.0;
+			}
+		}
+
+		currentCost.setCost(
+			newCost,
+			prevRowCount,
+			prevSingleScanRowCount);
+				
+		/*
+		** Subtract from the sort avoidance cost if there is a
+		** required row ordering.
+		**
+		** NOTE: It is not necessary here to check whether the
+		** best cost was ever set for the sort avoidance path,
+		** because it considerSortAvoidancePath() would not be
+		** set if there cost were not set.
+		*/
+		if (requiredRowOrdering != null)
+		{
+			if (pullMe.considerSortAvoidancePath())
+			{
+				AccessPath ap = pullMe.getBestSortAvoidancePath();
+				double	   prevEstimatedCost = 0.0d;
+
+				/*
+				** Subtract the sort avoidance cost estimate of the
+				** optimizable being removed from the total sort
+				** avoidance cost estimate.
+				**
+				** The total cost is the sum of all the costs, but the
+				** total number of rows is the number of rows returned
+				** by the innermost optimizable.
+				*/
+				if (joinPosition == 0)
+				{
+					prevRowCount = outermostCostEstimate.rowCount();
+					prevSingleScanRowCount =
+						outermostCostEstimate.singleScanRowCount();
+
+					/* If we are choosing a new outer table, then
+					 * we rest the starting cost to the outermostCost.
+					 * (Thus avoiding any problems with floating point
+					 * accuracy and going negative.)
+					 */
+					prevEstimatedCost =
+						outermostCostEstimate.getEstimatedCost();
+				}
+				else
+				{
+					CostEstimate localCE = 
+						optimizableList.
+							getOptimizable(prevPosition).
+								getBestSortAvoidancePath().
+									getCostEstimate();
+					prevRowCount = localCE.rowCount();
+					prevSingleScanRowCount = localCE.singleScanRowCount();
+					prevEstimatedCost =
+						currentSortAvoidanceCost.getEstimatedCost() -
+						ap.getCostEstimate().getEstimatedCost();
+				}
+
+				// See discussion above for "newCost"; same applies here.
+				if (prevEstimatedCost <= 0.0)
+				{
+					if (joinPosition == 0)
+						prevEstimatedCost = 0.0;
+					else
+					{
+						prevEstimatedCost =
+							recoverCostFromProposedJoinOrder(true);
+					}
+				}
+
+				currentSortAvoidanceCost.setCost(
+					prevEstimatedCost,
+					prevRowCount,
+					prevSingleScanRowCount);
+
+				/*
+				** Remove the table from the best row ordering.
+				** It should not be necessary to remove it from
+				** the current row ordering, because it is
+				** maintained as we step through the access paths
+				** for the current Optimizable.
+				*/
+				bestRowOrdering.removeOptimizable(pullMe.getTableNumber());
+
+				/*
+				** When removing a table from the join order,
+				** the best row ordering for the remaining outer tables
+				** becomes the starting point for the row ordering of
+				** the current table.
+				*/
+				bestRowOrdering.copy(currentRowOrdering);
+			}
+		}
+
+		/*
+		** Pull the predicates at from the optimizable and put
+		** them back in the predicate list.
+		**
+		** NOTE: This is a little inefficient because it pulls the
+		** single-table predicates, which are guaranteed to always
+		** be pushed to the same optimizable.  We could make this
+		** leave the single-table predicates where they are.
+		*/
+		pullMe.pullOptPredicates(predicateList);
+
+		/*
+		** When we pull an Optimizable we need to go through and
+		** load whatever best path we found for that Optimizable
+		** with respect to this OptimizerImpl.  The reason is that
+		** we could be pulling the Optimizable for the last time
+		** (before returning false), in which case we want it (the
+		** Optimizable) to be holding the best access path that it
+		** had at the time we found bestJoinOrder.  This ensures
+		** that the access path which is generated and executed for
+		** the Optimizable matches the the access path decisions
+		** made by this OptimizerImpl for the best join order.
+		**
+		** NOTE: We we only reload the best plan if it's necessary
+		** to do so--i.e. if the best plans aren't already loaded.
+		** The plans will already be loaded if the last complete
+		** join order we had was the best one so far, because that
+		** means we called "rememberAsBest" on every Optimizable
+		** in the list and, as part of that call, we will run through
+		** and set trulyTheBestAccessPath for the entire subtree.
+		** So if we haven't tried any other plans since then,
+		** we know that every Optimizable (and its subtree) already
+		** has the correct best plan loaded in its trulyTheBest
+		** path field.  It's good to skip the load in this case
+		** because 'reloading best plans' involves walking the
+		** entire subtree of _every_ Optimizable in the list, which
+		** can be expensive if there are deeply nested subqueries.
+		*/
+		if (reloadBestPlan)
+			pullMe.updateBestPlanMap(FromTable.LOAD_PLAN, this);
+
+		/* Mark current join position as unused */
+		proposedJoinOrder[joinPosition] = -1;
+
+		/* If we didn't advance the join position then the optimizable
+		 * which currently sits at proposedJoinOrder[joinPosition]--call
+		 * it PULL_ME--is *not* going to remain there. Instead, we're
+		 * going to pull that optimizable from its position and attempt
+		 * to put another one in its place.  That said, when we try to
+		 * figure out which of the other optimizables to place at
+		 * joinPosition, we'll first do some "dependency checking", the
+		 * result of which relies on the contents of assignedTableMap.
+		 * Since assignedTableMap currently holds info about PULL_ME
+		 * and since PULL_ME is *not* going to remain in the join order,
+		 * we need to remove the info for PULL_ME from assignedTableMap.
+		 * Otherwise an Optimizable which depends on PULL_ME could
+		 * incorrectly be placed in the join order *before* PULL_ME,
+		 * which would violate the dependency and lead to incorrect
+		 * results. DERBY-3288.
+		 */
+		assignedTableMap.xor(pullMe.getReferencedTableMap());
 	}
 
 	/*

Modified: db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out?rev=619932&r1=619931&r2=619932&view=diff
==============================================================================
--- db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out
(original)
+++ db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out
Fri Feb  8 08:31:44 2008
@@ -7648,4 +7648,107 @@
 0 rows inserted/updated/deleted
 ij> drop table odd;
 0 rows inserted/updated/deleted
+ij> -- DERBY-3288: Optimizer does not correctly enforce EXISTS join order
+-- dependencies in the face of "short-circuited" plans.  In this test
+-- an EXISTS subquery is flattened into the outer query and thus has
+-- has a dependency on another FromTable (esp. HalfOuterJoinNode).
+-- The tables are such that the optimizer will attempt to short-
+-- circuit some relatively bad plans (namely, any join order that
+-- starts with { TAB_V, HOJ, ...}), and needs to correctly enforce
+-- join order dependencies in the process.
+CREATE TABLE tab_a (PId BIGINT NOT NULL);
+0 rows inserted/updated/deleted
+ij> CREATE TABLE tab_c (Id BIGINT NOT NULL PRIMARY KEY,
+  PAId BIGINT NOT NULL, PBId BIGINT NOT NULL);
+0 rows inserted/updated/deleted
+ij> INSERT INTO tab_c VALUES (91, 81, 82);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_c VALUES (92, 81, 84);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_c VALUES (93, 81, 88);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_c VALUES (96, 81, 83);
+1 row inserted/updated/deleted
+ij> CREATE TABLE tab_v (OId BIGINT NOT NULL,
+  UGId BIGINT NOT NULL, val CHAR(1) NOT NULL);
+0 rows inserted/updated/deleted
+ij> CREATE UNIQUE INDEX tab_v_i1 ON tab_v (OId, UGId, val);
+0 rows inserted/updated/deleted
+ij> CREATE INDEX tab_v_i2 ON tab_v (UGId, val, OId);
+0 rows inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (81, 31, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (82, 31, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (83, 31, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (84, 31, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (85, 31, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (86, 31, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (87, 31, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (81, 32, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (82, 32, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (83, 32, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (84, 32, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (85, 32, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (86, 32, 'A');
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_v VALUES (87, 32, 'A');
+1 row inserted/updated/deleted
+ij> CREATE TABLE tab_b (Id BIGINT NOT NULL PRIMARY KEY, OId BIGINT NOT NULL);
+0 rows inserted/updated/deleted
+ij> INSERT INTO tab_b VALUES (141, 81);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_b VALUES (142, 82);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_b VALUES (143, 84);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_b VALUES (144, 88);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_b VALUES (151, 81);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_b VALUES (152, 83);
+1 row inserted/updated/deleted
+ij> CREATE TABLE tab_d (Id BIGINT NOT NULL PRIMARY KEY,
+  PAId BIGINT NOT NULL, PBId BIGINT NOT NULL);
+0 rows inserted/updated/deleted
+ij> INSERT INTO tab_d VALUES (181, 141, 142);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_d VALUES (182, 141, 143);
+1 row inserted/updated/deleted
+ij> INSERT INTO tab_d VALUES (186, 151, 152);
+1 row inserted/updated/deleted
+ij> -- Query should return 2 rows; before DERBY-3288 was fixed, it would
+-- only return a single row due to violation of join order dependencies.
+SELECT tab_b.Id
+FROM tab_b JOIN tab_c ON (tab_b.OId = tab_c.PAId OR tab_b.OId = tab_c.PBId)
+LEFT OUTER JOIN tab_a ON tab_b.OId = PId
+WHERE EXISTS
+  (SELECT 'X' FROM tab_d
+    WHERE (PAId = 141 AND PBId = tab_b.Id)
+        OR (PBId = 141 AND PAId = tab_b.Id))
+  AND EXISTS
+    (SELECT 'X' FROM tab_v
+      WHERE OId = tab_b.OId AND UGId = 31 AND val = 'A');
+ID                  
+--------------------
+142                 
+143                 
+ij> drop table tab_d;
+0 rows inserted/updated/deleted
+ij> drop table tab_b;
+0 rows inserted/updated/deleted
+ij> drop table tab_v;
+0 rows inserted/updated/deleted
+ij> drop table tab_c;
+0 rows inserted/updated/deleted
 ij> 

Modified: db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql?rev=619932&r1=619931&r2=619932&view=diff
==============================================================================
--- db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql
(original)
+++ db/derby/code/branches/10.3/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql
Fri Feb  8 08:31:44 2008
@@ -433,3 +433,77 @@
 drop table digits;
 drop table odd;
 
+-- DERBY-3288: Optimizer does not correctly enforce EXISTS join order
+-- dependencies in the face of "short-circuited" plans.  In this test
+-- an EXISTS subquery is flattened into the outer query and thus has
+-- has a dependency on another FromTable (esp. HalfOuterJoinNode).
+-- The tables are such that the optimizer will attempt to short-
+-- circuit some relatively bad plans (namely, any join order that
+-- starts with { TAB_V, HOJ, ...}), and needs to correctly enforce
+-- join order dependencies in the process.
+
+CREATE TABLE tab_a (PId BIGINT NOT NULL); 
+CREATE TABLE tab_c (Id BIGINT NOT NULL PRIMARY KEY,
+  PAId BIGINT NOT NULL, PBId BIGINT NOT NULL);
+
+INSERT INTO tab_c VALUES (91, 81, 82);
+INSERT INTO tab_c VALUES (92, 81, 84);
+INSERT INTO tab_c VALUES (93, 81, 88);
+INSERT INTO tab_c VALUES (96, 81, 83);
+
+CREATE TABLE tab_v (OId BIGINT NOT NULL,
+  UGId BIGINT NOT NULL, val CHAR(1) NOT NULL);
+
+CREATE UNIQUE INDEX tab_v_i1 ON tab_v (OId, UGId, val);
+CREATE INDEX tab_v_i2 ON tab_v (UGId, val, OId);
+
+INSERT INTO tab_v VALUES (81, 31, 'A');
+INSERT INTO tab_v VALUES (82, 31, 'A');
+INSERT INTO tab_v VALUES (83, 31, 'A');
+INSERT INTO tab_v VALUES (84, 31, 'A');
+INSERT INTO tab_v VALUES (85, 31, 'A');
+INSERT INTO tab_v VALUES (86, 31, 'A');
+INSERT INTO tab_v VALUES (87, 31, 'A');
+INSERT INTO tab_v VALUES (81, 32, 'A');
+INSERT INTO tab_v VALUES (82, 32, 'A');
+INSERT INTO tab_v VALUES (83, 32, 'A');
+INSERT INTO tab_v VALUES (84, 32, 'A');
+INSERT INTO tab_v VALUES (85, 32, 'A');
+INSERT INTO tab_v VALUES (86, 32, 'A');
+INSERT INTO tab_v VALUES (87, 32, 'A');
+
+CREATE TABLE tab_b (Id BIGINT NOT NULL PRIMARY KEY, OId BIGINT NOT NULL);
+
+INSERT INTO tab_b VALUES (141, 81);
+INSERT INTO tab_b VALUES (142, 82);
+INSERT INTO tab_b VALUES (143, 84);
+INSERT INTO tab_b VALUES (144, 88);
+INSERT INTO tab_b VALUES (151, 81);
+INSERT INTO tab_b VALUES (152, 83);
+
+CREATE TABLE tab_d (Id BIGINT NOT NULL PRIMARY KEY,
+  PAId BIGINT NOT NULL, PBId BIGINT NOT NULL);
+
+INSERT INTO tab_d VALUES (181, 141, 142);
+INSERT INTO tab_d VALUES (182, 141, 143);
+INSERT INTO tab_d VALUES (186, 151, 152); 
+
+-- Query should return 2 rows; before DERBY-3288 was fixed, it would
+-- only return a single row due to violation of join order dependencies.
+
+SELECT tab_b.Id
+FROM tab_b JOIN tab_c ON (tab_b.OId = tab_c.PAId OR tab_b.OId = tab_c.PBId)
+LEFT OUTER JOIN tab_a ON tab_b.OId = PId
+WHERE EXISTS
+  (SELECT 'X' FROM tab_d
+    WHERE (PAId = 141 AND PBId = tab_b.Id)
+        OR (PBId = 141 AND PAId = tab_b.Id))
+  AND EXISTS
+    (SELECT 'X' FROM tab_v
+      WHERE OId = tab_b.OId AND UGId = 31 AND val = 'A');
+
+
+drop table tab_d;
+drop table tab_b;
+drop table tab_v;
+drop table tab_c;



Mime
View raw message