At file:///home/psergey/dev/maria-5.1-table-elim-r11/ ------------------------------------------------------------ revno: 2733 revision-id: psergey@askmonty.org-20090818130358-akd84j4m2i91lw5a parent: psergey@askmonty.org-20090817160724-fmmrmwp8zorzn82q committer: Sergey Petrunya <psergey@askmonty.org> branch nick: maria-5.1-table-elim-r11 timestamp: Tue 2009-08-18 16:03:58 +0300 message: MWL#17: Table elimination - Switch from trying to eliminate all tables at once (which didn't work) to the original approach of bottom-up elimination. === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-17 15:02:29 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-18 13:03:58 +0000 @@ -273,8 +273,9 @@ class Outer_join_module: public Module_dep { public: - Outer_join_module(TABLE_LIST *table_list_arg, uint n_children) : - table_list(table_list_arg), parent(NULL) + Outer_join_module(//TABLE_LIST *table_list_arg, + uint n_children) + // table_list(table_list_arg), parent(NULL) { type= Module_dep::MODULE_OUTER_JOIN; unknown_args= n_children; @@ -283,10 +284,10 @@ Outer join we're representing. This can be a join nest or one table that is outer join'ed. */ - TABLE_LIST *table_list; +// TABLE_LIST *table_list; /* Parent eliminable outer join, if any */ - Outer_join_module *parent; +// Outer_join_module *parent; }; @@ -334,10 +335,10 @@ static Table_value *get_table_value(Table_elimination *te, TABLE *table); static Field_value *get_field_value(Table_elimination *te, Field *field); static Outer_join_module *get_outer_join_dep(Table_elimination *te, - TABLE_LIST *outer_join, + //TABLE_LIST *outer_join, table_map deps_map); static -void run_elimination_wave(Table_elimination *te, Module_dep *bound_modules); +bool run_elimination_wave(Table_elimination *te, Module_dep *bound_modules); void eliminate_tables(JOIN *join); static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl); @@ -357,7 +358,7 @@ and_level INOUT AND-level (like in add_key_fields) cond Condition to process usable_tables Tables which fields we're interested in. That is, - Equality_dep represent "tbl.col=expr" and we'll + Equality_module represent "tbl.col=expr" and we'll produce them only if tbl is in usable_tables. DESCRIPTION This function is modeled after add_key_fields() @@ -747,11 +748,11 @@ static Outer_join_module *get_outer_join_dep(Table_elimination *te, - TABLE_LIST *outer_join, + // TABLE_LIST *outer_join, table_map deps_map) { Outer_join_module *oj_dep; - if (!(oj_dep= new Outer_join_module(outer_join, my_count_bits(deps_map)))) + if (!(oj_dep= new Outer_join_module(/*outer_join, */my_count_bits(deps_map)))) return NULL; te->n_outer_joins++; @@ -792,8 +793,9 @@ point to the newly created Outer_join_module. to set the pointer of its near */ - if (!table_dep->outer_join_dep) + //if (!table_dep->outer_join_dep) table_dep->outer_join_dep= oj_dep; + /* else { Outer_join_module *oj= table_dep->outer_join_dep; @@ -802,95 +804,13 @@ if (oj != oj_dep) oj->parent=oj_dep; } + */ } return oj_dep; } /* - Build functional dependency graph for elements of given join list - - SYNOPSIS - collect_funcdeps_for_join_list() - te Table elimination context. - join_list Join list to work on - build_eq_deps TRUE <=> build Equality_module elements for all - members of the join list, even if they cannot - be individually eliminated - tables_used_elsewhere Bitmap of tables that are referred to from - somewhere outside of this join list (e.g. - select list, HAVING, ON expressions of parent - joins, etc). - eliminable_tables INOUT Tables that can potentially be eliminated - (needed so we know for which tables to build - dependencies for) - eq_dep INOUT End of array of equality dependencies. - - DESCRIPTION - . -*/ - -static bool -collect_funcdeps_for_join_list(Table_elimination *te, - List<TABLE_LIST> *join_list, - bool build_eq_deps, - table_map tables_used_elsewhere, - table_map *eliminable_tables, - Equality_module **eq_dep) -{ - TABLE_LIST *tbl; - List_iterator<TABLE_LIST> it(*join_list); - table_map tables_used_on_left= 0; - - while ((tbl= it++)) - { - if (tbl->on_expr) - { - table_map outside_used_tables= tables_used_elsewhere | - tables_used_on_left; - bool eliminable; - table_map cur_map; - if (tbl->nested_join) - { - /* This is "... LEFT JOIN (join_nest) ON cond" */ - cur_map= tbl->nested_join->used_tables; - eliminable= !(cur_map & outside_used_tables); - if (eliminable) - *eliminable_tables |= cur_map; - if (collect_funcdeps_for_join_list(te, &tbl->nested_join->join_list, - eliminable || build_eq_deps, - outside_used_tables, - eliminable_tables, - eq_dep)) - return TRUE; - } - else - { - /* This is "... LEFT JOIN tbl ON cond" */ - cur_map= tbl->table->map; - eliminable= !(tbl->table->map & outside_used_tables); - *eliminable_tables |= cur_map; - } - - if (eliminable || build_eq_deps) - { - // build comp_cond from ON expression - uint and_level=0; - build_eq_deps_for_cond(te, eq_dep, &and_level, tbl->on_expr, - *eliminable_tables); - } - - if (eliminable && !get_outer_join_dep(te, tbl, cur_map)) - return TRUE; - - tables_used_on_left |= tbl->on_expr->used_tables(); - } - } - return FALSE; -} - - -/* This is used to analyze expressions in "tbl.col=expr" dependencies so that we can figure out which fields the expression depends on. */ @@ -950,13 +870,15 @@ { DBUG_ENTER("setup_equality_deps"); + if (!te->n_equality_deps) + DBUG_RETURN(TRUE); /* Count Field_value objects and assign each of them a unique bitmap_offset. */ uint offset= 0; for (Table_value **tbl_dep=te->table_deps; tbl_dep < te->table_deps + MAX_TABLES; - tbl_dep++) + tbl_dep++) // psergey-todo: TODO change to Table_map_iterator { if (*tbl_dep) { @@ -1046,6 +968,12 @@ See the OVERVIEW section at the top of this file. */ +static uint +eliminate_tables_for_list(Table_elimination *te, + List<TABLE_LIST> *join_list, + Item *on_expr, + table_map tables_in_list, + table_map tables_used_elsewhere); void eliminate_tables(JOIN *join) { @@ -1101,15 +1029,22 @@ thd->lex->current_select->between_count)*m + 1 + 10; if (!(te.equality_deps= new Equality_module[max_elems])) DBUG_VOID_RETURN; - Equality_module *eq_deps_end= te.equality_deps; - table_map eliminable_tables= 0; + //Equality_module *eq_deps_end= te.equality_deps; + //table_map eliminable_tables= 0; + /* if (collect_funcdeps_for_join_list(&te, join->join_list, FALSE, used_tables, &eliminable_tables, - &eq_deps_end)) + &eq_deps)) DBUG_VOID_RETURN; - te.n_equality_deps= eq_deps_end - te.equality_deps; + */ + eliminate_tables_for_list(&te, join->join_list, + NULL, + (table_map(1) << join->tables) - 1, + used_tables); + + /*te.n_equality_deps= eq_deps_end - te.equality_deps; Module_dep *bound_modules; //Value_dep *bound_values; @@ -1117,11 +1052,207 @@ DBUG_VOID_RETURN; run_elimination_wave(&te, bound_modules); + */ } DBUG_VOID_RETURN; } +//////////////////////////// + +/* + Perform table elimination in a given join list + + SYNOPSIS + eliminate_tables_for_list() + join The join + leaves_arr OUT Store here an array of leaf (base) tables that + are descendants of the join_list, and increment + the pointer to point right above the array. + join_list Join list to work on + its_outer_join TRUE <=> join_list is an inner side of an outer + join + FALSE <=> otherwise (this is top-level join list) + tables_in_list Bitmap of tables embedded in the join_list. + tables_used_elsewhere Bitmap of tables that are referred to from + somewhere outside of the join list (e.g. + select list, HAVING, etc). + + DESCRIPTION + Perform table elimination for a join list. + Try eliminating children nests first. + The "all tables in join nest can produce only one matching record + combination" property checking is modeled after constant table detection, + plus we reuse info attempts to eliminate child join nests. + + RETURN + Number of children left after elimination. 0 means everything was + eliminated. +*/ + +bool try_eliminating(Table_elimination *te, table_map tables_in_list, + Item* on_expr) +{ + uint and_level=0; + Equality_module* eq_dep= te->equality_deps; + build_eq_deps_for_cond(te, &eq_dep, &and_level, on_expr, + tables_in_list); + te->n_equality_deps= eq_dep - te->equality_deps; + Module_dep *bound_modules; + get_outer_join_dep(te, tables_in_list); + + if (!setup_equality_deps(te, &bound_modules) && + run_elimination_wave(te, bound_modules)) + return TRUE; // eliminated + return FALSE; +} + + +static uint +eliminate_tables_for_list(Table_elimination *te, List<TABLE_LIST> *join_list, + Item *on_expr, + table_map tables_in_list, + table_map tables_used_elsewhere) +{ + TABLE_LIST *tbl; + List_iterator<TABLE_LIST> it(*join_list); + table_map tables_used_on_left= 0; + bool not_eliminated= FALSE; + + while ((tbl= it++)) + { + if (tbl->on_expr) + { + table_map outside_used_tables= tables_used_elsewhere | + tables_used_on_left; + if (tbl->nested_join) + { + /* This is "... LEFT JOIN (join_nest) ON cond" */ + if (eliminate_tables_for_list(te, + &tbl->nested_join->join_list, + tbl->on_expr, + tbl->nested_join->used_tables, + outside_used_tables)) + { + mark_as_eliminated(te->join, tbl); + } + else + not_eliminated= TRUE; + + } + else + { + /* This is "... LEFT JOIN tbl ON cond" */ + if (!(tbl->table->map & outside_used_tables) && + try_eliminating(te, tbl->table->map, tbl->on_expr)) + { + mark_as_eliminated(te->join, tbl); + } + else + not_eliminated= TRUE; + } + tables_used_on_left |= tbl->on_expr->used_tables(); + } + else + { + DBUG_ASSERT(!tbl->nested_join); + } + } + + /* Try eliminating the nest we're called for */ + if (!not_eliminated && on_expr && !(tables_in_list & tables_used_elsewhere)) + return try_eliminating(te, tables_in_list & ~te->join->eliminated_tables, + on_expr); + + return FALSE; /* not eliminated */ +} + +#if 0 +/* + Build functional dependency graph for elements of given join list + + SYNOPSIS + collect_funcdeps_for_join_list() + te Table elimination context. + join_list Join list to work on + build_eq_deps TRUE <=> build Equality_module elements for all + members of the join list, even if they cannot + be individually eliminated + tables_used_elsewhere Bitmap of tables that are referred to from + somewhere outside of this join list (e.g. + select list, HAVING, ON expressions of parent + joins, etc). + eliminable_tables INOUT Tables that can potentially be eliminated + (needed so we know for which tables to build + dependencies for) + eq_dep INOUT End of array of equality dependencies. + + DESCRIPTION + . +*/ + +static bool +collect_funcdeps_for_join_list(Table_elimination *te, + List<TABLE_LIST> *join_list, + bool build_eq_deps, + table_map tables_used_elsewhere, + table_map *eliminable_tables, + Equality_module **eq_dep) +{ + TABLE_LIST *tbl; + List_iterator<TABLE_LIST> it(*join_list); + table_map tables_used_on_left= 0; + + while ((tbl= it++)) + { + if (tbl->on_expr) + { + table_map outside_used_tables= tables_used_elsewhere | + tables_used_on_left; + bool eliminable; + table_map cur_map; + if (tbl->nested_join) + { + /* This is "... LEFT JOIN (join_nest) ON cond" */ + cur_map= tbl->nested_join->used_tables; + eliminable= !(cur_map & outside_used_tables); + if (eliminable) + *eliminable_tables |= cur_map; + if (collect_funcdeps_for_join_list(te, &tbl->nested_join->join_list, + eliminable || build_eq_deps, + outside_used_tables, + eliminable_tables, + eq_dep)) + return TRUE; + } + else + { + /* This is "... LEFT JOIN tbl ON cond" */ + cur_map= tbl->table->map; + eliminable= !(tbl->table->map & outside_used_tables); + *eliminable_tables |= cur_map; + } + + if (eliminable || build_eq_deps) + { + // build comp_cond from ON expression + uint and_level=0; + build_eq_deps_for_cond(te, eq_dep, &and_level, tbl->on_expr, + *eliminable_tables); + } + + if (eliminable && !get_outer_join_dep(te, tbl, cur_map)) + return TRUE; + + tables_used_on_left |= tbl->on_expr->used_tables(); + } + } + return FALSE; +} +#endif + +//////////////////////////// + static void signal_from_field_to_exprs(Table_elimination* te, Field_value *field_dep, Module_dep **bound_modules) @@ -1142,7 +1273,7 @@ static -void run_elimination_wave(Table_elimination *te, Module_dep *bound_modules) +bool run_elimination_wave(Table_elimination *te, Module_dep *bound_modules) { Value_dep *bound_values= NULL; /* @@ -1187,13 +1318,13 @@ } case Module_dep::MODULE_OUTER_JOIN: { - Outer_join_module *outer_join_dep= (Outer_join_module*)bound_modules; - mark_as_eliminated(te->join, outer_join_dep->table_list); - if (!--te->n_outer_joins) + //Outer_join_module *outer_join_dep= (Outer_join_module*)bound_modules; + //mark_as_eliminated(te->join, outer_join_dep->table_list); + //if (!--te->n_outer_joins) { DBUG_PRINT("info", ("Table elimination eliminated everything" " it theoretically could")); - return; + return TRUE; } break; } @@ -1256,8 +1387,9 @@ signal_from_field_to_exprs(te, field_dep, &bound_modules); } } - for (Outer_join_module *outer_join_dep= table_dep->outer_join_dep; - outer_join_dep; outer_join_dep= outer_join_dep->parent) + //for ( + Outer_join_module *outer_join_dep= table_dep->outer_join_dep; + // outer_join_dep; outer_join_dep= outer_join_dep->parent) { if (outer_join_dep->unknown_args && !--outer_join_dep->unknown_args) @@ -1274,6 +1406,7 @@ } } } + return FALSE; }