MySQL Bugs: #54102: wrong result (or crash with join buffering) with STRAIGHT JOIN + RIGHT JOIN

Bug #54102	wrong result (or crash with join buffering) with STRAIGHT JOIN + RIGHT JOIN
Submitted:	31 May 2010 10:06	Modified:	3 Jun 2010 20:48
Reporter:	John Embretsen	Email Updates:
Status:	Duplicate	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S1 (Critical)
Version:	bzr_next-mr-opt-backporting, 6.0.14	OS:	Any
Assigned to:	Assigned Account	CPU Architecture:	Any

Description:
With optimizer_join_cache_level=8 (or 4) the following assertion was hit:

Assertion failed: cache, file sql/sql_join_cache.cc, line 1892

This issue exhibits the same symptoms as Bug#52540, except that the repro is different and both join_cache_levels 4 and 8 are vulnerable.
InnoDB storage engine is required.

Query:

SELECT STRAIGHT_JOIN 
  table1 .`col_varchar_10_utf8`
FROM F table1  
  RIGHT  JOIN I table2  
    LEFT  JOIN E table3  
      JOIN K  ON table3 .`col_varchar_1024_utf8_key`  
    ON table3 .`col_int_key`  
  ON table1 .`pk`  = table2 .`col_int_key`   
;

Removing STRAIGHT JOIN makes the issue go away.
Using a join_cache_level different from 4 or 8 makes the issue go away.

Backtrace:

---- called from signal handler with signal 6 (SIGABRT) ------
  [8] _lwp_kill(0xd, 0x6, 0xffffff02d9fe93e0, 0x5, 0x0, 0x20), at 0xfffffd7fff2842aa 
  [9] thr_kill(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff2788cd 
  [10] raise(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff227511 
  [11] abort(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff1fd9c5 
  [12] _assert(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff1fdc95 
  [13] JOIN_CACHE::set_match_flag_if_none(this = 0x657e4b0, first_inner = 0x655d220, rec_ptr = 0x6580490 "úÿ^Aÿ^Aøÿ^Aÿ^A^A"), line 1892 in "sql_join_cache.cc"
  [14] JOIN_CACHE::check_match(this = 0x657e4b0, rec_ptr = 0x6580490 "úÿ^Aÿ^Aøÿ^Aÿ^A^A"), line 1994 in "sql_join_cache.cc"
  [15] JOIN_CACHE::generate_full_extensions(this = 0x657e4b0, rec_ptr = 0x6580490 "úÿ^Aÿ^Aøÿ^Aÿ^A^A"), line 1930 in "sql_join_cache.cc"
  [16] JOIN_CACHE_BNL::join_matching_records(this = 0x657e4b0, skip_last = false), line 1829 in "sql_join_cache.cc"
  [17] JOIN_CACHE::join_records(this = 0x657e4b0, skip_last = false), line 1637 in "sql_join_cache.cc"
  [18] sub_select_cache(join = 0x652a790, join_tab = 0x655d780, end_of_records = true), line 16540 in "sql_select.cc"
  [19] sub_select(join = 0x652a790, join_tab = 0x655d4d0, end_of_records = true), line 16709 in "sql_select.cc"
  [20] sub_select(join = 0x652a790, join_tab = 0x655d220, end_of_records = true), line 16709 in "sql_select.cc"
  [21] sub_select_cache(join = 0x652a790, join_tab = 0x655d220, end_of_records = true), line 16542 in "sql_select.cc"
  [22] sub_select(join = 0x652a790, join_tab = 0x655cf70, end_of_records = true), line 16709 in "sql_select.cc"
  [23] do_select(join = 0x652a790, fields = 0x64c0fe0, table = (nil), procedure = (nil)), line 16295 in "sql_select.cc"
  [24] JOIN::exec(this = 0x652a790), line 3055 in "sql_select.cc"
  [25] mysql_select(thd = 0x64bf080, rref_pointer_array = 0x64c10c0, tables = 0x6508850, wild_num = 0, fields = CLASS, conds = (nil), og_num = 0, order = (nil), group = (nil), having = (nil), proc_param = (nil), select_options = 2147748610ULL, result = 0x65278d8, unit = 0x64c08b8, select_lex = 0x64c0ed8), line 3251 in "sql_select.cc"
  [26] handle_select(thd = 0x64bf080, lex = 0x64c0810, result = 0x65278d8, setup_tables_done_option = 0), line 301 in "sql_select.cc"
  [27] execute_sqlcom_select(thd = 0x64bf080, all_tables = 0x6508850), line 4779 in "sql_parse.cc"
  [28] mysql_execute_command(thd = 0x64bf080), line 2260 in "sql_parse.cc"
  [29] mysql_parse(thd = 0x64bf080, inBuf = 0x6508470 "SELECT  \nSTRAIGHT_JOIN \ntable1 .`col_varchar_10_utf8`\nFROM F table1  \nRIGHT  JOIN I table2  \nLEFT  JOIN E table3  \nJOIN K  ON table3 .`col_varchar_1024_utf8_key`  \nON table3 .`col_int_key`  \nON table1 .`pk`  = table2 .`col_int_key`", length = 231U, parser_state = 0xfffffd7fff06da58), line 5808 in "sql_parse.cc"
  [30] dispatch_command(command = COM_QUERY, thd = 0x64bf080, packet = 0x6500421 "", packet_length = 235U), line 1085 in "sql_parse.cc"
  [31] do_command(thd = 0x64bf080), line 771 in "sql_parse.cc"
  [32] do_handle_one_connection(thd_arg = 0x64bf080), line 1188 in "sql_connect.cc"
  [33] handle_one_connection(arg = 0x64bf080), line 1127 in "sql_connect.cc"
  [34] pfs_spawn_thread(arg = 0x6557f90), line 1011 in "pfs.cc"
  [35] _thrp_setup(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff27acf5 
  [36] _lwp_start(0x0, 0x0, 0x0, 0x0, 0x0, 0x0), at 0xfffffd7fff27afb0 

How to repeat:
The following is a repro based on data generated by the Random Query Generator:

SET SESSION optimizer_join_cache_level = 8;

DROP TABLE /*! IF EXISTS */ F;
DROP TABLE /*! IF EXISTS */ K;
DROP TABLE /*! IF EXISTS */ I;
DROP TABLE /*! IF EXISTS */ E;

CREATE TABLE `F` (
  `col_varchar_10_utf8` varchar(10) CHARACTER SET utf8 DEFAULT NULL,
  `col_int_key` int(11) DEFAULT NULL,
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (`pk`),
  KEY `test_idx` (`col_int_key`,`pk`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=latin1;

CREATE TABLE `K` (
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_varchar_1024_utf8_key` varchar(1024) CHARACTER SET utf8 DEFAULT NULL,
  `col_int_key` int(11) DEFAULT NULL,
  `col_varchar_10_utf8` varchar(10) CHARACTER SET utf8 DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `col_int_key` (`col_int_key`)
) ENGINE=MyISAM AUTO_INCREMENT=51 DEFAULT CHARSET=latin1;

INSERT INTO `K` VALUES (1,'in',44826624,'that\'s');

CREATE TABLE `I` (
  `col_varchar_10_utf8` varchar(10) CHARACTER SET utf8 DEFAULT NULL,
  `col_int_key` int(11) DEFAULT NULL,
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_varchar_1024_utf8_key` varchar(1024) CHARACTER SET utf8 DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `col_varchar_1024_utf8_key` (`col_varchar_1024_utf8_key`(333))
) ENGINE=MyISAM AUTO_INCREMENT=26 DEFAULT CHARSET=latin1;

INSERT INTO `I` VALUES ('ZMUDM',NULL,1,'test');
INSERT INTO `I` VALUES ('ANOYH',1,25,'m');

CREATE TABLE `E` (
  `col_varchar_10_utf8` varchar(10) CHARACTER SET utf8 DEFAULT NULL,
  `col_varchar_1024_utf8_key` varchar(1024) CHARACTER SET utf8 DEFAULT NULL,
  `pk` int(11) NOT NULL AUTO_INCREMENT,
  `col_int_key` int(11) DEFAULT NULL,
  PRIMARY KEY (`pk`),
  KEY `col_int_key` (`col_int_key`)
) ENGINE=MyISAM AUTO_INCREMENT=11 DEFAULT CHARSET=latin1;

INSERT INTO `E` VALUES ('WUXKP','e',10,-1584529408);
 
SELECT  
  STRAIGHT_JOIN 
  table1 .`col_varchar_10_utf8`
FROM F table1  
  RIGHT  JOIN I table2  
    LEFT  JOIN E table3  
      JOIN K  ON table3 .`col_varchar_1024_utf8_key`  
    ON table3 .`col_int_key`  
  ON table1 .`pk`  = table2 .`col_int_key`   
;

DROP TABLE F;
DROP TABLE K;
DROP TABLE I;
DROP TABLE E;

Comments on the testcase:
- semijoin=off doesn't matter
- crash occurs with join_cache_level=4,6,8

The root problem is that optimizer, only in the STRAIGHT_JOIN case, fails to detect that the plan requested by the user is impossible to execute. This causes 'join buffering' code to crash, but after changing a bit the tables' content, we can see wrong results even without any join buffering.
Testcase for wrong results (and assertion failure if optimizer_join_cache_level=4,6,8):

CREATE TABLE t1 (a int) ;
INSERT INTO t1 VALUES (1);
INSERT INTO t1 VALUES (36);

CREATE TABLE t2 (a varchar(1024), b int) ;
INSERT INTO t2 VALUES ('e', -1584529408);

CREATE TABLE t3 (pk int PRIMARY KEY) ;
INSERT INTO t3 VALUES(1);

CREATE TABLE t4 (a int) ;
INSERT INTO t4 VALUES (1);

explain SELECT STRAIGHT_JOIN t3.pk FROM
t3
RIGHT JOIN
(
  t1
  LEFT  JOIN
  (
     t2
     JOIN
     t4
     ON t2.a
  )
  ON t2.b
)
ON t3.pk  = t1.a
;

SELECT STRAIGHT_JOIN t3.pk FROM
t3
RIGHT JOIN
(
  t1
  LEFT  JOIN
  (
     t2
     JOIN
     t4
     ON t2.a
  )
  ON t2.b
)
ON t3.pk  = t1.a
;

SELECT t3.pk FROM
t3
RIGHT JOIN
(
  t1
  LEFT  JOIN
  (
     t2
     JOIN
     t4
     ON t2.a
  )
  ON t2.b
)
ON t3.pk  = t1.a
;

DROP TABLE t1,t2,t3,t4;

The first SELECT shows:
NULL
NULL
and the second SELECT shows correctly
1
NULL.

This BUG#54102 is a duplicate of BUG#52005. The synopsis of the latter corresponds very well STRAIGHT_JOIN, RIGHT JOIN, wrong order), and applying the patch for BUG#52005 makes the testcase for BUG#54102 give correct results and no crash. The patch for BUG#52005 isn't yet merged from 5.1-bugteam to next-mr-opt-backporting.
I will leave BUG#54102 assigned to me, and when the patch for BUG#52005 has been merged I will add the testcase of BUG#54102 and close the bug.

It is safe on my TODO to add the testcase once fix is merged.