MySQL Bugs: #19895: No optimization of where clause subqueries rewritable as joins

Bug #19895	No optimization of where clause subqueries rewritable as joins
Submitted:	17 May 2006 22:41	Modified:	10 Jan 2013 13:14
Reporter:	Michael Del Monte	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	5.0.20, 6.0.7, 6.0.14	OS:	Windows (Windows XP)
Assigned to:		CPU Architecture:	Any

Description:
MySQL fails to optimize WHERE clause subqueries that could be rewritten as inner joins to temp tables of primary keys.  This results in extremely poor performance unless the subquery is explicitly rewritten as a join.

How to repeat:
On any table t having indexed column x, queries of the following type will have very poor performance, and EXPLAIN will show that both primary query and subquery use table scans, even though optimization should (at best) remove the subquery entirely and (at worst) reduce it to a temp table with a ref or eq_ref join:

select * from t where x in (select x from t group by x)
select * from t where x in (select distinct x from t)
select * from t where x in (select x from t)
select * from t where exists (select x from t as t2 where t.x=t2.x)

All of these should reduce to "select * from t"

Rewriting as an explicit join provides nearly the level of desired performance.   Although MySQL still fails to remove the subquery entirely, it does perform the join correctly:

select * from t inner join (select x from t group by x) t2 on t.x=t2.x

Suggested fix:
Improve the optimizer to detect reducible subqueries.

Thank you for a problem report. It is a well-known problem (no subqueries rewrite, bad determination if subqueries are dependent or not etc.). Work in progress. Will be fixed some day.

There is similar bug #23370

We still have this problem in 6.0.7 (to some extent):

C:\Program Files\MySQL\MySQL Server 5.0\bin>mysql -P3311 -uroot -proot test
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 17
Server version: 6.0.7-alpha-community MySQL Community Server (GPL)

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> drop table t;
Query OK, 0 rows affected (0.06 sec)

mysql> create table t (id int primary key, x int, key(x)) engine=MyISAM;
Query OK, 0 rows affected (0.05 sec)

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

mysql> explain select * from t where x in (select x from t group by x)\G
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: t
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 3
        Extra: Using where
*************************** 2. row ***************************
           id: 2
  select_type: SUBQUERY
        table: t
         type: index
possible_keys: NULL
          key: x
      key_len: 5
          ref: NULL
         rows: 3
        Extra: Using index
2 rows in set (0.05 sec)

mysql> explain select * from t where x in (select x from t)\G
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: t
         type: index
possible_keys: x
          key: x
      key_len: 5
          ref: NULL
         rows: 3
        Extra: Using index; LooseScan
*************************** 2. row ***************************
           id: 1
  select_type: PRIMARY
        table: t
         type: ALL
possible_keys: x
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 3
        Extra: Using where; Using join buffer
2 rows in set (0.01 sec)

mysql> explain select * from t where exists (select x from t as t2 where t.x=t2.
x)\G
*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: t
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 3
        Extra: Using where
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: t2
         type: ref
possible_keys: x
          key: x
      key_len: 5
          ref: test.t.x
         rows: 2
        Extra: Using index
2 rows in set (0.00 sec)

Only last case is still NOT optimized any better with 6.0.14 from bzr:

77-52-7-73:6.0-codebase 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 1
Server version: 6.0.14-alpha-debug Source distribution

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

mysql> drop table if exists t;
Query OK, 0 rows affected, 1 warning (0.01 sec)

mysql> create table t (id int primary key, x int, key(x)) engine=MyISAM;
Query OK, 0 rows affected (0.08 sec)

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

mysql> explain select * from t where x in (select x from t group by x);
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
|  1 | PRIMARY     | t     | ALL   | NULL          | NULL | NULL    | NULL |    3 | Using where |
|  2 | SUBQUERY    | t     | index | NULL          | x    | 5       | NULL |    3 | Using index |
+----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
2 rows in set (0.03 sec)

mysql> explain select * from t where x in (select x from t);
+----+-------------+-------+-------+---------------+------+---------+----------+------+------------------------+
| id | select_type | table | type  | possible_keys | key  | key_len | ref      | rows | Extra                  |
+----+-------------+-------+-------+---------------+------+---------+----------+------+------------------------+
|  1 | PRIMARY     | t     | index | x             | x    | 5       | NULL     |    3 | Using index; LooseScan |
|  1 | PRIMARY     | t     | ref   | x             | x    | 5       | test.t.x |    2 |                        |
+----+-------------+-------+-------+---------------+------+---------+----------+------+------------------------+
2 rows in set (0.00 sec)

mysql> explain select * from t where exists (select x from t as t2 where t.x=t2.x);
+----+--------------------+-------+------+---------------+------+---------+----------+------+-------------+
| id | select_type        | table | type | possible_keys | key  | key_len | ref      | rows | Extra       |
+----+--------------------+-------+------+---------------+------+---------+----------+------+-------------+
|  1 | PRIMARY            | t     | ALL  | NULL          | NULL | NULL    | NULL     |    3 | Using where |
|  2 | DEPENDENT SUBQUERY | t2    | ref  | x             | x    | 5       | test.t.x |    2 | Using index |
+----+--------------------+-------+------+---------------+------+---------+----------+------+-------------+
2 rows in set (0.00 sec)

Implemented in 5.6.8.