#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*) ¶m,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(¶m, 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(¶m, 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: