Bug #58456 Assertion 0 in QUICK_INDEX_MERGE_SELECT::need_sorted_output in opt_range.h
Submitted: 24 Nov 2010 13:17 Modified: 20 Jan 2011 19:14
Reporter: John Embretsen Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S1 (Critical)
Version:5.6.1-m5 OS:Any
Assigned to: Jørgen Løland CPU Architecture:Any
Triage: Triaged: D1 (Critical)

[24 Nov 2010 13:17] John Embretsen
Description:
While running a relatively simple JOIN query with ORDER BY against a debug build of MySQL (mysql-trunk-bugfixing), the following assertion is hit:

Assertion failed: 0, file /export/home/tmp/je159969/mysql-dev/bzr-repos/mysql-trunk-bugfixing/sql/opt_range.h, line 565
101124 14:54:34 - mysqld got signal 6 ;

Stacktrace:

[12] _assert(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff1fdc95 
  [13] QUICK_INDEX_MERGE_SELECT::need_sorted_output(this = 0x463bb80), line 565 in "opt_range.h"
  [14] test_if_skip_sort_order(tab = 0x4648c80, order = 0x4646758, select_limit = 18446744073709551615ULL, no_changes = false, map = 0x4641f20), line 20003 in "sql_select.cc"
  [15] create_sort_index(thd = 0x45ea1f0, join = 0x4646818, order = 0x4646758, filesort_limit = 18446744073709551615ULL, select_limit = 18446744073709551615ULL, is_order_by = true), line 20072 in "sql_select.cc"
  [16] JOIN::exec(this = 0x4646818), line 3254 in "sql_select.cc"
  [17] mysql_select(thd = 0x45ea1f0, rref_pointer_array = 0x45ec610, tables = 0x46354f8, wild_num = 0, fields = CLASS, conds = 0x4646598, og_num = 1U, order = 0x4646758, group = (nil), having = (nil), proc_param = (nil), select_options = 2147748608ULL, result = 0x4637158, unit = 0x45ebdf0, select_lex = 0x45ec428), line 3498 in "sql_select.cc"
  [18] handle_select(thd = 0x45ea1f0, lex = 0x45ebd40, result = 0x4637158, setup_tables_done_option = 0), line 311 in "sql_select.cc"
  [19] execute_sqlcom_select(thd = 0x45ea1f0, all_tables = 0x46354f8), line 4493 in "sql_parse.cc"
  [20] mysql_execute_command(thd = 0x45ea1f0), line 2089 in "sql_parse.cc"
  [21] mysql_parse(thd = 0x45ea1f0, rawbuf = 0x4635180 "SELECT table2.pk AS field1\nFROM t2 AS table1\nLEFT JOIN t1 AS table2 ON table1.col_int_key = table2.col_int\nWHERE table2.col_int_key BETWEEN 5 AND 6 \nAND table2.pk IS NULL \nOR table2.pk IN ( 5 )\nORDER BY field1", length = 209U, parser_state = 0xfffffd7fff07da88), line 5537 in "sql_parse.cc"
  [22] dispatch_command(command = COM_QUERY, thd = 0x45ea1f0, packet = 0x462d131 "SELECT table2.pk AS field1\nFROM t2 AS table1\nLEFT JOIN t1 AS table2 ON table1.col_int_key = table2.col_int\nWHERE table2.col_int_key BETWEEN 5 AND 6 \nAND table2.pk IS NULL \nOR table2.pk IN ( 5 )\nORDER BY field1 ", packet_length = 210U), line 1075 in "sql_parse.cc"
  [23] do_command(thd = 0x45ea1f0), line 815 in "sql_parse.cc"
  [24] do_handle_one_connection(thd_arg = 0x45ea1f0), line 745 in "sql_connect.cc"
  [25] handle_one_connection(arg = 0x45ea1f0), line 684 in "sql_connect.cc"
  [26] pfs_spawn_thread(arg = 0x460bc30), line 1078 in "pfs.cc"
  [27] _thrp_setup(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff27acf5 
  [28] _lwp_start(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff27afb0 

Code where the assertion is hit (opt_range.h):

void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ }

How to repeat:
CREATE TABLE t1 (
  col_int INT,
  col_int_key INT,
  pk INT NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (pk),
  KEY col_int_key (col_int_key)
) ENGINE=InnoDB;

INSERT INTO t1 VALUES (-850788352,NULL,1);
INSERT INTO t1 VALUES (-1463156736,-1097990144,2);
INSERT INTO t1 VALUES (NULL,-1402404864,3);
INSERT INTO t1 VALUES (6,1660551168,4);
INSERT INTO t1 VALUES (5,2,5);
INSERT INTO t1 VALUES (NULL,8,6);
INSERT INTO t1 VALUES (-1320091648,7,7);
INSERT INTO t1 VALUES (3,5,8);
INSERT INTO t1 VALUES (NULL,1,9);
INSERT INTO t1 VALUES (6,1330774016,10);
INSERT INTO t1 VALUES (1650458624,NULL,11);
INSERT INTO t1 VALUES (8,NULL,12);
INSERT INTO t1 VALUES (1841758208,NULL,13);
INSERT INTO t1 VALUES (-874315776,-944570368,14);
INSERT INTO t1 VALUES (NULL,8,15);

CREATE TABLE t2 (
  pk INT NOT NULL AUTO_INCREMENT,
  col_int INT,
  col_int_key INT,
  PRIMARY KEY (pk),
  KEY col_int_key (col_int_key)
) ENGINE=InnoDB;

SELECT t1.pk AS field1
FROM t2
  LEFT JOIN t1 ON t2.col_int_key = t1.col_int
WHERE t1.col_int_key BETWEEN 5 AND 6 
AND t1.pk IS NULL 
OR t1.pk IN ( 5 )
ORDER BY field1 ;
[24 Nov 2010 13:25] John Embretsen
First observed with the RQG using outer_join.yy grammar with --seed=1290531120.

Note that if the query is modified slightly to use

WHERE t1.col_int_key = 5

instead of

WHERE t1.col_int_key BETWEEN 5 AND 6

we hit a different, but similar, assert in:

QUICK_ROR_UNION_SELECT::need_sorted_output(this = 0x4644f10), line 682 in "opt_range.h"
[24 Nov 2010 13:28] John Embretsen
There is a similar (closed) bug in the bug database:
Bug#49867 - Assertion failed - QUICK_ROR_INTERSECT_SELECT::need_sorted_output
[1 Dec 2010 11:46] Jørgen Løland
An interesting observation: With the offending line is commented out...

20011 else if (select && select->quick)
20012   /*select->quick->need_sorted_output();*/
20013 /*
20014    Restore condition only if we didn't chose index different to what we used
20015    for ICP.
20016  */

...we can get the execution plan for the query:

EXPLAIN SELECT t1.pk AS field1
FROM t2
LEFT JOIN t1 ON t2.col_int_key = t1.col_int
WHERE t1.col_int_key BETWEEN 5 AND 6 
AND t1.pk IS NULL 
OR t1.pk IN ( 5 )
ORDER BY field1 ;
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	t1	const	PRIMARY,col_int_key	PRIMARY	4	const	2	Using where
1	SIMPLE	t2	ref	col_int_key	col_int_key	5	test.t1.col_int	1	Using index

As can be seen in the EXPLAIN output, the quick select QUICK_INDEX_MERGE_SELECT is not used to access table t1 (which is the table that triggers the ASSERT). Instead, the PRIMARY key index is preferred.
[8 Dec 2010 9:59] 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/126298

3427 Jorgen Loland	2010-12-08
      BUG#58456 - Assertion 0 in QUICK_INDEX_MERGE_SELECT::need_sorted_output 
                  in opt_range.h
      
      In this bug, there are two alternative access plans: 
       * Index merge range access
       * Const ref access
      
      best_access_path() decided that the ref access was preferrable, 
      but make_join_select() still decided to point 
      SQL_SELECT::quick to the index merge because the table had 
      type==JT_CONST which was not handled. 
      
      At the same time the table's ref.key still referred to the 
      index the ref access would use indicating that ref access 
      should be used. In this state, different parts of the 
      optimizer code have different perceptions of which access path
      is in use (ref or range).
      
      test_if_skip_sort_order() was called to check if the ref access
      needed ordering, but test_if_skip_sort_order() got confused and
      requested the index merge to return records in sorted order. 
      Index merge cannot do this, and fired an ASSERT.
      
      The fix is to take join_tab->type==JT_CONST into concideration
      when make_join_select() decides whether or not to use the 
      range access method.
     @ mysql-test/r/join_outer_innodb.result
        Add test for BUG#58456
     @ mysql-test/t/join_outer_innodb.test
        Add test for BUG#58456
[16 Dec 2010 11:25] 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/127056

3203 Jorgen Loland	2010-12-16
      BUG#58456 - Assertion 0 in QUICK_INDEX_MERGE_SELECT::need_sorted_output 
                  in opt_range.h
      
      In this bug, there are two alternative access plans: 
       * Index merge range access
       * Const ref access
      
      best_access_path() decided that the ref access was preferrable, 
      but make_join_select() still decided to point 
      SQL_SELECT::quick to the index merge because the table had 
      type==JT_CONST which was not handled. 
      
      At the same time the table's ref.key still referred to the 
      index the ref access would use indicating that ref access 
      should be used. In this state, different parts of the 
      optimizer code have different perceptions of which access path
      is in use (ref or range).
      
      test_if_skip_sort_order() was called to check if the ref access
      needed ordering, but test_if_skip_sort_order() got confused and
      requested the index merge to return records in sorted order. 
      Index merge cannot do this, and fired an ASSERT.
      
      The fix is to take join_tab->type==JT_CONST into concideration
      when make_join_select() decides whether or not to use the 
      range access method.
     @ mysql-test/r/join_outer_innodb.result
        Add test for BUG#58456
     @ mysql-test/t/join_outer_innodb.test
        Add test for BUG#58456
[16 Dec 2010 14:12] 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/127082

3436 Jorgen Loland	2010-12-16 [merge]
      BUG#58456: Merge 5.5-bugteam -> trunk-bugfixing
[17 Dec 2010 7:01] Øystein Grøvlen
The fix for this bug seems to have introduced the regression reported in Bug#58985.
[17 Dec 2010 12:51] Bugs System
Pushed into mysql-5.5 5.5.9 (revid:georgi.kodinov@oracle.com-20101217124733-p1ivu6higouawv8l) (version source revid:georgi.kodinov@oracle.com-20101217111134-n5htzj2bnehvnv4w) (merge vers: 5.5.9) (pib:24)
[17 Dec 2010 12:55] Bugs System
Pushed into mysql-trunk 5.6.1 (revid:georgi.kodinov@oracle.com-20101217125013-y8pb3az32rtbplc9) (version source revid:georgi.kodinov@oracle.com-20101217112525-t71wcarh16fii9bz) (merge vers: 5.6.1) (pib:24)
[11 Jan 2011 16:07] Paul Dubois
Noted in 5.5.9 changelog.

An assertion could be raised for queries for which the optimizer
could choose between Index Merge range access or const ref access
methods.
[20 Jan 2011 9:10] Bugs System
Pushed into mysql-trunk 5.6.2 (revid:jorgen.loland@oracle.com-20110120090926-xms6k8scdrtl8yai) (version source revid:jorgen.loland@oracle.com-20110120090926-xms6k8scdrtl8yai) (merge vers: 5.6.2) (pib:24)