diff options
Diffstat (limited to 'sql/sql_statistics.h')
| -rw-r--r-- | sql/sql_statistics.h | 625 |
1 files changed, 625 insertions, 0 deletions
diff --git a/sql/sql_statistics.h b/sql/sql_statistics.h new file mode 100644 index 00000000..12802bc9 --- /dev/null +++ b/sql/sql_statistics.h @@ -0,0 +1,625 @@ +/* Copyright 2006-2008 MySQL AB, 2008 Sun Microsystems, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */ + +#ifndef SQL_STATISTICS_H +#define SQL_STATISTICS_H + +#include <vector> +#include <string> + +/* + For COMPLEMENTARY_FOR_QUERIES and PREFERABLY_FOR_QUERIES they are + similar to the COMPLEMENTARY and PREFERABLY respectively except that + with these values we would not be collecting EITS for queries like + ANALYZE TABLE t1; + To collect EITS with these values, we have to use PERSISITENT FOR + analyze table t1 persistent for + columns (col1,col2...) index (idx1, idx2...) + or + analyze table t1 persistent for all +*/ + +typedef +enum enum_use_stat_tables_mode +{ + NEVER, + COMPLEMENTARY, + PREFERABLY, + COMPLEMENTARY_FOR_QUERIES, + PREFERABLY_FOR_QUERIES +} Use_stat_tables_mode; + +typedef +enum enum_histogram_type +{ + SINGLE_PREC_HB, + DOUBLE_PREC_HB, + JSON_HB, + INVALID_HISTOGRAM +} Histogram_type; + +enum enum_stat_tables +{ + TABLE_STAT, + COLUMN_STAT, + 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, + TABLE_STAT_TABLE_NAME, + TABLE_STAT_CARDINALITY, + TABLE_STAT_N_FIELDS +}; + +enum enum_column_stat_col +{ + COLUMN_STAT_DB_NAME, + COLUMN_STAT_TABLE_NAME, + COLUMN_STAT_COLUMN_NAME, + COLUMN_STAT_MIN_VALUE, + COLUMN_STAT_MAX_VALUE, + COLUMN_STAT_NULLS_RATIO, + COLUMN_STAT_AVG_LENGTH, + COLUMN_STAT_AVG_FREQUENCY, + COLUMN_STAT_HIST_SIZE, + COLUMN_STAT_HIST_TYPE, + COLUMN_STAT_HISTOGRAM, + COLUMN_STAT_N_FIELDS +}; + +enum enum_index_stat_col +{ + INDEX_STAT_DB_NAME, + INDEX_STAT_TABLE_NAME, + INDEX_STAT_INDEX_NAME, + INDEX_STAT_PREFIX_ARITY, + INDEX_STAT_AVG_FREQUENCY, + INDEX_STAT_N_FIELDS +}; + +inline +Use_stat_tables_mode get_use_stat_tables_mode(THD *thd) +{ + return (Use_stat_tables_mode) (thd->variables.use_stat_tables); +} +inline +bool check_eits_collection_allowed(THD *thd) +{ + return (get_use_stat_tables_mode(thd) == COMPLEMENTARY || + get_use_stat_tables_mode(thd) == PREFERABLY); +} + +inline +bool check_eits_preferred(THD *thd) +{ + return (get_use_stat_tables_mode(thd) == PREFERABLY || + get_use_stat_tables_mode(thd) == PREFERABLY_FOR_QUERIES); +} + +int read_statistics_for_tables_if_needed(THD *thd, TABLE_LIST *tables); +int read_statistics_for_tables(THD *thd, TABLE_LIST *tables, + bool force_reload); +int collect_statistics_for_table(THD *thd, TABLE *table); +int alloc_statistics_for_table(THD *thd, TABLE *table, MY_BITMAP *stat_fields); +void free_statistics_for_table(TABLE *table); +int update_statistics_for_table(THD *thd, TABLE *table); +int delete_statistics_for_table(THD *thd, const LEX_CSTRING *db, + const LEX_CSTRING *tab); +int delete_statistics_for_column(THD *thd, TABLE *tab, Field *col); +int delete_statistics_for_index(THD *thd, TABLE *tab, KEY *key_info, + bool ext_prefixes_only); +int rename_table_in_stat_tables(THD *thd, const LEX_CSTRING *db, + const LEX_CSTRING *tab, + const LEX_CSTRING *new_db, + const LEX_CSTRING *new_tab); +int rename_columns_in_stat_table(THD *thd, TABLE *tab, + List<Alter_info::RENAME_COLUMN_STAT_PARAMS> *fields); +int rename_indexes_in_stat_table(THD *thd, TABLE *tab, + List<Alter_info::RENAME_INDEX_STAT_PARAMS> *indexes); +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); +bool is_stat_table(const LEX_CSTRING *db, LEX_CSTRING *table); +bool is_eits_usable(Field* field); + +class Histogram_builder; + +/* + Common base for all histograms +*/ +class Histogram_base :public Sql_alloc +{ +public: + Histogram_base() {} + virtual ~Histogram_base()= default; + + virtual bool parse(MEM_ROOT *mem_root, + const char *db_name, const char *table_name, + Field *field, const char *hist_data, + size_t hist_data_len)= 0; + virtual void serialize(Field *to_field)= 0; + + virtual Histogram_type get_type()=0; + + virtual uint get_width()=0; + + /* + The creation-time workflow is: + * create a histogram + * init_for_collection() + * create_builder() + * feed the data to the builder + * serialize(); + */ + virtual void init_for_collection(MEM_ROOT *mem_root, Histogram_type htype_arg, + ulonglong size)=0; + virtual Histogram_builder *create_builder(Field *col, uint col_len, + ha_rows rows)=0; + + /* + This function checks that histograms should be usable only when + 1) the level of optimizer_use_condition_selectivity > 3 + */ + bool is_usable(THD *thd) + { + return thd->variables.optimizer_use_condition_selectivity > 3; + } + + + virtual double point_selectivity(Field *field, key_range *endpoint, + double avg_sel)=0; + virtual double range_selectivity(Field *field, key_range *min_endp, + key_range *max_endp, double avg_sel)=0; + /* + Legacy: return the size of the histogram on disk. + + This will be stored in mysql.column_stats.hist_size column. + The value is not really needed as one can look at + LENGTH(mysql.column_stats.histogram) directly. + */ + virtual uint get_size()=0; +}; + + +/* + A Height-balanced histogram that stores numeric fractions +*/ + +class Histogram_binary final : public Histogram_base +{ +private: + Histogram_type type; + size_t size; /* Size of values array, in bytes */ + 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); + default: + DBUG_ASSERT(0); + } + return 1; + } + +public: + Histogram_binary(Histogram_type type_arg) : type(type_arg) + {} + + uint get_width() override + { + switch (type) { + case SINGLE_PREC_HB: + return (uint) size; + case DOUBLE_PREC_HB: + return (uint) (size / 2); + default: + DBUG_ASSERT(0); + } + return 0; + } +private: + uint get_value(uint i) + { + DBUG_ASSERT(i < get_width()); + switch (type) { + case SINGLE_PREC_HB: + return (uint) (((uint8 *) values)[i]); + case DOUBLE_PREC_HB: + return (uint) uint2korr(values + i * 2); + default: + DBUG_ASSERT(0); + } + return 0; + } + + /* Find the bucket which value 'pos' falls into. */ + uint find_bucket(double pos, bool first) + { + size_t val= (size_t) (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) && i < (get_width() - 1)) + i++; + + 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() override {return (uint)size;} + + Histogram_type get_type() override { return type; } + + bool parse(MEM_ROOT *mem_root, const char*, const char*, Field*, + const char *hist_data, size_t hist_data_len) override; + void serialize(Field *to_field) override; + void init_for_collection(MEM_ROOT *mem_root, Histogram_type htype_arg, + ulonglong size) override; + Histogram_builder *create_builder(Field *col, uint col_len, + ha_rows rows) override; + + 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: + int2store(values + i * 2, val * prec_factor()); + return; + default: + DBUG_ASSERT(0); + 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: + int2store(values + i * 2, uint2korr(values + i * 2 - 2)); + return; + default: + DBUG_ASSERT(0); + return; + } + } + + double range_selectivity(Field *field, key_range *min_endp, + key_range *max_endp, double avg_sel) override; + + /* + Estimate selectivity of "col=const" using a histogram + */ + double point_selectivity(Field *field, key_range *endpoint, + double avg_sel) override; +}; + + +/* + This is used to collect the the basic statistics from a Unique object: + - count of values + - count of distinct values + - count of distinct values that have occurred only once +*/ + +class Basic_stats_collector +{ + ulonglong count; /* number of values retrieved */ + ulonglong count_distinct; /* number of distinct values retrieved */ + /* number of distinct values that occurred only once */ + ulonglong count_distinct_single_occurence; + +public: + Basic_stats_collector() + { + count= 0; + count_distinct= 0; + count_distinct_single_occurence= 0; + } + + ulonglong get_count_distinct() const { return count_distinct; } + ulonglong get_count_single_occurence() const + { + return count_distinct_single_occurence; + } + ulonglong get_count() const { return count; } + + void next(void *elem, element_count elem_cnt) + { + count_distinct++; + if (elem_cnt == 1) + count_distinct_single_occurence++; + count+= elem_cnt; + } +}; + + +/* + Histogram_builder is a helper class that is used to build histograms + for columns. + + Do not create directly, call Histogram->get_builder(...); +*/ + +class Histogram_builder: public Sql_alloc +{ +protected: + Field *column; /* table field for which the histogram is built */ + uint col_length; /* size of this field */ + ha_rows records; /* number of records the histogram is built for */ + + Histogram_builder(Field *col, uint col_len, ha_rows rows) : + column(col), col_length(col_len), records(rows) + {} + +public: + // A histogram builder will also collect the counters + Basic_stats_collector counters; + + virtual int next(void *elem, element_count elem_cnt)=0; + virtual void finalize()=0; + virtual ~Histogram_builder(){} +}; + + +class Column_statistics; +class Index_statistics; + +/* Statistical data on a table */ + +class Table_statistics +{ +public: + my_bool cardinality_is_null; /* TRUE if the cardinality is unknown */ + uint columns; /* Number of columns in table */ + ha_rows cardinality; /* Number of rows in the table */ + 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 */ + + /* Array of records per key for index prefixes */ + ulonglong *idx_avg_frequency; + uchar *histograms; /* Sequence of histograms */ +}; + + +/* + Statistical data on a column + + Note: objects of this class may be "empty", where they have almost all fields + as zeros, for example, get_avg_frequency() will return 0. + + objects are allocated in alloc_statistics_for_table[_share]. +*/ + +class Column_statistics :public Sql_alloc +{ + +private: + static const uint Scale_factor_nulls_ratio= 100000; + static const uint Scale_factor_avg_length= 100000; + static const uint Scale_factor_avg_frequency= 100000; + +public: + ~Column_statistics() + { + delete histogram; + } + /* + Bitmap indicating what statistical characteristics + are available for the column + */ + uint32 column_stat_nulls; + + /* For the below two, see comments in get_column_range_cardinality() */ + /* Minimum value for the column */ + Field *min_value; + /* Maximum value for the column */ + Field *max_value; + +private: + + /* + The ratio Z/N multiplied by the scale factor Scale_factor_nulls_ratio, + where + N is the total number of rows, + Z is the number of nulls in the column + */ + ulong nulls_ratio; + + /* + Average number of bytes occupied by the representation of a + value of the column in memory buffers such as join buffer + multiplied by the scale factor Scale_factor_avg_length. + CHAR values are stripped of trailing spaces. + Flexible values are stripped of their length prefixes. + */ + ulonglong avg_length; + + /* + The ratio N/D multiplied by the scale factor Scale_factor_avg_frequency, + where + N is the number of rows with not null value in the column, + D the number of distinct values among them + */ + ulonglong avg_frequency; + +public: + Histogram_base *histogram; + bool histogram_exists; + + uint32 no_values_provided_bitmap() + { + return + ((1 << (COLUMN_STAT_HISTOGRAM-COLUMN_STAT_COLUMN_NAME))-1) << + (COLUMN_STAT_COLUMN_NAME+1); + } + + void set_all_nulls() + { + column_stat_nulls= no_values_provided_bitmap(); + } + + void set_not_null(uint stat_field_no) + { + column_stat_nulls&= ~(1 << stat_field_no); + } + + void set_null(uint stat_field_no) + { + column_stat_nulls|= (1 << stat_field_no); + } + + bool is_null(uint stat_field_no) + { + return MY_TEST(column_stat_nulls & (1 << stat_field_no)); + } + + double get_nulls_ratio() + { + return (double) nulls_ratio / Scale_factor_nulls_ratio; + } + + double get_avg_length() + { + return (double) avg_length / Scale_factor_avg_length; + } + + double get_avg_frequency() + { + return (double) avg_frequency / Scale_factor_avg_frequency; + } + + void set_nulls_ratio (double val) + { + nulls_ratio= (ulong) (val * Scale_factor_nulls_ratio); + } + + void set_avg_length (double val) + { + avg_length= (ulonglong) (val * Scale_factor_avg_length); + } + + void set_avg_frequency (double val) + { + avg_frequency= (ulonglong) (val * Scale_factor_avg_frequency); + } + + bool min_max_values_are_provided() + { + return !is_null(COLUMN_STAT_MIN_VALUE) && + !is_null(COLUMN_STAT_MAX_VALUE); + } + /* + This function checks whether the values for the fields of the statistical + tables that were NULL by DEFAULT for a column have changed or not. + + @retval + TRUE: Statistics are not present for a column + FALSE: Statisitics are present for a column + */ + bool no_stat_values_provided() + { + return (column_stat_nulls == no_values_provided_bitmap()); + } +}; + + +/* Statistical data on an index prefixes */ + +class Index_statistics +{ + +private: + static const uint Scale_factor_avg_frequency= 100000; + /* + The k-th element of this array contains the ratio N/D + multiplied by the scale factor Scale_factor_avg_frequency, + where N is the number of index entries without nulls + in the first k components, and D is the number of distinct + k-component prefixes among them + */ + ulonglong *avg_frequency; + +public: + + void init_avg_frequency(ulonglong *ptr) { avg_frequency= ptr; } + + bool avg_frequency_is_inited() { return avg_frequency != NULL; } + + double get_avg_frequency(uint i) + { + return (double) avg_frequency[i] / Scale_factor_avg_frequency; + } + + void set_avg_frequency(uint i, double val) + { + avg_frequency[i]= (ulonglong) (val * Scale_factor_avg_frequency); + } + +}; + +#endif /* SQL_STATISTICS_H */ |