MySQL Lists are EOL. Please join:

List:Commits« Previous MessageNext Message »
From:Sergey Glukhov Date:May 27 2010 3:13pm
Subject:bzr commit into mysql-5.1-bugteam branch (Sergey.Glukhov:3398)
Bug#52005
View as plain text  
#At file:///home/gluh/MySQL/mysql-5.1-bugteam/ based on revid:alexey.kopytov@stripped

 3398 Sergey Glukhov	2010-05-27
      Bug#52005 'JOIN_TAB->dependent' may be incorrectly propageted for multilevel outer joins
      There are two problems:
      1. In simplify_joins function we calculate table dependencies. If STRAIGHT_JOIN hint
      is used for whole SELECT we do not count it and as result some dependendecies
      might be lost. It leads to incorrect table order which is returned by
      join_tab_cmp_straight() function.
      2. make_join_statistics() calculate the transitive closure for relations a particular
      JOIN_TAB is 'dependent on'.
      We aggregate the dependent table_map of a JOIN_TAB by adding dependencies from other
      tables which we depend on. However, this may also cause new dependencies to be
      available after we have completed processing a certain JOIN_TAB.
      Both these problems affect condition pushdown and as result condition might be pushed
      into wrong table which leads to crash or even omitted which leads to wrong result.
      The fix:
      1. Use modified 'transitive closure' algorithm provided by Ole John Aske
      2. Update table dependences in simplify_joins according to 
         global STRAIGHT_JOIN hint.
      Note: the patch also fixes bugs 46091 & 51492
     @ mysql-test/r/join_outer.result
        test case
     @ mysql-test/t/join_outer.test
        test case
     @ sql/sql_select.cc
        1. Use modified 'transitive closure' algorithm provided by Ole John Aske
        2. Update table dependences in simplify_joins according to 
           global STRAIGHT_JOIN hint.

    modified:
      mysql-test/r/join_outer.result
      mysql-test/t/join_outer.test
      sql/sql_select.cc
=== modified file 'mysql-test/r/join_outer.result'
--- a/mysql-test/r/join_outer.result	2010-05-06 08:59:28 +0000
+++ b/mysql-test/r/join_outer.result	2010-05-27 15:13:53 +0000
@@ -1338,4 +1338,63 @@ id	select_type	table	type	possible_keys	
 1	SIMPLE	tt9	ALL	NULL	NULL	NULL	NULL	2	Using join buffer
 SET optimizer_search_depth = DEFAULT;
 DROP TABLE t1;
+#
+# Bug#46091 STRAIGHT_JOIN + RIGHT JOIN returns different result
+#
+CREATE TABLE t1 (f1 INT NOT NULL);
+INSERT INTO t1 VALUES (9),(0);
+CREATE TABLE t2 (f1 INT NOT NULL);
+INSERT INTO t2 VALUES
+(5),(3),(0),(3),(1),(0),(1),(7),(1),(0),(0),(8),(4),(9),(0),(2),(0),(8),(5),(1);
+SELECT STRAIGHT_JOIN COUNT(*) FROM t1 TA1
+RIGHT JOIN t2 TA2 JOIN t2 TA3 ON TA2.f1 ON TA3.f1;
+COUNT(*)
+476
+EXPLAIN SELECT STRAIGHT_JOIN COUNT(*) FROM t1 TA1
+RIGHT JOIN t2 TA2 JOIN t2 TA3 ON TA2.f1 ON TA3.f1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
+1	SIMPLE	TA2	ALL	NULL	NULL	NULL	NULL	20	Using where
+1	SIMPLE	TA3	ALL	NULL	NULL	NULL	NULL	20	Using join buffer
+1	SIMPLE	TA1	ALL	NULL	NULL	NULL	NULL	2	
+DROP TABLE t1, t2;
+#
+# Bug#48971 Segfault in add_found_match_trig_cond () at sql_select.cc:5990
+#
+CREATE TABLE t1(f1 INT, PRIMARY KEY (f1));
+INSERT INTO t1 VALUES (1),(2);
+EXPLAIN EXTENDED SELECT STRAIGHT_JOIN T1.f1 FROM t1 AS T1
+LEFT JOIN t1 AS T2
+RIGHT JOIN t1 AS T3
+JOIN t1 AS T4 ON 1
+LEFT JOIN t1 AS T5 ON 1
+ON 1
+RIGHT JOIN t1 AS T6 ON T6.f1
+ON 1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	T1	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T6	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T3	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T4	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T5	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T2	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+Warnings:
+Note	1003	select straight_join `test`.`T1`.`f1` AS `f1` from `test`.`t1` `T1` left join (`test`.`t1` `T6` left join (`test`.`t1` `T3` join `test`.`t1` `T4` left join `test`.`t1` `T5` on(1) left join `test`.`t1` `T2` on(1)) on((`test`.`T6`.`f1` and 1))) on(1) where 1
+EXPLAIN EXTENDED SELECT STRAIGHT_JOIN T1.f1 FROM t1 AS T1
+RIGHT JOIN t1 AS T2
+RIGHT JOIN t1 AS T3
+JOIN t1 AS T4 ON 1
+LEFT JOIN t1 AS T5 ON 1
+ON 1
+RIGHT JOIN t1 AS T6 ON T6.f1
+ON 1;
+id	select_type	table	type	possible_keys	key	key_len	ref	rows	filtered	Extra
+1	SIMPLE	T6	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T3	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T4	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T5	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T2	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+1	SIMPLE	T1	index	NULL	PRIMARY	4	NULL	2	100.00	Using index
+Warnings:
+Note	1003	select straight_join `test`.`T1`.`f1` AS `f1` from `test`.`t1` `T6` left join (`test`.`t1` `T3` join `test`.`t1` `T4` left join `test`.`t1` `T5` on(1) left join `test`.`t1` `T2` on(1)) on((`test`.`T6`.`f1` and 1)) left join `test`.`t1` `T1` on(1) where 1
+DROP TABLE t1;
 End of 5.1 tests

=== modified file 'mysql-test/t/join_outer.test'
--- a/mysql-test/t/join_outer.test	2010-05-06 08:59:28 +0000
+++ b/mysql-test/t/join_outer.test	2010-05-27 15:13:53 +0000
@@ -936,4 +936,49 @@ FROM t1 tt3 LEFT  OUTER JOIN t1 tt4 ON 1
 
 SET optimizer_search_depth = DEFAULT;
 DROP TABLE t1;
+
+--echo #
+--echo # Bug#46091 STRAIGHT_JOIN + RIGHT JOIN returns different result
+--echo #
+CREATE TABLE t1 (f1 INT NOT NULL);
+INSERT INTO t1 VALUES (9),(0);
+
+CREATE TABLE t2 (f1 INT NOT NULL);
+INSERT INTO t2 VALUES
+(5),(3),(0),(3),(1),(0),(1),(7),(1),(0),(0),(8),(4),(9),(0),(2),(0),(8),(5),(1);
+
+SELECT STRAIGHT_JOIN COUNT(*) FROM t1 TA1
+RIGHT JOIN t2 TA2 JOIN t2 TA3 ON TA2.f1 ON TA3.f1;
+
+EXPLAIN SELECT STRAIGHT_JOIN COUNT(*) FROM t1 TA1
+RIGHT JOIN t2 TA2 JOIN t2 TA3 ON TA2.f1 ON TA3.f1;
+
+DROP TABLE t1, t2;
+
+--echo #
+--echo # Bug#48971 Segfault in add_found_match_trig_cond () at sql_select.cc:5990
+--echo #
+CREATE TABLE t1(f1 INT, PRIMARY KEY (f1));
+INSERT INTO t1 VALUES (1),(2);
+
+EXPLAIN EXTENDED SELECT STRAIGHT_JOIN T1.f1 FROM t1 AS T1
+ LEFT JOIN t1 AS T2
+  RIGHT JOIN t1 AS T3
+    JOIN t1 AS T4 ON 1
+   LEFT JOIN t1 AS T5 ON 1
+  ON 1
+  RIGHT JOIN t1 AS T6 ON T6.f1
+ ON 1;
+
+EXPLAIN EXTENDED SELECT STRAIGHT_JOIN T1.f1 FROM t1 AS T1
+ RIGHT JOIN t1 AS T2
+  RIGHT JOIN t1 AS T3
+    JOIN t1 AS T4 ON 1
+   LEFT JOIN t1 AS T5 ON 1
+  ON 1
+  RIGHT JOIN t1 AS T6 ON T6.f1
+ ON 1;
+
+DROP TABLE t1;
+
 --echo End of 5.1 tests

=== modified file 'sql/sql_select.cc'
--- a/sql/sql_select.cc	2010-05-07 07:12:16 +0000
+++ b/sql/sql_select.cc	2010-05-27 15:13:53 +0000
@@ -2709,31 +2709,53 @@ make_join_statistics(JOIN *join, TABLE_L
     /* 
        Build transitive closure for relation 'to be dependent on'.
        This will speed up the plan search for many cases with outer joins,
-       as well as allow us to catch illegal cross references/
+       as well as allow us to catch illegal cross references.
        Warshall's algorithm is used to build the transitive closure.
-       As we use bitmaps to represent the relation the complexity
-       of the algorithm is O((number of tables)^2). 
+       As we may restart the outer loop upto 'table_count' times, the
+       complexity of the algorithm is O((number of tables)^3).
+       However, most of the iterations will be shortcircuited when
+       there are no pedendencies to propogate.
     */
-    for (i= 0, s= stat ; i < table_count ; i++, s++)
+    for (i= 0 ; i < table_count ; i++)
     {
-      for (uint j= 0 ; j < table_count ; j++)
+      uint j;
+      table= stat[i].table;
+
+      if (!table->reginfo.join_tab->dependent)
+        continue;
+
+      /* Add my dependencies to other tables depending on me */
+      for (j= 0, s= stat ; j < table_count ; j++, s++)
       {
-        table= stat[j].table;
         if (s->dependent & table->map)
+        {
+          table_map was_dependent= s->dependent;
           s->dependent |= table->reginfo.join_tab->dependent;
+          /*
+            If we change dependencies for a table we already have
+            processed: Redo dependency propagation from this table.
+          */
+          if (i > j && s->dependent != was_dependent)
+          {
+            i = j-1;
+            break;
+          }
+        }
       }
-      if (outer_join & s->table->map)
-        s->table->maybe_null= 1;
     }
-    /* Catch illegal cross references for outer joins */
+
     for (i= 0, s= stat ; i < table_count ; i++, s++)
     {
+      /* Catch illegal cross references for outer joins */
       if (s->dependent & s->table->map)
       {
         join->tables=0;			// Don't use join->table
         my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
         goto error;
       }
+
+      if (outer_join & s->table->map)
+        s->table->maybe_null= 1;
       s->key_dependent= s->dependent;
     }
   }
@@ -8704,6 +8726,7 @@ simplify_joins(JOIN *join, List<TABLE_LI
   NESTED_JOIN *nested_join;
   TABLE_LIST *prev_table= 0;
   List_iterator<TABLE_LIST> li(*join_list);
+  bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
   DBUG_ENTER("simplify_joins");
 
   /* 
@@ -8814,7 +8837,7 @@ simplify_joins(JOIN *join, List<TABLE_LI
     if (prev_table)
     {
       /* The order of tables is reverse: prev_table follows table */
-      if (prev_table->straight)
+      if (prev_table->straight || straight_join)
         prev_table->dep_tables|= used_tables;
       if (prev_table->on_expr)
       {


Attachment: [text/bzr-bundle] bzr/sergey.glukhov@sun.com-20100527151353-7wgqj73d16lkzt57.bundle
Thread
bzr commit into mysql-5.1-bugteam branch (Sergey.Glukhov:3398)Bug#52005Sergey Glukhov27 May