MySQL Bugs: #31048: many nested subqueries causes out of memory and crash

Bug #31048	many nested subqueries causes out of memory and crash
Submitted:	16 Sep 2007 17:49	Modified:	14 Jan 2008 20:42
Reporter:	Shane Bester (Platinum Quality Contributor)	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: General	Severity:	S3 (Non-critical)
Version:	5.1.23BK, 5.0.48	OS:	Any
Assigned to:	Evgeny Potemkin	CPU Architecture:	Any
Tags:	bfsm_2007_10_18

Description:
Many nested subqueries is not very optimal.  memory usage is huge, and if kernel doesn't kill mysqld, then mysqld will segfault and crash by itself.

On Windows for example, there is no OOM killer.  In this case I get a few errors in the log:

070916 19:41:21 [ERROR] mysqld-nt: Out of memory (Needed 2800252 bytes)
070916 19:41:21 [ERROR] Out of memory; check if mysqld or some other process uses all available memory; if not, you may

Then, at end, mysqld-nt.exe crashes with this stack:

mysqld-nt.exe!st_join_table::cleanup  Line 6245
mysqld-nt.exe!JOIN::cleanup Line 6401
mysqld-nt.exe!JOIN::destroy  Line 2119
mysqld-nt.exe!st_select_lex::cleanup  Line 768
mysqld-nt.exe!mysql_select  Line 2269
mysqld-nt.exe!mysql_explain_union  Line 15355
mysqld-nt.exe!mysql_execute_command  Line 2647
mysqld-nt.exe!mysql_parse  Line 6093
mysqld-nt.exe!dispatch_command  Line 1814
mysqld-nt.exe!do_command  Line 1586
mysqld-nt.exe!handle_one_connection  Line 1197
mysqld-nt.exe!pthread_start  Line 62
mysqld-nt.exe!_threadstart  Line 196
kernel32.dll!FlsSetValue 

How to repeat:
drop table if exists t1;
create table t1(a int,b int,key(a),key(b))engine=myisam;
insert into t1(a,b) values (1,2),(2,1),(2,3),(3,4),(5,4),(5,5),(6,7),(7,4),(5,3);
explain select sum(a),a from t1 
where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 where a>
(
        select sum(a) from t1 
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)group by b limit 1
)
        
group by a;

Suggested fix:
1) Fix the crash.  Return some error message such as out of memory.
2) See if memory consumption can be reduced.  The above query needed >2GB of RAM!

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/36635

ChangeSet@1.2549, 2007-10-30 15:39:51+00:00, evgen@moonbone.local +4 -0
  Bug#31048: Many nested subqueries may cause server crash.
  
  This bug is actually two. The first one manifests itself on an EXPLAIN
  SELECT query with nested subqueries that employs the filesort algorithm.
  The whole SELECT under explain is marked as UNCACHEABLE_EXPLAIN to preserve
  some temporary structures for explain. As a side-effect of this values of
  nested subqueries weren't cached and subqueries were re-evaluated many
  times. Each time buffer for filesort was allocated but wasn't freed because
  freeing occurs at the end of topmost SELECT. Thus all available memory was
  eaten up step by step and OOM event occur.
  The second bug manifests itself on SELECT queries with conditions where
  a subquery result is compared with a key field and the subquery itself also
  has such condition. When a long chain of such nested subqueries is present
  the stack overrun occur. This happens because at some point the range optimizer
  temporary puts the PARAM structure on the stack. Its size if about 8K and
  the stack is exhausted very fast.
  
  Now the subselect_single_select_engine::exec function allows subquery result
  caching when the UNCACHEABLE_EXPLAIN flag is set.
  Now the SQL_SELECT::test_quick_select function allocates the PARAM structure
  on the heap and frees it on exit.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/37668

ChangeSet@1.2549, 2007-11-13 18:03:08+00:00, evgen@moonbone.local +4 -0
  Bug#31048: Many nested subqueries may cause server crash.
  
  This bug is actually two. The first one manifests itself on an EXPLAIN
  SELECT query with nested subqueries that employs the filesort algorithm.
  The whole SELECT under explain is marked as UNCACHEABLE_EXPLAIN to preserve
  some temporary structures for explain. As a side-effect of this values of
  nested subqueries weren't cached and subqueries were re-evaluated many
  times. Each time buffer for filesort was allocated but wasn't freed because
  freeing occurs at the end of topmost SELECT. Thus all available memory was
  eaten up step by step and OOM event occur.
  The second bug manifests itself on SELECT queries with conditions where
  a subquery result is compared with a key field and the subquery itself also
  has such condition. When a long chain of such nested subqueries is present
  the stack overrun occur. This happens because at some point the range optimizer
  temporary puts the PARAM structure on the stack. Its size if about 8K and
  the stack is exhausted very fast.
  
  Now the subselect_single_select_engine::exec function allows subquery result
  caching when the UNCACHEABLE_EXPLAIN flag is set.
  Now the SQL_SELECT::test_quick_select function allocates the PARAM structure
  on the heap and frees it on exit. Also now it calls the check_stack_overrun
  function for stack checking purposes.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/38089

ChangeSet@1.2549, 2007-11-19 20:00:25+00:00, evgen@moonbone.local +4 -0
  Bug#31048: Many nested subqueries may cause server crash.
  
  This bug is actually two. The first one manifests itself on an EXPLAIN
  SELECT query with nested subqueries that employs the filesort algorithm.
  The whole SELECT under explain is marked as UNCACHEABLE_EXPLAIN to preserve
  some temporary structures for explain. As a side-effect of this values of
  nested subqueries weren't cached and subqueries were re-evaluated many
  times. Each time buffer for filesort was allocated but wasn't freed because
  freeing occurs at the end of topmost SELECT. Thus all available memory was
  eaten up step by step and OOM event occur.
  The second bug manifests itself on SELECT queries with conditions where
  a subquery result is compared with a key field and the subquery itself also
  has such condition. When a long chain of such nested subqueries is present
  the stack overrun occur. This happens because at some point the range optimizer
  temporary puts the PARAM structure on the stack. Its size if about 8K and
  the stack is exhausted very fast.
  
  Now the subselect_single_select_engine::exec function allows subquery result
  caching when the UNCACHEABLE_EXPLAIN flag is set.
  Now the SQL_SELECT::test_quick_select function calls the check_stack_overrun
  function for stack checking purposes to prevent server crash.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/38312

ChangeSet@1.2580, 2007-11-23 00:16:17+03:00, evgen@moonbone.local +3 -0
  opt_range.cc:
    Fix for the bug#31048 for 64bit platforms.
  subselect.test, subselect.result:
    Corrected text case for the bug#31048.

Pushed into 5.0.54

Pushed into 5.1.23-rc

Pushed into 6.0.5-alpha

Documented bugfix in the 5.0.54, 5.1.23, and 6.0.5 changelogs as follows:

        Many nested subqueries in a single query could led to excessive
        memory consumption and possibly a crash of the server.

Pushed into 6.0.5-alpha

Pushed into 5.1.24-rc

Pushed into 5.0.60

System: Redhat EL5 Server i386
MySQL Version: 5.1.24-rc

It seems this is still failing:

main.subselect3                
[ pass ]           2750
main.subselect_gis             
[ pass ]            122
main.subselect_innodb          
[ pass ]           1693
main.subselect_notembedded     
[ fail ]
mysqltest: At line 52: query '$start $end' failed with wrong errno 2013: 'Lost
connection to MySQL server during query', instead of 0...
The result from queries just before the failure was:
purge master logs before (select adddate(current_timestamp(), interval -4
day));
ERROR 42000: You have an error in your SQL syntax; check the manual that
corresponds to your MySQL server version for the right syntax to use near
'select adddate(current_timestamp(), interval -4 day))' at line 1
purge master logs before adddate(current_timestamp(), interval -4 day);
create table t1(a int,b int,key(a),key(b));
insert into t1(a,b) values (1,2),(2,1),(2,3),(3,4),(5,4),(5,5),
(6,7),(7,4),(5,3);
5
4
3
2
1
26
25
24
23
22
21
More results from queries before failure can be found in
/builddir/build/BUILD/mysql-5.1.24-rc/mysql-test/var/log/subselect_notembedded.log
Aborting: main.subselect_notembedded failed in default mode. 
To continue, re-run with '--force'.
Stopping All Servers
make: *** [test-ns] Error 1

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/53178

2821 Konstantin Osipov	2008-09-03
      Fix a valgrind test suite failure on blade13 (pb-valgrind host).
      The test case for Bug#31048 runs out of stack there in --ps-protocol.
      This is a 64 bit host, and we need a lot of stack there.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/53179

2821 Konstantin Osipov	2008-09-03
      Fix a valgrind test suite failure on blade13 (pb-valgrind host).
      The test case for Bug#31048 runs out of stack there in --ps-protocol.
      This is a 64 bit host, and we need a lot of stack there.

Pushed into 6.0.7-alpha  (revid:konstantin@mysql.com-20080903144019-98m69kawe1ckl7p8) (version source revid:kgeorge@mysql.com-20080903144653-4ualkgw26vtl0t0j) (pib:3)

Pushed into 6.0.7-alpha  (revid:konstantin@mysql.com-20080903144019-98m69kawe1ckl7p8) (version source revid:jorgen.loland@sun.com-20080818082556-mwzfrfaarth2zprz) (pib:3)

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/53909

2682 He Zhenxing	2008-09-12 [merge]
      Auto merge
      Update plugin.h.pp for WL#4398

Pushed into 6.0.7-alpha  (revid:konstantin@mysql.com-20080903144019-98m69kawe1ckl7p8) (version source revid:vvaintroub@mysql.com-20080804094710-jb2qpqxpf2ir2gf3) (pib:3)

Pushed into 6.0.7-alpha  (revid:konstantin@mysql.com-20080903144019-98m69kawe1ckl7p8) (version source revid:alik@mysql.com-20080805141411-g3y3q3q3ot01y2uj) (pib:3)