summaryrefslogtreecommitdiff
path: root/sql/sql_statistics.h
blob: c399951b8284c48b7fde724e043072caa69c5573 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
/* 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-1301  USA */

#ifndef SQL_STATISTICS_H
#define SQL_STATISTICS_H

typedef
enum enum_use_stat_tables_mode
{
  NEVER,
  COMPLEMENTARY,
  PEFERABLY,
} Use_stat_tables_mode;

typedef
enum enum_histogram_type
{
  SINGLE_PREC_HB,
  DOUBLE_PREC_HB
} 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
};

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
};

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
};

inline
Use_stat_tables_mode get_use_stat_tables_mode(THD *thd)
{ 
  return (Use_stat_tables_mode) (thd->variables.use_stat_tables);
}

int read_statistics_for_tables_if_needed(THD *thd, TABLE_LIST *tables);
int collect_statistics_for_table(THD *thd, TABLE *table);
int alloc_statistics_for_table_share(THD* thd, TABLE_SHARE *share,
                                     bool is_safe);
int alloc_statistics_for_table(THD *thd, TABLE *table);
int update_statistics_for_table(THD *thd, TABLE *table);
int delete_statistics_for_table(THD *thd, LEX_STRING *db, LEX_STRING *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, LEX_STRING *db, LEX_STRING *tab,
                                LEX_STRING *new_db, LEX_STRING *new_tab);
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; /* 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);
    }
    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)
  {
    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);
    }
    return 0;
  }

  /* Find the bucket which value 'pos' falls into. */
  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) && 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() { 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:
      int2store(values + i * 2, 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:
      int2store(values + i * 2, uint2korr(values + i * 2 - 2));
      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;
  } 
  
  /*
    Estimate selectivity of "col=const" using a histogram
  */
  double point_selectivity(double pos, double avg_sel);
};


class Columns_statistics;
class Index_statistics;

static inline
int rename_table_in_stat_tables(THD *thd, const char *db, const char *tab,
                                const char *new_db, const char *new_tab)
{
  LEX_STRING od= { const_cast<char*>(db), strlen(db) };
  LEX_STRING ot= { const_cast<char*>(tab), strlen(tab) };
  LEX_STRING nd= { const_cast<char*>(new_db), strlen(new_db) };
  LEX_STRING nt= { const_cast<char*>(new_tab), strlen(new_tab) };
  return rename_table_in_stat_tables(thd, &od, &ot, &nd, &nt);
}


/* Statistical data on a table */

class Table_statistics
{

public:
  my_bool cardinality_is_null;      /* TRUE if the cardinality is unknown */
  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 */
  ulong *idx_avg_frequency;   /* Array of records per key for index prefixes */
  ulong total_hist_size;            /* Total size of all histograms */
  uchar *histograms;                /* Sequence of histograms       */                    
};


/* Statistical data on a column */

class Column_statistics
{

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:
  /* 
    Bitmap indicating  what statistical characteristics
    are available for the column
  */
  uint32 column_stat_nulls;

  /* 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.
  */
  ulong 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
  */
  ulong avg_frequency;

public:

  Histogram histogram;
 
  void set_all_nulls()
  {
    column_stat_nulls= 
      ((1 << (COLUMN_STAT_HISTOGRAM-COLUMN_STAT_COLUMN_NAME))-1) <<
      (COLUMN_STAT_COLUMN_NAME+1);
  }

  void set_not_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= (ulong) (val * Scale_factor_avg_length);
  }

  void set_avg_frequency (double val)
  {
    avg_frequency= (ulong) (val * Scale_factor_avg_frequency);
  }

};


/* 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 
  */
  ulong *avg_frequency;

public:

  void init_avg_frequency(ulong *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]= (ulong) (val * Scale_factor_avg_frequency);
  }

};

#endif /* SQL_STATISTICS_H */