db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From banda...@apache.org
Subject svn commit: r431293 - in /db/derby/code/trunk/java: engine/org/apache/derby/iapi/sql/compile/ engine/org/apache/derby/impl/sql/execute/ testing/org/apache/derbyTesting/functionTests/master/ testing/org/apache/derbyTesting/functionTests/tests/lang/
Date Mon, 14 Aug 2006 05:06:17 GMT
Author: bandaram
Date: Sun Aug 13 22:06:16 2006
New Revision: 431293

URL: http://svn.apache.org/viewvc?rev=431293&view=rev
Log:
DERBY-634: Prevent StackOverflow due to bad subquery optimization. Prevent cases of subquery
optimization that can cause runtime stack overflow.

Submitted by Satheesh Bandaram (satheesh@gmail.com)

Modified:
    db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/execute/BaseActivation.java
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery2.out
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery2.sql

Modified: db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java?rev=431293&r1=431292&r2=431293&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/iapi/sql/compile/Optimizer.java Sun Aug
13 22:06:16 2006
@@ -70,6 +70,12 @@
 	String MAX_MEMORY_PER_TABLE = "derby.language.maxMemoryPerTable";
 
 	/**
+		Maximum size of dynamically created materialized rows. Caching large results
+		use lot of memory and can cause stack overflow. See DERBY-634
+	*/
+	int MAX_DYNAMIC_MATERIALIZED_ROWS = 512;
+
+	/**
 	   Property name for disabling statistics use for all queries.
 	*/
 	String USE_STATISTICS = "derby.language.useStatistics";

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/execute/BaseActivation.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/execute/BaseActivation.java?rev=431293&r1=431292&r2=431293&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/execute/BaseActivation.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/execute/BaseActivation.java
Sun Aug 13 22:06:16 2006
@@ -1409,6 +1409,19 @@
 	 * in-memory converted resultset, or the original result set if not converted.
 	 * See beetle 4373 for details.
 	 *
+	 * Optimization implemented as part of Beetle: 4373 can cause severe stack overflow
+	 * problems. See JIRA entry DERBY-634. With default MAX_MEMORY_PER_TABLE of 1MG, it is
+	 * possible that this optimization could attempt to cache upto 250K rows as nested
+	 * union results. At runtime, this would cause stack overflow.
+	 *
+	 * As Jeff mentioned in DERBY-634, right way to optimize original problem would have been
+	 * to address subquery materialization during optimization phase, through hash joins.
+	 * Recent Army's optimizer work through DEBRY-781 and related work introduced a way to
+	 * materialize subquery results correctly and needs to be extended to cover this case.
+	 * While his optimization needs to be made more generic and stable, I propose to avoid
+	 * this regression by limiting size of the materialized resultset created here to be
+	 * less than MAX_MEMORY_PER_TABLE and MAX_DYNAMIC_MATERIALIZED_ROWS.
+	 *
 	 *	@param	rs	input result set
 	 *	@return	materialized resultset, or original rs if it can't be materialized
 	 */
@@ -1432,7 +1445,8 @@
 		while (aRow != null)
 		{
 			cacheSize += aRow.getColumn(1).getLength();
-			if (cacheSize > maxMemoryPerTable)
+			if (cacheSize > maxMemoryPerTable ||
+					rowCache.size() > Optimizer.MAX_DYNAMIC_MATERIALIZED_ROWS)
 				break;
 			rowCache.addElement(aRow.getClone(toClone));
 			aRow = rs.getNextRowCore();

Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery2.out
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery2.out?rev=431293&r1=431292&r2=431293&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery2.out
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/subquery2.out
Sun Aug 13 22:06:16 2006
@@ -1020,4 +1020,73 @@
 0 rows inserted/updated/deleted
 ij> drop table w_2;
 0 rows inserted/updated/deleted
+ij> -- DERBY-634: Dynamic subquery materialization can cause stack overflow
+create table parentT ( i int, j int, k int);
+0 rows inserted/updated/deleted
+ij> create table childT ( i int, j int, k int);
+0 rows inserted/updated/deleted
+ij> -- Load some data
+insert into parentT values (1,1,1), (2,2,2), (3,3,3), (4,4,4);
+4 rows inserted/updated/deleted
+ij> insert into parentT select i+4, j+4, k+4 from parentT;
+4 rows inserted/updated/deleted
+ij> insert into parentT select i+8, j+8, k+8 from parentT;
+8 rows inserted/updated/deleted
+ij> insert into parentT select i+16, j+16, k+16 from parentT;
+16 rows inserted/updated/deleted
+ij> insert into parentT select i+32, j+32, k+32 from parentT;
+32 rows inserted/updated/deleted
+ij> insert into parentT select i+64, j+64, k+64 from parentT;
+64 rows inserted/updated/deleted
+ij> insert into parentT select i+128, j+128, k+128 from parentT;
+128 rows inserted/updated/deleted
+ij> insert into parentT select i+256, j+256, k+256 from parentT;
+256 rows inserted/updated/deleted
+ij> insert into parentT select i+512, j+512, k+512 from parentT;
+512 rows inserted/updated/deleted
+ij> insert into parentT select i+1024, j+1024, k+1024 from parentT;
+1024 rows inserted/updated/deleted
+ij> insert into parentT select i+2048, j+2048, k+2048 from parentT;
+2048 rows inserted/updated/deleted
+ij> insert into parentT select i+4096, j+4096, k+4096 from parentT;
+4096 rows inserted/updated/deleted
+ij> insert into parentT select i+8192, j+8192, k+8192 from parentT;
+8192 rows inserted/updated/deleted
+ij> -- Try with three different sizes of subquery results.
+update parentT set j = j /10;
+16384 rows inserted/updated/deleted
+ij> update parentT set k = k /100;
+16384 rows inserted/updated/deleted
+ij> create unique index parentIdx on parentT(i);
+0 rows inserted/updated/deleted
+ij> insert into childT select * from parentT;
+16384 rows inserted/updated/deleted
+ij> select count(*) from parentT where i < 10 and i not in (select i from childT);
+1          
+-----------
+0          
+ij> select count(*) from parentT where i< 10 and exists (select i from childT where
childT.i=parentT.i);
+1          
+-----------
+9          
+ij> select count(*) from parentT where i< 10 and j not in (select distinct j from childT);
+1          
+-----------
+0          
+ij> select count(*) from parentT where i< 10 and exists (select distinct j from childT
where childT.j=parentT.j);
+1          
+-----------
+9          
+ij> select count(*) from parentT where i< 10 and k not in (select distinct k from childT);
+1          
+-----------
+0          
+ij> select count(*) from parentT where i< 10 and exists (select distinct k from childT
where childT.k=parentT.k);
+1          
+-----------
+9          
+ij> drop table childT;
+0 rows inserted/updated/deleted
+ij> drop table parentT;
+0 rows inserted/updated/deleted
 ij> 

Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery2.sql
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery2.sql?rev=431293&r1=431292&r2=431293&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery2.sql
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/lang/subquery2.sql
Sun Aug 13 22:06:16 2006
@@ -337,3 +337,45 @@
 drop table v_empty;
 drop table w_2;
 
+-- DERBY-634: Dynamic subquery materialization can cause stack overflow
+
+create table parentT ( i int, j int, k int);
+create table childT ( i int, j int, k int);
+
+-- Load some data
+insert into parentT values (1,1,1), (2,2,2), (3,3,3), (4,4,4);
+insert into parentT select i+4, j+4, k+4 from parentT;
+insert into parentT select i+8, j+8, k+8 from parentT;
+insert into parentT select i+16, j+16, k+16 from parentT;
+insert into parentT select i+32, j+32, k+32 from parentT;
+insert into parentT select i+64, j+64, k+64 from parentT;
+insert into parentT select i+128, j+128, k+128 from parentT;
+insert into parentT select i+256, j+256, k+256 from parentT;
+insert into parentT select i+512, j+512, k+512 from parentT;
+insert into parentT select i+1024, j+1024, k+1024 from parentT;
+insert into parentT select i+2048, j+2048, k+2048 from parentT;
+insert into parentT select i+4096, j+4096, k+4096 from parentT;
+insert into parentT select i+8192, j+8192, k+8192 from parentT;
+
+-- Try with three different sizes of subquery results.
+update parentT set j = j /10;
+update parentT set k = k /100;
+create unique index parentIdx on parentT(i);
+
+insert into childT select * from parentT;
+
+select count(*) from parentT where i < 10 and i not in (select i from childT);
+
+select count(*) from parentT where i< 10 and exists (select i from childT where childT.i=parentT.i);
+
+select count(*) from parentT where i< 10 and j not in (select distinct j from childT);
+
+select count(*) from parentT where i< 10 and exists (select distinct j from childT where
childT.j=parentT.j);
+
+select count(*) from parentT where i< 10 and k not in (select distinct k from childT);
+
+select count(*) from parentT where i< 10 and exists (select distinct k from childT where
childT.k=parentT.k);
+
+drop table childT;
+drop table parentT;
+



Mime
View raw message