MariaDB

Elimination of a table results in an invalid execution plan

Bug #675118 reported by Philip Stoev on 2010-11-14

This bug affects 1 person

Affects		Status	Importance	Assigned to	Milestone
	MariaDB	Fix Released	Critical	Sergey Petrunia	MariaDB 5.1

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.

Tags:

Revision history for this message

Philip Stoev (pstoev-askmonty) wrote on 2010-11-14:

core and binary Edit (49.6 MiB, application/zip)

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

Revision history for this message

Philip Stoev (pstoev-askmonty) wrote on 2010-11-14:

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.

Sergei Golubchik (sergii) on 2010-11-30

Changed in maria:
milestone:	none → 5.3

Revision history for this message

Philip Stoev (philip-stoev) wrote on 2010-12-25: 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 ;

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

Revision history for this message

Igor Babaev (igorb-seattle) wrote on 2010-12-26:

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)

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

Changed in maria:
milestone:	5.3 → 5.1
importance:	Undecided → Critical
assignee:	Igor Babaev (igorb-seattle) → nobody

Philip Stoev (philip-stoev) on 2010-12-26

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)

Igor Babaev (igorb-seattle) on 2010-12-27

summary:

- table elimination does not adjust the nested join structure when
- eliminating tables
+ Elimination of a table results in an invalid execution plan

Sergey Petrunia (sergefp) on 2011-01-12

Changed in maria:
status:	Confirmed → Fix Committed

Daniel Bartholomew (dbart) on 2011-12-13

Changed in maria:
status:	Fix Committed → Fix Released

Report a bug

This report contains Public information

Everyone can see this information.

You are

Subscribing...

Edit bug mail

Other bug subscribers

Bug attachments

core and binary Edit

Add attachment

Remote bug watches

Bug watches keep track of this bug in other bug trackers.