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

[MDEV-3476] LP:675118 - Elimination of a table results in an invalid execution plan Created: 2010-11-14 Updated: 2015-02-02 Resolved: 2012-10-04
Status:	Closed
Project:	MariaDB Server
Component/s:	None
Affects Version/s:	None
Fix Version/s:	None

Type:

Bug

Priority:

Critical

Reporter:

Philip Stoev (Inactive)

Assignee:

Sergei Petrunia

Resolution:

Fixed

Votes:

Labels:

Launchpad

Attachments:

LPexportBug675118.xml

LPexportBug675118_var-bug675118.zip

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.

Comments

Comment by Philip Stoev (Inactive) [ 2010-11-14 ]

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

Comment by Philip Stoev (Inactive) [ 2010-11-14 ]

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

Comment by Philip Stoev (Inactive) [ 2010-11-14 ]

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.

Comment by Philip Stoev (Inactive) [ 2010-12-25 ]

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 ;

Comment by Igor Babaev [ 2010-12-26 ]

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 ;
--------------------------------------------------------------------------------------

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;
--------------------------------------------------------------------------------------------------------------

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.

Comment by Rasmus Johansson (Inactive) [ 2011-12-13 ]

Launchpad bug id: 675118

Generated at Thu Feb 08 06:48:55 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.

[MDEV-3476] LP:675118 - Elimination of a table results in an invalid execution plan Created: 2010-11-14 Updated: 2015-02-02 Resolved: 2012-10-04