diff options
Diffstat (limited to 'sql')
| -rw-r--r-- | sql/field.cc | 70 | ||||
| -rw-r--r-- | sql/field.h | 36 | ||||
| -rw-r--r-- | sql/item_cmpfunc.cc | 20 | ||||
| -rw-r--r-- | sql/item_cmpfunc.h | 4 | ||||
| -rw-r--r-- | sql/opt_range.cc | 249 | ||||
| -rw-r--r-- | sql/opt_range.h | 2 | ||||
| -rw-r--r-- | sql/opt_range_mrr.cc | 6 | ||||
| -rw-r--r-- | sql/opt_subselect.cc | 2 | ||||
| -rw-r--r-- | sql/opt_subselect.h | 1 | ||||
| -rw-r--r-- | sql/sql_class.h | 4 | ||||
| -rw-r--r-- | sql/sql_priv.h | 1 | ||||
| -rw-r--r-- | sql/sql_select.cc | 376 | ||||
| -rw-r--r-- | sql/sql_select.h | 6 | ||||
| -rw-r--r-- | sql/sql_statistics.cc | 432 | ||||
| -rw-r--r-- | sql/sql_statistics.h | 194 | ||||
| -rw-r--r-- | sql/sys_vars.cc | 37 | ||||
| -rw-r--r-- | sql/table.cc | 14 | ||||
| -rw-r--r-- | sql/table.h | 8 | ||||
| -rw-r--r-- | sql/uniques.cc | 40 |
19 files changed, 1401 insertions, 101 deletions
diff --git a/sql/field.cc b/sql/field.cc index e2ec9d35707..103d868d834 100644 --- a/sql/field.cc +++ b/sql/field.cc @@ -1273,6 +1273,20 @@ out_of_range: return 1; } + +double Field_num::middle_point_pos(Field *min, Field *max) +{ + double n, d; + n= val_real() - min->val_real(); + if (n < 0) + return 0.0; + d= max->val_real() - min->val_real(); + if (d <= 0) + return 1.0; + return min(n/d, 1.0); +} + + /** Process decimal library return codes and issue warnings for overflow and truncation. @@ -1344,6 +1358,8 @@ Field::Field(uchar *ptr_arg,uint32 length_arg,uchar *null_ptr_arg, comment.length=0; field_index= 0; is_stat_field= FALSE; + cond_selectivity= 1.0; + next_equal_field= NULL; } @@ -6167,6 +6183,47 @@ int Field_str::store(double nr) return store(buff, length, &my_charset_numeric); } +static +inline ulonglong char_prefix_to_ulonglong(uchar *src) +{ + uint sz= sizeof(ulonglong); + for (uint i= 0; i < sz/2; i++) + { + uchar tmp= src[i]; + src[i]= src[sz-1-i]; + src[sz-1-i]= tmp; + } + return uint8korr(src); +} + +double Field_str::middle_point_pos(Field *min, Field *max) +{ + uchar mp_prefix[sizeof(ulonglong)]; + uchar minp_prefix[sizeof(ulonglong)]; + uchar maxp_prefix[sizeof(ulonglong)]; + ulonglong mp, minp, maxp; + my_strnxfrm(charset(), mp_prefix, sizeof(mp), + ptr + length_size(), + data_length()); + my_strnxfrm(charset(), minp_prefix, sizeof(minp), + min->ptr + length_size(), + min->data_length()); + my_strnxfrm(charset(), maxp_prefix, sizeof(maxp), + max->ptr + length_size(), + max->data_length()); + mp= char_prefix_to_ulonglong(mp_prefix); + minp= char_prefix_to_ulonglong(minp_prefix); + maxp= char_prefix_to_ulonglong(maxp_prefix); + double n, d; + n= mp - minp; + if (n < 0) + return 0.0; + d= maxp - minp; + if (d <= 0) + return 1.0; + return min(n/d, 1.0); +} + uint Field::is_equal(Create_field *new_field) { @@ -8378,6 +8435,19 @@ my_decimal *Field_bit::val_decimal(my_decimal *deciaml_value) } +double Field_bit::middle_point_pos(Field *min, Field *max) +{ + double n, d; + n= val_real() - min->val_real(); + if (n < 0) + return 0.0; + d= max->val_real() - min->val_real(); + if (d <= 0) + return 1.0; + return min(n/d, 1.0); +} + + /* Compare two bit fields using pointers within the record. SYNOPSIS diff --git a/sql/field.h b/sql/field.h index d03479bbd06..550ae9d65b9 100644 --- a/sql/field.h +++ b/sql/field.h @@ -220,7 +220,23 @@ public: */ bool is_created_from_null_item; - bool is_stat_field; /* TRUE in Field objects created for column min/max values */ + /* TRUE in Field objects created for column min/max values */ + bool is_stat_field; + + /* + Selectivity of the range condition over this field. + When calculating this selectivity a range predicate + is taken into account only if: + - it is extracted from the WHERE clause + - it depends only on the table the field belongs to + */ + double cond_selectivity; + + /* + The next field in the class of equal fields at the top AND level + of the WHERE clause + */ + Field *next_equal_field; /* This structure is used for statistical data on the column @@ -456,6 +472,10 @@ public: } return update_fl; } + virtual void store_field_value(uchar *val, uint len) + { + memcpy(ptr, val, len); + } virtual uint decimals() const { return 0; } /* Caller beware: sql_type can change str.Ptr, so check @@ -703,6 +723,11 @@ public: virtual bool hash_join_is_possible() { return TRUE; } virtual bool eq_cmp_as_binary() { return TRUE; } + virtual double middle_point_pos(Field *min, Field *max) + { + return (double) 1.0; + } + friend int cre_myisam(char * name, register TABLE *form, uint options, ulonglong auto_increment_value); friend class Copy_field; @@ -821,6 +846,7 @@ public: bool get_int(CHARSET_INFO *cs, const char *from, uint len, longlong *rnd, ulonglong unsigned_max, longlong signed_min, longlong signed_max); + double middle_point_pos(Field *min, Field *max); }; @@ -866,6 +892,8 @@ public: virtual bool str_needs_quotes() { return TRUE; } uint is_equal(Create_field *new_field); bool eq_cmp_as_binary() { return test(flags & BINARY_FLAG); } + virtual uint length_size() { return 0; } + double middle_point_pos(Field *min, Field *max); }; /* base class for Field_string, Field_varstring and Field_blob */ @@ -1894,6 +1922,7 @@ public: uint new_null_bit); uint is_equal(Create_field *new_field); void hash(ulong *nr, ulong *nr2); + uint length_size() { return length_bytes; } private: int do_save_field_metadata(uchar *first_byte); }; @@ -2275,6 +2304,11 @@ public: } return update_fl; } + void store_field_value(uchar *val, uint len) + { + store(*((longlong *)val), TRUE); + } + double middle_point_pos(Field *min, Field *max); void get_image(uchar *buff, uint length, CHARSET_INFO *cs) { get_key_image(buff, length, itRAW); } void set_image(const uchar *buff,uint length, CHARSET_INFO *cs) diff --git a/sql/item_cmpfunc.cc b/sql/item_cmpfunc.cc index 6f10e84a5f5..b5b143a2448 100644 --- a/sql/item_cmpfunc.cc +++ b/sql/item_cmpfunc.cc @@ -5568,7 +5568,8 @@ Item *Item_bool_rowready_func2::negated_item() */ Item_equal::Item_equal(Item *f1, Item *f2, bool with_const_item) - : Item_bool_func(), eval_item(0), cond_false(0), context_field(NULL) + : Item_bool_func(), eval_item(0), cond_false(0), context_field(NULL), + link_equal_fields(FALSE) { const_item_cache= 0; with_const= with_const_item; @@ -5592,7 +5593,8 @@ Item_equal::Item_equal(Item *f1, Item *f2, bool with_const_item) */ Item_equal::Item_equal(Item_equal *item_equal) - : Item_bool_func(), eval_item(0), cond_false(0), context_field(NULL) + : Item_bool_func(), eval_item(0), cond_false(0), context_field(NULL), + link_equal_fields(FALSE) { const_item_cache= 0; List_iterator_fast<Item> li(item_equal->equal_items); @@ -5918,6 +5920,9 @@ bool Item_equal::fix_fields(THD *thd, Item **ref) DBUG_ASSERT(fixed == 0); Item_equal_fields_iterator it(*this); Item *item; + Field *first_equal_field; + Field *last_equal_field; + Field *prev_equal_field= NULL; not_null_tables_cache= used_tables_cache= 0; const_item_cache= 0; while ((item= it++)) @@ -5931,7 +5936,18 @@ bool Item_equal::fix_fields(THD *thd, Item **ref) maybe_null= 1; if (!item->get_item_equal()) item->set_item_equal(this); + if (link_equal_fields && item->real_item()->type() == FIELD_ITEM) + { + last_equal_field= ((Item_field *) (item->real_item()))->field; + if (!prev_equal_field) + first_equal_field= last_equal_field; + else + prev_equal_field->next_equal_field= last_equal_field; + prev_equal_field= last_equal_field; + } } + if (prev_equal_field && last_equal_field != first_equal_field) + last_equal_field->next_equal_field= first_equal_field; fix_length_and_dec(); fixed= 1; return FALSE; diff --git a/sql/item_cmpfunc.h b/sql/item_cmpfunc.h index 4ca31e01df9..81598ba96c8 100644 --- a/sql/item_cmpfunc.h +++ b/sql/item_cmpfunc.h @@ -1737,6 +1737,8 @@ class Item_equal: public Item_bool_func */ Item_field *context_field; + bool link_equal_fields; + public: COND_EQUAL *upper_levels; /* multiple equalities of upper and levels */ @@ -1774,6 +1776,8 @@ public: CHARSET_INFO *compare_collation(); void set_context_field(Item_field *ctx_field) { context_field= ctx_field; } + void set_link_equal_fields(bool flag) { link_equal_fields= flag; } + friend class Item_equal_fields_iterator; friend class Item_equal_iterator<List_iterator_fast,Item>; friend class Item_equal_iterator<List_iterator,Item>; friend Item *eliminate_item_equal(COND *cond, COND_EQUAL *upper_levels, diff --git a/sql/opt_range.cc b/sql/opt_range.cc index 955250905e8..5cadd26da6e 100644 --- a/sql/opt_range.cc +++ b/sql/opt_range.cc @@ -117,6 +117,7 @@ #include "records.h" // init_read_record, end_read_record #include <m_ctype.h> #include "sql_select.h" +#include "sql_statistics.h" #include "filesort.h" // filesort_free_buffers #ifndef EXTRA_DEBUG @@ -3218,6 +3219,254 @@ int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use, } /**************************************************************************** + * Condition selectivity module + ****************************************************************************/ + +static +bool create_key_parts_for_pseudo_indexes(RANGE_OPT_PARAM *param, + MY_BITMAP *used_fields) +{ + Field **field_ptr; + TABLE *table= param->table; + uint parts= 0; + + for (field_ptr= table->field; *field_ptr; field_ptr++) + { + if (bitmap_is_set(used_fields, (*field_ptr)->field_index)) + parts++; + } + + KEY_PART *key_part; + uint keys= 0; + + if (!(key_part= (KEY_PART *) alloc_root(param->mem_root, + sizeof(KEY_PART) * parts))) + return TRUE; + + param->key_parts= key_part; + + for (field_ptr= table->field; *field_ptr; field_ptr++) + { + if (bitmap_is_set(used_fields, (*field_ptr)->field_index)) + { + Field *field= *field_ptr; + uint16 store_length; + key_part->key= keys; + key_part->part= 0; + key_part->length= (uint16) field->key_length(); + store_length= key_part->length; + if (field->real_maybe_null()) + store_length+= HA_KEY_NULL_LENGTH; + if (field->real_type() == MYSQL_TYPE_VARCHAR) + store_length+= HA_KEY_BLOB_LENGTH; + key_part->store_length= store_length; + key_part->field= field; + key_part->image_type= Field::itRAW; + key_part->flag= 0; + param->key[keys]= key_part; + keys++; + key_part++; + } + } + param->keys= keys; + param->key_parts_end= key_part; + + return FALSE; +} + + +static +double records_in_column_ranges(PARAM *param, uint idx, + SEL_ARG *tree) +{ + SEL_ARG_RANGE_SEQ seq; + KEY_MULTI_RANGE range; + range_seq_t seq_it; + double rows; + Field *field; + uint flags= 0; + double total_rows= 0; + RANGE_SEQ_IF seq_if = {NULL, sel_arg_range_seq_init, + sel_arg_range_seq_next, 0, 0}; + + /* Handle cases when we don't have a valid non-empty list of range */ + if (!tree) + return HA_POS_ERROR; + if (tree->type == SEL_ARG::IMPOSSIBLE) + return (0L); + + field= tree->field; + + seq.keyno= idx; + seq.real_keyno= MAX_KEY; + seq.param= param; + seq.start= tree; + + seq_it= seq_if.init((void *) &seq, 0, flags); + + while (!seq_if.next(seq_it, &range)) + { + key_range *min_endp, *max_endp; + min_endp= range.start_key.length? &range.start_key : NULL; + max_endp= range.end_key.length? &range.end_key : NULL; + rows= get_column_range_cardinality(field, min_endp, max_endp, + range.range_flag); + if (HA_POS_ERROR == rows) + { + total_rows= HA_POS_ERROR; + break; + } + total_rows += rows; + } + return total_rows; +} + + +bool calculate_cond_selectivity_for_table(THD *thd, TABLE *table, Item *cond) +{ + uint keynr; + uint max_quick_key_parts= 0; + MY_BITMAP *used_fields= &table->cond_set; + double table_records= table->stat_records(); + DBUG_ENTER("calculate_cond_selectivity_for_table"); + + table->cond_selectivity= 1.0; + + if (table_records == 0) + DBUG_RETURN(FALSE); + + if (thd->variables.optimizer_use_condition_selectivity > 2 && + !bitmap_is_clear_all(used_fields)) + { + PARAM param; + MEM_ROOT alloc; + SEL_TREE *tree; + SEL_ARG **key, **end; + double rows; + uint idx= 0; + + init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0, + MYF(MY_THREAD_SPECIFIC)); + param.thd= thd; + param.mem_root= &alloc; + param.old_root= thd->mem_root; + param.table= table; + param.is_ror_scan= FALSE; + + if (create_key_parts_for_pseudo_indexes(¶m, used_fields)) + goto free_alloc; + + param.prev_tables= param.read_tables= 0; + param.current_table= table->map; + param.using_real_indexes= FALSE; + param.real_keynr[0]= 0; + param.alloced_sel_args= 0; + + thd->no_errors=1; + + tree= get_mm_tree(¶m, cond); + + if (!tree) + goto free_alloc; + + table->reginfo.impossible_range= 0; + if (tree->type == SEL_TREE::IMPOSSIBLE) + { + rows= 0; + table->reginfo.impossible_range= 1; + goto free_alloc; + } + else if (tree->type == SEL_TREE::MAYBE) + { + rows= table_records; + goto free_alloc; + } + + for (key= tree->keys, end= key + param.keys; key != end; key++, idx++) + { + if (*key) + { + if ((*key)->type == SEL_ARG::IMPOSSIBLE) + { + rows= 0; + table->reginfo.impossible_range= 1; + goto free_alloc; + } + else + { + rows= records_in_column_ranges(¶m, idx, *key); + if (rows != HA_POS_ERROR) + (*key)->field->cond_selectivity= rows/table_records; + } + } + } + + for (Field **field_ptr= table->field; *field_ptr; field_ptr++) + { + Field *table_field= *field_ptr; + if (bitmap_is_set(table->read_set, table_field->field_index) && + table_field->cond_selectivity < 1.0) + table->cond_selectivity*= table_field->cond_selectivity; + } + + free_alloc: + thd->mem_root= param.old_root; + free_root(&alloc, MYF(0)); + + } + + /* Calculate the selectivity of the range conditions supported by indexes */ + + bitmap_clear_all(used_fields); + + for (keynr= 0; keynr < table->s->keys; keynr++) + { + if (table->quick_keys.is_set(keynr)) + set_if_bigger(max_quick_key_parts, table->quick_key_parts[keynr]); + } + + for (uint quick_key_parts= max_quick_key_parts; + quick_key_parts; quick_key_parts--) + { + for (keynr= 0; keynr < table->s->keys; keynr++) + { + if (table->quick_keys.is_set(keynr) && + table->quick_key_parts[keynr] == quick_key_parts) + { + uint i; + uint used_key_parts= table->quick_key_parts[keynr]; + double quick_cond_selectivity= table->quick_rows[keynr] / + table_records; + KEY *key_info= table->key_info + keynr; + KEY_PART_INFO* key_part= key_info->key_part; + for (i= 0; i < used_key_parts; i++, key_part++) + { + if (bitmap_is_set(used_fields, key_part->fieldnr-1)) + break; + bitmap_set_bit(used_fields, key_part->fieldnr-1); + } + if (i) + { + table->cond_selectivity*= quick_cond_selectivity; + if (i != used_key_parts) + { + double f1= key_info->actual_rec_per_key(i-1); + double f2= key_info->actual_rec_per_key(i); + table->cond_selectivity*= f1 / f2; + } + } + } + } + } + + DBUG_RETURN(FALSE); +} + +/**************************************************************************** + * Condition selectivity code ends + ****************************************************************************/ + +/**************************************************************************** * Partition pruning module ****************************************************************************/ #ifdef WITH_PARTITION_STORAGE_ENGINE diff --git a/sql/opt_range.h b/sql/opt_range.h index fff6e414ad9..d98bf1186e8 100644 --- a/sql/opt_range.h +++ b/sql/opt_range.h @@ -1042,6 +1042,8 @@ SQL_SELECT *make_select(TABLE *head, table_map const_tables, table_map read_tables, COND *conds, bool allow_null_cond, int *error); +bool calculate_cond_selectivity_for_table(THD *thd, TABLE *table, Item *cond); + #ifdef WITH_PARTITION_STORAGE_ENGINE bool prune_partitions(THD *thd, TABLE *table, Item *pprune_cond); void store_key_image_to_rec(Field *field, uchar *ptr, uint len); diff --git a/sql/opt_range_mrr.cc b/sql/opt_range_mrr.cc index 1f4e36178db..8029dbf000f 100644 --- a/sql/opt_range_mrr.cc +++ b/sql/opt_range_mrr.cc @@ -268,8 +268,10 @@ walk_up_n_right: range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts); if (!(cur->min_key_flag & ~NULL_RANGE) && !cur->max_key_flag && - (uint)key_tree->part+1 == seq->param->table->key_info[seq->real_keyno].key_parts && - (seq->param->table->key_info[seq->real_keyno].flags & HA_NOSAME) && + (seq->real_keyno == MAX_KEY || + ((uint)key_tree->part+1 == + seq->param->table->key_info[seq->real_keyno].key_parts && + (seq->param->table->key_info[seq->real_keyno].flags & HA_NOSAME))) && range->start_key.length == range->end_key.length && !memcmp(seq->param->min_key,seq->param->max_key,range->start_key.length)) range->range_flag= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE); diff --git a/sql/opt_subselect.cc b/sql/opt_subselect.cc index b720a0d0c92..1dc15627627 100644 --- a/sql/opt_subselect.cc +++ b/sql/opt_subselect.cc @@ -3908,7 +3908,7 @@ SJ_TMP_TABLE::create_sj_weedout_tmp_table(THD *thd) &tmpname, (uint) strlen(path)+1, &group_buff, (!using_unique_constraint ? uniq_tuple_length_arg : 0), - &bitmaps, bitmap_buffer_size(1)*3, + &bitmaps, bitmap_buffer_size(1)*5, NullS)) { if (temp_pool_slot != MY_BIT_NONE) diff --git a/sql/opt_subselect.h b/sql/opt_subselect.h index 7b8f3142851..508531b8c37 100644 --- a/sql/opt_subselect.h +++ b/sql/opt_subselect.h @@ -283,6 +283,7 @@ public: { pos->records_read= best_loose_scan_records; pos->key= best_loose_scan_start_key; + pos->cond_selectivity= 1.0; pos->loosescan_picker.loosescan_key= best_loose_scan_key; pos->loosescan_picker.loosescan_parts= best_max_loose_keypart + 1; pos->use_join_buffer= FALSE; diff --git a/sql/sql_class.h b/sql/sql_class.h index 03dcdf482e5..221c0d3bd51 100644 --- a/sql/sql_class.h +++ b/sql/sql_class.h @@ -504,7 +504,10 @@ typedef struct system_variables ulong net_write_timeout; ulong optimizer_prune_level; ulong optimizer_search_depth; + ulong optimizer_use_condition_selectivity; ulong use_stat_tables; + ulong histogram_size; + ulong histogram_type; ulong preload_buff_size; ulong profiling_history_size; ulong read_buff_size; @@ -4017,6 +4020,7 @@ class Unique :public Sql_alloc uint size; uint full_size; uint min_dupl_count; /* always 0 for unions, > 0 for intersections */ + bool with_counters; bool merge(TABLE *table, uchar *buff, bool without_last_merge); diff --git a/sql/sql_priv.h b/sql/sql_priv.h index 7ff13bf06c3..9891cf1b24e 100644 --- a/sql/sql_priv.h +++ b/sql/sql_priv.h @@ -228,6 +228,7 @@ template <class T> bool valid_buffer_range(T jump, #define OPTIMIZER_SWITCH_TABLE_ELIMINATION (1ULL << 26) #define OPTIMIZER_SWITCH_EXTENDED_KEYS (1ULL << 27) #define OPTIMIZER_SWITCH_EXISTS_TO_IN (1ULL << 28) +#define OPTIMIZER_SWITCH_USE_CONDITION_SELECTIVITY (1ULL << 29) #define OPTIMIZER_SWITCH_DEFAULT (OPTIMIZER_SWITCH_INDEX_MERGE | \ OPTIMIZER_SWITCH_INDEX_MERGE_UNION | \ diff --git a/sql/sql_select.cc b/sql/sql_select.cc index abefbc42255..be8ff20eb48 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -89,12 +89,14 @@ void best_access_path(JOIN *join, JOIN_TAB *s, POSITION *pos, POSITION *loose_scan_pos); static void optimize_straight_join(JOIN *join, table_map join_tables); static bool greedy_search(JOIN *join, table_map remaining_tables, - uint depth, uint prune_level); + uint depth, uint prune_level, + uint use_cond_selectivity); static bool best_extension_by_limited_search(JOIN *join, table_map remaining_tables, uint idx, double record_count, double read_time, uint depth, - uint prune_level); + uint prune_level, + uint use_cond_selectivity); static uint determine_search_depth(JOIN* join); C_MODE_START static int join_tab_cmp(const void *dummy, const void* ptr1, const void* ptr2); @@ -134,7 +136,8 @@ static COND *build_equal_items(JOIN *join, COND *cond, COND_EQUAL *inherited, List<TABLE_LIST> *join_list, bool ignore_on_conds, - COND_EQUAL **cond_equal_ref); + COND_EQUAL **cond_equal_ref, + bool link_equal_fields= FALSE); static COND* substitute_for_best_equal_field(JOIN_TAB *context_tab, COND *cond, COND_EQUAL *cond_equal, @@ -150,8 +153,9 @@ static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list, static COND *optimize_cond(JOIN *join, COND *conds, List<TABLE_LIST> *join_list, bool ignore_on_conds, - Item::cond_result *cond_value, - COND_EQUAL **cond_equal); + Item::cond_result *cond_value, + COND_EQUAL **cond_equal, + int flags= 0); bool const_expression_in_where(COND *conds,Item *item, Item **comp_item); static bool create_internal_tmp_table_from_heap2(THD *, TABLE *, ENGINE_COLUMNDEF *, ENGINE_COLUMNDEF **, @@ -279,6 +283,8 @@ enum enum_exec_or_opt {WALK_OPTIMIZATION_TABS , WALK_EXECUTION_TABS}; JOIN_TAB *first_breadth_first_tab(JOIN *join, enum enum_exec_or_opt tabs_kind); JOIN_TAB *next_breadth_first_tab(JOIN *join, enum enum_exec_or_opt tabs_kind, JOIN_TAB *tab); +static double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, + table_map rem_tables); #ifndef DBUG_OFF @@ -1158,7 +1164,7 @@ TODO: make view to decide if it is possible to write to WHERE directly or make S DBUG_RETURN(1); conds= optimize_cond(this, conds, join_list, FALSE, - &cond_value, &cond_equal); + &cond_value, &cond_equal, OPT_LINK_EQUAL_FIELDS); if (thd->is_error()) { @@ -3355,6 +3361,7 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list, table->pos_in_table_list= tables; error= tables->fetch_number_of_rows(); set_statistics_for_table(join->thd, table); + bitmap_clear_all(&table->cond_set); #ifdef WITH_PARTITION_STORAGE_ENGINE const bool no_partitions_used= table->no_partitions_used; @@ -3786,6 +3793,8 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list, all select distinct fields participate in one index. */ add_group_and_distinct_keys(join, s); + + s->table->cond_selectivity= 1.0; /* Perform range analysis if there are keys it could use (1). @@ -3794,7 +3803,8 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list, Don't do range analysis for materialized subqueries (4). Don't do range analysis for materialized derived tables (5) */ - if (!s->const_keys.is_clear_all() && // (1) + if ((!s->const_keys.is_clear_all() || + !bitmap_is_clear_all(&s->table->cond_set)) && // (1) (!s->table->pos_in_table_list->embedding || // (2) (s->table->pos_in_table_list->embedding && // (3) s->table->pos_in_table_list->embedding->sj_on_expr)) && // (3) @@ -3802,20 +3812,37 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list, !(s->table->pos_in_table_list->derived && // (5) s->table->pos_in_table_list->is_materialized_derived())) // (5) { - ha_rows records; - SQL_SELECT *select; - select= make_select(s->table, found_const_table_map, - found_const_table_map, - *s->on_expr_ref ? *s->on_expr_ref : conds, - 1, &error); - if (!select) - goto error; - records= get_quick_record_count(join->thd, select, s->table, - &s->const_keys, join->row_limit); - s->quick=select->quick; - s->needed_reg=select->needed_reg; - select->quick=0; - if (records == 0 && s->table->reginfo.impossible_range) + bool impossible_range= FALSE; + ha_rows records= HA_POS_ERROR; + SQL_SELECT *select= 0; + if (!s->const_keys.is_clear_all()) + { + select= make_select(s->table, found_const_table_map, + found_const_table_map, + *s->on_expr_ref ? *s->on_expr_ref : conds, + 1, &error); + if (!select) + goto error; + records= get_quick_record_count(join->thd, select, s->table, + &s->const_keys, join->row_limit); + s->quick=select->quick; + s->needed_reg=select->needed_reg; + select->quick=0; + impossible_range= records == 0 && s->table->reginfo.impossible_range; + } + if (!impossible_range) + { + if (join->thd->variables.optimizer_use_condition_selectivity > 1) + calculate_cond_selectivity_for_table(join->thd, s->table, + *s->on_expr_ref ? + *s->on_expr_ref : conds); + if (s->table->reginfo.impossible_range) + { + impossible_range= TRUE; + records= 0; + } + } + if (impossible_range) { /* Impossible WHERE or ON expression @@ -3840,8 +3867,10 @@ make_join_statistics(JOIN *join, List<TABLE_LIST> &tables_list, s->found_records=records; s->read_time= s->quick ? s->quick->read_time : 0.0; } - delete select; + if (select) + delete select; } + } if (pull_out_semijoin_tables(join)) @@ -4198,11 +4227,12 @@ add_key_field(JOIN *join, else if (!(field->flags & PART_KEY_FLAG)) { // Don't remove column IS NULL on a LEFT JOIN table - if (!eq_func || (*value)->type() != Item::NULL_ITEM || - !field->table->maybe_null || field->null_ptr) - return; // Not a key. Skip it - optimize= KEY_OPTIMIZE_EXISTS; - DBUG_ASSERT(num_values == 1); + if (eq_func && (*value)->type() == Item::NULL_ITEM && + field->table->maybe_null && !field->null_ptr) + { + optimize= KEY_OPTIMIZE_EXISTS; + DBUG_ASSERT(num_values == 1); + } } if (optimize != KEY_OPTIMIZE_EXISTS) { @@ -4251,7 +4281,11 @@ add_key_field(JOIN *join, break; } if (is_const) + { stat[0].const_keys.merge(possible_keys); + if (possible_keys.is_clear_all()) + bitmap_set_bit(&field->table->cond_set, field->field_index); + } else if (!eq_func) { /* @@ -5322,6 +5356,7 @@ void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key) join->positions[idx].table= table; join->positions[idx].key=key; join->positions[idx].records_read=1.0; /* This is a const table */ + join->positions[idx].cond_selectivity= 1.0; join->positions[idx].ref_depend_map= 0; // join->positions[idx].loosescan_key= MAX_KEY; /* Not a LooseScan */ @@ -6140,6 +6175,8 @@ choose_plan(JOIN *join, table_map join_tables) { uint search_depth= join->thd->variables.optimizer_search_depth; uint prune_level= join->thd->variables.optimizer_prune_level; + uint use_cond_selectivity= + join->thd->variables.optimizer_use_condition_selectivity; bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN); DBUG_ENTER("choose_plan"); @@ -6204,7 +6241,8 @@ choose_plan(JOIN *join, table_map join_tables) if (search_depth == 0) /* Automatically determine a reasonable value for 'search_depth' */ search_depth= determine_search_depth(join); - if (greedy_search(join, join_tables, search_depth, prune_level)) + if (greedy_search(join, join_tables, search_depth, prune_level, + use_cond_selectivity)) DBUG_RETURN(TRUE); } } @@ -6478,6 +6516,8 @@ optimize_straight_join(JOIN *join, table_map join_tables) bool disable_jbuf= join->thd->variables.join_cache_level == 0; double record_count= 1.0; double read_time= 0.0; + uint use_cond_selectivity= + join->thd->variables.optimizer_use_condition_selectivity; POSITION loose_scan_pos; for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++) @@ -6494,6 +6534,11 @@ optimize_straight_join(JOIN *join, table_map join_tables) &loose_scan_pos); join_tables&= ~(s->table->map); + double pushdown_cond_selectivity= 1.0; + if (use_cond_selectivity > 1) + pushdown_cond_selectivity= table_cond_selectivity(join, idx, s, + join_tables); + join->positions[idx].cond_selectivity= pushdown_cond_selectivity; ++idx; } @@ -6581,6 +6626,8 @@ optimize_straight_join(JOIN *join, table_map join_tables) @param search_depth controlls the exhaustiveness of the search @param prune_level the pruning heuristics that should be applied during search + @param use_cond_selectivity specifies how the selectivity of the conditions + pushed to a table should be taken into account @retval FALSE ok @@ -6592,7 +6639,8 @@ static bool greedy_search(JOIN *join, table_map remaining_tables, uint search_depth, - uint prune_level) + uint prune_level, + uint use_cond_selectivity) { double record_count= 1.0; double read_time= 0.0; @@ -6617,7 +6665,8 @@ greedy_search(JOIN *join, /* Find the extension of the current QEP with the lowest cost */ join->best_read= DBL_MAX; if (best_extension_by_limited_search(join, remaining_tables, idx, record_count, - read_time, search_depth, prune_level)) + read_time, search_depth, prune_level, + use_cond_selectivity)) DBUG_RETURN(TRUE); /* 'best_read < DBL_MAX' means that optimizer managed to find @@ -6856,6 +6905,210 @@ double JOIN::get_examined_rows() } +static +double table_multi_eq_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, + table_map rem_tables, uint keyparts, + uint16 *ref_keyuse_steps) +{ + double sel= 1.0; + COND_EQUAL *cond_equal= join->cond_equal; + + if (!cond_equal || !cond_equal->current_level.elements) + return sel; + + if (!s->keyuse) + return sel; + + Item_equal *item_equal; + List_iterator_fast<Item_equal> it(cond_equal->current_level); + TABLE *table= s->table; + table_map table_bit= table->map; + POSITION *pos= &join->positions[idx]; + + while ((item_equal= it++)) + { + /* + Check whether we need to take into account the selectivity of + multiple equality item_equal. If this is the case multiply + the current value of sel by this selectivity + */ + table_map used_tables= item_equal->used_tables(); + if (!(used_tables & table_bit)) + continue; + if (item_equal->get_const()) + continue; + + Field *fld; + bool adjust_sel= FALSE; + Item_equal_fields_iterator fi(*item_equal); + while((fi++) && !adjust_sel) + { + Field *fld= fi.get_curr_field(); + if (fld->table->map != table_bit) + continue; + if (pos->key == 0) + adjust_sel= TRUE; + else + { + uint i; + KEYUSE *keyuse= pos->key; + uint key= keyuse->key; + + for (i= 0; i < keyparts; i++) + { + uint fldno; + if (is_hash_join_key_no(key)) + fldno= keyuse->keypart; + else + fldno= table->key_info[key].key_part[keyparts-1].fieldnr - 1; + if (fld->field_index == fldno) + break; + } + if (i == keyparts) + { + /* + Field fld is included in multiple equality item_equal + and is not a part of the ref key. + The selectivity of the multiple equality must be taken + into account unless one of the ref arguments is + equal to fld. + */ + adjust_sel= TRUE; + for (uint j= 0; j < keyparts && adjust_sel; j++) + { + if (j > 0) + keyuse+= ref_keyuse_steps[j-1]; + Item *ref_item= keyuse->val; + if (ref_item->real_item()->type() == Item::FIELD_ITEM) + { + Item_field *field_item= (Item_field *) (ref_item->real_item()); + if (item_equal->contains(field_item->field)) + adjust_sel= FALSE; + } + } + } + } + } + if (adjust_sel) + { + /* + If ref == 0 and there are no fields in the multiple equality + item_equal that belong to the tables joined prior to s + then the selectivity of multiple equality will be set to 1.0. + */ + double eq_fld_sel= 1.0; + fi.rewind(); + while ((fi++)) + { + double curr_eq_fld_sel; + fld= fi.get_curr_field(); + if (!fld->table->map & ~(table_bit | rem_tables)) + continue; + curr_eq_fld_sel= get_column_avg_frequency(fld) / + fld->table->stat_records(); + if (curr_eq_fld_sel < 1.0) + set_if_bigger(eq_fld_sel, curr_eq_fld_sel); + } + sel*= eq_fld_sel; + } + } + return sel; +} + +static +double table_cond_selectivity(JOIN *join, uint idx, JOIN_TAB *s, + table_map rem_tables) +{ + uint16 ref_keyuse_steps[MAX_REF_PARTS - 1]; + Field *field; + TABLE *table= s->table; + MY_BITMAP *read_set= table->read_set; + double sel= s->table->cond_selectivity; + double table_records= table->stat_records(); + POSITION *pos= &join->positions[idx]; + uint keyparts= 0; + uint found_part_ref_or_null= 0; + + /* Discount the selectivity of the access method used to join table s */ + if (s->quick && s->quick->index != MAX_KEY) + { + if (pos->key == 0 && table_records > 0) + { + sel*= table->quick_rows[s->quick->index]/table_records; + } + } + else if (pos->key != 0) + { + /* A ref/ access or hash join is used to join table */ + KEYUSE *keyuse= pos->key; + KEYUSE *prev_ref_keyuse= keyuse; + uint key= keyuse->key; + do + { + if (!(keyuse->used_tables & (rem_tables | table->map))) + { + if (are_tables_local(s, keyuse->val->used_tables())) + { + if (is_hash_join_key_no(key)) + { + if (keyparts == keyuse->keypart) + keyparts++; + } + else + { + if (keyparts == keyuse->keypart && + !(~(keyuse->val->used_tables()) & pos->ref_depend_map) && + !(found_part_ref_or_null & keyuse->optimize)) + { + keyparts++; + found_part_ref_or_null|= keyuse->optimize & ~KEY_OPTIMIZE_EQ; + } + } + if (keyparts > keyuse->keypart) + { + uint fldno; + if (is_hash_join_key_no(key)) + fldno= keyuse->keypart; + else + fldno= table->key_info[key].key_part[keyparts-1].fieldnr - 1; + if (keyuse->val->const_item()) + sel*= table->field[fldno]->cond_selectivity; + if (keyparts > 1) + { + ref_keyuse_steps[keyparts-2]= keyuse - prev_ref_keyuse; + prev_ref_keyuse= keyuse; + } + } + } + } + keyuse++; + } while (keyuse->table == table && keyuse->key == key); + } + + for (Field **f_ptr=table->field ; (field= *f_ptr) ; f_ptr++) + { + if (!bitmap_is_set(read_set, field->field_index) || + !field->next_equal_field) + continue; + for (Field *next_field= field->next_equal_field; + next_field != field; + next_field= next_field->next_equal_field) + { + if (!(next_field->table->map & rem_tables) && next_field->table != table) + { + sel/= field->cond_selectivity; + break; + } + } + } + + sel*= table_multi_eq_cond_selectivity(join, idx, s, rem_tables, + keyparts, ref_keyuse_steps); + + return sel; +} + + /** Find a good, possibly optimal, query execution plan (QEP) by a possibly exhaustive search. @@ -6966,6 +7219,8 @@ double JOIN::get_examined_rows() @param prune_level pruning heuristics that should be applied during optimization (values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS) + @param use_cond_selectivity specifies how the selectivity of the conditions + pushed to a table should be taken into account @retval FALSE ok @@ -6980,7 +7235,8 @@ best_extension_by_limited_search(JOIN *join, double record_count, double read_time, uint search_depth, - uint prune_level) + uint prune_level, + uint use_cond_selectivity) { DBUG_ENTER("best_extension_by_limited_search"); @@ -7083,16 +7339,25 @@ best_extension_by_limited_search(JOIN *join, } } + double pushdown_cond_selectivity= 1.0; + if (use_cond_selectivity > 1) + pushdown_cond_selectivity= table_cond_selectivity(join, idx, s, + remaining_tables & + ~real_table_bit); + join->positions[idx].cond_selectivity= pushdown_cond_selectivity; + double partial_join_cardinality= current_record_count * + pushdown_cond_selectivity; if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) & allowed_tables ) { /* Recursively expand the current partial plan */ swap_variables(JOIN_TAB*, join->best_ref[idx], *pos); if (best_extension_by_limited_search(join, remaining_tables & ~real_table_bit, idx + 1, - current_record_count, + partial_join_cardinality, current_read_time, search_depth - 1, - prune_level)) + prune_level, + use_cond_selectivity)) DBUG_RETURN(TRUE); swap_variables(JOIN_TAB*, join->best_ref[idx], *pos); } @@ -7110,7 +7375,7 @@ best_extension_by_limited_search(JOIN *join, { memcpy((uchar*) join->best_positions, (uchar*) join->positions, sizeof(POSITION) * (idx + 1)); - join->record_count= current_record_count; + join->record_count= partial_join_cardinality; join->best_read= current_read_time - 0.001; } DBUG_EXECUTE("opt", print_plan(join, idx+1, @@ -7755,6 +8020,7 @@ get_best_combination(JOIN *join) */ SJ_MATERIALIZATION_INFO *sjm= cur_pos->table->emb_sj_nest->sj_mat_info; j->records= j->records_read= (ha_rows)(sjm->is_sj_scan? sjm->rows : 1); + j->cond_selectivity= 1.0; JOIN_TAB *jt; JOIN_TAB_RANGE *jt_range; if (!(jt= (JOIN_TAB*)join->thd->alloc(sizeof(JOIN_TAB)*sjm->tables)) || @@ -7818,6 +8084,7 @@ get_best_combination(JOIN *join) to access join->best_positions[]. */ j->records_read= (ha_rows)join->best_positions[tablenr].records_read; + j->cond_selectivity= join->best_positions[tablenr].cond_selectivity; join->map2table[j->table->tablenr]= j; /* If we've reached the end of sjm nest, switch back to main sequence */ @@ -11796,7 +12063,8 @@ static bool check_equality(THD *thd, Item *item, COND_EQUAL *cond_equal, */ static COND *build_equal_items_for_cond(THD *thd, COND *cond, - COND_EQUAL *inherited) + COND_EQUAL *inherited, + bool link_item_fields) { Item_equal *item_equal; COND_EQUAL cond_equal; @@ -11843,6 +12111,7 @@ static COND *build_equal_items_for_cond(THD *thd, COND *cond, List_iterator_fast<Item_equal> it(cond_equal.current_level); while ((item_equal= it++)) { + item_equal->set_link_equal_fields(link_item_fields); item_equal->fix_fields(thd, NULL); item_equal->update_used_tables(); set_if_bigger(thd->lex->current_select->max_equal_elems, @@ -11862,7 +12131,8 @@ static COND *build_equal_items_for_cond(THD *thd, COND *cond, while ((item= li++)) { Item *new_item; - if ((new_item= build_equal_items_for_cond(thd, item, inherited)) != item) + if ((new_item= build_equal_items_for_cond(thd, item, inherited, FALSE)) + != item) { /* This replacement happens only for standalone equalities */ /* @@ -12025,14 +12295,15 @@ static COND *build_equal_items(JOIN *join, COND *cond, COND_EQUAL *inherited, List<TABLE_LIST> *join_list, bool ignore_on_conds, - COND_EQUAL **cond_equal_ref) + COND_EQUAL **cond_equal_ref, + bool link_equal_fields) { THD *thd= join->thd; COND_EQUAL *cond_equal= 0; if (cond) { - cond= build_equal_items_for_cond(thd, cond, inherited); + cond= build_equal_items_for_cond(thd, cond, inherited, link_equal_fields); cond->update_used_tables(); if (cond->type() == Item::COND_ITEM && ((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC) @@ -13548,9 +13819,10 @@ void optimize_wo_join_buffering(JOIN *join, uint first_tab, uint last_tab, static COND * -optimize_cond(JOIN *join, COND *conds, +optimize_cond(JOIN *join, COND *conds, List<TABLE_LIST> *join_list, bool ignore_on_conds, - Item::cond_result *cond_value, COND_EQUAL **cond_equal) + Item::cond_result *cond_value, COND_EQUAL **cond_equal, + int flags) { THD *thd= join->thd; DBUG_ENTER("optimize_cond"); @@ -13573,9 +13845,10 @@ optimize_cond(JOIN *join, COND *conds, multiple equality contains a constant. */ DBUG_EXECUTE("where", print_where(conds, "original", QT_ORDINARY);); - conds= build_equal_items(join, conds, NULL, join_list, ignore_on_conds, - cond_equal); - DBUG_EXECUTE("where",print_where(conds,"after equal_items", QT_ORDINARY);); + conds= build_equal_items(join, conds, NULL, join_list, + ignore_on_conds, cond_equal, + test(flags & OPT_LINK_EQUAL_FIELDS)); + DBUG_EXECUTE("where",print_where(conds,"after equal_items", QT_ORDINARY);); /* change field = field to field = const for each found field = const */ propagate_cond_constants(thd, (I_List<COND_CMP> *) 0, conds, conds); @@ -14068,6 +14341,8 @@ Field *create_tmp_field_from_field(THD *thd, Field *org_field, ((Field_double *) new_field)->not_fixed= TRUE; new_field->vcol_info= 0; new_field->stored_in_db= TRUE; + new_field->cond_selectivity= 1.0; + new_field->next_equal_field= NULL; } return new_field; } @@ -14412,6 +14687,9 @@ void setup_tmp_table_column_bitmaps(TABLE *table, uchar *bitmaps) bitmap_init(&table->eq_join_set, (my_bitmap_map*) (bitmaps+ 3*bitmap_buffer_size(field_count)), field_count, FALSE); + bitmap_init(&table->cond_set, + (my_bitmap_map*) (bitmaps+ 4*bitmap_buffer_size(field_count)), + field_count, FALSE); /* write_set and all_set are copies of read_set */ table->def_write_set= table->def_read_set; table->s->all_set= table->def_read_set; @@ -14575,7 +14853,7 @@ create_tmp_table(THD *thd, TMP_TABLE_PARAM *param, List<Item> &fields, &tmpname, (uint) strlen(path)+1, &group_buff, (group && ! using_unique_constraint ? param->group_length : 0), - &bitmaps, bitmap_buffer_size(field_count)*4, + &bitmaps, bitmap_buffer_size(field_count)*5, NullS)) { if (temp_pool_slot != MY_BIT_NONE) @@ -15330,7 +15608,7 @@ TABLE *create_virtual_tmp_table(THD *thd, List<Create_field> &field_list) &share, sizeof(*share), &field, (field_count + 1) * sizeof(Field*), &blob_field, (field_count+1) *sizeof(uint), - &bitmaps, bitmap_buffer_size(field_count)*4, + &bitmaps, bitmap_buffer_size(field_count)*5, NullS)) return 0; @@ -22221,7 +22499,13 @@ int JOIN::print_explain(select_result_sink *result, uint8 explain_flags, { float f= 0.0; if (examined_rows) - f= (float) (100.0 * tab->records_read / examined_rows); + { + double pushdown_cond_selectivity= tab->cond_selectivity; + if (pushdown_cond_selectivity == 1.0) + f= (float) (100.0 * tab->records_read / examined_rows); + else + f= (float) (100.0 * pushdown_cond_selectivity); + } set_if_smaller(f, 100.0); item_list.push_back(new Item_float(f, 2)); } diff --git a/sql/sql_select.h b/sql/sql_select.h index 7e6f81cc65b..d52d312f14b 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -292,6 +292,8 @@ typedef struct st_join_table { /* psergey-todo: make the below have type double, like POSITION::records_read? */ ha_rows records_read; + double cond_selectivity; + /* Startup cost for execution */ double startup_cost; @@ -772,6 +774,8 @@ typedef struct st_position :public Sql_alloc */ double records_read; + double cond_selectivity; + /* Cost accessing the table in course of the entire complete join execution, i.e. cost of one access method use (e.g. 'range' or 'ref' scan ) times @@ -1820,6 +1824,8 @@ void eliminate_tables(JOIN *join); /* Index Condition Pushdown entry point function */ void push_index_cond(JOIN_TAB *tab, uint keyno); +#define OPT_LINK_EQUAL_FIELDS 1 + /**************************************************************************** Temporary table support for SQL Runtime ***************************************************************************/ diff --git a/sql/sql_statistics.cc b/sql/sql_statistics.cc index e34b4b21819..df86686f773 100644 --- a/sql/sql_statistics.cc +++ b/sql/sql_statistics.cc @@ -26,6 +26,7 @@ #include "sql_base.h" #include "key.h" #include "sql_statistics.h" +#include "opt_range.h" #include "my_atomic.h" /* @@ -888,7 +889,7 @@ public: char buff[MAX_FIELD_WIDTH]; String val(buff, sizeof(buff), &my_charset_utf8_bin); - for (uint i= COLUMN_STAT_MIN_VALUE; i <= COLUMN_STAT_AVG_FREQUENCY; i++) + for (uint i= COLUMN_STAT_MIN_VALUE; i <= COLUMN_STAT_HISTOGRAM; i++) { Field *stat_field= stat_table->field[i]; if (table_field->collected_stats->is_null(i)) @@ -923,7 +924,21 @@ public: break; case COLUMN_STAT_AVG_FREQUENCY: stat_field->store(table_field->collected_stats->get_avg_frequency()); - break; + break; + case COLUMN_STAT_HIST_SIZE: + stat_field->store(table_field->collected_stats->histogram.get_size()); + break; + case COLUMN_STAT_HIST_TYPE: + stat_field->store(table_field->collected_stats->histogram.get_type() + + 1); + break; + case COLUMN_STAT_HISTOGRAM: + const char * col_histogram= + (const char *) (table_field->collected_stats->histogram.get_values()); + stat_field->store(col_histogram, + table_field->collected_stats->histogram.get_size(), + &my_charset_bin); + break; } } } @@ -960,7 +975,7 @@ public: char buff[MAX_FIELD_WIDTH]; String val(buff, sizeof(buff), &my_charset_utf8_bin); - for (uint i= COLUMN_STAT_MIN_VALUE; i <= COLUMN_STAT_AVG_FREQUENCY; i++) + for (uint i= COLUMN_STAT_MIN_VALUE; i <= COLUMN_STAT_HIST_TYPE; i++) { Field *stat_field= stat_table->field[i]; @@ -992,6 +1007,14 @@ public: break; case COLUMN_STAT_AVG_FREQUENCY: table_field->read_stats->set_avg_frequency(stat_field->val_real()); + break; + case COLUMN_STAT_HIST_SIZE: + table_field->read_stats->histogram.set_size(stat_field->val_int()); + break; + case COLUMN_STAT_HIST_TYPE: + Histogram_type hist_type= (Histogram_type) (stat_field->val_int() - + 1); + table_field->read_stats->histogram.set_type(hist_type); break; } } @@ -999,6 +1022,21 @@ public: } } + void get_histogram_value() + { + if (find_stat()) + { + char buff[MAX_FIELD_WIDTH]; + String val(buff, sizeof(buff), &my_charset_utf8_bin); + uint fldno= COLUMN_STAT_HISTOGRAM; + Field *stat_field= stat_table->field[fldno]; + table_field->read_stats->set_not_null(fldno); + stat_field->val_str(&val); + memcpy(table_field->read_stats->histogram.get_values(), + val.ptr(), table_field->read_stats->histogram.get_size()); + } + } + }; @@ -1201,6 +1239,72 @@ public: }; +class Histogram_builder +{ + Field *column; + uint col_length; + ha_rows records; + Field *min_value; + Field *max_value; + Histogram *histogram; + uint hist_width; + double bucket_capacity; + uint curr_bucket; + ulonglong count; + ulonglong count_distinct; + +public: + Histogram_builder(Field *col, uint col_len, ha_rows rows) + : column(col), col_length(col_len), records(rows) + { + Column_statistics *col_stats= col->collected_stats; + min_value= col_stats->min_value; + max_value= col_stats->max_value; + histogram= &col_stats->histogram; + hist_width= histogram->get_width(); + bucket_capacity= (double) records / (hist_width + 1); + curr_bucket= 0; + count= 0; + count_distinct= 0; + } + + ulonglong get_count_distinct() { return count_distinct; } + + int next(void *elem, element_count elem_cnt) + { + count_distinct++; + count+= elem_cnt; + if (curr_bucket == hist_width) + return 0; + if (count > bucket_capacity * (curr_bucket + 1)) + { + column->store_field_value((uchar *) elem, col_length); + histogram->set_value(curr_bucket, + column->middle_point_pos(min_value, max_value)); + curr_bucket++; + while (curr_bucket != hist_width && + count > bucket_capacity * (curr_bucket + 1)) + { + histogram->set_prev_value(curr_bucket); + curr_bucket++; + } + } + return 0; + } +}; + + +C_MODE_START + +int histogram_build_walk(void *elem, element_count elem_cnt, void *arg) +{ + Histogram_builder *hist_builder= (Histogram_builder *) arg; + return hist_builder->next(elem, elem_cnt); +} + +C_MODE_END + + /* The class Count_distinct_field is a helper class used to calculate the number of distinct values for a column. The class employs the @@ -1220,6 +1324,8 @@ protected: uint tree_key_length; /* The length of the keys for the elements of 'tree */ public: + + Count_distinct_field() {} /** @param @@ -1238,28 +1344,11 @@ public: Count_distinct_field(Field *field, uint max_heap_table_size) { - qsort_cmp2 compare_key; - void* cmp_arg; - enum enum_field_types f_type= field->type(); - table_field= field; tree_key_length= field->pack_length(); - if ((f_type == MYSQL_TYPE_VARCHAR) || - (!field->binary() && (f_type == MYSQL_TYPE_STRING || - f_type == MYSQL_TYPE_VAR_STRING))) - { - compare_key= (qsort_cmp2) simple_str_key_cmp; - cmp_arg= (void*) field; - } - else - { - cmp_arg= (void*) &tree_key_length; - compare_key= (qsort_cmp2) simple_raw_key_cmp; - } - - tree= new Unique(compare_key, cmp_arg, - tree_key_length, max_heap_table_size); + tree= new Unique((qsort_cmp2) simple_str_key_cmp, (void*) field, + tree_key_length, max_heap_table_size, 1); } virtual ~Count_distinct_field() @@ -1299,9 +1388,36 @@ public: tree->walk(table_field->table, count_distinct_walk, (void*) &count); return count; } + + ulonglong get_value_with_histogram(ha_rows rows) + { + Histogram_builder hist_builder(table_field, tree_key_length, rows); + tree->walk(table_field->table, histogram_build_walk, (void *) &hist_builder); + return hist_builder.get_count_distinct(); + } + + uint get_hist_size() + { + return table_field->collected_stats->histogram.get_size(); + } + + uchar *get_histogram() + { + return table_field->collected_stats->histogram.get_values(); + } + }; +static +int simple_ulonglong_key_cmp(void* arg, uchar* key1, uchar* key2) +{ + ulonglong *val1= (ulonglong *) key1; + ulonglong *val2= (ulonglong *) key2; + return *val1 > *val2 ? 1 : *val1 == *val2 ? 0 : -1; +} + + /* The class Count_distinct_field_bit is derived from the class Count_distinct_field to be used only for fields of the MYSQL_TYPE_BIT type. @@ -1311,8 +1427,17 @@ public: class Count_distinct_field_bit: public Count_distinct_field { public: + Count_distinct_field_bit(Field *field, uint max_heap_table_size) - :Count_distinct_field(field, max_heap_table_size) {} + { + table_field= field; + tree_key_length= sizeof(ulonglong); + + tree= new Unique((qsort_cmp2) simple_ulonglong_key_cmp, + (void*) &tree_key_length, + tree_key_length, max_heap_table_size, 1); + } + bool add() { longlong val= table_field->val_int(); @@ -1671,13 +1796,27 @@ int alloc_statistics_for_table(THD* thd, TABLE *table) ulong *idx_avg_frequency= (ulong*) alloc_root(&table->mem_root, sizeof(ulong) * key_parts); - if (!table_stats || !column_stats || !index_stats || !idx_avg_frequency) + uint columns= 0; + for (field_ptr= table->field; *field_ptr; field_ptr++) + { + if (bitmap_is_set(table->read_set, (*field_ptr)->field_index)) + columns++; + } + uint hist_size= thd->variables.histogram_size; + Histogram_type hist_type= (Histogram_type) (thd->variables.histogram_type); + uchar *histogram= NULL; + if (hist_size > 0) + histogram= (uchar *) alloc_root(&table->mem_root, hist_size * columns); + + if (!table_stats || !column_stats || !index_stats || !idx_avg_frequency || + (hist_size && !histogram)) DBUG_RETURN(1); table->collected_stats= table_stats; table_stats->column_stats= column_stats; table_stats->index_stats= index_stats; table_stats->idx_avg_frequency= idx_avg_frequency; + table_stats->histograms= histogram; memset(column_stats, 0, sizeof(Column_statistics) * (fields+1)); @@ -1686,6 +1825,13 @@ int alloc_statistics_for_table(THD* thd, TABLE *table) (*field_ptr)->collected_stats= column_stats; (*field_ptr)->collected_stats->max_value= NULL; (*field_ptr)->collected_stats->min_value= NULL; + if (bitmap_is_set(table->read_set, (*field_ptr)->field_index)) + { + column_stats->histogram.set_size(hist_size); + column_stats->histogram.set_type(hist_type); + column_stats->histogram.set_values(histogram); + histogram+= hist_size; + } } memset(idx_avg_frequency, 0, sizeof(ulong) * key_parts); @@ -1902,10 +2048,51 @@ int alloc_statistics_for_table_share(THD* thd, TABLE_SHARE *table_share, if (!is_safe) mysql_mutex_unlock(&table_share->LOCK_ha_data); - DBUG_RETURN(0); } +static +int alloc_histograms_for_table_share(THD* thd, TABLE_SHARE *table_share, + bool is_safe) +{ + TABLE_STATISTICS_CB *stats_cb= &table_share->stats_cb; + + DBUG_ENTER("alloc_histograms_for_table_share"); + + if (!is_safe) + mysql_mutex_lock(&table_share->LOCK_ha_data); + + if (stats_cb->histograms_can_be_read) + { + if (!is_safe) + mysql_mutex_unlock(&table_share->LOCK_ha_data); + DBUG_RETURN(0); + } + + Table_statistics *table_stats= stats_cb->table_stats; + ulong total_hist_size= table_stats->total_hist_size; + + if (total_hist_size && !table_stats->histograms) + { + uchar *histograms= (uchar *) alloc_root(&stats_cb->mem_root, + total_hist_size); + if (!histograms) + { + if (!is_safe) + mysql_mutex_unlock(&table_share->LOCK_ha_data); + DBUG_RETURN(1); + } + memset(histograms, 0, total_hist_size); + table_stats->histograms= histograms; + stats_cb->histograms_can_be_read= TRUE; + } + + if (!is_safe) + mysql_mutex_unlock(&table_share->LOCK_ha_data); + + DBUG_RETURN(0); + +} /** @brief @@ -2005,14 +2192,29 @@ void Column_statistics_collected::finish(ha_rows rows) set_not_null(COLUMN_STAT_AVG_LENGTH); } if (count_distinct) - { - ulonglong distincts= count_distinct->get_value(); + { + ulonglong distincts; + uint hist_size= count_distinct->get_hist_size(); + if (hist_size == 0) + distincts= count_distinct->get_value(); + else + distincts= count_distinct->get_value_with_histogram(rows - nulls); if (distincts) { val= (double) (rows - nulls) / distincts; set_avg_frequency(val); set_not_null(COLUMN_STAT_AVG_FREQUENCY); } + else + hist_size= 0; + histogram.set_size(hist_size); + set_not_null(COLUMN_STAT_HIST_SIZE); + if (hist_size && distincts) + { + set_not_null(COLUMN_STAT_HIST_TYPE); + histogram.set_values(count_distinct->get_histogram()); + set_not_null(COLUMN_STAT_HISTOGRAM); + } delete count_distinct; count_distinct= NULL; } @@ -2233,16 +2435,19 @@ int collect_statistics_for_table(THD *thd, TABLE *table) table->collected_stats->cardinality= rows; } + bitmap_clear_all(table->write_set); for (field_ptr= table->field; *field_ptr; field_ptr++) { table_field= *field_ptr; if (!bitmap_is_set(table->read_set, table_field->field_index)) continue; + bitmap_set_bit(table->write_set, table_field->field_index); if (!rc) table_field->collected_stats->finish(rows); else table_field->collected_stats->cleanup(); } +bitmap_clear_all(table->write_set); if (!rc) { @@ -2420,6 +2625,7 @@ int read_statistics_for_table(THD *thd, TABLE *table, TABLE_LIST *stat_tables) Field **field_ptr; KEY *key_info, *key_info_end; TABLE_SHARE *table_share= table->s; + Table_statistics *read_stats= table_share->stats_cb.table_stats; DBUG_ENTER("read_statistics_for_table"); @@ -2431,16 +2637,18 @@ int read_statistics_for_table(THD *thd, TABLE *table, TABLE_LIST *stat_tables) /* Read statistics from the statistical table column_stats */ stat_table= stat_tables[COLUMN_STAT].table; + ulong total_hist_size= 0; Column_stat column_stat(stat_table, table); for (field_ptr= table_share->field; *field_ptr; field_ptr++) { table_field= *field_ptr; column_stat.set_key_fields(table_field); column_stat.get_stat_values(); + total_hist_size+= table_field->read_stats->histogram.get_size(); } + read_stats->total_hist_size= total_hist_size; /* Read statistics from the statistical table index_stats */ - Table_statistics *read_stats= table_share->stats_cb.table_stats; stat_table= stat_tables[INDEX_STAT].table; Index_stat index_stat(stat_table, table); for (key_info= table_share->key_info, @@ -2558,10 +2766,14 @@ bool statistics_for_tables_is_needed(THD *thd, TABLE_LIST *tables) TABLE_SHARE *table_share= tl->table->s; if (table_share && table_share->stats_cb.stats_can_be_read && - !table_share->stats_cb.stats_is_read) + (!table_share->stats_cb.stats_is_read || + (!table_share->stats_cb.histograms_are_read && + thd->variables.optimizer_use_condition_selectivity > 3))) return TRUE; if (table_share->stats_cb.stats_is_read) tl->table->stats_is_read= TRUE; + if (table_share->stats_cb.histograms_are_read) + tl->table->histograms_are_read= TRUE; } } @@ -2569,6 +2781,41 @@ bool statistics_for_tables_is_needed(THD *thd, TABLE_LIST *tables) } +static +int read_histograms_for_table(THD *thd, TABLE *table, TABLE_LIST *stat_tables) +{ + TABLE_SHARE *table_share= table->s; + + DBUG_ENTER("read_histograms_for_table"); + + if (!table_share->stats_cb.histograms_can_be_read) + { + (void) alloc_histograms_for_table_share(thd, table_share, FALSE); + } + if (table_share->stats_cb.histograms_can_be_read && + !table_share->stats_cb.histograms_are_read) + { + Field **field_ptr; + uchar *histogram= table_share->stats_cb.table_stats->histograms; + TABLE *stat_table= stat_tables[COLUMN_STAT].table; + Column_stat column_stat(stat_table, table); + for (field_ptr= table_share->field; *field_ptr; field_ptr++) + { + Field *table_field= *field_ptr; + uint hist_size= table_field->read_stats->histogram.get_size(); + if (hist_size) + { + column_stat.set_key_fields(table_field); + table_field->read_stats->histogram.set_values(histogram); + column_stat.get_histogram_value(); + histogram+= hist_size; + } + } + } + + DBUG_RETURN(0); +} + /** @brief Read statistics for tables from a table list if it is needed @@ -2596,7 +2843,7 @@ int read_statistics_for_tables_if_needed(THD *thd, TABLE_LIST *tables) TABLE_LIST stat_tables[STATISTICS_TABLES]; Open_tables_backup open_tables_backup; - DBUG_ENTER("read_statistics_for_table_if_needed"); + DBUG_ENTER("read_statistics_for_tables_if_needed"); DEBUG_SYNC(thd, "statistics_read_start"); @@ -2623,6 +2870,14 @@ int read_statistics_for_tables_if_needed(THD *thd, TABLE_LIST *tables) } if (table_share->stats_cb.stats_is_read) tl->table->stats_is_read= TRUE; + if (thd->variables.optimizer_use_condition_selectivity > 3 && + table_share && !table_share->stats_cb.histograms_are_read) + { + (void) read_histograms_for_table(thd, tl->table, stat_tables); + table_share->stats_cb.histograms_are_read= TRUE; + } + if (table_share->stats_cb.stats_is_read) + tl->table->histograms_are_read= TRUE; } } @@ -3054,3 +3309,120 @@ void set_statistics_for_table(THD *thd, TABLE *table) key_info->read_stats->get_avg_frequency(0) > 0.5); } } + + +double get_column_avg_frequency(Field * field) +{ + double res; + TABLE *table= field->table; + + /* + Statistics is shared by table instances and is accessed through + the table share. If table->s->field is not set for 'table', then + no column statistics is available for the table . + */ + if (!table->s->field) + { + res= table->stat_records(); + return res; + } + + Column_statistics *col_stats= table->s->field[field->field_index]->read_stats; + + if (!col_stats) + res= table->stat_records(); + else + res= col_stats->get_avg_frequency(); + return res; +} + + +double get_column_range_cardinality(Field *field, + key_range *min_endp, + key_range *max_endp, + uint range_flag) +{ + double res; + TABLE *table= field->table; + Column_statistics *col_stats= table->field[field->field_index]->read_stats; + double tab_records= table->stat_records(); + + if (!col_stats) + return tab_records; + + double col_nulls= tab_records * col_stats->get_nulls_ratio(); + + double col_non_nulls= tab_records - col_nulls; + + bool nulls_incl= field->null_ptr && min_endp && min_endp->key[0] && + !(range_flag & NEAR_MIN); + + if (col_non_nulls < 1) + res= 0; + else if (min_endp && max_endp && min_endp->length == max_endp->length && + !memcmp(min_endp->key, max_endp->key, min_endp->length)) + { + if (nulls_incl) + { + /* This is null single point range */ + res= col_nulls; + } + else + { + double avg_frequency= col_stats->get_avg_frequency(); + res= avg_frequency; + if (avg_frequency > 1.0 + 0.000001 && + col_stats->min_value && col_stats->max_value) + { + Histogram *hist= &col_stats->histogram; + if (hist->is_available()) + { + double pos= field->middle_point_pos(col_stats->min_value, + col_stats->max_value); + res= col_non_nulls * + hist->point_selectivity(pos, + avg_frequency / col_non_nulls); + } + } + } + } + else + { + if (col_stats->min_value && col_stats->max_value) + { + double sel, min_mp_pos, max_mp_pos; + + if (min_endp && !min_endp->key[0]) + { + store_key_image_to_rec(field, (uchar *) min_endp->key, + min_endp->length); + min_mp_pos= field->middle_point_pos(col_stats->min_value, + col_stats->max_value); + } + else + min_mp_pos= 0.0; + if (max_endp) + { + store_key_image_to_rec(field, (uchar *) max_endp->key, + max_endp->length); + max_mp_pos= field->middle_point_pos(col_stats->min_value, + col_stats->max_value); + } + else + max_mp_pos= 1.0; + + Histogram *hist= &col_stats->histogram; + if (!hist->is_available()) + sel= (max_mp_pos - min_mp_pos); + else + sel= hist->range_selectivity(min_mp_pos, max_mp_pos); + res= col_non_nulls * sel; + set_if_bigger(res, col_stats->get_avg_frequency()); + } + else + res= col_non_nulls; + if (nulls_incl) + res+= col_nulls; + } + return res; +} diff --git a/sql/sql_statistics.h b/sql/sql_statistics.h index 17f22cec4e5..8c1e95df1f0 100644 --- a/sql/sql_statistics.h +++ b/sql/sql_statistics.h @@ -16,15 +16,6 @@ #ifndef SQL_STATISTICS_H #define SQL_STATISTICS_H -/* - These enumeration types comprise the dictionary of three - statistical tables table_stat, column_stat and index_stat - as they defined in ../scripts/mysql_system_tables.sql. - - It would be nice if the declarations of these types were - generated automatically by the table definitions. -*/ - typedef enum enum_use_stat_tables_mode { @@ -33,6 +24,13 @@ enum enum_use_stat_tables_mode PEFERABLY, } Use_stat_tables_mode; +typedef +enum enum_histogram_type +{ + SINGLE_PREC_HB, + DOUBLE_PREC_HB +} Histogram_type; + enum enum_stat_tables { TABLE_STAT, @@ -40,6 +38,16 @@ enum enum_stat_tables INDEX_STAT, }; + +/* + These enumeration types comprise the dictionary of three + statistical tables table_stat, column_stat and index_stat + as they defined in ../scripts/mysql_system_tables.sql. + + It would be nice if the declarations of these types were + generated automatically by the table definitions. +*/ + enum enum_table_stat_col { TABLE_STAT_DB_NAME, @@ -56,7 +64,10 @@ enum enum_column_stat_col COLUMN_STAT_MAX_VALUE, COLUMN_STAT_NULLS_RATIO, COLUMN_STAT_AVG_LENGTH, - COLUMN_STAT_AVG_FREQUENCY + COLUMN_STAT_AVG_FREQUENCY, + COLUMN_STAT_HIST_SIZE, + COLUMN_STAT_HIST_TYPE, + COLUMN_STAT_HISTOGRAM }; enum enum_index_stat_col @@ -90,6 +101,160 @@ int rename_column_in_stat_tables(THD *thd, TABLE *tab, Field *col, const char *new_name); void set_statistics_for_table(THD *thd, TABLE *table); +double get_column_avg_frequency(Field * field); + +double get_column_range_cardinality(Field *field, + key_range *min_endp, + key_range *max_endp, + uint range_flag); + +class Histogram +{ + +private: + Histogram_type type; + uint8 size; + uchar *values; + + uint prec_factor() + { + switch (type) { + case SINGLE_PREC_HB: + return ((uint) (1 << 8) - 1); + case DOUBLE_PREC_HB: + return ((uint) (1 << 16) - 1); + } + return 1; + } + +public: + uint get_width() + { + switch (type) { + case SINGLE_PREC_HB: + return size; + case DOUBLE_PREC_HB: + return size / 2; + } + return 0; + } + +private: + uint get_value(uint i) + { + switch (type) { + case SINGLE_PREC_HB: + return (uint) (((uint8 *) values)[i]); + case DOUBLE_PREC_HB: + return (uint) (((uint16 *) values)[i]); + } + return 0; + } + + uint find_bucket(double pos, bool first) + { + uint val= (uint) (pos * prec_factor()); + int lp= 0; + int rp= get_width() - 1; + int d= get_width() / 2; + uint i= lp + d; + for ( ; d; d= (rp - lp) / 2, i= lp + d) + { + if (val == get_value(i)) + break; + if (val < get_value(i)) + rp= i; + else if (val > get_value(i + 1)) + lp= i + 1; + else + break; + } + if (val == get_value(i)) + { + if (first) + { + while(i && val == get_value(i - 1)) + i--; + } + else + { + while(i + 1 < get_width() && val == get_value(i + 1)) + i++; + } + } + return i; + } + +public: + + uint get_size() { return (uint) size; } + + Histogram_type get_type() { return type; } + + uchar *get_values() { return (uchar *) values; } + + void set_size (ulonglong sz) { size= (uint8) sz; } + + void set_type (Histogram_type t) { type= t; } + + void set_values (uchar *vals) { values= (uchar *) vals; } + + bool is_available() { return get_size() > 0 && get_values(); } + + void set_value(uint i, double val) + { + switch (type) { + case SINGLE_PREC_HB: + ((uint8 *) values)[i]= (uint8) (val * prec_factor()); + return; + case DOUBLE_PREC_HB: + ((uint16 *) values)[i]= (uint16) (val * prec_factor()); + return; + } + } + + void set_prev_value(uint i) + { + switch (type) { + case SINGLE_PREC_HB: + ((uint8 *) values)[i]= ((uint8 *) values)[i-1]; + return; + case DOUBLE_PREC_HB: + ((uint16 *) values)[i]= ((uint16 *) values)[i-1]; + return; + } + } + + double range_selectivity(double min_pos, double max_pos) + { + double sel; + double bucket_sel= 1.0/(get_width() + 1); + uint min= find_bucket(min_pos, TRUE); + uint max= find_bucket(max_pos, FALSE); + sel= bucket_sel * (max - min + 1); + return sel; + } + + double point_selectivity(double pos, double avg_sel) + { + double sel; + double bucket_sel= 1.0/(get_width() + 1); + uint min= find_bucket(pos, TRUE); + uint max= min; + while (max + 1 < get_width() && get_value(max + 1) == get_value(max)) + max++; + double inv_prec_factor= (double) 1.0 / prec_factor(); + double width= (max + 1 == get_width() ? + 1.0 : get_value(max) * inv_prec_factor) - + (min == 0 ? + 0.0 : get_value(min-1) * inv_prec_factor); + sel= avg_sel * (bucket_sel * (max + 1 - min)) / width; + return sel; + } + +}; + + class Columns_statistics; class Index_statistics; @@ -105,8 +270,9 @@ public: uchar *min_max_record_buffers; /* Record buffers for min/max values */ Column_statistics *column_stats; /* Array of statistical data for columns */ Index_statistics *index_stats; /* Array of statistical data for indexes */ - ulong *idx_avg_frequency; /* Array of records per key for index prefixes */ - + ulong *idx_avg_frequency; /* Array of records per key for index prefixes */ + ulong total_hist_size; + uchar *histograms; /* Sequence of histograms */ }; @@ -161,10 +327,12 @@ private: public: + Histogram histogram; + void set_all_nulls() { column_stat_nulls= - ((1 << (COLUMN_STAT_AVG_FREQUENCY-COLUMN_STAT_COLUMN_NAME))-1) << + ((1 << (COLUMN_STAT_HISTOGRAM-COLUMN_STAT_COLUMN_NAME))-1) << (COLUMN_STAT_COLUMN_NAME+1); } diff --git a/sql/sys_vars.cc b/sql/sys_vars.cc index e5914df7ce1..762b35da89a 100644 --- a/sql/sys_vars.cc +++ b/sql/sys_vars.cc @@ -1533,6 +1533,25 @@ static Sys_var_ulong Sys_optimizer_prune_level( SESSION_VAR(optimizer_prune_level), CMD_LINE(REQUIRED_ARG), VALID_RANGE(0, 1), DEFAULT(1), BLOCK_SIZE(1)); +static Sys_var_ulong Sys_optimizer_use_condition_selectivity( + "optimizer_use_condition_selectivity", + "Controls selectivity of which conditions the optimizer takes into " + "account to calculate cardinality of a partial join when it searches " + "for the best execution plan " + "Meaning: " + "1 - use selectivity of index backed range conditions to calculate " + "the cardinality of a partial join if the last joined table is " + "accessed by full table scan or an index scan, " + "2 - use selectivity of index backed range conditions to calculate " + "the cardinality of a partial join in any case, " + "3 - additionally always use selectivity of range conditions that are " + "not backed by any index to calculate the cardinality of a partial join, " + "4 - use histograms to calculate selectivity of range conditions that " + "are not backed by any index to calculate the cardinality of " + "a partial join.", + SESSION_VAR(optimizer_use_condition_selectivity), CMD_LINE(REQUIRED_ARG), + VALID_RANGE(1, 4), DEFAULT(1), BLOCK_SIZE(1)); + /** Warns about deprecated value 63 */ static bool fix_optimizer_search_depth(sys_var *self, THD *thd, enum_var_type type) @@ -3876,6 +3895,24 @@ static Sys_var_enum Sys_optimizer_use_stat_tables( SESSION_VAR(use_stat_tables), CMD_LINE(REQUIRED_ARG), use_stat_tables_modes, DEFAULT(0)); +static Sys_var_ulong Sys_histogram_size( + "histogram_size", + "Number of bytes used for a histogram. " + "If set to 0, no histograms are created by ANALYZE.", + SESSION_VAR(histogram_size), CMD_LINE(REQUIRED_ARG), + VALID_RANGE(0, 255), DEFAULT(0), BLOCK_SIZE(1)); + +const char *histogram_types[] = + {"SINGLE_PREC_HB", "DOUBLE_PREC_HB", 0}; +static Sys_var_enum Sys_histogram_type( + "histogram_type", + "Specifies type of the histograms created by ANALYZE. " + "Possible values are: " + "SINGLE_PREC_HB - single precision height-balanced, " + "DOUBLE_PREC_HB - double precision height-balanced.", + SESSION_VAR(histogram_type), CMD_LINE(REQUIRED_ARG), + histogram_types, DEFAULT(0)); + static Sys_var_mybool Sys_no_thread_alarm( "debug_no_thread_alarm", "Disable system thread alarm calls. Disabling it may be useful " diff --git a/sql/table.cc b/sql/table.cc index 7f430029eda..e88b3453ce9 100644 --- a/sql/table.cc +++ b/sql/table.cc @@ -425,6 +425,8 @@ void TABLE_SHARE::destroy() free_root(&stats_cb.mem_root, MYF(0)); stats_cb.stats_can_be_read= FALSE; stats_cb.stats_is_read= FALSE; + stats_cb.histograms_can_be_read= FALSE; + stats_cb.histograms_are_read= FALSE; if (tmp_table == NO_TMP_TABLE) mysql_mutex_unlock(&LOCK_ha_data); @@ -2749,7 +2751,7 @@ partititon_err: /* Allocate bitmaps */ bitmap_size= share->column_bitmap_size; - if (!(bitmaps= (uchar*) alloc_root(&outparam->mem_root, bitmap_size*5))) + if (!(bitmaps= (uchar*) alloc_root(&outparam->mem_root, bitmap_size*6))) goto err; bitmap_init(&outparam->def_read_set, (my_bitmap_map*) bitmaps, share->fields, FALSE); @@ -2761,8 +2763,12 @@ partititon_err: (my_bitmap_map*) (bitmaps+bitmap_size*3), share->fields, FALSE); bitmap_init(&outparam->eq_join_set, (my_bitmap_map*) (bitmaps+bitmap_size*4), share->fields, FALSE); + bitmap_init(&outparam->cond_set, + (my_bitmap_map*) (bitmaps+bitmap_size*5), share->fields, FALSE); outparam->default_column_bitmaps(); + outparam->cond_selectivity= 1.0; + /* The table struct is now initialized; Open the table */ if (db_stat) { @@ -3884,6 +3890,7 @@ void TABLE::init(THD *thd, TABLE_LIST *tl) file->ha_start_of_new_statement(); reginfo.impossible_range= 0; created= TRUE; + cond_selectivity= 1.0; /* Catch wrong handling of the auto_increment_field_not_null. */ DBUG_ASSERT(!auto_increment_field_not_null); @@ -3892,6 +3899,11 @@ void TABLE::init(THD *thd, TABLE_LIST *tl) pos_in_table_list= tl; clear_column_bitmaps(); + for (Field **f_ptr= field ; *f_ptr ; f_ptr++) + { + (*f_ptr)->next_equal_field= NULL; + (*f_ptr)->cond_selectivity= 1.0; + } DBUG_ASSERT(key_read == 0); diff --git a/sql/table.h b/sql/table.h index 2841b854da1..e721d60f892 100644 --- a/sql/table.h +++ b/sql/table.h @@ -586,7 +586,9 @@ struct TABLE_STATISTICS_CB Table_statistics *table_stats; /* Structure to access the statistical data */ bool stats_can_be_read; /* Memory for statistical data is allocated */ bool stats_is_read; /* Statistical data for table has been read - from statistical tables */ + from statistical tables */ + bool histograms_can_be_read; + bool histograms_are_read; }; @@ -1107,6 +1109,7 @@ public: my_bitmap_map *bitmap_init_value; MY_BITMAP def_read_set, def_write_set, def_vcol_set, tmp_set; MY_BITMAP eq_join_set; /* used to mark equi-joined fields */ + MY_BITMAP cond_set; /* used to mark fields from sargable conditions*/ MY_BITMAP *read_set, *write_set, *vcol_set; /* Active column sets */ /* The ID of the query that opened and is using this table. Has different @@ -1159,6 +1162,8 @@ public: */ ha_rows quick_condition_rows; + double cond_selectivity; + table_map map; /* ID bit of table (1,2,4,8,16...) */ uint lock_position; /* Position in MYSQL_LOCK.table */ @@ -1278,6 +1283,7 @@ public: #endif uint max_keys; /* Size of allocated key_info array. */ bool stats_is_read; /* Persistent statistics is read for the table */ + bool histograms_are_read; MDL_ticket *mdl_ticket; void init(THD *thd, TABLE_LIST *tl); diff --git a/sql/uniques.cc b/sql/uniques.cc index 9fa06311ece..0c1c34d495b 100644 --- a/sql/uniques.cc +++ b/sql/uniques.cc @@ -86,6 +86,7 @@ Unique::Unique(qsort_cmp2 comp_func, void * comp_func_fixed_arg, full_size= size; if (min_dupl_count_arg) full_size+= sizeof(element_count); + with_counters= test(min_dupl_count_arg); my_b_clear(&file); init_tree(&tree, (ulong) (max_in_memory_size / 16), 0, size, comp_func, NULL, comp_func_fixed_arg, MYF(MY_THREAD_SPECIFIC)); @@ -428,6 +429,22 @@ static int buffpek_compare(void *arg, uchar *key_ptr1, uchar *key_ptr2) C_MODE_END +inline +element_count get_counter_from_merged_element(void *ptr, uint ofs) +{ + element_count cnt; + memcpy((uchar *) &cnt, (uchar *) ptr + ofs, sizeof(element_count)); + return cnt; +} + + +inline +void put_counter_into_merged_element(void *ptr, uint ofs, element_count cnt) +{ + memcpy((uchar *) ptr + ofs, (uchar *) &cnt, sizeof(element_count)); +} + + /* DESCRIPTION @@ -457,6 +474,8 @@ C_MODE_END file file with all trees dumped. Trees in the file must contain sorted unique values. Cache must be initialized in read mode. + with counters take into account counters for equal merged + elements RETURN VALUE 0 ok <> 0 error @@ -466,7 +485,7 @@ static bool merge_walk(uchar *merge_buffer, ulong merge_buffer_size, uint key_length, BUFFPEK *begin, BUFFPEK *end, tree_walk_action walk_action, void *walk_action_arg, qsort_cmp2 compare, void *compare_arg, - IO_CACHE *file) + IO_CACHE *file, bool with_counters) { BUFFPEK_COMPARE_CONTEXT compare_context = { compare, compare_arg }; QUEUE queue; @@ -485,6 +504,8 @@ static bool merge_walk(uchar *merge_buffer, ulong merge_buffer_size, uint bytes_read; /* to hold return value of read_to_buffer */ BUFFPEK *top; int res= 1; + uint cnt_ofs= key_length - (with_counters ? sizeof(element_count) : 0); + element_count cnt; /* Invariant: queue must contain top element from each tree, until a tree is not completely walked through. @@ -543,9 +564,17 @@ static bool merge_walk(uchar *merge_buffer, ulong merge_buffer_size, /* new top has been obtained; if old top is unique, apply the action */ if (compare(compare_arg, old_key, top->key)) { - if (walk_action(old_key, 1, walk_action_arg)) + cnt= with_counters ? + get_counter_from_merged_element(old_key, cnt_ofs) : 1; + if (walk_action(old_key, cnt, walk_action_arg)) goto end; } + else if (with_counters) + { + cnt= get_counter_from_merged_element(top->key, cnt_ofs); + cnt+= get_counter_from_merged_element(old_key, cnt_ofs); + put_counter_into_merged_element(top->key, cnt_ofs, cnt); + } } /* Applying walk_action to the tail of the last tree: this is safe because @@ -556,7 +585,10 @@ static bool merge_walk(uchar *merge_buffer, ulong merge_buffer_size, { do { - if (walk_action(top->key, 1, walk_action_arg)) + + cnt= with_counters ? + get_counter_from_merged_element(top->key, cnt_ofs) : 1; + if (walk_action(top->key, cnt, walk_action_arg)) goto end; top->key+= key_length; } @@ -620,7 +652,7 @@ bool Unique::walk(TABLE *table, tree_walk_action action, void *walk_action_arg) (BUFFPEK *) file_ptrs.buffer, (BUFFPEK *) file_ptrs.buffer + file_ptrs.elements, action, walk_action_arg, - tree.compare, tree.custom_arg, &file); + tree.compare, tree.custom_arg, &file, with_counters); } my_free(merge_buffer); return res; |