MySQL Bugs: #54531: Performance regression with many joins

Bug #54531	Performance regression with many joins
Submitted:	15 Jun 2010 21:39	Modified:	16 Jun 2010 22:10
Reporter:	Gary Pendergast	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.1.46, 5.1.47	OS:	Any
Assigned to:		CPU Architecture:	Any
Tags:	join, performance, regression

Description:
There is a performance regression as of 5.1.46, using the attached schema/query. It has been verified in 5.1.46 and 5.1.47.

How to repeat:
See attachments.

Test schema

Attachment: schema.sql (application/octet-stream, text), 6.96 KiB.

Test query

Attachment: query.sql (application/octet-stream, text), 1.15 KiB.

This is what I see with current 5.1.49 from bzr on Mac OS X:

valeriy-kravchuks-macbook-pro:5.1 openxs$ bin/mysql -uroot test
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 4
Server version: 5.1.49-debug Source distribution

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> SELECT SQL_NO_CACHE COUNT(*)
    -> FROM J AS J
    -> INNER JOIN L
    -> ON L.L_id = J.L_id
    -> INNER JOIN N
    -> ON N.N_id = J.N_id
    -> INNER JOIN O
    -> ON O.O_id = N.O_id
    -> LEFT JOIN K
    -> ON K.J_id = J.J_id
    -> INNER JOIN O AS O_alias
	ON L.O_id = O_alias.O_id
INNER JOIN T
	ON N.N_id = T.N_id
INNER JOIN S
	ON T.S_id = S.S_id
INNER JOIN U
	ON S.U_id = U.U_id
	AND U.field_3 = 'text' AND S.field_1 <= 0
INNER JOIN B
	ON O_alias.B_id = B.B_id
INNER JOIN W
	ON T.S_id = W.S_id
LEFT JOIN R
	ON L.L_id = R.L_id
LEFT JOIN F
	ON L.L_id = F.L_id
LEFT JOIN X
	ON W.X_id = X.X_id
INNER JOIN C
	ON B.C_id = C.C_id
LEFT JOIN P
	ON L.L_id = P.L_id
INNER JOIN E
	ON C.E_id = E.E_id
LEFT JOIN V
	ON V.V_id = X.V_id
LEFT JOIN A
	ON F.A_id = A.A_id
LEFT JOIN Q
	ON R.R_id = Q.R_id
LEFT JOIN H
	ON L.L_id = H.L_id
LEFT JOIN I
	ON L.L_id = I.L_id
INNER JOIN Z
	ON B.Z_id = Z.Z_id
INNER JOIN M
	ON N.M_id = M.M_id
LEFT JOIN N AS N_alias
	ON A.N_id = N_alias.N_id
INNER JOIN D
	ON E.D_id = D.D_id
LEFT JOIN P AS P_alias
	ON Q.P_id = P_alias.P_id
LEFT JOIN G
	ON L.L_id = G.L_id
INNER JOIN Z AS Z_alias
	ON O_alias.Z_id = Z_alias.Z_id
LEFT JOIN Y
	ON Y.Y_id = V.Y_id
WHERE N.M_id = '3'
	AND L.O_id = '3'
	AND J.N_id = '3'
GROUP    -> ON L.O_id = O_alias.O_id
    -> INNER JOIN T
    -> ON N.N_id = T.N_id
    -> INNER JOIN S
    -> ON T.S_id = S.S_id
    -> INNER JOIN U
    -> ON S.U_id = U.U_id
    -> AND U.field_3 = 'text' AND S.field_1 <= 0
    -> INNER JOIN B
    -> ON O_alias.B_id = B.B_id
    -> INNER JOIN W
    -> ON T.S_id = W.S_id
    -> LEFT JOIN R
    -> ON L.L_id = R.L_id
    -> LEFT JOIN F
    -> ON L.L_id = F.L_id
    -> LEFT JOIN X
    -> ON W.X_id = X.X_id
    -> INNER JOIN C
    -> ON B.C_id = C.C_id
    -> LEFT JOIN P
    -> ON L.L_id = P.L_id
    -> INNER JOIN E
    -> ON C.E_id = E.E_id
    -> LEFT JOIN V
    -> ON V.V_id = X.V_id
    -> LEFT JOIN A
    -> ON F.A_id = A.A_id
    -> LEFT JOIN Q
    -> ON R.R_id = Q.R_id
    -> LEFT JOIN H
    -> ON L.L_id = H.L_id
    -> LEFT JOIN I
    -> ON L.L_id = I.L_id
    -> INNER JOIN Z
    -> ON B.Z_id = Z.Z_id
    -> INNER JOIN M
    -> ON N.M_id = M.M_id
    -> LEFT JOIN N AS N_alias
    -> ON A.N_id = N_alias.N_id
    -> INNER JOIN D
    -> ON E.D_id = D.D_id
    -> LEFT JOIN P AS P_alias
    -> ON Q.P_id = P_alias.P_id
    -> LEFT JOIN G
    -> ON L.L_id = G.L_id
    -> INNER JOIN Z AS Z_alias
    -> ON O_alias.Z_id = Z_alias.Z_id
    -> LEFT JOIN Y
    -> ON Y.Y_id = V.Y_id
    -> WHERE N.M_id = '3'
    -> AND L.O_id = '3'
    -> AND J.N_id = '3'
    -> GROUP BY J.J_id;
Empty set (0.05 sec)

So, somehow this is fixed. Now, with 5.1.47 it is slow enough:

valeriy-kravchuks-macbook-pro:mysql-5.1.47-osx10.5-x86_64 openxs$ bin/mysql -uroot test
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 2
Server version: 5.1.47 MySQL Community Server (GPL)

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> SELECT SQL_NO_CACHE COUNT(*)
    -> FROM J AS J
    -> INNER JOIN L
    -> ON L.L_id = J.L_id
    -> INNER JOIN N
    -> ON N.N_id = J.N_id
    -> INNER JOIN O
    -> ON O.O_id = N.O_id
    -> LEFT JOIN K
    -> ON K.J_id = J.J_id
    -> INNER JOIN O AS O_alias
    -> ON L.O_id = O_alias.O_id
    -> INNER JOIN T
    -> ON N.N_id = T.N_id
    -> INNER JOIN S
    -> ON T.S_id = S.S_id
    -> INNER JOIN U
    -> ON S.U_id = U.U_id
    -> AND U.field_3 = 'text' AND S.field_1 <= 0
    -> INNER JOIN B
    -> ON O_alias.B_id = B.B_id
    -> INNER JOIN W
    -> ON T.S_id = W.S_id
    -> LEFT JOIN R
    -> ON L.L_id = R.L_id
    -> LEFT JOIN F
    -> ON L.L_id = F.L_id
    -> LEFT JOIN X
    -> ON W.X_id = X.X_id
    -> INNER JOIN C
    -> ON B.C_id = C.C_id
    -> LEFT JOIN P
    -> ON L.L_id = P.L_id
    -> INNER JOIN E
    -> ON C.E_id = E.E_id
    -> LEFT JOIN V
    -> ON V.V_id = X.V_id
    -> LEFT JOIN A
    -> ON F.A_id = A.A_id
    -> LEFT JOIN Q
    -> ON R.R_id = Q.R_id
    -> LEFT JOIN H
    -> ON L.L_id = H.L_id
    -> LEFT JOIN I
    -> ON L.L_id = I.L_id
    -> INNER JOIN Z
    -> ON B.Z_id = Z.Z_id
    -> INNER JOIN M
    -> ON N.M_id = M.M_id
    -> LEFT JOIN N AS N_alias
    -> ON A.N_id = N_alias.N_id
    -> INNER JOIN D
    -> ON E.D_id = D.D_id
    -> LEFT JOIN P AS P_alias
    -> ON Q.P_id = P_alias.P_id
    -> LEFT JOIN G
    -> ON L.L_id = G.L_id
    -> INNER JOIN Z AS Z_alias
    -> ON O_alias.Z_id = Z_alias.Z_id
    -> LEFT JOIN Y
    -> ON Y.Y_id = V.Y_id
    -> WHERE N.M_id = '3'
    -> AND L.O_id = '3'
    -> AND J.N_id = '3'
    -> GROUP BY J.J_id;

Empty set (18.61 sec)

on the same schema and laptop. This is what we see in EXPLAIN with 5.1.47:

...
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                                               |
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
|  1 | SIMPLE      | NULL  | NULL | NULL          | NULL | NULL    | NULL | NULL | Impossible WHERE noticed after reading const tables |
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
1 row in set (17.89 sec)

With 5.1.49 we have the same:

+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra                                               |
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
|  1 | SIMPLE      | NULL  | NULL | NULL          | NULL | NULL    | NULL | NULL | Impossible WHERE noticed after reading const tables |
+----+-------------+-------+------+---------------+------+---------+------+------+-----------------------------------------------------+
1 row in set (0.03 sec)

I was not able to find any duplicate or exact reason why 5.1.49 runs fast again.

This is fixed in 5.1.48, I suspect it's a duplicate of Bug #53334.