- developers - lists.mariadb.org

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (knielsen:2703)
by knielsen＠knielsen-hq.org 22 Jun '09

22 Jun '09

#At lp:maria 2703 knielsen(a)knielsen-hq.org 2009-06-10 Fix XtraDB to build with atomic operations, for good performance. The root of the problem is that ./configure mixed together two different things. One is the availability of GCC atomic operation intrinsics. The other is the selection of which primitives to use for my_atomic implementation. Then at some point a hack was made to not use GCC intrinsics in my_atomic to work around some test failures. But because the two things are mixed in ./configure, this as a side effect also makes GCC intrinsics unavailable for XtraDB. Fixed by splitting this in two in configure, so that we have HAVE_GCC_ATOMIC_BUILTINS for GCC intrinsics availability and MY_ATOMIC_MODE_GCC_BUILTINS for use in my_atomic. modified: configure.in include/atomic/nolock.h === modified file 'configure.in' --- a/configure.in 2009-04-23 13:06:16 +0000 +++ b/configure.in 2009-06-10 09:13:53 +0000 @@ -1726,6 +1726,30 @@ then fi fi +AC_CACHE_CHECK([whether the compiler provides atomic builtins], + [mysql_cv_gcc_atomic_builtins], [AC_TRY_RUN([ + int main() + { + int foo= -10; int bar= 10; + if (!__sync_fetch_and_add(&foo, bar) || foo) + return -1; + bar= __sync_lock_test_and_set(&foo, bar); + if (bar || foo != 10) + return -1; + bar= __sync_val_compare_and_swap(&bar, foo, 15); + if (bar) + return -1; + return 0; + } +], [mysql_cv_gcc_atomic_builtins=yes], + [mysql_cv_gcc_atomic_builtins=no], + [mysql_cv_gcc_atomic_builtins=no])]) + +if test "x$mysql_cv_gcc_atomic_builtins" = xyes; then + AC_DEFINE(HAVE_GCC_ATOMIC_BUILTINS, 1, + [Define to 1 if compiler provides atomic builtins.]) +fi + AC_ARG_WITH([atomic-ops], AC_HELP_STRING([--with-atomic-ops=rwlocks|smp|up], [Implement atomic operations using pthread rwlocks or atomic CPU @@ -1739,28 +1763,9 @@ case "$with_atomic_ops" in [Use pthread rwlocks for atomic ops]) ;; "smp") ;; "") - AC_CACHE_CHECK([whether the compiler provides atomic builtins], - [mysql_cv_gcc_atomic_builtins], [AC_TRY_RUN([ - int main() - { - int foo= -10; int bar= 10; - if (!__sync_fetch_and_add(&foo, bar) || foo) - return -1; - bar= __sync_lock_test_and_set(&foo, bar); - if (bar || foo != 10) - return -1; - bar= __sync_val_compare_and_swap(&bar, foo, 15); - if (bar) - return -1; - return 0; - } - ], [mysql_cv_gcc_atomic_builtins=yes_but_disabled], - [mysql_cv_gcc_atomic_builtins=no], - [mysql_cv_gcc_atomic_builtins=no])]) - - if test "x$mysql_cv_gcc_atomic_builtins" = xyes; then - AC_DEFINE(HAVE_GCC_ATOMIC_BUILTINS, 1, - [Define to 1 if compiler provides atomic builtins.]) + if test "x$mysql_cv_gcc_atomic_builtins" = xyes_but_disabled; then + AC_DEFINE([MY_ATOMIC_MODE_GCC_BUILTINS], [1], + [Use GCC atomic builtins for atomic ops]) fi ;; *) AC_MSG_ERROR(["$with_atomic_ops" is not a valid value for --with-atomic-ops]) ;; === modified file 'include/atomic/nolock.h' --- a/include/atomic/nolock.h 2008-02-05 15:47:11 +0000 +++ b/include/atomic/nolock.h 2009-06-10 09:13:53 +0000 @@ -14,7 +14,7 @@ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #if defined(__i386__) || defined(_MSC_VER) || \ - defined(__x86_64__) || defined(HAVE_GCC_ATOMIC_BUILTINS) + defined(__x86_64__) || defined(MY_ATOMIC_MODE_GCC_BUILTINS) # ifdef MY_ATOMIC_MODE_DUMMY # define LOCK_prefix "" @@ -22,7 +22,7 @@ # define LOCK_prefix "lock" # endif -# ifdef HAVE_GCC_ATOMIC_BUILTINS +# ifdef MY_ATOMIC_MODE_GCC_BUILTINS # include "gcc_builtins.h" # elif __GNUC__ # include "x86-gcc.h"

4 4

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (psergey:2718)
by Sergey Petrunia 22 Jun '09

22 Jun '09

#At lp:maria based on revid:psergey@askmonty.org-20090617052739-37i1r8lip0m4ft9r 2718 Sergey Petrunia 2009-06-22 MWL#17: Table elimination - Make elimination check to be able detect cases like t.primary_key_col1=othertbl.col AND t.primary_key_col2=func(t.primary_key_col1). These are needed to handle e.g. the case of func() being a correlated subquery that selects the latest value. - If we've removed a condition with subquery predicate, EXPLAIN [EXTENDED] won't show the subquery anymore modified: sql/item.cc sql/item.h sql/item_subselect.cc sql/item_subselect.h sql/item_sum.cc sql/sql_lex.cc sql/sql_lex.h sql/sql_select.cc sql/sql_select.h per-file messages: sql/item.cc MWL#17: Table elimination - Add tem_field::check_column_usage_processor(). it allows to check which key parts a condition depends on. sql/item.h MWL#17: Table elimination - Add tem_field::check_column_usage_processor(). it allows to check which key parts a condition depends on. sql/item_subselect.cc MWL#17: Table elimination - Item_subselect got 'eliminated' attribute. It is used only to determine if the subselect should be printed by EXPLAIN. - Item_subselect got List<Item> refers_to - a list of item in the current select that are referred to from within the subselect. - Added Item_*::check_column_usage_processor(). it allows to check which key parts a condition depends on. - Added a comment about possible problem in Item_subselect::walk sql/item_subselect.h MWL#17: Table elimination - Item_subselect got 'eliminated' attribute. It is used only to determine if the subselect should be printed by EXPLAIN. - Item_subselect got List<Item> refers_to - a list of item in the current select that are referred to from within the subselect. - Added Item_*::check_column_usage_processor(). it allows to check which key parts a condition depends on. sql/item_sum.cc MWL#17: Table elimination sql/sql_lex.cc MWL#17: Table elimination sql/sql_lex.h MWL#17: Table elimination sql/sql_select.cc MWL#17: Table elimination - Make elimination check to be able detect cases like t.primary_key_col1=othertbl.col AND t.primary_key_col2=func(t.primary_key_col1). These are needed to handle e.g. the case of func() being a correlated subquery that selects the latest value. - If we've removed a condition with subquery predicate, EXPLAIN [EXTENDED] won't show the subquery anymore sql/sql_select.h MWL#17: Table elimination === modified file 'sql/item.cc' --- a/sql/item.cc 2009-04-25 10:05:32 +0000 +++ b/sql/item.cc 2009-06-22 11:46:31 +0000 @@ -1915,6 +1915,30 @@ void Item_field::reset_field(Field *f) name= (char*) f->field_name; } +bool Item_field::check_column_usage_processor(uchar *arg) +{ + Field_processor_info* info=(Field_processor_info*)arg; + if (used_tables() & ~info->allowed_tables) + return FALSE; + + if (field->table == info->table) + { + if (!(field->part_of_key.is_set(info->keyno))) + return TRUE; + + KEY *key= &field->table->key_info[info->keyno]; + for (uint part= 0; part < key->key_parts; part++) + { + if (field->field_index == key->key_part[part].field->field_index) + { + info->needed_key_parts |= key_part_map(1) << part; + break; + } + } + } + return FALSE; +} + const char *Item_ident::full_name() const { char *tmp; @@ -3380,7 +3404,7 @@ static void mark_as_dependent(THD *thd, /* store pointer on SELECT_LEX from which item is dependent */ if (mark_item) mark_item->depended_from= last; - current->mark_as_dependent(last); + current->mark_as_dependent(last, resolved_item); if (thd->lex->describe & DESCRIBE_EXTENDED) { char warn_buff[MYSQL_ERRMSG_SIZE]; === modified file 'sql/item.h' --- a/sql/item.h 2009-06-09 21:11:33 +0000 +++ b/sql/item.h 2009-06-22 11:46:31 +0000 @@ -888,6 +888,8 @@ public: virtual bool reset_query_id_processor(uchar *query_id_arg) { return 0; } virtual bool is_expensive_processor(uchar *arg) { return 0; } virtual bool register_field_in_read_map(uchar *arg) { return 0; } + virtual bool check_column_usage_processor(uchar *arg) { return 0; } + virtual bool mark_as_eliminated_processor(uchar *arg) { return 0; } /* Check if a partition function is allowed SYNOPSIS @@ -1012,6 +1014,14 @@ public: }; +typedef struct +{ + table_map allowed_tables; + TABLE *table; + uint keyno; + uint needed_key_parts; +} Field_processor_info; + class sp_head; @@ -1477,6 +1487,7 @@ public: bool find_item_in_field_list_processor(uchar *arg); bool register_field_in_read_map(uchar *arg); bool check_partition_func_processor(uchar *int_arg) {return FALSE;} + bool check_column_usage_processor(uchar *arg); void cleanup(); bool result_as_longlong() { === modified file 'sql/item_subselect.cc' --- a/sql/item_subselect.cc 2009-01-31 21:22:44 +0000 +++ b/sql/item_subselect.cc 2009-06-22 11:46:31 +0000 @@ -39,7 +39,7 @@ inline Item * and_items(Item* cond, Item Item_subselect::Item_subselect(): Item_result_field(), value_assigned(0), thd(0), substitution(0), engine(0), old_engine(0), used_tables_cache(0), have_to_be_excluded(0), - const_item_cache(1), engine_changed(0), changed(0), is_correlated(FALSE) + const_item_cache(1), in_fix_fields(0), engine_changed(0), changed(0), is_correlated(FALSE) { with_subselect= 1; reset(); @@ -151,10 +151,14 @@ bool Item_subselect::fix_fields(THD *thd DBUG_ASSERT(fixed == 0); engine->set_thd((thd= thd_param)); + if (!in_fix_fields) + refers_to.empty(); + eliminated= FALSE; if (check_stack_overrun(thd, STACK_MIN_SIZE, (uchar*)&res)) return TRUE; - + + in_fix_fields++; res= engine->prepare(); // all transformation is done (used by prepared statements) @@ -181,12 +185,14 @@ bool Item_subselect::fix_fields(THD *thd if (!(*ref)->fixed) ret= (*ref)->fix_fields(thd, ref); thd->where= save_where; + in_fix_fields--; return ret; } // Is it one field subselect? if (engine->cols() > max_columns) { my_error(ER_OPERAND_COLUMNS, MYF(0), 1); + in_fix_fields--; return TRUE; } fix_length_and_dec(); @@ -203,11 +209,30 @@ bool Item_subselect::fix_fields(THD *thd fixed= 1; err: + in_fix_fields--; thd->where= save_where; return res; } +bool Item_subselect::check_column_usage_processor(uchar *arg) +{ + List_iterator<Item> it(refers_to); + Item *item; + while ((item= it++)) + { + if (item->walk(&Item::check_column_usage_processor,FALSE, arg)) + return TRUE; + } + return FALSE; +} + +bool Item_subselect::mark_as_eliminated_processor(uchar *arg) +{ + eliminated= TRUE; + return FALSE; +} + bool Item_subselect::walk(Item_processor processor, bool walk_subquery, uchar *argument) { @@ -225,6 +250,7 @@ bool Item_subselect::walk(Item_processor if (lex->having && (lex->having)->walk(processor, walk_subquery, argument)) return 1; + /* TODO: why doesn't this walk the OUTER JOINs' ON expressions */ while ((item=li++)) { === modified file 'sql/item_subselect.h' --- a/sql/item_subselect.h 2008-02-22 10:30:33 +0000 +++ b/sql/item_subselect.h 2009-06-22 11:46:31 +0000 @@ -52,8 +52,16 @@ protected: bool have_to_be_excluded; /* cache of constant state */ bool const_item_cache; - + public: + /* + References from inside the subquery to the select that this predicate is + in. References to parent selects not included. + */ + List<Item> refers_to; + int in_fix_fields; + bool eliminated; + /* changed engine indicator */ bool engine_changed; /* subquery is transformed */ @@ -126,6 +134,8 @@ public: virtual void reset_value_registration() {} enum_parsing_place place() { return parsing_place; } bool walk(Item_processor processor, bool walk_subquery, uchar *arg); + bool mark_as_eliminated_processor(uchar *arg); + bool check_column_usage_processor(uchar *arg); /** Get the SELECT_LEX structure associated with this Item. === modified file 'sql/item_sum.cc' --- a/sql/item_sum.cc 2009-06-09 21:11:33 +0000 +++ b/sql/item_sum.cc 2009-06-22 11:46:31 +0000 @@ -350,7 +350,7 @@ bool Item_sum::register_sum_func(THD *th sl= sl->master_unit()->outer_select() ) sl->master_unit()->item->with_sum_func= 1; } - thd->lex->current_select->mark_as_dependent(aggr_sel); + thd->lex->current_select->mark_as_dependent(aggr_sel, NULL); return FALSE; } === modified file 'sql/sql_lex.cc' --- a/sql/sql_lex.cc 2009-04-25 10:05:32 +0000 +++ b/sql/sql_lex.cc 2009-06-22 11:46:31 +0000 @@ -1778,7 +1778,7 @@ void st_select_lex_unit::exclude_tree() 'last' should be reachable from this st_select_lex_node */ -void st_select_lex::mark_as_dependent(st_select_lex *last) +void st_select_lex::mark_as_dependent(st_select_lex *last, Item *dependency) { /* Mark all selects from resolved to 1 before select where was @@ -1804,6 +1804,8 @@ void st_select_lex::mark_as_dependent(st } is_correlated= TRUE; this->master_unit()->item->is_correlated= TRUE; + if (dependency) + this->master_unit()->item->refers_to.push_back(dependency); } bool st_select_lex_node::set_braces(bool value) { return 1; } === modified file 'sql/sql_lex.h' --- a/sql/sql_lex.h 2009-03-17 20:29:24 +0000 +++ b/sql/sql_lex.h 2009-06-22 11:46:31 +0000 @@ -743,7 +743,7 @@ public: return master_unit()->return_after_parsing(); } - void mark_as_dependent(st_select_lex *last); + void mark_as_dependent(st_select_lex *last, Item *dependency); bool set_braces(bool value); bool inc_in_sum_expr(); === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2009-06-17 05:27:39 +0000 +++ b/sql/sql_select.cc 2009-06-22 11:46:31 +0000 @@ -2478,6 +2478,14 @@ static ha_rows get_quick_record_count(TH } +typedef struct st_keyuse_w_needed_reg +{ + KEYUSE *first; + key_part_map second; + +} Keyuse_w_needed_reg; + +static bool has_eq_ref_access_candidate(TABLE *table, table_map can_refer_to_these) { KEYUSE *keyuse= table->reginfo.join_tab->keyuse; @@ -2494,24 +2502,85 @@ bool has_eq_ref_access_candidate(TABLE * { uint key= keyuse->key; key_part_map bound_parts=0; - bool ft_key= test(keyuse->keypart == FT_KEYPART); - + uint n_unusable=0; + bool ft_key= test(keyuse->keypart == FT_KEYPART); + KEY *keyinfo= table->key_info + key; + KEYUSE *key_start = keyuse; + do /* For each keypart and each way to read it */ { - if (!(keyuse->used_tables & ~can_refer_to_these) && - !(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)) + if (keyuse->usable) { - bound_parts |= keyuse->keypart_map; + if(!(keyuse->used_tables & ~can_refer_to_these) && + !(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)) + { + bound_parts |= keyuse->keypart_map; + } } + else + n_unusable++; keyuse++; - } while (keyuse->table && keyuse->key == key); + } while (keyuse->table == table && keyuse->key == key); + + if (ft_key || ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) + != HA_NOSAME)) + { + continue; + } - KEY *keyinfo= table->key_info + key; - if (!ft_key && - ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME) && - bound_parts == PREV_BITS(key_part_map, keyinfo->key_parts)) - { + if (bound_parts == PREV_BITS(key_part_map, keyinfo->key_parts)) return TRUE; + /* + Ok, usable keyuse elements didn't help us. Try making use of + unusable KEYUSEs (psergey-todo: sane comments:) + */ + if (n_unusable && bound_parts) + { + /* + Check if unusable KEYUSE elements cause all parts of key to be + bound. An unusable keyuse element makes a key part bound when it + represents the following: + + keyXpartY=func(bound_columns, preceding_tables) + + . + */ + Keyuse_w_needed_reg *uses; + if (!(uses= (Keyuse_w_needed_reg*)my_alloca(sizeof(Keyuse_w_needed_reg)*n_unusable))) + return FALSE; + uint n_uses=0; + for (KEYUSE *k= key_start; k!=keyuse; k++) + { + if (!k->usable && !(k->used_tables & ~can_refer_to_these)) + { + //Walk k->val and check which key parts it depends on. + Field_processor_info fp= {can_refer_to_these, table, k->key, 0}; + if (!k->val->walk(&Item::check_column_usage_processor, FALSE, + (uchar*)&fp)) + { + uses[n_uses].first= k; + uses[n_uses].second= fp.needed_key_parts; + n_uses++; + } + } + } + /* Now compute transitive closure */ + uint n_bounded; + do + { + n_bounded= 0; + for (uint i=0; i< n_uses; i++) + { + /* needed_parts is covered by what is already bound*/ + if (!(uses[i].second & ~bound_parts)) + { + bound_parts|= key_part_map(1) << uses[i].first->keypart; + n_bounded++; + } + if (bound_parts == PREV_BITS(key_part_map, keyinfo->key_parts)) + return TRUE; + } + } while (n_bounded != 0); } } } @@ -2657,6 +2726,7 @@ eliminate_tables_for_join_list(JOIN *joi eliminated += tbl->nested_join->join_list.elements; //psergey-todo: do we need to do anything about removing the join //nest? + tbl->on_expr->walk(&Item::mark_as_eliminated_processor, FALSE, NULL); } else { @@ -2673,6 +2743,7 @@ eliminate_tables_for_join_list(JOIN *joi { mark_table_as_eliminated(join, tbl->table, const_tbl_count, const_tables); + tbl->on_expr->walk(&Item::mark_as_eliminated_processor, FALSE, NULL); eliminated += 1; } } @@ -3065,14 +3136,16 @@ make_join_statistics(JOIN *join, TABLE_L { start_keyuse=keyuse; key=keyuse->key; - s->keys.set_bit(key); // QQ: remove this ? + if (keyuse->usable) + s->keys.set_bit(key); // QQ: remove this ? refs=0; const_ref.clear_all(); eq_part.clear_all(); do { - if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize) + if (keyuse->usable && keyuse->val->type() != Item::NULL_ITEM && + !keyuse->optimize) { if (!((~found_const_table_map) & keyuse->used_tables)) const_ref.set_bit(keyuse->keypart); @@ -3276,6 +3349,7 @@ typedef struct key_field_t { */ bool null_rejecting; bool *cond_guard; /* See KEYUSE::cond_guard */ + bool usable; } KEY_FIELD; @@ -3284,6 +3358,26 @@ typedef struct key_field_t { This is called for OR between different levels. + That is, the function operates on an array of KEY_FIELD elements which has + two parts: + + $LEFT_PART $RIGHT_PART + +-----------------------+-----------------------+ + start new_fields end + + $LEFT_PART and $RIGHT_PART are arrays that have KEY_FIELD elements for two + parts of the OR condition. Our task is to produce an array of KEY_FIELD + elements that would correspond to "$LEFT_PART OR $RIGHT_PART". + + The rules for combining elements are as follows: + (keyfieldA1 AND keyfieldA2 AND ...) OR (keyfieldB1 AND keyfieldB2 AND ...)= + AND_ij (keyfieldA_i OR keyfieldB_j) + + We discard all (keyfieldA_i OR keyfieldB_j) that refer to different + fields. For those referring to the same field, the logic is as follows: + + t.keycol= + To be able to do 'ref_or_null' we merge a comparison of a column and 'column IS NULL' to one test. This is useful for sub select queries that are internally transformed to something like:. @@ -3348,13 +3442,18 @@ merge_key_fields(KEY_FIELD *start,KEY_FI KEY_OPTIMIZE_REF_OR_NULL)); old->null_rejecting= (old->null_rejecting && new_fields->null_rejecting); + /* + The conditions are the same, hence their usabilities should + be, too (TODO: shouldn't that apply to the above + null_rejecting and optimize attributes?) + */ + DBUG_ASSERT(old->usable == new_fields->usable); } } else if (old->eq_func && new_fields->eq_func && old->val->eq_by_collation(new_fields->val, old->field->binary(), old->field->charset())) - { old->level= and_level; old->optimize= ((old->optimize & new_fields->optimize & @@ -3363,10 +3462,14 @@ merge_key_fields(KEY_FIELD *start,KEY_FI KEY_OPTIMIZE_REF_OR_NULL)); old->null_rejecting= (old->null_rejecting && new_fields->null_rejecting); + // "t.key_col=const" predicates are always usable + DBUG_ASSERT(old->usable && new_fields->usable); } else if (old->eq_func && new_fields->eq_func && - ((old->val->const_item() && old->val->is_null()) || - new_fields->val->is_null())) + ((new_fields->usable && old->val->const_item() && + old->val->is_null()) || + ((old->usable && new_fields->val->is_null())))) + /* TODO ^ why is the above asymmetric, why const_item()? */ { /* field = expression OR field IS NULL */ old->level= and_level; @@ -3437,6 +3540,7 @@ add_key_field(KEY_FIELD **key_fields,uin table_map usable_tables, SARGABLE_PARAM **sargables) { uint exists_optimize= 0; + bool optimizable=0; if (!(field->flags & PART_KEY_FLAG)) { // Don't remove column IS NULL on a LEFT JOIN table @@ -3449,15 +3553,15 @@ add_key_field(KEY_FIELD **key_fields,uin else { table_map used_tables=0; - bool optimizable=0; for (uint i=0; i<num_values; i++) { used_tables|=(value[i])->used_tables(); if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT))) optimizable=1; } - if (!optimizable) - return; + // psergey-tbl-elim: + // if (!optimizable) + // return; if (!(usable_tables & field->table->map)) { if (!eq_func || (*value)->type() != Item::NULL_ITEM || @@ -3470,7 +3574,8 @@ add_key_field(KEY_FIELD **key_fields,uin JOIN_TAB *stat=field->table->reginfo.join_tab; key_map possible_keys=field->key_start; possible_keys.intersect(field->table->keys_in_use_for_query); - stat[0].keys.merge(possible_keys); // Add possible keys + if (optimizable) + stat[0].keys.merge(possible_keys); // Add possible keys /* Save the following cases: @@ -3563,6 +3668,7 @@ add_key_field(KEY_FIELD **key_fields,uin (*key_fields)->val= *value; (*key_fields)->level= and_level; (*key_fields)->optimize= exists_optimize; + (*key_fields)->usable= optimizable; /* If the condition has form "tbl.keypart = othertbl.field" and othertbl.field can be NULL, there will be no matches if othertbl.field @@ -3874,6 +3980,7 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL; keyuse.null_rejecting= key_field->null_rejecting; keyuse.cond_guard= key_field->cond_guard; + keyuse.usable= key_field->usable; VOID(insert_dynamic(keyuse_array,(uchar*) &keyuse)); } } @@ -3954,6 +4061,11 @@ sort_keyuse(KEYUSE *a,KEYUSE *b) return (int) (a->key - b->key); if (a->keypart != b->keypart) return (int) (a->keypart - b->keypart); + + // Usable ones go before the unusable + if (a->usable != b->usable) + return (int)a->usable - (int)b->usable; + // Place const values before other ones if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) - test((b->used_tables & ~OUTER_REF_TABLE_BIT)))) @@ -4164,7 +4276,8 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR found_eq_constant=0; for (i=0 ; i < keyuse->elements-1 ; i++,use++) { - if (!use->used_tables && use->optimize != KEY_OPTIMIZE_REF_OR_NULL) + if (use->usable && !use->used_tables && + use->optimize != KEY_OPTIMIZE_REF_OR_NULL) use->table->const_key_parts[use->key]|= use->keypart_map; if (use->keypart != FT_KEYPART) { @@ -4188,7 +4301,8 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR /* Save ptr to first use */ if (!use->table->reginfo.join_tab->keyuse) use->table->reginfo.join_tab->keyuse=save_pos; - use->table->reginfo.join_tab->checked_keys.set_bit(use->key); + if (use->usable) + use->table->reginfo.join_tab->checked_keys.set_bit(use->key); save_pos++; } i=(uint) (save_pos-(KEYUSE*) keyuse->buffer); @@ -4218,7 +4332,7 @@ static void optimize_keyuse(JOIN *join, To avoid bad matches, we don't make ref_table_rows less than 100. */ keyuse->ref_table_rows= ~(ha_rows) 0; // If no ref - if (keyuse->used_tables & + if (keyuse->usable && keyuse->used_tables & (map= (keyuse->used_tables & ~join->const_table_map & ~OUTER_REF_TABLE_BIT))) { @@ -4411,7 +4525,8 @@ best_access_path(JOIN *join, if 1. expression doesn't refer to forward tables 2. we won't get two ref-or-null's */ - if (!(remaining_tables & keyuse->used_tables) && + if (keyuse->usable && + !(remaining_tables & keyuse->used_tables) && !(ref_or_null_part && (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))) { @@ -5915,9 +6030,11 @@ static bool create_ref_for_key(JOIN *joi uint i; for (i=0 ; i < keyparts ; keyuse++,i++) { - while (keyuse->keypart != i || - ((~used_tables) & keyuse->used_tables)) + while (keyuse->keypart != i || ((~used_tables) & keyuse->used_tables) || + !keyuse->usable) + { keyuse++; /* Skip other parts */ + } uint maybe_null= test(keyinfo->key_part[i].null_bit); j->ref.items[i]=keyuse->val; // Save for cond removal @@ -16853,8 +16970,11 @@ static void select_describe(JOIN *join, unit; unit= unit->next_unit()) { - if (mysql_explain_union(thd, unit, result)) - DBUG_VOID_RETURN; + if (!(unit->item && unit->item->eliminated)) + { + if (mysql_explain_union(thd, unit, result)) + DBUG_VOID_RETURN; + } } DBUG_VOID_RETURN; } === modified file 'sql/sql_select.h' --- a/sql/sql_select.h 2009-06-14 12:35:04 +0000 +++ b/sql/sql_select.h 2009-06-22 11:46:31 +0000 @@ -51,6 +51,7 @@ typedef struct keyuse_t { NULL - Otherwise (the source equality can't be turned off) */ bool *cond_guard; + bool usable; } KEYUSE; class store_key;

1 0

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (knielsen:2715)
by knielsen＠knielsen-hq.org 22 Jun '09

22 Jun '09

#At lp:maria 2715 knielsen(a)knielsen-hq.org 2009-06-22 More XtraDB after-merge fixes following review and buildbot runs: - Better fix for --innodb-use-sys-malloc causing Valgrind warnings. - Different fix for INNODB_IBUF_MAX_SIZE variable changing default value. - Fix some problems with the safe mutex lazy init patch. modified: mysql-test/include/mtr_check.sql mysql-test/lib/mtr_cases.pm mysql-test/mysql-test-run.pl mysys/thr_mutex.c storage/xtradb/ibuf/ibuf0ibuf.c per-file messages: mysql-test/include/mtr_check.sql Do not check INNODB_IBUF_MAX_SIZE for changes. It is not a dynamic variable, so cannot be changed by a test case anyway, and the value may vary slightly from one start of the server to the next. mysql-test/lib/mtr_cases.pm Even just starting and stopping the server with --innodb-use-sys-malloc to check for disabled test case under valgrind will cause valgrind leak warnings. So add not_valgrind to the list of conditions also tested for directly in mysql-test-run.pl. mysql-test/mysql-test-run.pl Even just starting and stopping the server with --innodb-use-sys-malloc to check for disabled test case under valgrind will cause valgrind leak warnings. So add not_valgrind to the list of conditions also tested for directly in mysql-test-run.pl. mysys/thr_mutex.c Fix a few problems found during review of the lazy init safe mutex patch. storage/xtradb/ibuf/ibuf0ibuf.c Revert previous fix of INNODB_IBUF_MAX_SIZE default varying slightly between server starts. (Fixed instead by ignoring that variable in the test suite). === modified file 'mysql-test/include/mtr_check.sql' --- a/mysql-test/include/mtr_check.sql 2009-02-19 09:01:25 +0000 +++ b/mysql-test/include/mtr_check.sql 2009-06-22 08:06:35 +0000 @@ -12,7 +12,9 @@ BEGIN -- Dump all global variables except those -- that are supposed to change SELECT * FROM INFORMATION_SCHEMA.GLOBAL_VARIABLES - WHERE variable_name != 'timestamp' and variable_name != "debug" order by variable_name; + WHERE variable_name != 'timestamp' AND variable_name != "debug" + AND variable_name != 'INNODB_IBUF_MAX_SIZE' + ORDER BY variable_name; -- Dump all databases, there should be none -- except those that was created during bootstrap === modified file 'mysql-test/lib/mtr_cases.pm' --- a/mysql-test/lib/mtr_cases.pm 2009-03-20 14:39:37 +0000 +++ b/mysql-test/lib/mtr_cases.pm 2009-06-22 08:06:35 +0000 @@ -970,6 +970,16 @@ sub collect_one_test_case { } } + if ( $tinfo->{'not_valgrind'} ) + { + if ( $::opt_valgrind_mysqld ) + { + $tinfo->{'skip'}= 1; + $tinfo->{'comment'}= "Not compatible with Valgrind testing"; + return $tinfo; + } + } + # ---------------------------------------------------------------------- # Find config file to use if not already selected in <testname>.opt file # ---------------------------------------------------------------------- @@ -1050,6 +1060,7 @@ my @tags= ["include/ndb_master-slave.inc", "ndb_test", 1], ["federated.inc", "federated_test", 1], ["include/not_embedded.inc", "not_embedded", 1], + ["include/not_valgrind.inc", "not_valgrind", 1], ); === modified file 'mysql-test/mysql-test-run.pl' --- a/mysql-test/mysql-test-run.pl 2009-06-18 12:39:21 +0000 +++ b/mysql-test/mysql-test-run.pl 2009-06-22 08:06:35 +0000 @@ -224,7 +224,7 @@ my $opt_strace_client; our $opt_user = "root"; my $opt_valgrind= 0; -my $opt_valgrind_mysqld= 0; +our $opt_valgrind_mysqld= 0; my $opt_valgrind_mysqltest= 0; my @default_valgrind_args= ("--show-reachable=yes"); my @valgrind_args; === modified file 'mysys/thr_mutex.c' --- a/mysys/thr_mutex.c 2009-06-09 15:08:46 +0000 +++ b/mysys/thr_mutex.c 2009-06-22 08:06:35 +0000 @@ -160,6 +160,9 @@ static int safe_mutex_lazy_init_deadlock &mp->locked_mutex, sizeof(*mp->locked_mutex), &mp->used_mutex, sizeof(*mp->used_mutex), NullS)) { + /* Disable deadlock handling for this mutex */ + mp->create_flags|= MYF_NO_DEADLOCK_DETECTION; + mp->active_flags|= MYF_NO_DEADLOCK_DETECTION; return 1; /* Error */ } @@ -196,6 +199,9 @@ int safe_mutex_init(safe_mutex_t *mp, mp->line= line; /* Skip the very common '&' prefix from the autogenerated name */ mp->name= name[0] == '&' ? name + 1 : name; + + if (!safe_mutex_deadlock_detector) + my_flags|= MYF_NO_DEADLOCK_DETECTION; /* Deadlock detection is initialised only lazily, on first use. */ mp->create_flags= my_flags; === modified file 'storage/xtradb/ibuf/ibuf0ibuf.c' --- a/storage/xtradb/ibuf/ibuf0ibuf.c 2009-06-09 15:08:46 +0000 +++ b/storage/xtradb/ibuf/ibuf0ibuf.c 2009-06-22 08:06:35 +0000 @@ -422,12 +422,7 @@ ibuf_init_at_db_start(void) grow in size, as the references on the upper levels of the tree can change */ - /* The default for ibuf_max_size is calculated from the requested - buffer pool size srv_buf_pool_size, not the actual size as returned - by buf_pool_get_curr_size(). The latter can differ from the former - by one page due to alignment requirements, and we do not want a - user-visible variable like INNODB_IBUF_MAX_SIZE to vary at random. */ - ibuf->max_size = ut_min( srv_buf_pool_size / UNIV_PAGE_SIZE + ibuf->max_size = ut_min( buf_pool_get_curr_size() / UNIV_PAGE_SIZE / IBUF_POOL_SIZE_PER_MAX_SIZE, (ulint) srv_ibuf_max_size / UNIV_PAGE_SIZE); srv_ibuf_max_size = (long long) ibuf->max_size * UNIV_PAGE_SIZE;

1 0

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (sanja:2712) Bug#41098
by sanja＠askmonty.org 20 Jun '09

20 Jun '09

#At lp:maria 2712 sanja(a)askmonty.org 2009-06-11 Real fix for bug Bug#41098 (http://bugs.mysql.com/bug.php?id=41098) Invalidate tables changed in insert after unlocking tables when the result of insert become really visible. modified: sql/handler.h sql/mysql_priv.h sql/sql_base.cc sql/sql_cache.cc sql/sql_cache.h sql/sql_delete.cc sql/sql_insert.cc sql/sql_load.cc sql/sql_parse.cc sql/sql_partition.cc sql/sql_rename.cc sql/sql_table.cc sql/sql_update.cc sql/sql_view.cc sql/table.h storage/maria/ha_maria.h storage/myisam/ha_myisam.h per-file messages: sql/handler.h table type for nontransactional tables with delayed to unlock insert visibility. sql/mysql_priv.h Invalidate call changed. sql/sql_base.cc Invalidation of marked tables. sql/sql_cache.cc Marking tables for on-unlock-invalidation added. sql/sql_cache.h Invalidate call changed. sql/sql_delete.cc Invalidate call changed. sql/sql_insert.cc Invalidate call changed. sql/sql_load.cc Invalidate call changed. sql/sql_parse.cc Invalidate call changed. sql/sql_partition.cc Invalidate call changed. sql/sql_rename.cc Invalidate call changed. sql/sql_table.cc Invalidate call changed. sql/sql_update.cc Invalidate call changed. sql/sql_view.cc Invalidate call changed. sql/table.h mark for tables which need query cache invalidation on unlock. storage/maria/ha_maria.h MyISAM and maria 1.5 use the new type of table for query cache. storage/myisam/ha_myisam.h MyISAM and maria 1.5 use the new type of table for query cache. === modified file 'sql/handler.h' --- a/sql/handler.h 2009-02-19 09:01:25 +0000 +++ b/sql/handler.h 2009-06-11 12:45:53 +0000 @@ -247,6 +247,11 @@ #define HA_CACHE_TBL_NOCACHE 1 #define HA_CACHE_TBL_ASKTRANSACT 2 #define HA_CACHE_TBL_TRANSACT 4 +/** + Non transactional table but insert results visible for other threads + only on unlock +*/ +#define HA_CACHE_TBL_NTRNS_INS2LOCK 8 /* Options of START TRANSACTION statement (and later of SET TRANSACTION stmt) */ #define MYSQL_START_TRANS_OPT_WITH_CONS_SNAPSHOT 1 === modified file 'sql/mysql_priv.h' --- a/sql/mysql_priv.h 2009-04-25 10:05:32 +0000 +++ b/sql/mysql_priv.h 2009-06-11 12:45:53 +0000 @@ -893,7 +893,7 @@ struct Query_cache_query_flags #define query_cache_init() query_cache.init() #define query_cache_resize(A) query_cache.resize(A) #define query_cache_set_min_res_unit(A) query_cache.set_min_res_unit(A) -#define query_cache_invalidate3(A, B, C) query_cache.invalidate(A, B, C) +#define query_cache_invalidate4(A, B, C, D) query_cache.invalidate(A, B, C, D) #define query_cache_invalidate1(A) query_cache.invalidate(A) #define query_cache_send_result_to_client(A, B, C) \ query_cache.send_result_to_client(A, B, C) @@ -912,7 +912,7 @@ struct Query_cache_query_flags #define query_cache_init() #define query_cache_resize(A) #define query_cache_set_min_res_unit(A) -#define query_cache_invalidate3(A, B, C) +#define query_cache_invalidate4(A, B, C, D) #define query_cache_invalidate1(A) #define query_cache_send_result_to_client(A, B, C) 0 #define query_cache_invalidate_by_MyISAM_filename_ref NULL === modified file 'sql/sql_base.cc' --- a/sql/sql_base.cc 2009-05-19 09:28:05 +0000 +++ b/sql/sql_base.cc 2009-06-11 12:45:53 +0000 @@ -1373,6 +1373,15 @@ bool close_thread_table(THD *thd, TABLE table->s->table_name.str, (long) table)); *table_ptr=table->next; + + /* Invalidate if it has mark about changing in insert + (not all tables has such marks */ + if (table->changed_in_insert) + { + table->changed_in_insert= FALSE; + query_cache_invalidate4(thd, table, FALSE, FALSE); + } + /* When closing a MERGE parent or child table, detach the children first. Clear child table references to force new assignment at next open. === modified file 'sql/sql_cache.cc' --- a/sql/sql_cache.cc 2009-04-25 10:05:32 +0000 +++ b/sql/sql_cache.cc 2009-06-11 12:45:53 +0000 @@ -1542,12 +1542,19 @@ err: } -/* +/** Remove all cached queries that uses any of the tables in the list + + @param thd Thread handler + @param tables_used List of tables used in this operation + @param using_transactions Not in autocommit mode + @param insert It is insert operation + */ void Query_cache::invalidate(THD *thd, TABLE_LIST *tables_used, - my_bool using_transactions) + my_bool using_transactions, + my_bool insert) { DBUG_ENTER("Query_cache::invalidate (table list)"); @@ -1567,6 +1574,15 @@ void Query_cache::invalidate(THD *thd, T force transaction finish. */ thd->add_changed_table(tables_used->table); + else if (insert && + (tables_used->table->file->table_cache_type() == + HA_CACHE_TBL_NTRNS_INS2LOCK)) + { + /* for other threads */ + tables_used->table->changed_in_insert= TRUE; + /* for this thread */ + invalidate_table(thd, tables_used); + } else invalidate_table(thd, tables_used); } @@ -1619,12 +1635,18 @@ void Query_cache::invalidate_locked_for_ DBUG_VOID_RETURN; } -/* +/** Remove all cached queries that uses the given table + + @param thd Thread handler + @param table TABLE descriptor + @param using_transactions Not in autocommit mode + @param insert It is insert operation */ -void Query_cache::invalidate(THD *thd, TABLE *table, - my_bool using_transactions) +void Query_cache::invalidate(THD *thd, TABLE *table, + my_bool using_transactions, + my_bool insert) { DBUG_ENTER("Query_cache::invalidate (table)"); @@ -1633,13 +1655,22 @@ void Query_cache::invalidate(THD *thd, T if (using_transactions && (table->file->table_cache_type() == HA_CACHE_TBL_TRANSACT)) thd->add_changed_table(table); + else if (insert && + (table->file->table_cache_type() == + HA_CACHE_TBL_NTRNS_INS2LOCK)) + { + /* for other threads */ + table->changed_in_insert= TRUE; + /* for this thread */ + invalidate_table(thd, table); + } else invalidate_table(thd, table); - DBUG_VOID_RETURN; } + void Query_cache::invalidate(THD *thd, const char *key, uint32 key_length, my_bool using_transactions) { === modified file 'sql/sql_cache.h' --- a/sql/sql_cache.h 2008-07-24 13:41:55 +0000 +++ b/sql/sql_cache.h 2009-06-11 12:45:53 +0000 @@ -445,10 +445,11 @@ protected: /* Remove all queries that uses any of the listed following tables */ void invalidate(THD* thd, TABLE_LIST *tables_used, - my_bool using_transactions); + my_bool using_transactions, my_bool insert); void invalidate(CHANGED_TABLE_LIST *tables_used); void invalidate_locked_for_write(TABLE_LIST *tables_used); - void invalidate(THD* thd, TABLE *table, my_bool using_transactions); + void invalidate(THD* thd, TABLE *table, + my_bool using_transactions, my_bool insert); void invalidate(THD *thd, const char *key, uint32 key_length, my_bool using_transactions); === modified file 'sql/sql_delete.cc' --- a/sql/sql_delete.cc 2009-04-25 09:04:38 +0000 +++ b/sql/sql_delete.cc 2009-06-11 12:45:53 +0000 @@ -370,7 +370,7 @@ cleanup: */ if (deleted) { - query_cache_invalidate3(thd, table_list, 1); + query_cache_invalidate4(thd, table_list, TRUE, FALSE); } delete select; @@ -783,7 +783,7 @@ void multi_delete::abort() /* Something already deleted so we have to invalidate cache */ if (deleted) - query_cache_invalidate3(thd, delete_tables, 1); + query_cache_invalidate4(thd, delete_tables, TRUE, FALSE); /* If rows from the first table only has been deleted and it is @@ -933,7 +933,7 @@ bool multi_delete::send_eof() */ if (deleted) { - query_cache_invalidate3(thd, delete_tables, 1); + query_cache_invalidate4(thd, delete_tables, TRUE, FALSE); } if ((local_error == 0) || thd->transaction.stmt.modified_non_trans_table) { @@ -1074,7 +1074,7 @@ bool mysql_truncate(THD *thd, TABLE_LIST error= ha_create_table(thd, path, table_list->db, table_list->table_name, &create_info, 1); VOID(pthread_mutex_unlock(&LOCK_open)); - query_cache_invalidate3(thd, table_list, 0); + query_cache_invalidate4(thd, table_list, FALSE, FALSE); end: if (!dont_send_ok) === modified file 'sql/sql_insert.cc' --- a/sql/sql_insert.cc 2009-04-25 10:05:32 +0000 +++ b/sql/sql_insert.cc 2009-06-11 12:45:53 +0000 @@ -880,7 +880,7 @@ bool mysql_insert(THD *thd,TABLE_LIST *t For the transactional algorithm to work the invalidation must be before binlog writing and ha_autocommit_or_rollback */ - query_cache_invalidate3(thd, table_list, 1); + query_cache_invalidate4(thd, table_list, TRUE, TRUE); } if ((changed && error <= 0) || thd->transaction.stmt.modified_non_trans_table || @@ -2743,7 +2743,7 @@ bool Delayed_insert::handle_inserts(void DBUG_PRINT("error", ("HA_EXTRA_NO_CACHE failed in loop")); goto err; } - query_cache_invalidate3(&thd, table, 1); + query_cache_invalidate4(&thd, table, TRUE, TRUE); if (thr_reschedule_write_lock(*thd.lock->locks)) { /* This is not known to happen. */ @@ -2785,7 +2785,7 @@ bool Delayed_insert::handle_inserts(void DBUG_PRINT("error", ("HA_EXTRA_NO_CACHE failed after loop")); goto err; } - query_cache_invalidate3(&thd, table, 1); + query_cache_invalidate4(&thd, table, TRUE, TRUE); pthread_mutex_lock(&mutex); DBUG_RETURN(0); @@ -3208,7 +3208,7 @@ bool select_insert::send_eof() We must invalidate the table in the query cache before binlog writing and ha_autocommit_or_rollback. */ - query_cache_invalidate3(thd, table, 1); + query_cache_invalidate4(thd, table, TRUE, TRUE); if (thd->transaction.stmt.modified_non_trans_table) thd->transaction.all.modified_non_trans_table= TRUE; } @@ -3299,7 +3299,7 @@ void select_insert::abort() { if (!thd->current_stmt_binlog_row_based && !can_rollback_data()) thd->transaction.all.modified_non_trans_table= TRUE; if (changed) - query_cache_invalidate3(thd, table, 1); + query_cache_invalidate4(thd, table, TRUE, TRUE); } DBUG_ASSERT(transactional_table || !changed || thd->transaction.stmt.modified_non_trans_table); === modified file 'sql/sql_load.cc' --- a/sql/sql_load.cc 2009-05-19 09:28:05 +0000 +++ b/sql/sql_load.cc 2009-06-11 12:45:53 +0000 @@ -446,7 +446,7 @@ int mysql_load(THD *thd,sql_exchange *ex We must invalidate the table in query cache before binlog writing and ha_autocommit_... */ - query_cache_invalidate3(thd, table_list, 0); + query_cache_invalidate4(thd, table_list, FALSE, FALSE); if (error) { if (read_file_from_client) === modified file 'sql/sql_parse.cc' --- a/sql/sql_parse.cc 2009-04-25 10:05:32 +0000 +++ b/sql/sql_parse.cc 2009-06-11 12:45:53 +0000 @@ -3211,7 +3211,7 @@ end_with_restore_list: /* INSERT ... SELECT should invalidate only the very first table */ TABLE_LIST *save_table= first_table->next_local; first_table->next_local= 0; - query_cache_invalidate3(thd, first_table, 1); + query_cache_invalidate4(thd, first_table, TRUE, FALSE); first_table->next_local= save_table; } delete sel_result; === modified file 'sql/sql_partition.cc' --- a/sql/sql_partition.cc 2009-02-15 10:58:34 +0000 +++ b/sql/sql_partition.cc 2009-06-11 12:45:53 +0000 @@ -4012,7 +4012,7 @@ static int fast_end_partition(THD *thd, thd->proc_info="end"; if (!is_empty) - query_cache_invalidate3(thd, table_list, 0); + query_cache_invalidate4(thd, table_list, FALSE, FALSE); error= ha_autocommit_or_rollback(thd, 0); if (end_active_trans(thd)) === modified file 'sql/sql_rename.cc' --- a/sql/sql_rename.cc 2008-02-19 12:45:21 +0000 +++ b/sql/sql_rename.cc 2009-06-11 12:45:53 +0000 @@ -182,7 +182,7 @@ bool mysql_rename_tables(THD *thd, TABLE } if (!error) - query_cache_invalidate3(thd, table_list, 0); + query_cache_invalidate4(thd, table_list, FALSE, FALSE); pthread_mutex_lock(&LOCK_open); unlock_table_names(thd, table_list, (TABLE_LIST*) 0); === modified file 'sql/sql_table.cc' --- a/sql/sql_table.cc 2009-06-02 09:58:27 +0000 +++ b/sql/sql_table.cc 2009-06-11 12:45:53 +0000 @@ -1775,7 +1775,7 @@ int mysql_rm_table_part2(THD *thd, TABLE if (some_tables_deleted || tmp_table_deleted || !error) { - query_cache_invalidate3(thd, tables, 0); + query_cache_invalidate4(thd, tables, FALSE, FALSE); if (!dont_log_query) { if (!thd->current_stmt_binlog_row_based || @@ -4372,7 +4372,7 @@ static bool mysql_admin_table(THD* thd, if (thd->killed) goto err; /* Flush entries in the query cache involving this table. */ - query_cache_invalidate3(thd, table->table, 0); + query_cache_invalidate4(thd, table->table, FALSE, FALSE); open_for_modify= 0; } @@ -4628,7 +4628,7 @@ send_result_message: pthread_mutex_unlock(&LOCK_open); } /* May be something modified consequently we have to invalidate cache */ - query_cache_invalidate3(thd, table->table, 0); + query_cache_invalidate4(thd, table->table, FALSE, FALSE); } } ha_autocommit_or_rollback(thd, 0); @@ -5163,7 +5163,7 @@ mysql_discard_or_import_tablespace(THD * The 0 in the call below means 'not in a transaction', which means immediate invalidation; that is probably what we wish here */ - query_cache_invalidate3(thd, table_list, 0); + query_cache_invalidate4(thd, table_list, FALSE, FALSE); /* The ALTER TABLE is always in its own transaction */ error = ha_autocommit_or_rollback(thd, 0); @@ -6433,7 +6433,7 @@ view_err: unlink_open_table(thd, name_lock, FALSE); VOID(pthread_mutex_unlock(&LOCK_open)); table_list->table= NULL; // For query cache - query_cache_invalidate3(thd, table_list, 0); + query_cache_invalidate4(thd, table_list, FALSE, FALSE); DBUG_RETURN(error); } @@ -7097,7 +7097,7 @@ view_err: ha_flush_logs(old_db_type); } table_list->table=0; // For query cache - query_cache_invalidate3(thd, table_list, 0); + query_cache_invalidate4(thd, table_list, FALSE, FALSE); if (thd->locked_tables && (new_name != table_name || new_db != db)) { === modified file 'sql/sql_update.cc' --- a/sql/sql_update.cc 2009-04-25 09:04:38 +0000 +++ b/sql/sql_update.cc 2009-06-11 12:45:53 +0000 @@ -779,7 +779,7 @@ int mysql_update(THD *thd, */ if (updated) { - query_cache_invalidate3(thd, table_list, 1); + query_cache_invalidate4(thd, table_list, TRUE, FALSE); } /* @@ -1780,7 +1780,7 @@ void multi_update::abort() /* Something already updated so we have to invalidate cache */ if (updated) - query_cache_invalidate3(thd, update_tables, 1); + query_cache_invalidate4(thd, update_tables, TRUE, FALSE); /* If all tables that has been updated are trans safe then just do rollback. If not attempt to do remaining updates. @@ -2023,7 +2023,7 @@ bool multi_update::send_eof() if (updated) { - query_cache_invalidate3(thd, update_tables, 1); + query_cache_invalidate4(thd, update_tables, TRUE, FALSE); } /* Write the SQL statement to the binlog if we updated === modified file 'sql/sql_view.cc' --- a/sql/sql_view.cc 2009-04-25 10:05:32 +0000 +++ b/sql/sql_view.cc 2009-06-11 12:45:53 +0000 @@ -667,7 +667,7 @@ bool mysql_create_view(THD *thd, TABLE_L VOID(pthread_mutex_unlock(&LOCK_open)); if (mode != VIEW_CREATE_NEW) - query_cache_invalidate3(thd, view, 0); + query_cache_invalidate4(thd, view, FALSE, FALSE); start_waiting_global_read_lock(thd); if (res) goto err; @@ -1631,7 +1631,7 @@ bool mysql_drop_view(THD *thd, TABLE_LIS pthread_mutex_unlock(&share->mutex); release_table_share(share, RELEASE_WAIT_FOR_DROP); } - query_cache_invalidate3(thd, view, 0); + query_cache_invalidate4(thd, view, FALSE, FALSE); sp_cache_invalidate(); } @@ -1983,7 +1983,7 @@ mysql_rename_view(THD *thd, DBUG_RETURN(1); /* remove cache entries */ - query_cache_invalidate3(thd, view, 0); + query_cache_invalidate4(thd, view, FALSE, FALSE); sp_cache_invalidate(); error= FALSE; === modified file 'sql/table.h' --- a/sql/table.h 2009-02-19 09:01:25 +0000 +++ b/sql/table.h 2009-06-11 12:45:53 +0000 @@ -790,6 +790,7 @@ struct st_table { my_bool get_fields_in_item_tree; /* Signal to fix_field */ /* If MERGE children attached to parent. See top comment in ha_myisammrg.cc */ my_bool children_attached; + my_bool changed_in_insert; /* Have been changed in insert since last lock */ REGINFO reginfo; /* field connections */ MEM_ROOT mem_root; === modified file 'storage/maria/ha_maria.h' --- a/storage/maria/ha_maria.h 2008-12-02 22:02:52 +0000 +++ b/storage/maria/ha_maria.h 2009-06-11 12:45:53 +0000 @@ -164,4 +164,6 @@ public: return file; } static int implicit_commit(THD *thd, bool new_trn); + /** Type of table for caching query */ + virtual uint8 table_cache_type() { return HA_CACHE_TBL_NTRNS_INS2LOCK; } }; === modified file 'storage/myisam/ha_myisam.h' --- a/storage/myisam/ha_myisam.h 2008-06-28 12:45:15 +0000 +++ b/storage/myisam/ha_myisam.h 2009-06-11 12:45:53 +0000 @@ -147,4 +147,6 @@ class ha_myisam: public handler { return file; } + /** Type of table for caching query */ + virtual uint8 table_cache_type() { return HA_CACHE_TBL_NTRNS_INS2LOCK; } };

2 1

[Maria-developers] Updated (by Guest): Using the Valgrind API in mysqld (23)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Using the Valgrind API in mysqld CREATION DATE..: Fri, 22 May 2009, 11:43 SUPERVISOR.....: Psergey IMPLEMENTOR....: Knielsen COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 23 (http://askmonty.org/worklog/?tid=23) VERSION........: Server-9.x STATUS.........: Complete PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 40 (hours remain) ORIG. ESTIMATE.: 40 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 21:35)=-=- Version updated. --- /tmp/wklog.23.old.7421 2009-06-20 21:35:40.000000000 +0300 +++ /tmp/wklog.23.new.7421 2009-06-20 21:35:40.000000000 +0300 @@ -1 +1 @@ -Connector/J-3.2 +Server-9.x -=-=(Guest - Fri, 19 Jun 2009, 20:48)=-=- Version updated. --- /tmp/wklog.23.old.1520 2009-06-19 20:48:56.000000000 +0300 +++ /tmp/wklog.23.new.1520 2009-06-19 20:48:56.000000000 +0300 @@ -1 +1 @@ -GUI-Tools-3.0 +Connector/J-3.2 -=-=(Guest - Fri, 19 Jun 2009, 20:45)=-=- Version updated. --- /tmp/wklog.23.old.1480 2009-06-19 20:45:53.000000000 +0300 +++ /tmp/wklog.23.new.1480 2009-06-19 20:45:53.000000000 +0300 @@ -1 +1 @@ -Connector/.NET-2.0 +GUI-Tools-3.0 -=-=(Guest - Fri, 19 Jun 2009, 20:42)=-=- Version updated. --- /tmp/wklog.23.old.1373 2009-06-19 20:42:48.000000000 +0300 +++ /tmp/wklog.23.new.1373 2009-06-19 20:42:48.000000000 +0300 @@ -1 +1 @@ -WorkLog-3.4 +Connector/.NET-2.0 -=-=(Guest - Fri, 19 Jun 2009, 20:39)=-=- Version updated. --- /tmp/wklog.23.old.1347 2009-06-19 20:39:44.000000000 +0300 +++ /tmp/wklog.23.new.1347 2009-06-19 20:39:44.000000000 +0300 @@ -1 +1 @@ -Server-6.0 +WorkLog-3.4 -=-=(Guest - Fri, 19 Jun 2009, 20:36)=-=- Version updated. --- /tmp/wklog.23.old.1240 2009-06-19 20:36:40.000000000 +0300 +++ /tmp/wklog.23.new.1240 2009-06-19 20:36:40.000000000 +0300 @@ -1 +1 @@ -Connector/J-5.2 +Server-6.0 -=-=(Guest - Fri, 19 Jun 2009, 20:33)=-=- Version updated. --- /tmp/wklog.23.old.1136 2009-06-19 20:33:36.000000000 +0300 +++ /tmp/wklog.23.new.1136 2009-06-19 20:33:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +Connector/J-5.2 -=-=(Guest - Fri, 19 Jun 2009, 20:30)=-=- Version updated. --- /tmp/wklog.23.old.1109 2009-06-19 20:30:32.000000000 +0300 +++ /tmp/wklog.23.new.1109 2009-06-19 20:30:32.000000000 +0300 @@ -1 +1 @@ -Maria-1.0 +Server-5.1 -=-=(Guest - Fri, 19 Jun 2009, 20:27)=-=- Version updated. --- /tmp/wklog.23.old.1004 2009-06-19 20:27:28.000000000 +0300 +++ /tmp/wklog.23.new.1004 2009-06-19 20:27:28.000000000 +0300 @@ -1 +1 @@ -Connector/J-3.1 +Maria-1.0 -=-=(Guest - Fri, 19 Jun 2009, 20:24)=-=- Version updated. --- /tmp/wklog.23.old.907 2009-06-19 20:24:24.000000000 +0300 +++ /tmp/wklog.23.new.907 2009-06-19 20:24:24.000000000 +0300 @@ -1 +1 @@ -Maria-1.1 +Connector/J-3.1 ------------------------------------------------------------ -=-=(View All Progress Notes, 173 total)=-=- http://askmonty.org/worklog/index.pl?tid=23&nolimit=1 DESCRIPTION: Valgrind (the memcheck tool) has some very useful APIs that can be used in mysqld when testing with Valgrind to improve testing and/or debugging: file:///usr/share/doc/valgrind/html/mc-manual.html#mc-manual.clientreqs file:///usr/share/doc/valgrind/html/mc-manual.html#mc-manual.mempools This worklog is about adding configure checks and headers to allow to use these in a way that continues to work on machines where the Valgrind headers or functionality is missing. It also includes adding some basic Valgrind enhancements: - Adding Valgrind annotations to custom memory allocators so that Valgrind can detect leaks, use-before-init, and use-after-free problems also for these allocators. - Adding checks for definedness in appropriate places (eg. when calling libz). HIGH-LEVEL SPECIFICATION: With custom memory allocators, using the Valgrind APIs we can tell Valgrind when a memory block is allocated (so that data read from memory is marked as undefined instead of being defined or not at random depending on prior use); and when a memory block is freed (so that use after freeing can be reported as an error). In some cases cheking for leaks may also be appropriate. Another possibility is to add an explicit check for whether memory is defined. One place this would be useful is when calling libz. Due to the design of that library, Valgrind produces lots of false alarms about using undefined values (I think the issue is that it runs a few bytes off of initialized memory to reduce boundary checks in each loop iteration, then after the loop has checks to avoid using the undefined part of the result). This means we have lots of libz Valgrind suppressions and continue to add more as new warnings surface. So we might easily miss a real problem in this area. This could be improved by adding explicit checks at the call to libz functions that the passed memory is properly defined. Another use is to improve debugging. It is often the case when debugging a warning about using un-initialised memory that the detection happens long after the real problem, the un-initialized value being passed along through the code for a long time before being detected. This makes debugging the problem slow. By adding in strategic places code that asserts that a specific value must be initialised, it is possible to detect problems earlier, speeding up debugging. Such code can be added in more places over time as development and debugging goes on. See also a patch here: http://bugs.mysql.com/bug.php?id=44582 LOW-LEVEL DESIGN: Two places where we call into libz, and where checking for defined parameters would be good: - mysys/my_compress.c - sql/item_strfunc.cc (Item_func_compress). ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Using the Valgrind API in mysqld (23)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Using the Valgrind API in mysqld CREATION DATE..: Fri, 22 May 2009, 11:43 SUPERVISOR.....: Psergey IMPLEMENTOR....: Knielsen COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 23 (http://askmonty.org/worklog/?tid=23) VERSION........: Server-9.x STATUS.........: Complete PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 40 (hours remain) ORIG. ESTIMATE.: 40 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 21:35)=-=- Version updated. --- /tmp/wklog.23.old.7421 2009-06-20 21:35:40.000000000 +0300 +++ /tmp/wklog.23.new.7421 2009-06-20 21:35:40.000000000 +0300 @@ -1 +1 @@ -Connector/J-3.2 +Server-9.x -=-=(Guest - Fri, 19 Jun 2009, 20:48)=-=- Version updated. --- /tmp/wklog.23.old.1520 2009-06-19 20:48:56.000000000 +0300 +++ /tmp/wklog.23.new.1520 2009-06-19 20:48:56.000000000 +0300 @@ -1 +1 @@ -GUI-Tools-3.0 +Connector/J-3.2 -=-=(Guest - Fri, 19 Jun 2009, 20:45)=-=- Version updated. --- /tmp/wklog.23.old.1480 2009-06-19 20:45:53.000000000 +0300 +++ /tmp/wklog.23.new.1480 2009-06-19 20:45:53.000000000 +0300 @@ -1 +1 @@ -Connector/.NET-2.0 +GUI-Tools-3.0 -=-=(Guest - Fri, 19 Jun 2009, 20:42)=-=- Version updated. --- /tmp/wklog.23.old.1373 2009-06-19 20:42:48.000000000 +0300 +++ /tmp/wklog.23.new.1373 2009-06-19 20:42:48.000000000 +0300 @@ -1 +1 @@ -WorkLog-3.4 +Connector/.NET-2.0 -=-=(Guest - Fri, 19 Jun 2009, 20:39)=-=- Version updated. --- /tmp/wklog.23.old.1347 2009-06-19 20:39:44.000000000 +0300 +++ /tmp/wklog.23.new.1347 2009-06-19 20:39:44.000000000 +0300 @@ -1 +1 @@ -Server-6.0 +WorkLog-3.4 -=-=(Guest - Fri, 19 Jun 2009, 20:36)=-=- Version updated. --- /tmp/wklog.23.old.1240 2009-06-19 20:36:40.000000000 +0300 +++ /tmp/wklog.23.new.1240 2009-06-19 20:36:40.000000000 +0300 @@ -1 +1 @@ -Connector/J-5.2 +Server-6.0 -=-=(Guest - Fri, 19 Jun 2009, 20:33)=-=- Version updated. --- /tmp/wklog.23.old.1136 2009-06-19 20:33:36.000000000 +0300 +++ /tmp/wklog.23.new.1136 2009-06-19 20:33:36.000000000 +0300 @@ -1 +1 @@ -Server-5.1 +Connector/J-5.2 -=-=(Guest - Fri, 19 Jun 2009, 20:30)=-=- Version updated. --- /tmp/wklog.23.old.1109 2009-06-19 20:30:32.000000000 +0300 +++ /tmp/wklog.23.new.1109 2009-06-19 20:30:32.000000000 +0300 @@ -1 +1 @@ -Maria-1.0 +Server-5.1 -=-=(Guest - Fri, 19 Jun 2009, 20:27)=-=- Version updated. --- /tmp/wklog.23.old.1004 2009-06-19 20:27:28.000000000 +0300 +++ /tmp/wklog.23.new.1004 2009-06-19 20:27:28.000000000 +0300 @@ -1 +1 @@ -Connector/J-3.1 +Maria-1.0 -=-=(Guest - Fri, 19 Jun 2009, 20:24)=-=- Version updated. --- /tmp/wklog.23.old.907 2009-06-19 20:24:24.000000000 +0300 +++ /tmp/wklog.23.new.907 2009-06-19 20:24:24.000000000 +0300 @@ -1 +1 @@ -Maria-1.1 +Connector/J-3.1 ------------------------------------------------------------ -=-=(View All Progress Notes, 173 total)=-=- http://askmonty.org/worklog/index.pl?tid=23&nolimit=1 DESCRIPTION: Valgrind (the memcheck tool) has some very useful APIs that can be used in mysqld when testing with Valgrind to improve testing and/or debugging: file:///usr/share/doc/valgrind/html/mc-manual.html#mc-manual.clientreqs file:///usr/share/doc/valgrind/html/mc-manual.html#mc-manual.mempools This worklog is about adding configure checks and headers to allow to use these in a way that continues to work on machines where the Valgrind headers or functionality is missing. It also includes adding some basic Valgrind enhancements: - Adding Valgrind annotations to custom memory allocators so that Valgrind can detect leaks, use-before-init, and use-after-free problems also for these allocators. - Adding checks for definedness in appropriate places (eg. when calling libz). HIGH-LEVEL SPECIFICATION: With custom memory allocators, using the Valgrind APIs we can tell Valgrind when a memory block is allocated (so that data read from memory is marked as undefined instead of being defined or not at random depending on prior use); and when a memory block is freed (so that use after freeing can be reported as an error). In some cases cheking for leaks may also be appropriate. Another possibility is to add an explicit check for whether memory is defined. One place this would be useful is when calling libz. Due to the design of that library, Valgrind produces lots of false alarms about using undefined values (I think the issue is that it runs a few bytes off of initialized memory to reduce boundary checks in each loop iteration, then after the loop has checks to avoid using the undefined part of the result). This means we have lots of libz Valgrind suppressions and continue to add more as new warnings surface. So we might easily miss a real problem in this area. This could be improved by adding explicit checks at the call to libz functions that the passed memory is properly defined. Another use is to improve debugging. It is often the case when debugging a warning about using un-initialised memory that the detection happens long after the real problem, the un-initialized value being passed along through the code for a long time before being detected. This makes debugging the problem slow. By adding in strategic places code that asserts that a specific value must be initialised, it is possible to detect problems earlier, speeding up debugging. Such code can be added in more places over time as development and debugging goes on. See also a patch here: http://bugs.mysql.com/bug.php?id=44582 LOW-LEVEL DESIGN: Two places where we call into libz, and where checking for defined parameters would be good: - mysys/my_compress.c - sql/item_strfunc.cc (Item_func_compress). ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Better choice between range and index_merge/intersection options (26)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Better choice between range and index_merge/intersection options CREATION DATE..: Wed, 27 May 2009, 15:20 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 26 (http://askmonty.org/worklog/?tid=26) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 09:39)=-=- High-Level Specification modified. --- /tmp/wklog.26.old.21828 2009-06-20 09:39:25.000000000 +0300 +++ /tmp/wklog.26.new.21828 2009-06-20 09:39:25.000000000 +0300 @@ -1 +1,9 @@ +* Not a spec but rather preliminary notes* +User cases +---------- + +* BUG#32254: Index merge used unnecessarily +* BUG#34869: Almost 300% regression in index merge intersect performance +* BUG#40051: needed way to prevent optimizer from using index_merge on useless +keys (no testcase) -=-=(Guest - Sat, 13 Jun 2009, 06:51)=-=- Category updated. --- /tmp/wklog.26.old.26624 2009-06-13 06:51:56.000000000 +0300 +++ /tmp/wklog.26.new.26624 2009-06-13 06:51:56.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:06)=-=- Category updated. --- /tmp/wklog.26.old.24784 2009-06-13 06:06:28.000000000 +0300 +++ /tmp/wklog.26.new.24784 2009-06-13 06:06:28.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 26 DESCRIPTION: The optimizer does a cost-based choice between possible range and index_merge/intersection scans. There are some issues with it: - index_merge/intersection gets chosen even when there is a single multi-part index that covers all keys. Measurements show that this is a poor choice. - The picked index_merge/intersection can use a redundant set of indexes: it will be intersect(idx1, ..., idxN) where all columns in idxN are covered by other used indexes. This WL is to fix these limitations. HIGH-LEVEL SPECIFICATION: * Not a spec but rather preliminary notes* User cases ---------- * BUG#32254: Index merge used unnecessarily * BUG#34869: Almost 300% regression in index merge intersect performance * BUG#40051: needed way to prevent optimizer from using index_merge on useless keys (no testcase) ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): Better choice between range and index_merge/intersection options (26)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Better choice between range and index_merge/intersection options CREATION DATE..: Wed, 27 May 2009, 15:20 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 26 (http://askmonty.org/worklog/?tid=26) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 09:39)=-=- High-Level Specification modified. --- /tmp/wklog.26.old.21828 2009-06-20 09:39:25.000000000 +0300 +++ /tmp/wklog.26.new.21828 2009-06-20 09:39:25.000000000 +0300 @@ -1 +1,9 @@ +* Not a spec but rather preliminary notes* +User cases +---------- + +* BUG#32254: Index merge used unnecessarily +* BUG#34869: Almost 300% regression in index merge intersect performance +* BUG#40051: needed way to prevent optimizer from using index_merge on useless +keys (no testcase) -=-=(Guest - Sat, 13 Jun 2009, 06:51)=-=- Category updated. --- /tmp/wklog.26.old.26624 2009-06-13 06:51:56.000000000 +0300 +++ /tmp/wklog.26.new.26624 2009-06-13 06:51:56.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:06)=-=- Category updated. --- /tmp/wklog.26.old.24784 2009-06-13 06:06:28.000000000 +0300 +++ /tmp/wklog.26.new.24784 2009-06-13 06:06:28.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 26 DESCRIPTION: The optimizer does a cost-based choice between possible range and index_merge/intersection scans. There are some issues with it: - index_merge/intersection gets chosen even when there is a single multi-part index that covers all keys. Measurements show that this is a poor choice. - The picked index_merge/intersection can use a redundant set of indexes: it will be intersect(idx1, ..., idxN) where all columns in idxN are covered by other used indexes. This WL is to fix these limitations. HIGH-LEVEL SPECIFICATION: * Not a spec but rather preliminary notes* User cases ---------- * BUG#32254: Index merge used unnecessarily * BUG#34869: Almost 300% regression in index merge intersect performance * BUG#40051: needed way to prevent optimizer from using index_merge on useless keys (no testcase) ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): index_merge: fair choice between index_merge union and range access (24)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: index_merge: fair choice between index_merge union and range access CREATION DATE..: Tue, 26 May 2009, 12:10 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 24 (http://askmonty.org/worklog/?tid=24) VERSION........: 9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 09:34)=-=- Low Level Design modified. --- /tmp/wklog.24.old.21663 2009-06-20 09:34:48.000000000 +0300 +++ /tmp/wklog.24.new.21663 2009-06-20 09:34:48.000000000 +0300 @@ -4,6 +4,7 @@ 2. New implementation 2.1 New tree_and() 2.2 New tree_or() +3. Testing and required coverage </contents> 1. Current implementation overview @@ -240,3 +241,14 @@ In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. + +3. Testing and required coverage +================================ +So far could find the following user cases: + +* BUG#17259: Query optimizer chooses wrong index +* BUG#17673: Optimizer does not use Index Merge optimization in some cases +* BUG#23322: Optimizer sometimes erroniously prefers other index over index merge +* BUG#30151: optimizer is very reluctant to chose index_merge algorithm + + -=-=(Guest - Thu, 18 Jun 2009, 16:55)=-=- Low Level Design modified. --- /tmp/wklog.24.old.19152 2009-06-18 16:55:00.000000000 +0300 +++ /tmp/wklog.24.new.19152 2009-06-18 16:55:00.000000000 +0300 @@ -141,13 +141,15 @@ Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: + 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: -1. Don't remove index_merge part of the tree. +A1. Don't remove index_merge part of the tree (this will take care of + DISCARD-IMERGE-1 problem) -2. Push range conditions down into index_merge trees that may support them. +A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: @@ -155,8 +157,86 @@ (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) -3. Just as before: if both sel_tree A and sel_tree B have index_merge options, +A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. -2.2 New tree_or() +2.2 New tree_or() +----------------- +O1. Dont remove non-range plans: + Current tree_or() code will refuse to produce index_merge plans for + conditions like + + "t.key1part2=const OR t.key2part1=const" + + (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of + the AND condition is not usable for range access, and the operation of + tree_and() guaranteed that there was no way it could changed to make a + usable range plan. With new tree_and() and rule A2, this is no longer the + case. For example for this query: + + (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const + + it will construct a + + imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) + + then tree_and() will apply rule A2 to push the range down into index merge + and after that we'll have: + + range(t.key1part1=const) + imerge( + t.key1part2=const AND t.key1part1=const, + t.key2part1=const + ) + note that imerge(...) describes a usable index_merge plan and it's possible + that it will be the best access path. + +O2. "Create index_merge accesses when possible" + Current tree_or() will not create index_merge access when it could create + non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems + in the current implementation" section). This will be changed to work as + follows: we will create index_merge made for index scans that didn't have + their match in the other sel_tree. + Ilustrating it with an example: + + | sel_tree_A | sel_tree_B | A or B | include in index_merge? + ------+------------+------------+--------+------------------------ + key1 | cond1 | cond2 | condM | no + key2 | cond3 | cond4 | NULL | no + key3 | cond5 | | | yes, A-side + key4 | cond6 | | | yes, A-side + key5 | | cond7 | | yes, B-side + key6 | | cond8 | | yes, B-side + + here we assume that + - (cond1 OR cond2) did produce a combined range. Not including them in + index_merge. + - (cond3 OR cond4) didn't produce a usable range (e.g. they were + t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them + didn't yield any range list) + - All other scand didn't have their counterparts, so we'll end up with a + SEL_TREE of: + + range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) + . + +O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is +that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven +seen any complaints that could be attributed to it. +If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to +lift it ,and produce a cross-product: + + ((key1p OR key2p) AND (key3p OR key4p)) + OR + ((key5p OR key6p) AND (key7p OR key8p)) + + = (key1p OR key2p OR key5p OR key6p) AND // this part is currently + (key3p OR key4p OR key5p OR key6p) AND // produced + + (key1p OR key2p OR key5p OR key6p) AND // this part will be added + (key3p OR key4p OR key5p OR key6p) //. + +In order to limit the impact of this combinatorial explosion, we will +introduce a rule that we won't generate more than #defined +MAX_IMERGE_OPTS options. -=-=(Guest - Thu, 18 Jun 2009, 14:56)=-=- Low Level Design modified. --- /tmp/wklog.24.old.15612 2009-06-18 14:56:09.000000000 +0300 +++ /tmp/wklog.24.new.15612 2009-06-18 14:56:09.000000000 +0300 @@ -1 +1,162 @@ +<contents> +1. Current implementation overview +1.1. Problems in the current implementation +2. New implementation +2.1 New tree_and() +2.2 New tree_or() +</contents> + +1. Current implementation overview +================================== +At the moment, range analyzer works as follows: + +SEL_TREE structure represents + + # There are sel_trees, a sel_tree is either range or merge tree + sel_tree = range_tree | imerge_tree + + # a range tree has range access options, possibly for several keys + range_tree = range(key1) AND range(key2) AND ... AND range(keyN); + + # merge tree represents several way to index_merge + imerge_tree = imerge1 AND imerge2 AND ... + + # a way to do index merge == a set to use of different indexes. + imergeX = range_tree1 OR range_tree2 OR .. + where no pair of range_treeX have ranges over the same index. + + + tree_and(A, B) + { + if (both A and B are range trees) + return a range_tree with computed intersection for each range; + if (only one of A and B is a range tree) + return that tree; // DISCARD-IMERGE-1 + // at this point both trees are index_merge trees + return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); + } + + + tree_or(A, B) + { + if (A and B are range trees) + { + R = new range_tree; + for each index i + R.add(range_union(A.range(i), B.range(i))); + + if (R has at least one range access) + return R; + else + { + /* could not build any range accesses. construct index_merge */ + remove non-ranges from A; // DISCARD-IMERGE-2 + remove non-ranges from B; + return new index_merge(A, B); + } + } + else if (A is range tree and B is index_merge tree (or vice versa)) + { + Perform this transformation: + + range_treeA // this is A + OR + (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND + (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND + ... + (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND + = + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND + ... + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + + Now each line represents an index_merge.. + } + else if (both A and B are index_merge trees) + { + Perform this transformation: + + imergeA1 AND imergeA2 AND ... AND imergeAN + OR + imergeB1 AND imergeB2 AND ... AND imergeBN + + -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 + + imergeA1 + OR + imergeB1 AND imergeB2 AND ... AND imergeBN = + + = (combine imergeA1 with each of the imergeB{i} ) = + + combine(imergeA1 OR imergeB1) AND + combine(imergeA1 OR imergeB2) AND + ... AND + combine(imergeA1 OR imergeBN) + } + } + +1.1. Problems in the current implementation +------------------------------------------- +As marked in the code above: + +DISCARD-IMERGE-1 step will cause index_merge option to be discarded when +the WHERE clause has this form: + + (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 + +DISCARD-IMERGE-2 step will cause index_merge option to be discarded when +the WHERE clause has this form (conditions t.badkey may have abritrary form): + + (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) + +DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are +two indexes: + + INDEX i1(col1, col2), + INDEX i2(col1, col3) + +and this WHERE clause: + + col1=c1 AND (col2=c2 OR col3=c3) + +The optimizer will generate the plans that only use the "col1=c1" part. The +right side of the AND will be ignored even if it has good selectivity. + + +2. New implementation +===================== + +<general idea> +* Don't start fighting combinatorial explosion until we've actually got one. +</> + +SEL_TREE structure will be now able to hold both index_merge and range scan +candidates at the same time. That is, + + sel_tree2 = range_tree AND imerge_tree + +where both parts are optional (i.e. can be empty) + +Operations on SEL_ARG trees will be modified to produce/process the trees of +this kind: + +2.1 New tree_and() +------------------ +In order not to lose plans, we'll make these changes: + +1. Don't remove index_merge part of the tree. + +2. Push range conditions down into index_merge trees that may support them. + if one tree has range(key1) and the other tree has imerge(key1 OR key2) + then perform an equvalent of this operation: + + rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = + + (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) + +3. Just as before: if both sel_tree A and sel_tree B have index_merge options, + concatenate them together. + +2.2 New tree_or() -=-=(Guest - Sat, 13 Jun 2009, 06:29)=-=- Category updated. --- /tmp/wklog.24.old.25753 2009-06-13 06:29:10.000000000 +0300 +++ /tmp/wklog.24.new.25753 2009-06-13 06:29:10.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:14)=-=- Category updated. --- /tmp/wklog.24.old.24991 2009-06-13 06:14:03.000000000 +0300 +++ /tmp/wklog.24.new.24991 2009-06-13 06:14:03.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 24 -=-=(Guest - Mon, 01 Jun 2009, 23:30)=-=- High-Level Specification modified. --- /tmp/wklog.24.old.21580 2009-06-01 23:30:06.000000000 +0300 +++ /tmp/wklog.24.new.21580 2009-06-01 23:30:06.000000000 +0300 @@ -64,6 +64,9 @@ * How strict is the limitation on the form of the WHERE? +* Which version should this be based on? 5.1? Which patches are should be in + (google's/percona's/maria/etc?) + * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Category updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Client-BackLog +Server-RawIdeaBin -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Version updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Server-9.x +9.x -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Title modified. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -index_merge optimizer: dont discard index_merge union strategies when range is available +index_merge: fair choice between index_merge union and range access ------------------------------------------------------------ -=-=(View All Progress Notes, 12 total)=-=- http://askmonty.org/worklog/index.pl?tid=24&nolimit=1 DESCRIPTION: Current range optimizer will discard possible index_merge/[sort]union strategies when there is a possible range plan. This action is a part of measures we take to avoid combinatorial explosion of possible range/ index_merge strategies. A bad side effect of this is that for WHERE clauses in form t.key1= 'very-frequent-value' AND (t.key2='rare-value1' OR t.key3='rare-value2') the optimizer will - discard union(key2,key3) in favor of range(key1) - consider costs of using range(key1) and discard that plan also and the overall effect is that possible poor range access will cause possible good index_merge access not to be considered. This WL is to about lifting this limitation at least for some subset of WHERE clauses. HIGH-LEVEL SPECIFICATION: (Not a ready HLS but draft) <contents> Solution overview Limitations TODO </contents> Solution overview ================= The idea is to delay discarding potential index_merge plans until the point where it is really necessary. This way, we won't have to do much changes in the range analyzer, but will be able to keep potential index_merge plan just enough so that it's possible to take it into consideration together with range access plans. Since there are no changes in the optimizer, the ability to consider both range and index_merge options will be limited to WHERE clauses of this form: WHERE := range_cond(key1_1) AND range_cond(key2_1) AND other_cond AND index_merge_OR_cond1(key3_1, key3_2, ...) index_merge_OR_cond2(key4_1, key4_2, ...) where index_merge_OR_cond{N} := (range_cond(keyN_1) OR range_cond(keyN_2) OR ...) range_cond(keyX) := condition that allows to construct range access of keyX and doesn't allow to construct range/index_merge accesses for any keys of the table in question. For such WHERE clauses, the range analyzer will produce SEL_TREE of this form: SEL_TREE( range(key1_1), ... range(key2_1), SEL_IMERGE( (1) SEL_TREE(key3_1}) SEL_TREE(key3_2}) ... ) ... ) which can be used to make a cost-based choice between range and index_merge. Limitations ----------- This will not be a full solution in a sense that the range analyzer will not be able to produce sel_tree (1) if the WHERE clause is specified in other form (e.g. brackets were opened). TODO ---- * is it a problem if there are keys that are referred to both from index_merge and from range access? * How strict is the limitation on the form of the WHERE? * Which version should this be based on? 5.1? Which patches are should be in (google's/percona's/maria/etc?) * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? LOW-LEVEL DESIGN: <contents> 1. Current implementation overview 1.1. Problems in the current implementation 2. New implementation 2.1 New tree_and() 2.2 New tree_or() 3. Testing and required coverage </contents> 1. Current implementation overview ================================== At the moment, range analyzer works as follows: SEL_TREE structure represents # There are sel_trees, a sel_tree is either range or merge tree sel_tree = range_tree | imerge_tree # a range tree has range access options, possibly for several keys range_tree = range(key1) AND range(key2) AND ... AND range(keyN); # merge tree represents several way to index_merge imerge_tree = imerge1 AND imerge2 AND ... # a way to do index merge == a set to use of different indexes. imergeX = range_tree1 OR range_tree2 OR .. where no pair of range_treeX have ranges over the same index. tree_and(A, B) { if (both A and B are range trees) return a range_tree with computed intersection for each range; if (only one of A and B is a range tree) return that tree; // DISCARD-IMERGE-1 // at this point both trees are index_merge trees return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); } tree_or(A, B) { if (A and B are range trees) { R = new range_tree; for each index i R.add(range_union(A.range(i), B.range(i))); if (R has at least one range access) return R; else { /* could not build any range accesses. construct index_merge */ remove non-ranges from A; // DISCARD-IMERGE-2 remove non-ranges from B; return new index_merge(A, B); } } else if (A is range tree and B is index_merge tree (or vice versa)) { Perform this transformation: range_treeA // this is A OR (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND ... (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND = (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND ... (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND Now each line represents an index_merge.. } else if (both A and B are index_merge trees) { Perform this transformation: imergeA1 AND imergeA2 AND ... AND imergeAN OR imergeB1 AND imergeB2 AND ... AND imergeBN -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 imergeA1 OR imergeB1 AND imergeB2 AND ... AND imergeBN = = (combine imergeA1 with each of the imergeB{i} ) = combine(imergeA1 OR imergeB1) AND combine(imergeA1 OR imergeB2) AND ... AND combine(imergeA1 OR imergeBN) } } 1.1. Problems in the current implementation ------------------------------------------- As marked in the code above: DISCARD-IMERGE-1 step will cause index_merge option to be discarded when the WHERE clause has this form: (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 DISCARD-IMERGE-2 step will cause index_merge option to be discarded when the WHERE clause has this form (conditions t.badkey may have abritrary form): (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are two indexes: INDEX i1(col1, col2), INDEX i2(col1, col3) and this WHERE clause: col1=c1 AND (col2=c2 OR col3=c3) The optimizer will generate the plans that only use the "col1=c1" part. The right side of the AND will be ignored even if it has good selectivity. 2. New implementation ===================== <general idea> * Don't start fighting combinatorial explosion until we've actually got one. </> SEL_TREE structure will be now able to hold both index_merge and range scan candidates at the same time. That is, sel_tree2 = range_tree AND imerge_tree where both parts are optional (i.e. can be empty) Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: A1. Don't remove index_merge part of the tree (this will take care of DISCARD-IMERGE-1 problem) A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. 2.2 New tree_or() ----------------- O1. Dont remove non-range plans: Current tree_or() code will refuse to produce index_merge plans for conditions like "t.key1part2=const OR t.key2part1=const" (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of the AND condition is not usable for range access, and the operation of tree_and() guaranteed that there was no way it could changed to make a usable range plan. With new tree_and() and rule A2, this is no longer the case. For example for this query: (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const it will construct a imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) then tree_and() will apply rule A2 to push the range down into index merge and after that we'll have: range(t.key1part1=const) imerge( t.key1part2=const AND t.key1part1=const, t.key2part1=const ) note that imerge(...) describes a usable index_merge plan and it's possible that it will be the best access path. O2. "Create index_merge accesses when possible" Current tree_or() will not create index_merge access when it could create non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems in the current implementation" section). This will be changed to work as follows: we will create index_merge made for index scans that didn't have their match in the other sel_tree. Ilustrating it with an example: | sel_tree_A | sel_tree_B | A or B | include in index_merge? ------+------------+------------+--------+------------------------ key1 | cond1 | cond2 | condM | no key2 | cond3 | cond4 | NULL | no key3 | cond5 | | | yes, A-side key4 | cond6 | | | yes, A-side key5 | | cond7 | | yes, B-side key6 | | cond8 | | yes, B-side here we assume that - (cond1 OR cond2) did produce a combined range. Not including them in index_merge. - (cond3 OR cond4) didn't produce a usable range (e.g. they were t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them didn't yield any range list) - All other scand didn't have their counterparts, so we'll end up with a SEL_TREE of: range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) . O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven seen any complaints that could be attributed to it. If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to lift it ,and produce a cross-product: ((key1p OR key2p) AND (key3p OR key4p)) OR ((key5p OR key6p) AND (key7p OR key8p)) = (key1p OR key2p OR key5p OR key6p) AND // this part is currently (key3p OR key4p OR key5p OR key6p) AND // produced (key1p OR key2p OR key5p OR key6p) AND // this part will be added (key3p OR key4p OR key5p OR key6p) //. In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. 3. Testing and required coverage ================================ So far could find the following user cases: * BUG#17259: Query optimizer chooses wrong index * BUG#17673: Optimizer does not use Index Merge optimization in some cases * BUG#23322: Optimizer sometimes erroniously prefers other index over index merge * BUG#30151: optimizer is very reluctant to chose index_merge algorithm ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0

[Maria-developers] Updated (by Guest): index_merge: fair choice between index_merge union and range access (24)
by worklog-noreply＠askmonty.org 20 Jun '09

20 Jun '09

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: index_merge: fair choice between index_merge union and range access CREATION DATE..: Tue, 26 May 2009, 12:10 SUPERVISOR.....: Monty IMPLEMENTOR....: Psergey COPIES TO......: Psergey CATEGORY.......: Server-Sprint TASK ID........: 24 (http://askmonty.org/worklog/?tid=24) VERSION........: 9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: -=-=(Guest - Sat, 20 Jun 2009, 09:34)=-=- Low Level Design modified. --- /tmp/wklog.24.old.21663 2009-06-20 09:34:48.000000000 +0300 +++ /tmp/wklog.24.new.21663 2009-06-20 09:34:48.000000000 +0300 @@ -4,6 +4,7 @@ 2. New implementation 2.1 New tree_and() 2.2 New tree_or() +3. Testing and required coverage </contents> 1. Current implementation overview @@ -240,3 +241,14 @@ In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. + +3. Testing and required coverage +================================ +So far could find the following user cases: + +* BUG#17259: Query optimizer chooses wrong index +* BUG#17673: Optimizer does not use Index Merge optimization in some cases +* BUG#23322: Optimizer sometimes erroniously prefers other index over index merge +* BUG#30151: optimizer is very reluctant to chose index_merge algorithm + + -=-=(Guest - Thu, 18 Jun 2009, 16:55)=-=- Low Level Design modified. --- /tmp/wklog.24.old.19152 2009-06-18 16:55:00.000000000 +0300 +++ /tmp/wklog.24.new.19152 2009-06-18 16:55:00.000000000 +0300 @@ -141,13 +141,15 @@ Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: + 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: -1. Don't remove index_merge part of the tree. +A1. Don't remove index_merge part of the tree (this will take care of + DISCARD-IMERGE-1 problem) -2. Push range conditions down into index_merge trees that may support them. +A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: @@ -155,8 +157,86 @@ (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) -3. Just as before: if both sel_tree A and sel_tree B have index_merge options, +A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. -2.2 New tree_or() +2.2 New tree_or() +----------------- +O1. Dont remove non-range plans: + Current tree_or() code will refuse to produce index_merge plans for + conditions like + + "t.key1part2=const OR t.key2part1=const" + + (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of + the AND condition is not usable for range access, and the operation of + tree_and() guaranteed that there was no way it could changed to make a + usable range plan. With new tree_and() and rule A2, this is no longer the + case. For example for this query: + + (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const + + it will construct a + + imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) + + then tree_and() will apply rule A2 to push the range down into index merge + and after that we'll have: + + range(t.key1part1=const) + imerge( + t.key1part2=const AND t.key1part1=const, + t.key2part1=const + ) + note that imerge(...) describes a usable index_merge plan and it's possible + that it will be the best access path. + +O2. "Create index_merge accesses when possible" + Current tree_or() will not create index_merge access when it could create + non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems + in the current implementation" section). This will be changed to work as + follows: we will create index_merge made for index scans that didn't have + their match in the other sel_tree. + Ilustrating it with an example: + + | sel_tree_A | sel_tree_B | A or B | include in index_merge? + ------+------------+------------+--------+------------------------ + key1 | cond1 | cond2 | condM | no + key2 | cond3 | cond4 | NULL | no + key3 | cond5 | | | yes, A-side + key4 | cond6 | | | yes, A-side + key5 | | cond7 | | yes, B-side + key6 | | cond8 | | yes, B-side + + here we assume that + - (cond1 OR cond2) did produce a combined range. Not including them in + index_merge. + - (cond3 OR cond4) didn't produce a usable range (e.g. they were + t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them + didn't yield any range list) + - All other scand didn't have their counterparts, so we'll end up with a + SEL_TREE of: + + range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) + . + +O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is +that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven +seen any complaints that could be attributed to it. +If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to +lift it ,and produce a cross-product: + + ((key1p OR key2p) AND (key3p OR key4p)) + OR + ((key5p OR key6p) AND (key7p OR key8p)) + + = (key1p OR key2p OR key5p OR key6p) AND // this part is currently + (key3p OR key4p OR key5p OR key6p) AND // produced + + (key1p OR key2p OR key5p OR key6p) AND // this part will be added + (key3p OR key4p OR key5p OR key6p) //. + +In order to limit the impact of this combinatorial explosion, we will +introduce a rule that we won't generate more than #defined +MAX_IMERGE_OPTS options. -=-=(Guest - Thu, 18 Jun 2009, 14:56)=-=- Low Level Design modified. --- /tmp/wklog.24.old.15612 2009-06-18 14:56:09.000000000 +0300 +++ /tmp/wklog.24.new.15612 2009-06-18 14:56:09.000000000 +0300 @@ -1 +1,162 @@ +<contents> +1. Current implementation overview +1.1. Problems in the current implementation +2. New implementation +2.1 New tree_and() +2.2 New tree_or() +</contents> + +1. Current implementation overview +================================== +At the moment, range analyzer works as follows: + +SEL_TREE structure represents + + # There are sel_trees, a sel_tree is either range or merge tree + sel_tree = range_tree | imerge_tree + + # a range tree has range access options, possibly for several keys + range_tree = range(key1) AND range(key2) AND ... AND range(keyN); + + # merge tree represents several way to index_merge + imerge_tree = imerge1 AND imerge2 AND ... + + # a way to do index merge == a set to use of different indexes. + imergeX = range_tree1 OR range_tree2 OR .. + where no pair of range_treeX have ranges over the same index. + + + tree_and(A, B) + { + if (both A and B are range trees) + return a range_tree with computed intersection for each range; + if (only one of A and B is a range tree) + return that tree; // DISCARD-IMERGE-1 + // at this point both trees are index_merge trees + return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); + } + + + tree_or(A, B) + { + if (A and B are range trees) + { + R = new range_tree; + for each index i + R.add(range_union(A.range(i), B.range(i))); + + if (R has at least one range access) + return R; + else + { + /* could not build any range accesses. construct index_merge */ + remove non-ranges from A; // DISCARD-IMERGE-2 + remove non-ranges from B; + return new index_merge(A, B); + } + } + else if (A is range tree and B is index_merge tree (or vice versa)) + { + Perform this transformation: + + range_treeA // this is A + OR + (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND + (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND + ... + (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND + = + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND + ... + (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND + + Now each line represents an index_merge.. + } + else if (both A and B are index_merge trees) + { + Perform this transformation: + + imergeA1 AND imergeA2 AND ... AND imergeAN + OR + imergeB1 AND imergeB2 AND ... AND imergeBN + + -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 + + imergeA1 + OR + imergeB1 AND imergeB2 AND ... AND imergeBN = + + = (combine imergeA1 with each of the imergeB{i} ) = + + combine(imergeA1 OR imergeB1) AND + combine(imergeA1 OR imergeB2) AND + ... AND + combine(imergeA1 OR imergeBN) + } + } + +1.1. Problems in the current implementation +------------------------------------------- +As marked in the code above: + +DISCARD-IMERGE-1 step will cause index_merge option to be discarded when +the WHERE clause has this form: + + (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 + +DISCARD-IMERGE-2 step will cause index_merge option to be discarded when +the WHERE clause has this form (conditions t.badkey may have abritrary form): + + (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) + +DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are +two indexes: + + INDEX i1(col1, col2), + INDEX i2(col1, col3) + +and this WHERE clause: + + col1=c1 AND (col2=c2 OR col3=c3) + +The optimizer will generate the plans that only use the "col1=c1" part. The +right side of the AND will be ignored even if it has good selectivity. + + +2. New implementation +===================== + +<general idea> +* Don't start fighting combinatorial explosion until we've actually got one. +</> + +SEL_TREE structure will be now able to hold both index_merge and range scan +candidates at the same time. That is, + + sel_tree2 = range_tree AND imerge_tree + +where both parts are optional (i.e. can be empty) + +Operations on SEL_ARG trees will be modified to produce/process the trees of +this kind: + +2.1 New tree_and() +------------------ +In order not to lose plans, we'll make these changes: + +1. Don't remove index_merge part of the tree. + +2. Push range conditions down into index_merge trees that may support them. + if one tree has range(key1) and the other tree has imerge(key1 OR key2) + then perform an equvalent of this operation: + + rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = + + (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) + +3. Just as before: if both sel_tree A and sel_tree B have index_merge options, + concatenate them together. + +2.2 New tree_or() -=-=(Guest - Sat, 13 Jun 2009, 06:29)=-=- Category updated. --- /tmp/wklog.24.old.25753 2009-06-13 06:29:10.000000000 +0300 +++ /tmp/wklog.24.new.25753 2009-06-13 06:29:10.000000000 +0300 @@ -1 +1 @@ -Server-BackLog +Server-Sprint -=-=(Guest - Sat, 13 Jun 2009, 06:14)=-=- Category updated. --- /tmp/wklog.24.old.24991 2009-06-13 06:14:03.000000000 +0300 +++ /tmp/wklog.24.new.24991 2009-06-13 06:14:03.000000000 +0300 @@ -1 +1 @@ -Server-RawIdeaBin +Server-BackLog -=-=(Psergey - Wed, 03 Jun 2009, 12:09)=-=- Dependency created: 30 now depends on 24 -=-=(Guest - Mon, 01 Jun 2009, 23:30)=-=- High-Level Specification modified. --- /tmp/wklog.24.old.21580 2009-06-01 23:30:06.000000000 +0300 +++ /tmp/wklog.24.new.21580 2009-06-01 23:30:06.000000000 +0300 @@ -64,6 +64,9 @@ * How strict is the limitation on the form of the WHERE? +* Which version should this be based on? 5.1? Which patches are should be in + (google's/percona's/maria/etc?) + * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Category updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Client-BackLog +Server-RawIdeaBin -=-=(Guest - Wed, 27 May 2009, 14:41)=-=- Version updated. --- /tmp/wklog.24.old.8414 2009-05-27 14:41:43.000000000 +0300 +++ /tmp/wklog.24.new.8414 2009-05-27 14:41:43.000000000 +0300 @@ -1 +1 @@ -Server-9.x +9.x -=-=(Guest - Wed, 27 May 2009, 13:59)=-=- Title modified. --- /tmp/wklog.24.old.9498 2009-05-27 13:59:23.000000000 +0300 +++ /tmp/wklog.24.new.9498 2009-05-27 13:59:23.000000000 +0300 @@ -1 +1 @@ -index_merge optimizer: dont discard index_merge union strategies when range is available +index_merge: fair choice between index_merge union and range access ------------------------------------------------------------ -=-=(View All Progress Notes, 12 total)=-=- http://askmonty.org/worklog/index.pl?tid=24&nolimit=1 DESCRIPTION: Current range optimizer will discard possible index_merge/[sort]union strategies when there is a possible range plan. This action is a part of measures we take to avoid combinatorial explosion of possible range/ index_merge strategies. A bad side effect of this is that for WHERE clauses in form t.key1= 'very-frequent-value' AND (t.key2='rare-value1' OR t.key3='rare-value2') the optimizer will - discard union(key2,key3) in favor of range(key1) - consider costs of using range(key1) and discard that plan also and the overall effect is that possible poor range access will cause possible good index_merge access not to be considered. This WL is to about lifting this limitation at least for some subset of WHERE clauses. HIGH-LEVEL SPECIFICATION: (Not a ready HLS but draft) <contents> Solution overview Limitations TODO </contents> Solution overview ================= The idea is to delay discarding potential index_merge plans until the point where it is really necessary. This way, we won't have to do much changes in the range analyzer, but will be able to keep potential index_merge plan just enough so that it's possible to take it into consideration together with range access plans. Since there are no changes in the optimizer, the ability to consider both range and index_merge options will be limited to WHERE clauses of this form: WHERE := range_cond(key1_1) AND range_cond(key2_1) AND other_cond AND index_merge_OR_cond1(key3_1, key3_2, ...) index_merge_OR_cond2(key4_1, key4_2, ...) where index_merge_OR_cond{N} := (range_cond(keyN_1) OR range_cond(keyN_2) OR ...) range_cond(keyX) := condition that allows to construct range access of keyX and doesn't allow to construct range/index_merge accesses for any keys of the table in question. For such WHERE clauses, the range analyzer will produce SEL_TREE of this form: SEL_TREE( range(key1_1), ... range(key2_1), SEL_IMERGE( (1) SEL_TREE(key3_1}) SEL_TREE(key3_2}) ... ) ... ) which can be used to make a cost-based choice between range and index_merge. Limitations ----------- This will not be a full solution in a sense that the range analyzer will not be able to produce sel_tree (1) if the WHERE clause is specified in other form (e.g. brackets were opened). TODO ---- * is it a problem if there are keys that are referred to both from index_merge and from range access? * How strict is the limitation on the form of the WHERE? * Which version should this be based on? 5.1? Which patches are should be in (google's/percona's/maria/etc?) * TODO: The optimizer didn't compare costs of index_merge and range before (ok it did but that was done for accesses to different tables). Will there be any possible gotchas here? LOW-LEVEL DESIGN: <contents> 1. Current implementation overview 1.1. Problems in the current implementation 2. New implementation 2.1 New tree_and() 2.2 New tree_or() 3. Testing and required coverage </contents> 1. Current implementation overview ================================== At the moment, range analyzer works as follows: SEL_TREE structure represents # There are sel_trees, a sel_tree is either range or merge tree sel_tree = range_tree | imerge_tree # a range tree has range access options, possibly for several keys range_tree = range(key1) AND range(key2) AND ... AND range(keyN); # merge tree represents several way to index_merge imerge_tree = imerge1 AND imerge2 AND ... # a way to do index merge == a set to use of different indexes. imergeX = range_tree1 OR range_tree2 OR .. where no pair of range_treeX have ranges over the same index. tree_and(A, B) { if (both A and B are range trees) return a range_tree with computed intersection for each range; if (only one of A and B is a range tree) return that tree; // DISCARD-IMERGE-1 // at this point both trees are index_merge trees return concat_lists( A.imerge1 ... A.imergeN, B.imerge1 ... B.imergeN); } tree_or(A, B) { if (A and B are range trees) { R = new range_tree; for each index i R.add(range_union(A.range(i), B.range(i))); if (R has at least one range access) return R; else { /* could not build any range accesses. construct index_merge */ remove non-ranges from A; // DISCARD-IMERGE-2 remove non-ranges from B; return new index_merge(A, B); } } else if (A is range tree and B is index_merge tree (or vice versa)) { Perform this transformation: range_treeA // this is A OR (range_treeB_11 OR range_treeB_12 OR ... OR range_treeB_1N) AND (range_treeB_21 OR range_treeB_22 OR ... OR range_treeB_2N) AND ... (range_treeB_K1 OR range_treeB_K2 OR ... OR range_treeB_kN) AND = (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND (range_treeA OR range_treeB_21 OR ... OR range_treeB_2N) AND ... (range_treeA OR range_treeB_11 OR ... OR range_treeB_1N) AND Now each line represents an index_merge.. } else if (both A and B are index_merge trees) { Perform this transformation: imergeA1 AND imergeA2 AND ... AND imergeAN OR imergeB1 AND imergeB2 AND ... AND imergeBN -> (discard all imergeA{i=2,3,...} -> // DISCARD-IMERGE-3 imergeA1 OR imergeB1 AND imergeB2 AND ... AND imergeBN = = (combine imergeA1 with each of the imergeB{i} ) = combine(imergeA1 OR imergeB1) AND combine(imergeA1 OR imergeB2) AND ... AND combine(imergeA1 OR imergeBN) } } 1.1. Problems in the current implementation ------------------------------------------- As marked in the code above: DISCARD-IMERGE-1 step will cause index_merge option to be discarded when the WHERE clause has this form: (t.key1=c1 OR t.key2=c2) AND t.badkey < c3 DISCARD-IMERGE-2 step will cause index_merge option to be discarded when the WHERE clause has this form (conditions t.badkey may have abritrary form): (t.badkey<c1 AND t.key1=c1) OR (t.key1=c2 AND t.badkey < c2) DISCARD-IMERGE-3 manifests itself as the following effect: suppose there are two indexes: INDEX i1(col1, col2), INDEX i2(col1, col3) and this WHERE clause: col1=c1 AND (col2=c2 OR col3=c3) The optimizer will generate the plans that only use the "col1=c1" part. The right side of the AND will be ignored even if it has good selectivity. 2. New implementation ===================== <general idea> * Don't start fighting combinatorial explosion until we've actually got one. </> SEL_TREE structure will be now able to hold both index_merge and range scan candidates at the same time. That is, sel_tree2 = range_tree AND imerge_tree where both parts are optional (i.e. can be empty) Operations on SEL_ARG trees will be modified to produce/process the trees of this kind: 2.1 New tree_and() ------------------ In order not to lose plans, we'll make these changes: A1. Don't remove index_merge part of the tree (this will take care of DISCARD-IMERGE-1 problem) A2. Push range conditions down into index_merge trees that may support them. if one tree has range(key1) and the other tree has imerge(key1 OR key2) then perform an equvalent of this operation: rangeA(key1) AND ( rangeB(key1) OR rangeB(key2)) = (rangeA(key1) AND rangeB(key1)) OR (rangeA(key1) AND rangeB(key2)) A3. Just as before: if both sel_tree A and sel_tree B have index_merge options, concatenate them together. 2.2 New tree_or() ----------------- O1. Dont remove non-range plans: Current tree_or() code will refuse to produce index_merge plans for conditions like "t.key1part2=const OR t.key2part1=const" (this is marked as DISCARD-IMERGE-3). This was justifed as the left part of the AND condition is not usable for range access, and the operation of tree_and() guaranteed that there was no way it could changed to make a usable range plan. With new tree_and() and rule A2, this is no longer the case. For example for this query: (t.key1part2=const OR t.key2part1=const) AND t.key1part1=const it will construct a imerge(t.key1part2=const OR t.key2part1=const), range(t.key1part1=const) then tree_and() will apply rule A2 to push the range down into index merge and after that we'll have: range(t.key1part1=const) imerge( t.key1part2=const AND t.key1part1=const, t.key2part1=const ) note that imerge(...) describes a usable index_merge plan and it's possible that it will be the best access path. O2. "Create index_merge accesses when possible" Current tree_or() will not create index_merge access when it could create non-index merge access (see DISCARD-IMERGE-3 and its example in the "Problems in the current implementation" section). This will be changed to work as follows: we will create index_merge made for index scans that didn't have their match in the other sel_tree. Ilustrating it with an example: | sel_tree_A | sel_tree_B | A or B | include in index_merge? ------+------------+------------+--------+------------------------ key1 | cond1 | cond2 | condM | no key2 | cond3 | cond4 | NULL | no key3 | cond5 | | | yes, A-side key4 | cond6 | | | yes, A-side key5 | | cond7 | | yes, B-side key6 | | cond8 | | yes, B-side here we assume that - (cond1 OR cond2) did produce a combined range. Not including them in index_merge. - (cond3 OR cond4) didn't produce a usable range (e.g. they were t.key1part1=c1 AND t.key1part2=c1, respectively, and combining them didn't yield any range list) - All other scand didn't have their counterparts, so we'll end up with a SEL_TREE of: range(condM) AND index_merge((cond5 AND cond6),(cond7 AND cond8)) . O4. There is no O4. DISCARD-INDEX-MERGE-4 will remain there. The idea is that although DISCARD-INDEX-MERGE-4 does discard plans, so far we haven seen any complaints that could be attributed to it. If we face the need to lift DISCARD-INDEX-MERGE-4, our answer will be to lift it ,and produce a cross-product: ((key1p OR key2p) AND (key3p OR key4p)) OR ((key5p OR key6p) AND (key7p OR key8p)) = (key1p OR key2p OR key5p OR key6p) AND // this part is currently (key3p OR key4p OR key5p OR key6p) AND // produced (key1p OR key2p OR key5p OR key6p) AND // this part will be added (key3p OR key4p OR key5p OR key6p) //. In order to limit the impact of this combinatorial explosion, we will introduce a rule that we won't generate more than #defined MAX_IMERGE_OPTS options. 3. Testing and required coverage ================================ So far could find the following user cases: * BUG#17259: Query optimizer chooses wrong index * BUG#17673: Optimizer does not use Index Merge optimization in some cases * BUG#23322: Optimizer sometimes erroniously prefers other index over index merge * BUG#30151: optimizer is very reluctant to chose index_merge algorithm ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v3.5.9)

1 0