diff options
Diffstat (limited to 'sql/opt_range.cc')
| -rw-r--r-- | sql/opt_range.cc | 188 |
1 files changed, 137 insertions, 51 deletions
diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 05575e2744b..52e8d5d61c2 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -708,7 +708,8 @@ static TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge, double read_time); static -TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree); +TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree, + double read_time); static double get_index_only_read_time(const PARAM* param, ha_rows records, int keynr); @@ -2049,7 +2050,7 @@ public: class TRP_GROUP_MIN_MAX : public TABLE_READ_PLAN { private: - bool have_min, have_max; + bool have_min, have_max, have_agg_distinct; KEY_PART_INFO *min_max_arg_part; uint group_prefix_len; uint used_key_parts; @@ -2061,11 +2062,13 @@ private: SEL_TREE *range_tree; /* Represents all range predicates in the query. */ SEL_ARG *index_tree; /* The SEL_ARG sub-tree corresponding to index_info. */ uint param_idx; /* Index of used key in param->key. */ - /* Number of records selected by the ranges in index_tree. */ + bool is_index_scan; /* Use index_next() instead of random read */ public: + /* Number of records selected by the ranges in index_tree. */ ha_rows quick_prefix_records; public: - TRP_GROUP_MIN_MAX(bool have_min_arg, bool have_max_arg, + TRP_GROUP_MIN_MAX(bool have_min_arg, bool have_max_arg, + bool have_agg_distinct_arg, KEY_PART_INFO *min_max_arg_part_arg, uint group_prefix_len_arg, uint used_key_parts_arg, uint group_key_parts_arg, KEY *index_info_arg, @@ -2074,11 +2077,12 @@ public: SEL_TREE *tree_arg, SEL_ARG *index_tree_arg, uint param_idx_arg, ha_rows quick_prefix_records_arg) : have_min(have_min_arg), have_max(have_max_arg), + have_agg_distinct(have_agg_distinct_arg), min_max_arg_part(min_max_arg_part_arg), group_prefix_len(group_prefix_len_arg), used_key_parts(used_key_parts_arg), group_key_parts(group_key_parts_arg), index_info(index_info_arg), index(index_arg), key_infix_len(key_infix_len_arg), range_tree(tree_arg), - index_tree(index_tree_arg), param_idx(param_idx_arg), + index_tree(index_tree_arg), param_idx(param_idx_arg), is_index_scan(FALSE), quick_prefix_records(quick_prefix_records_arg) { if (key_infix_len) @@ -2088,6 +2092,7 @@ public: QUICK_SELECT_I *make_quick(PARAM *param, bool retrieve_full_rows, MEM_ROOT *parent_alloc); + void use_index_scan() { is_index_scan= TRUE; } }; @@ -2349,7 +2354,7 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, Try to construct a QUICK_GROUP_MIN_MAX_SELECT. Notice that it can be constructed no matter if there is a range tree. */ - group_trp= get_best_group_min_max(¶m, tree); + group_trp= get_best_group_min_max(¶m, tree, best_read_time); if (group_trp) { param.table->quick_condition_rows= min(group_trp->records, @@ -9048,15 +9053,10 @@ cost_group_min_max(TABLE* table, KEY *index_info, uint used_key_parts, double *read_cost, ha_rows *records); -/* +/** Test if this access method is applicable to a GROUP query with MIN/MAX functions, and if so, construct a new TRP object. - SYNOPSIS - get_best_group_min_max() - param Parameter from test_quick_select - sel_tree Range tree generated by get_mm_tree - DESCRIPTION Test whether a query can be computed via a QUICK_GROUP_MIN_MAX_SELECT. Queries computable via a QUICK_GROUP_MIN_MAX_SELECT must satisfy the @@ -9167,17 +9167,16 @@ cost_group_min_max(TABLE* table, KEY *index_info, uint used_key_parts, - Lift the limitation in condition (B3), that is, make this access method applicable to ROLLUP queries. - RETURN - If mem_root != NULL - - valid TRP_GROUP_MIN_MAX object if this QUICK class can be used for - the query - - NULL o/w. - If mem_root == NULL - - NULL + @param param Parameter from test_quick_select + @param sel_tree Range tree generated by get_mm_tree + @param read_time Best read time so far (=table/index scan time) + @return table read plan + @retval NULL Loose index scan not applicable or mem_root == NULL + @retval !NULL Loose index scan table read plan */ static TRP_GROUP_MIN_MAX * -get_best_group_min_max(PARAM *param, SEL_TREE *tree) +get_best_group_min_max(PARAM *param, SEL_TREE *tree, double read_time) { THD *thd= param->thd; JOIN *join= thd->lex->current_select->join; @@ -9198,25 +9197,33 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) ORDER *tmp_group; Item *item; Item_field *item_field; + bool is_agg_distinct; + List<Item_field> agg_distinct_flds; + DBUG_ENTER("get_best_group_min_max"); /* Perform few 'cheap' tests whether this access method is applicable. */ if (!join) DBUG_RETURN(NULL); /* This is not a select statement. */ if ((join->tables != 1) || /* The query must reference one table. */ - ((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */ - (!join->select_distinct)) || (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */ DBUG_RETURN(NULL); if (table->s->keys == 0) /* There are no indexes to use. */ DBUG_RETURN(NULL); - /* Analyze the query in more detail. */ - List_iterator<Item> select_items_it(join->fields_list); - /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/ if (join->make_sum_func_list(join->all_fields, join->fields_list, 1)) DBUG_RETURN(NULL); + + List_iterator<Item> select_items_it(join->fields_list); + is_agg_distinct = is_indexed_agg_distinct(join, &agg_distinct_flds); + + if ((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */ + (!join->select_distinct) && + !is_agg_distinct) + DBUG_RETURN(NULL); + /* Analyze the query in more detail. */ + if (join->sum_funcs[0]) { Item_sum *min_max_item; @@ -9227,6 +9234,10 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) have_min= TRUE; else if (min_max_item->sum_func() == Item_sum::MAX_FUNC) have_max= TRUE; + else if (min_max_item->sum_func() == Item_sum::COUNT_DISTINCT_FUNC || + min_max_item->sum_func() == Item_sum::SUM_DISTINCT_FUNC || + min_max_item->sum_func() == Item_sum::AVG_DISTINCT_FUNC) + continue; else DBUG_RETURN(NULL); @@ -9243,13 +9254,12 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) DBUG_RETURN(NULL); } } - /* Check (SA5). */ if (join->select_distinct) { while ((item= select_items_it++)) { - if (item->type() != Item::FIELD_ITEM) + if (item->real_item()->type() != Item::FIELD_ITEM) DBUG_RETURN(NULL); } } @@ -9257,7 +9267,7 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) /* Check (GA4) - that there are no expressions among the group attributes. */ for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next) { - if ((*tmp_group->item)->type() != Item::FIELD_ITEM) + if ((*tmp_group->item)->real_item()->type() != Item::FIELD_ITEM) DBUG_RETURN(NULL); } @@ -9276,6 +9286,7 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) uint best_param_idx= 0; const uint pk= param->table->s->primary_key; + uint max_key_part; SEL_ARG *cur_index_tree= NULL; ha_rows cur_quick_prefix_records= 0; uint cur_param_idx=MAX_KEY; @@ -9329,6 +9340,8 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) } } + max_key_part= 0; + used_key_parts_map.clear_all(); /* Check (GA1) for GROUP BY queries. */ @@ -9352,6 +9365,8 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) { cur_group_prefix_len+= cur_part->store_length; ++cur_group_key_parts; + max_key_part= cur_part - cur_index_info->key_part + 1; + used_key_parts_map.set_bit(max_key_part); } else goto next_index; @@ -9365,14 +9380,26 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) Later group_fields_array of ORDER objects is used to convert the query to a GROUP query. */ - else if (join->select_distinct) + if ((!join->group_list && join->select_distinct) || + is_agg_distinct) { - select_items_it.rewind(); - used_key_parts_map.clear_all(); - uint max_key_part= 0; - while ((item= select_items_it++)) + if (!is_agg_distinct) { - item_field= (Item_field*) item; /* (SA5) already checked above. */ + select_items_it.rewind(); + } + + List_iterator<Item_field> agg_distinct_flds_it (agg_distinct_flds); + while (NULL != (item = (is_agg_distinct ? + (Item *) agg_distinct_flds_it++ : select_items_it++))) + { + /* (SA5) already checked above. */ + item_field= (Item_field*) item->real_item(); + DBUG_ASSERT(item->real_item()->type() == Item::FIELD_ITEM); + + /* not doing loose index scan for derived tables */ + if (!item_field->field) + goto next_index; + /* Find the order of the key part in the index. */ key_part_nr= get_field_keypart(cur_index_info, item_field->field); /* @@ -9381,7 +9408,8 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) */ if (used_key_parts_map.is_set(key_part_nr)) continue; - if (key_part_nr < 1 || key_part_nr > join->fields_list.elements) + if (key_part_nr < 1 || + (!is_agg_distinct && key_part_nr > join->fields_list.elements)) goto next_index; cur_part= cur_index_info->key_part + key_part_nr - 1; cur_group_prefix_len+= cur_part->store_length; @@ -9401,10 +9429,6 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) if (all_parts != cur_parts) goto next_index; } - else - { - DBUG_ASSERT(FALSE); - } /* Check (SA2). */ if (min_max_arg_item) @@ -9558,7 +9582,8 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) /* The query passes all tests, so construct a new TRP object. */ read_plan= new (param->mem_root) - TRP_GROUP_MIN_MAX(have_min, have_max, min_max_arg_part, + TRP_GROUP_MIN_MAX(have_min, have_max, is_agg_distinct, + min_max_arg_part, group_prefix_len, used_key_parts, group_key_parts, index_info, index, key_infix_len, @@ -9572,6 +9597,11 @@ get_best_group_min_max(PARAM *param, SEL_TREE *tree) read_plan->read_cost= best_read_cost; read_plan->records= best_records; + if (read_time < best_read_cost && is_agg_distinct) + { + read_plan->read_cost= 0; + read_plan->use_index_scan(); + } DBUG_PRINT("info", ("Returning group min/max plan: cost: %g, records: %lu", @@ -10077,11 +10107,12 @@ TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool retrieve_full_rows, quick= new QUICK_GROUP_MIN_MAX_SELECT(param->table, param->thd->lex->current_select->join, - have_min, have_max, min_max_arg_part, + have_min, have_max, + have_agg_distinct, min_max_arg_part, group_prefix_len, group_key_parts, used_key_parts, index_info, index, read_cost, records, key_infix_len, - key_infix, parent_alloc); + key_infix, parent_alloc, is_index_scan); if (!quick) DBUG_RETURN(NULL); @@ -10161,6 +10192,9 @@ TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool retrieve_full_rows, key_infix_len Length of the key infix appended to the group prefix key_infix Infix of constants from equality predicates parent_alloc Memory pool for this and quick_prefix_select data + is_index_scan get the next different key not by jumping on it via + index read, but by scanning until the end of the + rows with equal key value. RETURN None @@ -10168,20 +10202,22 @@ TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool retrieve_full_rows, QUICK_GROUP_MIN_MAX_SELECT:: QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join_arg, bool have_min_arg, - bool have_max_arg, + bool have_max_arg, bool have_agg_distinct_arg, KEY_PART_INFO *min_max_arg_part_arg, uint group_prefix_len_arg, uint group_key_parts_arg, uint used_key_parts_arg, KEY *index_info_arg, uint use_index, double read_cost_arg, ha_rows records_arg, uint key_infix_len_arg, - uchar *key_infix_arg, MEM_ROOT *parent_alloc) + uchar *key_infix_arg, MEM_ROOT *parent_alloc, + bool is_index_scan_arg) :join(join_arg), index_info(index_info_arg), group_prefix_len(group_prefix_len_arg), group_key_parts(group_key_parts_arg), have_min(have_min_arg), - have_max(have_max_arg), seen_first_key(FALSE), - min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg), - key_infix_len(key_infix_len_arg), min_functions_it(NULL), - max_functions_it(NULL) + have_max(have_max_arg), have_agg_distinct(have_agg_distinct_arg), + seen_first_key(FALSE), min_max_arg_part(min_max_arg_part_arg), + key_infix(key_infix_arg), key_infix_len(key_infix_len_arg), + min_functions_it(NULL), max_functions_it(NULL), + is_index_scan(is_index_scan_arg) { head= table; file= head->file; @@ -10744,6 +10780,56 @@ int QUICK_GROUP_MIN_MAX_SELECT::next_max() } +/** + Find the next different key value by skiping all the rows with the same key + value. + + Implements a specialized loose index access method for queries + containing aggregate functions with distinct of the form: + SELECT [SUM|COUNT|AVG](DISTINCT a,...) FROM t + This method comes to replace the index scan + Unique class + (distinct selection) for loose index scan that visits all the rows of a + covering index instead of jumping in the begining of each group. + TODO: Placeholder function. To be replaced by a handler API call + + @param is_index_scan hint to use index scan instead of random index read + to find the next different value. + @param file table handler + @param key_part group key to compare + @param record row data + @param group_prefix current key prefix data + @param group_prefix_len length of the current key prefix data + @param group_key_parts number of the current key prefix columns + @return status + @retval 0 success + @retval !0 failure +*/ + +static int index_next_different (bool is_index_scan, handler *file, + KEY_PART_INFO *key_part, uchar * record, + const uchar * group_prefix, + uint group_prefix_len, + uint group_key_parts) +{ + if (is_index_scan) + { + int result= 0; + + while (!key_cmp (key_part, group_prefix, group_prefix_len)) + { + result= file->index_next(record); + if (result) + return(result); + } + return result; + } + else + return file->index_read_map(record, group_prefix, + make_prev_keypart_map(group_key_parts), + HA_READ_AFTER_KEY); +} + + /* Determine the prefix of the next group. @@ -10790,9 +10876,9 @@ int QUICK_GROUP_MIN_MAX_SELECT::next_prefix() else { /* Load the first key in this group into record. */ - result= file->index_read_map(record, group_prefix, - make_prev_keypart_map(group_key_parts), - HA_READ_AFTER_KEY); + result= index_next_different (is_index_scan, file, index_info->key_part, + record, group_prefix, group_prefix_len, + group_key_parts); if (result) DBUG_RETURN(result); } |