- developers - lists.mariadb.org

[Maria-developers] Rev 2737: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim-r11/
by Sergey Petrunya 19 Aug '09

19 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r11/ ------------------------------------------------------------ revno: 2737 revision-id: psergey(a)askmonty.org-20090819101838-55ys0h923olqz4q9 parent: psergey(a)askmonty.org-20090818221948-f2mg0szfqrve06f9 committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r11 timestamp: Wed 2009-08-19 13:18:38 +0300 message: MWL#17: Table elimination - Use Table_elimination only for functional dependency checking for individual objects and rename it to Func_dep_analyzer === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-18 22:19:48 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-19 10:18:38 +0000 @@ -135,7 +135,7 @@ class Outer_join_module; class Key_module; -class Table_elimination; +class Func_dep_analyzer; /* @@ -147,7 +147,7 @@ { public: Value_dep(): bound(FALSE), next(NULL) {} - virtual void now_bound(Table_elimination *te, Module_dep **bound_modules)=0; + virtual void now_bound(Func_dep_analyzer *te, Module_dep **bound_modules)=0; virtual ~Value_dep() {} /* only to shut up compiler warnings */ bool bound; @@ -182,8 +182,8 @@ - unique keys we belong to - expressions that depend on us. */ - void now_bound(Table_elimination *te, Module_dep **bound_modules); - void signal_from_field_to_exprs(Table_elimination* te, + void now_bound(Func_dep_analyzer *te, Module_dep **bound_modules); + void signal_from_field_to_exprs(Func_dep_analyzer* te, Module_dep **bound_modules); }; @@ -203,7 +203,7 @@ Field_value *fields; /* Ordered list of fields that belong to this table */ Key_module *keys; /* Ordered list of Unique keys in this table */ //Outer_join_module *outer_join_dep; - void now_bound(Table_elimination *te, Module_dep **bound_modules); + void now_bound(Func_dep_analyzer *te, Module_dep **bound_modules); }; @@ -218,7 +218,7 @@ MODULE_OUTER_JOIN } type; /* Type of the object */ - virtual bool now_bound(Table_elimination *te, Value_dep **bound_modules)=0; + virtual bool now_bound(Func_dep_analyzer *te, Value_dep **bound_modules)=0; virtual ~Module_dep(){} /* Used to make a linked list of elements that became bound and thus can @@ -243,7 +243,7 @@ /* Used during condition analysis only, similar to KEYUSE::level */ uint level; - bool now_bound(Table_elimination *te, Value_dep **bound_values); + bool now_bound(Func_dep_analyzer *te, Value_dep **bound_values); }; @@ -264,7 +264,7 @@ uint keyno; /* Unique keys form a linked list, ordered by keyno */ Key_module *next_table_key; - bool now_bound(Table_elimination *te, Value_dep **bound_values); + bool now_bound(Func_dep_analyzer *te, Value_dep **bound_values); }; @@ -280,26 +280,30 @@ { unknown_args= n_children; } - bool now_bound(Table_elimination *te, Value_dep **bound_values); + bool now_bound(Func_dep_analyzer *te, Value_dep **bound_values); }; /* - Table elimination context + Functional dependency analyzer context */ -class Table_elimination +class Func_dep_analyzer { public: - Table_elimination(JOIN *join_arg) : join(join_arg) + Func_dep_analyzer(JOIN *join_arg) : join(join_arg) { bzero(table_deps, sizeof(table_deps)); } JOIN *join; /* Join we're working on */ + + /* Tables that we're looking at eliminating */ + table_map usable_tables; /* Array of equality dependencies */ Equality_module *equality_deps; uint n_equality_deps; /* Number of elements in the array */ + uint n_equality_deps_alloced; /* tablenr -> Table_value* mapping. */ Table_value *table_deps[MAX_KEY]; @@ -327,27 +331,25 @@ Item* cond); static -bool build_eq_deps_for_cond(Table_elimination *te, Equality_module **fdeps, - uint *and_level, Item *cond, - table_map usable_tables); +bool build_eq_deps_for_cond(Func_dep_analyzer *te, Equality_module **fdeps, + uint *and_level, Item *cond); static -bool add_eq_dep(Table_elimination *te, Equality_module **eq_dep, +bool add_eq_dep(Func_dep_analyzer *te, Equality_module **eq_dep, uint and_level, - Item_func *cond, Item *left, Item *right, - table_map usable_tables); + Item_func *cond, Item *left, Item *right); static Equality_module *merge_func_deps(Equality_module *start, Equality_module *new_fields, Equality_module *end, uint and_level); -static Table_value *get_table_value(Table_elimination *te, TABLE *table); -static Field_value *get_field_value(Table_elimination *te, Field *field); +static Table_value *get_table_value(Func_dep_analyzer *te, TABLE *table); +static Field_value *get_field_value(Func_dep_analyzer *te, Field *field); static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl); #ifndef DBUG_OFF -static void dbug_print_deps(Table_elimination *te); +static void dbug_print_deps(Func_dep_analyzer *te); #endif /*******************************************************************************************/ @@ -361,17 +363,13 @@ fdeps INOUT Put produced equality conditions here 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_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() */ static -bool build_eq_deps_for_cond(Table_elimination *te, Equality_module **fdeps, - uint *and_level, Item *cond, - table_map usable_tables) +bool build_eq_deps_for_cond(Func_dep_analyzer *te, Equality_module **fdeps, + uint *and_level, Item *cond) { if (cond->type() == Item_func::COND_ITEM) { @@ -384,7 +382,7 @@ Item *item; while ((item=li++)) { - if (build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables)) + if (build_eq_deps_for_cond(te, fdeps, and_level, item)) return TRUE; } for (; org_key_fields != *fdeps ; org_key_fields++) @@ -393,14 +391,14 @@ else { (*and_level)++; - if (build_eq_deps_for_cond(te, fdeps, and_level, li++, usable_tables)) + if (build_eq_deps_for_cond(te, fdeps, and_level, li++)) return TRUE; Item *item; while ((item=li++)) { Equality_module *start_key_fields= *fdeps; (*and_level)++; - if (build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables)) + if (build_eq_deps_for_cond(te, fdeps, and_level, item)) return TRUE; *fdeps= merge_func_deps(org_key_fields, start_key_fields, *fdeps, ++(*and_level)); @@ -420,10 +418,8 @@ { if (cond_func->argument_count() == 2) { - if (add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1], - usable_tables) || - add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0], - usable_tables)) + if (add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1]) || + add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0])) return TRUE; } } @@ -434,10 +430,8 @@ (fld= args[0]->real_item())->type() == Item::FIELD_ITEM && args[1]->eq(args[2], ((Item_field*)fld)->field->binary())) { - if (add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1], - usable_tables) || - add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0], - usable_tables)) + if (add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1]) || + add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0])) return TRUE; } break; @@ -445,17 +439,14 @@ case Item_func::EQ_FUNC: case Item_func::EQUAL_FUNC: { - add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1], - usable_tables); - add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0], - usable_tables); + add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1]); + add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0]); break; } case Item_func::ISNULL_FUNC: { Item *tmp=new Item_null; - if (!tmp || add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1], - usable_tables)) + if (!tmp || add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1])) return TRUE; break; } @@ -474,8 +465,7 @@ */ while ((item= it++)) { - if (add_eq_dep(te, fdeps, *and_level, cond_func, item, const_item, - usable_tables)) + if (add_eq_dep(te, fdeps, *and_level, cond_func, item, const_item)) return TRUE; } } @@ -496,8 +486,7 @@ { if (!field->eq(item2->field)) { - if (add_eq_dep(te, fdeps, *and_level, cond_func, item, item2, - usable_tables)) + if (add_eq_dep(te, fdeps, *and_level, cond_func, item, item2)) return TRUE; } } @@ -656,11 +645,10 @@ */ static -bool add_eq_dep(Table_elimination *te, Equality_module **eq_mod, - uint and_level, Item_func *cond, Item *left, Item *right, - table_map usable_tables) +bool add_eq_dep(Func_dep_analyzer *te, Equality_module **eq_mod, + uint and_level, Item_func *cond, Item *left, Item *right) { - if ((left->used_tables() & usable_tables) && + if ((left->used_tables() & te->usable_tables) && !(right->used_tables() & RAND_TABLE_BIT) && left->real_item()->type() == Item::FIELD_ITEM) { @@ -698,7 +686,7 @@ Get a Table_value object for the given table, creating it if necessary. */ -static Table_value *get_table_value(Table_elimination *te, TABLE *table) +static Table_value *get_table_value(Func_dep_analyzer *te, TABLE *table) { Table_value *tbl_dep; if (!(tbl_dep= new Table_value(table))) @@ -724,7 +712,7 @@ Get a Field_value object for the given field, creating it if necessary */ -static Field_value *get_field_value(Table_elimination *te, Field *field) +static Field_value *get_field_value(Func_dep_analyzer *te, Field *field) { TABLE *table= field->table; Table_value *tbl_dep; @@ -762,7 +750,7 @@ class Field_dependency_recorder : public Field_enumerator { public: - Field_dependency_recorder(Table_elimination *te_arg): te(te_arg) + Field_dependency_recorder(Func_dep_analyzer *te_arg): te(te_arg) {} void see_field(Field *field) @@ -792,7 +780,7 @@ } } - Table_elimination *te; + Func_dep_analyzer *te; /* Offset of the expression we're processing in the dependency bitmap */ uint expr_offset; }; @@ -819,7 +807,7 @@ */ static -bool setup_equality_modules_deps(Table_elimination *te, +bool setup_equality_modules_deps(Func_dep_analyzer *te, Module_dep **bound_deps_list) { DBUG_ENTER("setup_equality_modules_deps"); @@ -1089,8 +1077,8 @@ Module_dep *bound_modules; //psergey-todo: move allocs to somewhere else. - Table_elimination pte(join); - Table_elimination *te= &pte; + Func_dep_analyzer pte(join); + Func_dep_analyzer *te= &pte; uint m= max(join->thd->lex->current_select->max_equal_elems,1); uint max_elems= ((join->thd->lex->current_select->cond_count+1)*2 + join->thd->lex->current_select->between_count)*m + 1 + 10; @@ -1118,11 +1106,12 @@ } } + te->usable_tables= dep_tables; /* Analyze the the ON expression and create Equality_module objects and Field_value objects for their left parts. */ - if (build_eq_deps_for_cond(te, &eq_dep, &and_level, cond, dep_tables) || + if (build_eq_deps_for_cond(te, &eq_dep, &and_level, cond) || eq_dep == te->equality_deps) return FALSE; @@ -1158,7 +1147,7 @@ - all its fields are known */ -void Table_value::now_bound(Table_elimination *te, +void Table_value::now_bound(Func_dep_analyzer *te, Module_dep **bound_modules) { DBUG_PRINT("info", ("table %s is now bound", table->alias)); @@ -1184,7 +1173,7 @@ } -void Field_value::now_bound(Table_elimination *te, +void Field_value::now_bound(Func_dep_analyzer *te, Module_dep **bound_modules) { DBUG_PRINT("info", ("field %s.%s is now bound", field->table->alias, @@ -1212,7 +1201,7 @@ Walk through expressions that depend on this field and 'notify' them that this field is no longer unknown. */ -void Field_value::signal_from_field_to_exprs(Table_elimination* te, +void Field_value::signal_from_field_to_exprs(Func_dep_analyzer* te, Module_dep **bound_modules) { for (uint i=0; i < te->n_equality_deps; i++) @@ -1230,7 +1219,7 @@ } -bool Outer_join_module::now_bound(Table_elimination *te, +bool Outer_join_module::now_bound(Func_dep_analyzer *te, Value_dep **bound_values) { DBUG_PRINT("info", ("Outer join eliminated")); @@ -1238,7 +1227,7 @@ } -bool Equality_module::now_bound(Table_elimination *te, +bool Equality_module::now_bound(Func_dep_analyzer *te, Value_dep **bound_values) { /* For field=expr and we got to know the expr, so we know the field */ @@ -1253,7 +1242,7 @@ } /* Unique key is known means its table is known */ -bool Key_module::now_bound(Table_elimination *te, Value_dep **bound_values) +bool Key_module::now_bound(Func_dep_analyzer *te, Value_dep **bound_values) { if (!table->bound) { @@ -1305,7 +1294,7 @@ #ifndef DBUG_OFF static -void dbug_print_deps(Table_elimination *te) +void dbug_print_deps(Func_dep_analyzer *te) { DBUG_ENTER("dbug_print_deps"); DBUG_LOCK_FILE;

1 0

[Maria-developers] Rev 2736: More code cleanups in file:///home/psergey/dev/maria-5.1-table-elim-r11/
by Sergey Petrunya 19 Aug '09

19 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r11/ ------------------------------------------------------------ revno: 2736 revision-id: psergey(a)askmonty.org-20090818221948-f2mg0szfqrve06f9 parent: psergey(a)askmonty.org-20090818211810-48v6pb8dt0sqkysi committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r11 timestamp: Wed 2009-08-19 01:19:48 +0300 message: More code cleanups === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-18 21:18:10 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-18 22:19:48 +0000 @@ -295,14 +295,16 @@ bzero(table_deps, sizeof(table_deps)); } - JOIN *join; + JOIN *join; /* Join we're working on */ + /* Array of equality dependencies */ Equality_module *equality_deps; uint n_equality_deps; /* Number of elements in the array */ /* tablenr -> Table_value* mapping. */ Table_value *table_deps[MAX_KEY]; - + + /* Element for the outer join we're attempting to eliminate */ Outer_join_module *outer_join_dep; /* Bitmap of how expressions depend on bits */ @@ -312,13 +314,13 @@ void eliminate_tables(JOIN *join); static bool -eliminate_tables_for_list(Table_elimination *te, +eliminate_tables_for_list(JOIN *join, List<TABLE_LIST> *join_list, table_map tables_in_list, Item *on_expr, table_map tables_used_elsewhere); static -bool check_func_dependency(Table_elimination *te, +bool check_func_dependency(JOIN *join, table_map dep_tables, List_iterator<TABLE_LIST> *it, TABLE_LIST *oj_tbl, @@ -753,61 +755,6 @@ /* - Create an Outer_join_module object for the given outer join - - DESCRIPTION - Outer_join_module objects for children (or further descendants) are always - created before the parents. -*/ - -#if 0 -static -Outer_join_module *get_outer_join_dep(Table_elimination *te, - // 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)))) - return NULL; - - /* - Collect a bitmap fo tables that we depend on, and also set parent pointer - for descendant outer join elements. - */ - Table_map_iterator it(deps_map); - int idx; - while ((idx= it.next_bit()) != Table_map_iterator::BITMAP_END) - { - Table_value *table_dep; - if (!(table_dep= te->table_deps[idx])) - { - /* - We get here only when ON expression had no references to inner tables - and Table_map objects weren't created for them. This is a rare/ - unimportant case so it's ok to do not too efficient searches. - */ - TABLE *table= NULL; - for (TABLE_LIST *tlist= te->join->select_lex->leaf_tables; tlist; - tlist=tlist->next_leaf) - { - if (tlist->table->tablenr == (uint)idx) - { - table=tlist->table; - break; - } - } - DBUG_ASSERT(table); - if (!(table_dep= get_table_value(te, table))) - return NULL; - } - table_dep->outer_join_dep= oj_dep; - } - return oj_dep; -} -#endif - - -/* This is used to analyze expressions in "tbl.col=expr" dependencies so that we can figure out which fields the expression depends on. */ @@ -852,33 +799,39 @@ /* - Setup equality dependencies + Setup inbound dependency relationships for tbl.col=expr equalities SYNOPSIS - setup_equality_deps() + setup_equality_modules_deps() te Table elimination context bound_deps_list OUT Start of linked list of elements that were found to be bound (caller will use this to see if that allows to declare further elements bound) DESCRIPTION + Setup inbound dependency relationships for tbl.col=expr equalities: + - allocate a bitmap where we store such dependencies + - for each "tbl.col=expr" equality, analyze the expr part and find out + which fields it refers to and set appropriate dependencies. + RETURN - + FALSE OK + TRUE Out of memory */ static -bool setup_equality_deps(Table_elimination *te, Module_dep **bound_deps_list) +bool setup_equality_modules_deps(Table_elimination *te, + Module_dep **bound_deps_list) { - DBUG_ENTER("setup_equality_deps"); + DBUG_ENTER("setup_equality_modules_deps"); - if (!te->n_equality_deps) - DBUG_RETURN(TRUE); /* - Count Field_value objects and assign each of them a unique bitmap_offset. + Count Field_value objects and assign each of them a unique bitmap_offset + value. */ uint offset= 0; for (Table_value **tbl_dep=te->table_deps; tbl_dep < te->table_deps + MAX_TABLES; - tbl_dep++) // psergey-todo: Wipe this out altogether + tbl_dep++) { if (*tbl_dep) { @@ -924,7 +877,6 @@ } *bound_deps_list= bound_dep; - DBUG_EXECUTE("test", dbug_print_deps(te); ); DBUG_RETURN(FALSE); } @@ -1016,15 +968,7 @@ if (all_tables & ~used_tables) { /* There are some tables that we probably could eliminate. Try it. */ - //psergey-todo: move allocs to somewhere else. - Table_elimination te(join); - uint m= max(thd->lex->current_select->max_equal_elems,1); - uint max_elems= ((thd->lex->current_select->cond_count+1)*2 + - thd->lex->current_select->between_count)*m + 1 + 10; - if (!(te.equality_deps= new Equality_module[max_elems])) - DBUG_VOID_RETURN; - - eliminate_tables_for_list(&te, join->join_list, all_tables, NULL, + eliminate_tables_for_list(join, join->join_list, all_tables, NULL, used_tables); } DBUG_VOID_RETURN; @@ -1056,7 +1000,7 @@ */ static bool -eliminate_tables_for_list(Table_elimination *te, List<TABLE_LIST> *join_list, +eliminate_tables_for_list(JOIN *join, List<TABLE_LIST> *join_list, table_map list_tables, Item *on_expr, table_map tables_used_elsewhere) { @@ -1074,13 +1018,13 @@ if (tbl->nested_join) { /* This is "... LEFT JOIN (join_nest) ON cond" */ - if (eliminate_tables_for_list(te, + if (eliminate_tables_for_list(join, &tbl->nested_join->join_list, tbl->nested_join->used_tables, tbl->on_expr, outside_used_tables)) { - mark_as_eliminated(te->join, tbl); + mark_as_eliminated(join, tbl); } else all_eliminated= FALSE; @@ -1089,10 +1033,10 @@ { /* This is "... LEFT JOIN tbl ON cond" */ if (!(tbl->table->map & outside_used_tables) && - check_func_dependency(te, tbl->table->map, NULL, tbl, + check_func_dependency(join, tbl->table->map, NULL, tbl, tbl->on_expr)) { - mark_as_eliminated(te->join, tbl); + mark_as_eliminated(join, tbl); } else all_eliminated= FALSE; @@ -1109,7 +1053,7 @@ if (all_eliminated && on_expr && !(list_tables & tables_used_elsewhere)) { it.rewind(); - return check_func_dependency(te, list_tables & ~te->join->eliminated_tables, + return check_func_dependency(join, list_tables & ~join->eliminated_tables, &it, NULL, on_expr); } return FALSE; /* not eliminated */ @@ -1135,18 +1079,27 @@ */ static -bool check_func_dependency(Table_elimination *te, +bool check_func_dependency(JOIN *join, table_map dep_tables, List_iterator<TABLE_LIST> *it, TABLE_LIST *oj_tbl, Item* cond) { uint and_level=0; + Module_dep *bound_modules; + + //psergey-todo: move allocs to somewhere else. + Table_elimination pte(join); + Table_elimination *te= &pte; + uint m= max(join->thd->lex->current_select->max_equal_elems,1); + uint max_elems= ((join->thd->lex->current_select->cond_count+1)*2 + + join->thd->lex->current_select->between_count)*m + 1 + 10; + if (!(te->equality_deps= new Equality_module[max_elems])) + return FALSE; + Equality_module* eq_dep= te->equality_deps; - Module_dep *bound_modules; - - bzero(te->table_deps, sizeof(te->table_deps)); - + + /* Create Table_value objects for all tables we're trying to eliminate */ if (oj_tbl) { if (!get_table_value(te, oj_tbl->table)) @@ -1165,19 +1118,25 @@ } } - /* Extract equalities from the ON expression */ + /* + Analyze the the ON expression and create Equality_module objects and + Field_value objects for their left parts. + */ if (build_eq_deps_for_cond(te, &eq_dep, &and_level, cond, dep_tables) || eq_dep == te->equality_deps) return FALSE; - + te->n_equality_deps= eq_dep - te->equality_deps; - /* Create objects for running wave algorithm */ + if (!(te->outer_join_dep= new Outer_join_module(my_count_bits(dep_tables))) || - setup_equality_deps(te, &bound_modules)) + setup_equality_modules_deps(te, &bound_modules)) { return FALSE; /* OOM, default to non-dependent */ } + + DBUG_EXECUTE("test", dbug_print_deps(te); ); + /* The running wave algorithm itself: */ Value_dep *bound_values= NULL; while (bound_modules) {

1 0

[Maria-developers] Rev 2735: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim-r11/
by Sergey Petrunya 18 Aug '09

18 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r11/ ------------------------------------------------------------ revno: 2735 revision-id: psergey(a)askmonty.org-20090818211810-48v6pb8dt0sqkysi parent: psergey(a)askmonty.org-20090818150151-uef38y50m8m1mgnu committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r11 timestamp: Wed 2009-08-19 00:18:10 +0300 message: MWL#17: Table elimination - Better comments - Switch from "type" enum and switch to virtual functions for member funcs. === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-18 15:01:51 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-18 21:18:10 +0000 @@ -58,7 +58,7 @@ Table elimination is redone on every PS re-execution. - TABLE ELIMINATION ALGORITHM + TABLE ELIMINATION ALGORITHM FOR ONE OUTER JOIN As said above, we can remove inner side of an outer join if it is @@ -101,14 +101,14 @@ each value is either bound (i.e. functionally dependent) or not. Module nodes: - - Nodes representing tblX.colY=expr equalities. Equality node has + - Modules representing tblX.colY=expr equalities. Equality module has = incoming edges from columns used in expr = outgoing edge to tblX.colY column. - Nodes representing unique keys. Unique key has - = incoming edges from key component value nodes - = outgoing edge to key's table node - - Inner side of outer join node. Outer join node has - = incoming edges from table value nodes + = incoming edges from key component value modules + = outgoing edge to key's table module + - Inner side of outer join module. Outer join module has + = incoming edges from table value modules = No outgoing edges. Once we reach it, we know we can eliminate the outer join. A module may depend on multiple values, and hence its primary attribute is @@ -116,10 +116,13 @@ The algorithm starts with equality nodes that don't have any incoming edges (their expressions are either constant or depend only on tables that are - outside of any outer joins) and proceeds to traverse dependency->dependant - edges until we've other traversed everything (TODO rephrase elaborate), or - we've reached the point where all outer join modules have zero unsatisfied - dependencies. + outside of the outer join in question) and performns a breadth-first + traversal. If we reach the outer join nest node, it means outer join is + functionally-dependant and can be eliminated. Otherwise it cannot. + + HANDLING MULTIPLE NESTED OUTER JOINS + (TODO : explanations why 'local bottom up is sufficient') + */ class Value_dep; @@ -143,13 +146,9 @@ class Value_dep : public Sql_alloc { public: - enum { - VALUE_FIELD, - VALUE_TABLE, - } type; /* Type of the object */ - - Value_dep(): bound(FALSE), next(NULL) - {} + Value_dep(): bound(FALSE), next(NULL) {} + virtual void now_bound(Table_elimination *te, Module_dep **bound_modules)=0; + virtual ~Value_dep() {} /* only to shut up compiler warnings */ bool bound; Value_dep *next; @@ -166,22 +165,28 @@ public: Field_value(Table_value *table_arg, Field *field_arg) : table(table_arg), field(field_arg) - { - type= Value_dep::VALUE_FIELD; - } + {} Table_value *table; /* Table this field is from */ Field *field; /* - Field_deps that belong to one table form a linked list. list members are - ordered by field_index + Field_deps that belong to one table form a linked list, ordered by + field_index */ Field_value *next_table_field; uint bitmap_offset; /* Offset of our part of the bitmap */ + + /* + Field became known. Check out + - unique keys we belong to + - expressions that depend on us. + */ + void now_bound(Table_elimination *te, Module_dep **bound_modules); + void signal_from_field_to_exprs(Table_elimination* te, + Module_dep **bound_modules); }; - /* A table value. There is one Table_value object for every table that can potentially be eliminated. @@ -192,14 +197,13 @@ { public: Table_value(TABLE *table_arg) : - table(table_arg), fields(NULL), keys(NULL), outer_join_dep(NULL) - { - type= Value_dep::VALUE_TABLE; - } + table(table_arg), fields(NULL), keys(NULL) + {} TABLE *table; Field_value *fields; /* Ordered list of fields that belong to this table */ Key_module *keys; /* Ordered list of Unique keys in this table */ - Outer_join_module *outer_join_dep; /* Innermost eliminable outer join we're in */ + //Outer_join_module *outer_join_dep; + void now_bound(Table_elimination *te, Module_dep **bound_modules); }; @@ -211,12 +215,11 @@ { public: enum { - MODULE_EXPRESSION, - MODULE_MULTI_EQUALITY, - MODULE_UNIQUE_KEY, MODULE_OUTER_JOIN } type; /* Type of the object */ + virtual bool now_bound(Table_elimination *te, Value_dep **bound_modules)=0; + virtual ~Module_dep(){} /* Used to make a linked list of elements that became bound and thus can make elements that depend on them bound, too. @@ -240,6 +243,7 @@ /* Used during condition analysis only, similar to KEYUSE::level */ uint level; + bool now_bound(Table_elimination *te, Value_dep **bound_values); }; @@ -254,17 +258,16 @@ Key_module(Table_value *table_arg, uint keyno_arg, uint n_parts_arg) : table(table_arg), keyno(keyno_arg), next_table_key(NULL) { - type= Module_dep::MODULE_UNIQUE_KEY; unknown_args= n_parts_arg; } Table_value *table; /* Table this key is from */ uint keyno; /* Unique keys form a linked list, ordered by keyno */ Key_module *next_table_key; + bool now_bound(Table_elimination *te, Value_dep **bound_values); }; - /* An outer join nest that is subject to elimination - it depends on all tables inside it @@ -273,18 +276,11 @@ class Outer_join_module: public Module_dep { public: - Outer_join_module(//TABLE_LIST *table_list_arg, - uint n_children) - // table_list(table_list_arg) + Outer_join_module(uint n_children) { - type= Module_dep::MODULE_OUTER_JOIN; unknown_args= n_children; } - /* - Outer join we're representing. This can be a join nest or one table that - is outer join'ed. - */ -// TABLE_LIST *table_list; + bool now_bound(Table_elimination *te, Value_dep **bound_values); }; @@ -307,6 +303,8 @@ /* tablenr -> Table_value* mapping. */ Table_value *table_deps[MAX_KEY]; + Outer_join_module *outer_join_dep; + /* Bitmap of how expressions depend on bits */ MY_BITMAP expr_deps; }; @@ -319,8 +317,12 @@ table_map tables_in_list, Item *on_expr, table_map tables_used_elsewhere); -static bool -check_func_dependency(Table_elimination *te, table_map tables, Item* cond); +static +bool check_func_dependency(Table_elimination *te, + table_map dep_tables, + List_iterator<TABLE_LIST> *it, + TABLE_LIST *oj_tbl, + Item* cond); static bool build_eq_deps_for_cond(Table_elimination *te, Equality_module **fdeps, @@ -332,16 +334,12 @@ Item_func *cond, Item *left, Item *right, table_map usable_tables); static -Equality_module *merge_func_deps(Equality_module *start, Equality_module *new_fields, - Equality_module *end, uint and_level); +Equality_module *merge_func_deps(Equality_module *start, + Equality_module *new_fields, + Equality_module *end, uint and_level); 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_map deps_map); -static -bool run_elimination_wave(Table_elimination *te, Module_dep *bound_modules); static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl); @@ -560,7 +558,7 @@ static Equality_module *merge_func_deps(Equality_module *start, Equality_module *new_fields, - Equality_module *end, uint and_level) + Equality_module *end, uint and_level) { if (start == new_fields) return start; // Impossible or @@ -684,7 +682,6 @@ } } - (*eq_mod)->type= Module_dep::MODULE_EXPRESSION; //psergey-todo; if (!((*eq_mod)->field= get_field_value(te, field))) return TRUE; (*eq_mod)->expression= right; @@ -763,6 +760,7 @@ created before the parents. */ +#if 0 static Outer_join_module *get_outer_join_dep(Table_elimination *te, // TABLE_LIST *outer_join, @@ -806,6 +804,7 @@ } return oj_dep; } +#endif /* @@ -879,7 +878,7 @@ uint offset= 0; for (Table_value **tbl_dep=te->table_deps; tbl_dep < te->table_deps + MAX_TABLES; - tbl_dep++) // psergey-todo: TODO change to Table_map_iterator + tbl_dep++) // psergey-todo: Wipe this out altogether { if (*tbl_dep) { @@ -1090,7 +1089,8 @@ { /* This is "... LEFT JOIN tbl ON cond" */ if (!(tbl->table->map & outside_used_tables) && - check_func_dependency(te, tbl->table->map, tbl->on_expr)) + check_func_dependency(te, tbl->table->map, NULL, tbl, + tbl->on_expr)) { mark_as_eliminated(te->join, tbl); } @@ -1108,8 +1108,9 @@ /* Try eliminating the nest we're called for */ if (all_eliminated && on_expr && !(list_tables & tables_used_elsewhere)) { + it.rewind(); return check_func_dependency(te, list_tables & ~te->join->eliminated_tables, - on_expr); + &it, NULL, on_expr); } return FALSE; /* not eliminated */ } @@ -1134,31 +1135,130 @@ */ static -bool check_func_dependency(Table_elimination *te, table_map tables, Item* cond) +bool check_func_dependency(Table_elimination *te, + table_map dep_tables, + List_iterator<TABLE_LIST> *it, + TABLE_LIST *oj_tbl, + Item* cond) { uint and_level=0; Equality_module* eq_dep= te->equality_deps; - if (build_eq_deps_for_cond(te, &eq_dep, &and_level, cond, tables)) - return TRUE; + Module_dep *bound_modules; + + bzero(te->table_deps, sizeof(te->table_deps)); + + if (oj_tbl) + { + if (!get_table_value(te, oj_tbl->table)) + return FALSE; + } + else + { + TABLE_LIST *tbl; + while ((tbl= (*it)++)) + { + if (tbl->table && (tbl->table->map & dep_tables)) + { + if (!get_table_value(te, tbl->table)) + return FALSE; + } + } + } + + /* Extract equalities from the ON expression */ + if (build_eq_deps_for_cond(te, &eq_dep, &and_level, cond, dep_tables) || + eq_dep == te->equality_deps) + return FALSE; + te->n_equality_deps= eq_dep - te->equality_deps; - Module_dep *bound_modules; - if (!get_outer_join_dep(te, tables) && - !setup_equality_deps(te, &bound_modules) && - run_elimination_wave(te, bound_modules)) - { - return TRUE; /* eliminated */ - } - return FALSE; -} - - -static -void signal_from_field_to_exprs(Table_elimination* te, Field_value *field_dep, - Module_dep **bound_modules) + /* Create objects for running wave algorithm */ + if (!(te->outer_join_dep= new Outer_join_module(my_count_bits(dep_tables))) || + setup_equality_deps(te, &bound_modules)) + { + return FALSE; /* OOM, default to non-dependent */ + } + + Value_dep *bound_values= NULL; + while (bound_modules) + { + for (;bound_modules; bound_modules= bound_modules->next) + { + if (bound_modules->now_bound(te, &bound_values)) + return TRUE; /* Dependent! */ + } + for (;bound_values; bound_values=bound_values->next) + bound_values->now_bound(te, &bound_modules); + } + return FALSE; /* Not dependent */ +} + + +/* + Table is known means that + - one more element in outer join nest is known + - all its fields are known +*/ + +void Table_value::now_bound(Table_elimination *te, + Module_dep **bound_modules) +{ + DBUG_PRINT("info", ("table %s is now bound", table->alias)); + + for (Field_value *field_dep= fields; field_dep; + field_dep= field_dep->next_table_field) + { + if (!field_dep->bound) + { + /* Mark as bound and add to the list */ + field_dep->bound= TRUE; + field_dep->signal_from_field_to_exprs(te, bound_modules); + } + } + + if (te->outer_join_dep->unknown_args && + !--te->outer_join_dep->unknown_args) + { + /* Mark as bound and add to the list */ + te->outer_join_dep->next= *bound_modules; + *bound_modules= te->outer_join_dep; + } +} + + +void Field_value::now_bound(Table_elimination *te, + Module_dep **bound_modules) +{ + DBUG_PRINT("info", ("field %s.%s is now bound", field->table->alias, + field->field_name)); + + for (Key_module *key_dep= table->keys; key_dep; + key_dep= key_dep->next_table_key) + { + if (field->part_of_key.is_set(key_dep->keyno) && + key_dep->unknown_args && !--key_dep->unknown_args) + { + DBUG_PRINT("info", ("key %s.%s is now bound", + key_dep->table->table->alias, + key_dep->table->table->key_info[key_dep->keyno].name)); + /* Mark as bound and add to the list */ + key_dep->next= *bound_modules; + *bound_modules= key_dep; + } + } + signal_from_field_to_exprs(te, bound_modules); +} + + +/* + Walk through expressions that depend on this field and 'notify' them + that this field is no longer unknown. +*/ +void Field_value::signal_from_field_to_exprs(Table_elimination* te, + Module_dep **bound_modules) { for (uint i=0; i < te->n_equality_deps; i++) { - if (bitmap_is_set(&te->expr_deps, field_dep->bitmap_offset + i) && + if (bitmap_is_set(&te->expr_deps, bitmap_offset + i) && te->equality_deps[i].unknown_args && !--te->equality_deps[i].unknown_args) { @@ -1171,131 +1271,37 @@ } -/* - Run the wave. - All Func_dep-derived objects are divided into three classes: - - Those that have bound=FALSE - - Those that have bound=TRUE - - Those that have bound=TRUE and are in the list.. -*/ - -static -bool run_elimination_wave(Table_elimination *te, Module_dep *bound_modules) -{ - Value_dep *bound_values= NULL; - while (bound_modules) - { - for (;bound_modules; bound_modules= bound_modules->next) - { - switch (bound_modules->type) - { - case Module_dep::MODULE_EXPRESSION: - { - /* It's a field=expr and we got to know the expr, so we know the field */ - Equality_module *eq_dep= (Equality_module*)bound_modules; - if (!eq_dep->field->bound) - { - /* Mark as bound and add to the list */ - eq_dep->field->bound= TRUE; - eq_dep->field->next= bound_values; - bound_values= eq_dep->field; - } - break; - } - case Module_dep::MODULE_UNIQUE_KEY: - { - /* Unique key is known means the table is known */ - Table_value *table_dep=((Key_module*)bound_modules)->table; - if (!table_dep->bound) - { - /* Mark as bound and add to the list */ - table_dep->bound= TRUE; - table_dep->next= bound_values; - bound_values= table_dep; - } - break; - } - case Module_dep::MODULE_OUTER_JOIN: - { - DBUG_PRINT("info", ("Outer join eliminated")); - return TRUE; - break; - } - case Module_dep::MODULE_MULTI_EQUALITY: - default: - DBUG_ASSERT(0); - } - } - - for (;bound_values; bound_values=bound_values->next) - { - switch (bound_values->type) - { - case Value_dep::VALUE_FIELD: - { - /* - Field became known. Check out - - unique keys we belong to - - expressions that depend on us. - */ - Field_value *field_dep= (Field_value*)bound_values; - DBUG_PRINT("info", ("field %s.%s is now bound", - field_dep->field->table->alias, - field_dep->field->field_name)); - - for (Key_module *key_dep= field_dep->table->keys; key_dep; - key_dep= key_dep->next_table_key) - { - if (field_dep->field->part_of_key.is_set(key_dep->keyno) && - key_dep->unknown_args && !--key_dep->unknown_args) - { - DBUG_PRINT("info", ("key %s.%s is now bound", - key_dep->table->table->alias, - key_dep->table->table->key_info[key_dep->keyno].name)); - /* Mark as bound and add to the list */ - key_dep->next= bound_modules; - bound_modules= key_dep; - } - } - signal_from_field_to_exprs(te, field_dep, &bound_modules); - break; - } - case Value_dep::VALUE_TABLE: - { - Table_value *table_dep=(Table_value*)bound_values; - DBUG_PRINT("info", ("table %s is now bound", - table_dep->table->alias)); - /* - Table is known means that - - one more element in outer join nest is known - - all its fields are known - */ - Outer_join_module *outer_join_dep= table_dep->outer_join_dep; - if (outer_join_dep->unknown_args && - !--outer_join_dep->unknown_args) - { - /* Mark as bound and add to the list */ - outer_join_dep->next= bound_modules; - bound_modules= outer_join_dep; - break; - } - - for (Field_value *field_dep= table_dep->fields; field_dep; - field_dep= field_dep->next_table_field) - { - if (!field_dep->bound) - { - /* Mark as bound and add to the list */ - field_dep->bound= TRUE; - signal_from_field_to_exprs(te, field_dep, &bound_modules); - } - } - break; - } - default: - DBUG_ASSERT(0); - } - } +bool Outer_join_module::now_bound(Table_elimination *te, + Value_dep **bound_values) +{ + DBUG_PRINT("info", ("Outer join eliminated")); + return TRUE; /* Signal to finish the process */ +} + + +bool Equality_module::now_bound(Table_elimination *te, + Value_dep **bound_values) +{ + /* For field=expr and we got to know the expr, so we know the field */ + if (!field->bound) + { + /* Mark as bound and add to the list */ + field->bound= TRUE; + field->next= *bound_values; + *bound_values= field; + } + return FALSE; +} + +/* Unique key is known means its table is known */ +bool Key_module::now_bound(Table_elimination *te, Value_dep **bound_values) +{ + if (!table->bound) + { + /* Mark as bound and add to the list */ + table->bound= TRUE; + table->next= *bound_values; + *bound_values= table; } return FALSE; } @@ -1304,6 +1310,7 @@ /* Mark one table or the whole join nest as eliminated. */ + static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl) { TABLE *table;

1 0

[Maria-developers] Rev 2734: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim-r11/
by Sergey Petrunya 18 Aug '09

18 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r11/ ------------------------------------------------------------ revno: 2734 revision-id: psergey(a)askmonty.org-20090818150151-uef38y50m8m1mgnu parent: psergey(a)askmonty.org-20090818130358-akd84j4m2i91lw5a committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r11 timestamp: Tue 2009-08-18 18:01:51 +0300 message: MWL#17: Table elimination - Code cleanup === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-18 13:03:58 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-18 15:01:51 +0000 @@ -275,7 +275,7 @@ public: Outer_join_module(//TABLE_LIST *table_list_arg, uint n_children) - // table_list(table_list_arg), parent(NULL) + // table_list(table_list_arg) { type= Module_dep::MODULE_OUTER_JOIN; unknown_args= n_children; @@ -285,9 +285,6 @@ is outer join'ed. */ // TABLE_LIST *table_list; - - /* Parent eliminable outer join, if any */ -// Outer_join_module *parent; }; @@ -297,7 +294,7 @@ class Table_elimination { public: - Table_elimination(JOIN *join_arg) : join(join_arg), n_outer_joins(0) + Table_elimination(JOIN *join_arg) : join(join_arg) { bzero(table_deps, sizeof(table_deps)); } @@ -310,14 +307,20 @@ /* tablenr -> Table_value* mapping. */ Table_value *table_deps[MAX_KEY]; - /* Outer joins that are candidates for elimination */ - List<Outer_join_module> oj_deps; - uint n_outer_joins; - /* Bitmap of how expressions depend on bits */ MY_BITMAP expr_deps; }; +void eliminate_tables(JOIN *join); + +static bool +eliminate_tables_for_list(Table_elimination *te, + List<TABLE_LIST> *join_list, + table_map tables_in_list, + Item *on_expr, + table_map tables_used_elsewhere); +static bool +check_func_dependency(Table_elimination *te, table_map tables, Item* cond); static bool build_eq_deps_for_cond(Table_elimination *te, Equality_module **fdeps, @@ -339,9 +342,10 @@ table_map deps_map); static 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); + + #ifndef DBUG_OFF static void dbug_print_deps(Table_elimination *te); #endif @@ -383,10 +387,6 @@ if (build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables)) return TRUE; } - /* - TODO: inject here a "if we have {t.col=const AND t.col=smth_else}, then - remove the second part" logic. - */ for (; org_key_fields != *fdeps ; org_key_fields++) org_key_fields->level= *and_level; } @@ -614,7 +614,7 @@ /* Ok, the results are within the [start, first_free) range, and the useful - elements have level==and_level. Now, lets remove all unusable elements: + elements have level==and_level. Now, remove all unusable elements: */ for (Equality_module *old=start ; old != first_free ;) { @@ -632,14 +632,31 @@ /* - Add an Equality_module element for a given predicate, if applicable + Add an Equality_module element for left=right condition + + SYNOPSIS + add_eq_dep() + te Table elimination context + eq_mod INOUT Store created Equality_module here and increment ptr if + you do so + and_level AND-level () + cond Condition we've inferred the left=right equality from. + left Left expression + right Right expression + usable_tables Create Equality_module only if Left_expression's table + belongs to this set. DESCRIPTION - This function is modeled after add_key_field(). + Check if the passed equality means that 'left' expr is functionally dependent on + the 'right', and if yes, create an Equality_module object for it. + + RETURN + FALSE OK + TRUE Out of memory */ static -bool add_eq_dep(Table_elimination *te, Equality_module **eq_dep, +bool add_eq_dep(Table_elimination *te, Equality_module **eq_mod, uint and_level, Item_func *cond, Item *left, Item *right, table_map usable_tables) { @@ -658,8 +675,8 @@ else { /* - We can't use indexes if the effective collation - of the operation differ from the field collation. + We can't assume there's a functional dependency if the effective + collation of the operation differ from the field collation. */ if (field->cmp_type() == STRING_RESULT && ((Field_str*)field)->charset() != cond->compare_collation()) @@ -667,12 +684,12 @@ } } - (*eq_dep)->type= Module_dep::MODULE_EXPRESSION; //psergey-todo; - if (!((*eq_dep)->field= get_field_value(te, field))) + (*eq_mod)->type= Module_dep::MODULE_EXPRESSION; //psergey-todo; + if (!((*eq_mod)->field= get_field_value(te, field))) return TRUE; - (*eq_dep)->expression= right; - (*eq_dep)->level= and_level; - (*eq_dep)++; + (*eq_mod)->expression= right; + (*eq_mod)->level= and_level; + (*eq_mod)++; } return FALSE; } @@ -754,7 +771,6 @@ Outer_join_module *oj_dep; if (!(oj_dep= new Outer_join_module(/*outer_join, */my_count_bits(deps_map)))) return NULL; - te->n_outer_joins++; /* Collect a bitmap fo tables that we depend on, and also set parent pointer @@ -786,25 +802,7 @@ if (!(table_dep= get_table_value(te, table))) return NULL; } - - /* - Walk from the table up to its embedding outer joins. The goal is to - find the least embedded outer join nest and set its parent pointer to - point to the newly created Outer_join_module. - to set the pointer of its near - */ - //if (!table_dep->outer_join_dep) - table_dep->outer_join_dep= oj_dep; - /* - else - { - Outer_join_module *oj= table_dep->outer_join_dep; - while (oj->parent) - oj= oj->parent; - if (oj != oj_dep) - oj->parent=oj_dep; - } - */ + table_dep->outer_join_dep= oj_dep; } return oj_dep; } @@ -815,10 +813,10 @@ that we can figure out which fields the expression depends on. */ -class Field_dependency_setter : public Field_enumerator +class Field_dependency_recorder : public Field_enumerator { public: - Field_dependency_setter(Table_elimination *te_arg): te(te_arg) + Field_dependency_recorder(Table_elimination *te_arg): te(te_arg) {} void see_field(Field *field) @@ -856,13 +854,16 @@ /* Setup equality dependencies - + SYNOPSIS setup_equality_deps() te Table elimination context bound_deps_list OUT Start of linked list of elements that were found to be bound (caller will use this to see if that allows to declare further elements bound) + DESCRIPTION + RETURN + */ static @@ -907,15 +908,15 @@ Also collect a linked list of equalities that are bound. */ Module_dep *bound_dep= NULL; - Field_dependency_setter deps_setter(te); + Field_dependency_recorder deps_recorder(te); for (Equality_module *eq_dep= te->equality_deps; eq_dep < te->equality_deps + te->n_equality_deps; eq_dep++) { - deps_setter.expr_offset= eq_dep - te->equality_deps; + deps_recorder.expr_offset= eq_dep - te->equality_deps; eq_dep->unknown_args= 0; eq_dep->expression->walk(&Item::check_column_usage_processor, FALSE, - (uchar*)&deps_setter); + (uchar*)&deps_recorder); if (!eq_dep->unknown_args) { eq_dep->next= bound_dep; @@ -935,12 +936,11 @@ SYNOPSIS eliminate_tables() join Join to work on - const_tbl_count INOUT Number of constant tables (this includes - eliminated tables) - const_tables INOUT Bitmap of constant tables DESCRIPTION - This function is the entry point for table elimination. + This is the entry point for table elimination. Grep for MODULE INTERFACE + section in this file for calling convention. + The idea behind table elimination is that if we have an outer join: SELECT * FROM t1 LEFT JOIN @@ -968,12 +968,6 @@ 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) { @@ -1023,101 +1017,54 @@ if (all_tables & ~used_tables) { /* There are some tables that we probably could eliminate. Try it. */ + //psergey-todo: move allocs to somewhere else. Table_elimination te(join); uint m= max(thd->lex->current_select->max_equal_elems,1); uint max_elems= ((thd->lex->current_select->cond_count+1)*2 + 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; - /* - if (collect_funcdeps_for_join_list(&te, join->join_list, - FALSE, - used_tables, - &eliminable_tables, - &eq_deps)) - DBUG_VOID_RETURN; - */ - eliminate_tables_for_list(&te, join->join_list, - NULL, - (table_map(1) << join->tables) - 1, + + eliminate_tables_for_list(&te, join->join_list, all_tables, NULL, used_tables); - - /*te.n_equality_deps= eq_deps_end - te.equality_deps; - - Module_dep *bound_modules; - //Value_dep *bound_values; - if (setup_equality_deps(&te, &bound_modules)) - 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. + te Table elimination context + join_list Join list to work on + list_tables Bitmap of tables embedded in the join_list. + on_expr ON expression, if the join list is the inner side + of an outer join. + NULL means it's not an outer join but rather a + top-level 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). + select list, HAVING, other ON expressions, 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. - + Perform table elimination in a given join list. + RETURN - Number of children left after elimination. 0 means everything was - eliminated. + TRUE The entire join list eliminated + FALSE Join list wasn't eliminated (but some of its possibly were) */ -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 +static bool eliminate_tables_for_list(Table_elimination *te, List<TABLE_LIST> *join_list, - Item *on_expr, - table_map tables_in_list, + table_map list_tables, Item *on_expr, 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; + bool all_eliminated= TRUE; while ((tbl= it++)) { @@ -1130,26 +1077,25 @@ /* This is "... LEFT JOIN (join_nest) ON cond" */ if (eliminate_tables_for_list(te, &tbl->nested_join->join_list, + tbl->nested_join->used_tables, tbl->on_expr, - tbl->nested_join->used_tables, outside_used_tables)) { mark_as_eliminated(te->join, tbl); } else - not_eliminated= TRUE; - + all_eliminated= FALSE; } else { /* This is "... LEFT JOIN tbl ON cond" */ if (!(tbl->table->map & outside_used_tables) && - try_eliminating(te, tbl->table->map, tbl->on_expr)) + check_func_dependency(te, tbl->table->map, tbl->on_expr)) { mark_as_eliminated(te->join, tbl); } else - not_eliminated= TRUE; + all_eliminated= FALSE; } tables_used_on_left |= tbl->on_expr->used_tables(); } @@ -1160,98 +1106,51 @@ } /* 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); - + if (all_eliminated && on_expr && !(list_tables & tables_used_elsewhere)) + { + return check_func_dependency(te, list_tables & ~te->join->eliminated_tables, + on_expr); + } return FALSE; /* not eliminated */ } -#if 0 + /* - Build functional dependency graph for elements of given join list + Check if condition makes the a set of tables functionally-dependent 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. + check_func_dependency() + te Table elimination context + tables Set of tables we want to be functionally dependent + cond Condition to use DESCRIPTION - . + Check if condition allows to conclude that the table set is functionally + dependent on everything else. + + RETURN + TRUE - Yes, functionally dependent + FALSE - No, or error */ -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) +static +bool check_func_dependency(Table_elimination *te, table_map tables, Item* cond) { - TABLE_LIST *tbl; - List_iterator<TABLE_LIST> it(*join_list); - table_map tables_used_on_left= 0; - - while ((tbl= it++)) + uint and_level=0; + Equality_module* eq_dep= te->equality_deps; + if (build_eq_deps_for_cond(te, &eq_dep, &and_level, cond, tables)) + return TRUE; + te->n_equality_deps= eq_dep - te->equality_deps; + Module_dep *bound_modules; + if (!get_outer_join_dep(te, tables) && + !setup_equality_deps(te, &bound_modules) && + run_elimination_wave(te, bound_modules)) { - 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 TRUE; /* eliminated */ } return FALSE; } -#endif -//////////////////////////// static void signal_from_field_to_exprs(Table_elimination* te, Field_value *field_dep, @@ -1272,18 +1171,18 @@ } +/* + Run the wave. + All Func_dep-derived objects are divided into three classes: + - Those that have bound=FALSE + - Those that have bound=TRUE + - Those that have bound=TRUE and are in the list.. +*/ + static bool run_elimination_wave(Table_elimination *te, Module_dep *bound_modules) { Value_dep *bound_values= NULL; - /* - Run the wave. - All Func_dep-derived objects are divided into three classes: - - Those that have bound=FALSE - - Those that have bound=TRUE - - Those that have bound=TRUE and are in the list.. - - */ while (bound_modules) { for (;bound_modules; bound_modules= bound_modules->next) @@ -1318,14 +1217,8 @@ } 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) - { - DBUG_PRINT("info", ("Table elimination eliminated everything" - " it theoretically could")); - return TRUE; - } + DBUG_PRINT("info", ("Outer join eliminated")); + return TRUE; break; } case Module_dep::MODULE_MULTI_EQUALITY: @@ -1373,10 +1266,20 @@ DBUG_PRINT("info", ("table %s is now bound", table_dep->table->alias)); /* - Table is known means + Table is known means that + - one more element in outer join nest is known - all its fields are known - - one more element in outer join nest is known */ + Outer_join_module *outer_join_dep= table_dep->outer_join_dep; + if (outer_join_dep->unknown_args && + !--outer_join_dep->unknown_args) + { + /* Mark as bound and add to the list */ + outer_join_dep->next= bound_modules; + bound_modules= outer_join_dep; + break; + } + for (Field_value *field_dep= table_dep->fields; field_dep; field_dep= field_dep->next_table_field) { @@ -1387,18 +1290,6 @@ 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) - { - if (outer_join_dep->unknown_args && - !--outer_join_dep->unknown_args) - { - /* Mark as bound and add to the list */ - outer_join_dep->next= bound_modules; - bound_modules= outer_join_dep; - } - } break; } default:

1 0

[Maria-developers] Updated (by Psergey): Add EXPLAIN for UPDATE/DELETE (51)
by worklog-noreply＠askmonty.org 18 Aug '09

18 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add EXPLAIN for UPDATE/DELETE CREATION DATE..: Tue, 18 Aug 2009, 16:24 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 51 (http://askmonty.org/worklog/?tid=51) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Tue, 18 Aug 2009, 16:25)=-=- High-Level Specification modified. --- /tmp/wklog.51.old.12524 2009-08-18 16:25:52.000000000 +0300 +++ /tmp/wklog.51.new.12524 2009-08-18 16:25:52.000000000 +0300 @@ -1 +1,22 @@ +User interface +-------------- +EXPLAIN UPDATE ... and EXPLAIN DELETE ... statements will work and produce +a tabular output similar to EXPLAIN SELECT. + +Implementation +-------------- +The primary challenge will be to change UPDATE/DELETE code to first produce +action plan and then act on it (and not make decisions on the go as it +currently does). + +What EXPLAIN will show +---------------------- +* multi-table one will show the SELECT part as usual +* single-table statements will show an equivalent of access method. + +Besides that, we want to know +- if sorting will be used +- whether the UPDATE will occur on the fly or not. + +(print or not "Using filesort"...) DESCRIPTION: Add support for EXPLAIN UPDATE/DELETE (we'd like support for all potentially long statements, e.g. for ALTER TABLE, but this WL entry is limited to UPDATE/DELETE as they are most often requested, and code that handles them is similar and distinct from other statements). HIGH-LEVEL SPECIFICATION: User interface -------------- EXPLAIN UPDATE ... and EXPLAIN DELETE ... statements will work and produce a tabular output similar to EXPLAIN SELECT. Implementation -------------- The primary challenge will be to change UPDATE/DELETE code to first produce action plan and then act on it (and not make decisions on the go as it currently does). What EXPLAIN will show ---------------------- * multi-table one will show the SELECT part as usual * single-table statements will show an equivalent of access method. Besides that, we want to know - if sorting will be used - whether the UPDATE will occur on the fly or not. (print or not "Using filesort"...) ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Psergey): Add EXPLAIN for UPDATE/DELETE (51)
by worklog-noreply＠askmonty.org 18 Aug '09

18 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add EXPLAIN for UPDATE/DELETE CREATION DATE..: Tue, 18 Aug 2009, 16:24 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 51 (http://askmonty.org/worklog/?tid=51) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Psergey - Tue, 18 Aug 2009, 16:25)=-=- High-Level Specification modified. --- /tmp/wklog.51.old.12524 2009-08-18 16:25:52.000000000 +0300 +++ /tmp/wklog.51.new.12524 2009-08-18 16:25:52.000000000 +0300 @@ -1 +1,22 @@ +User interface +-------------- +EXPLAIN UPDATE ... and EXPLAIN DELETE ... statements will work and produce +a tabular output similar to EXPLAIN SELECT. + +Implementation +-------------- +The primary challenge will be to change UPDATE/DELETE code to first produce +action plan and then act on it (and not make decisions on the go as it +currently does). + +What EXPLAIN will show +---------------------- +* multi-table one will show the SELECT part as usual +* single-table statements will show an equivalent of access method. + +Besides that, we want to know +- if sorting will be used +- whether the UPDATE will occur on the fly or not. + +(print or not "Using filesort"...) DESCRIPTION: Add support for EXPLAIN UPDATE/DELETE (we'd like support for all potentially long statements, e.g. for ALTER TABLE, but this WL entry is limited to UPDATE/DELETE as they are most often requested, and code that handles them is similar and distinct from other statements). HIGH-LEVEL SPECIFICATION: User interface -------------- EXPLAIN UPDATE ... and EXPLAIN DELETE ... statements will work and produce a tabular output similar to EXPLAIN SELECT. Implementation -------------- The primary challenge will be to change UPDATE/DELETE code to first produce action plan and then act on it (and not make decisions on the go as it currently does). What EXPLAIN will show ---------------------- * multi-table one will show the SELECT part as usual * single-table statements will show an equivalent of access method. Besides that, we want to know - if sorting will be used - whether the UPDATE will occur on the fly or not. (print or not "Using filesort"...) ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Psergey): Add EXPLAIN for UPDATE/DELETE (51)
by worklog-noreply＠askmonty.org 18 Aug '09

18 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add EXPLAIN for UPDATE/DELETE CREATION DATE..: Tue, 18 Aug 2009, 16:24 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 51 (http://askmonty.org/worklog/?tid=51) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Add support for EXPLAIN UPDATE/DELETE (we'd like support for all potentially long statements, e.g. for ALTER TABLE, but this WL entry is limited to UPDATE/DELETE as they are most often requested, and code that handles them is similar and distinct from other statements). ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] New (by Psergey): Add EXPLAIN for UPDATE/DELETE (51)
by worklog-noreply＠askmonty.org 18 Aug '09

18 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add EXPLAIN for UPDATE/DELETE CREATION DATE..: Tue, 18 Aug 2009, 16:24 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 51 (http://askmonty.org/worklog/?tid=51) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Add support for EXPLAIN UPDATE/DELETE (we'd like support for all potentially long statements, e.g. for ALTER TABLE, but this WL entry is limited to UPDATE/DELETE as they are most often requested, and code that handles them is similar and distinct from other statements). ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Rev 2733: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim-r11/
by Sergey Petrunya 18 Aug '09

18 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r11/ ------------------------------------------------------------ revno: 2733 revision-id: psergey(a)askmonty.org-20090818130358-akd84j4m2i91lw5a parent: psergey(a)askmonty.org-20090817160724-fmmrmwp8zorzn82q committer: Sergey Petrunya <psergey(a)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; }

1 0

[Maria-developers] Rev 2732: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim-r10/
by Sergey Petrunya 17 Aug '09

17 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r10/ ------------------------------------------------------------ revno: 2732 revision-id: psergey(a)askmonty.org-20090817160724-fmmrmwp8zorzn82q parent: psergey(a)askmonty.org-20090817150229-jy461nqbmk8nzhha committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r10 timestamp: Mon 2009-08-17 19:07:24 +0300 message: MWL#17: Table elimination - More testcases === modified file 'mysql-test/r/table_elim.result' --- a/mysql-test/r/table_elim.result 2009-08-17 15:02:29 +0000 +++ b/mysql-test/r/table_elim.result 2009-08-17 16:07:24 +0000 @@ -218,4 +218,48 @@ id select_type table type possible_keys key key_len ref rows Extra 1 SIMPLE t1 ALL NULL NULL NULL NULL 2 1 SIMPLE t2 eq_ref PRIMARY PRIMARY 4 test.t1.col 1 +drop table t1, t2, t3; +# +# Check things that look like functional dependencies but really are not +# +create table t1 (a char(10) character set latin1 collate latin1_general_ci primary key); +insert into t1 values ('foo'); +insert into t1 values ('bar'); +create table t2 (a char(10) character set latin1 collate latin1_general_cs primary key); +insert into t2 values ('foo'); +insert into t2 values ('FOO'); +this must not use table elimination: +explain select t1.* from t1 left join t2 on t2.a='foo' collate latin1_general_ci; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index NULL PRIMARY 10 NULL 2 Using index +1 SIMPLE t2 index PRIMARY PRIMARY 10 NULL 2 Using index +this must not use table elimination: +explain select t1.* from t1 left join t2 on t2.a=t1.a collate latin1_general_ci; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index NULL PRIMARY 10 NULL 2 Using index +1 SIMPLE t2 index PRIMARY PRIMARY 10 NULL 2 Using index +drop table t1,t2; +create table t1 (a int primary key); +insert into t1 values (1),(2); +create table t2 (a char(10) primary key); +insert into t2 values ('1'),('1.0'); +this must not use table elimination: +explain select t1.* from t1 left join t2 on t2.a=1; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index NULL PRIMARY 4 NULL 2 Using index +1 SIMPLE t2 index PRIMARY PRIMARY 10 NULL 2 Using index +this must not use table elimination: +explain select t1.* from t1 left join t2 on t2.a=t1.a; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index NULL PRIMARY 4 NULL 2 Using index +1 SIMPLE t2 index PRIMARY PRIMARY 10 NULL 2 Using index +drop table t1, t2; +create table t1 (a char(10) primary key); +insert into t1 values ('foo'),('bar'); +create table t2 (a char(10), unique key(a(2))); +insert into t2 values ('foo'),('bar'); +explain select t1.* from t1 left join t2 on t2.a=t1.a; +id select_type table type possible_keys key key_len ref rows Extra +1 SIMPLE t1 index NULL PRIMARY 10 NULL 2 Using index +1 SIMPLE t2 ref a a 3 test.t1.a 2 drop table t1, t2; === modified file 'mysql-test/t/table_elim.test' --- a/mysql-test/t/table_elim.test 2009-08-17 15:02:29 +0000 +++ b/mysql-test/t/table_elim.test 2009-08-17 16:07:24 +0000 @@ -175,5 +175,46 @@ explain select t1.*, t2.* from t1 left join (t2 left join t3 on t3.pk=t2.col) on t2.pk=t1.col; +drop table t1, t2, t3; + +--echo # +--echo # Check things that look like functional dependencies but really are not +--echo # + +create table t1 (a char(10) character set latin1 collate latin1_general_ci primary key); +insert into t1 values ('foo'); +insert into t1 values ('bar'); + +create table t2 (a char(10) character set latin1 collate latin1_general_cs primary key); +insert into t2 values ('foo'); +insert into t2 values ('FOO'); + +-- echo this must not use table elimination: +explain select t1.* from t1 left join t2 on t2.a='foo' collate latin1_general_ci; + +-- echo this must not use table elimination: +explain select t1.* from t1 left join t2 on t2.a=t1.a collate latin1_general_ci; +drop table t1,t2; + +create table t1 (a int primary key); +insert into t1 values (1),(2); +create table t2 (a char(10) primary key); +insert into t2 values ('1'),('1.0'); +-- echo this must not use table elimination: +explain select t1.* from t1 left join t2 on t2.a=1; +-- echo this must not use table elimination: +explain select t1.* from t1 left join t2 on t2.a=t1.a; + +drop table t1, t2; +# partial unique keys do not work at the moment, although they are able to +# provide one-match guarantees: +create table t1 (a char(10) primary key); +insert into t1 values ('foo'),('bar'); + +create table t2 (a char(10), unique key(a(2))); +insert into t2 values ('foo'),('bar'); + +explain select t1.* from t1 left join t2 on t2.a=t1.a; + drop table t1, t2;

1 0