MySQL Bugs: #16393: No index used on outer table of nested left join

Bug #16393	No index used on outer table of nested left join
Submitted:	12 Jan 2006 3:03	Modified:	2 Feb 2006 0:49
Reporter:	Kolbe Kegel	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	5.0.18	OS:	Linux (Linux)
Assigned to:	Sergey Petrunya	CPU Architecture:	Any

Description:
No index is used on the outer table (t2) of an nested left join of this form:

select * from t1 left join (t2 left join t3 using (c) ) using (c) where t1.a='x';

How to repeat:
Execute the uploaded .SQL file.

Suggested fix:
It should be possible to use an index for such a query by the following steps:

 1) Satisfy WHERE clause against t1
 2) Gather values from t1 that satisfy the join condition
 3) Gather values from t2 filtered against list from step 2
 4) Execute nested join using rows from 3
 5) Execute outer join using rows from 4

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/1060

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/1061

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/1065

The fix has been pushed into 5.0.19 tree.

Notes for the changelog:
The optimizer could miss possible ways to construct 'ref' access methods for tables inside nested outer joins from nested join's ON condition.

(in more detail:
For a non-simplifable nested join in form  
some_tables LEFT JOIN (t_1 JOIN t_2 ...) ON (t_1.key=somefunc(some_tables) AND ... )
(*)

the optimizer could(**) miss possible ways to use 'ref' access method on "t_1.somekey=somefunc(some_tables)".

)

(*) condition can actually have any form, but we assume that ref-optimizer is able to convert it to the specified form.

(**) The omission of ref accesses is deterministic, it is dependent on what kinds of joins are done within the nested join, and, for some kinds of joins, on the order of the tables in the query.

Documented in 5.0.19 changelog:

      <listitem>
        <para>
          Certain nested LEFT JOIN operations were not properly
          optimized. (Bug #16393)
        </para>
      </listitem>