opt_qpf.h 11.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/*
   Copyright (c) 2013 Monty Program Ab

   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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */


Sergey Petrunya's avatar
Sergey Petrunya committed
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
/**************************************************************************************
 
  Query Plan Footprint (QPF) structures

  These structures
  - Can be produced in-expensively from query plan.
  - Store sufficient information to produce either a tabular or a json EXPLAIN
    output
  - Have methods that produce a tabular output.
 
*************************************************************************************/

class QPF_query;

/* 
  A node can be either a SELECT, or a UNION.
*/
class QPF_node : public Sql_alloc
{
public:
38
  enum qpf_node_type {QPF_UNION, QPF_SELECT, QPF_UPDATE, QPF_DELETE };
Sergey Petrunya's avatar
Sergey Petrunya committed
39
  virtual enum qpf_node_type get_type()= 0;
40 41


Sergey Petrunya's avatar
Sergey Petrunya committed
42 43 44 45 46 47
  virtual int get_select_id()= 0;

  /* 
    A node may have children nodes. When a node's QPF (Query Plan Footprint) is
    created, children nodes may not yet have QPFs.  This is why we store ids.
  */
48 49 50 51 52 53
  Dynamic_array<int> children;
  void add_child(int select_no)
  {
    children.append(select_no);
  }

Sergey Petrunya's avatar
Sergey Petrunya committed
54 55
  virtual int print_explain(QPF_query *query, select_result_sink *output, 
                            uint8 explain_flags)=0;
56 57 58
  
  int print_explain_for_children(QPF_query *query, select_result_sink *output, 
                                 uint8 explain_flags);
Sergey Petrunya's avatar
Sergey Petrunya committed
59 60 61 62
  virtual ~QPF_node(){}
};


Sergey Petrunya's avatar
Sergey Petrunya committed
63
class QPF_table_access;
Sergey Petrunya's avatar
Sergey Petrunya committed
64 65


Sergey Petrunya's avatar
Sergey Petrunya committed
66 67 68 69
/*
  Query Plan Footprint of a SELECT.
  
  A select can be:
Sergey Petrunya's avatar
Sergey Petrunya committed
70 71 72 73
  1. A degenerate case. In this case, message!=NULL, and it contains a 
     description of what kind of degenerate case it is (e.g. "Impossible 
     WHERE").
  2. a non-degenrate join. In this case, join_tabs describes the join.
Sergey Petrunya's avatar
Sergey Petrunya committed
74 75

  In the non-degenerate case, a SELECT may have a GROUP BY/ORDER BY operation.
Sergey Petrunya's avatar
Sergey Petrunya committed
76 77 78

  In both cases, the select may have children nodes. class QPF_node provides
  a way get node's children.
Sergey Petrunya's avatar
Sergey Petrunya committed
79 80 81 82 83 84 85 86 87 88 89
*/

class QPF_select : public QPF_node
{
public:
  enum qpf_node_type get_type() { return QPF_SELECT; }

  QPF_select() : 
    message(NULL), join_tabs(NULL),
    using_temporary(false), using_filesort(false)
  {}
90 91
  
  ~QPF_select();
Sergey Petrunya's avatar
Sergey Petrunya committed
92 93 94 95 96

  bool add_table(QPF_table_access *tab)
  {
    if (!join_tabs)
    {
97 98
      join_tabs= (QPF_table_access**) my_malloc(sizeof(QPF_table_access*) *
                                                MAX_TABLES, MYF(0));
Sergey Petrunya's avatar
Sergey Petrunya committed
99 100 101 102 103 104 105
      n_join_tabs= 0;
    }
    join_tabs[n_join_tabs++]= tab;
    return false;
  }

public:
Sergey Petrunya's avatar
Sergey Petrunya committed
106
  int select_id;
Sergey Petrunya's avatar
Sergey Petrunya committed
107 108
  const char *select_type;

Sergey Petrunya's avatar
Sergey Petrunya committed
109 110
  int get_select_id() { return select_id; }

Sergey Petrunya's avatar
Sergey Petrunya committed
111 112 113 114 115 116 117
  /*
    If message != NULL, this is a degenerate join plan, and all subsequent
    members have no info 
  */
  const char *message;
  
  /*
Sergey Petrunya's avatar
Sergey Petrunya committed
118 119
    A flat array of Query Plan Footprints. The order is "just like EXPLAIN
    would print them".
Sergey Petrunya's avatar
Sergey Petrunya committed
120 121 122 123 124 125 126
  */
  QPF_table_access** join_tabs;
  uint n_join_tabs;

  /* Global join attributes. In tabular form, they are printed on the first row */
  bool using_temporary;
  bool using_filesort;
127
  
Sergey Petrunya's avatar
Sergey Petrunya committed
128 129 130 131 132
  int print_explain(QPF_query *query, select_result_sink *output, 
                    uint8 explain_flags);
};


Sergey Petrunya's avatar
Sergey Petrunya committed
133 134 135 136 137 138
/* 
  Query Plan Footprint of a UNION.

  A UNION may or may not have "Using filesort".
*/

Sergey Petrunya's avatar
Sergey Petrunya committed
139 140 141 142 143 144 145
class QPF_union : public QPF_node
{
public:
  enum qpf_node_type get_type() { return QPF_UNION; }

  int get_select_id()
  {
146 147
    DBUG_ASSERT(union_members.elements() > 0);
    return union_members.at(0);
Sergey Petrunya's avatar
Sergey Petrunya committed
148
  }
149
  /*
Sergey Petrunya's avatar
Sergey Petrunya committed
150
    Members of the UNION.  Note: these are different from UNION's "children".
151 152 153 154 155 156
    Example:

      (select * from t1) union 
      (select * from t2) order by (select col1 from t3 ...)

    here 
Sergey Petrunya's avatar
Sergey Petrunya committed
157
      - select-from-t1 and select-from-t2 are "union members",
158 159 160
      - select-from-t3 is the only "child".
  */
  Dynamic_array<int> union_members;
Sergey Petrunya's avatar
Sergey Petrunya committed
161 162 163

  void add_select(int select_no)
  {
164
    union_members.append(select_no);
Sergey Petrunya's avatar
Sergey Petrunya committed
165 166 167 168 169 170 171 172
  }
  int print_explain(QPF_query *query, select_result_sink *output, 
                    uint8 explain_flags);

  const char *fake_select_type;
  bool using_filesort;
};

173 174
class QPF_delete;

Sergey Petrunya's avatar
Sergey Petrunya committed
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
  Query Plan Footprint (QPF) for a query (i.e. a statement).

  This should be able to survive when the query plan was deleted. Currently, 
  we do not intend for it survive until after query's MEM_ROOT is freed. It
  does surivive freeing of query's items.
   
  For reference, the process of post-query cleanup is as follows:

    >dispatch_command
    | >mysql_parse
    | |  ...
    | | lex_end()
    | |  ...
    | | >THD::cleanup_after_query
    | | | ...
    | | | free_items()
    | | | ...
    | | <THD::cleanup_after_query
    | |
    | <mysql_parse
    |
    | log_slow_statement()
    | 
    | free_root()
    | 
    >dispatch_command
  
  That is, the order of actions is:
    - free query's Items
    - write to slow query log 
    - free query's MEM_ROOT
    
Sergey Petrunya's avatar
Sergey Petrunya committed
209 210
*/

211
class QPF_query : public Sql_alloc
Sergey Petrunya's avatar
Sergey Petrunya committed
212 213 214
{
public:
  QPF_query();
215
  ~QPF_query();
Sergey Petrunya's avatar
Sergey Petrunya committed
216
  /* Add a new node */
Sergey Petrunya's avatar
Sergey Petrunya committed
217 218 219 220 221 222 223
  void add_node(QPF_node *node);

  /* This will return a select, or a union */
  QPF_node *get_node(uint select_id);

  /* This will return a select (even if there is a union with this id) */
  QPF_select *get_select(uint select_id);
224
  
225 226
  QPF_union *get_union(uint select_id);
  
227 228
  /* QPF_delete inherits from QPF_update */
  QPF_update *upd_del_plan;
Sergey Petrunya's avatar
Sergey Petrunya committed
229

Sergey Petrunya's avatar
Sergey Petrunya committed
230 231
  /* Produce a tabular EXPLAIN output */
  int print_explain(select_result_sink *output, uint8 explain_flags);
232 233 234
  
  /* If true, at least part of EXPLAIN can be printed */
  bool have_query_plan() { return upd_del_plan!= NULL || get_node(1) != NULL; }
235
  MEM_ROOT *mem_root;
Sergey Petrunya's avatar
Sergey Petrunya committed
236
private:
237 238
  Dynamic_array<QPF_union*> unions;
  Dynamic_array<QPF_select*> selects;
Sergey Petrunya's avatar
Sergey Petrunya committed
239 240 241 242 243 244 245
  
  /* 
    Debugging aid: count how many times add_node() was called. Ideally, it
    should be one, we currently allow O(1) query plan saves for each
    select or union.  The goal is not to have O(#rows_in_some_table), which 
    is unacceptable.
  */
246
  longlong operations;
Sergey Petrunya's avatar
Sergey Petrunya committed
247 248 249
};


Sergey Petrunya's avatar
Sergey Petrunya committed
250 251 252 253 254
/* 
  Some of the tags have matching text. See extra_tag_text for text names, and 
  QPF_table_access::append_tag_name() for code to convert from tag form to text
  form.
*/
Sergey Petrunya's avatar
Sergey Petrunya committed
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
enum Extra_tag
{
  ET_none= 0, /* not-a-tag */
  ET_USING_INDEX_CONDITION,
  ET_USING_INDEX_CONDITION_BKA,
  ET_USING, /* For quick selects of various kinds */
  ET_RANGE_CHECKED_FOR_EACH_RECORD,
  ET_USING_WHERE_WITH_PUSHED_CONDITION,
  ET_USING_WHERE,
  ET_NOT_EXISTS,

  ET_USING_INDEX,
  ET_FULL_SCAN_ON_NULL_KEY,
  ET_SKIP_OPEN_TABLE,
  ET_OPEN_FRM_ONLY,
  ET_OPEN_FULL_TABLE,

  ET_SCANNED_0_DATABASES,
  ET_SCANNED_1_DATABASE,
  ET_SCANNED_ALL_DATABASES,

  ET_USING_INDEX_FOR_GROUP_BY,

  ET_USING_MRR, // does not print "Using mrr". 

  ET_DISTINCT,
  ET_LOOSESCAN,
  ET_START_TEMPORARY,
  ET_END_TEMPORARY,
  ET_FIRST_MATCH,
  
  ET_USING_JOIN_BUFFER,

  ET_CONST_ROW_NOT_FOUND,
  ET_UNIQUE_ROW_NOT_FOUND,
  ET_IMPOSSIBLE_ON_CONDITION,

  ET_total
};


296 297 298 299 300 301 302 303 304
typedef struct st_qpf_bka_type
{
  bool incremental;
  const char *join_alg;
  StringBuffer<64> mrr_type;

} QPF_BKA_TYPE;


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
/*
  Data about how an index is used by some access method
*/
class QPF_index_use : public Sql_alloc
{
public:
  const char *key_name;
  uint key_len;
  /* will add #keyparts here if we implement EXPLAIN FORMAT=JSON */
};


/*
  QPF for quick range selects, as well as index_merge select
*/
class QPF_quick_select : public Sql_alloc
{
public:
  int quick_type;
  
  /* This is used when quick_type == QUICK_SELECT_I::QS_TYPE_RANGE */
  QPF_index_use range;
  
  /* Used in all other cases */
  List<QPF_quick_select> children;
  
  void print_extra(String *str);
  void print_key(String *str);
  void print_key_len(String *str);
private:
  void print_extra_recursive(String *str);
  const char *get_name_by_type();
};


Sergey Petrunya's avatar
Sergey Petrunya committed
340 341 342
/*
  Query Plan Footprint for a JOIN_TAB.
*/
343
class QPF_table_access : public Sql_alloc
Sergey Petrunya's avatar
Sergey Petrunya committed
344 345 346 347 348 349
{
public:
  void push_extra(enum Extra_tag extra_tag);

  /* Internals */
public:
350 351 352 353 354 355
  /* 
    0 means this tab is not inside SJM nest and should use QPF_select's id
    other value means the tab is inside an SJM nest.
  */
  int sjm_nest_select_id;

Sergey Petrunya's avatar
Sergey Petrunya committed
356
  /* id and 'select_type' are cared-of by the parent QPF_select */
357
  StringBuffer<32> table_name;
Sergey Petrunya's avatar
Sergey Petrunya committed
358 359 360

  enum join_type type;

361
  StringBuffer<32> used_partitions;
Sergey Petrunya's avatar
Sergey Petrunya committed
362 363
  bool used_partitions_set;
  
Sergey Petrunya's avatar
Sergey Petrunya committed
364
  /* Empty string means "NULL" will be printed */
365 366 367 368 369 370
  StringBuffer<32> possible_keys_str;
  
  /*
    Index use: key name and length.
    Note: that when one is accessing I_S tables, those may show use of 
    non-existant indexes.
371

372 373 374 375 376 377
    key.key_name == NULL means 'NULL' will be shown in tabular output.
    key.key_len == (uint)-1 means 'NULL' will be shown in tabular output.
  */
  QPF_index_use key;
  
  /*
Sergey Petrunya's avatar
Sergey Petrunya committed
378 379
    when type==JT_HASH_NEXT, 'key' stores the hash join pseudo-key.
    hash_next_key stores the table's key.
380 381 382
  */
  QPF_index_use hash_next_key;
  
383
  bool ref_set; /* not set means 'NULL' should be printed */
384
  StringBuffer<32> ref;
Sergey Petrunya's avatar
Sergey Petrunya committed
385

Sergey Petrunya's avatar
Sergey Petrunya committed
386
  bool rows_set; /* not set means 'NULL' should be printed */
Sergey Petrunya's avatar
Sergey Petrunya committed
387 388
  ha_rows rows;

Sergey Petrunya's avatar
Sergey Petrunya committed
389
  bool filtered_set; /* not set means 'NULL' should be printed */
390
  double filtered;
Sergey Petrunya's avatar
Sergey Petrunya committed
391

Sergey Petrunya's avatar
Sergey Petrunya committed
392 393 394 395 396 397
  /* 
    Contents of the 'Extra' column. Some are converted into strings, some have
    parameters, values for which are stored below.
  */
  Dynamic_array<enum Extra_tag> extra_tags;

Sergey Petrunya's avatar
Sergey Petrunya committed
398
  // Valid if ET_USING tag is present
399
  QPF_quick_select *quick_info;
Sergey Petrunya's avatar
Sergey Petrunya committed
400 401

  // Valid if ET_USING_INDEX_FOR_GROUP_BY is present
402
  bool loose_scan_is_scanning;
Sergey Petrunya's avatar
Sergey Petrunya committed
403 404 405 406 407
  
  // valid with ET_RANGE_CHECKED_FOR_EACH_RECORD
  key_map range_checked_map;

  // valid with ET_USING_MRR
408
  StringBuffer<32> mrr_type;
Sergey Petrunya's avatar
Sergey Petrunya committed
409 410

  // valid with ET_USING_JOIN_BUFFER
411
  QPF_BKA_TYPE bka_type;
Sergey Petrunya's avatar
Sergey Petrunya committed
412
  
413
  StringBuffer<32> firstmatch_table_name;
Sergey Petrunya's avatar
Sergey Petrunya committed
414 415 416 417 418 419 420 421

  int print_explain(select_result_sink *output, uint8 explain_flags, 
                    uint select_id, const char *select_type,
                    bool using_temporary, bool using_filesort);
private:
  void append_tag_name(String *str, enum Extra_tag tag);
};

422 423

/*
Sergey Petrunya's avatar
Sergey Petrunya committed
424 425 426 427
  Query Plan Footprint for single-table UPDATE. 
  
  This is similar to QPF_table_access, except that it is more restrictive.
  Also, it can have UPDATE operation options, but currently there aren't any.
428 429 430 431 432 433 434 435
*/

class QPF_update : public QPF_node
{
public:
  virtual enum qpf_node_type get_type() { return QPF_UPDATE; }
  virtual int get_select_id() { return 1; /* always root */ }

436 437
  const char *select_type;

438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457
  bool impossible_where;
  StringBuffer<64> table_name;

  enum join_type jtype;
  StringBuffer<128> possible_keys_line;
  StringBuffer<128> key_str;
  StringBuffer<128> key_len_str;
  StringBuffer<64> mrr_type;
  
  bool using_where;
  ha_rows rows;

  bool using_filesort;

  virtual int print_explain(QPF_query *query, select_result_sink *output, 
                            uint8 explain_flags);
};


/* 
Sergey Petrunya's avatar
Sergey Petrunya committed
458
  Query Plan Footprint for a single-table DELETE.
459 460 461 462 463
*/

class QPF_delete: public QPF_update
{
public:
Sergey Petrunya's avatar
Sergey Petrunya committed
464 465 466 467
  /*
    TRUE means we're going to call handler->delete_all_rows() and not read any
    rows.
  */
468 469 470 471 472 473 474 475 476
  bool deleting_all_rows;

  virtual enum qpf_node_type get_type() { return QPF_DELETE; }
  virtual int get_select_id() { return 1; /* always root */ }

  virtual int print_explain(QPF_query *query, select_result_sink *output, 
                            uint8 explain_flags);
};

Sergey Petrunya's avatar
Sergey Petrunya committed
477