MySQL Bugs: #57024: Serious performance issue with an outer join

Bug #57024	Serious performance issue with an outer join
Submitted:	26 Sep 2010 4:44	Modified:	29 Sep 2010 12:11
Reporter:	Igor Babaev	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.1	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
You can observe a serious performance issues for outer join queries with the following tables:

create table t1 (a int);
insert into t1 values (NULL), (NULL), (NULL), (NULL);
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 values (4), (2), (1), (3);

create table t2 like t1;
insert into t2 select if(t1.a is null, 10, t1.a) from t1;

create table t3 (a int, b int, index idx(a));  
insert into t3 values (1, 100), (3, 301), (4, 402), (1, 102), (1, 101);

If you execute the query

  select sum(t3.b) from t1 left join t3 on t3.a=t1.a and t1.a is not null

it will take much less time than the execution of the query

  select sum(t3.b) from t2 left join t3 on t3.a=t2.a and t2.a <> 10

though the tables t1 and t2 are similar and whenever a row of t1 contains null
the corresponding row of t2 contains 10:

mysql> select sum(t3.b) from t1 left join t3 on t3.a=t1.a and t1.a is not null;
+-----------+
| sum(t3.b) |
+-----------+
|      1006 |
+-----------+
1 row in set (1.76 sec)

mysql> select sum(t3.b) from t2 left join t3 on t3.a=t2.a and t2.a <> 10;
+-----------+
| sum(t3.b) |
+-----------+
|      1006 |
+-----------+
1 row in set (10.36 sec)

The following statistics explains why it happens:

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

mysql> select sum(t3.b) from t1 left join t3 on t3.a=t1.a and t1.a is not null;
+-----------+
| sum(t3.b) |
+-----------+
|      1006 |
+-----------+
1 row in set (1.77 sec)

mysql> show status like "handler_read%";
+-----------------------+---------+
| Variable_name         | Value   |
+-----------------------+---------+
| Handler_read_first    | 0       |
| Handler_read_key      | 4       |
| Handler_read_next     | 5       |
| Handler_read_prev     | 0       |
| Handler_read_rnd      | 0       |
| Handler_read_rnd_next | 1048581 |
+-----------------------+---------+
6 rows in set (0.00 sec)

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

mysql> select sum(t3.b) from t2 left join t3 on t3.a=t2.a and t2.a <> 10;
+-----------+
| sum(t3.b) |
+-----------+
|      1006 |
+-----------+
1 row in set (10.34 sec)

mysql> show status like "handler_read%";
+-----------------------+---------+
| Variable_name         | Value   |
+-----------------------+---------+
| Handler_read_first    | 0       |
| Handler_read_key      | 1048580 |
| Handler_read_next     | 5       |
| Handler_read_prev     | 0       |
| Handler_read_rnd      | 0       |
| Handler_read_rnd_next | 1048581 |
+-----------------------+---------+
6 rows in set (0.01 sec)

How to repeat:
The following commands reproduce the problem:

create table t1 (a int);
insert into t1 values (NULL), (NULL), (NULL), (NULL);
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 select * from t1; 
insert into t1 values (4), (2), (1), (3);

create table t2 like t1;
insert into t2 select if(t1.a is null, 10, t1.a) from t1;

create table t3 (a int, b int, index idx(a));  
insert into t3 values (1, 100), (3, 301), (4, 402), (1, 102), (1, 101);

flush status;
select sum(t3.b) from t1 left join t3 on t3.a=t1.a and t1.a is not null;
show status like "handler_read%";
flush status;
select sum(t3.b) from t2 left join t3 on t3.a=t2.a and t2.a <> 10;
show status like "handler_read%";

Verified with current mysql-5.1 from bzr on Mac OS X:

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 2
Server version: 5.1.52-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> create table t1 (a int);
Query OK, 0 rows affected (0.06 sec)

mysql> insert into t1 values (NULL), (NULL), (NULL), (NULL);
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 8 rows affected (0.00 sec)
Records: 8  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 16 rows affected (0.01 sec)
Records: 16  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 32 rows affected (0.00 sec)
Records: 32  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 64 rows affected (0.00 sec)
Records: 64  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 128 rows affected (0.00 sec)
Records: 128  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 256 rows affected (0.00 sec)
Records: 256  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 512 rows affected (0.01 sec)
Records: 512  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 1024 rows affected (0.00 sec)
Records: 1024  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 2048 rows affected (0.01 sec)
Records: 2048  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 4096 rows affected (0.02 sec)
Records: 4096  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 8192 rows affected (0.03 sec)
Records: 8192  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 16384 rows affected (0.05 sec)
Records: 16384  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 32768 rows affected (0.10 sec)
Records: 32768  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 65536 rows affected (0.22 sec)
Records: 65536  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 131072 rows affected (0.44 sec)
Records: 131072  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 262144 rows affected (0.88 sec)
Records: 262144  Duplicates: 0  Warnings: 0

mysql> insert into t1 select * from t1; 
Query OK, 524288 rows affected (1.67 sec)
Records: 524288  Duplicates: 0  Warnings: 0

mysql> insert into t1 values (4), (2), (1), (3);
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> 
mysql> create table t2 like t1;
Query OK, 0 rows affected (0.05 sec)

mysql> insert into t2 select if(t1.a is null, 10, t1.a) from t1;
Query OK, 1048580 rows affected (2.59 sec)
Records: 1048580  Duplicates: 0  Warnings: 0

mysql> create table t3 (a int, b int, index idx(a));  
Query OK, 0 rows affected (0.06 sec)

mysql> insert into t3 values (1, 100), (3, 301), (4, 402), (1, 102), (1, 101);
Query OK, 5 rows affected (0.00 sec)
Records: 5  Duplicates: 0  Warnings: 0

mysql>  select sum(t3.b) from t1 left join t3 on t3.a=t1.a and t1.a is not null;
+-----------+
| sum(t3.b) |
+-----------+
|      1006 |
+-----------+
1 row in set (1.40 sec)

mysql>  select sum(t3.b) from t2 left join t3 on t3.a=t2.a and t2.a <> 10;
+-----------+
| sum(t3.b) |
+-----------+
|      1006 |
+-----------+
1 row in set (7.00 sec)

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

mysql>  select sum(t3.b) from t1 left join t3 on t3.a=t1.a and t1.a is not null;
+-----------+
| sum(t3.b) |
+-----------+
|      1006 |
+-----------+
1 row in set (1.43 sec)

mysql>  show status like "handler_read%";
+-----------------------+---------+
| Variable_name         | Value   |
+-----------------------+---------+
| Handler_read_first    | 0       |
| Handler_read_key      | 4       |
| Handler_read_next     | 5       |
| Handler_read_prev     | 0       |
| Handler_read_rnd      | 0       |
| Handler_read_rnd_next | 1048581 |
+-----------------------+---------+
6 rows in set (0.00 sec)

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

mysql>  select sum(t3.b) from t2 left join t3 on t3.a=t2.a and t2.a <> 10;
+-----------+
| sum(t3.b) |
+-----------+
|      1006 |
+-----------+
1 row in set (7.08 sec)

mysql>  show status like "handler_read%";
+-----------------------+---------+
| Variable_name         | Value   |
+-----------------------+---------+
| Handler_read_first    | 0       |
| Handler_read_key      | 1048580 |
| Handler_read_next     | 5       |
| Handler_read_prev     | 0       |
| Handler_read_rnd      | 0       |
| Handler_read_rnd_next | 1048581 |
+-----------------------+---------+
6 rows in set (0.00 sec)

mysql> explain select sum(t3.b) from t1 left join t3 on t3.a=t1.a and t1.a is not null;
+----+-------------+-------+------+---------------+------+---------+-----------+---------+-------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows    | Extra |
+----+-------------+-------+------+---------------+------+---------+-----------+---------+-------+
|  1 | SIMPLE      | t1    | ALL  | NULL          | NULL | NULL    | NULL      | 1048580 |       |
|  1 | SIMPLE      | t3    | ref  | idx           | idx  | 5       | test.t1.a |       2 |       |
+----+-------------+-------+------+---------------+------+---------+-----------+---------+-------+
2 rows in set (0.00 sec)

mysql> explain select sum(t3.b) from t2 left join t3 on t3.a=t2.a and t2.a <> 10;
+----+-------------+-------+------+---------------+------+---------+-----------+---------+-------+
| id | select_type | table | type | possible_keys | key  | key_len | ref       | rows    | Extra |
+----+-------------+-------+------+---------------+------+---------+-----------+---------+-------+
|  1 | SIMPLE      | t2    | ALL  | NULL          | NULL | NULL    | NULL      | 1048580 |       |
|  1 | SIMPLE      | t3    | ref  | idx           | idx  | 5       | test.t2.a |       2 |       |
+----+-------------+-------+------+---------------+------+---------+-----------+---------+-------+
2 rows in set (0.00 sec)

triage: previous comment should ave read "...what the W3 is"
SRMRTBD (risk/effort not trivial -  kostja)