Bug #40315 "Not exists" optimization doesn't use "Using index"
Submitted: 24 Oct 2008 18:40 Modified: 26 Oct 2008 7:12
Reporter: Sergey Petrunya Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Optimizer Severity:S4 (Feature request)
Version:5.1.29, 6.0.6 OS:Any
Assigned to: CPU Architecture:Any

[24 Oct 2008 18:40] Sergey Petrunya
Description:
LEFT JOIN's "Not exists" optimization doesn't use "Using index". The problem applies to queries in form

SELECT * FROM t1 LEFT JOIN t2 ON t2.key=t1.col WHERE t2.not_null_column IS NULL

Here we don't actually need the value of t2.not_null_column as "t2.not_null_column IS NULL" only means that outer join has no matches. 

How to repeat:
CREATE TABLE t1 (id int PRIMARY KEY, a varchar(8));
CREATE TABLE t2 (id int NOT NULL, b int NOT NULL, INDEX idx(id));
INSERT INTO t1 VALUES
  (1,'aaaaaaa'), (5,'eeeeeee'), (4,'ddddddd'), (2,'bbbbbbb'), (3,'ccccccc');
INSERT INTO t2 VALUES
  (3,10), (2,20), (5,30), (3,20), (5,10), (3,40), (3,30), (2,10), (2,40);

mysql> EXPLAIN SELECT t1.id, a FROM t1 LEFT JOIN t2 ON t1.id=t2.id WHERE t2.b IS NULL\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 5
        Extra: 
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: t2
         type: ref
possible_keys: idx
          key: idx
      key_len: 4
          ref: j55.t1.id
         rows: 2
        Extra: Using where; Not exists
2 rows in set (0.01 sec)

Suggested fix:
Make "Not EXISTS" work together with "Using index".
[26 Oct 2008 7:12] Valeriy Kravchuk
Verified as described with 6.0.6.