Hello Igor, Ok to push. I'm sorry for the delay. On Sun, Jul 25, 2010 at 10:50:03PM -0700, Igor Babaev wrote:

#At lp:maria based on revid:monty@askmonty.org-20100615220051-2xp3g51fysxle1r1

2869 Igor Babaev 2010-07-25 Fixed bug #52005. Corrected coding for Warshall's algorithm. 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-03-19 06:21:37 +0000 +++ b/mysql-test/r/join_outer.result 2010-07-26 05:49:51 +0000 @@ -1308,4 +1308,63 @@ WHERE (COALESCE(t1.f1, t2.f1), f3) IN (( f1 f2 f3 f1 f2 1 NULL 3 NULL NULL DROP TABLE t1, t2; +# +# 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 jt1.f1 FROM t1 AS jt1 +LEFT JOIN t1 AS jt2 +RIGHT JOIN t1 AS jt3 +JOIN t1 AS jt4 ON 1 +LEFT JOIN t1 AS jt5 ON 1 +ON 1 +RIGHT JOIN t1 AS jt6 ON jt6.f1 +ON 1; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 SIMPLE jt1 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt6 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt3 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt4 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt5 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt2 index NULL PRIMARY 4 NULL 2 100.00 Using index +Warnings: +Note 1003 select straight_join `test`.`jt1`.`f1` AS `f1` from `test`.`t1` `jt1` left join (`test`.`t1` `jt6` left join (`test`.`t1` `jt3` join `test`.`t1` `jt4` left join `test`.`t1` `jt5` on(1) left join `test`.`t1` `jt2` on(1)) on((`test`.`jt6`.`f1` and 1))) on(1) where 1 +EXPLAIN EXTENDED SELECT STRAIGHT_JOIN jt1.f1 FROM t1 AS jt1 +RIGHT JOIN t1 AS jt2 +RIGHT JOIN t1 AS jt3 +JOIN t1 AS jt4 ON 1 +LEFT JOIN t1 AS jt5 ON 1 +ON 1 +RIGHT JOIN t1 AS jt6 ON jt6.f1 +ON 1; +id select_type table type possible_keys key key_len ref rows filtered Extra +1 SIMPLE jt6 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt3 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt4 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt5 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt2 index NULL PRIMARY 4 NULL 2 100.00 Using index +1 SIMPLE jt1 index NULL PRIMARY 4 NULL 2 100.00 Using index +Warnings: +Note 1003 select straight_join `test`.`jt1`.`f1` AS `f1` from `test`.`t1` `jt6` left join (`test`.`t1` `jt3` join `test`.`t1` `jt4` left join `test`.`t1` `jt5` on(1) left join `test`.`t1` `jt2` on(1)) on((`test`.`jt6`.`f1` and 1)) left join `test`.`t1` `jt1` 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-03-19 06:21:37 +0000 +++ b/mysql-test/t/join_outer.test 2010-07-26 05:49:51 +0000 @@ -913,4 +913,48 @@ WHERE (COALESCE(t1.f1, t2.f1), f3) IN ((

DROP TABLE t1, t2;

+--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 jt1.f1 FROM t1 AS jt1 + LEFT JOIN t1 AS jt2 + RIGHT JOIN t1 AS jt3 + JOIN t1 AS jt4 ON 1 + LEFT JOIN t1 AS jt5 ON 1 + ON 1 + RIGHT JOIN t1 AS jt6 ON jt6.f1 + ON 1; + +EXPLAIN EXTENDED SELECT STRAIGHT_JOIN jt1.f1 FROM t1 AS jt1 + RIGHT JOIN t1 AS jt2 + RIGHT JOIN t1 AS jt3 + JOIN t1 AS jt4 ON 1 + LEFT JOIN t1 AS jt5 ON 1 + ON 1 + RIGHT JOIN t1 AS jt6 ON jt6.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-26 18:55:40 +0000 +++ b/sql/sql_select.cc 2010-07-26 05:49:51 +0000 @@ -2717,15 +2717,29 @@ make_join_statistics(JOIN *join, TABLE_L 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). + of the algorithm is O((number of tables)^2). + + The classic form of the Warshall's algorithm would look like: + for (i= 0; i < table_count; i++) + { + for (j= 0; j < table_count; j++) + { + for (k= 0; k < table_count; k++) + { + if (bitmap_is_set(stat[j], i) && bitmap_is_set(stat[i], k) + bitmap_set_bit(stat[j], k); + } + } + } */ for (i= 0, s= stat ; i < table_count ; i++, s++) { - for (uint j= 0 ; j < table_count ; j++) + table= s->table; + JOIN_TAB *t; + for (uint j= 0, t= stat ; j < table_count ; j++, t++) { - table= stat[j].table; - if (s->dependent & table->map) - s->dependent |= table->reginfo.join_tab->dependent; + if (t->dependent & table->map) + t->dependent |= table->reginfo.join_tab->dependent; } if (outer_join & s->table->map) s->table->maybe_null= 1; @@ -8784,6 +8798,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");

/* @@ -8896,7 +8911,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) {

BR Sergey -- Sergey Petrunia, Software Developer Monty Program AB, http://askmonty.org Blog: http://s.petrunia.net/blog