From derby-commits-return-1442-apmail-db-derby-commits-archive=db.apache.org@db.apache.org Tue Oct 04 01:12:40 2005 Return-Path: Delivered-To: apmail-db-derby-commits-archive@www.apache.org Received: (qmail 33967 invoked from network); 4 Oct 2005 01:12:40 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199) by minotaur.apache.org with SMTP; 4 Oct 2005 01:12:40 -0000 Received: (qmail 6874 invoked by uid 500); 4 Oct 2005 01:12:39 -0000 Delivered-To: apmail-db-derby-commits-archive@db.apache.org Received: (qmail 6816 invoked by uid 500); 4 Oct 2005 01:12:39 -0000 Mailing-List: contact derby-commits-help@db.apache.org; run by ezmlm Precedence: bulk list-help: list-unsubscribe: List-Post: Reply-To: "Derby Development" List-Id: Delivered-To: mailing list derby-commits@db.apache.org Received: (qmail 6804 invoked by uid 99); 4 Oct 2005 01:12:39 -0000 X-ASF-Spam-Status: No, hits=-9.8 required=10.0 tests=ALL_TRUSTED,NO_REAL_NAME X-Spam-Check-By: apache.org Received: from [209.237.227.194] (HELO minotaur.apache.org) (209.237.227.194) by apache.org (qpsmtpd/0.29) with SMTP; Mon, 03 Oct 2005 18:12:38 -0700 Received: (qmail 33933 invoked by uid 65534); 4 Oct 2005 01:12:18 -0000 Message-ID: <20051004011218.33932.qmail@minotaur.apache.org> Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: derby-commits@db.apache.org From: bandaram@apache.org X-Mailer: svnmailer-1.0.5 X-Virus-Checked: Checked by ClamAV on apache.org X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N 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 up thru + ** position . So here, we look at the + ** ideal optimizable to place at and see if + ** it's legal; if it is, then we're done. Otherwise, we + ** swap it with and see if that gives us + ** a legal join order w.r.t . If not, then we + ** swap it with and check, and if that + ** fails, then we swap it with , 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