- developers - lists.mariadb.org

[Maria-developers] Rev 2723: Fix trivial typo in file:///home/psergey/dev/maria-5.1-table-elim-r10/
by Sergey Petrunya 15 Aug '09

15 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r10/ ------------------------------------------------------------ revno: 2723 revision-id: psergey(a)askmonty.org-20090815121442-706m9ujn8km4u4y1 parent: psergey(a)askmonty.org-20090815102953-7s0jb470ibwq58qz committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r10 timestamp: Sat 2009-08-15 16:14:42 +0400 message: Fix trivial typo === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-15 10:29:53 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-15 12:14:42 +0000 @@ -841,7 +841,7 @@ *eliminable_tables); } - if (eliminable && get_outer_join_dep(te, tbl, cur_map)) + if (eliminable && !get_outer_join_dep(te, tbl, cur_map)) return TRUE; tables_used_on_left |= tbl->on_expr->used_tables();

1 0

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

15 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r10/ ------------------------------------------------------------ revno: 2722 revision-id: psergey(a)askmonty.org-20090815102953-7s0jb470ibwq58qz parent: psergey(a)askmonty.org-20090815060803-0yvp5mmgo87emykp committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r10 timestamp: Sat 2009-08-15 14:29:53 +0400 message: MWL#17: Table elimination Continue with addressing review feedback part two: - rename enum members - add checking for out of memory errors on allocation === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-15 06:08:03 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-15 10:29:53 +0000 @@ -111,11 +111,11 @@ { public: enum { - FD_EXPRESSION, - FD_MULTI_EQUALITY, - FD_UNIQUE_KEY, - FD_TABLE, - FD_OUTER_JOIN + MODULE_EXPRESSION, + MODULE_MULTI_EQUALITY, + MODULE_UNIQUE_KEY, + MODULE_TABLE, + MODULE_OUTER_JOIN } type; /* Type of the object */ /* @@ -156,7 +156,7 @@ 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::FD_UNIQUE_KEY; + type= Module_dep::MODULE_UNIQUE_KEY; unknown_args= n_parts_arg; } Table_value *table; /* Table this key is from */ @@ -178,7 +178,7 @@ Outer_join_module(TABLE_LIST *table_list_arg, uint n_children) : table_list(table_list_arg), parent(NULL) { - type= Module_dep::FD_OUTER_JOIN; + type= Module_dep::MODULE_OUTER_JOIN; unknown_args= n_children; } /* @@ -205,7 +205,7 @@ class Table_elimination { public: - Table_elimination(JOIN *join_arg) : join(join_arg) + Table_elimination(JOIN *join_arg) : join(join_arg), n_outer_joins(0) { bzero(table_deps, sizeof(table_deps)); } @@ -220,6 +220,7 @@ /* 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; @@ -630,22 +631,25 @@ DBUG_ASSERT(eq_func); /* Store possible eq field */ - (*eq_dep)->type= Module_dep::FD_EXPRESSION; //psergey-todo; + (*eq_dep)->type= Module_dep::MODULE_EXPRESSION; //psergey-todo; (*eq_dep)->field= get_field_value(te, field); (*eq_dep)->val= *value; (*eq_dep)->level= and_level; (*eq_dep)++; } + /* Get a Table_value object for the given table, creating it if necessary. */ static Table_value *get_table_value(Table_elimination *te, TABLE *table) { - Table_value *tbl_dep= new Table_value(table); + Table_value *tbl_dep; + if (!(tbl_dep= new Table_value(table))) + return NULL; + Key_module **key_list= &(tbl_dep->keys); - /* Add dependencies for unique keys */ for (uint i=0; i < table->s->keys; i++) { @@ -657,7 +661,7 @@ key_list= &(key_dep->next_table_key); } } - return te->table_deps[table->tablenr] = tbl_dep; + return te->table_deps[table->tablenr]= tbl_dep; } @@ -672,7 +676,10 @@ /* First, get the table*/ if (!(tbl_dep= te->table_deps[table->tablenr])) - tbl_dep= get_table_value(te, table); + { + if (!(tbl_dep= get_table_value(te, table))) + return NULL; + } /* Try finding the field in field list */ Field_value **pfield= &(tbl_dep->fields); @@ -702,10 +709,12 @@ static Outer_join_module *get_outer_join_dep(Table_elimination *te, - TABLE_LIST *outer_join, table_map deps_map) + TABLE_LIST *outer_join, + table_map deps_map) { Outer_join_module *oj_dep; oj_dep= new Outer_join_module(outer_join, my_count_bits(deps_map)); + te->n_outer_joins++; /* Collect a bitmap fo tables that we depend on, and also set parent pointer @@ -734,7 +743,8 @@ } } DBUG_ASSERT(table); - table_dep= get_table_value(te, table); + if (!(table_dep= get_table_value(te, table))) + return NULL; } /* @@ -781,7 +791,7 @@ . */ -static void +static bool collect_funcdeps_for_join_list(Table_elimination *te, List<TABLE_LIST> *join_list, bool build_eq_deps, @@ -808,11 +818,12 @@ eliminable= !(cur_map & outside_used_tables); if (eliminable) *eliminable_tables |= cur_map; - collect_funcdeps_for_join_list(te, &tbl->nested_join->join_list, - eliminable || build_eq_deps, - outside_used_tables, - eliminable_tables, - eq_dep); + 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 { @@ -830,13 +841,13 @@ *eliminable_tables); } - if (eliminable) - te->oj_deps.push_back(get_outer_join_dep(te, tbl, cur_map)); + if (eliminable && get_outer_join_dep(te, tbl, cur_map)) + return TRUE; tables_used_on_left |= tbl->on_expr->used_tables(); } } - return; + return FALSE; } @@ -1053,16 +1064,18 @@ DBUG_VOID_RETURN; Equality_module *eq_deps_end= te.equality_deps; table_map eliminable_tables= 0; - collect_funcdeps_for_join_list(&te, join->join_list, - FALSE, - used_tables, - &eliminable_tables, - &eq_deps_end); + if (collect_funcdeps_for_join_list(&te, join->join_list, + FALSE, + used_tables, + &eliminable_tables, + &eq_deps_end)) + DBUG_VOID_RETURN; te.n_equality_deps= eq_deps_end - te.equality_deps; Module_dep *bound_modules; //Value_dep *bound_values; - setup_equality_deps(&te, &bound_modules); + if (setup_equality_deps(&te, &bound_modules)) + DBUG_VOID_RETURN; run_elimination_wave(&te, bound_modules); } @@ -1108,7 +1121,7 @@ { switch (bound_modules->type) { - case Module_dep::FD_EXPRESSION: + 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; @@ -1121,7 +1134,7 @@ } break; } - case Module_dep::FD_UNIQUE_KEY: + case Module_dep::MODULE_UNIQUE_KEY: { /* Unique key is known means the table is known */ Table_value *table_dep=((Key_module*)bound_modules)->table; @@ -1134,13 +1147,13 @@ } break; } - case Module_dep::FD_OUTER_JOIN: + 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); break; } - case Module_dep::FD_MULTI_EQUALITY: + case Module_dep::MODULE_MULTI_EQUALITY: default: DBUG_ASSERT(0); }

1 0

[Maria-developers] Rev 2721: MWL#17: Address 2nd post-review feedback in file:///home/psergey/dev/maria-5.1-table-elim-r10/
by Sergey Petrunya 15 Aug '09

15 Aug '09

At file:///home/psergey/dev/maria-5.1-table-elim-r10/ ------------------------------------------------------------ revno: 2721 revision-id: psergey(a)askmonty.org-20090815060803-0yvp5mmgo87emykp parent: psergey(a)askmonty.org-20090813211212-jghejwxsl6adtopl committer: Sergey Petrunya <psergey(a)askmonty.org> branch nick: maria-5.1-table-elim-r10 timestamp: Sat 2009-08-15 10:08:03 +0400 message: MWL#17: Address 2nd post-review feedback - Switch from uniform graph to bipartite graph with two kinds of nodes: "values" (tables and fields) and "modules" (t.col=func(...) equalities, multi-equalities, unique keys, inner sides of outer joins). - Rename functions, classes, etc. === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-13 20:44:52 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-15 06:08:03 +0000 @@ -40,19 +40,78 @@ Table elimination is redone on every PS re-execution. */ - -/* - An abstract structure that represents some entity that's being dependent on - some other entity. -*/ - -class Func_dep : public Sql_alloc -{ -public: - enum { - FD_INVALID, +class Value_dep +{ +public: + enum { + VALUE_FIELD, + VALUE_TABLE, + } type; /* Type of the object */ + + bool bound; + Value_dep *next; +}; + +class Field_value; +class Table_value; +class Outer_join_module; +class Key_module; + +/* + A table field. There is only one such object for any tblX.fieldY + - the field epends on its table and equalities + - expressions that use the field are its dependencies +*/ +class Field_value : public Value_dep +{ +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_value *next_table_field; + uint bitmap_offset; /* Offset of our part of the bitmap */ +}; + + +/* + A table. + - table depends on any of its unique keys + - has its fields and embedding outer join as dependency. +*/ +class Table_value : public Value_dep +{ +public: + Table_value(TABLE *table_arg) : + table(table_arg), fields(NULL), keys(NULL), outer_join_dep(NULL) + { + type= Value_dep::VALUE_TABLE; + } + 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 */ +}; + + +/* + A 'module' +*/ + +class Module_dep : public Sql_alloc +{ +public: + enum { FD_EXPRESSION, - FD_FIELD, FD_MULTI_EQUALITY, FD_UNIQUE_KEY, FD_TABLE, @@ -63,58 +122,26 @@ Used to make a linked list of elements that became bound and thus can make elements that depend on them bound, too. */ - Func_dep *next; - bool bound; /* TRUE<=> The entity is considered bound */ - Func_dep() : next(NULL), bound(FALSE) {} + Module_dep *next; + uint unknown_args; /* TRUE<=> The entity is considered bound */ + + Module_dep() : next(NULL), unknown_args(0) {} }; -class Field_dep; -class Table_dep; -class Outer_join_dep; - /* A "tbl.column= expr" equality dependency. tbl.column depends on fields used in expr. */ -class Equality_dep : public Func_dep +class Equality_module : public Module_dep { public: - Field_dep *field; + Field_value *field; Item *val; /* Used during condition analysis only, similar to KEYUSE::level */ uint level; - - /* Number of fields referenced from *val that are not yet 'bound' */ - uint unknown_args; -}; - - -/* - A table field. There is only one such object for any tblX.fieldY - - the field epends on its table and equalities - - expressions that use the field are its dependencies -*/ -class Field_dep : public Func_dep -{ -public: - Field_dep(Table_dep *table_arg, Field *field_arg) : - table(table_arg), field(field_arg) - { - type= Func_dep::FD_FIELD; - } - - Table_dep *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_dep *next_table_field; - uint bitmap_offset; /* Offset of our part of the bitmap */ }; @@ -123,41 +150,21 @@ - Unique key depends on all of its components - Key's table is its dependency */ -class Key_dep: public Func_dep +class Key_module: public Module_dep { public: - Key_dep(Table_dep *table_arg, uint keyno_arg, uint n_parts_arg) : - table(table_arg), keyno(keyno_arg), n_missing_keyparts(n_parts_arg), - next_table_key(NULL) + Key_module(Table_value *table_arg, uint keyno_arg, uint n_parts_arg) : + table(table_arg), keyno(keyno_arg), next_table_key(NULL) { - type= Func_dep::FD_UNIQUE_KEY; + type= Module_dep::FD_UNIQUE_KEY; + unknown_args= n_parts_arg; } - Table_dep *table; /* Table this key is from */ + Table_value *table; /* Table this key is from */ uint keyno; - uint n_missing_keyparts; /* Unique keys form a linked list, ordered by keyno */ - Key_dep *next_table_key; -}; - - -/* - A table. - - table depends on any of its unique keys - - has its fields and embedding outer join as dependency. -*/ -class Table_dep : public Func_dep -{ -public: - Table_dep(TABLE *table_arg) : - table(table_arg), fields(NULL), keys(NULL), outer_join_dep(NULL) - { - type= Func_dep::FD_TABLE; - } - TABLE *table; - Field_dep *fields; /* Ordered list of fields that belong to this table */ - Key_dep *keys; /* Ordered list of Unique keys in this table */ - Outer_join_dep *outer_join_dep; /* Innermost eliminable outer join we're in */ -}; + Key_module *next_table_key; +}; + /* @@ -165,14 +172,14 @@ - it depends on all tables inside it - has its parent outer join as dependency */ -class Outer_join_dep: public Func_dep +class Outer_join_module: public Module_dep { public: - Outer_join_dep(TABLE_LIST *table_list_arg, table_map missing_tables_arg) : - table_list(table_list_arg), missing_tables(missing_tables_arg), - all_tables(missing_tables_arg), parent(NULL) + Outer_join_module(TABLE_LIST *table_list_arg, uint n_children) : + table_list(table_list_arg), parent(NULL) { - type= Func_dep::FD_OUTER_JOIN; + type= Module_dep::FD_OUTER_JOIN; + unknown_args= n_children; } /* Outer join we're representing. This can be a join nest or a one table that @@ -184,11 +191,11 @@ Tables within this outer join (and its descendants) that are not yet known to be functionally dependent. */ - table_map missing_tables; + table_map missing_tables; //psergey-todo: remove /* All tables within this outer join and its descendants */ - table_map all_tables; + table_map all_tables; //psergey-todo: remove /* Parent eliminable outer join, if any */ - Outer_join_dep *parent; + Outer_join_module *parent; }; @@ -205,44 +212,45 @@ JOIN *join; /* Array of equality dependencies */ - Equality_dep *equality_deps; + Equality_module *equality_deps; uint n_equality_deps; /* Number of elements in the array */ - /* tablenr -> Table_dep* mapping. */ - Table_dep *table_deps[MAX_KEY]; + /* tablenr -> Table_value* mapping. */ + Table_value *table_deps[MAX_KEY]; /* Outer joins that are candidates for elimination */ - List<Outer_join_dep> oj_deps; + List<Outer_join_module> oj_deps; /* Bitmap of how expressions depend on bits */ MY_BITMAP expr_deps; }; - static -void build_eq_deps_for_cond(Table_elimination *te, Equality_dep **fdeps, +void build_eq_deps_for_cond(Table_elimination *te, Equality_module **fdeps, uint *and_level, Item *cond, table_map usable_tables); static void add_eq_dep(Table_elimination *te, - Equality_dep **eq_dep, uint and_level, + Equality_module **eq_dep, uint and_level, Item_func *cond, Field *field, bool eq_func, Item **value, uint num_values, table_map usable_tables); static -Equality_dep *merge_func_deps(Equality_dep *start, Equality_dep *new_fields, - Equality_dep *end, uint and_level); - -static Table_dep *get_table_dep(Table_elimination *te, TABLE *table); -static Field_dep *get_field_dep(Table_elimination *te, Field *field); - +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 +void 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); +#if 0 #ifndef DBUG_OFF static void dbug_print_deps(Table_elimination *te); #endif - +#endif /*******************************************************************************************/ /* @@ -262,14 +270,14 @@ */ static -void build_eq_deps_for_cond(Table_elimination *te, Equality_dep **fdeps, +void build_eq_deps_for_cond(Table_elimination *te, Equality_module **fdeps, uint *and_level, Item *cond, table_map usable_tables) { if (cond->type() == Item_func::COND_ITEM) { List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list()); - Equality_dep *org_key_fields= *fdeps; + Equality_module *org_key_fields= *fdeps; /* AND/OR */ if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC) @@ -293,7 +301,7 @@ Item *item; while ((item=li++)) { - Equality_dep *start_key_fields= *fdeps; + Equality_module *start_key_fields= *fdeps; (*and_level)++; build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables); *fdeps= merge_func_deps(org_key_fields, start_key_fields, *fdeps, @@ -432,7 +440,7 @@ /* - Perform an OR operation on two (adjacent) Equality_dep arrays. + Perform an OR operation on two (adjacent) Equality_module arrays. SYNOPSIS merge_func_deps() @@ -442,7 +450,7 @@ and_level AND-level. DESCRIPTION - This function is invoked for two adjacent arrays of Equality_dep elements: + This function is invoked for two adjacent arrays of Equality_module elements: $LEFT_PART $RIGHT_PART +-----------------------+-----------------------+ @@ -477,19 +485,19 @@ */ static -Equality_dep *merge_func_deps(Equality_dep *start, Equality_dep *new_fields, - Equality_dep *end, uint and_level) +Equality_module *merge_func_deps(Equality_module *start, Equality_module *new_fields, + Equality_module *end, uint and_level) { if (start == new_fields) return start; // Impossible or if (new_fields == end) return start; // No new fields, skip all - Equality_dep *first_free=new_fields; + Equality_module *first_free=new_fields; for (; new_fields != end ; new_fields++) { - for (Equality_dep *old=start ; old != first_free ; old++) + for (Equality_module *old=start ; old != first_free ; old++) { /* TODO: does it make sense to attempt to merging multiple-equalities? @@ -534,7 +542,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: */ - for (Equality_dep *old=start ; old != first_free ;) + for (Equality_module *old=start ; old != first_free ;) { if (old->level != and_level) { // Not used in all levels @@ -550,14 +558,14 @@ /* - Add an Equality_dep element for a given predicate, if applicable + Add an Equality_module element for a given predicate, if applicable DESCRIPTION This function is modeled after add_key_field(). */ static -void add_eq_dep(Table_elimination *te, Equality_dep **eq_dep, +void add_eq_dep(Table_elimination *te, Equality_module **eq_dep, uint and_level, Item_func *cond, Field *field, bool eq_func, Item **value, uint num_values, table_map usable_tables) @@ -622,22 +630,21 @@ DBUG_ASSERT(eq_func); /* Store possible eq field */ - (*eq_dep)->type= Func_dep::FD_EXPRESSION; //psergey-todo; - (*eq_dep)->field= get_field_dep(te, field); + (*eq_dep)->type= Module_dep::FD_EXPRESSION; //psergey-todo; + (*eq_dep)->field= get_field_value(te, field); (*eq_dep)->val= *value; (*eq_dep)->level= and_level; (*eq_dep)++; } - /* - Get a Table_dep object for the given table, creating it if necessary. + Get a Table_value object for the given table, creating it if necessary. */ -static Table_dep *get_table_dep(Table_elimination *te, TABLE *table) +static Table_value *get_table_value(Table_elimination *te, TABLE *table) { - Table_dep *tbl_dep= new Table_dep(table); - Key_dep **key_list= &(tbl_dep->keys); + Table_value *tbl_dep= new Table_value(table); + Key_module **key_list= &(tbl_dep->keys); /* Add dependencies for unique keys */ for (uint i=0; i < table->s->keys; i++) @@ -645,7 +652,7 @@ KEY *key= table->key_info + i; if ((key->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == HA_NOSAME) { - Key_dep *key_dep= new Key_dep(tbl_dep, i, key->key_parts); + Key_module *key_dep= new Key_module(tbl_dep, i, key->key_parts); *key_list= key_dep; key_list= &(key_dep->next_table_key); } @@ -655,20 +662,20 @@ /* - Get a Field_dep object for the given field, creating it if necessary + Get a Field_value object for the given field, creating it if necessary */ -static Field_dep *get_field_dep(Table_elimination *te, Field *field) +static Field_value *get_field_value(Table_elimination *te, Field *field) { TABLE *table= field->table; - Table_dep *tbl_dep; + Table_value *tbl_dep; /* First, get the table*/ if (!(tbl_dep= te->table_deps[table->tablenr])) - tbl_dep= get_table_dep(te, table); + tbl_dep= get_table_value(te, table); /* Try finding the field in field list */ - Field_dep **pfield= &(tbl_dep->fields); + Field_value **pfield= &(tbl_dep->fields); while (*pfield && (*pfield)->field->field_index < field->field_index) { pfield= &((*pfield)->next_table_field); @@ -677,7 +684,7 @@ return *pfield; /* Create the field and insert it in the list */ - Field_dep *new_field= new Field_dep(tbl_dep, field); + Field_value *new_field= new Field_value(tbl_dep, field); new_field->next_table_field= *pfield; *pfield= new_field; @@ -686,19 +693,19 @@ /* - Create an Outer_join_dep object for the given outer join + Create an Outer_join_module object for the given outer join DESCRIPTION - Outer_join_dep objects for children (or further descendants) are always + Outer_join_module objects for children (or further descendants) are always created before the parents. */ static -Outer_join_dep *get_outer_join_dep(Table_elimination *te, +Outer_join_module *get_outer_join_dep(Table_elimination *te, TABLE_LIST *outer_join, table_map deps_map) { - Outer_join_dep *oj_dep; - oj_dep= new Outer_join_dep(outer_join, deps_map); + Outer_join_module *oj_dep; + oj_dep= new Outer_join_module(outer_join, my_count_bits(deps_map)); /* Collect a bitmap fo tables that we depend on, and also set parent pointer @@ -708,7 +715,7 @@ int idx; while ((idx= it.next_bit()) != Table_map_iterator::BITMAP_END) { - Table_dep *table_dep; + Table_value *table_dep; if (!(table_dep= te->table_deps[idx])) { /* @@ -727,23 +734,24 @@ } } DBUG_ASSERT(table); - table_dep= get_table_dep(te, table); + table_dep= get_table_value(te, table); } /* 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_dep. + 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_dep *oj= table_dep->outer_join_dep; + Outer_join_module *oj= table_dep->outer_join_dep; while (oj->parent) oj= oj->parent; - oj->parent=oj_dep; + if (oj != oj_dep) + oj->parent=oj_dep; } } return oj_dep; @@ -757,7 +765,7 @@ collect_funcdeps_for_join_list() te Table elimination context. join_list Join list to work on - build_eq_deps TRUE <=> build Equality_dep elements for all + 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 @@ -779,7 +787,7 @@ bool build_eq_deps, table_map tables_used_elsewhere, table_map *eliminable_tables, - Equality_dep **eq_dep) + Equality_module **eq_dep) { TABLE_LIST *tbl; List_iterator<TABLE_LIST> it(*join_list); @@ -845,10 +853,10 @@ void see_field(Field *field) { - Table_dep *tbl_dep; + Table_value *tbl_dep; if ((tbl_dep= te->table_deps[field->table->tablenr])) { - for (Field_dep *field_dep= tbl_dep->fields; field_dep; + for (Field_value *field_dep= tbl_dep->fields; field_dep; field_dep= field_dep->next_table_field) { if (field->field_index == field_dep->field->field_index) @@ -888,21 +896,21 @@ */ static -bool setup_equality_deps(Table_elimination *te, Func_dep **bound_deps_list) +bool setup_equality_deps(Table_elimination *te, Module_dep **bound_deps_list) { DBUG_ENTER("setup_equality_deps"); /* - Count Field_dep objects and assign each of them a unique bitmap_offset. + Count Field_value objects and assign each of them a unique bitmap_offset. */ uint offset= 0; - for (Table_dep **tbl_dep=te->table_deps; + for (Table_value **tbl_dep=te->table_deps; tbl_dep < te->table_deps + MAX_TABLES; tbl_dep++) { if (*tbl_dep) { - for (Field_dep *field_dep= (*tbl_dep)->fields; + for (Field_value *field_dep= (*tbl_dep)->fields; field_dep; field_dep= field_dep->next_table_field) { @@ -926,9 +934,9 @@ Also collect a linked list of equalities that are bound. */ - Func_dep *bound_dep= NULL; + Module_dep *bound_dep= NULL; Field_dependency_setter deps_setter(te); - for (Equality_dep *eq_dep= te->equality_deps; + for (Equality_module *eq_dep= te->equality_deps; eq_dep < te->equality_deps + te->n_equality_deps; eq_dep++) { @@ -940,12 +948,11 @@ { eq_dep->next= bound_dep; bound_dep= eq_dep; - eq_dep->bound= TRUE; } } *bound_deps_list= bound_dep; - DBUG_EXECUTE("test", dbug_print_deps(te); ); + //DBUG_EXECUTE("test", dbug_print_deps(te); ); DBUG_RETURN(FALSE); } @@ -1042,9 +1049,9 @@ 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_dep[max_elems])) + if (!(te.equality_deps= new Equality_module[max_elems])) DBUG_VOID_RETURN; - Equality_dep *eq_deps_end= te.equality_deps; + Equality_module *eq_deps_end= te.equality_deps; table_map eliminable_tables= 0; collect_funcdeps_for_join_list(&te, join->join_list, FALSE, @@ -1052,96 +1059,125 @@ &eliminable_tables, &eq_deps_end); te.n_equality_deps= eq_deps_end - te.equality_deps; - Func_dep *bound_dep; - setup_equality_deps(&te, &bound_dep); - - /* - 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_dep) - { - Func_dep *next= bound_dep->next; - //e= list.remove_first(); - switch (bound_dep->type) + + Module_dep *bound_modules; + //Value_dep *bound_values; + setup_equality_deps(&te, &bound_modules); + + run_elimination_wave(&te, bound_modules); + } + DBUG_VOID_RETURN; +} + + +static +void signal_from_field_to_exprs(Table_elimination* te, Field_value *field_dep, + Module_dep **bound_modules) +{ + /* Now, expressions */ + for (uint i=0; i < te->n_equality_deps; i++) + { + if (bitmap_is_set(&te->expr_deps, field_dep->bitmap_offset + i) && + te->equality_deps[i].unknown_args && + !--te->equality_deps[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; + } + } +} + + +static +void 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) + { + switch (bound_modules->type) { - case Func_dep::FD_EXPRESSION: + case Module_dep::FD_EXPRESSION: { /* It's a field=expr and we got to know the expr, so we know the field */ - Equality_dep *eq_dep= (Equality_dep*)bound_dep; + 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= next; - next= eq_dep->field; - } - break; - } - case Func_dep::FD_FIELD: + eq_dep->field->next= bound_values; + bound_values= eq_dep->field; + } + break; + } + case Module_dep::FD_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::FD_OUTER_JOIN: + { + Outer_join_module *outer_join_dep= (Outer_join_module*)bound_modules; + mark_as_eliminated(te->join, outer_join_dep->table_list); + break; + } + case Module_dep::FD_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_dep *field_dep= (Field_dep*)bound_dep; - for (Key_dep *key_dep= field_dep->table->keys; key_dep; + Field_value *field_dep= (Field_value*)bound_values; + for (Key_module *key_dep= field_dep->table->keys; key_dep; key_dep= key_dep->next_table_key) { DBUG_PRINT("info", ("key %s.%s is now bound", key_dep->table->table->alias, key_dep->table->table->key_info[key_dep->keyno].name)); if (field_dep->field->part_of_key.is_set(key_dep->keyno) && - !key_dep->bound) - { - if (!--key_dep->n_missing_keyparts) - { - /* Mark as bound and add to the list */ - key_dep->bound= TRUE; - key_dep->next= next; - next= key_dep; - } - } - } - - /* Now, expressions */ - for (uint i=0; i < te.n_equality_deps; i++) - { - if (bitmap_is_set(&te.expr_deps, field_dep->bitmap_offset + i)) - { - Equality_dep* eq_dep= &te.equality_deps[i]; - if (!--eq_dep->unknown_args) - { - /* Mark as bound and add to the list */ - eq_dep->bound= TRUE; - eq_dep->next= next; - next= eq_dep; - } - } - } - break; - } - case Func_dep::FD_UNIQUE_KEY: - { - /* Unique key is known means the table is known */ - Table_dep *table_dep=((Key_dep*)bound_dep)->table; - if (!table_dep->bound) - { - /* Mark as bound and add to the list */ - table_dep->bound= TRUE; - table_dep->next= next; - next= table_dep; - } - break; - } - case Func_dep::FD_TABLE: - { - Table_dep *table_dep=(Table_dep*)bound_dep; + key_dep->unknown_args && !--key_dep->unknown_args) + { + /* 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)); /* @@ -1149,50 +1185,35 @@ - all its fields are known - one more element in outer join nest is known */ - for (Field_dep *field_dep= table_dep->fields; field_dep; + 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; - field_dep->next= next; - next= field_dep; - } - } - Outer_join_dep *outer_join_dep= table_dep->outer_join_dep; - if (!(outer_join_dep->missing_tables &= ~table_dep->table->map)) - { - /* Mark as bound and add to the list */ - outer_join_dep->bound= TRUE; - outer_join_dep->next= next; - next= outer_join_dep; - } - break; - } - case Func_dep::FD_OUTER_JOIN: - { - Outer_join_dep *outer_join_dep= (Outer_join_dep*)bound_dep; - mark_as_eliminated(te.join, outer_join_dep->table_list); - Outer_join_dep *parent= outer_join_dep->parent; - if (parent && - !(parent->missing_tables &= ~outer_join_dep->all_tables)) - { - /* Mark as bound and add to the list */ - parent->bound= TRUE; - parent->next= next; - next= parent; - } - break; - } - case Func_dep::FD_MULTI_EQUALITY: - default: + 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->missing_tables &= ~table_dep->table->map)) + 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: DBUG_ASSERT(0); } - bound_dep= next; } } - DBUG_VOID_RETURN; } @@ -1232,7 +1253,7 @@ } - +#if 0 #ifndef DBUG_OFF static void dbug_print_deps(Table_elimination *te) @@ -1243,7 +1264,7 @@ fprintf(DBUG_FILE,"deps {\n"); /* Start with printing equalities */ - for (Equality_dep *eq_dep= te->equality_deps; + for (Equality_module *eq_dep= te->equality_deps; eq_dep != te->equality_deps + te->n_equality_deps; eq_dep++) { char buf[128]; @@ -1261,13 +1282,13 @@ /* Then tables and their fields */ for (uint i=0; i < MAX_TABLES; i++) { - Table_dep *table_dep; + Table_value *table_dep; if ((table_dep= te->table_deps[i])) { /* Print table */ fprintf(DBUG_FILE, " table %s\n", table_dep->table->alias); /* Print fields */ - for (Field_dep *field_dep= table_dep->fields; field_dep; + for (Field_value *field_dep= table_dep->fields; field_dep; field_dep= field_dep->next_table_field) { fprintf(DBUG_FILE, " field %s.%s ->", table_dep->table->alias, @@ -1288,7 +1309,7 @@ } #endif - +#endif /** @} (end of group Table_Elimination) */

1 0

[Maria-developers] Updated (by Guest): improving mysqlbinlog output and doing rename (39)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: improving mysqlbinlog output and doing rename CREATION DATE..: Sun, 09 Aug 2009, 12:24 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Client-RawIdeaBin TASK ID........: 39 (http://askmonty.org/worklog/?tid=39) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 17 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Fri, 14 Aug 2009, 15:52)=-=- Title modified. --- /tmp/wklog.39.old.11123 2009-08-14 15:52:29.000000000 +0300 +++ /tmp/wklog.39.new.11123 2009-08-14 15:52:29.000000000 +0300 @@ -1 +1 @@ -Replication tasks +improving mysqlbinlog output and doing rename -=-=(Guest - Mon, 10 Aug 2009, 16:32)=-=- Adding 1 hour for Monty's initial work on starting the architecture review. Worked 1 hour and estimate 0 hours remain (original estimate increased by 1 hour). -=-=(Psergey - Mon, 10 Aug 2009, 15:59)=-=- Re-searched and added subtasks. Worked 16 hours and estimate 0 hours remain (original estimate increased by 16 hours). -=-=(Psergey - Mon, 10 Aug 2009, 15:31)=-=- Dependency created: 39 now depends on 41 -=-=(Guest - Mon, 10 Aug 2009, 14:52)=-=- Dependency created: 39 now depends on 40 -=-=(Psergey - Sun, 09 Aug 2009, 12:27)=-=- Dependency created: 39 now depends on 36 -=-=(Psergey - Sun, 09 Aug 2009, 12:24)=-=- Dependency created: 39 now depends on 38 -=-=(Psergey - Sun, 09 Aug 2009, 12:24)=-=- Dependency created: 39 now depends on 37 DESCRIPTION: A combine task for all replication tasks. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): improving mysqlbinlog output and doing rename (39)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: improving mysqlbinlog output and doing rename CREATION DATE..: Sun, 09 Aug 2009, 12:24 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Client-RawIdeaBin TASK ID........: 39 (http://askmonty.org/worklog/?tid=39) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 17 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Fri, 14 Aug 2009, 15:52)=-=- Title modified. --- /tmp/wklog.39.old.11123 2009-08-14 15:52:29.000000000 +0300 +++ /tmp/wklog.39.new.11123 2009-08-14 15:52:29.000000000 +0300 @@ -1 +1 @@ -Replication tasks +improving mysqlbinlog output and doing rename -=-=(Guest - Mon, 10 Aug 2009, 16:32)=-=- Adding 1 hour for Monty's initial work on starting the architecture review. Worked 1 hour and estimate 0 hours remain (original estimate increased by 1 hour). -=-=(Psergey - Mon, 10 Aug 2009, 15:59)=-=- Re-searched and added subtasks. Worked 16 hours and estimate 0 hours remain (original estimate increased by 16 hours). -=-=(Psergey - Mon, 10 Aug 2009, 15:31)=-=- Dependency created: 39 now depends on 41 -=-=(Guest - Mon, 10 Aug 2009, 14:52)=-=- Dependency created: 39 now depends on 40 -=-=(Psergey - Sun, 09 Aug 2009, 12:27)=-=- Dependency created: 39 now depends on 36 -=-=(Psergey - Sun, 09 Aug 2009, 12:24)=-=- Dependency created: 39 now depends on 38 -=-=(Psergey - Sun, 09 Aug 2009, 12:24)=-=- Dependency created: 39 now depends on 37 DESCRIPTION: A combine task for all replication tasks. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Knielsen): Add a mysqlbinlog option to filter updates to certain tables (40)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add a mysqlbinlog option to filter updates to certain tables CREATION DATE..: Mon, 10 Aug 2009, 13:25 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Psergey CATEGORY.......: Server-RawIdeaBin TASK ID........: 40 (http://askmonty.org/worklog/?tid=40) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Knielsen - Fri, 14 Aug 2009, 15:47)=-=- High-Level Specification modified. --- /tmp/wklog.40.old.10896 2009-08-14 15:47:39.000000000 +0300 +++ /tmp/wklog.40.new.10896 2009-08-14 15:47:39.000000000 +0300 @@ -72,3 +72,21 @@ /* !mysqlbinlog: updates t1,db3.t2 */ UPDATE t1 LEFT JOIN ... and further processing in mysqlbinlog will be trivial. + +2.4 Implement server functionality to ignore certain tables +----------------------------------------------------------- + +We could add a general facility in the server to ignore certain tables: + + SET SESSION ignored_tables = "db1.t1,db2.t2"; + +This would work similar to --replicate-ignore-table, but in a general way not +restricted to the slave SQL thread. + +It would then be trivial for mysqlbinlog to add such statements at the start +of the output, or probably the user could just do it manually with no need for +additional options for mysqlbinlog. + +It might be useful to integrate this with the code that already handles +--replicate-ignore-db and similar slave options. + -=-=(Psergey - Mon, 10 Aug 2009, 15:41)=-=- High-Level Specification modified. --- /tmp/wklog.40.old.12989 2009-08-10 15:41:23.000000000 +0300 +++ /tmp/wklog.40.new.12989 2009-08-10 15:41:23.000000000 +0300 @@ -1,6 +1,7 @@ - 1. Context ---------- +(See http://askmonty.org/wiki/index.php/Scratch/ReplicationOptions for global +overview) At the moment, the server has these replication slave options: --replicate-do-table=db.tbl -=-=(Guest - Mon, 10 Aug 2009, 14:52)=-=- Dependency created: 39 now depends on 40 -=-=(Guest - Mon, 10 Aug 2009, 14:51)=-=- High Level Description modified. --- /tmp/wklog.40.old.16985 2009-08-10 14:51:59.000000000 +0300 +++ /tmp/wklog.40.new.16985 2009-08-10 14:51:59.000000000 +0300 @@ -1,3 +1,4 @@ Replication slave can be set to filter updates to certain tables with ---replicate-[wild-]{do,ignore}-table options. This task is about adding similar -functionality to mysqlbinlog. +--replicate-[wild-]{do,ignore}-table options. + +This task is about adding similar functionality to mysqlbinlog. -=-=(Guest - Mon, 10 Aug 2009, 14:51)=-=- High-Level Specification modified. --- /tmp/wklog.40.old.16949 2009-08-10 14:51:33.000000000 +0300 +++ /tmp/wklog.40.new.16949 2009-08-10 14:51:33.000000000 +0300 @@ -1 +1,73 @@ +1. Context +---------- +At the moment, the server has these replication slave options: + + --replicate-do-table=db.tbl + --replicate-ignore-table=db.tbl + --replicate-wild-do-table=pattern.pattern + --replicate-wild-ignore-table=pattern.pattern + +They affect both RBR and SBR events. SBR events are checked after the +statement has been parsed, the server iterates over list of used tables and +checks them againist --replicate instructions. + +What is interesting is that this scheme still allows to update the ignored +table through a VIEW. + +2. Table filtering in mysqlbinlog +--------------------------------- + +Per-table filtering of RBR events is easy (as it is relatively easy to extract +the name of the table that the event applies to). + +Per-table filtering of SBR events is hard, as generally it is not apparent +which tables the statement refers to. + +This opens possible options: + +2.1 Put the parser into mysqlbinlog +----------------------------------- +Once we have a full parser in mysqlbinlog, we'll be able to check which tables +are used by a statement, and will allow to show behaviour identical to those +that one obtains when using --replicate-* slave options. + +(It is not clear how much effort is needed to put the parser into mysqlbinlog. +Any guesses?) + + +2.2 Use dumb regexp match +------------------------- +Use a really dumb approach. A query is considered to be modifying table X if +it matches an expression + +CREATE TABLE $tablename +DROP $tablename +UPDATE ...$tablename ... SET // here '...' can't contain the word 'SET' +DELETE ...$tablename ... WHERE // same as above +ALTER TABLE $tablename +.. etc (go get from the grammar) .. + +The advantage over doing the same in awk is that mysqlbinlog will also process +RBR statements, and together with that will provide a working solution for +those who are careful with their table names not mixing with string constants +and such. + +(TODO: string constants are of particular concern as they come from +[potentially hostile] users, unlike e.g. table aliases which come from +[not hostile] developers. Remove also all string constants before attempting +to do match?) + +2.3 Have the master put annotations +----------------------------------- +We could add a master option so that it injects into query a mark that tells +which tables the query will affect, e.g. for the query + + UPDATE t1 LEFT JOIN db3.t2 ON ... WHERE ... + + +the binlog will have + + /* !mysqlbinlog: updates t1,db3.t2 */ UPDATE t1 LEFT JOIN ... + +and further processing in mysqlbinlog will be trivial. DESCRIPTION: Replication slave can be set to filter updates to certain tables with --replicate-[wild-]{do,ignore}-table options. This task is about adding similar functionality to mysqlbinlog. HIGH-LEVEL SPECIFICATION: 1. Context ---------- (See http://askmonty.org/wiki/index.php/Scratch/ReplicationOptions for global overview) At the moment, the server has these replication slave options: --replicate-do-table=db.tbl --replicate-ignore-table=db.tbl --replicate-wild-do-table=pattern.pattern --replicate-wild-ignore-table=pattern.pattern They affect both RBR and SBR events. SBR events are checked after the statement has been parsed, the server iterates over list of used tables and checks them againist --replicate instructions. What is interesting is that this scheme still allows to update the ignored table through a VIEW. 2. Table filtering in mysqlbinlog --------------------------------- Per-table filtering of RBR events is easy (as it is relatively easy to extract the name of the table that the event applies to). Per-table filtering of SBR events is hard, as generally it is not apparent which tables the statement refers to. This opens possible options: 2.1 Put the parser into mysqlbinlog ----------------------------------- Once we have a full parser in mysqlbinlog, we'll be able to check which tables are used by a statement, and will allow to show behaviour identical to those that one obtains when using --replicate-* slave options. (It is not clear how much effort is needed to put the parser into mysqlbinlog. Any guesses?) 2.2 Use dumb regexp match ------------------------- Use a really dumb approach. A query is considered to be modifying table X if it matches an expression CREATE TABLE $tablename DROP $tablename UPDATE ...$tablename ... SET // here '...' can't contain the word 'SET' DELETE ...$tablename ... WHERE // same as above ALTER TABLE $tablename .. etc (go get from the grammar) .. The advantage over doing the same in awk is that mysqlbinlog will also process RBR statements, and together with that will provide a working solution for those who are careful with their table names not mixing with string constants and such. (TODO: string constants are of particular concern as they come from [potentially hostile] users, unlike e.g. table aliases which come from [not hostile] developers. Remove also all string constants before attempting to do match?) 2.3 Have the master put annotations ----------------------------------- We could add a master option so that it injects into query a mark that tells which tables the query will affect, e.g. for the query UPDATE t1 LEFT JOIN db3.t2 ON ... WHERE ... the binlog will have /* !mysqlbinlog: updates t1,db3.t2 */ UPDATE t1 LEFT JOIN ... and further processing in mysqlbinlog will be trivial. 2.4 Implement server functionality to ignore certain tables ----------------------------------------------------------- We could add a general facility in the server to ignore certain tables: SET SESSION ignored_tables = "db1.t1,db2.t2"; This would work similar to --replicate-ignore-table, but in a general way not restricted to the slave SQL thread. It would then be trivial for mysqlbinlog to add such statements at the start of the output, or probably the user could just do it manually with no need for additional options for mysqlbinlog. It might be useful to integrate this with the code that already handles --replicate-ignore-db and similar slave options. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Knielsen): Add a mysqlbinlog option to filter updates to certain tables (40)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add a mysqlbinlog option to filter updates to certain tables CREATION DATE..: Mon, 10 Aug 2009, 13:25 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Psergey CATEGORY.......: Server-RawIdeaBin TASK ID........: 40 (http://askmonty.org/worklog/?tid=40) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Knielsen - Fri, 14 Aug 2009, 15:47)=-=- High-Level Specification modified. --- /tmp/wklog.40.old.10896 2009-08-14 15:47:39.000000000 +0300 +++ /tmp/wklog.40.new.10896 2009-08-14 15:47:39.000000000 +0300 @@ -72,3 +72,21 @@ /* !mysqlbinlog: updates t1,db3.t2 */ UPDATE t1 LEFT JOIN ... and further processing in mysqlbinlog will be trivial. + +2.4 Implement server functionality to ignore certain tables +----------------------------------------------------------- + +We could add a general facility in the server to ignore certain tables: + + SET SESSION ignored_tables = "db1.t1,db2.t2"; + +This would work similar to --replicate-ignore-table, but in a general way not +restricted to the slave SQL thread. + +It would then be trivial for mysqlbinlog to add such statements at the start +of the output, or probably the user could just do it manually with no need for +additional options for mysqlbinlog. + +It might be useful to integrate this with the code that already handles +--replicate-ignore-db and similar slave options. + -=-=(Psergey - Mon, 10 Aug 2009, 15:41)=-=- High-Level Specification modified. --- /tmp/wklog.40.old.12989 2009-08-10 15:41:23.000000000 +0300 +++ /tmp/wklog.40.new.12989 2009-08-10 15:41:23.000000000 +0300 @@ -1,6 +1,7 @@ - 1. Context ---------- +(See http://askmonty.org/wiki/index.php/Scratch/ReplicationOptions for global +overview) At the moment, the server has these replication slave options: --replicate-do-table=db.tbl -=-=(Guest - Mon, 10 Aug 2009, 14:52)=-=- Dependency created: 39 now depends on 40 -=-=(Guest - Mon, 10 Aug 2009, 14:51)=-=- High Level Description modified. --- /tmp/wklog.40.old.16985 2009-08-10 14:51:59.000000000 +0300 +++ /tmp/wklog.40.new.16985 2009-08-10 14:51:59.000000000 +0300 @@ -1,3 +1,4 @@ Replication slave can be set to filter updates to certain tables with ---replicate-[wild-]{do,ignore}-table options. This task is about adding similar -functionality to mysqlbinlog. +--replicate-[wild-]{do,ignore}-table options. + +This task is about adding similar functionality to mysqlbinlog. -=-=(Guest - Mon, 10 Aug 2009, 14:51)=-=- High-Level Specification modified. --- /tmp/wklog.40.old.16949 2009-08-10 14:51:33.000000000 +0300 +++ /tmp/wklog.40.new.16949 2009-08-10 14:51:33.000000000 +0300 @@ -1 +1,73 @@ +1. Context +---------- +At the moment, the server has these replication slave options: + + --replicate-do-table=db.tbl + --replicate-ignore-table=db.tbl + --replicate-wild-do-table=pattern.pattern + --replicate-wild-ignore-table=pattern.pattern + +They affect both RBR and SBR events. SBR events are checked after the +statement has been parsed, the server iterates over list of used tables and +checks them againist --replicate instructions. + +What is interesting is that this scheme still allows to update the ignored +table through a VIEW. + +2. Table filtering in mysqlbinlog +--------------------------------- + +Per-table filtering of RBR events is easy (as it is relatively easy to extract +the name of the table that the event applies to). + +Per-table filtering of SBR events is hard, as generally it is not apparent +which tables the statement refers to. + +This opens possible options: + +2.1 Put the parser into mysqlbinlog +----------------------------------- +Once we have a full parser in mysqlbinlog, we'll be able to check which tables +are used by a statement, and will allow to show behaviour identical to those +that one obtains when using --replicate-* slave options. + +(It is not clear how much effort is needed to put the parser into mysqlbinlog. +Any guesses?) + + +2.2 Use dumb regexp match +------------------------- +Use a really dumb approach. A query is considered to be modifying table X if +it matches an expression + +CREATE TABLE $tablename +DROP $tablename +UPDATE ...$tablename ... SET // here '...' can't contain the word 'SET' +DELETE ...$tablename ... WHERE // same as above +ALTER TABLE $tablename +.. etc (go get from the grammar) .. + +The advantage over doing the same in awk is that mysqlbinlog will also process +RBR statements, and together with that will provide a working solution for +those who are careful with their table names not mixing with string constants +and such. + +(TODO: string constants are of particular concern as they come from +[potentially hostile] users, unlike e.g. table aliases which come from +[not hostile] developers. Remove also all string constants before attempting +to do match?) + +2.3 Have the master put annotations +----------------------------------- +We could add a master option so that it injects into query a mark that tells +which tables the query will affect, e.g. for the query + + UPDATE t1 LEFT JOIN db3.t2 ON ... WHERE ... + + +the binlog will have + + /* !mysqlbinlog: updates t1,db3.t2 */ UPDATE t1 LEFT JOIN ... + +and further processing in mysqlbinlog will be trivial. DESCRIPTION: Replication slave can be set to filter updates to certain tables with --replicate-[wild-]{do,ignore}-table options. This task is about adding similar functionality to mysqlbinlog. HIGH-LEVEL SPECIFICATION: 1. Context ---------- (See http://askmonty.org/wiki/index.php/Scratch/ReplicationOptions for global overview) At the moment, the server has these replication slave options: --replicate-do-table=db.tbl --replicate-ignore-table=db.tbl --replicate-wild-do-table=pattern.pattern --replicate-wild-ignore-table=pattern.pattern They affect both RBR and SBR events. SBR events are checked after the statement has been parsed, the server iterates over list of used tables and checks them againist --replicate instructions. What is interesting is that this scheme still allows to update the ignored table through a VIEW. 2. Table filtering in mysqlbinlog --------------------------------- Per-table filtering of RBR events is easy (as it is relatively easy to extract the name of the table that the event applies to). Per-table filtering of SBR events is hard, as generally it is not apparent which tables the statement refers to. This opens possible options: 2.1 Put the parser into mysqlbinlog ----------------------------------- Once we have a full parser in mysqlbinlog, we'll be able to check which tables are used by a statement, and will allow to show behaviour identical to those that one obtains when using --replicate-* slave options. (It is not clear how much effort is needed to put the parser into mysqlbinlog. Any guesses?) 2.2 Use dumb regexp match ------------------------- Use a really dumb approach. A query is considered to be modifying table X if it matches an expression CREATE TABLE $tablename DROP $tablename UPDATE ...$tablename ... SET // here '...' can't contain the word 'SET' DELETE ...$tablename ... WHERE // same as above ALTER TABLE $tablename .. etc (go get from the grammar) .. The advantage over doing the same in awk is that mysqlbinlog will also process RBR statements, and together with that will provide a working solution for those who are careful with their table names not mixing with string constants and such. (TODO: string constants are of particular concern as they come from [potentially hostile] users, unlike e.g. table aliases which come from [not hostile] developers. Remove also all string constants before attempting to do match?) 2.3 Have the master put annotations ----------------------------------- We could add a master option so that it injects into query a mark that tells which tables the query will affect, e.g. for the query UPDATE t1 LEFT JOIN db3.t2 ON ... WHERE ... the binlog will have /* !mysqlbinlog: updates t1,db3.t2 */ UPDATE t1 LEFT JOIN ... and further processing in mysqlbinlog will be trivial. 2.4 Implement server functionality to ignore certain tables ----------------------------------------------------------- We could add a general facility in the server to ignore certain tables: SET SESSION ignored_tables = "db1.t1,db2.t2"; This would work similar to --replicate-ignore-table, but in a general way not restricted to the slave SQL thread. It would then be trivial for mysqlbinlog to add such statements at the start of the output, or probably the user could just do it manually with no need for additional options for mysqlbinlog. It might be useful to integrate this with the code that already handles --replicate-ignore-db and similar slave options. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Knielsen): Add a mysqlbinlog option to filter certain kinds of statements (41)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add a mysqlbinlog option to filter certain kinds of statements CREATION DATE..: Mon, 10 Aug 2009, 15:30 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 41 (http://askmonty.org/worklog/?tid=41) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Knielsen - Fri, 14 Aug 2009, 14:17)=-=- High-Level Specification modified. --- /tmp/wklog.41.old.6963 2009-08-14 14:17:32.000000000 +0300 +++ /tmp/wklog.41.new.6963 2009-08-14 14:17:32.000000000 +0300 @@ -1,6 +1,11 @@ The implementation will depend on design choices made in WL#40: -- If we decide to parse the statement, SQL-verb filtering will be trivial -- If we decide not to parse the statement, we still can reliably distinguish the + +Option 1: + +If we decide to parse the statement, SQL-verb filtering will be trivial + +Option 2: +If we decide not to parse the statement, we still can reliably distinguish the statement by matching the first characters against a set of patterns. If we chose the second, we'll have to perform certain normalization before -=-=(Psergey - Mon, 10 Aug 2009, 15:47)=-=- High-Level Specification modified. --- /tmp/wklog.41.old.13282 2009-08-10 15:47:13.000000000 +0300 +++ /tmp/wklog.41.new.13282 2009-08-10 15:47:13.000000000 +0300 @@ -2,3 +2,10 @@ - If we decide to parse the statement, SQL-verb filtering will be trivial - If we decide not to parse the statement, we still can reliably distinguish the statement by matching the first characters against a set of patterns. + +If we chose the second, we'll have to perform certain normalization before +matching the patterns: + - Remove all comments from the command + - Remove all pre-space + - Compare the string case-insensitively + - etc -=-=(Psergey - Mon, 10 Aug 2009, 15:35)=-=- High-Level Specification modified. --- /tmp/wklog.41.old.12689 2009-08-10 15:35:04.000000000 +0300 +++ /tmp/wklog.41.new.12689 2009-08-10 15:35:04.000000000 +0300 @@ -1 +1,4 @@ - +The implementation will depend on design choices made in WL#40: +- If we decide to parse the statement, SQL-verb filtering will be trivial +- If we decide not to parse the statement, we still can reliably distinguish the +statement by matching the first characters against a set of patterns. -=-=(Psergey - Mon, 10 Aug 2009, 15:31)=-=- Dependency created: 39 now depends on 41 DESCRIPTION: Add a mysqlbinlog option to filter certain kinds of statements, i.e. (syntax subject to discussion): mysqlbinlog --exclude='alter table,drop table,alter database,...' HIGH-LEVEL SPECIFICATION: The implementation will depend on design choices made in WL#40: Option 1: If we decide to parse the statement, SQL-verb filtering will be trivial Option 2: If we decide not to parse the statement, we still can reliably distinguish the statement by matching the first characters against a set of patterns. If we chose the second, we'll have to perform certain normalization before matching the patterns: - Remove all comments from the command - Remove all pre-space - Compare the string case-insensitively - etc ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Knielsen): Add a mysqlbinlog option to filter certain kinds of statements (41)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Add a mysqlbinlog option to filter certain kinds of statements CREATION DATE..: Mon, 10 Aug 2009, 15:30 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Client-BackLog TASK ID........: 41 (http://askmonty.org/worklog/?tid=41) VERSION........: Benchmarks-3.0 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Knielsen - Fri, 14 Aug 2009, 14:17)=-=- High-Level Specification modified. --- /tmp/wklog.41.old.6963 2009-08-14 14:17:32.000000000 +0300 +++ /tmp/wklog.41.new.6963 2009-08-14 14:17:32.000000000 +0300 @@ -1,6 +1,11 @@ The implementation will depend on design choices made in WL#40: -- If we decide to parse the statement, SQL-verb filtering will be trivial -- If we decide not to parse the statement, we still can reliably distinguish the + +Option 1: + +If we decide to parse the statement, SQL-verb filtering will be trivial + +Option 2: +If we decide not to parse the statement, we still can reliably distinguish the statement by matching the first characters against a set of patterns. If we chose the second, we'll have to perform certain normalization before -=-=(Psergey - Mon, 10 Aug 2009, 15:47)=-=- High-Level Specification modified. --- /tmp/wklog.41.old.13282 2009-08-10 15:47:13.000000000 +0300 +++ /tmp/wklog.41.new.13282 2009-08-10 15:47:13.000000000 +0300 @@ -2,3 +2,10 @@ - If we decide to parse the statement, SQL-verb filtering will be trivial - If we decide not to parse the statement, we still can reliably distinguish the statement by matching the first characters against a set of patterns. + +If we chose the second, we'll have to perform certain normalization before +matching the patterns: + - Remove all comments from the command + - Remove all pre-space + - Compare the string case-insensitively + - etc -=-=(Psergey - Mon, 10 Aug 2009, 15:35)=-=- High-Level Specification modified. --- /tmp/wklog.41.old.12689 2009-08-10 15:35:04.000000000 +0300 +++ /tmp/wklog.41.new.12689 2009-08-10 15:35:04.000000000 +0300 @@ -1 +1,4 @@ - +The implementation will depend on design choices made in WL#40: +- If we decide to parse the statement, SQL-verb filtering will be trivial +- If we decide not to parse the statement, we still can reliably distinguish the +statement by matching the first characters against a set of patterns. -=-=(Psergey - Mon, 10 Aug 2009, 15:31)=-=- Dependency created: 39 now depends on 41 DESCRIPTION: Add a mysqlbinlog option to filter certain kinds of statements, i.e. (syntax subject to discussion): mysqlbinlog --exclude='alter table,drop table,alter database,...' HIGH-LEVEL SPECIFICATION: The implementation will depend on design choices made in WL#40: Option 1: If we decide to parse the statement, SQL-verb filtering will be trivial Option 2: If we decide not to parse the statement, we still can reliably distinguish the statement by matching the first characters against a set of patterns. If we chose the second, we'll have to perform certain normalization before matching the patterns: - Remove all comments from the command - Remove all pre-space - Compare the string case-insensitively - etc ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Progress (by Guest): Implement UNION ALL without usage of a temporary table (44)
by worklog-noreply＠askmonty.org 14 Aug '09

14 Aug '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Implement UNION ALL without usage of a temporary table CREATION DATE..: Fri, 14 Aug 2009, 08:31 SUPERVISOR.....: Monty IMPLEMENTOR....: COPIES TO......: Monty, Psergey CATEGORY.......: Client-BackLog TASK ID........: 44 (http://askmonty.org/worklog/?tid=44) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 20 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Fri, 14 Aug 2009, 09:13)=-=- 2009-8-10: spent 3.5 hrs for analysis of the current implementation of UNION/UNION ALL came up with the idea how to bypass temporary table when executing UNION ALL 2009-8-11: spent 6.5 hrs to prepare a hack that executed UNION ALL without temporary table 2009-8-12: spent 4 hrs more to investigate in debugger different cases with usage of union operations (in subqueries, in queries that do not use tables) 2009-8-13: spent 6 hrs to put together and to publish an HLS document for the task Worked 20 hours and estimate 0 hours remain (original estimate increased by 20 hours). -=-=(Guest - Fri, 14 Aug 2009, 08:52)=-=- Supervisor updated. --- /tmp/wklog.44.old.22769 2009-08-14 08:52:13.000000000 +0300 +++ /tmp/wklog.44.new.22769 2009-08-14 08:52:13.000000000 +0300 @@ -1 +1 @@ -Bothorsen +Monty -=-=(Guest - Fri, 14 Aug 2009, 08:52)=-=- Version updated. --- /tmp/wklog.44.old.22769 2009-08-14 08:52:13.000000000 +0300 +++ /tmp/wklog.44.new.22769 2009-08-14 08:52:13.000000000 +0300 @@ -1 +1 @@ -Benchmarks-3.0 +Server-9.x -=-=(Guest - Fri, 14 Aug 2009, 08:52)=-=- Privacy level updated. --- /tmp/wklog.44.old.22769 2009-08-14 08:52:13.000000000 +0300 +++ /tmp/wklog.44.new.22769 2009-08-14 08:52:13.000000000 +0300 @@ -1 +1 @@ -y +n -=-=(Guest - Fri, 14 Aug 2009, 08:50)=-=- High-Level Specification modified. --- /tmp/wklog.44.old.22656 2009-08-14 08:50:48.000000000 +0300 +++ /tmp/wklog.44.new.22656 2009-08-14 08:50:48.000000000 +0300 @@ -19,28 +19,29 @@ UNION and UNION ALL are the only set operations supported by MySQL Server. MySQL allows us to use these operations in a sequence, one after another. For example the following queries are accepted by the MySQL Server: - (select a1,b1,c1 from t1 where a1=b1) union (select a2,b2,c2 from t2 where -a2!=b2) union + (select a1,b1,c1 from t1 where a1=b1) union + (select a2,b2,c2 from t2 where a2!=b2) union (select a3,b3,c3 from t3 where a3>b3); (1) - (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where -a2!=b2) union all + (select a1,b1,c1 from t1 where a1=b1) union all + (select a2,b2,c2 from t2 where a2!=b2) union all (select a3,b3,c3 from t3 where a3>b3); (2) Any mix of UNION and UNION ALL is also acceptable: - (select a1,b1,c3 from t1 where a1=b1) union (select a2,b2,c3 from t2 where -a2!=b2) union all + (select a1,b1,c3 from t1 where a1=b1) union + (select a2,b2,c3 from t2 where a2!=b2) union all (select a3,b3,c3 from t3 where a3>b3); (3) - (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where -a2!=b2) union + (select a1,b1,c1 from t1 where a1=b1) union all + (select a2,b2,c2 from t2 where a2!=b2) union (select a3,b3,c3 from t3 where a3>b3); (4) + It should be noted that query (4) is equivalent to query (1). At the same time query (3) is not equivalent to any of the queries (1),(2),(4). In general any UNION ALL in a sequence of union operations can be equivalently substituted for UNION if there occur another UNION further in the sequence. -MySQL does not accept nested unions. For example the following valid query is -considered by MySQL Server as erroneous: - ( (select a1,b1 from t1 where a1=b1) union (select a2,b2 from t2 where a2!=b2) -) union all - ( (select a3,b3 from t3 where a3=b3) union (select a4,b4 from t4 where a4!=b4) ) +MySQL does not accept nested unions. For example the following valid SQL query +is considered by MySQL Server as erroneous: + ((select a1,b1 from t1 where a1=b1) union (select a2,b2 from t2 where a2!=b2)) + union all + ((select a3,b3 from t3 where a3=b3) union (select a4,b4 from t4 where a4!=b4)) A sequence of select constructs separated by UNION/UNION ALL is called 'union unit' if it s not a part of another such sequence. -=-=(Guest - Fri, 14 Aug 2009, 08:45)=-=- High-Level Specification modified. --- /tmp/wklog.44.old.22406 2009-08-14 08:45:22.000000000 +0300 +++ /tmp/wklog.44.new.22406 2009-08-14 08:45:22.000000000 +0300 @@ -6,15 +6,15 @@ 2. Optimizations improving performance of UNION ALL operations 2.1 Execution of UNION ALL without temporary table 2.2. Avoiding unnecessary copying - 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations + 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL 3. Other possible optimizations for union units </contents> 1. Handling union operations in MySQL Server -================================== +============================================ 1.1. Specifics of MySQL union operations ------------------------------------------------------- +---------------------------------------- UNION and UNION ALL are the only set operations supported by MySQL Server. MySQL allows us to use these operations in a sequence, one after another. For example @@ -49,7 +49,7 @@ In this case it cannot be used as a subquery. 1.2 Validation of union units ----------------------------------- +----------------------------- When the parser stage is over the further processing of a union unit is performed by the function mysql_union. @@ -77,7 +77,7 @@ select_union. All selects from a union unit share the same select_union object. 1.3 Execution of union units ----------------------------------- +---------------------------- After SELECT_LEX_UNIT::prepare has successfully validated the union unit, has created a temporary table as a container for rows from the result sets returned @@ -109,13 +109,13 @@ rows read from the temporary table have to be sorted first. 2. Optimizations improving performance of UNION ALL operations -================================================= +=============================================================== The following three optimizations are proposed to be implemented in the framework of this task. 2.1 Execution of UNION ALL without temporary table ------------------------------------------------------------------- +-------------------------------------------------- If a union unit with only UNION ALL operations is used at the top level of the query (in other words it's not used as a subquery) and is not appended with an @@ -159,7 +159,7 @@ }; 2.2. Avoiding unnecessary copying ------------------------------------------- +--------------------------------- If a field does not need type conversion it does not make sense to send it to a record buffer. It can be sent directly to the output stream. Different selects @@ -174,8 +174,8 @@ needed that would take as parameter the info that says what fields are to be stored in the record buffer. -2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations ----------------------------------------------------------------------------------------------------------- +2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL +---------------------------------------------------------------------- If a union unit with a mix of UNIIN/UNION ALL operations and without ORDER BY is used at the top level of a query then any UNION ALL operation after the last @@ -190,7 +190,7 @@ 3. Other possible optimizations for union units -================================= +=============================================== The following optimizations are not supposed to be implemented in the framework this task. -=-=(Guest - Fri, 14 Aug 2009, 08:41)=-=- High-Level Specification modified. --- /tmp/wklog.44.old.22182 2009-08-14 08:41:17.000000000 +0300 +++ /tmp/wklog.44.new.22182 2009-08-14 08:41:17.000000000 +0300 @@ -1 +1,205 @@ +<contents> +1. Handling union operations in MySQL Server + 1.1. Specifics of MySQL union operations + 1.2 Validation of union units + 1.3 Execution of union units +2. Optimizations improving performance of UNION ALL operations + 2.1 Execution of UNION ALL without temporary table + 2.2. Avoiding unnecessary copying + 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations +3. Other possible optimizations for union units +</contents> + +1. Handling union operations in MySQL Server +================================== + +1.1. Specifics of MySQL union operations +------------------------------------------------------ + +UNION and UNION ALL are the only set operations supported by MySQL Server. MySQL +allows us to use these operations in a sequence, one after another. For example +the following queries are accepted by the MySQL Server: + (select a1,b1,c1 from t1 where a1=b1) union (select a2,b2,c2 from t2 where +a2!=b2) union + (select a3,b3,c3 from t3 where a3>b3); (1) + (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where +a2!=b2) union all + (select a3,b3,c3 from t3 where a3>b3); (2) +Any mix of UNION and UNION ALL is also acceptable: + (select a1,b1,c3 from t1 where a1=b1) union (select a2,b2,c3 from t2 where +a2!=b2) union all + (select a3,b3,c3 from t3 where a3>b3); (3) + (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where +a2!=b2) union + (select a3,b3,c3 from t3 where a3>b3); (4) +It should be noted that query (4) is equivalent to query (1). At the same time +query (3) is not equivalent to any of the queries (1),(2),(4). +In general any UNION ALL in a sequence of union operations can be equivalently +substituted for UNION if there occur another UNION further in the sequence. +MySQL does not accept nested unions. For example the following valid query is +considered by MySQL Server as erroneous: + ( (select a1,b1 from t1 where a1=b1) union (select a2,b2 from t2 where a2!=b2) +) union all + ( (select a3,b3 from t3 where a3=b3) union (select a4,b4 from t4 where a4!=b4) ) + +A sequence of select constructs separated by UNION/UNION ALL is called 'union +unit' if it s not a part of another such sequence. +A union unit can be executed as a query. It also can be used as a subquery. +A union unit can be optionally appended by an ORDER BY and/or LIMIT construct. +In this case it cannot be used as a subquery. + +1.2 Validation of union units +---------------------------------- + +When the parser stage is over the further processing of a union unit is +performed by the function mysql_union. +The function first validate the unit in the method SELECT_LEX_UNIT::prepare. +The method first validates each of the select constructs of the unit and then it +checks that all select are compatible. The method checks that the selects return +the same number of columns and for each set of columns with the same number k +there is a type to which the types of the columns can be coerced. This type is +considered as the type of column k of the result set returned by the union unit. +For example, if in the query (1) the columns b1, b2 and b3 are of the types int, +bigint and double respectively then the second column of the union unit will be +of the type double. If the types of the columns c1,c2,c3 are specified as +varchar(10), varchar(20), varchar(10) then the type of the corresponding column +of the result set will be varchar(20). If the columns have different collations +then a collation from which all these collations can be derived is looked for +and it is assigned as the +collation of the third column in the result set. +After compatibility of the corresponding select columns has been checked and the +types of the columns from of the result set have been determined the method +SELECT_LEX_UNIT::prepare creates a temporary table to store the rows of the +result set for the union unit. Currently rows returned by the selects from the +union unit are always written into a temporary table. To force selects to send +rows to this temporary table SELECT_LEX_UNIT::prepare creates JOIN objects for +the selects such that the JOIN::result field refers to an object of the class +select_union. All selects from a union unit share the same select_union object. + +1.3 Execution of union units +---------------------------------- + +After SELECT_LEX_UNIT::prepare has successfully validated the union unit, has +created a temporary table as a container for rows from the result sets returned +by the selects of the unit, and has prepared all data structures needed for +execution, the function mysql_union invokes SELECT_LEX_UNIT::exec. +The method SELECT_LEX_UNIT::exec processes the selects from the union unit one +by one. +Each select first is optimized with JOIN::optimize(), then it's executed with +JOIN::exec().The result rows from each select are sent to a temporary table. +This table accumulates all rows that are to be returned by the union unit. For +UNION operations duplicate rows are not added, for UNION ALL operations all +records are added. It is achieved by enabling and disabling usage of the unique +index defined on all fields of the temporary table. The index is never used if +only UINION ALL operation occurs in the unit. Otherwise it is enabled before +the first select is executed and disabled after the last UNION operation. +To send rows to the temporary table the method select_union::send_data is used. +For a row it receives from the currently executed select the method first stores +the fields of the row in in the fields of the record buffer of the temporary +table. To do this the method calls function fill_record. All needed type +conversions of the field values are performed when they are stored the record +buffer. After this the method select_union::send_data calls the ha_write_row +handler function to write the record from the buffer to the temporary table. A +possible error on duplicate key that occurs with an attempt to write a duplicate +row is ignored. +After all rows received from all selects have been placed into the temporary +table the method SELECT_LEX_UNIT::exec calls mysql_select that reads rows +from the temporary table and sends them to the output stream (to the client). If +there is an ORDER BY clause to be applied to result of the union unit then the +rows read from the temporary table have to be sorted first. + +2. Optimizations improving performance of UNION ALL operations +================================================= + +The following three optimizations are proposed to be implemented in the +framework of this task. + +2.1 Execution of UNION ALL without temporary table +------------------------------------------------------------------ + +If a union unit with only UNION ALL operations is used at the top level of the +query (in other words it's not used as a subquery) and is not appended with an +ORDER BY clause then it does not make sense to send rows received from selects +to a temporary table at all. After all needed type conversions have been done +the row fields could be sent directly into the output stream. It would improve +the performance of UNION ALL operations since writing to the temporary table and +reading from it would not be needed anymore. In the cases when the result set is +big enough and the temporary table cannot be allocated in the main memory the +performance gains would be significant. Besides, the client could get the first +result rows at once as it would not have to wait until all selects have been +executed. +To make an UNION ALL operation not to send rows to a temporary table we could +provide the JOIN objects created for the selects from the union unit with an +interceptor object that differs from the one they use now. In the current code +they use an object of the class select_union derived from the +select_result_interceptor class. The new interceptor object of the class that +we'll call select_union_send (by analogy with the class select_send) shall +inherit from the select_union and shall have its own implementations of the +virtual methods send_data, send_fields, and send_eof. +The method send_data shall send fields received from selects to the record +buffer of the temporary table and then from this buffer to the output stream. +The method send_fields shall send the format of the rows to the client before it +starts getting records from the first select , while the method send_eof shall +signal about the end of the rows after the last select finishes sending records. +The method create_result_table of the class select_union shall be re-defined +as virtual. The implementation of this method for the class select_union_send +shall call select_union::create_result_table and then shall build internal +structures needed for select_unionsend::send_data. So, the definition of the +class select_union_send should look like this: + class select_union_send :public select_union + { + ... // private structures + public: + select_union_send() :select_union(), ...{...} + bool send_data(List<Item> &items); + bool send_fields(List<Item> &list, uint flags); + bool create_result_table(THD *thd, List<Item> *column_types, + bool is_distinct, ulonglong options, + const char *alias); + }; + +2.2. Avoiding unnecessary copying +------------------------------------------ + +If a field does not need type conversion it does not make sense to send it to a +record buffer. It can be sent directly to the output stream. Different selects +can require type conversions for different columns. +Let's provide each select from the union unit with a data structure (e.g. a +bitmap) that says what fields require conversions, and what don't . Before +execution of a select this data structure must be passed to the +select_union_send object shared by all selects from the unit. The info in this +structure will tell select_union_send::send_data what fields should be sent to +the record buffer for type conversion and what can be sent directly to the +output stream. In this case another variant of the fill_record procedure is +needed that would take as parameter the info that says what fields are to be +stored in the record buffer. + +2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL operations +---------------------------------------------------------------------------------------------------------- + +If a union unit with a mix of UNIIN/UNION ALL operations and without ORDER BY is +used at the top level of a query then any UNION ALL operation after the last +UNION operation can be executed in more efficient way than it's done in the +current implementation. More exactly, the rows from any select that follows +after the second operand of the last UNION operations could be sent directly to +the output stream. In this case two interceptor objects have to be created: one, +of the type select_union, is shared by the selects for which UNION operations +are performed, another, of the type select_union_send, is shared by the the +remaining selects. For this optimization the method SELECT_LEX_UNIT::exec is to +undergo a serious re-work. + + +3. Other possible optimizations for union units +================================= + +The following optimizations are not supposed to be implemented in the framework +this task. +1. For a union unit containing only UNION ALL with an ORDER BY send rows from +selects directly to the sorting procedure. +2. For a union unit at the top level of the query without ORDER BY clause send +any row received from an operand of a UNION operation directly to the output +stream as soon as it has been checked by a lookup in the temporary table that +it's not a duplicate. +3. Not to use temporary table for any union unit used in EXIST or IN subquery. + DESCRIPTION: Currently when any union operation is executed the rows received from its operands are always sent to a temporary table. Meanwhile for a UNION ALL operation that is used at the top level of a query without an ORDER BY clause it is not necessary. In this case the rows could be sent directly to the client. The goal of this task is to provide such an implementation of UNION ALL operation that would not use temporary table at all in certain, most usable cases. HIGH-LEVEL SPECIFICATION: <contents> 1. Handling union operations in MySQL Server 1.1. Specifics of MySQL union operations 1.2 Validation of union units 1.3 Execution of union units 2. Optimizations improving performance of UNION ALL operations 2.1 Execution of UNION ALL without temporary table 2.2. Avoiding unnecessary copying 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL 3. Other possible optimizations for union units </contents> 1. Handling union operations in MySQL Server ============================================ 1.1. Specifics of MySQL union operations ---------------------------------------- UNION and UNION ALL are the only set operations supported by MySQL Server. MySQL allows us to use these operations in a sequence, one after another. For example the following queries are accepted by the MySQL Server: (select a1,b1,c1 from t1 where a1=b1) union (select a2,b2,c2 from t2 where a2!=b2) union (select a3,b3,c3 from t3 where a3>b3); (1) (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where a2!=b2) union all (select a3,b3,c3 from t3 where a3>b3); (2) Any mix of UNION and UNION ALL is also acceptable: (select a1,b1,c3 from t1 where a1=b1) union (select a2,b2,c3 from t2 where a2!=b2) union all (select a3,b3,c3 from t3 where a3>b3); (3) (select a1,b1,c1 from t1 where a1=b1) union all (select a2,b2,c2 from t2 where a2!=b2) union (select a3,b3,c3 from t3 where a3>b3); (4) It should be noted that query (4) is equivalent to query (1). At the same time query (3) is not equivalent to any of the queries (1),(2),(4). In general any UNION ALL in a sequence of union operations can be equivalently substituted for UNION if there occur another UNION further in the sequence. MySQL does not accept nested unions. For example the following valid SQL query is considered by MySQL Server as erroneous: ((select a1,b1 from t1 where a1=b1) union (select a2,b2 from t2 where a2!=b2)) union all ((select a3,b3 from t3 where a3=b3) union (select a4,b4 from t4 where a4!=b4)) A sequence of select constructs separated by UNION/UNION ALL is called 'union unit' if it s not a part of another such sequence. A union unit can be executed as a query. It also can be used as a subquery. A union unit can be optionally appended by an ORDER BY and/or LIMIT construct. In this case it cannot be used as a subquery. 1.2 Validation of union units ----------------------------- When the parser stage is over the further processing of a union unit is performed by the function mysql_union. The function first validate the unit in the method SELECT_LEX_UNIT::prepare. The method first validates each of the select constructs of the unit and then it checks that all select are compatible. The method checks that the selects return the same number of columns and for each set of columns with the same number k there is a type to which the types of the columns can be coerced. This type is considered as the type of column k of the result set returned by the union unit. For example, if in the query (1) the columns b1, b2 and b3 are of the types int, bigint and double respectively then the second column of the union unit will be of the type double. If the types of the columns c1,c2,c3 are specified as varchar(10), varchar(20), varchar(10) then the type of the corresponding column of the result set will be varchar(20). If the columns have different collations then a collation from which all these collations can be derived is looked for and it is assigned as the collation of the third column in the result set. After compatibility of the corresponding select columns has been checked and the types of the columns from of the result set have been determined the method SELECT_LEX_UNIT::prepare creates a temporary table to store the rows of the result set for the union unit. Currently rows returned by the selects from the union unit are always written into a temporary table. To force selects to send rows to this temporary table SELECT_LEX_UNIT::prepare creates JOIN objects for the selects such that the JOIN::result field refers to an object of the class select_union. All selects from a union unit share the same select_union object. 1.3 Execution of union units ---------------------------- After SELECT_LEX_UNIT::prepare has successfully validated the union unit, has created a temporary table as a container for rows from the result sets returned by the selects of the unit, and has prepared all data structures needed for execution, the function mysql_union invokes SELECT_LEX_UNIT::exec. The method SELECT_LEX_UNIT::exec processes the selects from the union unit one by one. Each select first is optimized with JOIN::optimize(), then it's executed with JOIN::exec().The result rows from each select are sent to a temporary table. This table accumulates all rows that are to be returned by the union unit. For UNION operations duplicate rows are not added, for UNION ALL operations all records are added. It is achieved by enabling and disabling usage of the unique index defined on all fields of the temporary table. The index is never used if only UINION ALL operation occurs in the unit. Otherwise it is enabled before the first select is executed and disabled after the last UNION operation. To send rows to the temporary table the method select_union::send_data is used. For a row it receives from the currently executed select the method first stores the fields of the row in in the fields of the record buffer of the temporary table. To do this the method calls function fill_record. All needed type conversions of the field values are performed when they are stored the record buffer. After this the method select_union::send_data calls the ha_write_row handler function to write the record from the buffer to the temporary table. A possible error on duplicate key that occurs with an attempt to write a duplicate row is ignored. After all rows received from all selects have been placed into the temporary table the method SELECT_LEX_UNIT::exec calls mysql_select that reads rows from the temporary table and sends them to the output stream (to the client). If there is an ORDER BY clause to be applied to result of the union unit then the rows read from the temporary table have to be sorted first. 2. Optimizations improving performance of UNION ALL operations =============================================================== The following three optimizations are proposed to be implemented in the framework of this task. 2.1 Execution of UNION ALL without temporary table -------------------------------------------------- If a union unit with only UNION ALL operations is used at the top level of the query (in other words it's not used as a subquery) and is not appended with an ORDER BY clause then it does not make sense to send rows received from selects to a temporary table at all. After all needed type conversions have been done the row fields could be sent directly into the output stream. It would improve the performance of UNION ALL operations since writing to the temporary table and reading from it would not be needed anymore. In the cases when the result set is big enough and the temporary table cannot be allocated in the main memory the performance gains would be significant. Besides, the client could get the first result rows at once as it would not have to wait until all selects have been executed. To make an UNION ALL operation not to send rows to a temporary table we could provide the JOIN objects created for the selects from the union unit with an interceptor object that differs from the one they use now. In the current code they use an object of the class select_union derived from the select_result_interceptor class. The new interceptor object of the class that we'll call select_union_send (by analogy with the class select_send) shall inherit from the select_union and shall have its own implementations of the virtual methods send_data, send_fields, and send_eof. The method send_data shall send fields received from selects to the record buffer of the temporary table and then from this buffer to the output stream. The method send_fields shall send the format of the rows to the client before it starts getting records from the first select , while the method send_eof shall signal about the end of the rows after the last select finishes sending records. The method create_result_table of the class select_union shall be re-defined as virtual. The implementation of this method for the class select_union_send shall call select_union::create_result_table and then shall build internal structures needed for select_unionsend::send_data. So, the definition of the class select_union_send should look like this: class select_union_send :public select_union { ... // private structures public: select_union_send() :select_union(), ...{...} bool send_data(List<Item> &items); bool send_fields(List<Item> &list, uint flags); bool create_result_table(THD *thd, List<Item> *column_types, bool is_distinct, ulonglong options, const char *alias); }; 2.2. Avoiding unnecessary copying --------------------------------- If a field does not need type conversion it does not make sense to send it to a record buffer. It can be sent directly to the output stream. Different selects can require type conversions for different columns. Let's provide each select from the union unit with a data structure (e.g. a bitmap) that says what fields require conversions, and what don't . Before execution of a select this data structure must be passed to the select_union_send object shared by all selects from the unit. The info in this structure will tell select_union_send::send_data what fields should be sent to the record buffer for type conversion and what can be sent directly to the output stream. In this case another variant of the fill_record procedure is needed that would take as parameter the info that says what fields are to be stored in the record buffer. 2.3 Optimizing execution of a union unit with a mix of UNION/UNION ALL ---------------------------------------------------------------------- If a union unit with a mix of UNIIN/UNION ALL operations and without ORDER BY is used at the top level of a query then any UNION ALL operation after the last UNION operation can be executed in more efficient way than it's done in the current implementation. More exactly, the rows from any select that follows after the second operand of the last UNION operations could be sent directly to the output stream. In this case two interceptor objects have to be created: one, of the type select_union, is shared by the selects for which UNION operations are performed, another, of the type select_union_send, is shared by the the remaining selects. For this optimization the method SELECT_LEX_UNIT::exec is to undergo a serious re-work. 3. Other possible optimizations for union units =============================================== The following optimizations are not supposed to be implemented in the framework this task. 1. For a union unit containing only UNION ALL with an ORDER BY send rows from selects directly to the sorting procedure. 2. For a union unit at the top level of the query without ORDER BY clause send any row received from an operand of a UNION operation directly to the output stream as soon as it has been checked by a lookup in the temporary table that it's not a duplicate. 3. Not to use temporary table for any union unit used in EXIST or IN subquery. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0