Bug #37662 nested if() inside sum() is parsed in exponential time

• Submitted: 26 Jun 2008 12:00
• Modified: 14 Aug 2008 3:46
• Reporter: Shane Bester (Platinum Quality Contributor)
• Status: Closed
• Category: MySQL Server: General
• Severity: S1 (Critical)
• Version: 5.0.64, 5.1.24
• OS: Any
• Assigned to: Georgi Kodinov
• CPU Architecture: Any
• Tags: DoS, regression

[26 Jun 2008 12:00] Shane Bester

Description:
Asking mysql to calculate lengthly expressions, we can cause the server to enter 100% cpu and hang the connection, as well as any other connection attempting to access those tables.

Processlist shows this:

 Query   |  388 | init  | select t1.a,

The server isn't totally, hung, but takes forever.  The running stack trace of the thread looks like this:

mysqld.exe!Item::decimal_int_part
mysqld.exe!Item_func_if::decimal_precision
mysqld.exe!Item::decimal_int_part
mysqld.exe!Item_func_if::decimal_precision
mysqld.exe!Item::decimal_int_part
mysqld.exe!Item_func_if::decimal_precision
<cut many>
mysqld.exe!Item_func_if::decimal_precision
mysqld.exe!Item_func_additive_op::result_precision
mysqld.exe!Item_num_op::find_num_type
mysqld.exe!Item_func_numhybrid::fix_length_and_dec
mysqld.exe!Item_func::fix_fields
mysqld.exe!setup_fields
mysqld.exe!JOIN::prepare
mysqld.exe!mysql_select
mysqld.exe!handle_select
mysqld.exe!mysql_execute_command
mysqld.exe!mysql_parse
mysqld.exe!dispatch_command
mysqld.exe!do_command
mysqld.exe!handle_one_connection
mysqld.exe!pthread_start

How to repeat:
run the attached sql at the command line prompt.

[26 Jun 2008 12:02] MySQL Verification Team

import into mysql client, watch processlist

Attachment: bug37662_testcase.sql (application/unknown, text), 10.66 KiB.

[26 Jun 2008 14:52] Axel Schwenke

I narrowed down the test case. It basically looks like this

create table t1 (c1 int);

select sum(
if(c1=x1, y1,
if(c1=x2, y2,
if(c1=x3, y3,
...
if(c1=xN, yN, 0).....)
) as r1
from t1;

it is a Matrjoska of nested IF()s inside a SUM(). The runtime seems to grow exponentially, even if the table is empty. The attached test.sql file runs in 0.07sec for 20 nested IF()s, nearly doubling the runtime with each step deeper. With 30 IF()s runtime is 27.45sec.

[26 Jun 2008 14:53] Axel Schwenke

test.sql

Attachment: test.sql (application/octet-stream, text), 4.84 KiB.

[26 Jun 2008 15:12] Axel Schwenke

This is a regression bug, probably introduced with 5.0. Not seen in 4.1.24 and 4.0.31.

[29 Jul 2008 15:48] Georgi Kodinov

Let me just say : the server is not hung. It's working, but it's working in a redundant set of functions.
It does that only if there is a + as a top level and then there's an if() in it.

[29 Jul 2008 15:50] Georgi Kodinov

The top of the gprof list is :
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total     
 time   seconds   seconds    calls   s/call   s/call  name    
 39.47      8.98     8.98        1     8.98    12.74  Item_func_if::decimal_precision() const
 16.53     12.74     3.76 2147483649     0.00     0.00  Item_int::decimal_precision() const
 12.35     15.55     2.81                             __profile_frequency
 12.18     18.32     2.77                             Item_func_ifnull::decimal_precision() const
 10.37     20.68     2.36                             __recvmsg_nocancel
  9.01     22.73     2.05                             Item_int::neg()
  0.04     22.74     0.01       14     0.00     0.00  get_form_pos(int, unsigned char*, st_typelib*)
  0.04     22.75     0.01                             fde_mixed_encoding_compare
...

[30 Jul 2008 11:16] Georgi Kodinov

The patch : http://lists.mysql.com/commits/50704

[7 Aug 2008 18:39] Bugs System

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/51138

2744 Marc Alff	2008-08-07 [merge]
      Merge mysql-6.0-bugteam -> local bugfix branch

[12 Aug 2008 14:48] Bugs System

Pushed into 6.0.7-alpha  (revid:[e-mail]-20080730110737-jddt94c5rtcxu9uo) (version source revid:[e-mail]-20080812141852-8e6knbqclpfd8irn) (pib:3)

[12 Aug 2008 15:14] Bugs System

Pushed into 5.1.28  (revid:[e-mail]-20080730110737-jddt94c5rtcxu9uo) (version source revid:[e-mail]-20080812142843-he05ncsggstbn57z) (pib:3)

[12 Aug 2008 19:11] Bugs System

Pushed into 5.0.68  (revid:[e-mail]-20080730110737-jddt94c5rtcxu9uo) (version source revid:[e-mail]-20080812185100-d47qb8mz2ye6pe6b) (pib:3)

[14 Aug 2008 3:46] Paul DuBois

Noted in 5.0.68, 5.1.28, 6.0.7 changelogs.

Nesting of IF() inside of SUM() could cause an extreme server
slowdown.

[28 Aug 2008 20:16] Bugs System

Pushed into 6.0.7-alpha  (revid:[e-mail]-20080822132131-uveo6wiuecy6m2b8) (version source revid:[e-mail]-20080822132131-uveo6wiuecy6m2b8) (pib:3)

[13 Sep 2008 21:10] Bugs System

Pushed into 6.0.7-alpha  (revid:[e-mail]-20080730110737-jddt94c5rtcxu9uo) (version source revid:[e-mail]-20080725175322-8wgujj5xuzrjz3ke) (pib:3)