- developers - lists.mariadb.org

[Maria-developers] bzr commit into MariaDB 5.1, with Maria 1.5:maria branch (igor:2750)
by Igor Babaev 28 Jun '10

28 Jun '10

#At lp:maria based on revid:igor@askmonty.org-20091103182103-jnjuss2b4t72rz83 2750 Igor Babaev 2010-06-28 An implementation of index intersect via a modified Unique class. This code is planned to be used for mwl#21. modified: include/my_tree.h mysys/tree.c sql/filesort.cc sql/opt_range.cc sql/opt_range.h sql/sql_class.h sql/sql_select.cc sql/sql_sort.h sql/uniques.cc === modified file 'include/my_tree.h' --- a/include/my_tree.h 2008-05-29 15:33:33 +0000 +++ b/include/my_tree.h 2010-06-29 00:02:19 +0000 @@ -31,6 +31,7 @@ extern "C" { #define tree_set_pointer(element,ptr) *((uchar **) (element+1))=((uchar*) (ptr)) #define TREE_NO_DUPS 1 +#define TREE_ONLY_DUPS 2 typedef enum { left_root_right, right_root_left } TREE_WALK; typedef uint32 element_count; === modified file 'mysys/tree.c' --- a/mysys/tree.c 2007-05-10 09:59:39 +0000 +++ b/mysys/tree.c 2010-06-29 00:02:19 +0000 @@ -221,6 +221,8 @@ TREE_ELEMENT *tree_insert(TREE *tree, vo } if (element == &tree->null_element) { + if (tree->flag & TREE_ONLY_DUPS) + return((TREE_ELEMENT *) 1); uint alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element; tree->allocated+=alloc_size; === modified file 'sql/filesort.cc' --- a/sql/filesort.cc 2009-09-03 14:05:38 +0000 +++ b/sql/filesort.cc 2010-06-29 00:02:19 +0000 @@ -50,10 +50,6 @@ static int write_keys(SORTPARAM *param,u uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile); static void make_sortkey(SORTPARAM *param,uchar *to, uchar *ref_pos); static void register_used_fields(SORTPARAM *param); -static int merge_index(SORTPARAM *param,uchar *sort_buffer, - BUFFPEK *buffpek, - uint maxbuffer,IO_CACHE *tempfile, - IO_CACHE *outfile); static bool save_index(SORTPARAM *param,uchar **sort_keys, uint count, FILESORT_INFO *table_sort); static uint suffix_length(ulong string_length); @@ -143,6 +139,7 @@ ha_rows filesort(THD *thd, TABLE *table, bzero((char*) &param,sizeof(param)); param.sort_length= sortlength(thd, sortorder, s_length, &multi_byte_charset); param.ref_length= table->file->ref_length; + param.min_dupl_count= 0; param.addon_field= 0; param.addon_length= 0; if (!(table->file->ha_table_flags() & HA_FAST_KEY_READ) && @@ -1212,7 +1209,13 @@ int merge_buffers(SORTPARAM *param, IO_C rec_length= param->rec_length; res_length= param->res_length; sort_length= param->sort_length; - offset= rec_length-res_length; + element_count dupl_count; + uchar *src; + uint dupl_count_ofs= rec_length-sizeof(element_count); + uint min_dupl_count= param->min_dupl_count; + offset= rec_length- + (flag && min_dupl_count ? sizeof(dupl_count) : 0)-res_length; + uint wr_len= flag ? res_length : rec_length; maxcount= (ulong) (param->keys/((uint) (Tb-Fb) +1)); to_start_filepos= my_b_tell(to_file); strpos= sort_buffer; @@ -1258,16 +1261,20 @@ int merge_buffers(SORTPARAM *param, IO_C */ buffpek= (BUFFPEK*) queue_top(&queue); memcpy(param->unique_buff, buffpek->key, rec_length); - if (my_b_write(to_file, (uchar*) buffpek->key, rec_length)) - { - error=1; goto err; /* purecov: inspected */ - } + if (min_dupl_count) + memcpy(&dupl_count, param->unique_buff+dupl_count_ofs, + sizeof(dupl_count)); buffpek->key+= rec_length; - buffpek->mem_count--; - if (!--max_rows) + if (! --buffpek->mem_count) { - error= 0; /* purecov: inspected */ - goto end; /* purecov: inspected */ + if (!(error= (int) read_to_buffer(from_file,buffpek, + rec_length))) + { + VOID(queue_remove(&queue,0)); + reuse_freed_buff(&queue, buffpek, rec_length); + } + else if (error == -1) + goto err; /* purecov: inspected */ } queue_replaced(&queue); // Top element has been used } @@ -1283,27 +1290,42 @@ int merge_buffers(SORTPARAM *param, IO_C for (;;) { buffpek= (BUFFPEK*) queue_top(&queue); + src= buffpek->key; if (cmp) // Remove duplicates { if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (uchar**) &buffpek->key)) - goto skip_duplicate; - memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length); - } - if (flag == 0) - { - if (my_b_write(to_file,(uchar*) buffpek->key, rec_length)) - { - error=1; goto err; /* purecov: inspected */ + { + if (min_dupl_count) + { + element_count cnt; + memcpy(&cnt, (uchar *) buffpek->key+dupl_count_ofs, sizeof(cnt)); + dupl_count+= cnt; + } + goto skip_duplicate; } + if (min_dupl_count) + { + memcpy(param->unique_buff+dupl_count_ofs, &dupl_count, + sizeof(dupl_count)); + } + src= param->unique_buff; } - else + + if (!flag || !min_dupl_count || dupl_count >= min_dupl_count) { - if (my_b_write(to_file, (uchar*) buffpek->key+offset, res_length)) + if (my_b_write(to_file, src+(flag ? offset : 0), wr_len)) { error=1; goto err; /* purecov: inspected */ } } + if (cmp) + { + memcpy(param->unique_buff, (uchar*) buffpek->key, rec_length); + if (min_dupl_count) + memcpy(&dupl_count, param->unique_buff+dupl_count_ofs, + sizeof(dupl_count)); + } if (!--max_rows) { error= 0; /* purecov: inspected */ @@ -1339,9 +1361,33 @@ int merge_buffers(SORTPARAM *param, IO_C { if (!(*cmp)(first_cmp_arg, &(param->unique_buff), (uchar**) &buffpek->key)) { - buffpek->key+= rec_length; // Remove duplicate + if (min_dupl_count) + { + element_count cnt; + memcpy(&cnt, (uchar *) buffpek->key+dupl_count_ofs, sizeof(cnt)); + dupl_count+= cnt; + } + buffpek->key+= rec_length; --buffpek->mem_count; } + + if (min_dupl_count) + memcpy(param->unique_buff+dupl_count_ofs, &dupl_count, + sizeof(dupl_count)); + + if (!flag || !min_dupl_count || dupl_count >= min_dupl_count) + { + src= param->unique_buff; + if (my_b_write(to_file, src+(flag ? offset : 0), wr_len)) + { + error=1; goto err; /* purecov: inspected */ + } + if (!--max_rows) + { + error= 0; + goto end; + } + } } do @@ -1363,12 +1409,17 @@ int merge_buffers(SORTPARAM *param, IO_C else { register uchar *end; - strpos= buffpek->key+offset; - for (end= strpos+buffpek->mem_count*rec_length ; - strpos != end ; - strpos+= rec_length) - { - if (my_b_write(to_file, strpos, res_length)) + src= buffpek->key+offset; + for (end= src+buffpek->mem_count*rec_length ; + src != end ; + src+= rec_length) + { + if (flag && min_dupl_count && + memcmp(&min_dupl_count, src+dupl_count_ofs, + sizeof(dupl_count_ofs))<0) + continue; + + if (my_b_write(to_file, src, wr_len)) { error=1; goto err; } @@ -1389,7 +1440,7 @@ err: /* Do a merge to output-file (save only positions) */ -static int merge_index(SORTPARAM *param, uchar *sort_buffer, +int merge_index(SORTPARAM *param, uchar *sort_buffer, BUFFPEK *buffpek, uint maxbuffer, IO_CACHE *tempfile, IO_CACHE *outfile) { === modified file 'sql/opt_range.cc' --- a/sql/opt_range.cc 2009-10-30 00:36:35 +0000 +++ b/sql/opt_range.cc 2010-06-29 00:02:19 +0000 @@ -697,6 +697,9 @@ public: key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */ uint n_ror_scans; /* number of set bits in ror_scans_map */ + struct st_index_scan_info **index_scans; /* list of index scans */ + struct st_index_scan_info **index_scans_end; /* last index scan */ + struct st_ror_scan_info **ror_scans; /* list of ROR key scans */ struct st_ror_scan_info **ror_scans_end; /* last ROR scan */ /* Note that #records for each key scan is stored in table->quick_rows */ @@ -776,9 +779,11 @@ class TABLE_READ_PLAN; class TRP_RANGE; class TRP_ROR_INTERSECT; class TRP_ROR_UNION; + class TRP_INDEX_INTERSECT; class TRP_INDEX_MERGE; class TRP_GROUP_MIN_MAX; +struct st_index_scan_info; struct st_ror_scan_info; static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field, @@ -804,6 +809,9 @@ static TRP_RANGE *get_key_scans_params(P bool update_tbl_stats, double read_time); static +TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree, + double read_time); +static TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree, double read_time, bool *are_all_covering); @@ -1743,7 +1751,7 @@ int QUICK_INDEX_MERGE_SELECT::init() int QUICK_INDEX_MERGE_SELECT::reset() { DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::reset"); - DBUG_RETURN(read_keys_and_merge()); + DBUG_RETURN (read_keys_and_merge()); } bool @@ -1778,6 +1786,63 @@ QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_M DBUG_VOID_RETURN; } +QUICK_INDEX_INTERSECT_SELECT::QUICK_INDEX_INTERSECT_SELECT(THD *thd_param, + TABLE *table) + :pk_quick_select(NULL), thd(thd_param) +{ + DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::QUICK_INDEX_INTERSECT_SELECT"); + index= MAX_KEY; + head= table; + bzero(&read_record, sizeof(read_record)); + init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0); + DBUG_VOID_RETURN; +} + +int QUICK_INDEX_INTERSECT_SELECT::init() +{ + DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::init"); + DBUG_RETURN(0); +} + +int QUICK_INDEX_INTERSECT_SELECT::reset() +{ + DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::reset"); + DBUG_RETURN (read_keys_and_merge()); +} + +bool +QUICK_INDEX_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range) +{ + /* + Save quick_select that does scan on clustered primary key as it will be + processed separately. + */ + if (head->file->primary_key_is_clustered() && + quick_sel_range->index == head->s->primary_key) + pk_quick_select= quick_sel_range; + else + return quick_selects.push_back(quick_sel_range); + return 0; +} + +QUICK_INDEX_INTERSECT_SELECT::~QUICK_INDEX_INTERSECT_SELECT() +{ + List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects); + QUICK_RANGE_SELECT* quick; + DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::~QUICK_INDEX_INTERSECT_SELECT"); + quick_it.rewind(); + while ((quick= quick_it++)) + quick->file= NULL; + quick_selects.delete_elements(); + delete pk_quick_select; + /* It's ok to call the next two even if they are already deinitialized */ + end_read_record(&read_record); + free_io_cache(head); + free_root(&alloc,MYF(0)); + DBUG_VOID_RETURN; +} + + QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param, TABLE *table, @@ -2555,6 +2620,24 @@ public: /* + Plan for QUICK_INDEX_INTERSECT_SELECT scan. + QUICK_INDEX_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows + is ignored by make_quick. +*/ + +class TRP_INDEX_INTERSECT : public TABLE_READ_PLAN +{ +public: + TRP_INDEX_INTERSECT() {} /* Remove gcc warning */ + virtual ~TRP_INDEX_INTERSECT() {} /* Remove gcc warning */ + QUICK_SELECT_I *make_quick(PARAM *param, bool retrieve_full_rows, + MEM_ROOT *parent_alloc); + TRP_RANGE **range_scans; /* array of ptrs to plans of merged scans */ + TRP_RANGE **range_scans_end; /* end of the array */ +}; + + +/* Plan for QUICK_INDEX_MERGE_SELECT scan. QUICK_ROR_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows is ignored by make_quick. @@ -2621,6 +2704,30 @@ public: }; +typedef struct st_index_scan_info +{ + uint idx; /* # of used key in param->keys */ + uint keynr; /* # of used key in table */ + uint range_count; + ha_rows records; /* estimate of # records this scan will return */ + + /* Set of intervals over key fields that will be used for row retrieval. */ + SEL_ARG *sel_arg; + + /* Fields used in the query and covered by this ROR scan. */ + MY_BITMAP covered_fields; + uint used_fields_covered; /* # of set bits in covered_fields */ + int key_rec_length; /* length of key record (including rowid) */ + + /* + Cost of reading all index records with values in sel_arg intervals set + (assuming there is no need to access full table records) + */ + double index_read_cost; + uint first_uncovered_field; /* first unused bit in covered_fields */ + uint key_components; /* # of parts in the key */ +} INDEX_SCAN_INFO; + /* Fill param->needed_fields with bitmap of fields used in the query. SYNOPSIS @@ -2899,6 +3006,7 @@ int SQL_SELECT::test_quick_select(THD *t */ TRP_RANGE *range_trp; TRP_ROR_INTERSECT *rori_trp; + TRP_INDEX_INTERSECT *intersect_trp; bool can_build_covering= FALSE; remove_nonrange_trees(&param, tree); @@ -2938,6 +3046,18 @@ int SQL_SELECT::test_quick_select(THD *t best_trp= rori_trp; } } +#if 1 +#else + if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE)) + { + if ((intersect_trp= get_best_index_intersect(&param, tree, + best_read_time))) + { + best_trp= intersect_trp; + best_read_time= best_trp->read_cost; + } + } +#endif if (optimizer_flag(thd, OPTIMIZER_SWITCH_INDEX_MERGE)) { @@ -4601,6 +4721,85 @@ TABLE_READ_PLAN *merge_same_index_scans( DBUG_RETURN(trp); } +static +TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree, + double read_time) +{ + uint i; + uint unique_calc_buff_size; + TRP_RANGE **cur_range; + TRP_RANGE **range_scans; + TRP_INDEX_INTERSECT *intersect_trp= NULL; + double intersect_cost= 0.0; + ha_rows scan_records= 0; + double selectivity= 1.0; + ha_rows table_records= param->table->file->stats.records; + uint n_index_scans= tree->index_scans_end - tree->index_scans; + + DBUG_ENTER("get_best_index_intersect"); + + if (!n_index_scans) + DBUG_RETURN(NULL); + + if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root, + sizeof(TRP_RANGE *)* + n_index_scans))) + DBUG_RETURN(NULL); + + for (i= 0, cur_range= range_scans; i < n_index_scans; i++) + { + struct st_index_scan_info *index_scan= tree->index_scans[i]; + if ((*cur_range= new (param->mem_root) TRP_RANGE(index_scan->sel_arg, + index_scan->idx))) + { + TRP_RANGE *trp= *cur_range; + trp->records= index_scan->records; + trp->is_ror= FALSE; + trp->read_cost= get_index_only_read_time(param, index_scan->records, + index_scan->keynr); + scan_records+= trp->records; + selectivity*= (double) trp->records/table_records; + intersect_cost+= trp->read_cost; + cur_range++; + } + } + + /* Add Unique operations cost */ + unique_calc_buff_size= + Unique::get_cost_calc_buff_size((ulong)scan_records, + param->table->file->ref_length, + param->thd->variables.sortbuff_size); + if (param->imerge_cost_buff_size < unique_calc_buff_size) + { + if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root, + unique_calc_buff_size))) + DBUG_RETURN(NULL); + param->imerge_cost_buff_size= unique_calc_buff_size; + } + + intersect_cost += + Unique::get_use_cost(param->imerge_cost_buff, scan_records, + param->table->file->ref_length, + param->thd->variables.sortbuff_size); + + intersect_cost += get_sweep_read_cost(param, + (ha_rows) (table_records*selectivity)); + + if (intersect_cost < read_time) + { + if ((intersect_trp= new (param->mem_root)TRP_INDEX_INTERSECT)) + { + intersect_trp->read_cost= intersect_cost; + intersect_trp->records= (ha_rows) table_records*selectivity; + set_if_bigger(intersect_trp->records, 1); + intersect_trp->range_scans= range_scans; + intersect_trp->range_scans_end= cur_range; + read_time= intersect_cost; + } + } + DBUG_RETURN(intersect_trp); +} + /* Calculate cost of 'index only' scan for given index and number of records. @@ -4638,27 +4837,8 @@ static double get_index_only_read_time(c } -typedef struct st_ror_scan_info -{ - uint idx; /* # of used key in param->keys */ - uint keynr; /* # of used key in table */ - ha_rows records; /* estimate of # records this scan will return */ - - /* Set of intervals over key fields that will be used for row retrieval. */ - SEL_ARG *sel_arg; - - /* Fields used in the query and covered by this ROR scan. */ - MY_BITMAP covered_fields; - uint used_fields_covered; /* # of set bits in covered_fields */ - int key_rec_length; /* length of key record (including rowid) */ - - /* - Cost of reading all index records with values in sel_arg intervals set - (assuming there is no need to access full table records) - */ - double index_read_cost; - uint first_uncovered_field; /* first unused bit in covered_fields */ - uint key_components; /* # of parts in the key */ +typedef struct st_ror_scan_info : INDEX_SCAN_INFO +{ } ROR_SCAN_INFO; @@ -5518,6 +5698,14 @@ static TRP_RANGE *get_key_scans_params(P "tree scans");); tree->ror_scans_map.clear_all(); tree->n_ror_scans= 0; + tree->index_scans= 0; + if (!tree->keys_map.is_clear_all()) + { + tree->index_scans= + (INDEX_SCAN_INFO **) alloc_root(param->mem_root, + sizeof(INDEX_SCAN_INFO *) * param->keys); + } + tree->index_scans_end= tree->index_scans; for (idx= 0,key=tree->keys, end=key+param->keys; key != end ; key++,idx++) @@ -5526,6 +5714,7 @@ static TRP_RANGE *get_key_scans_params(P double found_read_time; if (*key) { + INDEX_SCAN_INFO *index_scan; uint keynr= param->real_keynr[idx]; if ((*key)->type == SEL_ARG::MAYBE_KEY || (*key)->maybe_flag) @@ -5535,6 +5724,17 @@ static TRP_RANGE *get_key_scans_params(P (bool) param->table->covering_keys.is_set(keynr); found_records= check_quick_select(param, idx, *key, update_tbl_stats); + if (found_records != HA_POS_ERROR && tree->index_scans && + (index_scan= (INDEX_SCAN_INFO *)alloc_root(param->mem_root, + sizeof(INDEX_SCAN_INFO)))) + { + index_scan->idx= idx; + index_scan->keynr= keynr; + index_scan->range_count= param->range_count; + index_scan->records= found_records; + index_scan->sel_arg= *key; + *tree->index_scans_end++= index_scan; + } if (param->is_ror_scan) { tree->n_ror_scans++; @@ -5629,6 +5829,34 @@ QUICK_SELECT_I *TRP_INDEX_MERGE::make_qu return quick_imerge; } +QUICK_SELECT_I *TRP_INDEX_INTERSECT::make_quick(PARAM *param, + bool retrieve_full_rows, + MEM_ROOT *parent_alloc) +{ + QUICK_INDEX_INTERSECT_SELECT *quick_intersect; + QUICK_RANGE_SELECT *quick; + /* index_merge always retrieves full rows, ignore retrieve_full_rows */ + if (!(quick_intersect= new QUICK_INDEX_INTERSECT_SELECT(param->thd, param->table))) + return NULL; + + quick_intersect->records= records; + quick_intersect->read_time= read_cost; + for (TRP_RANGE **range_scan= range_scans; range_scan != range_scans_end; + range_scan++) + { + if (!(quick= (QUICK_RANGE_SELECT*) + ((*range_scan)->make_quick(param, FALSE, &quick_intersect->alloc)))|| + quick_intersect->push_quick_back(quick)) + { + delete quick; + delete quick_intersect; + return NULL; + } + } + return quick_intersect; +} + + QUICK_SELECT_I *TRP_ROR_INTERSECT::make_quick(PARAM *param, bool retrieve_full_rows, MEM_ROOT *parent_alloc) @@ -8893,6 +9121,18 @@ bool QUICK_INDEX_MERGE_SELECT::is_keys_u return 0; } +bool QUICK_INDEX_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields) +{ + QUICK_RANGE_SELECT *quick; + List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); + while ((quick= it++)) + { + if (is_key_used(head, quick->index, fields)) + return 1; + } + return 0; +} + bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields) { QUICK_RANGE_SELECT *quick; @@ -9038,14 +9278,19 @@ err: other error */ -int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() +int read_keys_and_merge_scans(THD *thd, + TABLE *head, + List<QUICK_RANGE_SELECT> quick_selects, + QUICK_RANGE_SELECT *pk_quick_select, + READ_RECORD *read_record, + bool intersection) { List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects); QUICK_RANGE_SELECT* cur_quick; int result; Unique *unique; handler *file= head->file; - DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge"); + DBUG_ENTER("read_keys_and_merge"); /* We're going to just read rowids. */ file->extra(HA_EXTRA_KEYREAD); @@ -9053,6 +9298,7 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_ cur_quick_it.rewind(); cur_quick= cur_quick_it++; + bool first_quick= TRUE; DBUG_ASSERT(cur_quick != 0); /* @@ -9064,13 +9310,20 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_ unique= new Unique(refpos_order_cmp, (void *)file, file->ref_length, - thd->variables.sortbuff_size); + thd->variables.sortbuff_size, + intersection ? quick_selects.elements : 0); if (!unique) DBUG_RETURN(1); for (;;) { while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE) { + if (first_quick) + { + first_quick= FALSE; + if (intersection && unique->is_in_memory()) + unique->close_for_expansion(); + } cur_quick->range_end(); cur_quick= cur_quick_it++; if (!cur_quick) @@ -9113,14 +9366,24 @@ int QUICK_INDEX_MERGE_SELECT::read_keys_ */ result= unique->get(head); delete unique; - doing_pk_scan= FALSE; /* index_merge currently doesn't support "using index" at all */ file->extra(HA_EXTRA_NO_KEYREAD); - init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1 , 1, TRUE); + init_read_record(read_record, thd, head, (SQL_SELECT*) 0, 1 , 1, TRUE); DBUG_RETURN(result); } +int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge() + +{ + int result; + DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge"); + result= read_keys_and_merge_scans(thd, head, quick_selects, pk_quick_select, + &read_record, FALSE); + doing_pk_scan= FALSE; + DBUG_RETURN(result); +} + /* Get next row for index_merge. NOTES @@ -9157,6 +9420,44 @@ int QUICK_INDEX_MERGE_SELECT::get_next() DBUG_RETURN(result); } +int QUICK_INDEX_INTERSECT_SELECT::read_keys_and_merge() + +{ + int result; + DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::read_keys_and_merge"); + result= read_keys_and_merge_scans(thd, head, quick_selects, pk_quick_select, + &read_record, TRUE); + doing_pk_scan= FALSE; + DBUG_RETURN(result); +} + +int QUICK_INDEX_INTERSECT_SELECT::get_next() +{ + int result; + DBUG_ENTER("QUICK_INDEX_INTERSECT_SELECT::get_next"); + + if (doing_pk_scan) + DBUG_RETURN(pk_quick_select->get_next()); + + if ((result= read_record.read_record(&read_record)) == -1) + { + result= HA_ERR_END_OF_FILE; + end_read_record(&read_record); + free_io_cache(head); + /* All rows from Unique have been retrieved, do a clustered PK scan */ + if (pk_quick_select) + { + doing_pk_scan= TRUE; + if ((result= pk_quick_select->init()) || + (result= pk_quick_select->reset())) + DBUG_RETURN(result); + DBUG_RETURN(pk_quick_select->get_next()); + } + } + + DBUG_RETURN(result); +} + /* Retrieve next record. @@ -9887,6 +10188,28 @@ void QUICK_INDEX_MERGE_SELECT::add_info_ str->append(')'); } +void QUICK_INDEX_INTERSECT_SELECT::add_info_string(String *str) +{ + QUICK_RANGE_SELECT *quick; + bool first= TRUE; + List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); + str->append(STRING_WITH_LEN("sort_intersect(")); + while ((quick= it++)) + { + if (!first) + str->append(','); + else + first= FALSE; + quick->add_info_string(str); + } + if (pk_quick_select) + { + str->append(','); + pk_quick_select->add_info_string(str); + } + str->append(')'); +} + void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str) { bool first= TRUE; @@ -9911,6 +10234,7 @@ void QUICK_ROR_INTERSECT_SELECT::add_inf str->append(')'); } + void QUICK_ROR_UNION_SELECT::add_info_string(String *str) { bool first= TRUE; @@ -9940,8 +10264,12 @@ void QUICK_RANGE_SELECT::add_keys_and_le used_lengths->append(buf, length); } -void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names, - String *used_lengths) +static +void add_keys_and_lengths_of_index_scans(TABLE *head, + List<QUICK_RANGE_SELECT> quick_selects, + QUICK_RANGE_SELECT *pk_quick_select, + String *key_names, + String *used_lengths) { char buf[64]; uint length; @@ -9975,6 +10303,20 @@ void QUICK_INDEX_MERGE_SELECT::add_keys_ } } +void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names, + String *used_lengths) +{ + add_keys_and_lengths_of_index_scans(head, quick_selects, pk_quick_select, + key_names, used_lengths); +} + +void QUICK_INDEX_INTERSECT_SELECT::add_keys_and_lengths(String *key_names, + String *used_lengths) +{ + add_keys_and_lengths_of_index_scans(head, quick_selects, pk_quick_select, + key_names, used_lengths); +} + void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names, String *used_lengths) { @@ -12310,6 +12652,22 @@ void QUICK_INDEX_MERGE_SELECT::dbug_dump fprintf(DBUG_FILE, "%*s}\n", indent, ""); } +void QUICK_INDEX_INTERSECT_SELECT::dbug_dump(int indent, bool verbose) +{ + List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); + QUICK_RANGE_SELECT *quick; + fprintf(DBUG_FILE, "%*squick index_intersect select\n", indent, ""); + fprintf(DBUG_FILE, "%*smerged scans {\n", indent, ""); + while ((quick= it++)) + quick->dbug_dump(indent+2, verbose); + if (pk_quick_select) + { + fprintf(DBUG_FILE, "%*sclustered PK quick:\n", indent, ""); + pk_quick_select->dbug_dump(indent+2, verbose); + } + fprintf(DBUG_FILE, "%*s}\n", indent, ""); +} + void QUICK_ROR_INTERSECT_SELECT::dbug_dump(int indent, bool verbose) { List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); === modified file 'sql/opt_range.h' --- a/sql/opt_range.h 2009-09-02 08:40:18 +0000 +++ b/sql/opt_range.h 2010-06-29 00:02:19 +0000 @@ -195,12 +195,13 @@ public: enum { QS_TYPE_RANGE = 0, - QS_TYPE_INDEX_MERGE = 1, - QS_TYPE_RANGE_DESC = 2, - QS_TYPE_FULLTEXT = 3, - QS_TYPE_ROR_INTERSECT = 4, - QS_TYPE_ROR_UNION = 5, - QS_TYPE_GROUP_MIN_MAX = 6 + QS_TYPE_INDEX_INTERSECT = 1, + QS_TYPE_INDEX_MERGE = 2, + QS_TYPE_RANGE_DESC = 3, + QS_TYPE_FULLTEXT = 4, + QS_TYPE_ROR_INTERSECT = 5, + QS_TYPE_ROR_UNION = 6, + QS_TYPE_GROUP_MIN_MAX = 7 }; /* Get type of this quick select - one of the QS_TYPE_* values */ @@ -312,8 +313,16 @@ protected: friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx, SEL_ARG *key_tree, MEM_ROOT *alloc); + friend + int read_keys_and_merge_scans(THD *thd, TABLE *head, + List<QUICK_RANGE_SELECT> quick_selects, + QUICK_RANGE_SELECT *pk_quick_select, + READ_RECORD *read_record, + bool intersection); + friend class QUICK_SELECT_DESC; friend class QUICK_INDEX_MERGE_SELECT; + friend class QUICK_INDEX_INTERSECT_SELECT; friend class QUICK_ROR_INTERSECT_SELECT; friend class QUICK_GROUP_MIN_MAX_SELECT; @@ -463,6 +472,44 @@ public: READ_RECORD read_record; }; +class QUICK_INDEX_INTERSECT_SELECT : public QUICK_SELECT_I +{ +public: + QUICK_INDEX_INTERSECT_SELECT(THD *thd, TABLE *table); + ~QUICK_INDEX_INTERSECT_SELECT(); + + int init(); + int reset(void); + int get_next(); + bool reverse_sorted() { return false; } + bool unique_key_range() { return false; } + int get_type() { return QS_TYPE_INDEX_INTERSECT; } + void add_keys_and_lengths(String *key_names, String *used_lengths); + void add_info_string(String *str); + bool is_keys_used(const MY_BITMAP *fields); +#ifndef DBUG_OFF + void dbug_dump(int indent, bool verbose); +#endif + + bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range); + + /* range quick selects this index_merge read consists of */ + List<QUICK_RANGE_SELECT> quick_selects; + + /* quick select that uses clustered primary key (NULL if none) */ + QUICK_RANGE_SELECT* pk_quick_select; + + /* true if this select is currently doing a clustered PK scan */ + bool doing_pk_scan; + + MEM_ROOT alloc; + THD *thd; + int read_keys_and_merge(); + + /* used to get rows collected in Unique */ + READ_RECORD read_record; +}; + /* Rowid-Ordered Retrieval (ROR) index intersection quick select. === modified file 'sql/sql_class.h' --- a/sql/sql_class.h 2009-09-15 10:46:35 +0000 +++ b/sql/sql_class.h 2010-06-29 00:02:19 +0000 @@ -2827,6 +2827,7 @@ class user_var_entry DTCollation collation; }; + /* Unique -- class for unique (removing of duplicates). Puts all values to the TREE. If the tree becomes too big, @@ -2845,11 +2846,21 @@ class Unique :public Sql_alloc uchar *record_pointers; bool flush(); uint size; +#if 0 +#else + uint full_size; + uint min_dupl_count; +#endif public: ulong elements; Unique(qsort_cmp2 comp_func, void *comp_func_fixed_arg, +#if 0 uint size_arg, ulonglong max_in_memory_size_arg); +#else + uint size_arg, ulonglong max_in_memory_size_arg, + uint min_dupl_count_arg= 0); +#endif ~Unique(); ulong elements_in_tree() { return tree.elements_in_tree; } inline bool unique_add(void *ptr) @@ -2861,6 +2872,9 @@ public: DBUG_RETURN(!tree_insert(&tree, ptr, 0, tree.custom_arg)); } + bool is_in_memory() { return (my_b_tell(&file) == 0); } + void close_for_expansion() { tree.flag= TREE_ONLY_DUPS; } + bool get(TABLE *table); static double get_use_cost(uint *buffer, uint nkeys, uint key_size, ulonglong max_in_memory_size); @@ -2877,6 +2891,11 @@ public: friend int unique_write_to_file(uchar* key, element_count count, Unique *unique); friend int unique_write_to_ptrs(uchar* key, element_count count, Unique *unique); + + friend int unique_write_to_file_with_count(uchar* key, element_count count, + Unique *unique); + friend int unique_intersect_write_to_ptrs(uchar* key, element_count count, + Unique *unique); }; === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2009-10-26 11:38:17 +0000 +++ b/sql/sql_select.cc 2010-06-29 00:02:19 +0000 @@ -13333,7 +13333,8 @@ test_if_skip_sort_order(JOIN_TAB *tab,OR by clustered PK values. */ - if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE || + if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE || + quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT || quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION || quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) DBUG_RETURN(0); @@ -13682,6 +13683,7 @@ check_reverse_order: QUICK_SELECT_DESC *tmp; int quick_type= select->quick->get_type(); if (quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE || + quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT || quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT || quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION || quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX) @@ -16405,6 +16407,7 @@ static void select_describe(JOIN *join, quick_type= tab->select->quick->get_type(); if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) || (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) || + (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) || (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION)) tab->type = JT_INDEX_MERGE; else @@ -16609,6 +16612,7 @@ static void select_describe(JOIN *join, { if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION || quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT || + quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_INTERSECT || quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) { extra.append(STRING_WITH_LEN("; Using ")); === modified file 'sql/sql_sort.h' --- a/sql/sql_sort.h 2007-09-27 14:05:07 +0000 +++ b/sql/sql_sort.h 2010-06-29 00:02:19 +0000 @@ -57,6 +57,7 @@ typedef struct st_sort_param { uint addon_length; /* Length of added packed fields */ uint res_length; /* Length of records in final sorted file/buffer */ uint keys; /* Max keys / buffer */ + element_count min_dupl_count; ha_rows max_rows,examined_rows; TABLE *sort_form; /* For quicker make_sortkey */ SORT_FIELD *local_sortorder; @@ -80,4 +81,9 @@ int merge_buffers(SORTPARAM *param,IO_CA IO_CACHE *to_file, uchar *sort_buffer, BUFFPEK *lastbuff,BUFFPEK *Fb, BUFFPEK *Tb,int flag); +int merge_index(SORTPARAM *param, uchar *sort_buffer, + BUFFPEK *buffpek, uint maxbuffer, + IO_CACHE *tempfile, IO_CACHE *outfile); + void reuse_freed_buff(QUEUE *queue, BUFFPEK *reuse, uint key_length); + === modified file 'sql/uniques.cc' --- a/sql/uniques.cc 2009-09-07 20:50:10 +0000 +++ b/sql/uniques.cc 2010-06-29 00:02:19 +0000 @@ -33,7 +33,6 @@ #include "mysql_priv.h" #include "sql_sort.h" - int unique_write_to_file(uchar* key, element_count count, Unique *unique) { /* @@ -45,6 +44,12 @@ int unique_write_to_file(uchar* key, ele return my_b_write(&unique->file, key, unique->size) ? 1 : 0; } +int unique_write_to_file_with_count(uchar* key, element_count count, Unique *unique) +{ + return my_b_write(&unique->file, key, unique->size) || + my_b_write(&unique->file, &count, sizeof(element_count)) ? 1 : 0; +} + int unique_write_to_ptrs(uchar* key, element_count count, Unique *unique) { memcpy(unique->record_pointers, key, unique->size); @@ -52,10 +57,26 @@ int unique_write_to_ptrs(uchar* key, ele return 0; } +int unique_intersect_write_to_ptrs(uchar* key, element_count count, Unique *unique) +{ + if (count >= unique->min_dupl_count) + { + memcpy(unique->record_pointers, key, unique->size); + unique->record_pointers+=unique->size; + } + return 0; +} + + Unique::Unique(qsort_cmp2 comp_func, void * comp_func_fixed_arg, - uint size_arg, ulonglong max_in_memory_size_arg) + uint size_arg, ulonglong max_in_memory_size_arg, + uint min_dupl_count_arg) :max_in_memory_size(max_in_memory_size_arg), size(size_arg), elements(0) { + min_dupl_count= min_dupl_count_arg; + full_size= size; + if (min_dupl_count_arg) + full_size+= sizeof(element_count); my_b_clear(&file); init_tree(&tree, (ulong) (max_in_memory_size / 16), 0, size, comp_func, 0, NULL, comp_func_fixed_arg); @@ -276,7 +297,11 @@ double Unique::get_use_cost(uint *buffer result= 2*log2_n_fact(last_tree_elems + 1.0); if (n_full_trees) result+= n_full_trees * log2_n_fact(max_elements_in_tree + 1.0); +#if 1 result /= TIME_FOR_COMPARE_ROWID; +#else + result /= TIME_FOR_COMPARE_ROWID * 10; +#endif DBUG_PRINT("info",("unique trees sizes: %u=%u*%lu + %lu", nkeys, n_full_trees, n_full_trees?max_elements_in_tree:0, @@ -327,7 +352,10 @@ bool Unique::flush() file_ptr.count=tree.elements_in_tree; file_ptr.file_pos=my_b_tell(&file); - if (tree_walk(&tree, (tree_walk_action) unique_write_to_file, + tree_walk_action action= min_dupl_count ? + (tree_walk_action) unique_write_to_file_with_count : + (tree_walk_action) unique_write_to_file; + if (tree_walk(&tree, action, (void*) this, left_root_right) || insert_dynamic(&file_ptrs, (uchar*) &file_ptr)) return 1; @@ -357,6 +385,7 @@ Unique::reset() reinit_io_cache(&file, WRITE_CACHE, 0L, 0, 1); } elements= 0; + tree.flag= 0; } /* @@ -576,14 +605,16 @@ bool Unique::get(TABLE *table) { SORTPARAM sort_param; table->sort.found_records=elements+tree.elements_in_tree; - if (my_b_tell(&file) == 0) { /* Whole tree is in memory; Don't use disk if you don't need to */ if ((record_pointers=table->sort.record_pointers= (uchar*) my_malloc(size * tree.elements_in_tree, MYF(0)))) { - (void) tree_walk(&tree, (tree_walk_action) unique_write_to_ptrs, + tree_walk_action action= min_dupl_count ? + (tree_walk_action) unique_intersect_write_to_ptrs : + (tree_walk_action) unique_write_to_ptrs; + (void) tree_walk(&tree, action, this, left_root_right); return 0; } @@ -614,7 +645,10 @@ bool Unique::get(TABLE *table) sort_param.max_rows= elements; sort_param.sort_form=table; sort_param.rec_length= sort_param.sort_length= sort_param.ref_length= - size; + sort_param.rec_length= sort_param.sort_length= sort_param.ref_length= + full_size; + sort_param.min_dupl_count= min_dupl_count; + sort_param.res_length= 0; sort_param.keys= (uint) (max_in_memory_size / sort_param.sort_length); sort_param.not_killable=1; @@ -635,8 +669,9 @@ bool Unique::get(TABLE *table) if (flush_io_cache(&file) || reinit_io_cache(&file,READ_CACHE,0L,0,0)) goto err; - if (merge_buffers(&sort_param, &file, outfile, sort_buffer, file_ptr, - file_ptr, file_ptr+maxbuffer,0)) + sort_param.res_length= sort_param.rec_length- + (min_dupl_count ? sizeof(min_dupl_count) : 0); + if (merge_index(&sort_param, sort_buffer, file_ptr, maxbuffer, &file, outfile)) goto err; error=0; err:

1 0

[Maria-developers] update_virtual_fields() calls missing in sql_join_cache.cc?
by Sergey Petrunya 28 Jun '10

28 Jun '10

Hello Igor, It has come to my attention that sql_join_cache.cc does not have as many update_virtual_fields() calls as I think it ought to have. My reasoning was as follows: AFAIU when one has read a record from a table, they must call update_virtual_fields() before they try to evaluate the attached table condition (because the condition may refer to virtual fields). Now if one opens sql_join_cache.cc and looks at these three functions: JOIN_CACHE_BKA::join_matching_records(bool skip_last) { ... while (!(error= file->multi_range_read_next((char **) &rec_ptr))) { ... rc= generate_full_extensions(rec_ptr); ... } ... } JOIN_CACHE::generate_full_extensions(uchar *rec_ptr) { ... if (check_match(rec_ptr)) { ... } JOIN_CACHE::check_match(uchar *rec_ptr) { /* Check whether pushdown conditions are satisfied */ if (join_tab->select && join_tab->select->skip_record()) return FALSE; ... } one can see a call path where we read a table record with multi_range_read_next and then proceed to evaluating the attached condition with skip_record() without calling update_virtual_fields(). Is there a problem. Another thing I can't understand about update_virtual_fields() is the asymmetry between rr_XXX() functions. Why do rr_quick() and rr_sequential() call update_virtual_fields() while rr_index_first() and rr_from_pointers() don't? If that is intentional, I think it deserves to be documented. BR Sergey -- Sergey Petrunia, Software Developer Monty Program AB, http://askmonty.org Blog: http://s.petrunia.net/blog

1 0

[Maria-developers] worklog update
by Sergei Golubchik 28 Jun '10

28 Jun '10

Hi. A quick summary of recent changes in WorkLog: * there are no "archived" tasks anymore. All cancelled and closed tasks are "inactive", others are "active" * guest users shouldn't be able to update WL tasks now. * "private" field dissapeared, you won't see "Private: yes" anymore. * major rework of the reporting engine: - multiple report generators (two, at the moment) - multi-value select filters - configurable result display - saved reports - more fields to display and to filter on * sections in the task view are reordered * second code review removed * lead architect added * WL emails set List-Archive and have the task number first in the subject * a "developer" can be anybody, not just an employee of MPAB * virtual tasks removed from the right sidebar - one can get similar results with saved reports * no "Current as text" button * no two tasks may have the same title anymore (this was a bug in the old worklog that caused duplicate titles) I may occasionally do more work on WL, after using it for a while and understanding what's missing. Regards, Sergei

1 0

[Maria-developers] WL#69 Deleted (by Serg): Fix table_cache negative scalability
by worklog-noreply＠askmonty.org 28 Jun '10

28 Jun '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Fix table_cache negative scalability CREATION DATE..: Fri, 18 Dec 2009, 16:30 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 69 (http://askmonty.org/worklog/?tid=69) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Fix the problem described in this blog entry: http://www.mysqlperformanceblog.com/2009/11/16/table_cache-negative-scalabi… You can read the blog, or the text below. --- quoted text --- November 16, 2009 table_cache negative scalability Posted by peter | Vote on Planet MySQL Couple of months ago there was a post by FreshBooks on getting great performance improvements by lowering table_cache variable. So I decided to investigate what is really happening here. The common sense approach to tuning caches is to get them as large as you can if you have enough resources (such as memory). With MySQL common sense however does not always works weve seen performance issues with large query_cache_size also sort_buffer_size and read_buffer_size may not give you better performance if you increase them. I found this also applies to some other buffers. Even though having previous experience of surprised behavior I did not expect such a table_cache issue the LRU for cache management is classics and there are scalable algorithms to deal with it. I would expect Monty to implement one of them. To do the test I have created 100.000 empty tables containing single integer column and no indexes and when ran SELECT * FROM tableN in the loop. Each table in such case is accessed only once and on any but first run each access would require table replacement in table cache based on LRU logic. MySQL Sandbox helped me to test this with different servers easily. I did test on CentOS 5.3, Xeon E5405, 16GB RAM and EXT3 file system on the SATA hard drive. MySQL 5.0.85 Created 100.000 tables in around 3min 40 sec which is about 450 tables/sec This indicates the fsync is lying on this test system as default sync_frm option is used. With default table_cache=64 accessing all tables take 12 sec which is almost 8500 tables/sec which is a great speed. We can note significant writes to the disk during this read-only benchmark. Why ? Because for MyISAM tables table header has to be modified each time the table is opened. In this case the performance was so great because all 100.000 tables data (first block of index) was placed close by on disk as well as fully cached which made updates to headers very slow. In the production systems with table headers not in OS cache you often will see significantly low numbers 100 or less. With significantly larger table_cache=16384 (and appropriately adjusted number of open files) the same operation takes 660 seconds which is 151 tables/sec which is around 50 times slower. Wow. This is the slow down. We can see the load becomes very CPU bound in this case and it looks like some of the table_cache algorithms do not scale well. The absolute numbers are also very interesting 151 tables/sec is not that bad if you look at it as an absolute number. So if you tune table cache is normal case and is able to bring down your miss rate (opened_tables) to 10/sec or less by using large table_cache you should do so. However if you have so many tables you still see 100+ misses/sec while your data (at least table headers) is well cached so the cost of table cache miss is not very high, you may be better of with significantly reduced table cache size. The next step for me was to see if the problem was fixed in MySQL 5.1 in this version table_cache was significantly redone and split in table_open_cache and table_definition_cache and I assumed the behavior may be different as well. MySQL 5.1.40 I started testing with default table_open_cache=64 and table_definition_cache=256 the read took about 12 seconds very close to MySQL 5.0.85. As I increased table_definition_cache to 16384 result remained the same so this variable is not causing the bottleneck. However increasing table_open_cache to 16384 causes scan to take about 780 sec which is a bit worse than MySQL 5.0.85. So the problem is not fixed in MySQL 5.1, lets see how MySQL 5.4 behaves. MySQL 5.4.2 MySQL 5.4.2 has higher default table_open_cache so I took it down to 64 so we can compare apples to apples. It performs same as MySQL 5.0 and MySQL 5.1 with small table cache. With table_open_cache increased to 16384 the test took 750 seconds so the problem exists in MySQL 5.4 as well. So the problem is real and it is not fixed even in Performance focused MySQL 5.4. As we can see large table_cache (or table_open_cache_ values indeed can cause significant performance problems. Interesting enough Innodb has a very similar task of managing its own cache of file descriptors (set by innodb_open_files) As the time allows I should test if Heikki knows how to implement LRU properly so it does not have problem with large number. Well see. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v4.0.0)

1 0

[Maria-developers] WL#70 Deleted (by Serg): Fix table_cache negative scalability
by worklog-noreply＠askmonty.org 28 Jun '10

28 Jun '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Fix table_cache negative scalability CREATION DATE..: Fri, 18 Dec 2009, 16:30 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 70 (http://askmonty.org/worklog/?tid=70) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Fix the problem described in this blog entry: http://www.mysqlperformanceblog.com/2009/11/16/table_cache-negative-scalabi… You can read the blog, or the text below. --- quoted text --- November 16, 2009 table_cache negative scalability Posted by peter | Vote on Planet MySQL Couple of months ago there was a post by FreshBooks on getting great performance improvements by lowering table_cache variable. So I decided to investigate what is really happening here. The common sense approach to tuning caches is to get them as large as you can if you have enough resources (such as memory). With MySQL common sense however does not always works weve seen performance issues with large query_cache_size also sort_buffer_size and read_buffer_size may not give you better performance if you increase them. I found this also applies to some other buffers. Even though having previous experience of surprised behavior I did not expect such a table_cache issue the LRU for cache management is classics and there are scalable algorithms to deal with it. I would expect Monty to implement one of them. To do the test I have created 100.000 empty tables containing single integer column and no indexes and when ran SELECT * FROM tableN in the loop. Each table in such case is accessed only once and on any but first run each access would require table replacement in table cache based on LRU logic. MySQL Sandbox helped me to test this with different servers easily. I did test on CentOS 5.3, Xeon E5405, 16GB RAM and EXT3 file system on the SATA hard drive. MySQL 5.0.85 Created 100.000 tables in around 3min 40 sec which is about 450 tables/sec This indicates the fsync is lying on this test system as default sync_frm option is used. With default table_cache=64 accessing all tables take 12 sec which is almost 8500 tables/sec which is a great speed. We can note significant writes to the disk during this read-only benchmark. Why ? Because for MyISAM tables table header has to be modified each time the table is opened. In this case the performance was so great because all 100.000 tables data (first block of index) was placed close by on disk as well as fully cached which made updates to headers very slow. In the production systems with table headers not in OS cache you often will see significantly low numbers 100 or less. With significantly larger table_cache=16384 (and appropriately adjusted number of open files) the same operation takes 660 seconds which is 151 tables/sec which is around 50 times slower. Wow. This is the slow down. We can see the load becomes very CPU bound in this case and it looks like some of the table_cache algorithms do not scale well. The absolute numbers are also very interesting 151 tables/sec is not that bad if you look at it as an absolute number. So if you tune table cache is normal case and is able to bring down your miss rate (opened_tables) to 10/sec or less by using large table_cache you should do so. However if you have so many tables you still see 100+ misses/sec while your data (at least table headers) is well cached so the cost of table cache miss is not very high, you may be better of with significantly reduced table cache size. The next step for me was to see if the problem was fixed in MySQL 5.1 in this version table_cache was significantly redone and split in table_open_cache and table_definition_cache and I assumed the behavior may be different as well. MySQL 5.1.40 I started testing with default table_open_cache=64 and table_definition_cache=256 the read took about 12 seconds very close to MySQL 5.0.85. As I increased table_definition_cache to 16384 result remained the same so this variable is not causing the bottleneck. However increasing table_open_cache to 16384 causes scan to take about 780 sec which is a bit worse than MySQL 5.0.85. So the problem is not fixed in MySQL 5.1, lets see how MySQL 5.4 behaves. MySQL 5.4.2 MySQL 5.4.2 has higher default table_open_cache so I took it down to 64 so we can compare apples to apples. It performs same as MySQL 5.0 and MySQL 5.1 with small table cache. With table_open_cache increased to 16384 the test took 750 seconds so the problem exists in MySQL 5.4 as well. So the problem is real and it is not fixed even in Performance focused MySQL 5.4. As we can see large table_cache (or table_open_cache_ values indeed can cause significant performance problems. Interesting enough Innodb has a very similar task of managing its own cache of file descriptors (set by innodb_open_files) As the time allows I should test if Heikki knows how to implement LRU properly so it does not have problem with large number. Well see. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v4.0.0)

1 0

[Maria-developers] WL#72 Deleted (by Serg): Fix table_cache negative scalability
by worklog-noreply＠askmonty.org 28 Jun '10

28 Jun '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Fix table_cache negative scalability CREATION DATE..: Fri, 18 Dec 2009, 16:31 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 72 (http://askmonty.org/worklog/?tid=72) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Fix the problem described in this blog entry: http://www.mysqlperformanceblog.com/2009/11/16/table_cache-negative-scalabi… I attempted to paste the contents of the blog here, but worklog didn't accept the text. You have to read the blog entry. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v4.0.0)

1 0

[Maria-developers] WL#73 Deleted (by Serg): Fix table_cache negative scalability
by worklog-noreply＠askmonty.org 28 Jun '10

28 Jun '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Fix table_cache negative scalability CREATION DATE..: Fri, 18 Dec 2009, 16:31 SUPERVISOR.....: Bothorsen IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-Sprint TASK ID........: 73 (http://askmonty.org/worklog/?tid=73) VERSION........: WorkLog-3.4 STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Fix the problem described in this blog entry: http://www.mysqlperformanceblog.com/2009/11/16/table_cache-negative-scalabi… You can read the blog, or the text below. --- quoted text --- November 16, 2009 table_cache negative scalability Posted by peter | Vote on Planet MySQL Couple of months ago there was a post by FreshBooks on getting great performance improvements by lowering table_cache variable. So I decided to investigate what is really happening here. The common sense approach to tuning caches is to get them as large as you can if you have enough resources (such as memory). With MySQL common sense however does not always works weve seen performance issues with large query_cache_size also sort_buffer_size and read_buffer_size may not give you better performance if you increase them. I found this also applies to some other buffers. Even though having previous experience of surprised behavior I did not expect such a table_cache issue the LRU for cache management is classics and there are scalable algorithms to deal with it. I would expect Monty to implement one of them. To do the test I have created 100.000 empty tables containing single integer column and no indexes and when ran SELECT * FROM tableN in the loop. Each table in such case is accessed only once and on any but first run each access would require table replacement in table cache based on LRU logic. MySQL Sandbox helped me to test this with different servers easily. I did test on CentOS 5.3, Xeon E5405, 16GB RAM and EXT3 file system on the SATA hard drive. MySQL 5.0.85 Created 100.000 tables in around 3min 40 sec which is about 450 tables/sec This indicates the fsync is lying on this test system as default sync_frm option is used. With default table_cache=64 accessing all tables take 12 sec which is almost 8500 tables/sec which is a great speed. We can note significant writes to the disk during this read-only benchmark. Why ? Because for MyISAM tables table header has to be modified each time the table is opened. In this case the performance was so great because all 100.000 tables data (first block of index) was placed close by on disk as well as fully cached which made updates to headers very slow. In the production systems with table headers not in OS cache you often will see significantly low numbers 100 or less. With significantly larger table_cache=16384 (and appropriately adjusted number of open files) the same operation takes 660 seconds which is 151 tables/sec which is around 50 times slower. Wow. This is the slow down. We can see the load becomes very CPU bound in this case and it looks like some of the table_cache algorithms do not scale well. The absolute numbers are also very interesting 151 tables/sec is not that bad if you look at it as an absolute number. So if you tune table cache is normal case and is able to bring down your miss rate (opened_tables) to 10/sec or less by using large table_cache you should do so. However if you have so many tables you still see 100+ misses/sec while your data (at least table headers) is well cached so the cost of table cache miss is not very high, you may be better of with significantly reduced table cache size. The next step for me was to see if the problem was fixed in MySQL 5.1 in this version table_cache was significantly redone and split in table_open_cache and table_definition_cache and I assumed the behavior may be different as well. MySQL 5.1.40 I started testing with default table_open_cache=64 and table_definition_cache=256 the read took about 12 seconds very close to MySQL 5.0.85. As I increased table_definition_cache to 16384 result remained the same so this variable is not causing the bottleneck. However increasing table_open_cache to 16384 causes scan to take about 780 sec which is a bit worse than MySQL 5.0.85. So the problem is not fixed in MySQL 5.1, lets see how MySQL 5.4 behaves. MySQL 5.4.2 MySQL 5.4.2 has higher default table_open_cache so I took it down to 64 so we can compare apples to apples. It performs same as MySQL 5.0 and MySQL 5.1 with small table cache. With table_open_cache increased to 16384 the test took 750 seconds so the problem exists in MySQL 5.4 as well. So the problem is real and it is not fixed even in Performance focused MySQL 5.4. As we can see large table_cache (or table_open_cache_ values indeed can cause significant performance problems. Interesting enough Innodb has a very similar task of managing its own cache of file descriptors (set by innodb_open_files) As the time allows I should test if Heikki knows how to implement LRU properly so it does not have problem with large number. Well see. ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v4.0.0)

1 0

[Maria-developers] WL#78 Deleted (by Serg): INSTALL PLUGIN *
by worklog-noreply＠askmonty.org 28 Jun '10

28 Jun '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: INSTALL PLUGIN * CREATION DATE..: Tue, 09 Feb 2010, 18:10 SUPERVISOR.....: Sergei IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-RawIdeaBin TASK ID........: 78 (http://askmonty.org/worklog/?tid=78) VERSION........: WorkLog-3.4 STATUS.........: Cancelled PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 10 (hours remain) ORIG. ESTIMATE.: 10 PROGRESS NOTES: -=-=(Serg - Mon, 08 Mar 2010, 20:13)=-=- High Level Description modified. --- /tmp/wklog.78.old.32207 2010-03-08 20:13:06.000000000 +0000 +++ /tmp/wklog.78.new.32207 2010-03-08 20:13:06.000000000 +0000 @@ -6,3 +6,5 @@ INSTALL PLUGIN * SONAME xxx would be a more convenient way to install everything at once. + +cancelled, as a duplicate of mwl:77 -=-=(Serg - Mon, 08 Mar 2010, 20:12)=-=- Status updated. --- /tmp/wklog.78.old.32035 2010-03-08 20:12:39.000000000 +0000 +++ /tmp/wklog.78.new.32035 2010-03-08 20:12:39.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Cancelled DESCRIPTION: InnoDB, XtraDB, PBXT (at least) come with a storage engine plugin and many information_schema plugins in one .so file. Currently one needs to install them all one by one. INSTALL PLUGIN * SONAME xxx would be a more convenient way to install everything at once. cancelled, as a duplicate of mwl:77 ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v4.0.0)

1 0

[Maria-developers] WL#78 Deleted (by Serg): INSTALL PLUGIN *
by worklog-noreply＠askmonty.org 28 Jun '10

28 Jun '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: INSTALL PLUGIN * CREATION DATE..: Tue, 09 Feb 2010, 18:10 SUPERVISOR.....: Sergei IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-RawIdeaBin TASK ID........: 78 (http://askmonty.org/worklog/?tid=78) VERSION........: WorkLog-3.4 STATUS.........: Cancelled PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 10 (hours remain) ORIG. ESTIMATE.: 10 PROGRESS NOTES: -=-=(Serg - Mon, 08 Mar 2010, 20:13)=-=- High Level Description modified. --- /tmp/wklog.78.old.32207 2010-03-08 20:13:06.000000000 +0000 +++ /tmp/wklog.78.new.32207 2010-03-08 20:13:06.000000000 +0000 @@ -6,3 +6,5 @@ INSTALL PLUGIN * SONAME xxx would be a more convenient way to install everything at once. + +cancelled, as a duplicate of mwl:77 -=-=(Serg - Mon, 08 Mar 2010, 20:12)=-=- Status updated. --- /tmp/wklog.78.old.32035 2010-03-08 20:12:39.000000000 +0000 +++ /tmp/wklog.78.new.32035 2010-03-08 20:12:39.000000000 +0000 @@ -1 +1 @@ -Un-Assigned +Cancelled DESCRIPTION: InnoDB, XtraDB, PBXT (at least) come with a storage engine plugin and many information_schema plugins in one .so file. Currently one needs to install them all one by one. INSTALL PLUGIN * SONAME xxx would be a more convenient way to install everything at once. cancelled, as a duplicate of mwl:77 ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v4.0.0)

1 0

[Maria-developers] WL#75 Deleted (by Serg): Extend build to create a shared libmysqld.so library
by worklog-noreply＠askmonty.org 28 Jun '10

28 Jun '10

----------------------------------------------------------------------- WORKLOG TASK -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- TASK...........: Extend build to create a shared libmysqld.so library CREATION DATE..: Fri, 22 Jan 2010, 09:39 SUPERVISOR.....: Knielsen IMPLEMENTOR....: COPIES TO......: CATEGORY.......: Server-RawIdeaBin TASK ID........: 75 (http://askmonty.org/worklog/?tid=75) VERSION........: Server-9.x STATUS.........: Un-Assigned PRIORITY.......: 60 WORKED HOURS...: 0 ESTIMATE.......: 0 (hours remain) ORIG. ESTIMATE.: 0 PROGRESS NOTES: DESCRIPTION: Currently, the embedded library libmysqld is only built as a static library, libmysqld.a. However, there is also a need for a shared embedded library, libmysqld.so. A good example is Amarok, which is now using MySQL (and by default an embedded libmysqld) for storing the user's music collection. Amarok is designed to load a number of modules as .so plugins, and the code using libmysqld is one such plugin. Any code that is to be loaded as a shared object on Linux must be built with -fPIC (position independent code). Any library used must thus also be built with -fPIC and preferably itself be linked statically. Amarok is a widely used application (end-user desktop). It could be a good leverage for making libmysqld more popular eg. in distros. However, currently the distros need to resort to various hacks to make things work with libmysqld and Amarok. Some links: Fedora patches .spec to add -fPIC in the build, extract all objects from libmysqld.a, and re-link them as libmysqld.so. http://cvs.fedoraproject.org/viewvc/devel/mysql/mysql.spec?r1=1.108&r2=1.109 Gentoo apparently have a patch for MySQL to build libmysqld.so: http://bugs.gentoo.org/attachment.cgi?id=188057 Debian seems to suggest building both libmysqld.a and libmysqld_pic.a, the latter to be used for shared objects linking with embedded server: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=508406#52 It would be nice if the main build system was able to build properly libmysqld.so, so different distros would not need to resort to different hacks to get things working. The normal way to build both .a and .so as far as I know is to use libtool; it will then build each object twice (with and without -fPIC) if needed. This one might want to make optional to reduce build times. It would also need to be done for each storage engine. An alternative would be to build everything with -fPIC. This should probably be optional also, as on some architectures (ELF x86 32-bit), there is some speed penalty for -fPIC. The libmysqld.so would then be made only in this case. Distro packages could do a separate build with -fPIC to make libmysqld.so (to not get -fPIC into the main server code). There is a MySQL bug for this: http://bugs.mysql.com/bug.php?id=39288 ESTIMATED WORK TIME ESTIMATED COMPLETION DATE ----------------------------------------------------------------------- WorkLog (v4.0.0)

1 0