MySQL Bugs: #49952: Inner tables in subquery outer join is not detected as constant tables

Bug #49952	Inner tables in subquery outer join is not detected as constant tables
Submitted:	28 Dec 2009 8:44	Modified:	23 Nov 2010 3:35
Reporter:	Øystein Grøvlen	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S3 (Non-critical)
Version:	6.0	OS:	Any
Assigned to:	Øystein Grøvlen	CPU Architecture:	Any
Tags:	constant table, optimizer_switch, semijoin, subquery

Description:
An empty or one-row table on the right side of a left outer join in an IN-subquery is not detected to be a constant table and pulled out of the semijoin.

Example where t2 and t3 contains one row:

EXPLAIN SELECT * FROM t1 WHERE (11) IN 
(SELECT t3.i FROM t2 LEFT JOIN t3 ON t2.i=t3.i);
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	t2	system	NULL	NULL	NULL	NULL	1	
1	PRIMARY	t3	ALL	NULL	NULL	NULL	NULL	1	Using where; FirstMatch(t2)
1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using join buffer

Note that with an inner join both tables are detected as constant tables:

EXPLAIN SELECT * FROM t1 WHERE (i) IN 
(SELECT t2.i FROM t2 JOIN t3 ON t2.i=t3.i);
id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	PRIMARY	t2	system	NULL	NULL	NULL	NULL	1	
1	PRIMARY	t3	system	NULL	NULL	NULL	NULL	1	
1	PRIMARY	t1	ALL	NULL	NULL	NULL	NULL	2	Using where

NOTE: This is not just an optimization issues since by doing this correctly, Bug#46692, Bug#48868, and Bug#49632 would become irrelevant in some, but not all, scenarios.

How to repeat:
CREATE TABLE t1 (i INTEGER);
INSERT INTO t1 VALUES (1);
INSERT INTO t1 VALUES (2);
CREATE TABLE t2 (i INTEGER);
INSERT INTO t2 VALUES(1);
CREATE TABLE t3 (i INTEGER);
INSERT INTO t3 VALUES(1);
EXPLAIN SELECT * FROM t1 WHERE (11) IN 
(SELECT t3.i FROM t2 LEFT JOIN t3 ON t2.i=t3.i);

Suggested fix:
Make sure to consider inner tables of outer join when detecting constant tables.

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/102323

2935 oystein.grovlen@sun.com	2010-03-04
      Bug#49952 - Inner tables in subquery outer join is not detected as constant tables
      
      Problem: If a subquery that has been converted to semijoin contains 
      an outer join, constant table optimization is not always done.  
      This happens because the necessary test to skip constant table 
      optimization in case of nested outer join gives false hits for 
      semijoin nests.
      
      Fix: Introduce a new function TABLE_LIST::in_nested_join() that correctly
      identifies when the table belongs to a nested join, and use this function
      where special handling of nested joins are required.  Also replaced correct
      tests for nested join with this function. 
      
      Also, fixed a check for dependence on const tables that was not
      based on the set of all const tables, but just the set of tables with
      one row.  Hence, it was not always detected that constant table
      optimization could be used for inner tables of outer joins when the 
      outer table was empty.
     @ mysql-test/r/subselect_sj.result
        Updated result file with added explain output.
     @ mysql-test/r/subselect_sj_jcl6.result
        Updated result file with added explain output.
        
        Also includes one correction of a query result since constant table optimization hides bug 50358 for this particular case.
     @ mysql-test/t/subselect_sj.test
        Added explain output for tests on constant tables in outer joins of 
        IN-subqueries to verify that changes results in more constant table optimizations.
        
        Because of the additional constant table optimizations, bug 50358 does no
        longer apply to the query in subselect_sj, and I have removed the comment.
     @ sql/sql_select.cc
        Constant table optimization was not always performed on tables in semi-join
        nests because they were handled as if they were in a nested join.
        Fixed by using new function TABLE_LIST::in_nested_join() to correctly detect
        when constant table optimization could not be done.
        
        Also replaced other checks for nested join with this function.
        
        Checks for dependence on constant tables is now done against
        join->const_table_map, not found_const_table_map which does not 
        contain empty tables.
        
        Some minor modifications to code since it is not necessary to
        have a separate variable for TABLE_LIST::embedding when it is not
        directly accessed that much anymore.
     @ sql/table.h
        Added funtion TABLE_LIST::in_nested_join() that can be used to check
        whether the table is part of a join nest.

Assigning Evgeny as reviewern since he originally suggested this approach.

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/102687

3799 oystein.grovlen@sun.com	2010-03-09
      Bug#49952 - Inner tables in subquery outer join is not detected as constant tables
      
      Problem: If a subquery that has been converted to semijoin contains 
      an outer join, constant table optimization is not always done.  
      This happens because the necessary test to skip constant table 
      optimization in case of nested outer join gives false hits for 
      semijoin nests.
      
      Fix: Introduce a new function TABLE_LIST::in_outer_join_nest() that correctly
      identifies when the table belongs to a nested join, and use this function
      where special handling of nested joins are required.  Also replaced correct
      tests for nested join with this function. 
      
      Also, fixed a check for dependence on const tables that was not
      based on the set of all const tables, but just the set of tables with
      one row.  Hence, it was not always detected that constant table
      optimization could be used for inner tables of outer joins when the 
      outer table was empty.
     @ mysql-test/r/subselect_sj.result
        Updated result file with added explain output.
     @ mysql-test/r/subselect_sj_jcl6.result
        Updated result file with added explain output.
        
        Also includes one correction of a query result since constant table optimization hides bug 50358 for this particular case.
     @ mysql-test/t/subselect_sj.test
        Added explain output for tests on constant tables in outer joins of 
        IN-subqueries to verify that changes results in more constant table optimizations.
        
        Because of the additional constant table optimizations, bug 50358 does no
        longer apply to the query in subselect_sj, and the comment have been removed.
     @ sql/sql_select.cc
        Constant table optimization was not always performed on tables in semi-join
        nests because they were handled as if they were in a nested join.
        Fixed by using new function TABLE_LIST::in_outer_join_nest() to correctly detect
        when constant table optimization could not be done.
        
        Also replaced other checks for nested join with this function.
        
        Checks for dependence on constant tables is now done against
        join->const_table_map, not found_const_table_map which does not 
        contain empty tables.
        
        Some minor modifications to code since it is not necessary to
        have a separate variable for TABLE_LIST::embedding when it is not
        directly accessed that much anymore.
     @ sql/table.h
        Added funtion TABLE_LIST::in_outer_join_nest() that can be used to check
        whether the table is part of a join nest.

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/103704

3832 oystein.grovlen@sun.com	2010-03-18
      Bug#49952 - Inner tables in subquery outer join is not detected as constant tables
      
      Problem: If a subquery that has been converted to semijoin contains 
      an outer join, constant table optimization is not always done.  
      This happens because the necessary test to skip constant table 
      optimization in case of nested outer join gives false hits for 
      semijoin nests.
      
      Fix: Introduce a new function TABLE_LIST::in_outer_join_nest() that correctly
      identifies when the table belongs to a nested join, and use this function
      where special handling of nested joins are required.  Also replaced correct
      tests for nested join with this function. 
      
      Also, fixed a check for dependence on const tables that was not
      based on the set of all const tables, but just the set of tables with
      one row.  Hence, it was not always detected that constant table
      optimization could be used for inner tables of outer joins when the 
      outer table was empty.
     @ mysql-test/r/subselect_sj.result
        Updated result file with added explain output.
     @ mysql-test/r/subselect_sj_jcl6.result
        Updated result file with added explain output.
        
        Also includes one correction of a query result since constant table optimization hides bug 50358 for this particular case.
     @ mysql-test/t/subselect_sj.test
        Added explain output for tests on constant tables in outer joins of 
        IN-subqueries to verify that changes results in more constant table optimizations.
        
        Because of the additional constant table optimizations, bug 50358 does no
        longer apply to the query in subselect_sj, and the comment have been removed.
     @ sql/sql_select.cc
        Constant table optimization was not always performed on tables in semi-join
        nests because they were handled as if they were in a nested join.
        Fixed by using new function TABLE_LIST::in_outer_join_nest() to correctly detect
        when constant table optimization could not be done.
        
        Also replaced other checks for nested join with this function.
        
        Checks for dependence on constant tables is now done against
        join->const_table_map, not found_const_table_map which does not 
        contain empty tables.
        
        Some minor modifications to code since it is not necessary to
        have a separate variable for TABLE_LIST::embedding when it is not
        directly accessed that much anymore.
     @ sql/table.h
        Added funtion TABLE_LIST::in_outer_join_nest() that can be used to check
        whether the table is part of a join nest.
        
        Update Copyright notice.

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/105925

3875 oystein.grovlen@sun.com	2010-04-17
      Bug#49952 - Inner tables in subquery outer join is not detected as constant tables
      
      Problem: If a subquery that has been converted to semijoin contains 
      an outer join, constant table optimization is not always done.  
      This happens because the necessary test to skip constant table 
      optimization in case of nested outer join gives false hits for 
      semijoin nests.
      
      Fix: Introduce a new function TABLE_LIST::in_outer_join_nest() that correctly
      identifies when the table belongs to a nested join, and use this function
      where special handling of nested joins are required.  Also replaced correct
      tests for nested join with this function. 
      
      Also, fixed a check for dependence on const tables that was not
      based on the set of all const tables, but just the set of tables with
      one row.  Hence, it was not always detected that constant table
      optimization could be used for inner tables of outer joins when the 
      outer table was empty.
     @ mysql-test/r/subselect_sj.result
        Updated result file with added explain output.
     @ mysql-test/r/subselect_sj_jcl6.result
        Updated result file with added explain output.
        
        Also includes one correction of a query result since constant table optimization hides bug 50358 for this particular case.
     @ mysql-test/t/subselect_sj.test
        Added explain output for tests on constant tables in outer joins of 
        IN-subqueries to verify that changes results in more constant table optimizations.
        
        Because of the additional constant table optimizations, bug 50358 does no
        longer apply to the query in subselect_sj, and the comment have been removed.
     @ sql/sql_select.cc
        Constant table optimization was not always performed on tables in semi-join
        nests because they were handled as if they were in a nested join.
        Fixed by using new function TABLE_LIST::in_outer_join_nest() to correctly detect
        when constant table optimization could not be done.
        
        Also replaced other checks for nested join with this function.
        
        Checks for dependence on constant tables is now done against
        join->const_table_map, not found_const_table_map which does not 
        contain empty tables.
        
        Some minor modifications to code since it is not necessary to
        have a separate variable for TABLE_LIST::embedding when it is not
        directly accessed that much anymore.
     @ sql/table.h
        Added funtion TABLE_LIST::in_outer_join_nest() that can be used to check
        whether the table is part of a join nest.
        
        Update Copyright notice.

Patch pushed to mysql-6.0-codebase-bugfixing with revision oystein.grovlen@sun.com-20100417063402-gmwfvs9mmu2u714k

Pushed into 6.0.14-alpha (revid:alik@sun.com-20100427094135-5s49ecp3ckson6e2) (version source revid:alik@sun.com-20100427093843-uekr85qkd7orx12t) (merge vers: 6.0.14-alpha) (pib:16)

Noted in 6.0.14 changelog.

If a subquery that had been converted to a semijoin contained an
outer join, constant table optimization was not always done.

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/108503

3181 oystein.grovlen@sun.com	2010-05-18
      Bug#49952 - Inner tables in subquery outer join is not detected as constant tables
      
      (Backporting of oystein.grovlen@sun.com-20100417063402-gmwfvs9mmu2u714k)
      
      Problem: If a subquery that has been converted to semijoin contains 
      an outer join, constant table optimization is not always done.  
      This happens because the necessary test to skip constant table 
      optimization in case of nested outer join gives false hits for 
      semijoin nests.
      
      Fix: Introduce a new function TABLE_LIST::in_outer_join_nest() that correctly
      identifies when the table belongs to a nested join, and use this function
      where special handling of nested joins are required.  Also replaced correct
      tests for nested join with this function. 
      
      Also, fixed a check for dependence on const tables that was not
      based on the set of all const tables, but just the set of tables with
      one row.  Hence, it was not always detected that constant table
      optimization could be used for inner tables of outer joins when the 
      outer table was empty.
     @ mysql-test/r/subselect_sj.result
        Updated result file with added explain output.
     @ mysql-test/r/subselect_sj_jcl6.result
        Updated result file with added explain output.
        
        Also includes one correction of a query result since constant table optimization hides bug 50358 for this particular case.
     @ mysql-test/t/subselect_sj.test
        Added explain output for tests on constant tables in outer joins of 
        IN-subqueries to verify that changes results in more constant table optimizations.
        
        Because of the additional constant table optimizations, bug 50358 does no
        longer apply to the query in subselect_sj, and the comment have been removed.
     @ sql/sql_select.cc
        Constant table optimization was not always performed on tables in semi-join
        nests because they were handled as if they were in a nested join.
        Fixed by using new function TABLE_LIST::in_outer_join_nest() to correctly detect
        when constant table optimization could not be done.
        
        Also replaced other checks for nested join with this function.
        
        Checks for dependence on constant tables is now done against
        join->const_table_map, not found_const_table_map which does not 
        contain empty tables.
        
        Some minor modifications to code since it is not necessary to
        have a separate variable for TABLE_LIST::embedding when it is not
        directly accessed that much anymore.
     @ sql/table.h
        Added funtion TABLE_LIST::in_outer_join_nest() that can be used to check
        whether the table is part of a join nest.
        
        Update Copyright notice.

Pushed into mysql-next-mr (revid:alik@sun.com-20100816062819-bluwgdq8q4xysmlg) (version source revid:alik@sun.com-20100816062612-enatdwnv809iw3s9) (pib:20)

Pushed into mysql-trunk 5.6.99-m5 (revid:alexander.nozdrin@oracle.com-20101113155825-czmva9kg4n31anmu) (version source revid:vasil.dimov@oracle.com-20100629074804-359l9m9gniauxr94) (merge vers: 5.6.99-m4) (pib:21)

Bug does not appear in any released 5.6.x version. No 5.6.1 changelog entry needed.