Bug #77340 Optimizer chooses wrong index for LEFT JOIN query

Description:
Under certain circumstances Optimizer uses wrong index for certain query.

How to repeat:
Use attached file, start MySQL with option innodb-file-format=barracuda, then run

mysql> flush tables; flush status;
Query OK, 0 rows affected (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql> SELECT COUNT(DISTINCT `t1`.`id`) FROM `t1` INNER JOIN `t2` ON `t2`.`id` = `t1`.`f1` LEFT OUTER JOIN `t3` ON `t3`.`f1` = `t1`.`id` AND t3.f3 IS NULL AND `t3`.`f4` = 'Entry' LEFT OUTER JOIN `t3` `thumbnails_t3` ON `thumbnails_t3`.`f3` = `t3`.`id` WHERE `t1`.`f2` IS NULL AND `t1`.`f3` = 85260 AND (t1.f3 = 85260 AND t2.f2 IS NULL);
+---------------------------+
| COUNT(DISTINCT `t1`.`id`) |
+---------------------------+
| 512 |
+---------------------------+
1 row in set (13.73 sec)

mysql> show status like 'Handler_%';
+----------------------------+--------+
| Variable_name | Value |
+----------------------------+--------+
| Handler_commit | 1 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_external_lock | 8 |
| Handler_mrr_init | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 1 |
| Handler_read_key | 514 |
| Handler_read_last | 0 |
| Handler_read_next | 512512 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 26 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 0 |
+----------------------------+--------+
18 rows in set (0.00 sec)

mysql> explain SELECT COUNT(DISTINCT `t1`.`id`) FROM `t1` INNER JOIN `t2` ON `t2`.`id` = `t1`.`f1` LEFT OUTER JOIN `t3` force index(f1) ON `t3`.`f1` = `t1`.`id` AND t3.f3 IS NULL AND `t3`.`f4` = 'Entry' LEFT OUTER JOIN `t3` `thumbnails_t3` ON `thumbnails_t3`.`f3` = `t3`.`id` WHERE `t1`.`f2` IS NULL AND `t1`.`f3` = 85260 AND (t1.f3 = 85260 AND t2.f2 IS NULL);
+----+-------------+---------------+------------+------+---------------+------+---------+------------------+------+----------+----------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------------+------------+------+---------------+------+---------+------------------+------+----------+----------------------------------------------------+
| 1 | SIMPLE | t1 | NULL | ref | f3 | f3 | 4 | const | 511 | 10.00 | Using where |
| 1 | SIMPLE | t2 | NULL | ALL | PRIMARY | NULL | NULL | NULL | 25 | 0.40 | Using where; Using join buffer (Block Nested Loop) |
| 1 | SIMPLE | t3 | NULL | ref | f1 | f1 | 1032 | test.t1.id,const | 19 | 100.00 | Using where |
| 1 | SIMPLE | thumbnails_t3 | NULL | ref | f3 | f3 | 9 | test.t3.id | 3 | 100.00 | Using index |
+----+-------------+---------------+------------+------+---------------+------+---------+------------------+------+----------+----------------------------------------------------+
4 rows in set, 1 warning (0.00 sec)

mysql> flush tables; flush status; Query OK, 0 rows affected (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql> SELECT COUNT(DISTINCT `t1`.`id`) FROM `t1` INNER JOIN `t2` ON `t2`.`id` = `t1`.`f1` LEFT OUTER JOIN `t3` force index(f1) ON `t3`.`f1` = `t1`.`id` AND t3.f3 IS NULL AND `t3`.`f4` = 'Entry' LEFT OUTER JOIN `t3` `thumbnails_t3` ON `thumbnails_t3`.`f3` = `t3`.`id` WHERE `t1`.`f2` IS NULL AND `t1`.`f3` = 85260 AND (t1.f3 = 85260 AND t2.f2 IS NULL);
+---------------------------+
| COUNT(DISTINCT `t1`.`id`) |
+---------------------------+
| 512 |
+---------------------------+
1 row in set (0.14 sec)

mysql> show status like 'Handler_%'; +----------------------------+-------+
| Variable_name | Value |
+----------------------------+-------+
| Handler_commit | 1 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_external_lock | 8 |
| Handler_mrr_init | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 1 |
| Handler_read_key | 514 |
| Handler_read_last | 0 |
| Handler_read_next | 512 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 26 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 0 |
+----------------------------+-------+
18 rows in set (0.00 sec)

CREATE TABLE `t3` (
  `id` bigint(20) NOT NULL,
  `f1` bigint(20) DEFAULT NULL,
  `f3` bigint(20) DEFAULT NULL,
  `f4` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `f3` (`f3`),
  KEY `f1` (`f1`,`f4`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 ROW_FORMAT=DYNAMIC;

Note that in the first case index f3 chosen while using f1 demonstrates better result.

Sometimes Optimizer chooses f3 index in optimizer_switch set to "use_index_extensions=off", but this is more likely repeatable with larger tables.

First two tables, necessary to repeat the bug

Attachment: issue53536_renamed.sql.1.gz (application/gzip, text), 2.64 MiB.

Third table, necessary to repeat this bug

Attachment: issue53536_renamed.sql.2.gz (application/gzip, text), 670.81 KiB.

Originally reported at https://bugs.launchpad.net/percona-server/+bug/1464789

Thank you for the bug version. Version 5.5 not affected.

C:\dbs>c:\dbs\5.5\bin\mysql -uroot --port=3550 --prompt="mysql 5.5 > "
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 3
Server version: 5.5.45-log Source distribution PULL: 2015/06/05

mysql 5.5 > use test
Database changed
mysql 5.5 > SHOW VARIABLES LIKE "innodb_file_format";
+--------------------+-----------+
| Variable_name      | Value     |
+--------------------+-----------+
| innodb_file_format | Barracuda |
+--------------------+-----------+
1 row in set (0.00 sec)

mysql 5.5 >  flush tables; flush status;
Query OK, 0 rows affected (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql 5.5 > SELECT COUNT(DISTINCT `t1`.`id`) FROM `t1` INNER JOIN `t2` ON `t2`.`id` = `t1`.`f1` LEFT OUTER JOIN `t3` ON `t3`.`f1` = `t1`.`id` AND t3.f3 IS NULL AND `t3`.`f4` = 'Entry' LEFT OUTER JOIN `t3` `thumbnails_t3` ON `thumbnails_t3`.`f3` = `t3`.`id` WHE
RE `t1`.`f2` IS NULL AND `t1`.`f3` = 85260 AND (t1.f3 = 85260 AND t2.f2 IS NULL);
+---------------------------+
| COUNT(DISTINCT `t1`.`id`) |
+---------------------------+
|                       512 |
+---------------------------+
1 row in set (0.00 sec)

mysql 5.5 > show status like 'Handler_%';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| Handler_commit             | 1     |
| Handler_delete             | 0     |
| Handler_discover           | 0     |
| Handler_prepare            | 0     |
| Handler_read_first         | 0     |
| Handler_read_key           | 514   |
| Handler_read_last          | 0     |
| Handler_read_next          | 512   |
| Handler_read_prev          | 0     |

C:\dbs>c:\dbs\5.6\bin\mysql -uroot --port=3560 -p --prompt="mysql 5.6 > "
Enter password: ******
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 2
Server version: 5.6.26 Source distribution PULL 2015/06/05

mysql 5.6 > use test
Database changed
mysql 5.6 > SHOW VARIABLES LIKE "innodb_file_format";
+--------------------+-----------+
| Variable_name      | Value     |
+--------------------+-----------+
| innodb_file_format | Barracuda |
+--------------------+-----------+
1 row in set (0.00 sec)

mysql 5.6 >  flush tables; flush status;
Query OK, 0 rows affected (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql 5.6 > SELECT COUNT(DISTINCT `t1`.`id`) FROM `t1` INNER JOIN `t2` ON `t2`.`id` = `t1`.`f1` LEFT OUTER JOIN `t3` ON `t3`.`f1` = `t1`.`id` AND t3.f3 IS NULL AND `t3`.`f4` = 'Entry' LEFT OUTER JOIN `t3` `thumbnails_t3` ON `thumbnails_t3`.`f3` = `t3`.`id` WHE
RE `t1`.`f2` IS NULL AND `t1`.`f3` = 85260 AND (t1.f3 = 85260 AND t2.f2 IS NULL);
+---------------------------+
| COUNT(DISTINCT `t1`.`id`) |
+---------------------------+
|                       512 |
+---------------------------+
1 row in set (0.30 sec)

mysql 5.6 > show status like 'Handler_%';
+----------------------------+--------+
| Variable_name              | Value  |
+----------------------------+--------+
| Handler_commit             | 1      |
| Handler_delete             | 0      |
| Handler_discover           | 0      |
| Handler_external_lock      | 8      |
| Handler_mrr_init           | 0      |
| Handler_prepare            | 0      |
| Handler_read_first         | 0      |
| Handler_read_key           | 514    |
| Handler_read_last          | 0      |
| Handler_read_next          | 512512 |
| Handler_read_prev          | 0      |

mysql 5.6 >  flush tables; flush status;
Query OK, 0 rows affected (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql 5.6 > SELECT COUNT(DISTINCT `t1`.`id`) FROM `t1` INNER JOIN `t2` ON `t2`.`id` = `t1`.`f1` LEFT OUTER JOIN `t3` force index(f1) ON `t3`.`f1` = `t1`.`id` AND t3.f3 IS NULL AND `t3`.`f4` = 'Entry' LEFT OUTER JOIN `t3` `thumbnails_t3` ON `thumbnails_t3`.`f3`
 = `t3`.`id` WHERE `t1`.`f2` IS NULL AND `t1`.`f3` = 85260 AND (t1.f3 = 85260 AND t2.f2 IS NULL);
+---------------------------+
| COUNT(DISTINCT `t1`.`id`) |
+---------------------------+
|                       512 |
+---------------------------+
1 row in set (0.00 sec)

mysql 5.6 >  show status like 'Handler_%';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| Handler_commit             | 1     |
| Handler_delete             | 0     |
| Handler_discover           | 0     |
| Handler_external_lock      | 8     |
| Handler_mrr_init           | 0     |
| Handler_prepare            | 0     |
| Handler_read_first         | 0     |
| Handler_read_key           | 514   |
| Handler_read_last          | 0     |
| Handler_read_next          | 512   |
| Handler_read_prev          | 0     |

C:\dbs>c:\dbs\5.7\bin\mysql -uroot -p --port=3570 --prompt="mysql 5.7 > "
Enter password: ******
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 3
Server version: 5.7.8-rc Source distribution PULL 2015/06/05

mysql 5.7 > use test
Database changed
mysql 5.7 > SHOW VARIABLES LIKE "innodb_file_format";
+--------------------+-----------+
| Variable_name      | Value     |
+--------------------+-----------+
| innodb_file_format | Barracuda |
+--------------------+-----------+
1 row in set, 1 warning (0.00 sec)

mysql 5.7 >  flush tables; flush status;
Query OK, 0 rows affected (0.00 sec)

Query OK, 0 rows affected (0.00 sec)

mysql 5.7 > SELECT COUNT(DISTINCT `t1`.`id`) FROM `t1` INNER JOIN `t2` ON `t2`.`id` = `t1`.`f1` LEFT OUTER JOIN `t3` ON `t3`.`f1` = `t1`.`id` AND t3.f3 IS NULL AND `t3`.`f4` = 'Entry' LEFT OUTER JOIN `t3` `thumbnails_t3` ON `thumbnails_t3`.`f3` = `t3`.`id` WHE
RE `t1`.`f2` IS NULL AND `t1`.`f3` = 85260 AND (t1.f3 = 85260 AND t2.f2 IS NULL);
+---------------------------+
| COUNT(DISTINCT `t1`.`id`) |
+---------------------------+
|                       512 |
+---------------------------+
1 row in set (0.38 sec)

mysql 5.7 > show status like 'Handler_%';
+----------------------------+--------+
| Variable_name              | Value  |
+----------------------------+--------+
| Handler_commit             | 1      |
| Handler_delete             | 0      |
| Handler_discover           | 0      |
| Handler_external_lock      | 9      |
| Handler_mrr_init           | 0      |
| Handler_prepare            | 0      |
| Handler_read_first         | 1      |
| Handler_read_key           | 514    |
| Handler_read_last          | 0      |
| Handler_read_next          | 512512 |
| Handler_read_prev          | 0      |
| Handler_read_rnd           | 0      |
| Handler_read_rnd_next      | 26     |
| Handler_rollback           | 0      |
| Handler_savepoint          | 0      |
| Handler_savepoint_rollback | 0      |
| Handler_update             | 0      |
| Handler_write              | 0      |
+----------------------------+--------+
18 rows in set (0.00 sec)

EXPLAIN FORMAT=JSON  cost_info for the slow query:

    "cost_info": {
      "query_cost": "1212.09"
    },

For the fast query:

    "cost_info": {
      "query_cost": "2349.71"
    },

For t3 in the slow query:

          "cost_info": {
            "read_cost": "191.75",
            "eval_cost": "38.35",
            "prefix_cost": "875.62",
            "data_read_per_join": "196K"
          },

For t3 in the fast query:

          "cost_info": {
            "read_cost": "273.36",
            "eval_cost": "54.67",
            "prefix_cost": "1870.04",
            "data_read_per_join": "279K"
          },

Looks like these calculations wrong, at least overall query cost.

Posted by developer: Bug status updated to 'In progress'