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 03:12:17 UTC
svn commit: r293480 - 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: bandaram
Date: Mon Oct 3 18:12:05 2005
New Revision: 293480
URL: http://svn.apache.org/viewcvs?rev=293480&view=rev
Log:
DERBY-558: Fix optimizer hang seen for large queries with exists-joins.
The patch does the following:
1) Fixes the logic in OptimizerImpl.java that was causing the hang (an indirect infinite loop).
2) Adds some comments describing the "JUMPING" logic that is in OptimizerImpl so that developers looking at the code can (hopefully) figure out what's going on more quickly in the future.
3) Adds a test case to the lang/subqueryFlattening.sql test for verification of the fix. The test case is based on the repro attached to this issue. NOTE: I had to set the "derby.optimizer.noTimeout" property to true for this entire test--I think this is okay since everything still passes (on my machine), but if anyone feels otherwise, please let me know...
Submitted by Army Brown (qozinx@sbcglobal.net)
Modified:
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
db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties
Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/OptimizerImpl.java?rev=293480&r1=293479&r2=293480&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 Mon Oct 3 18:12:05 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/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subqueryFlattening.out?rev=293480&r1=293479&r2=293480&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 Mon Oct 3 18:12:05 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/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening.sql?rev=293480&r1=293479&r2=293480&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 Mon Oct 3 18:12:05 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/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties
URL: http://svn.apache.org/viewcvs/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties?rev=293480&r1=293479&r2=293480&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties (original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subqueryFlattening_derby.properties Mon Oct 3 18:12:05 2005
@@ -4,3 +4,4 @@
# inbetween.properties for an example.
#
# derby.language.statementCacheSize=20
+derby.optimizer.noTimeout=true