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 ab...@apache.org on 2008/02/06 01:45:52 UTC
svn commit: r618841 - 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: abrown
Date: Tue Feb 5 16:45:48 2008
New Revision: 618841
URL: http://svn.apache.org/viewvc?rev=618841&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.
Modified:
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out
db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java?rev=618841&r1=618840&r2=618841&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/FromVTI.java Tue Feb 5 16:45:48 2008
@@ -1084,17 +1084,25 @@
/* Generate the referenced table map */
referencedTableMap = new JBitSet(numTables);
referencedTableMap.set(tableNumber);
- methodCall.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 methodCall 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 methodCall. So methodCall 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);
- }
- }
+ methodCall.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/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=618841&r1=618840&r2=618841&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 Tue Feb 5 16:45:48 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/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out?rev=618841&r1=618840&r2=618841&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out (original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out Tue Feb 5 16:45:48 2008
@@ -7660,4 +7660,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/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql?rev=618841&r1=618840&r2=618841&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql (original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql Tue Feb 5 16:45:48 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;