List:Commits« Previous MessageNext Message »
From:Olav Sandstaa Date:August 3 2010 11:37am
Subject:Re: bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)
Bug#51457
View as plain text  
Hi Roy,

Thanks for great comments in both the code, commit message and bug 
report (by Guilhem). Based on the explanation in the bug report and 
commit message I was able to understand both what was wrong with the old 
code and how the change fixes the problem. The code change looks correct.

Some tiny comments about the test case (which you can feel free to ignore):

1. It should not be necessary to include this in new tests:

--disable_warnings
DROP TABLE IF EXISTS t0, t1, t2, t6, t8;
--enable_warnings

as all test cases are assumed to do proper clean up.

2. Instead of setting:

      SET @@default_storage_engine='innodb';

     I would have explicitly addeded "ENGINE=InnoDB" to the CREATE 
statements (that needed it) since this is done everywhere else in this 
test file.

OK to push the patch as it is.

Olav


On 08/03/10 09:42, Roy Lyseng wrote:
> #At file:///home/rl136806/mysql/repo/mysql-work2/ based on
> revid:roy.lyseng@stripped
>
>   3222 Roy Lyseng	2010-08-03
>        Bug#51457: Firstmatch semijoin strategy gives wrong results for
>                   certain query plans
>
>        When the optimizer selects a semijoin FirstMatch plan that has
>        non-correlated tables interspersed with inner tables, the "jumps"
>        are placed so that execution might become incorrect.
>        Example: A query with an outer correlated table ot, a non-correlated
>        table nt and two inner tables it1 and it2 are used in a query and the
>        optimizer chooses the FirstMatch join order ot - it1 - nt - it2.
>        The optimizer assigns a "jump" from table it2 to ot. This strategy will
>        omit duplicates resulting from table nt.
>
>        The fix assures that the jump from the last table in a consecutive
>        range of inner table goes to the most immediately preceeding outer
>        table (regardless of whether the outer table is correlated or not).
>        In this case, there are two consecutive ranges of inner tables:
>        {it1} and {it2}. In the first range, the last inner table is it1, the
>        jump should be to table ot. In the second range, the jump from it2
>        should be to nt.
>
>        It is currently possible to generate such query plans, hence the
>        bug fix includes some test cases. However, such plans are probably
>        generated due to a problem with the join optimizer cost model.
>        When this problem is fixed, it may be impossible to generate
>        such FirstMatch plans, unless one can assign different costs
>        to different tables, or another measure is used to force a specific
>        join order.
>
>        mysql-test/r/subselect_innodb.result
>          Test results for bug#51457.
>
>        mysql-test/t/subselect_innodb.test
>          Test case for bug#51457. Notice the above comment for test validity.
>          The test goes into subselect_innodb because it is required to use
>          tables with one row that are not hit by const table optimization.
>
>        sql/sql_select.cc
>          In setup_semijoin_dups_elimination(), in the case for FIRST_MATCH,
>          loop over the set of inner and non-correlated outer tables and assign
>          jump target to the last table in each consecutive range of inner
>          tables. The jump target should be the most immediately preceeding
>          outer table.
>
>      modified:
>        mysql-test/r/subselect_innodb.result
>        mysql-test/t/subselect_innodb.test
>        sql/sql_select.cc
> === modified file 'mysql-test/r/subselect_innodb.result'
> --- a/mysql-test/r/subselect_innodb.result	2010-06-19 13:22:14 +0000
> +++ b/mysql-test/r/subselect_innodb.result	2010-08-03 07:40:15 +0000
> @@ -392,3 +392,87 @@ and t2.a='1' AND t1.a=t3.b)>  0;
>   a
>   2
>   DROP TABLE t1,t2,t3;
> +#
> +# Bug#51457 Firstmatch semijoin strategy gives wrong results for
> +#           certain query plans
> +#
> +DROP TABLE IF EXISTS t0, t1, t2, t6, t8;
> +SET @@default_storage_engine='innodb';
> +SET
> @@optimizer_switch='semijoin=on,materialization=off,firstmatch=on,loosescan=off';
> +SET @@optimizer_join_cache_level=0;
> +CREATE TABLE t0(a INTEGER);
> +CREATE TABLE t1(a INTEGER);
> +INSERT INTO t1 VALUES(1);
> +CREATE TABLE t2(a INTEGER);
> +INSERT INTO t2 VALUES(5), (8);
> +CREATE TABLE t6(a INTEGER);
> +INSERT INTO t6 VALUES(7), (1), (0), (5), (1), (4);
> +CREATE TABLE t8(a INTEGER);
> +INSERT INTO t8 VALUES(1), (3), (5), (7), (9), (7), (3), (1);
> +EXPLAIN
> +SELECT *
> +FROM t2 AS nt2
> +WHERE 1 IN (SELECT it1.a
> +FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	PRIMARY	it1	ALL	NULL	NULL	NULL	NULL	1	Using where; FirstMatch
> +1	PRIMARY	nt2	ALL	NULL	NULL	NULL	NULL	2	
> +1	PRIMARY	it3	ALL	NULL	NULL	NULL	NULL	6	Using where; FirstMatch(nt2)
> +SELECT *
> +FROM t2 AS nt2
> +WHERE 1 IN (SELECT it1.a
> +FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
> +a
> +5
> +8
> +EXPLAIN
> +SELECT *
> +FROM t2 AS nt2, t8 AS nt4
> +WHERE 1 IN (SELECT it1.a
> +FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	PRIMARY	it1	ALL	NULL	NULL	NULL	NULL	1	Using where; FirstMatch
> +1	PRIMARY	nt2	ALL	NULL	NULL	NULL	NULL	2	
> +1	PRIMARY	it3	ALL	NULL	NULL	NULL	NULL	6	Using where; FirstMatch(nt2)
> +1	PRIMARY	nt4	ALL	NULL	NULL	NULL	NULL	8	
> +SELECT *
> +FROM t2 AS nt2, t8 AS nt4
> +WHERE 1 IN (SELECT it1.a
> +FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
> +a	a
> +5	1
> +5	3
> +5	5
> +5	7
> +5	9
> +5	7
> +5	3
> +5	1
> +8	1
> +8	3
> +8	5
> +8	7
> +8	9
> +8	7
> +8	3
> +8	1
> +EXPLAIN
> +SELECT *
> +FROM t0 AS ot1, t2 AS nt3
> +WHERE ot1.a IN (SELECT it2.a
> +FROM t1 AS it2 JOIN t8 AS it4 ON it2.a=it4.a);
> +id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
> +1	PRIMARY	ot1	ALL	NULL	NULL	NULL	NULL	1	
> +1	PRIMARY	it2	ALL	NULL	NULL	NULL	NULL	1	Using where; FirstMatch(ot1)
> +1	PRIMARY	nt3	ALL	NULL	NULL	NULL	NULL	2	
> +1	PRIMARY	it4	ALL	NULL	NULL	NULL	NULL	8	Using where; FirstMatch(nt3)
> +SELECT *
> +FROM t0 as ot1, t2 AS nt3
> +WHERE ot1.a IN (SELECT it2.a
> +FROM t1 AS it2 JOIN t8 AS it4 ON it2.a=it4.a);
> +a	a
> +DROP TABLE t0, t1, t2, t6, t8;
> +SET @@default_storage_engine=default;
> +SET @@optimizer_switch=default;
> +SET @@optimizer_join_cache_level=default;
> +# End of bug#51457
>
> === modified file 'mysql-test/t/subselect_innodb.test'
> --- a/mysql-test/t/subselect_innodb.test	2010-06-18 08:45:53 +0000
> +++ b/mysql-test/t/subselect_innodb.test	2010-08-03 07:40:15 +0000
> @@ -401,3 +401,71 @@ SELECT t1.* FROM t1 WHERE (SELECT COUNT(
>                              and t2.a='1' AND t1.a=t3.b)>  0;
>
>   DROP TABLE t1,t2,t3;
> +
> +--echo #
> +--echo # Bug#51457 Firstmatch semijoin strategy gives wrong results for
> +--echo #           certain query plans
> +--echo #
> +
> +--disable_warnings
> +DROP TABLE IF EXISTS t0, t1, t2, t6, t8;
> +--enable_warnings
> +
> +SET @@default_storage_engine='innodb';
> +SET
> @@optimizer_switch='semijoin=on,materialization=off,firstmatch=on,loosescan=off';
> +SET @@optimizer_join_cache_level=0;
> +
> +CREATE TABLE t0(a INTEGER);
> +
> +CREATE TABLE t1(a INTEGER);
> +INSERT INTO t1 VALUES(1);
> +
> +CREATE TABLE t2(a INTEGER);
> +INSERT INTO t2 VALUES(5), (8);
> +
> +CREATE TABLE t6(a INTEGER);
> +INSERT INTO t6 VALUES(7), (1), (0), (5), (1), (4);
> +
> +CREATE TABLE t8(a INTEGER);
> +INSERT INTO t8 VALUES(1), (3), (5), (7), (9), (7), (3), (1);
> +
> +EXPLAIN
> +SELECT *
> +FROM t2 AS nt2
> +WHERE 1 IN (SELECT it1.a
> +            FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
> +
> +SELECT *
> +FROM t2 AS nt2
> +WHERE 1 IN (SELECT it1.a
> +            FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
> +
> +EXPLAIN
> +SELECT *
> +FROM t2 AS nt2, t8 AS nt4
> +WHERE 1 IN (SELECT it1.a
> +            FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
> +
> +SELECT *
> +FROM t2 AS nt2, t8 AS nt4
> +WHERE 1 IN (SELECT it1.a
> +            FROM t1 AS it1 JOIN t6 AS it3 ON it1.a=it3.a);
> +
> +EXPLAIN
> +SELECT *
> +FROM t0 AS ot1, t2 AS nt3
> +WHERE ot1.a IN (SELECT it2.a
> +                FROM t1 AS it2 JOIN t8 AS it4 ON it2.a=it4.a);
> +
> +SELECT *
> +FROM t0 as ot1, t2 AS nt3
> +WHERE ot1.a IN (SELECT it2.a
> +                FROM t1 AS it2 JOIN t8 AS it4 ON it2.a=it4.a);
> +
> +DROP TABLE t0, t1, t2, t6, t8;
> +
> +SET @@default_storage_engine=default;
> +SET @@optimizer_switch=default;
> +SET @@optimizer_join_cache_level=default;
> +
> +--echo # End of bug#51457
>
> === modified file 'sql/sql_select.cc'
> --- a/sql/sql_select.cc	2010-07-30 07:32:20 +0000
> +++ b/sql/sql_select.cc	2010-08-03 07:40:15 +0000
> @@ -1509,9 +1509,26 @@ int setup_semijoin_dups_elimination(JOIN
>         {
>           JOIN_TAB *jump_to= tab - 1;
>           DBUG_ASSERT(tab->emb_sj_nest != NULL); // First table must be inner
> -        if (!tab->emb_sj_nest)
> -          jump_to= tab;         /// @todo fix this (BUG#51457)
> -        tab_end->do_firstmatch= jump_to;
> +        for (JOIN_TAB *j= tab; j<= tab_end; j++)
> +        {
> +          if (!j->emb_sj_nest)
> +          {
> +            /*
> +              Let last non-correlated table be jump target for
> +              subsequent inner tables.
> +            */
> +            jump_to= j;
> +          }
> +          else
> +          {
> +            /*
> +              Assign jump target for last table in a consecutive range of
> +              inner tables.
> +            */
> +            if (j == tab_end || !(j+1)->emb_sj_nest)
> +              j->do_firstmatch= jump_to;
> +          }
> +        }
>           i+= pos->n_sj_tables;
>           break;
>         }
>
>    
>
>
>
>    


Thread
bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)Bug#51457Roy Lyseng3 Aug
  • Re: bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)Bug#51457Guilhem Bichot3 Aug
  • Re: bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)Bug#51457Olav Sandstaa3 Aug
    • Re: bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)Bug#51457Roy Lyseng3 Aug