List:Commits« Previous MessageNext Message »
From:Roy Lyseng Date:July 30 2010 11:54am
Subject:bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)
Bug#51457
View as plain text  
#At file:///home/rl136806/mysql/repo/mysql-work2/ based on revid:roy.lyseng@stripped

 3222 Roy Lyseng	2010-07-30
      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. 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-07-30 11:54:24 +0000
@@ -392,3 +392,93 @@ 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 empty, ones, ot1, nt1, nt4, it1, it3, it4;
+SET @@default_storage_engine='innodb';
+SET @@optimizer_switch='semijoin=on,materialization=off,firstmatch=on,loosescan=off';
+SET @@optimizer_join_cache_level=0;
+CREATE TABLE empty(a INTEGER);
+CREATE TABLE ones(a INTEGER);
+INSERT INTO ones VALUES(1);
+CREATE TABLE it1(a INTEGER);
+INSERT INTO it1 VALUES(5), (8);
+CREATE TABLE it3(a INTEGER);
+INSERT INTO it3 VALUES(7), (1), (0), (5), (1), (4);
+CREATE TABLE it4(a INTEGER);
+INSERT INTO it4 VALUES(1), (3), (5), (7), (9), (7), (3), (1);
+CREATE TABLE ot1(a INTEGER);
+INSERT INTO ot1 select * from it1;
+CREATE TABLE nt1(a INTEGER);
+INSERT INTO nt1 select * from it1;
+CREATE TABLE nt4(a INTEGER);
+INSERT INTO nt4 select * from it4;
+EXPLAIN
+SELECT *
+FROM nt1 AS nt2
+WHERE 1 IN (SELECT it1.a
+FROM ones AS it1 JOIN 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 nt1 AS nt2
+WHERE 1 IN (SELECT it1.a
+FROM ones AS it1 JOIN it3 ON it1.a=it3.a);
+a
+5
+8
+EXPLAIN
+SELECT *
+FROM nt1 AS nt2, nt4
+WHERE 1 IN (SELECT it1.a
+FROM ones AS it1 JOIN 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 nt1 AS nt2, nt4
+WHERE 1 IN (SELECT it1.a
+FROM ones AS it1 JOIN 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 empty as ot1, nt1 AS nt3
+WHERE ot1.a IN (SELECT it2.a
+FROM ones AS it2 JOIN 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 empty as ot1, nt1 AS nt3
+WHERE ot1.a IN (SELECT it2.a
+FROM ones AS it2 JOIN it4 ON it2.a=it4.a);
+a	a
+DROP TABLE  empty, ones, ot1, nt1, nt4, it1, it3, it4;
+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-07-30 11:54:24 +0000
@@ -401,3 +401,80 @@ 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 empty, ones, ot1, nt1, nt4, it1, it3, it4;
+--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 empty(a INTEGER);
+
+CREATE TABLE ones(a INTEGER);
+INSERT INTO ones VALUES(1);
+
+CREATE TABLE it1(a INTEGER);
+INSERT INTO it1 VALUES(5), (8);
+
+CREATE TABLE it3(a INTEGER);
+INSERT INTO it3 VALUES(7), (1), (0), (5), (1), (4);
+
+CREATE TABLE it4(a INTEGER);
+INSERT INTO it4 VALUES(1), (3), (5), (7), (9), (7), (3), (1);
+
+CREATE TABLE ot1(a INTEGER);
+INSERT INTO ot1 select * from it1;
+
+CREATE TABLE nt1(a INTEGER);
+INSERT INTO nt1 select * from it1;
+
+CREATE TABLE nt4(a INTEGER);
+INSERT INTO nt4 select * from it4;
+
+EXPLAIN
+SELECT *
+FROM nt1 AS nt2
+WHERE 1 IN (SELECT it1.a
+            FROM ones AS it1 JOIN it3 ON it1.a=it3.a);
+
+SELECT *
+FROM nt1 AS nt2
+WHERE 1 IN (SELECT it1.a
+            FROM ones AS it1 JOIN it3 ON it1.a=it3.a);
+
+EXPLAIN
+SELECT *
+FROM nt1 AS nt2, nt4
+WHERE 1 IN (SELECT it1.a
+            FROM ones AS it1 JOIN it3 ON it1.a=it3.a);
+
+SELECT *
+FROM nt1 AS nt2, nt4
+WHERE 1 IN (SELECT it1.a
+            FROM ones AS it1 JOIN it3 ON it1.a=it3.a);
+
+EXPLAIN
+SELECT *
+FROM empty as ot1, nt1 AS nt3
+WHERE ot1.a IN (SELECT it2.a
+                FROM ones AS it2 JOIN it4 ON it2.a=it4.a);
+
+SELECT *
+FROM empty as ot1, nt1 AS nt3
+WHERE ot1.a IN (SELECT it2.a
+                FROM ones AS it2 JOIN it4 ON it2.a=it4.a);
+
+DROP TABLE  empty, ones, ot1, nt1, nt4, it1, it3, it4;
+
+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-07-30 11:54:24 +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;
       }


Attachment: [text/bzr-bundle] bzr/roy.lyseng@oracle.com-20100730115424-2ynjt8sx7tu8aen9.bundle
Thread
bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)Bug#51457Roy Lyseng30 Jul
  • Re: bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)Bug#51457Guilhem Bichot30 Jul
    • Re: bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)Bug#51457Roy Lyseng31 Jul
Re: bzr commit into mysql-next-mr-opt-backporting branch (roy.lyseng:3222)Bug#51457Guilhem Bichot30 Jul