MySQL Bugs: #72854: Extremely slow performance with outer joins and join buffer

Bug #72854	Extremely slow performance with outer joins and join buffer
Submitted:	3 Jun 2014 20:12	Modified:	5 Oct 2017 15:43
Reporter:	Sergey Petrunya	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.6.17	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
A query with lots of LEFT JOINs is very slow when join buffer is on. When join buffer is off, it finishes instantly.

It doesn't seem to matter how many values are in the tables. The example uses a degenerate case where all queried tables are empty.

How to repeat:
drop table if exists t2,t1;

CREATE TABLE `t1` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `col1` varchar(255) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

CREATE TABLE `t2` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `parent_id` smallint(3) NOT NULL DEFAULT '0',
  `col2` varchar(25) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

select now();
SELECT t.* 
FROM 
  t1 t 
  LEFT JOIN t2 c1 ON c1.parent_id = t.id AND c1.col2 = "val"
  LEFT JOIN t2 c2 ON c2.parent_id = t.id AND c2.col2 = "val"
  LEFT JOIN t2 c3 ON c3.parent_id = t.id AND c3.col2 = "val"
  LEFT JOIN t2 c4 ON c4.parent_id = t.id AND c4.col2 = "val"
  LEFT JOIN t2 c5 ON c5.parent_id = t.id AND c5.col2 = "val"
  LEFT JOIN t2 c6 ON c6.parent_id = t.id AND c6.col2 = "val"
  LEFT JOIN t2 c7 ON c7.parent_id = t.id AND c7.col2 = "val"
  LEFT JOIN t2 c8 ON c8.parent_id = t.id AND c8.col2 = "val"
  LEFT JOIN t2 c9 ON c9.parent_id = t.id AND c9.col2 = "val"
  LEFT JOIN t2 c10 ON c10.parent_id = t.id AND c10.col2 = "val"
  LEFT JOIN t2 c11 ON c11.parent_id = t.id AND c11.col2 = "val"
  LEFT JOIN t2 c12 ON c12.parent_id = t.id AND c12.col2 = "val"
  LEFT JOIN t2 c13 ON c13.parent_id = t.id AND c13.col2 = "val"
  LEFT JOIN t2 c14 ON c14.parent_id = t.id AND c14.col2 = "val"
  LEFT JOIN t2 c15 ON c15.parent_id = t.id AND c15.col2 = "val"
  LEFT JOIN t2 c16 ON c16.parent_id = t.id AND c16.col2 = "val"
  LEFT JOIN t2 c17 ON c17.parent_id = t.id AND c17.col2 = "val"
  LEFT JOIN t2 c18 ON c18.parent_id = t.id AND c18.col2 = "val"
  LEFT JOIN t2 c19 ON c19.parent_id = t.id AND c19.col2 = "val"
  LEFT JOIN t2 c20 ON c20.parent_id = t.id AND c20.col2 = "val"
  LEFT JOIN t2 c21 ON c21.parent_id = t.id AND c21.col2 = "val"
  LEFT JOIN t2 c22 ON c22.parent_id = t.id AND c22.col2 = "val"
  LEFT JOIN t2 c23 ON c23.parent_id = t.id AND c23.col2 = "val"
  LEFT JOIN t2 c24 ON c24.parent_id = t.id AND c24.col2 = "val"
  LEFT JOIN t2 c25 ON c25.parent_id = t.id AND c25.col2 = "val"
  LEFT JOIN t2 c26 ON c26.parent_id = t.id AND c26.col2 = "val"
  LEFT JOIN t2 c27 ON c27.parent_id = t.id AND c27.col2 = "val"
  LEFT JOIN t2 c28 ON c28.parent_id = t.id AND c28.col2 = "val"
  LEFT JOIN t2 c29 ON c29.parent_id = t.id AND c29.col2 = "val"
  LEFT JOIN t2 c30 ON c30.parent_id = t.id AND c30.col2 = "val"
  LEFT JOIN t2 c31 ON c31.parent_id = t.id AND c31.col2 = "val"
  LEFT JOIN t2 c32 ON c32.parent_id = t.id AND c32.col2 = "val"
  LEFT JOIN t2 c33 ON c33.parent_id = t.id AND c33.col2 = "val"
ORDER BY 
  col1;

select now();

Note that if one runs the above query with optimizer_switch='block_nested_loop=off', it finishes instantly.

mysql 5.6 > select now();
+---------------------+
| now()               |
+---------------------+
| 2014-06-03 17:48:44 |
+---------------------+
1 row in set (0.00 sec)

mysql 5.6 > SELECT t.*
    -> FROM
    ->   t1 t
    ->   LEFT JOIN t2 c1 ON c1.parent_id = t.id AND c1.col2 = "val"
    ->   LEFT JOIN t2 c2 ON c2.parent_id = t.id AND c2.col2 = "val"
    ->   LEFT JOIN t2 c3 ON c3.parent_id = t.id AND c3.col2 = "val"
    ->   LEFT JOIN t2 c4 ON c4.parent_id = t.id AND c4.col2 = "val"
    ->   LEFT JOIN t2 c5 ON c5.parent_id = t.id AND c5.col2 = "val"
    ->   LEFT JOIN t2 c6 ON c6.parent_id = t.id AND c6.col2 = "val"
    ->   LEFT JOIN t2 c7 ON c7.parent_id = t.id AND c7.col2 = "val"
    ->   LEFT JOIN t2 c8 ON c8.parent_id = t.id AND c8.col2 = "val"
    ->   LEFT JOIN t2 c9 ON c9.parent_id = t.id AND c9.col2 = "val"
    ->   LEFT JOIN t2 c10 ON c10.parent_id = t.id AND c10.col2 = "val"
    ->   LEFT JOIN t2 c11 ON c11.parent_id = t.id AND c11.col2 = "val"
    ->   LEFT JOIN t2 c12 ON c12.parent_id = t.id AND c12.col2 = "val"
    ->   LEFT JOIN t2 c13 ON c13.parent_id = t.id AND c13.col2 = "val"
    ->   LEFT JOIN t2 c14 ON c14.parent_id = t.id AND c14.col2 = "val"
    ->   LEFT JOIN t2 c15 ON c15.parent_id = t.id AND c15.col2 = "val"
    ->   LEFT JOIN t2 c16 ON c16.parent_id = t.id AND c16.col2 = "val"
    ->   LEFT JOIN t2 c17 ON c17.parent_id = t.id AND c17.col2 = "val"
    ->   LEFT JOIN t2 c18 ON c18.parent_id = t.id AND c18.col2 = "val"
    ->   LEFT JOIN t2 c19 ON c19.parent_id = t.id AND c19.col2 = "val"
    ->   LEFT JOIN t2 c20 ON c20.parent_id = t.id AND c20.col2 = "val"
    ->   LEFT JOIN t2 c21 ON c21.parent_id = t.id AND c21.col2 = "val"
    ->   LEFT JOIN t2 c22 ON c22.parent_id = t.id AND c22.col2 = "val"
    ->   LEFT JOIN t2 c23 ON c23.parent_id = t.id AND c23.col2 = "val"
    ->   LEFT JOIN t2 c24 ON c24.parent_id = t.id AND c24.col2 = "val"
    ->   LEFT JOIN t2 c25 ON c25.parent_id = t.id AND c25.col2 = "val"
    ->   LEFT JOIN t2 c26 ON c26.parent_id = t.id AND c26.col2 = "val"
    ->   LEFT JOIN t2 c27 ON c27.parent_id = t.id AND c27.col2 = "val"
    ->   LEFT JOIN t2 c28 ON c28.parent_id = t.id AND c28.col2 = "val"
    ->   LEFT JOIN t2 c29 ON c29.parent_id = t.id AND c29.col2 = "val"
    ->   LEFT JOIN t2 c30 ON c30.parent_id = t.id AND c30.col2 = "val"
    ->   LEFT JOIN t2 c31 ON c31.parent_id = t.id AND c31.col2 = "val"
    ->   LEFT JOIN t2 c32 ON c32.parent_id = t.id AND c32.col2 = "val"
    ->   LEFT JOIN t2 c33 ON c33.parent_id = t.id AND c33.col2 = "val"
    -> ORDER BY
    ->   col1;
Empty set (16 min 21.11 sec)

mysql 5.6 >
mysql 5.6 > select now();
+---------------------+
| now()               |
+---------------------+
| 2014-06-03 18:05:11 |
+---------------------+
1 row in set (0.00 sec)

mysql 5.6 > set optimizer_switch='block_nested_loop=off';
Query OK, 0 rows affected (0.00 sec)

mysql 5.6 > select now();
+---------------------+
| now()               |
+---------------------+
| 2014-06-03 18:06:37 |
+---------------------+
1 row in set (0.00 sec)

mysql 5.6 > SELECT t.*
    -> FROM
    ->   t1 t
    ->   LEFT JOIN t2 c1 ON c1.parent_id = t.id AND c1.col2 = "val"
    ->   LEFT JOIN t2 c2 ON c2.parent_id = t.id AND c2.col2 = "val"
    ->   LEFT JOIN t2 c3 ON c3.parent_id = t.id AND c3.col2 = "val"
    ->   LEFT JOIN t2 c4 ON c4.parent_id = t.id AND c4.col2 = "val"
    ->   LEFT JOIN t2 c5 ON c5.parent_id = t.id AND c5.col2 = "val"
    ->   LEFT JOIN t2 c6 ON c6.parent_id = t.id AND c6.col2 = "val"
    ->   LEFT JOIN t2 c7 ON c7.parent_id = t.id AND c7.col2 = "val"
    ->   LEFT JOIN t2 c8 ON c8.parent_id = t.id AND c8.col2 = "val"
    ->   LEFT JOIN t2 c9 ON c9.parent_id = t.id AND c9.col2 = "val"
    ->   LEFT JOIN t2 c10 ON c10.parent_id = t.id AND c10.col2 = "val"
    ->   LEFT JOIN t2 c11 ON c11.parent_id = t.id AND c11.col2 = "val"
    ->   LEFT JOIN t2 c12 ON c12.parent_id = t.id AND c12.col2 = "val"
    ->   LEFT JOIN t2 c13 ON c13.parent_id = t.id AND c13.col2 = "val"
    ->   LEFT JOIN t2 c14 ON c14.parent_id = t.id AND c14.col2 = "val"
    ->   LEFT JOIN t2 c15 ON c15.parent_id = t.id AND c15.col2 = "val"
    ->   LEFT JOIN t2 c16 ON c16.parent_id = t.id AND c16.col2 = "val"
    ->   LEFT JOIN t2 c17 ON c17.parent_id = t.id AND c17.col2 = "val"
    ->   LEFT JOIN t2 c18 ON c18.parent_id = t.id AND c18.col2 = "val"
    ->   LEFT JOIN t2 c19 ON c19.parent_id = t.id AND c19.col2 = "val"
    ->   LEFT JOIN t2 c20 ON c20.parent_id = t.id AND c20.col2 = "val"
    ->   LEFT JOIN t2 c21 ON c21.parent_id = t.id AND c21.col2 = "val"
    ->   LEFT JOIN t2 c22 ON c22.parent_id = t.id AND c22.col2 = "val"
    ->   LEFT JOIN t2 c23 ON c23.parent_id = t.id AND c23.col2 = "val"
    ->   LEFT JOIN t2 c24 ON c24.parent_id = t.id AND c24.col2 = "val"
    ->   LEFT JOIN t2 c25 ON c25.parent_id = t.id AND c25.col2 = "val"
    ->   LEFT JOIN t2 c26 ON c26.parent_id = t.id AND c26.col2 = "val"
    ->   LEFT JOIN t2 c27 ON c27.parent_id = t.id AND c27.col2 = "val"
    ->   LEFT JOIN t2 c28 ON c28.parent_id = t.id AND c28.col2 = "val"
    ->   LEFT JOIN t2 c29 ON c29.parent_id = t.id AND c29.col2 = "val"
    ->   LEFT JOIN t2 c30 ON c30.parent_id = t.id AND c30.col2 = "val"
    ->   LEFT JOIN t2 c31 ON c31.parent_id = t.id AND c31.col2 = "val"
    ->   LEFT JOIN t2 c32 ON c32.parent_id = t.id AND c32.col2 = "val"
    ->   LEFT JOIN t2 c33 ON c33.parent_id = t.id AND c33.col2 = "val"
    -> ORDER BY
    ->   col1;
Empty set (0.00 sec)

mysql 5.6 >
mysql 5.6 > select now();
+---------------------+
| now()               |
+---------------------+
| 2014-06-03 18:06:37 |
+---------------------+
1 row in set (0.00 sec)

mysql 5.6 > SHOW VARIABLES LIKE "%VERSION%";
+-------------------------+---------------------+
| Variable_name           | Value               |
+-------------------------+---------------------+
| innodb_version          | 5.6.20              |
| protocol_version        | 10                  |
| slave_type_conversions  |                     |
| version                 | 5.6.20              |
| version_comment         | Source distribution |
| version_compile_machine | x86_64              |
| version_compile_os      | Win64               |
+-------------------------+---------------------+
7 rows in set (0.00 sec)

mysql 5.6 >

Thank you for the bug report.

Back yo verified following internal note.

when is this being fixed and released ?
how can I help ?

Posted by developer:
 
Noted in 5.7.21, 8.0.4.

Queries with many left joins were slow if join buffering was used
(for example, using the block nested loop algorithm).