| Bug #51762 | Infinite loop when optimizing query | ||
|---|---|---|---|
| Submitted: | 5 Mar 2010 10:04 | Modified: | 6 Mar 2010 7:11 |
| Reporter: | Ole John Aske | Email Updates: | |
| Status: | Not a Bug | Impact on me: | |
| Category: | MySQL Server: Optimizer | Severity: | S2 (Serious) |
| Version: | 5.1.41,next-mr | OS: | Any |
| Assigned to: | CPU Architecture: | Any | |
[5 Mar 2010 10:05]
Ole John Aske
mysqldump of test database
Attachment: dump.sql (text/x-sql), 139.14 KiB.
[5 Mar 2010 10:14]
Ole John Aske
This insanely large query was produced by RQG using the 'outer_join' grammar. Even though it might not be considered to be a relevant query, it seriously affects the testability of the server as it will cause RQG tests to stop after a few 1.000 queries.
[5 Mar 2010 13:48]
Valeriy Kravchuk
I was NOT able to repeat this hand with recent 5.1.45 from bzr and MyISAM engine instead of ndbcluster for the tables:
openxs@suse:/home2/openxs/dbs/5.1> bin/mysql -uroot spj_ndb
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A
Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 5
Server version: 5.1.45-debug Source distribution
Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.
mysql> explain SELECT COUNT( table1 . `pk` ) AS field1 FROM CC AS table1 RIGHT JOIN C AS table2 ON table1 . `pk` = table2 . `int_key` RIGHT JOIN CC AS table3 ON table2 . `pk` = table3 . `int_key` LEFT OUTER JOIN C AS table4 RIGHT JOIN C AS table5 ON table4 . `int_key` = table5 . `pk` ON table2 . `int_key` = table4 . `int_key` LEFT JOIN CC AS table6 LEFT OUTER JOIN D AS table7 RIGHT JOIN C AS table8 ON table7 . `pk` = table8 . `pk` ON table6 . `pk` = table7 . `pk` ON table5 . `pk` = table8 . `int_key` LEFT JOIN CC AS table9 LEFT JOIN BB AS table10 ON table9 . `int_key` = table10 . `int_key` ON table3 . `pk` = table9 . `int_key` RIGHT JOIN CC AS table11 LEFT JOIN C AS table12 ON table11 . `pk` = table12 . `int_key` ON table5 . `int_key` = table12 . `int_key` LEFT JOIN C AS table13 ON table6 . `pk` = table13 . `int_key` LEFT JOIN C AS table14 RIGHT OUTER JOIN C AS table15 ON table14 . `int_key` = table15 . `int_key` LEFT JOIN CC AS table16 LEFT JOIN CC AS table17 ON table16 . `int_key` = table17 . `pk` LEFT JOIN C AS table18 ON table17 . `int_key` = table18 . `pk` ON table15 . `int_key` = table17 . `pk` ON table12 . `int_key` = table16 . `pk` WHERE table14 . `pk` >= table7 . `int_nokey` HAVING (field1 <= 9 OR field1 <> 1) ORDER BY field1 DESC;
+----+-------------+---------+--------+-----------------+---------+---------+-------------------------+------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+---------+--------+-----------------+---------+---------+-------------------------+------+--------------------------+
| 1 | SIMPLE | table2 | ALL | PRIMARY,int_key | NULL | NULL | NULL | 20 | Using temporary |
| 1 | SIMPLE | table1 | eq_ref | PRIMARY | PRIMARY | 4 | spj_ndb.table2.int_key | 1 | Using index |
| 1 | SIMPLE | table3 | ref | int_key | int_key | 5 | spj_ndb.table2.pk | 1 | Using where |
| 1 | SIMPLE | table5 | eq_ref | PRIMARY,int_key | PRIMARY | 4 | spj_ndb.table2.int_key | 1 | Using where |
| 1 | SIMPLE | table9 | ref | int_key | int_key | 5 | spj_ndb.table3.pk | 1 | Using index |
| 1 | SIMPLE | table10 | ref | int_key | int_key | 5 | spj_ndb.table3.pk | 1 | Using index |
| 1 | SIMPLE | table8 | ref | PRIMARY,int_key | int_key | 5 | spj_ndb.table2.int_key | 2 | Using where |
| 1 | SIMPLE | table6 | eq_ref | PRIMARY | PRIMARY | 4 | spj_ndb.table8.pk | 1 | Using where; Using index |
| 1 | SIMPLE | table11 | eq_ref | PRIMARY | PRIMARY | 4 | spj_ndb.table5.int_key | 1 | Using index |
| 1 | SIMPLE | table16 | eq_ref | PRIMARY,int_key | PRIMARY | 4 | spj_ndb.table11.pk | 1 | Using where |
| 1 | SIMPLE | table17 | eq_ref | PRIMARY | PRIMARY | 4 | spj_ndb.table16.int_key | 1 | Using where |
| 1 | SIMPLE | table14 | ref | PRIMARY,int_key | int_key | 5 | spj_ndb.table16.int_key | 2 | Using where |
| 1 | SIMPLE | table13 | ref | int_key | int_key | 5 | spj_ndb.table6.pk | 2 | Using index |
| 1 | SIMPLE | table15 | ref | int_key | int_key | 5 | spj_ndb.table16.int_key | 2 | Using where; Using index |
| 1 | SIMPLE | table4 | ref | int_key | int_key | 5 | spj_ndb.table5.pk | 2 | Using where; Using index |
| 1 | SIMPLE | table12 | ref | int_key | int_key | 5 | spj_ndb.table16.pk | 2 | Using where; Using index |
| 1 | SIMPLE | table18 | eq_ref | PRIMARY | PRIMARY | 4 | spj_ndb.table17.int_key | 1 | Using index |
| 1 | SIMPLE | table7 | eq_ref | PRIMARY | PRIMARY | 4 | spj_ndb.table8.pk | 1 | Using where |
+----+-------------+---------+--------+-----------------+---------+---------+-------------------------+------+--------------------------+
18 rows in set (29.13 sec)
mysql> show create table C\G
*************************** 1. row ***************************
Table: C
Create Table: CREATE TABLE `C` (
`pk` int(11) NOT NULL AUTO_INCREMENT,
`int_nokey` int(11) DEFAULT NULL,
`int_key` int(11) DEFAULT NULL,
`date_key` date DEFAULT NULL,
`date_nokey` date DEFAULT NULL,
`time_key` time DEFAULT NULL,
`time_nokey` time DEFAULT NULL,
`datetime_key` datetime DEFAULT NULL,
`datetime_nokey` datetime DEFAULT NULL,
`varchar_key` varchar(1) DEFAULT NULL,
`varchar_nokey` varchar(1) DEFAULT NULL,
PRIMARY KEY (`pk`),
KEY `int_key` (`int_key`),
KEY `date_key` (`date_key`),
KEY `time_key` (`time_key`),
KEY `datetime_key` (`datetime_key`),
KEY `varchar_key` (`varchar_key`,`int_key`)
) ENGINE=MyISAM AUTO_INCREMENT=21 DEFAULT CHARSET=latin1
1 row in set (0.01 sec)
EXPLAIN is slow, but it works. So, please, check with a newer version, 5.1.44.
Also if the bug is repeatable with ndbcluster tables only, then Optimizer category is wrong here.
[5 Mar 2010 14:15]
Ole John Aske
I assume you created the database using RQGs gendata-old? I have a minor modification in my local GendataSimple.pm which I assumed didn't matter: It defines the column int_key as 'UNIQUE KEY': CREATE TABLE `C` ( `pk` int(11) NOT NULL AUTO_INCREMENT, `int_nokey` int(11) DEFAULT NULL, `int_key` int(11) DEFAULT NULL, `date_key` date DEFAULT NULL, `date_nokey` date DEFAULT NULL, `time_key` time DEFAULT NULL, `time_nokey` time DEFAULT NULL, `datetime_key` datetime DEFAULT NULL, `datetime_nokey` datetime DEFAULT NULL, `varchar_key` varchar(1) DEFAULT NULL, `varchar_nokey` varchar(1) DEFAULT NULL, PRIMARY KEY (`pk`), UNIQUE KEY `int_key` (`int_key`), KEY `date_key` (`date_key`), KEY `time_key` (`time_key`), KEY `datetime_key` (`datetime_key`), KEY `varchar_key` (`varchar_key`,`int_key`) ) ENGINE=MyISAM AUTO_INCREMENT=12 DEFAULT CHARSET=latin1 | I don't know if this makes any difference.... Re. MyISAM vs Cluster - This is actually a MyIsam problem only. On Cluster the explain - and execution - is almost instant. Probably due to different access plan generated as the calculated 'costs' may be different for the SEs.
[5 Mar 2010 14:31]
Ole John Aske
Tested UNIQUE KEY vs non-UNIQUE myself: explain, non-UNIQUE: 1 min 29 sec explain UNIQUE:
[5 Mar 2010 14:35]
Ole John Aske
Tested UNIQUE KEY vs non-UNIQUE myself: explain, non-UNIQUE: 1 min, 29 sec explain UNIQUE: 12 min, 15 sec Not entirely an infinite loop, but obviously some bad optimizer decissions are made as ndbcluster explains the same query in virtually no time.
[6 Mar 2010 7:11]
Philip Stoev
Hello. I am afraid that this is not a genuine bug. The reason for the slow EXPLAIN is that the optimizer does an exhaustive search of all possibilities, which takes time, especially if there are numerous tables that are not differentiated, that is, no join order is better than any other, since all tables contain random data with a flat distribution. To fix this, use optimizer_search_depth=10 and the EXPLAIN will complete within 0.1 seconds. Thank you.
Description: The attach query seems to hang in an infine loop in the query optimizer - Even when it is only EXPLAINed it never completes (At least not in several minutes). Lookin at mysqld.trace, it loops in best_access_path: =========================== T@10 : 10:37:43.092348 | | | | | | | | | | | | | | | | | | | | | | | | | | <best_extension_by_limited_search T@10 : 10:37:43.092355 | | | | | | | | | | | | | | | | | | | | | | | | | <best_extension_by_limited_search T@10 : 10:37:43.092363 | | | | | | | | | | | | | | | | | | | | | | | | | >best_access_path T@10 : 10:37:43.092372 | | | | | | | | | | | | | | | | | | | | | | | | | <best_access_path pruned_by_heuristic; idx :15 best: 799477 accumulated: 359187 increment: 359176 count: 414691 POSITIONS: C C C C C C CC CC CC C C CC CC BB CC BEST_POSITIONS: C C C C C C C CC CC D C CC CC BB CC BEST_REF: C(11,11,2) C(11,11,2) C(11,11,2) C(11,11,2) C(11,11,2) C(11,11,2) CC(14,14,2) CC(14,14,2) CC(14,14,2) C(11,11,2) C(11,11,2) CC(14,14,2) CC(14,14,2) BB(1,1,2) C(11,11,2) CC(14,14,2) CC(14,14,2) D(32,32,2) T@10 : 10:37:43.092393 | | | | | | | | | | | | | | | | | | | | | | | | | >best_access_path T@10 : 10:37:43.092402 | | | | | | | | | | | | | | | | | | | | | | | | | <best_access_path T@10 : 10:37:43.092409 | | | | | | | | | | | | | | | | | | | | | | | | | >best_extension_by_limited_search SOFAR:; idx :15 best: 799477 accumulated: 15 increment: 414691 count: 359185 POSITIONS: C C C C C C CC CC CC C C CC CC BB D BEST_POSITIONS: C C C C C C C CC CC D C CC CC BB CC BEST_REF: C(11,11,2) C(11,11,2) C(11,11,2) C(11,11,2) C(11,11,2) C(11,11,2) CC(14,14,2) CC(14,14,2) CC(14,14,2) C(11,11,2) C(11,11,2) CC(14,14,2) CC(14,14,2) BB(1,1,2) D(32,32,2) CC(14,14,2) CC(14,14,2) C(11,11,2) part_plan; idx :15 best: 799477 accumulated: 359185 increment: 359185 count: 414691 POSITIONS: C C C C C C CC CC CC C C CC CC BB D BEST_POSITIONS: C C C C C C C CC CC D C CC CC BB CC BEST_REF: C(11,11,2) C(11,11,2) C(11,11,2) C(11,11,2) C(11,11,2) C(11,11,2) CC(14,14,2) CC(14,14,2) CC(14,14,2) C(11,11,2) C(11,11,2) CC(14,14,2) CC(14,14,2) BB(1,1,2) D(32,32,2) CC(14,14,2) CC(14,14,2) C(11,11,2) How to repeat: With the test database created by the Random Query Generator 'gendata-old' scripts. (I will attach a dump of my database to this bug report): SELECT COUNT( table1 . `pk` ) AS field1 FROM CC AS table1 RIGHT JOIN C AS table2 ON table1 . `pk` = table2 . `int_key` RIGHT JOIN CC AS table3 ON table2 . `pk` = table3 . `int_key` LEFT OUTER JOIN C AS table4 RIGHT JOIN C AS table5 ON table4 . `int_key` = table5 . `pk` ON table2 . `int_key` = table4 . `int_key` LEFT JOIN CC AS table6 LEFT OUTER JOIN D AS table7 RIGHT JOIN C AS table8 ON table7 . `pk` = table8 . `pk` ON table6 . `pk` = table7 . `pk` ON table5 . `pk` = table8 . `int_key` LEFT JOIN CC AS table9 LEFT JOIN BB AS table10 ON table9 . `int_key` = table10 . `int_key` ON table3 . `pk` = table9 . `int_key` RIGHT JOIN CC AS table11 LEFT JOIN C AS table12 ON table11 . `pk` = table12 . `int_key` ON table5 . `int_key` = table12 . `int_key` LEFT JOIN C AS table13 ON table6 . `pk` = table13 . `int_key` LEFT JOIN C AS table14 RIGHT OUTER JOIN C AS table15 ON table14 . `int_key` = table15 . `int_key` LEFT JOIN CC AS table16 LEFT JOIN CC AS table17 ON table16 . `int_key` = table17 . `pk` LEFT JOIN C AS table18 ON table17 . `int_key` = table18 . `pk` ON table15 . `int_key` = table17 . `pk` ON table12 . `int_key` = table16 . `pk` WHERE table14 . `pk` >= table7 . `int_nokey` HAVING (field1 <= 9 OR field1 <> 1) ORDER BY field1 DESC;