Elimination of a table results in an invalid execution plan

Bug #675118 reported by Philip Stoev on 2010-11-14
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
MariaDB
Fix Released
Critical
Sergey Petrunia

Bug 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.

Philip Stoev (pstoev-askmonty) wrote :

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

Philip Stoev (pstoev-askmonty) wrote :

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.

Changed in maria:
milestone: none → 5.3

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 ;

summary: 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
+ `join_tab->first_inner' failed with join_cache_level=4,
+ outer_join_with_cache=on
Changed in maria:
assignee: nobody → Igor Babaev (igorb-seattle)
status: New → Confirmed
Igor Babaev (igorb-seattle) wrote :
Download full text (6.1 KiB)

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

Read more...

Changed in maria:
milestone: 5.3 → 5.1
importance: Undecided → Critical
assignee: Igor Babaev (igorb-seattle) → nobody
summary: - 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
+ table elimination does not adjust the nested join structure when
+ eliminating tables
Changed in maria:
assignee: nobody → Sergey Petrunia (sergefp)
summary: - table elimination does not adjust the nested join structure when
- eliminating tables
+ Elimination of a table results in an invalid execution plan
Changed in maria:
status: Confirmed → Fix Committed
Changed in maria:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers

Bug attachments