MySQL Bugs: #21153: Join with many tables hangs mysql (and taking 100% cpu)

Bug #21153	Join with many tables hangs mysql (and taking 100% cpu)
Submitted:	19 Jul 2006 15:10	Modified:	16 Aug 2006 14:29
Reporter:	Corin Langosch	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server	Severity:	S2 (Serious)
Version:	5.0.21-standard	OS:	Linux (linux)
Assigned to:	Igor Babaev	CPU Architecture:	Any
Tags:	100% cpu, hangs, join, many tables

Description:
the following query hangs the mysql server taking 100% cpu. also an "explain" of the query hangs the server!

How to repeat:
create tables using attached test data.

queries:
EXPLAIN SELECT u1.user AS u1,u2.user AS u2,u3.user AS u3,u4.user AS u4,u5.user AS u5,u6.user AS u6 FROM user AS u1,contact_folders AS f1,contacts AS c1,user AS u2,contact_folders AS f2,contacts AS c2,user AS u3,contact_folders AS f3,contacts AS c3,user AS u4,contact_folders AS f4,contacts AS c4,user AS u5,contact_folders AS f5,contacts AS c5,user AS u6,contact_folders AS f6,contacts AS c6 WHERE u1.user='gucki' AND u6.user='test' AND f1.owner_id=u1.id and c1.folder_id=f1.id AND f2.owner_id=u2.id and c2.folder_id=f2.id AND f3.owner_id=u3.id and c3.folder_id=f3.id AND f4.owner_id=u4.id and c4.folder_id=f4.id AND f5.owner_id=u5.id and c5.folder_id=f5.id AND f6.owner_id=u6.id and c6.folder_id=f6.id AND (c1.user_id=u2.id) AND (c2.user_id=u3.id) AND (c3.user_id=u4.id) AND (c4.user_id=u5.id) AND (c5.user_id=u6.id)

hangs the server with or without the "explain"

Suggested fix:
remove some infinite loop? ;)

Thank you for the report.

Please, provide output of SHOW CREATE TABLE xxx; statement for each table using in the query.

CREATE TABLE `contacts` (\n  `id` int(10) unsigned NOT NULL auto_increment,\n  `folder_id` int(10) unsigned NOT NULL default '0',\n  `user_id` int(10) unsigned NOT NULL default '0',\n  PRIMARY KEY  (`id`),\n  UNIQUE KEY `user_owner` (`user_id`),\n  KEY `folder_id` (`folder_id`)\n) ENGINE=InnoDB DEFAULT CHARSET=latin1 COLLATE=latin1_german1_ci

--

CREATE TABLE `contact_folders` (\n  `id` int(10) unsigned NOT NULL auto_increment,\n  `owner_id` int(10) unsigned NOT NULL default '0',\n  `pos` tinyint(3) unsigned NOT NULL default '0',\n  PRIMARY KEY  (`id`),\n  UNIQUE KEY `owner_pos` (`owner_id`,`pos`)\n) ENGINE=InnoDB DEFAULT CHARSET=latin1 COLLATE=latin1_german1_ci

--

CREATE TABLE `user` (\n  `id` int(10) unsigned NOT NULL auto_increment,\n  `user` varchar(80) collate latin1_german1_ci NOT NULL default '',\n  PRIMARY KEY  (`id`),\n  UNIQUE KEY `user` (`user`)\n) ENGINE=InnoDB DEFAULT CHARSET=latin1 COLLATE=latin1_german1_ci

please note the hang only happens when the tables contain some data. so please use the attached file to generate the tables+data.

>so please use the attached file to generate the tables+data.
Sorry, but I don't see any attached file.

sorry you are right..there must have been an error while uploading and i didn't see it. now it's attached!

Verified on Windows and Linux using last BK sources. Server does not crashes, but always takes 100% CPU. EXPLAIN query processes on different machines from 28 to 42 seconds.

This is not a bug.
The reported query is a 18-way join. For such queries we expect that the full search for the best execution plan will take a significant amount of time.
At the same due to a specific structure of the reported query we can hope to get a good execution plan with a limited search (see Manual 5.0: 7.5.3. Controlling Query Optimizer Performance).

Setting the value of the global variable 'optimizer_search_depth' to 4 or even to 2 we can get the same execution plan as with a full search. Yet it will take much less time:

mysql> set @@optimizer_search_depth=4;
Query OK, 0 rows affected (0.00 sec)

mysql> EXPLAIN
    -> SELECT
    -> u1.user AS u1,
    -> u2.user AS u2,
    -> u3.user AS u3,
    -> u4.user AS u4,
    -> u5.user AS u5,
    -> u6.user AS u6
    -> FROM
    -> user AS u1,
    -> contact_folders AS f1,
    -> contacts AS c1,
    -> user AS u2,
    -> contact_folders AS f2,
    -> contacts AS c2,
    -> user AS u3,
    -> contact_folders AS f3,
    -> contacts AS c3,
    -> user AS u4,
    -> contact_folders AS f4,
    -> contacts AS c4,
    -> user AS u5,
    -> contact_folders AS f5,
    -> contacts AS c5,
    -> user AS u6,
    -> contact_folders AS f6,
    -> contacts AS c6
    -> WHERE
    -> u1.user='gucki' AND
    -> u6.user='test' AND
    -> f1.owner_id=u1.id AND
    -> c1.folder_id=f1.id AND
    -> f2.owner_id=u2.id AND
    -> c2.folder_id=f2.id AND
    -> f3.owner_id=u3.id AND
    -> c3.folder_id=f3.id AND
    -> f4.owner_id=u4.id AND
    -> c4.folder_id=f4.id AND
    -> f5.owner_id=u5.id AND
    -> c5.folder_id=f5.id AND
    -> f6.owner_id=u6.id AND
    -> c6.folder_id=f6.id AND
    -> (c1.user_id=u2.id) AND
    -> (c2.user_id=u3.id) AND
    -> (c3.user_id=u4.id) AND
    -> (c4.user_id=u5.id) AND
    -> (c5.user_id=u6.id);
+----+-------------+-------+--------+----------------------+------------+---------+-------------------+------+--------------------------+
| id | select_type | table | type   | possible_keys        | key        | key_len | ref               | rows | Extra                    |
+----+-------------+-------+--------+----------------------+------------+---------+-------------------+------+--------------------------+
|  1 | SIMPLE      | u1    | ref    | PRIMARY,user         | user       | 82      | const             |    1 | Using where; Using index |
|  1 | SIMPLE      | u6    | ref    | PRIMARY,user         | user       | 82      | const             |    1 | Using where; Using index |
|  1 | SIMPLE      | c5    | eq_ref | user_owner,folder_id | user_owner | 4       | test.u6.id        |    1 |                          |
|  1 | SIMPLE      | f5    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c5.folder_id |    1 |                          |
|  1 | SIMPLE      | u5    | eq_ref | PRIMARY              | PRIMARY    | 4       | test.f5.owner_id  |    1 |                          |
|  1 | SIMPLE      | c4    | eq_ref | user_owner,folder_id | user_owner | 4       | test.u5.id        |    1 | Using where              |
|  1 | SIMPLE      | f4    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c4.folder_id |    1 |                          |
|  1 | SIMPLE      | u4    | eq_ref | PRIMARY              | PRIMARY    | 4       | test.f4.owner_id  |    1 |                          |
|  1 | SIMPLE      | c3    | eq_ref | user_owner,folder_id | user_owner | 4       | test.f4.owner_id  |    1 |                          |
|  1 | SIMPLE      | f3    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c3.folder_id |    1 |                          |
|  1 | SIMPLE      | u3    | eq_ref | PRIMARY              | PRIMARY    | 4       | test.f3.owner_id  |    1 |                          |
|  1 | SIMPLE      | c2    | eq_ref | user_owner,folder_id | user_owner | 4       | test.u3.id        |    1 | Using where              |
|  1 | SIMPLE      | f2    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c2.folder_id |    1 |                          |
|  1 | SIMPLE      | u2    | eq_ref | PRIMARY              | PRIMARY    | 4       | test.f2.owner_id  |    1 |                          |
|  1 | SIMPLE      | c1    | eq_ref | user_owner,folder_id | user_owner | 4       | test.u2.id        |    1 | Using where              |
|  1 | SIMPLE      | f1    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c1.folder_id |    1 | Using where              |
|  1 | SIMPLE      | f6    | ref    | PRIMARY,owner_pos    | owner_pos  | 4       | test.u6.id        |    1 | Using index              |
|  1 | SIMPLE      | c6    | ref    | folder_id            | folder_id  | 4       | test.f6.id        |    1 | Using index              |
+----+-------------+-------+--------+----------------------+------------+---------+-------------------+------+--------------------------+
18 rows in set (0.03 sec)

mysql> set @@optimizer_search_depth=2;
Query OK, 0 rows affected (0.00 sec)

mysql> EXPLAIN
    -> SELECT
    -> u1.user AS u1,
    -> u2.user AS u2,
...
+----+-------------+-------+--------+----------------------+------------+---------+-------------------+------+--------------------------+
| id | select_type | table | type   | possible_keys        | key        | key_len | ref               | rows | Extra                    |
+----+-------------+-------+--------+----------------------+------------+---------+-------------------+------+--------------------------+
|  1 | SIMPLE      | u1    | ref    | PRIMARY,user         | user       | 82      | const             |    1 | Using where; Using index |
|  1 | SIMPLE      | u6    | ref    | PRIMARY,user         | user       | 82      | const             |    1 | Using where; Using index |
|  1 | SIMPLE      | c5    | eq_ref | user_owner,folder_id | user_owner | 4       | test.u6.id        |    1 |                          |
|  1 | SIMPLE      | f5    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c5.folder_id |    1 |                          |
|  1 | SIMPLE      | u5    | eq_ref | PRIMARY              | PRIMARY    | 4       | test.f5.owner_id  |    1 |                          |
|  1 | SIMPLE      | c4    | eq_ref | user_owner,folder_id | user_owner | 4       | test.u5.id        |    1 | Using where              |
|  1 | SIMPLE      | f4    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c4.folder_id |    1 |                          |
|  1 | SIMPLE      | u4    | eq_ref | PRIMARY              | PRIMARY    | 4       | test.f4.owner_id  |    1 |                          |
|  1 | SIMPLE      | c3    | eq_ref | user_owner,folder_id | user_owner | 4       | test.f4.owner_id  |    1 |                          |
|  1 | SIMPLE      | f3    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c3.folder_id |    1 |                          |
|  1 | SIMPLE      | u3    | eq_ref | PRIMARY              | PRIMARY    | 4       | test.f3.owner_id  |    1 |                          |
|  1 | SIMPLE      | c2    | eq_ref | user_owner,folder_id | user_owner | 4       | test.u3.id        |    1 | Using where              |
|  1 | SIMPLE      | f2    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c2.folder_id |    1 |                          |
|  1 | SIMPLE      | u2    | eq_ref | PRIMARY              | PRIMARY    | 4       | test.f2.owner_id  |    1 |                          |
|  1 | SIMPLE      | c1    | eq_ref | user_owner,folder_id | user_owner | 4       | test.u2.id        |    1 | Using where              |
|  1 | SIMPLE      | f1    | eq_ref | PRIMARY,owner_pos    | PRIMARY    | 4       | test.c1.folder_id |    1 | Using where              |
|  1 | SIMPLE      | f6    | ref    | PRIMARY,owner_pos    | owner_pos  | 4       | test.u6.id        |    1 | Using index              |
|  1 | SIMPLE      | c6    | ref    | folder_id            | folder_id  | 4       | test.f6.id        |    1 | Using index              |
+----+-------------+-------+--------+----------------------+------------+---------+-------------------+------+--------------------------+
18 rows in set (0.00 sec)

Why is this not considered a bug? We have exactly the same problem with complex joins. The same query on the same data set works perfectly with mysql 4.1. When using mysql 5.0 the server simply hangs on the cpu. And worse: if there is any insert/update/delete statement after such a query then all of the known locking issues with myisam tables arise.

The docs say: "For example, queries with 12, 13, or more tables may easily require hours and even days to compile if optimizer_search_depth is close to the number of tables in the query" (7.5.3. Controlling Query Optimizer Performance). So this is at least documented behaviour ;-)

Shrinking optimizer_search_depth helps indeed, thanks for this hint. I'd consider a more conservative default value than the standard 62, I think this would help many people. It seems that 4 is a reasonable value, 5 is already too large.

Cheers,
Michael

Even though this is an _old_ discussion, Michael's advice is still very relevant.
It saved my day.
In the context of a CakePHP research database (see <http://www.ncbi.nlm.nih.gov/pubmed/24507951>) I had a query with a 19-way join. Even though I optimized everything and used indexes throughout, adding the 17th join suddenly hung the server. Even though the database was quite small, execution time went up from less than 1 s to 120 seconds under MySQL 5.5.30/Open Suse 12.3-64 with 8 GB RAM and an SSD.
After a simple:
set @@optimizer_search_depth=4;
execution time dropped to 0.015 s.
Thanks a lot!