path: root/sql/sql_statistics.h

/* 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 */