August 2009 - developers - lists.mariadb.org

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

20 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r11/ ------------------------------------------------------------ revno: 2739 revision-id: psergey(a)askmonty.org-20090820155102-5zvm1m6idmie9mmv parent: psergey(a)askmonty.org-20090819120659-0ndd6mqxeetgee2n committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r11 timestamp: Thu 2009-08-20 17:51:02 +0200 message: MWL#17: Table elimination - Multiple-equality handling === modified file 'sql/item_cmpfunc.h' --- a/sql/item_cmpfunc.h 2008-12-12 11:13:11 +0000 +++ b/sql/item_cmpfunc.h 2009-08-20 15:51:02 +0000 @@ -1578,6 +1578,7 @@ uint members(); bool contains(Field *field); Item_field* get_first() { return fields.head(); } + uint n_fields() { return fields.elements; } void merge(Item_equal *item); void update_const(); enum Functype functype() const { return MULT_EQUAL_FUNC; } === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-19 12:06:59 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-20 15:51:02 +0000 @@ -175,7 +175,10 @@ field_index */ Field_value *next_table_field; - uint bitmap_offset; /* Offset of our part of the bitmap */ + /* + Offset of our part of the bitmap psergey-todo: better comment! + */ + uint bitmap_offset; /* Field became known. Check out @@ -214,10 +217,6 @@ class Module_dep : public Sql_alloc { public: - enum { - MODULE_OUTER_JOIN - } type; /* Type of the object */ - virtual bool now_bound(Func_dep_analyzer *fda, Value_dep **bound_modules)=0; virtual ~Module_dep(){} /* @@ -232,8 +231,10 @@ /* - A "tbl.column= expr" equality dependency. tbl.column depends on fields - used in expr. + This represents either + - "tbl.column= expr" equality dependency, i.e. tbl.column depends on fields + used in the expression, or + - tbl1.col1=tbl2.col2=... multi-equality. */ class Equality_module : public Module_dep { @@ -241,6 +242,8 @@ Field_value *field; Item *expression; + List<Field_value> *mult_equal_fields; + /* Used during condition analysis only, similar to KEYUSE::level */ uint level; bool now_bound(Func_dep_analyzer *fda, Value_dep **bound_values); @@ -331,7 +334,7 @@ Item* cond); static -void build_eq_mods_for_cond(Func_dep_analyzer *fda, Equality_module **fdeps, +void build_eq_mods_for_cond(Func_dep_analyzer *fda, Equality_module **eq_mod, uint *and_level, Item *cond); static void add_eq_mod(Func_dep_analyzer *fda, Equality_module **eq_mod, @@ -346,6 +349,9 @@ static Field_value *get_field_value(Func_dep_analyzer *fda, Field *field); static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl); +static void add_eq_mod2(Func_dep_analyzer *fda, Equality_module **eq_mod, + uint and_level, Field_value *field_val, Item *right, + List<Field_value>* mult_equal_fields); #ifndef DBUG_OFF @@ -360,7 +366,7 @@ SYNOPSIS build_eq_mods_for_cond() fda Table elimination context - fdeps INOUT Put produced equality conditions here + eq_mod INOUT Put produced equality conditions here and_level INOUT AND-level (like in add_key_fields) cond Condition to process @@ -369,34 +375,34 @@ */ static -void build_eq_mods_for_cond(Func_dep_analyzer *fda, Equality_module **fdeps, +void build_eq_mods_for_cond(Func_dep_analyzer *fda, Equality_module **eq_mod, uint *and_level, Item *cond) { if (cond->type() == Item_func::COND_ITEM) { List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list()); - Equality_module *org_key_fields= *fdeps; + Equality_module *org_key_fields= *eq_mod; /* AND/OR */ if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC) { Item *item; while ((item=li++)) - build_eq_mods_for_cond(fda, fdeps, and_level, item); - for (; org_key_fields != *fdeps ; org_key_fields++) + build_eq_mods_for_cond(fda, eq_mod, and_level, item); + for (; org_key_fields != *eq_mod ; org_key_fields++) org_key_fields->level= *and_level; } else { Item *item; (*and_level)++; - build_eq_mods_for_cond(fda, fdeps, and_level, li++); + build_eq_mods_for_cond(fda, eq_mod, and_level, li++); while ((item=li++)) { - Equality_module *start_key_fields= *fdeps; + Equality_module *start_key_fields= *eq_mod; (*and_level)++; - build_eq_mods_for_cond(fda, fdeps, and_level, item); - *fdeps= merge_func_deps(org_key_fields, start_key_fields, *fdeps, + build_eq_mods_for_cond(fda, eq_mod, and_level, item); + *eq_mod= merge_func_deps(org_key_fields, start_key_fields, *eq_mod, ++(*and_level)); } } @@ -414,8 +420,8 @@ { if (cond_func->argument_count() == 2) { - add_eq_mod(fda, fdeps, *and_level, cond_func, args[0], args[1]); - add_eq_mod(fda, fdeps, *and_level, cond_func, args[1], args[0]); + add_eq_mod(fda, eq_mod, *and_level, cond_func, args[0], args[1]); + add_eq_mod(fda, eq_mod, *and_level, cond_func, args[1], args[0]); } break; } @@ -426,62 +432,72 @@ (fld= args[0]->real_item())->type() == Item::FIELD_ITEM && args[1]->eq(args[2], ((Item_field*)fld)->field->binary())) { - add_eq_mod(fda, fdeps, *and_level, cond_func, args[0], args[1]); - add_eq_mod(fda, fdeps, *and_level, cond_func, args[1], args[0]); + add_eq_mod(fda, eq_mod, *and_level, cond_func, args[0], args[1]); + add_eq_mod(fda, eq_mod, *and_level, cond_func, args[1], args[0]); } break; } case Item_func::EQ_FUNC: case Item_func::EQUAL_FUNC: { - add_eq_mod(fda, fdeps, *and_level, cond_func, args[0], args[1]); - add_eq_mod(fda, fdeps, *and_level, cond_func, args[1], args[0]); + add_eq_mod(fda, eq_mod, *and_level, cond_func, args[0], args[1]); + add_eq_mod(fda, eq_mod, *and_level, cond_func, args[1], args[0]); break; } case Item_func::ISNULL_FUNC: { Item *tmp=new Item_null; if (tmp) - add_eq_mod(fda, fdeps, *and_level, cond_func, args[0], args[1]); + add_eq_mod(fda, eq_mod, *and_level, cond_func, args[0], args[1]); break; } case Item_func::MULT_EQUAL_FUNC: { - Item_equal *item_equal= (Item_equal *) cond; - Item *const_item= item_equal->get_const(); + Item_equal *item_equal= (Item_equal*)cond; + // const item is 'item', field -> NULL. mult_equal_fields <-- an ordered + // list of + List<Field_value> *fvl; + if (!(fvl= new List<Field_value>)) + break; + Item_equal_iterator it(*item_equal); Item_field *item; - if (const_item) - { - /* - For each field field1 from item_equal consider the equality - field1=const_item as a condition allowing an index access of the table - with field1 by the keys value of field1. - */ - while ((item= it++)) - add_eq_mod(fda, fdeps, *and_level, cond_func, item, const_item); - } - else - { - /* - Consider all pairs of different fields included into item_equal. - For each of them (field1, field1) consider the equality - field1=field2 as a condition allowing an index access of the table - with field1 by the keys value of field2. - */ - Item_equal_iterator fi(*item_equal); - while ((item= fi++)) + Item *bound_item= item_equal->get_const(); + while ((item= it++)) + { + if ((item->used_tables() & fda->usable_tables)) { - Field *field= item->field; - Item_field *item2; - while ((item2= it++)) + Field_value *field_val; + if ((field_val= get_field_value(fda, item->field))) { - if (!field->eq(item2->field)) - add_eq_mod(fda, fdeps, *and_level, cond_func, item, item2); + List_iterator<Field_value> it2(*fvl); + Field_value *other_f; + uint field_val_ratio= field_val->field->table->tablenr*MAX_FIELDS + + field_val->field->field_index; + bool added= FALSE; + while ((other_f= it2++)) + { + uint other_f_ratio= other_f->field->table->tablenr*MAX_FIELDS + + other_f->field->field_index; + if (other_f_ratio > field_val_ratio) + { + *(it2.ref())= field_val; + it2.after(other_f); + added= TRUE; + break; + } + } + if (!added) + fvl->push_back(field_val); } - it.rewind(); + } + else + { + if (!bound_item) + bound_item= item; } } + add_eq_mod2(fda, eq_mod, *and_level, NULL, bound_item, fvl); break; } default: @@ -491,6 +507,39 @@ /* + The only requirement of this function is to order fields in some + deterministic way. +*/ + +int cmp_equal_fields(Item_field *field1, Item_field *field2, void *arg) +{ + int cmp= 0; + bool outer_ref= 0; + if (field2->used_tables() & OUTER_REF_TABLE_BIT) + { + outer_ref= 1; + cmp= -1; + } + if (field2->used_tables() & OUTER_REF_TABLE_BIT) + { + outer_ref= 1; + cmp++; + } + if (outer_ref) + return cmp; + cmp= (int)field2->field->table->tablenr - + (int)field1->field->table->tablenr; + if (cmp) + return cmp < 0 ? -1 : 1; + cmp= (int)field2->field->field_index - + (int)field1->field->field_index; + + return cmp < 0 ? -1 : (cmp ? 1 : 0); + +} + + +/* Perform an OR operation on two (adjacent) Equality_module arrays. SYNOPSIS @@ -540,9 +589,9 @@ Equality_module *end, uint and_level) { if (start == new_fields) - return start; // Impossible or + return start; // Impossible or if (new_fields == end) - return start; // No new fields, skip all + return start; // No new fields, skip all Equality_module *first_free=new_fields; @@ -551,40 +600,119 @@ for (Equality_module *old=start ; old != first_free ; old++) { /* - TODO: does it make sense to attempt to merging multiple-equalities? - A: YES. - (a=b=c) OR (a=b=d) produce "a=b". - QQ: - What to use for merging? Trivial N*M algorithm or pre-sort and then - merge ordered sequences? + Merge multiple-equalities: + A: YES. + (a=b=c) OR (a=b=d) produce "a=b". + + TODO: + sort by (table_ptr, column_index) + then run along the two and produce an intersection + + Q: What about constants? + a=b=3 OR a=b=5 -> a=b= (either 3 or 5) + + a=b OR a=b=5 -> a=b= (any constant) + A: keep the constant iff it is present in both sides and is the same. + + class Multi_equality + { + Item *const_item; + List<...) list; + }; + */ if (old->field == new_fields->field) { - if (!new_fields->expression->const_item()) - { - /* - If the value matches, we can use the key reference. - If not, we keep it until we have examined all new values - */ - if (old->expression->eq(new_fields->expression, old->field->field->binary())) - { - old->level= and_level; - } - } - else if (old->expression->eq_by_collation(new_fields->expression, - old->field->field->binary(), - old->field->field->charset())) - { - old->level= and_level; - } - else - { + if (!old->field) + { + /* + OR-ing two multiple equalities. We must compute an intersection of + used fields, and check the constants according to these rules: + + a=b=c=d OR a=c=e=f -> a=c (compute intersection) + a=const1 OR a=b -> (nothing) + a=const1 OR a=const1 -> a=const1 + a=const1 OR a=const2 -> (nothing) + + If we're performing an OR operation over multiple equalities, e.g. + + (a=b=c AND p=q) OR (a=b AND v=z) + + then we'll need to try combining each equality with each. ANDed + equalities are guaranteed to be disjoint, so we'll only get one + hit. + */ + if (old->expression && new_fields->expression && + old->expression->eq_by_collation(new_fields->expression, + old->mult_equal_fields->head()->field->binary(), + old->mult_equal_fields->head()->field->charset())) + { + /* Ok, keep */ + } + else + { + // no single constant/bound item. + old->expression= NULL; + } + + List <Field_value> *fv; + if (!(fv= new List<Field_value>)) + break; + + List_iterator<Field_value> it1(*old->mult_equal_fields); + List_iterator<Field_value> it2(*new_fields->mult_equal_fields); + Field_value *lfield= it1++; + Field_value *rfield= it2++; + // Merge + while (lfield && rfield) + { + if (lfield == rfield) + fv->push_back(lfield); + else + { + uint left_ratio= lfield->field->table->tablenr*MAX_FIELDS + + lfield->field->field_index; + uint right_ratio= rfield->field->table->tablenr*MAX_FIELDS + + rfield->field->field_index; + if (left_ratio < right_ratio) + lfield=it1++; + else + rfield=it2++; + } + } + + if (fv->elements + test(old->expression) > 1) + { + old->mult_equal_fields= fv; + old->level= and_level; + } + } + else if (!new_fields->expression->const_item()) + { + /* + If the value matches, we can use the key reference. + If not, we keep it until we have examined all new values + */ + if (old->expression->eq(new_fields->expression, + old->field->field->binary())) + { + old->level= and_level; + } + } + else if (old->expression->eq_by_collation(new_fields->expression, + old->field->field->binary(), + old->field->field->charset())) + { + old->level= and_level; + } + else + { /* The expressions are different. */ - if (old == --first_free) // If last item - break; - *old= *first_free; // Remove old value - old--; // Retry this value - } + if (old == --first_free) // If last item + break; + *old= *first_free; // Remove old value + old--; // Retry this value + } } } } @@ -596,10 +724,10 @@ for (Equality_module *old=start ; old != first_free ;) { if (old->level != and_level) - { // Not used in all levels + { // Not used in all levels if (old == --first_free) - break; - *old= *first_free; // Remove old value + break; + *old= *first_free; // Remove old value continue; } old++; @@ -659,33 +787,42 @@ return; } } - - if (*eq_mod == fda->equality_mods + fda->n_equality_mods_alloced) - { - /* - We've filled the entire equality_mods array. Replace it with a bigger - one. We do it somewhat inefficiently but it doesn't matter. - */ - Equality_module *new_arr; - if (!(new_arr= new Equality_module[fda->n_equality_mods_alloced *2])) - return; - fda->n_equality_mods_alloced *= 2; - for (int i= 0; i < *eq_mod - fda->equality_mods; i++) - new_arr[i]= fda->equality_mods[i]; - - fda->equality_mods= new_arr; - *eq_mod= new_arr + (*eq_mod - fda->equality_mods); - } - - if (!((*eq_mod)->field= get_field_value(fda, field))) + Field_value *field_val; + if ((field_val= get_field_value(fda, field))) + add_eq_mod2(fda, eq_mod, and_level, field_val, right, NULL); + } +} + + +/* Just add eq_mod w/o any checks */ +static void add_eq_mod2(Func_dep_analyzer *fda, Equality_module **eq_mod, + uint and_level, Field_value *field_val, Item *right, + List<Field_value>* mult_equal_fields) +{ + if (*eq_mod == fda->equality_mods + fda->n_equality_mods_alloced) + { + /* + We've filled the entire equality_mods array. Replace it with a bigger + one. We do it somewhat inefficiently but it doesn't matter. + */ + Equality_module *new_arr; + if (!(new_arr= new Equality_module[fda->n_equality_mods_alloced *2])) return; - (*eq_mod)->expression= right; - (*eq_mod)->level= and_level; - (*eq_mod)++; + fda->n_equality_mods_alloced *= 2; + for (int i= 0; i < *eq_mod - fda->equality_mods; i++) + new_arr[i]= fda->equality_mods[i]; + + fda->equality_mods= new_arr; + *eq_mod= new_arr + (*eq_mod - fda->equality_mods); } + + (*eq_mod)->field= field_val; + (*eq_mod)->expression= right; + (*eq_mod)->level= and_level; + (*eq_mod)->mult_equal_fields= mult_equal_fields; + (*eq_mod)++; } - /* Get a Table_value object for the given table, creating it if necessary. */ @@ -782,11 +919,15 @@ */ fda->equality_mods[expr_offset].unknown_args++; } + else + saw_other_tbl= TRUE; } Func_dep_analyzer *fda; /* Offset of the expression we're processing in the dependency bitmap */ - uint expr_offset; + uint expr_offset; + + bool saw_other_tbl; }; @@ -858,9 +999,21 @@ eq_mod++) { deps_recorder.expr_offset= eq_mod - fda->equality_mods; + deps_recorder.saw_other_tbl= FALSE; eq_mod->unknown_args= 0; + + /* Regular tbl.col=expr(tblX1.col1, tblY1.col2, ...) */ eq_mod->expression->walk(&Item::check_column_usage_processor, FALSE, (uchar*)&deps_recorder); + + if (!eq_mod->field) + { + if (eq_mod->unknown_args) + eq_mod->unknown_args= 1; + if (deps_recorder.saw_other_tbl) + eq_mod->unknown_args= 0; + } + if (!eq_mod->unknown_args) { eq_mod->next= bound_dep; @@ -1235,12 +1388,30 @@ 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; + if (mult_equal_fields) + { + List_iterator<Field_value> it(*mult_equal_fields); + Field_value *fv; + while ((fv= it++)) + { + if (!fv->bound) + { + /* Mark as bound and add to the list */ + fv->bound= TRUE; + fv->next= *bound_values; + *bound_values= fv; + } + } + } + else + { + if (!field->bound) + { + /* Mark as bound and add to the list */ + field->bound= TRUE; + field->next= *bound_values; + *bound_values= field; + } } return FALSE; } @@ -1313,11 +1484,19 @@ String str(buf, sizeof(buf), &my_charset_bin); str.length(0); eq_mod->expression->print(&str, QT_ORDINARY); - fprintf(DBUG_FILE, " equality%d: %s -> %s.%s\n", - eq_mod - fda->equality_mods, - str.c_ptr(), - eq_mod->field->table->table->alias, - eq_mod->field->field->field_name); + if (eq_mod->field) + { + fprintf(DBUG_FILE, " equality%d: %s -> %s.%s\n", + eq_mod - fda->equality_mods, + str.c_ptr(), + eq_mod->field->table->table->alias, + eq_mod->field->field->field_name); + } + else + { + fprintf(DBUG_FILE, " equality%d: multi-equality", + eq_mod - fda->equality_mods); + } } fprintf(DBUG_FILE,"\n");

1 0

[Maria-developers] Rev 2738: Variable/function renames 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: 2738 revision-id: psergey(a)askmonty.org-20090819120659-0ndd6mqxeetgee2n parent: psergey(a)askmonty.org-20090819101838-55ys0h923olqz4q9 committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r11 timestamp: Wed 2009-08-19 15:06:59 +0300 message: Variable/function renames === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-19 10:18:38 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-19 12:06:59 +0000 @@ -147,7 +147,7 @@ { public: Value_dep(): bound(FALSE), next(NULL) {} - virtual void now_bound(Func_dep_analyzer *te, Module_dep **bound_modules)=0; + virtual void now_bound(Func_dep_analyzer *fda, 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(Func_dep_analyzer *te, Module_dep **bound_modules); - void signal_from_field_to_exprs(Func_dep_analyzer* te, + void now_bound(Func_dep_analyzer *fda, Module_dep **bound_modules); + void signal_from_field_to_exprs(Func_dep_analyzer* fda, 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(Func_dep_analyzer *te, Module_dep **bound_modules); + void now_bound(Func_dep_analyzer *fda, Module_dep **bound_modules); }; @@ -218,7 +218,7 @@ MODULE_OUTER_JOIN } type; /* Type of the object */ - virtual bool now_bound(Func_dep_analyzer *te, Value_dep **bound_modules)=0; + virtual bool now_bound(Func_dep_analyzer *fda, 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(Func_dep_analyzer *te, Value_dep **bound_values); + bool now_bound(Func_dep_analyzer *fda, 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(Func_dep_analyzer *te, Value_dep **bound_values); + bool now_bound(Func_dep_analyzer *fda, Value_dep **bound_values); }; @@ -280,7 +280,7 @@ { unknown_args= n_children; } - bool now_bound(Func_dep_analyzer *te, Value_dep **bound_values); + bool now_bound(Func_dep_analyzer *fda, Value_dep **bound_values); }; @@ -301,9 +301,9 @@ 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; + Equality_module *equality_mods; + uint n_equality_mods; /* Number of elements in the array */ + uint n_equality_mods_alloced; /* tablenr -> Table_value* mapping. */ Table_value *table_deps[MAX_KEY]; @@ -331,10 +331,10 @@ Item* cond); static -bool build_eq_deps_for_cond(Func_dep_analyzer *te, Equality_module **fdeps, +void build_eq_mods_for_cond(Func_dep_analyzer *fda, Equality_module **fdeps, uint *and_level, Item *cond); static -bool add_eq_dep(Func_dep_analyzer *te, Equality_module **eq_dep, +void add_eq_mod(Func_dep_analyzer *fda, Equality_module **eq_mod, uint and_level, Item_func *cond, Item *left, Item *right); static @@ -342,14 +342,14 @@ Equality_module *new_fields, Equality_module *end, uint and_level); -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 Table_value *get_table_value(Func_dep_analyzer *fda, TABLE *table); +static Field_value *get_field_value(Func_dep_analyzer *fda, Field *field); static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl); #ifndef DBUG_OFF -static void dbug_print_deps(Func_dep_analyzer *te); +static void dbug_print_deps(Func_dep_analyzer *fda); #endif /*******************************************************************************************/ @@ -358,17 +358,18 @@ Produce Eq_dep elements for given condition. SYNOPSIS - build_eq_deps_for_cond() - te Table elimination context + build_eq_mods_for_cond() + fda Table elimination context fdeps INOUT Put produced equality conditions here and_level INOUT AND-level (like in add_key_fields) cond Condition to process + DESCRIPTION This function is modeled after add_key_fields() */ static -bool build_eq_deps_for_cond(Func_dep_analyzer *te, Equality_module **fdeps, +void build_eq_mods_for_cond(Func_dep_analyzer *fda, Equality_module **fdeps, uint *and_level, Item *cond) { if (cond->type() == Item_func::COND_ITEM) @@ -381,34 +382,29 @@ { Item *item; while ((item=li++)) - { - if (build_eq_deps_for_cond(te, fdeps, and_level, item)) - return TRUE; - } + build_eq_mods_for_cond(fda, fdeps, and_level, item); for (; org_key_fields != *fdeps ; org_key_fields++) org_key_fields->level= *and_level; } else { + Item *item; (*and_level)++; - if (build_eq_deps_for_cond(te, fdeps, and_level, li++)) - return TRUE; - Item *item; + build_eq_mods_for_cond(fda, fdeps, and_level, li++); while ((item=li++)) { Equality_module *start_key_fields= *fdeps; (*and_level)++; - if (build_eq_deps_for_cond(te, fdeps, and_level, item)) - return TRUE; + build_eq_mods_for_cond(fda, fdeps, and_level, item); *fdeps= merge_func_deps(org_key_fields, start_key_fields, *fdeps, ++(*and_level)); } } - return FALSE; + return; } if (cond->type() != Item::FUNC_ITEM) - return FALSE; + return; Item_func *cond_func= (Item_func*) cond; Item **args= cond_func->arguments(); @@ -418,10 +414,10 @@ { if (cond_func->argument_count() == 2) { - 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; + add_eq_mod(fda, fdeps, *and_level, cond_func, args[0], args[1]); + add_eq_mod(fda, fdeps, *and_level, cond_func, args[1], args[0]); } + break; } case Item_func::BETWEEN: { @@ -430,24 +426,23 @@ (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]) || - add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0])) - return TRUE; + add_eq_mod(fda, fdeps, *and_level, cond_func, args[0], args[1]); + add_eq_mod(fda, fdeps, *and_level, cond_func, args[1], args[0]); } break; } case Item_func::EQ_FUNC: case Item_func::EQUAL_FUNC: { - 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]); + add_eq_mod(fda, fdeps, *and_level, cond_func, args[0], args[1]); + add_eq_mod(fda, 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])) - return TRUE; + if (tmp) + add_eq_mod(fda, fdeps, *and_level, cond_func, args[0], args[1]); break; } case Item_func::MULT_EQUAL_FUNC: @@ -462,12 +457,9 @@ For each field field1 from item_equal consider the equality field1=const_item as a condition allowing an index access of the table with field1 by the keys value of field1. - */ + */ while ((item= it++)) - { - if (add_eq_dep(te, fdeps, *and_level, cond_func, item, const_item)) - return TRUE; - } + add_eq_mod(fda, fdeps, *and_level, cond_func, item, const_item); } else { @@ -485,10 +477,7 @@ while ((item2= it++)) { if (!field->eq(item2->field)) - { - if (add_eq_dep(te, fdeps, *and_level, cond_func, item, item2)) - return TRUE; - } + add_eq_mod(fda, fdeps, *and_level, cond_func, item, item2); } it.rewind(); } @@ -498,7 +487,6 @@ default: break; } - return FALSE; } @@ -624,8 +612,8 @@ Add an Equality_module element for left=right condition SYNOPSIS - add_eq_dep() - te Table elimination context + add_eq_mod() + fda Table elimination context eq_mod INOUT Store created Equality_module here and increment ptr if you do so and_level AND-level () @@ -645,10 +633,10 @@ */ static -bool add_eq_dep(Func_dep_analyzer *te, Equality_module **eq_mod, +void add_eq_mod(Func_dep_analyzer *fda, Equality_module **eq_mod, uint and_level, Item_func *cond, Item *left, Item *right) { - if ((left->used_tables() & te->usable_tables) && + if ((left->used_tables() & fda->usable_tables) && !(right->used_tables() & RAND_TABLE_BIT) && left->real_item()->type() == Item::FIELD_ITEM) { @@ -658,7 +646,7 @@ if (right->result_type() != STRING_RESULT) { if (field->cmp_type() != right->result_type()) - return FALSE; + return; } else { @@ -668,17 +656,33 @@ */ if (field->cmp_type() == STRING_RESULT && ((Field_str*)field)->charset() != cond->compare_collation()) - return FALSE; + return; } } - - if (!((*eq_mod)->field= get_field_value(te, field))) - return TRUE; + + if (*eq_mod == fda->equality_mods + fda->n_equality_mods_alloced) + { + /* + We've filled the entire equality_mods array. Replace it with a bigger + one. We do it somewhat inefficiently but it doesn't matter. + */ + Equality_module *new_arr; + if (!(new_arr= new Equality_module[fda->n_equality_mods_alloced *2])) + return; + fda->n_equality_mods_alloced *= 2; + for (int i= 0; i < *eq_mod - fda->equality_mods; i++) + new_arr[i]= fda->equality_mods[i]; + + fda->equality_mods= new_arr; + *eq_mod= new_arr + (*eq_mod - fda->equality_mods); + } + + if (!((*eq_mod)->field= get_field_value(fda, field))) + return; (*eq_mod)->expression= right; (*eq_mod)->level= and_level; (*eq_mod)++; } - return FALSE; } @@ -686,7 +690,7 @@ Get a Table_value object for the given table, creating it if necessary. */ -static Table_value *get_table_value(Func_dep_analyzer *te, TABLE *table) +static Table_value *get_table_value(Func_dep_analyzer *fda, TABLE *table) { Table_value *tbl_dep; if (!(tbl_dep= new Table_value(table))) @@ -704,7 +708,7 @@ key_list= &(key_dep->next_table_key); } } - return te->table_deps[table->tablenr]= tbl_dep; + return fda->table_deps[table->tablenr]= tbl_dep; } @@ -712,15 +716,15 @@ Get a Field_value object for the given field, creating it if necessary */ -static Field_value *get_field_value(Func_dep_analyzer *te, Field *field) +static Field_value *get_field_value(Func_dep_analyzer *fda, Field *field) { TABLE *table= field->table; Table_value *tbl_dep; /* First, get the table*/ - if (!(tbl_dep= te->table_deps[table->tablenr])) + if (!(tbl_dep= fda->table_deps[table->tablenr])) { - if (!(tbl_dep= get_table_value(te, table))) + if (!(tbl_dep= get_table_value(fda, table))) return NULL; } @@ -750,13 +754,13 @@ class Field_dependency_recorder : public Field_enumerator { public: - Field_dependency_recorder(Func_dep_analyzer *te_arg): te(te_arg) + Field_dependency_recorder(Func_dep_analyzer *te_arg): fda(te_arg) {} void see_field(Field *field) { Table_value *tbl_dep; - if ((tbl_dep= te->table_deps[field->table->tablenr])) + if ((tbl_dep= fda->table_deps[field->table->tablenr])) { for (Field_value *field_dep= tbl_dep->fields; field_dep; field_dep= field_dep->next_table_field) @@ -764,9 +768,9 @@ if (field->field_index == field_dep->field->field_index) { uint offs= field_dep->bitmap_offset + expr_offset; - if (!bitmap_is_set(&te->expr_deps, offs)) - te->equality_deps[expr_offset].unknown_args++; - bitmap_set_bit(&te->expr_deps, offs); + if (!bitmap_is_set(&fda->expr_deps, offs)) + fda->equality_mods[expr_offset].unknown_args++; + bitmap_set_bit(&fda->expr_deps, offs); return; } } @@ -776,11 +780,11 @@ Bump the dependency anyway, this will signal that this dependency cannot be satisfied. */ - te->equality_deps[expr_offset].unknown_args++; + fda->equality_mods[expr_offset].unknown_args++; } } - Func_dep_analyzer *te; + Func_dep_analyzer *fda; /* Offset of the expression we're processing in the dependency bitmap */ uint expr_offset; }; @@ -791,7 +795,7 @@ SYNOPSIS setup_equality_modules_deps() - te Table elimination context + fda 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) @@ -807,7 +811,7 @@ */ static -bool setup_equality_modules_deps(Func_dep_analyzer *te, +bool setup_equality_modules_deps(Func_dep_analyzer *fda, Module_dep **bound_deps_list) { DBUG_ENTER("setup_equality_modules_deps"); @@ -817,8 +821,8 @@ value. */ uint offset= 0; - for (Table_value **tbl_dep=te->table_deps; - tbl_dep < te->table_deps + MAX_TABLES; + for (Table_value **tbl_dep=fda->table_deps; + tbl_dep < fda->table_deps + MAX_TABLES; tbl_dep++) { if (*tbl_dep) @@ -828,39 +832,39 @@ field_dep= field_dep->next_table_field) { field_dep->bitmap_offset= offset; - offset += te->n_equality_deps; + offset += fda->n_equality_mods; } } } void *buf; if (!(buf= current_thd->alloc(bitmap_buffer_size(offset))) || - bitmap_init(&te->expr_deps, (my_bitmap_map*)buf, offset, FALSE)) + bitmap_init(&fda->expr_deps, (my_bitmap_map*)buf, offset, FALSE)) { DBUG_RETURN(TRUE); } - bitmap_clear_all(&te->expr_deps); + bitmap_clear_all(&fda->expr_deps); /* - Analyze all "field=expr" dependencies, and have te->expr_deps encode + Analyze all "field=expr" dependencies, and have fda->expr_deps encode dependencies of expressions from fields. Also collect a linked list of equalities that are bound. */ Module_dep *bound_dep= NULL; - 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++) + Field_dependency_recorder deps_recorder(fda); + for (Equality_module *eq_mod= fda->equality_mods; + eq_mod < fda->equality_mods + fda->n_equality_mods; + eq_mod++) { - deps_recorder.expr_offset= eq_dep - te->equality_deps; - eq_dep->unknown_args= 0; - eq_dep->expression->walk(&Item::check_column_usage_processor, FALSE, + deps_recorder.expr_offset= eq_mod - fda->equality_mods; + eq_mod->unknown_args= 0; + eq_mod->expression->walk(&Item::check_column_usage_processor, FALSE, (uchar*)&deps_recorder); - if (!eq_dep->unknown_args) + if (!eq_mod->unknown_args) { - eq_dep->next= bound_dep; - bound_dep= eq_dep; + eq_mod->next= bound_dep; + bound_dep= eq_mod; } } *bound_deps_list= bound_dep; @@ -968,7 +972,7 @@ SYNOPSIS eliminate_tables_for_list() - te Table elimination context + fda 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 @@ -1053,7 +1057,7 @@ SYNOPSIS check_func_dependency() - te Table elimination context + fda Table elimination context tables Set of tables we want to be functionally dependent cond Condition to use @@ -1073,24 +1077,25 @@ TABLE_LIST *oj_tbl, Item* cond) { - uint and_level=0; Module_dep *bound_modules; - //psergey-todo: move allocs to somewhere else. - 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; - if (!(te->equality_deps= new Equality_module[max_elems])) + Func_dep_analyzer fda(join); + + /* Start value */ + fda.n_equality_mods_alloced= + join->thd->lex->current_select->max_equal_elems + + (join->thd->lex->current_select->cond_count+1)*2 + + join->thd->lex->current_select->between_count; + + if (!(fda.equality_mods= new Equality_module[fda.n_equality_mods_alloced])) return FALSE; - Equality_module* eq_dep= te->equality_deps; + Equality_module* last_eq_mod= fda.equality_mods; /* Create Table_value objects for all tables we're trying to eliminate */ if (oj_tbl) { - if (!get_table_value(te, oj_tbl->table)) + if (!get_table_value(&fda, oj_tbl->table)) return FALSE; } else @@ -1100,30 +1105,29 @@ { if (tbl->table && (tbl->table->map & dep_tables)) { - if (!get_table_value(te, tbl->table)) + if (!get_table_value(&fda, tbl->table)) return FALSE; } } } - te->usable_tables= dep_tables; + fda.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) || - eq_dep == te->equality_deps) - return FALSE; - - te->n_equality_deps= eq_dep - te->equality_deps; + uint and_level=0; + build_eq_mods_for_cond(&fda, &last_eq_mod, &and_level, cond); + if (!(fda.n_equality_mods= last_eq_mod - fda.equality_mods)) + return FALSE; /* No useful conditions */ - if (!(te->outer_join_dep= new Outer_join_module(my_count_bits(dep_tables))) || - setup_equality_modules_deps(te, &bound_modules)) + if (!(fda.outer_join_dep= new Outer_join_module(my_count_bits(dep_tables))) || + setup_equality_modules_deps(&fda, &bound_modules)) { return FALSE; /* OOM, default to non-dependent */ } - DBUG_EXECUTE("test", dbug_print_deps(te); ); + DBUG_EXECUTE("test", dbug_print_deps(&fda); ); /* The running wave algorithm itself: */ Value_dep *bound_values= NULL; @@ -1131,11 +1135,11 @@ { for (;bound_modules; bound_modules= bound_modules->next) { - if (bound_modules->now_bound(te, &bound_values)) + if (bound_modules->now_bound(&fda, &bound_values)) return TRUE; /* Dependent! */ } for (;bound_values; bound_values=bound_values->next) - bound_values->now_bound(te, &bound_modules); + bound_values->now_bound(&fda, &bound_modules); } return FALSE; /* Not dependent */ } @@ -1147,7 +1151,7 @@ - all its fields are known */ -void Table_value::now_bound(Func_dep_analyzer *te, +void Table_value::now_bound(Func_dep_analyzer *fda, Module_dep **bound_modules) { DBUG_PRINT("info", ("table %s is now bound", table->alias)); @@ -1159,21 +1163,21 @@ { /* Mark as bound and add to the list */ field_dep->bound= TRUE; - field_dep->signal_from_field_to_exprs(te, bound_modules); + field_dep->signal_from_field_to_exprs(fda, bound_modules); } } - if (te->outer_join_dep->unknown_args && - !--te->outer_join_dep->unknown_args) + if (fda->outer_join_dep->unknown_args && + !--fda->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; + fda->outer_join_dep->next= *bound_modules; + *bound_modules= fda->outer_join_dep; } } -void Field_value::now_bound(Func_dep_analyzer *te, +void Field_value::now_bound(Func_dep_analyzer *fda, Module_dep **bound_modules) { DBUG_PRINT("info", ("field %s.%s is now bound", field->table->alias, @@ -1193,7 +1197,7 @@ *bound_modules= key_dep; } } - signal_from_field_to_exprs(te, bound_modules); + signal_from_field_to_exprs(fda, bound_modules); } @@ -1201,25 +1205,25 @@ 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(Func_dep_analyzer* te, +void Field_value::signal_from_field_to_exprs(Func_dep_analyzer* fda, Module_dep **bound_modules) { - for (uint i=0; i < te->n_equality_deps; i++) + for (uint i=0; i < fda->n_equality_mods; i++) { - if (bitmap_is_set(&te->expr_deps, bitmap_offset + i) && - te->equality_deps[i].unknown_args && - !--te->equality_deps[i].unknown_args) + if (bitmap_is_set(&fda->expr_deps, bitmap_offset + i) && + fda->equality_mods[i].unknown_args && + !--fda->equality_mods[i].unknown_args) { /* Mark as bound and add to the list */ - Equality_module* eq_dep= &te->equality_deps[i]; - eq_dep->next= *bound_modules; - *bound_modules= eq_dep; + Equality_module* eq_mod= &fda->equality_mods[i]; + eq_mod->next= *bound_modules; + *bound_modules= eq_mod; } } } -bool Outer_join_module::now_bound(Func_dep_analyzer *te, +bool Outer_join_module::now_bound(Func_dep_analyzer *fda, Value_dep **bound_values) { DBUG_PRINT("info", ("Outer join eliminated")); @@ -1227,7 +1231,7 @@ } -bool Equality_module::now_bound(Func_dep_analyzer *te, +bool Equality_module::now_bound(Func_dep_analyzer *fda, Value_dep **bound_values) { /* For field=expr and we got to know the expr, so we know the field */ @@ -1242,7 +1246,7 @@ } /* Unique key is known means its table is known */ -bool Key_module::now_bound(Func_dep_analyzer *te, Value_dep **bound_values) +bool Key_module::now_bound(Func_dep_analyzer *fda, Value_dep **bound_values) { if (!table->bound) { @@ -1294,7 +1298,7 @@ #ifndef DBUG_OFF static -void dbug_print_deps(Func_dep_analyzer *te) +void dbug_print_deps(Func_dep_analyzer *fda) { DBUG_ENTER("dbug_print_deps"); DBUG_LOCK_FILE; @@ -1302,18 +1306,18 @@ fprintf(DBUG_FILE,"deps {\n"); /* Start with printing equalities */ - for (Equality_module *eq_dep= te->equality_deps; - eq_dep != te->equality_deps + te->n_equality_deps; eq_dep++) + for (Equality_module *eq_mod= fda->equality_mods; + eq_mod != fda->equality_mods + fda->n_equality_mods; eq_mod++) { char buf[128]; String str(buf, sizeof(buf), &my_charset_bin); str.length(0); - eq_dep->expression->print(&str, QT_ORDINARY); + eq_mod->expression->print(&str, QT_ORDINARY); fprintf(DBUG_FILE, " equality%d: %s -> %s.%s\n", - eq_dep - te->equality_deps, + eq_mod - fda->equality_mods, str.c_ptr(), - eq_dep->field->table->table->alias, - eq_dep->field->field->field_name); + eq_mod->field->table->table->alias, + eq_mod->field->field->field_name); } fprintf(DBUG_FILE,"\n"); @@ -1321,7 +1325,7 @@ for (uint i=0; i < MAX_TABLES; i++) { Table_value *table_dep; - if ((table_dep= te->table_deps[i])) + if ((table_dep= fda->table_deps[i])) { /* Print table */ fprintf(DBUG_FILE, " table %s\n", table_dep->table->alias); @@ -1332,9 +1336,9 @@ fprintf(DBUG_FILE, " field %s.%s ->", table_dep->table->alias, field_dep->field->field_name); uint ofs= field_dep->bitmap_offset; - for (uint bit= ofs; bit < ofs + te->n_equality_deps; bit++) + for (uint bit= ofs; bit < ofs + fda->n_equality_mods; bit++) { - if (bitmap_is_set(&te->expr_deps, bit)) + if (bitmap_is_set(&fda->expr_deps, bit)) fprintf(DBUG_FILE, " equality%d ", bit - ofs); } fprintf(DBUG_FILE, "\n");

1 0

[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