MySQL Bugs: #37896: Assertion on entry of Item_in_subselect::exec on subquery with AND NOT

Bug #37896	Assertion on entry of Item_in_subselect::exec on subquery with AND NOT
Submitted:	5 Jul 2008 21:32	Modified:	20 Nov 2010 23:10
Reporter:	Philip Stoev	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S1 (Critical)
Version:	6.0	OS:	Any
Assigned to:	Timour Katchaounov	CPU Architecture:	Any
Tags:	regression

Description:
Even with bug #36133 fixed, when executing the SELECT query below, mysqld asserted as follows:

#0  0x00110416 in __kernel_vsyscall ()
#1  0x00581c78 in pthread_kill () from /lib/libpthread.so.0
#2  0x085b0da4 in my_write_core (sig=6) at stacktrace.c:307
#3  0x08213e98 in handle_segfault (sig=6) at mysqld.cc:2638
#4  <signal handler called>
#5  0x00110416 in __kernel_vsyscall ()
#6  0x003e6660 in raise () from /lib/libc.so.6
#7  0x003e8028 in abort () from /lib/libc.so.6
#8  0x003df57e in __assert_fail () from /lib/libc.so.6
#9  0x081d4286 in Item_in_subselect::exec (this=0x9ca3de0) at item_subselect.cc:298
#10 0x081d1363 in Item_in_subselect::val_bool (this=0x9ca3de0) at item_subselect.cc:899
#11 0x0817cd6d in Item::val_bool_result (this=0x9ca3de0) at ../item.h:742
#12 0x081a17e1 in Item_in_optimizer::val_int (this=0x9cbaf38) at item_cmpfunc.cc:1595
#13 0x0828ba55 in JOIN::exec (this=0x9cb99a0) at sql_select.cc:2284
#14 0x0828e1fa in mysql_select (thd=0x9c41f38, rref_pointer_array=0x9c4341c, tables=0x9ca2990, wild_num=0, fields=@0x9c433ac, conds=0x9cb9668, og_num=0,
    order=0x0, group=0x0, having=0x9cb9840, proc_param=0x0, select_options=2147764736, result=0x9cb9990, unit=0x9c43088, select_lex=0x9c43318)
    at sql_select.cc:3001
#15 0x082910dc in handle_select (thd=0x9c41f38, lex=0x9c4302c, result=0x9cb9990, setup_tables_done_option=0) at sql_select.cc:302
#16 0x082201e2 in execute_sqlcom_select (thd=0x9c41f38, all_tables=0x9ca2990) at sql_parse.cc:4847
#17 0x08220f61 in mysql_execute_command (thd=0x9c41f38) at sql_parse.cc:2015
#18 0x0822a02e in mysql_parse (thd=0x9c41f38,
    inBuf=0x9ca2478 "SELECT MIN(DISTINCT OUTR . `date_key` ) AS X FROM B AS OUTR WHERE '0:17:31' IN ( SELECT INNR . `time_nokey` AS Y FROM AA AS INNR WHERE INNR . `time_key` >= INNR . `date_nokey` OR INNR . `varchar_key` "..., length=331, found_semicolon=0xaaaac314) at sql_parse.cc:5811
#19 0x0822a921 in dispatch_command (command=COM_QUERY, thd=0x9c41f38, packet=0x9c9a449 "", packet_length=331) at sql_parse.cc:1051
#20 0x0822ba49 in do_command (thd=0x9c41f38) at sql_parse.cc:724
#21 0x0821bef0 in handle_one_connection (arg=0x9c41f38) at sql_connect.cc:1153
#22 0x0057d32f in start_thread () from /lib/libpthread.so.0
#23 0x0049a27e in clone () from /lib/libc.so.6

The assertion is here:

293     */
294
295     bool Item_in_subselect::exec()
296     {
297       DBUG_ENTER("Item_in_subselect::exec");
298       DBUG_ASSERT(exec_method != MATERIALIZATION ||
299                   (exec_method == MATERIALIZATION &&
300                    engine->engine_type() == subselect_engine::HASH_SJ_ENGINE));
301       /*
302         Initialize the cache of the left predicate operand. This has to be done as

(gdb) print exec_method
$1 = Item_in_subselect::MATERIALIZATION
(gdb) call engine->engine_type()
$1 = subselect_engine::HASH_SJ_ENGINE

How to repeat:
This is the query that caused the crash:

SELECT MIN(DISTINCT OUTR . `date_key` ) AS X FROM B AS OUTR WHERE '0:17:31' IN ( SELECT INNR . `time_nokey` AS Y FROM AA AS INNR WHERE INNR . `time_key` >= INNR . `date_nokey` OR INNR . `varchar_key` <= INNR . `varchar_key`   ) OR ( OUTR . `varchar_key` < 'ifh' AND NOT OUTR . `varchar_key` <> 'o' )  HAVING X <= '2007-6-2 6:18:56;

A full test case will be uploaded shortly.

Here is a simplifed test case:

CREATE TABLE t1 (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `date_key` date DEFAULT NULL,
  `varchar_key` varchar(5) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `date_key` (`date_key`),
  KEY `varchar_key` (`varchar_key`)
);

INSERT INTO t1 VALUES (1,'0000-00-00','ompky');

CREATE TABLE t2 (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `time_nokey` time DEFAULT NULL,
  PRIMARY KEY (`pk`)
);

SELECT MIN(OUTR . `date_key` )
FROM t1 AS OUTR WHERE '0:17:31' IN (
 SELECT INNR . `time_nokey` AS Y
 FROM t2 AS INNR
)
OR (
 OUTR . `varchar_key` < 'ifh'
 AND NOT
 OUTR . `varchar_key` <> 'o'
);

Setting to Open so that the bug verification team can check previous releases.

The subquery in provided testcase cannot be run with semi-join. The problem is somewhere in materialization strategy code.

The regression occurred between 6.0.3 and 6.0.4. The bug is not reproducible
in 6.0.3, reproducible in 6.0.4.

-- Simplified test case:

set @@optimizer_switch='no_semijoin';
SELECT MIN(OUTR.date_key )
FROM t1 AS OUTR
WHERE '0:17:31' IN (SELECT INNR.time_nokey AS Y FROM t2 AS INNR);

Analysis:
--------------------------------------------------------------------------------

(See code outline at the end of the explanation)

The cause of the assertion failure is in the call of JOIN::optimize call to
opt_sum_query. In this case opt_sum_query returns "1", which tells
JOIN::optimize that the query can be computed without access to any table.
Therefore JOIN::optimize sets tables_list == 0.

There is a shortcut in JOIN::optimize that exits early in the optimization
phase if all tables have been optimizer away.

As a result, JOIN::optimize never calls setup_subquery_materialization()
which actually creates/initializes a subselect_hash_sj_engine object for
materialized subquery execution.

At the same time, JOIN::execute still calls conds->val_int(), which in turn
calls Item_in_subselect::exec() where we get the assertion failure because
the "engine" for this item has never been changed to a
subselect_hash_sj_engine.

TODO:
* What remains to be done is to fully analyze opt_sum_query(), and to
* decide whether it legally returns "1" for this query, or not.
If opt_sum_query is fine, then we need to add one extra early call to
setup_subquery_materialization(). Otherwise fix opt_sum_query.

This is an outline of the related code:

JOIN::optimize
{
.....
  conds = optimize_cond(conds, ...)
  *  reduces the where clause to
     Item_in_optimizer(Item_in_subselect(
       '0:17:31' IN (SELECT INNR.time_nokey AS Y FROM t2 AS INNR))
     )
  * but doesn't detect that IN is FALSE because it is marked as expensive
.....
  // Since there is a MIN() function, we call:
  res= opt_sum_query(), res == 1
  ......
  table_list= 0                    <<<=== set the list of FROM tables to empty
  .....
  if (table_list == 0)
    return 0;                      <<<=== RETURN PREMATURELY
  .....
  setup_subquery_materialization() <<<=== never called
  .....
}

JOIN::exec()
{
  .......
  if (!tables_list && (tables || !select_lex->with_sum_func))
  {
    .....
      /*
        We have to test for 'conds' here as the WHERE may not be constant
        even if we don't have any tables for prepared statements or if
        conds uses something like 'rand()'.
      */
      if (cond_value != Item::COND_FALSE &&
          (!conds || conds->val_int()) &&      <<<=== Indirect call to
          (!having || having->val_int()))             Item_in_subselect::exec
    .....
    DBUG_VOID_RETURN;
  }
}

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

2694 Timour Katchaounov	2008-10-15
      BUG#37896 Assertion on entry of Item_in_subselect::exec on subquery with AND NOT
      
      Problem:
      The assertion failure is due to a shortcut in JOIN::optimize where if opt_sum_query
      detects that:
      a) a MIN/MAX function can be computed and substituted by an index lookup, and
      b) the WHERE clause doesn't reference any table in the FROM clause,
      then it does constant substitution, sets JOIN::tables_list = 0, and returns.
      As a result JOIN::optimize never calls setup_subquery_materialization, and never
      creates the correct subselect_engine. JOIN::exec still needs to execute the
      table-independent WHERE clause to check whether there is any result at all.
      This is when the assertion detects this inconsistent state.
      
      
      Solution:
      Call setup_subquery_materialization after the call to opt_sum_query detected that
      (a) and (b) above hold true.
      
      Note:
      This fix makes the behavior the same as that of subquery execution via the IN=>EXISTS
      transformation, thus the same as that of 5.x. However, as BUG#40037 explains, this
      behavior is incorrect because MIN/MAX should return NULL, if the query result is
      empty. This problem is filed as a separate bug since it is not related to materialization
      and is present in older versions.

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

2694 Timour Katchaounov	2008-10-17
      BUG#37896 Assertion on entry of Item_in_subselect::exec on subquery with AND NOT
            
      Problem:
      The assertion failure is due to a shortcut in JOIN::optimize where if opt_sum_query
      detects that:
      a) a MIN/MAX function can be computed and substituted by an index lookup, and
      b) the WHERE clause doesn't reference any table in the FROM clause,
         then it does constant substitution, sets JOIN::tables_list = 0, and returns.
         As a result JOIN::optimize never calls setup_subquery_materialization, and never
         creates the correct subselect_engine. JOIN::exec still needs to execute the
         table-independent WHERE clause to check whether there is any result at all.
         This is when the assertion detects this inconsistent state.
            
            
      Solution:
      Call setup_subquery_materialization after the call to opt_sum_query detected that
      (a) and (b) above hold true.
            
      Note:
      This fix makes the behavior the same as that of subquery execution via the IN=>EXISTS
      transformation, thus the same as that of 5.x. However, as BUG#40037 explains, this
      behavior is incorrect because MIN/MAX should return NULL, if the query result is
      empty. This problem is filed as a separate bug since it is not related to materialization
      and is present in older versions.

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

2700 Timour Katchaounov	2008-11-19 [merge]
      BUG#37896: Assertion on entry of Item_in_subselect::exec on subquery with AND NOT
      
      Merge with mysql-6.0-opt branch.

Pushed into 6.0.10-alpha (revid:sergefp@mysql.com-20081229085854-ui755edl9x4xomen) (version source revid:sergefp@mysql.com-20081126143611-sh4x9pv9vmbnm00v) (merge vers: 6.0.9-alpha) (pib:6)

Short comment for the ChangeLog:

"Fixed a problem where an initialization procedure for materialized subquery
execution wasn't called due to an early optimization of MIN/MAX queries."

I hope the above is clear and compact.

Noted in 6.0.10 changelog.

An initialization procedure for materialized subquery execution was
not called due to an early optimization of MIN()/MAX() queries.

Pushed into mysql-next-mr (revid:alik@sun.com-20100816062819-bluwgdq8q4xysmlg) (version source revid:alik@sun.com-20100816062612-enatdwnv809iw3s9) (pib:20)

Pushed into mysql-trunk 5.6.99-m5 (revid:alexander.nozdrin@oracle.com-20101113155825-czmva9kg4n31anmu) (version source revid:vasil.dimov@oracle.com-20100629074804-359l9m9gniauxr94) (merge vers: 5.6.99-m4) (pib:21)

Noted in 5.6.1 changelog.

Correction: No 5.6.1 changelog entry. Bug does not appear in any released 5.6.x version.