db-derby-commits mailing list archives

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



Mime
View raw message