From 8ede529b361b0c86121879700de580d797fddd4c Mon Sep 17 00:00:00 2001 From: Sergey Glukhov Date: Thu, 27 May 2010 19:13:53 +0400 Subject: 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. --- sql/sql_select.cc | 43 +++++++++++++++++++++++++++++++++---------- 1 file changed, 33 insertions(+), 10 deletions(-) (limited to 'sql') diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 6f128cb8181..ccb63dc0ed0 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -2709,31 +2709,53 @@ make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds, /* 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 *join_list, COND *conds, bool top) NESTED_JOIN *nested_join; TABLE_LIST *prev_table= 0; List_iterator 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 *join_list, COND *conds, bool top) 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) { -- cgit v1.2.1