[MDEV-3476] LP:675118 - Elimination of a table results in an invalid execution plan - JIRA

Details

Type: Bug
Status: Closed
Priority: Critical
Resolution: Fixed
Affects Version/s: None
Fix Version/s: None
Component/s: None
Labels:
- Launchpad

Description

The following unsimplified query:

SELECT table1 . `col_int_key` AS field1 FROM O AS table1 LEFT JOIN D AS table2 LEFT OUTER JOIN M AS table3 ON table2 . `col_varchar_10_utf8_key` = table3 . `col_varchar_10_latin1_key` LEFT JOIN C AS table4 ON table2 . `col_varchar_10_utf8_key` = table4 . `col_varchar_1024_utf8_key` ON table1 . `col_int_key` = table3 . `col_int_key` LEFT OUTER JOIN J AS table5 LEFT JOIN J AS table6 RIGHT JOIN K AS table7 ON table6 . `pk` = table7 . `col_int` ON table5 . `col_varchar_1024_latin1_key` = table7 . `col_varchar_10_utf8_key` ON table2 . `col_varchar_1024_latin1_key` = table7 . `col_varchar_10_utf8_key` WHERE ( ( table7 . `pk` <= 2 OR table2 . `col_int` <= table4 . `pk` ) AND table2 . `col_int_key` != 9 ) HAVING field1 >= 3

caused the following assertion:

mysqld: sql_join_cache.cc:2388: virtual enum_nested_loop_state JOIN_CACHE::join_null_complements(bool): Assertion `join_tab->first_inner' failed.

backtrace:

2010-11-13T22:05:09 #8 0x00a72d98 in __assert_fail () from /lib/libc.so.6
2010-11-13T22:05:09 #9 0x082de97b in JOIN_CACHE::join_null_complements (this=0x912682f0, skip_last=false) at sql_join_cache.cc:2388
2010-11-13T22:05:09 #10 0x082de2d5 in JOIN_CACHE::join_records (this=0x912682f0, skip_last=false) at sql_join_cache.cc:2001
2010-11-13T22:05:09 #11 0x082de311 in JOIN_CACHE::join_records (this=0x91267f78, skip_last=false) at sql_join_cache.cc:2013
2010-11-13T22:05:09 #12 0x08326019 in sub_select_cache (join=0x915132b0, join_tab=0x9155d788, end_of_records=true) at sql_select.cc:13234
2010-11-13T22:05:09 #13 0x08326232 in sub_select (join=0x915132b0, join_tab=0x9155d5b0, end_of_records=true) at sql_select.cc:13396
2010-11-13T22:05:09 #14 0x08326232 in sub_select (join=0x915132b0, join_tab=0x9155d3d8, end_of_records=true) at sql_select.cc:13396
2010-11-13T22:05:09 #15 0x0832584f in do_select (join=0x915132b0, fields=0xbb4f980, table=0x0, procedure=0x0) at sql_select.cc:12992
2010-11-13T22:05:09 #16 0x0830b21b in JOIN::exec (this=0x915132b0) at sql_select.cc:2392
2010-11-13T22:05:09 #17 0x0830b981 in mysql_select (thd=0xbb4df50, rref_pointer_array=0xbb4fa08, tables=0x91176a88, wild_num=0, fields=..., conds=0xa76c6360, og_num=0,
2010-11-13T22:05:09 order=0x0, group=0x0, having=0xa766f058, proc_param=0x0, select_options=2147764736, result=0x90f105d8, unit=0xbb4f63c, select_lex=0xbb4f8e0)
2010-11-13T22:05:09 at sql_select.cc:2602
2010-11-13T22:05:09 #18 0x08303ed1 in handle_select (thd=0xbb4df50, lex=0xbb4f5dc, result=0x90f105d8, setup_tables_done_option=0) at sql_select.cc:286
2010-11-13T22:05:09 #19 0x0829fcd7 in execute_sqlcom_select (thd=0xbb4df50, all_tables=0x91176a88) at sql_parse.cc:5102
2010-11-13T22:05:09 #20 0x082967d7 in mysql_execute_command (thd=0xbb4df50) at sql_parse.cc:2281
2010-11-13T22:05:09 #21 0x082a2248 in mysql_parse (thd=0xbb4df50,
2010-11-13T22:05:09 rawbuf=0xa7660c30 "SELECT table1 . `col_int_key` AS field1 FROM O AS table1 LEFT JOIN D AS table2 LEFT OUTER JOIN M AS table3 ON table2 . `col_varchar_10_utf8_key` = table3 . `col_varchar_10_latin1_key` LEFT JOIN C AS table4 ON table2 . `col_varchar_10_utf8_key` = table4 . `col_varchar_1024_utf8_key` ON table1 . `col_int_key` = table3 . `col_int_key` LEFT OUTER JOIN J AS table5 LEFT JOIN J AS table6 RIGHT JOIN K AS table7 ON table6 . `pk` = table7 . `col_int` ON table5 . `col_varchar_1024_latin1_key` = table7 . `col_varchar_10_utf8_key` ON table2 . `col_varchar_1024_latin1_key` = table7 . `col_varchar_10_utf8_key` WHERE ( ( table7 . `pk` <= 2 OR table2 . `col_int` <= table4 . `pk` ) AND table2 . `col_int_key` != 9 ) HAVING field1 >= 3",
2010-11-13T22:05:09 length=763, found_semicolon=0x916dd228) at sql_parse.cc:6109
2010-11-13T22:05:09 #22 0x08294344 in dispatch_command (command=COM_QUERY, thd=0xbb4df50, packet=0xbb542c9 "", packet_length=767) at sql_parse.cc:1209
2010-11-13T22:05:09 #23 0x082937f6 in do_command (thd=0xbb4df50) at sql_parse.cc:902
2010-11-13T22:05:09 #24 0x082907ac in handle_one_connection (arg=0xbb4df50) at sql_connect.cc:1154
2010-11-13T22:05:09 #25 0x00bea919 in start_thread () from /lib/libpthread.so.0
2010-11-13T22:05:09 #26 0x00b2ccbe in clone () from /lib/libc.so.6

bug is not reproducible with the original test case. Not reproducible with MyISAM or FOCE KEY.

Gliffy Diagrams

Attachments

Options
- Sort By Name
- Sort By Date
- Ascending
- Descending
- Thumbnails
- List
- Download All

Attachments

LPexportBug675118_var-bug675118.zip
49.57 MB
2010-11-14 09:17
LPexportBug675118.xml
25 kB
2012-10-03 11:32

Activity

Ascending order - Click to sort in descending order

Hide

Permalink

Philip Stoev added a comment - 2010-11-14 09:17

bzr version-info:

revision-id: <email address hidden>
date: 2010-11-13 07:47:43 -0800
build-date: 2010-11-14 11:03:28 +0200
revno: 2856
branch-nick: maria-5.3-mwl128

core and binary
LPexportBug675118_var-bug675118.zip

Show

Philip Stoev added a comment - 2010-11-14 09:17 bzr version-info: revision-id: <email address hidden> date: 2010-11-13 07:47:43 -0800 build-date: 2010-11-14 11:03:28 +0200 revno: 2856 branch-nick: maria-5.3-mwl128 core and binary LPexportBug675118_var-bug675118.zip

Hide

Permalink

Philip Stoev added a comment - 2010-11-14 09:17

Re: mysqld: sql_join_cache.cc:2388: virtual enum_nested_loop_state JOIN_CACHE::join_null_complements(bool): Assertion `join_tab->first_inner' failed in maria-5.3-mwl128
bzr version-info:

revision-id: igor@askmonty.org-20101113154743-nwdowwt4cycyyprl
date: 2010-11-13 07:47:43 -0800
build-date: 2010-11-14 11:03:28 +0200
revno: 2856
branch-nick: maria-5.3-mwl128

Show

Philip Stoev added a comment - 2010-11-14 09:17 Re: mysqld: sql_join_cache.cc:2388: virtual enum_nested_loop_state JOIN_CACHE::join_null_complements(bool): Assertion `join_tab->first_inner' failed in maria-5.3-mwl128 bzr version-info: revision-id: igor@askmonty.org-20101113154743-nwdowwt4cycyyprl date: 2010-11-13 07:47:43 -0800 build-date: 2010-11-14 11:03:28 +0200 revno: 2856 branch-nick: maria-5.3-mwl128

Hide

Permalink

Philip Stoev added a comment - 2010-11-14 12:19

Re: mysqld: sql_join_cache.cc:2388: virtual enum_nested_loop_state JOIN_CACHE::join_null_complements(bool): Assertion `join_tab->first_inner' failed in maria-5.3-mwl128
I was able to repeat this bug without HAVING, however it is very difficult to simplify. Once I have a presentable test case, I will assign it over to you.

Show

Philip Stoev added a comment - 2010-11-14 12:19 Re: mysqld: sql_join_cache.cc:2388: virtual enum_nested_loop_state JOIN_CACHE::join_null_complements(bool): Assertion `join_tab->first_inner' failed in maria-5.3-mwl128 I was able to repeat this bug without HAVING, however it is very difficult to simplify. Once I have a presentable test case, I will assign it over to you.

Hide

Permalink

Philip Stoev added a comment - 2010-12-25 16:16

Re: mysqld: sql_join_cache.cc:2388: virtual enum_nested_loop_state JOIN_CACHE::join_null_complements(bool): Assertion `join_tab->first_inner' failed with join_cache_level=4, outer_join_with_cache=on
Test case that works against maria-5.3

SET SESSION join_cache_level = 4;
SET SESSION optimizer_switch = 'outer_join_with_cache=on';

CREATE TABLE t2 (f4 varchar(1024), KEY (f4)) ;
INSERT IGNORE INTO t2 VALUES ('xcddwntkbxyorzdv'),('cnxxcddwntkbxyor'),('r'),('r'),('did'),('I'),('when'),('hczkfqjeggivdvac'),('e'),('okay'),('up');

CREATE TABLE t4 (f1 int(11), f3 varchar(10)) ;
INSERT IGNORE INTO t4 VALUES ('8','n'),('9','nwzcerzsgx'),('10','c');

CREATE TABLE t3 (f4 varchar(1024), f1 int(11), f2 int(11)) ;
INSERT IGNORE INTO t3 VALUES ('f','4','0'),('n','5','-996540416');

CREATE TABLE t1 (f1 int(11), PRIMARY KEY (f1)) ;
CREATE TABLE t5 (f5 int(11), KEY (f5)) ;

SELECT alias2.f2
FROM t2 AS alias1
LEFT JOIN t3 AS alias2
LEFT JOIN t4 AS alias3
LEFT JOIN t1 AS alias4 ON alias3.f1 = alias4.f1
JOIN t5 AS alias5
ON alias3.f3 ON alias2.f1 = alias5.f5 ON alias1.f4 = alias2.f4
WHERE alias2.f2 ;

Show

Philip Stoev added a comment - 2010-12-25 16:16 Re: mysqld: sql_join_cache.cc:2388: virtual enum_nested_loop_state JOIN_CACHE::join_null_complements(bool): Assertion `join_tab->first_inner' failed with join_cache_level=4, outer_join_with_cache=on Test case that works against maria-5.3 SET SESSION join_cache_level = 4; SET SESSION optimizer_switch = 'outer_join_with_cache=on'; CREATE TABLE t2 (f4 varchar(1024), KEY (f4)) ; INSERT IGNORE INTO t2 VALUES ('xcddwntkbxyorzdv'),('cnxxcddwntkbxyor'),('r'),('r'),('did'),('I'),('when'),('hczkfqjeggivdvac'),('e'),('okay'),('up'); CREATE TABLE t4 (f1 int(11), f3 varchar(10)) ; INSERT IGNORE INTO t4 VALUES ('8','n'),('9','nwzcerzsgx'),('10','c'); CREATE TABLE t3 (f4 varchar(1024), f1 int(11), f2 int(11)) ; INSERT IGNORE INTO t3 VALUES ('f','4','0'),('n','5','-996540416'); CREATE TABLE t1 (f1 int(11), PRIMARY KEY (f1)) ; CREATE TABLE t5 (f5 int(11), KEY (f5)) ; SELECT alias2.f2 FROM t2 AS alias1 LEFT JOIN t3 AS alias2 LEFT JOIN t4 AS alias3 LEFT JOIN t1 AS alias4 ON alias3.f1 = alias4.f1 JOIN t5 AS alias5 ON alias3.f3 ON alias2.f1 = alias5.f5 ON alias1.f4 = alias2.f4 WHERE alias2.f2 ;

Hide

Permalink

Igor Babaev added a comment - 2010-12-26 09:41

Re: mysqld: sql_join_cache.cc:2388: virtual enum_nested_loop_state JOIN_CACHE::join_null_complements(bool): Assertion `join_tab->first_inner' failed with join_cache_level=4, outer_join_with_cache=on
I investigated this problem. It happens because the optimizer generates a plan with outer tables
interleaving inner tables of an outer join. The problem is reproducible in 5.1 as well:

MariaDB [test]> CREATE TABLE t2 (f4 varchar(1024), KEY (f4)) ;
Query OK, 0 rows affected, 1 warning (0.02 sec)

MariaDB [test]> INSERT IGNORE INTO t2 VALUES ('xcddwntkbxyorzdv'),('cnxxcddwntkbxyor'),('r'),('r'),('did'),('I'),('when'),('hczkfqjeggivdvac'),('e'),('okay'),('up');
Query OK, 11 rows affected (0.00 sec)
Records: 11 Duplicates: 0 Warnings: 0

MariaDB [test]>
MariaDB [test]> CREATE TABLE t4 (f1 int(11), f3 varchar(10)) ;
Query OK, 0 rows affected (0.01 sec)

MariaDB [test]> INSERT IGNORE INTO t4 VALUES ('8','n'),('9','nwzcerzsgx'),('10','c');
Query OK, 3 rows affected (0.00 sec)
Records: 3 Duplicates: 0 Warnings: 0

MariaDB [test]> CREATE TABLE t3 (f4 varchar(1024), f1 int(11), f2 int(11)) ;
Query OK, 0 rows affected (0.01 sec)

MariaDB [test]> INSERT IGNORE INTO t3 VALUES ('f','4','0'),('n','5','-996540416');
Query OK, 2 rows affected (0.00 sec)
Records: 2 Duplicates: 0 Warnings: 0

MariaDB [test]>
MariaDB [test]> CREATE TABLE t1 (f1 int(11), PRIMARY KEY (f1)) ;
Query OK, 0 rows affected (0.01 sec)

MariaDB [test]> CREATE TABLE t5 (f5 int(11), KEY (f5)) ;
Query OK, 0 rows affected (0.01 sec)

MariaDB [test]> EXPLAIN EXTENDED
-> SELECT alias2.f2
-> FROM t2 AS alias1
-> LEFT JOIN t3 AS alias2
-> LEFT JOIN t4 AS alias3
-> LEFT JOIN t1 AS alias4 ON alias3.f1 = alias4.f1
-> JOIN t5 AS alias5
-> ON alias3.f3 ON alias2.f1 = alias5.f5 ON alias1.f4 = alias2.f4
-> WHERE alias2.f2 ;
--------------------------------------------------------------------------------------

id

select_type

table

type

possible_keys

key

key_len

ref

rows

filtered

Extra

--------------------------------------------------------------------------------------

1	SIMPLE	alias2	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
1	SIMPLE	alias5	ref	f5	f5	5	test.alias2.f1	2	100.00	Using index
1	SIMPLE	alias1	ref	f4	f4	1003	test.alias2.f4	2	100.00	Using where
1	SIMPLE	alias3	ALL	NULL	NULL	NULL	NULL	3	100.00

--------------------------------------------------------------------------------------
4 rows in set, 1 warning (0.00 sec)

MariaDB [test]> SHOW WARNINGS;
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Level

Code

Message

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Note

1003

select `test`.`alias2`.`f2` AS `f2` from `test`.`t2` `alias1` join `test`.`t3` `alias2` left join (`test`.`t4` `alias3` join `test`.`t5` `alias5`) on((`test`.`alias3`.`f3` and (`test`.`alias5`.`f5` = `test`.`alias2`.`f1`))) where ((`test`.`alias1`.`f4` = `test`.`alias2`.`f4`) and `test`.`alias2`.`f2`)

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

If we turn table elimination off the the plan becomes non-interleaving:

MariaDB [test]> set optimizer_switch='table_elimination=off';
Query OK, 0 rows affected (0.00 sec)

MariaDB [test]> EXPLAIN EXTENDED SELECT alias2.f2 FROM t2 AS alias1 LEFT JOIN t3 AS alias2 LEFT JOIN t4 AS alias3 LEFT JOIN t1 AS alias4 ON alias3.f1 = alias4.f1 JOIN t5 AS alias5 ON alias3.f3 ON alias2.f1 = alias5.f5 ON alias1.f4 = alias2.f4 WHERE alias2.f2;
--------------------------------------------------------------------------------------------------------------

id

select_type

table

type

possible_keys

key

key_len

ref

rows

filtered

Extra

--------------------------------------------------------------------------------------------------------------

1	SIMPLE	alias2	ALL	NULL	NULL	NULL	NULL	2	100.00	Using where
1	SIMPLE	alias5	ref	f5	f5	5	test.alias2.f1	2	100.00	Using index
1	SIMPLE	alias3	ALL	NULL	NULL	NULL	NULL	3	100.00
1	SIMPLE	alias4	eq_ref	PRIMARY	PRIMARY	4	test.alias3.f1	1	100.00	Using index
1	SIMPLE	alias1	ALL	f4	NULL	NULL	NULL	11	81.82	Using where; Using join buffer

--------------------------------------------------------------------------------------------------------------
5 rows in set, 1 warning (0.00 sec)

The cause of the problem is the current code for the table elimination. It does not adjust the nested join structure
when eliminating tables. At the same time the functions that build auxiliary bitmaps to check interleaving use this structure.

Show

Igor Babaev added a comment - 2010-12-26 09:41 Re: mysqld: sql_join_cache.cc:2388: virtual enum_nested_loop_state JOIN_CACHE::join_null_complements(bool): Assertion `join_tab->first_inner' failed with join_cache_level=4, outer_join_with_cache=on I investigated this problem. It happens because the optimizer generates a plan with outer tables interleaving inner tables of an outer join. The problem is reproducible in 5.1 as well: MariaDB [test] > CREATE TABLE t2 (f4 varchar(1024), KEY (f4)) ; Query OK, 0 rows affected, 1 warning (0.02 sec) MariaDB [test] > INSERT IGNORE INTO t2 VALUES ('xcddwntkbxyorzdv'),('cnxxcddwntkbxyor'),('r'),('r'),('did'),('I'),('when'),('hczkfqjeggivdvac'),('e'),('okay'),('up'); Query OK, 11 rows affected (0.00 sec) Records: 11 Duplicates: 0 Warnings: 0 MariaDB [test] > MariaDB [test] > CREATE TABLE t4 (f1 int(11), f3 varchar(10)) ; Query OK, 0 rows affected (0.01 sec) MariaDB [test] > INSERT IGNORE INTO t4 VALUES ('8','n'),('9','nwzcerzsgx'),('10','c'); Query OK, 3 rows affected (0.00 sec) Records: 3 Duplicates: 0 Warnings: 0 MariaDB [test] > CREATE TABLE t3 (f4 varchar(1024), f1 int(11), f2 int(11)) ; Query OK, 0 rows affected (0.01 sec) MariaDB [test] > INSERT IGNORE INTO t3 VALUES ('f','4','0'),('n','5','-996540416'); Query OK, 2 rows affected (0.00 sec) Records: 2 Duplicates: 0 Warnings: 0 MariaDB [test] > MariaDB [test] > CREATE TABLE t1 (f1 int(11), PRIMARY KEY (f1)) ; Query OK, 0 rows affected (0.01 sec) MariaDB [test] > CREATE TABLE t5 (f5 int(11), KEY (f5)) ; Query OK, 0 rows affected (0.01 sec) MariaDB [test] > EXPLAIN EXTENDED -> SELECT alias2.f2 -> FROM t2 AS alias1 -> LEFT JOIN t3 AS alias2 -> LEFT JOIN t4 AS alias3 -> LEFT JOIN t1 AS alias4 ON alias3.f1 = alias4.f1 -> JOIN t5 AS alias5 -> ON alias3.f3 ON alias2.f1 = alias5.f5 ON alias1.f4 = alias2.f4 -> WHERE alias2.f2 ; --- ----------- ------ ---- ------------- ---- ------- -------------- ---- -------- ------------ id select_type table type possible_keys key key_len ref rows filtered Extra --- ----------- ------ ---- ------------- ---- ------- -------------- ---- -------- ------------ 1 SIMPLE alias2 ALL NULL NULL NULL NULL 2 100.00 Using where 1 SIMPLE alias5 ref f5 f5 5 test.alias2.f1 2 100.00 Using index 1 SIMPLE alias1 ref f4 f4 1003 test.alias2.f4 2 100.00 Using where 1 SIMPLE alias3 ALL NULL NULL NULL NULL 3 100.00 --- ----------- ------ ---- ------------- ---- ------- -------------- ---- -------- ------------ 4 rows in set, 1 warning (0.00 sec) MariaDB [test] > SHOW WARNINGS; ------ ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Level Code Message ------ ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Note 1003 select `test`.`alias2`.`f2` AS `f2` from `test`.`t2` `alias1` join `test`.`t3` `alias2` left join (`test`.`t4` `alias3` join `test`.`t5` `alias5`) on((`test`.`alias3`.`f3` and (`test`.`alias5`.`f5` = `test`.`alias2`.`f1`))) where ((`test`.`alias1`.`f4` = `test`.`alias2`.`f4`) and `test`.`alias2`.`f2`) ------ ---- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- If we turn table elimination off the the plan becomes non-interleaving: MariaDB [test] > set optimizer_switch='table_elimination=off'; Query OK, 0 rows affected (0.00 sec) MariaDB [test] > EXPLAIN EXTENDED SELECT alias2.f2 FROM t2 AS alias1 LEFT JOIN t3 AS alias2 LEFT JOIN t4 AS alias3 LEFT JOIN t1 AS alias4 ON alias3.f1 = alias4.f1 JOIN t5 AS alias5 ON alias3.f3 ON alias2.f1 = alias5.f5 ON alias1.f4 = alias2.f4 WHERE alias2.f2; --- ----------- ------ ------ ------------- ------- ------- -------------- ---- -------- ------------------------------- id select_type table type possible_keys key key_len ref rows filtered Extra --- ----------- ------ ------ ------------- ------- ------- -------------- ---- -------- ------------------------------- 1 SIMPLE alias2 ALL NULL NULL NULL NULL 2 100.00 Using where 1 SIMPLE alias5 ref f5 f5 5 test.alias2.f1 2 100.00 Using index 1 SIMPLE alias3 ALL NULL NULL NULL NULL 3 100.00 1 SIMPLE alias4 eq_ref PRIMARY PRIMARY 4 test.alias3.f1 1 100.00 Using index 1 SIMPLE alias1 ALL f4 NULL NULL NULL 11 81.82 Using where; Using join buffer --- ----------- ------ ------ ------------- ------- ------- -------------- ---- -------- ------------------------------- 5 rows in set, 1 warning (0.00 sec) The cause of the problem is the current code for the table elimination. It does not adjust the nested join structure when eliminating tables. At the same time the functions that build auxiliary bitmaps to check interleaving use this structure.

Hide

Permalink

Rasmus Johansson added a comment - 2011-12-13 15:18

Launchpad bug id: 675118

Show

Rasmus Johansson added a comment - 2011-12-13 15:18 Launchpad bug id: 675118

LP:675118 - Elimination of a table results in an invalid execution plan

Details

Description

Gliffy Diagrams

Attachments

Attachments

Activity

People

Dates

Agile