db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From banda...@apache.org
Subject 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/
Date Tue, 04 Oct 2005 01:12:17 GMT
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



Mime
View raw message