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 ba...@apache.org on 2005/10/04 23:31:48 UTC
svn commit: r294925 - in /db/derby/code/branches/10.1/java:
engine/org/apache/derby/impl/sql/compile/
testing/org/apache/derbyTesting/functionTests/master/
testing/org/apache/derbyTesting/functionTests/tests/lang/
Author: bandaram
Date: Tue Oct 4 14:31:41 2005
New Revision: 294925
URL: http://svn.apache.org/viewcvs?rev=294925&view=rev
Log:
Port fix for DERBY-558 from TRUNK to 10.1 branch.
Submitted by Army Brown (qozinx@sbcglobal.net)
Modified:
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out
db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql
db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties
Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?rev=294925&r1=294924&r2=294925&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java Tue Oct 4 14:31:41 2005
@@ -348,27 +348,121 @@
}
else if (permuteState == JUMPING) //still jumping
{
- nextOptimizable = firstLookOrder[joinPosition];
- Optimizable nextOpt = optimizableList.getOptimizable(nextOptimizable);
- if (! (nextOpt.legalJoinOrder(assignedTableMap)))
+ /* We're "jumping" to a join order that puts the optimizables
+ ** with the lowest estimated costs first (insofar as it
+ ** is legal to do so). The "firstLookOrder" array holds the
+ ** ideal join order for position <joinPosition> up thru
+ ** position <numOptimizables-1>. So here, we look at the
+ ** ideal optimizable to place at <joinPosition> and see if
+ ** it's legal; if it is, then we're done. Otherwise, we
+ ** swap it with <numOptimizables-1> and see if that gives us
+ ** a legal join order w.r.t <joinPosition>. If not, then we
+ ** swap it with <numOptimizables-2> and check, and if that
+ ** fails, then we swap it with <numOptimizables-3>, and so
+ ** on. For example, assume we have 6 optimizables whose
+ ** order from least expensive to most expensive is 2, 1, 4,
+ ** 5, 3, 0. Assume also that we've already verified the
+ ** legality of the first two positions--i.e. that joinPosition
+ ** is now "2". That means that "firstLookOrder" currently
+ ** contains the following:
+ **
+ ** [ pos ] 0 1 2 3 4 5
+ ** [ opt ] 2 1 4 5 3 0
+ **
+ ** Then at this point, we do the following:
+ **
+ ** -- Check to see if the ideal optimizable "4" is valid
+ ** at its current position (2)
+ ** -- If opt "4" is valid, then we're done; else we
+ ** swap it with the value at position _5_:
+ **
+ ** [ pos ] 0 1 2 3 4 5
+ ** [ opt ] 2 1 0 5 3 4
+ **
+ ** -- Check to see if optimizable "0" is valid at its
+ ** new position (2).
+ ** -- If opt "0" is valid, then we're done; else we
+ ** put "0" back in its original position and swap
+ ** the ideal optimizer ("4") with the value at
+ ** position _4_:
+ **
+ ** [ pos ] 0 1 2 3 4 5
+ ** [ opt ] 2 1 3 5 4 0
+ **
+ ** -- Check to see if optimizable "3" is valid at its
+ ** new position (2).
+ ** -- If opt "3" is valid, then we're done; else we
+ ** put "3" back in its original position and swap
+ ** the ideal optimizer ("4") with the value at
+ ** position _3_:
+ **
+ ** [ pos ] 0 1 2 3 4 5
+ ** [ opt ] 2 1 5 4 3 0
+ **
+ ** -- Check to see if optimizable "5" is valid at its
+ ** new position (2).
+ ** -- If opt "5" is valid, then we're done; else we've
+ ** tried all the available optimizables and none
+ ** of them are legal at position 2. In this case,
+ ** we give up on "JUMPING" and fall back to normal
+ ** join-order processing.
+ */
+
+ int idealOptimizable = firstLookOrder[joinPosition];
+ nextOptimizable = idealOptimizable;
+ int lookPos = numOptimizables;
+ int lastSwappedOpt = -1;
+
+ Optimizable nextOpt;
+ for (nextOpt = optimizableList.getOptimizable(nextOptimizable);
+ !(nextOpt.legalJoinOrder(assignedTableMap));
+ nextOpt = optimizableList.getOptimizable(nextOptimizable))
{
- if (joinPosition < numOptimizables - 1)
- {
- firstLookOrder[joinPosition] = firstLookOrder[numOptimizables - 1];
- firstLookOrder[numOptimizables - 1] = nextOptimizable;
+ // Undo last swap, if we had one.
+ if (lastSwappedOpt >= 0) {
+ firstLookOrder[joinPosition] = idealOptimizable;
+ firstLookOrder[lookPos] = lastSwappedOpt;
}
- else
- permuteState = NO_JUMP; //not good
- if (joinPosition > 0)
- {
- joinPosition--;
- rewindJoinOrder(); //jump again?
+
+ if (lookPos > joinPosition + 1) {
+ // we still have other possibilities; get the next
+ // one by "swapping" it into the current position.
+ lastSwappedOpt = firstLookOrder[--lookPos];
+ firstLookOrder[joinPosition] = lastSwappedOpt;
+ firstLookOrder[lookPos] = idealOptimizable;
+ nextOptimizable = lastSwappedOpt;
+ }
+ else {
+ // we went through all of the available optimizables
+ // and none of them were legal in the current position;
+ // so we give up and fall back to normal processing.
+ if (joinPosition > 0) {
+ joinPosition--;
+ rewindJoinOrder();
+ }
+ permuteState = NO_JUMP;
+ break;
}
- continue;
}
- if (joinPosition == numOptimizables - 1) //ready to walk
- permuteState = WALK_HIGH; //walk high hill
+ if (permuteState == NO_JUMP)
+ continue;
+
+ if (joinPosition == numOptimizables - 1) {
+ // we just set the final position within our
+ // "firstLookOrder" join order; now go ahead
+ // and search for the best join order, starting from
+ // the join order stored in "firstLookOrder". This
+ // is called walking "high" because we're searching
+ // the join orders that are at or "above" (after) the
+ // order found in firstLookOrder. Ex. if we had three
+ // optimizables and firstLookOrder was [1 2 0], then
+ // the "high" would be [1 2 0], [2 0 1] and [2 1 0];
+ // the "low" would be [0 1 2], [0 2 1], and [1 0 2].
+ // We walk the "high" first, then fall back and
+ // walk the "low".
+ permuteState = WALK_HIGH;
+ }
}
else
{
Modified: db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out?rev=294925&r1=294924&r2=294925&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out (original)
+++ db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out Tue Oct 4 14:31:41 2005
@@ -7730,4 +7730,46 @@
0 rows inserted/updated/deleted
ij> drop table t4;
0 rows inserted/updated/deleted
+ij> -- Test case for DERBY-558: optimizer hangs in rare cases where
+-- multiple subqueries flattened to EXISTS put multiple restrictions
+-- on legal join orders.
+create table digits (d int);
+0 rows inserted/updated/deleted
+ij> insert into digits values 1, 2, 3, 4, 5, 6, 7, 8, 9, 0;
+10 rows inserted/updated/deleted
+ij> create table odd (o int);
+0 rows inserted/updated/deleted
+ij> insert into odd values 1, 3, 5, 7, 9;
+5 rows inserted/updated/deleted
+ij> commit;
+ij> -- In order to test this, "noTimeout" must be true so that
+-- the optimizer will run through all of the possible join
+-- orders before it quits. In the case of DERBY-558 the
+-- optimizer was getting stuck in a logic loop and thus never
+-- quit, causing the hang. NOTE: The "noTimeout" property
+-- is set in the subqueryFlattening_derby.properties file.
+select distinct temp_t0.d from
+ (select d from digits where d > 3) temp_t0,
+ (select o from odd) temp_t1,
+ odd temp_t4,
+ (select o from odd) temp_t3
+ where temp_t0.d = temp_t1.o
+ and temp_t0.d = temp_t3.o
+ and temp_t0.d in (select o from odd where o = temp_t1.o)
+ and exists (
+ select d from digits
+ where d = temp_t0.d)
+-- Before fix for DERBY-558, we would HANG (loop indefinitely) here;
+-- after fix, we should see three rows returned.
+;
+D
+-----------
+5
+7
+9
+ij> -- clean-up.
+drop table digits;
+0 rows inserted/updated/deleted
+ij> drop table odd;
+0 rows inserted/updated/deleted
ij>
Modified: db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql?rev=294925&r1=294924&r2=294925&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql (original)
+++ db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql Tue Oct 4 14:31:41 2005
@@ -377,3 +377,43 @@
drop table t2;
drop table t3;
drop table t4;
+
+-- Test case for DERBY-558: optimizer hangs in rare cases where
+-- multiple subqueries flattened to EXISTS put multiple restrictions
+-- on legal join orders.
+
+create table digits (d int);
+insert into digits values 1, 2, 3, 4, 5, 6, 7, 8, 9, 0;
+
+create table odd (o int);
+insert into odd values 1, 3, 5, 7, 9;
+commit;
+
+-- In order to test this, "noTimeout" must be true so that
+-- the optimizer will run through all of the possible join
+-- orders before it quits. In the case of DERBY-558 the
+-- optimizer was getting stuck in a logic loop and thus never
+-- quit, causing the hang. NOTE: The "noTimeout" property
+-- is set in the subqueryFlattening_derby.properties file.
+
+select distinct temp_t0.d from
+ (select d from digits where d > 3) temp_t0,
+ (select o from odd) temp_t1,
+ odd temp_t4,
+ (select o from odd) temp_t3
+ where temp_t0.d = temp_t1.o
+ and temp_t0.d = temp_t3.o
+ and temp_t0.d in (select o from odd where o = temp_t1.o)
+ and exists (
+ select d from digits
+ where d = temp_t0.d)
+
+-- Before fix for DERBY-558, we would HANG (loop indefinitely) here;
+-- after fix, we should see three rows returned.
+;
+
+-- clean-up.
+
+drop table digits;
+drop table odd;
+
Modified: db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties
URL: http://svn.apache.org/viewcvs/db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties?rev=294925&r1=294924&r2=294925&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties (original)
+++ db/derby/code/branches/10.1/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties Tue Oct 4 14:31:41 2005
@@ -4,3 +4,4 @@
# inbetween.properties for an example.
#
# derby.language.statementCacheSize=20
+derby.optimizer.noTimeout=true