MySQL  8.0.16
Source Code Documentation
sql_optimizer.h
Go to the documentation of this file.
1 #ifndef SQL_OPTIMIZER_INCLUDED
2 #define SQL_OPTIMIZER_INCLUDED
3 
4 /* Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights reserved.
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License, version 2.0,
8  as published by the Free Software Foundation.
9 
10  This program is also distributed with certain software (including
11  but not limited to OpenSSL) that is licensed under separate terms,
12  as designated in a particular file or component or in included license
13  documentation. The authors of MySQL hereby grant you an additional
14  permission to link the program and your derivative works with the
15  separately licensed software that they have included with MySQL.
16 
17  This program is distributed in the hope that it will be useful,
18  but WITHOUT ANY WARRANTY; without even the implied warranty of
19  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20  GNU General Public License, version 2.0, for more details.
21 
22  You should have received a copy of the GNU General Public License
23  along with this program; if not, write to the Free Software
24  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
25 
26 /**
27  @file sql/sql_optimizer.h
28  Classes used for query optimizations.
29 */
30 
31 /*
32  This structure is used to collect info on potentially sargable
33  predicates in order to check whether they become sargable after
34  reading const tables.
35  We form a bitmap of indexes that can be used for sargable predicates.
36  Only such indexes are involved in range analysis.
37 */
38 
39 #include <string.h>
40 #include <sys/types.h>
41 #include <algorithm>
42 #include <memory>
43 
44 #include "my_alloc.h"
45 #include "my_base.h"
46 #include "my_compiler.h"
47 #include "my_dbug.h"
48 #include "my_table_map.h"
49 #include "sql/field.h"
50 #include "sql/item.h"
51 #include "sql/item_subselect.h"
52 #include "sql/mem_root_array.h"
53 #include "sql/opt_explain_format.h" // Explain_sort_clause
54 #include "sql/row_iterator.h"
55 #include "sql/sql_array.h"
56 #include "sql/sql_class.h"
57 #include "sql/sql_const.h"
58 #include "sql/sql_executor.h" // Next_select_func
59 #include "sql/sql_lex.h"
60 #include "sql/sql_list.h"
62 #include "sql/sql_select.h" // Key_use
63 #include "sql/table.h"
64 #include "sql/temp_table_param.h"
65 #include "template_utils.h"
66 
67 class COND_EQUAL;
68 class Item_sum;
69 class Opt_trace_context;
70 class Window;
71 struct MYSQL_LOCK;
72 
74 
75 // Key_use has a trivial destructor, no need to run it from Mem_root_array.
77 
78 class Cost_model_server;
79 
81  Field *field; /* field against which to check sargability */
82  Item **arg_value; /* values of potential keys for lookups */
83  uint num_values; /* number of values in the above array */
84 };
85 
86 struct ROLLUP {
91  List<Item> *fields_list; ///< SELECT list
92  List<Item> *all_fields; ///< Including hidden fields
93 };
94 
95 /**
96  Wrapper for ORDER* pointer to trace origins of ORDER list
97 
98  As far as ORDER is just a head object of ORDER expression
99  chain, we need some wrapper object to associate flags with
100  the whole ORDER list.
101 */
103  /**
104  Private empty class to implement type-safe NULL assignment
105 
106  This private utility class allows us to implement a constructor
107  from NULL and only NULL (or 0 -- this is the same thing) and
108  an assignment operator from NULL.
109  Assignments from other pointers still prohibited since other
110  pointer types are incompatible with the "null" type, and the
111  casting is impossible outside of ORDER_with_src class, since
112  the "null" type is private.
113  */
114  struct null {};
115 
116  public:
117  ORDER *order; ///< ORDER expression that we are wrapping with this class
118  Explain_sort_clause src; ///< origin of order list
119 
120  private:
121  int flags; ///< bitmap of Explain_sort_property
122 
123  public:
125 
127  : order(order_arg),
128  src(src_arg),
129  flags(order_arg ? ESP_EXISTS : ESP_none) {}
130 
131  /**
132  Type-safe NULL assignment
133 
134  See a commentary for the "null" type above.
135  */
137  clean();
138  return *this;
139  }
140 
141  /**
142  Type-safe constructor from NULL
143 
144  See a commentary for the "null" type above.
145  */
147 
148  /**
149  Transparent access to the wrapped order list
150 
151  These operators are safe, since we don't do any conversion of
152  ORDER_with_src value, but just an access to the wrapped
153  ORDER pointer value.
154  We can use ORDER_with_src objects instead ORDER pointers in
155  a transparent way without accessor functions.
156 
157  @note This operator also implements safe "operator bool()"
158  functionality.
159  */
160  operator ORDER *() { return order; }
161  operator const ORDER *() const { return order; }
162 
163  ORDER *operator->() const { return order; }
164 
165  void clean() {
166  order = NULL;
167  src = ESC_none;
168  flags = ESP_none;
169  }
170 
171  int get_flags() const {
173  return flags;
174  }
175 };
176 
177 class JOIN {
178  JOIN(const JOIN &rhs); /**< not implemented */
179  JOIN &operator=(const JOIN &rhs); /**< not implemented */
180 
181  public:
182  JOIN(THD *thd_arg, SELECT_LEX *select)
183  : select_lex(select),
184  unit(select->master_unit()),
185  thd(thd_arg),
186  join_tab(NULL),
187  qep_tab(NULL),
188  best_ref(NULL),
189  map2table(NULL),
190  map2qep_tab(NULL),
192  tables(0),
193  primary_tables(0),
194  const_tables(0),
195  tmp_tables(0),
196  send_group_parts(0),
199  // @todo Can this be substituted with select->is_explicitly_grouped()?
200  grouped(select->is_explicitly_grouped()),
202  all_table_map(0),
203  // Inner tables may always be considered to be constant:
207  send_records(0),
208  found_records(0),
209  examined_rows(0),
210  row_limit(0),
211  m_select_limit(0),
214  positions(NULL),
216  best_read(0.0),
217  best_rowcount(0),
218  sort_cost(0.0),
219  windowing_cost(0.0),
220  // Needed in case optimizer short-cuts, set properly in
221  // make_tmp_tables_info()
222  fields(&select->item_list),
223  group_fields(),
225  sum_funcs(NULL),
226  sum_funcs_end(),
227  tmp_table_param(thd_arg->mem_root),
228  lock(thd->lock),
229  rollup(),
230  // @todo Can this be substituted with select->is_implicitly_grouped()?
231  implicit_grouping(select->is_implicitly_grouped()),
232  select_distinct(select->is_distinct()),
241  all_fields(select->all_fields),
242  fields_list(select->fields_list),
243  tmp_all_fields(nullptr),
244  tmp_fields_list(nullptr),
245  error(0),
246  order(select->order_list.first, ESC_ORDER_BY),
247  group_list(select->group_list.first, ESC_GROUP_BY),
248  m_windows(select->m_windows),
251  explain_flags(),
252  /*
253  Those four members are meaningless before JOIN::optimize(), so force a
254  crash if they are used before that.
255  */
256  where_cond((Item *)1),
257  having_cond((Item *)1),
258  having_for_explain((Item *)1),
259  tables_list((TABLE_LIST *)1),
260  cond_equal(NULL),
261  return_tab(0),
262  ref_items(nullptr),
269  sj_tmp_tables(),
270  sjm_exec_list(),
271  group_sent(false),
273  with_json_agg(select->json_agg_func_used()),
274  optimized(false),
275  executed(false),
284  // Calculate the number of groups
285  for (ORDER *group = group_list; group; group = group->next)
287  }
288 
289  /// Query block that is optimized and executed using this JOIN
291  /// Query expression referring this query block
293  /// Thread handler
294  THD *const thd;
295 
296  /**
297  Optimal query execution plan. Initialized with a tentative plan in
298  JOIN::make_join_plan() and later replaced with the optimal plan in
299  get_best_combination().
300  */
302  /// Array of QEP_TABs
304 
305  /**
306  Array of plan operators representing the current (partial) best
307  plan. The array is allocated in JOIN::make_join_plan() and is valid only
308  inside this function. Initially (*best_ref[i]) == join_tab[i].
309  The optimizer reorders best_ref.
310  */
312  JOIN_TAB **map2table; ///< mapping between table indexes and JOIN_TABs
313  QEP_TAB **map2qep_tab; ///< mapping between table indexes and QEB_TABs
314  /*
315  The table which has an index that allows to produce the requried ordering.
316  A special value of 0x1 means that the ordering will be produced by
317  passing 1st non-const table to filesort(). NULL means no such table exists.
318  */
320  /**
321  Before plan has been created, "tables" denote number of input tables in the
322  query block and "primary_tables" is equal to "tables".
323  After plan has been created (after JOIN::get_best_combination()),
324  the JOIN_TAB objects are enumerated as follows:
325  - "tables" gives the total number of allocated JOIN_TAB objects
326  - "primary_tables" gives the number of input tables, including
327  materialized temporary tables from semi-join operation.
328  - "const_tables" are those tables among primary_tables that are detected
329  to be constant.
330  - "tmp_tables" is 0, 1 or 2 (more if windows) and counts the maximum
331  possible number of intermediate tables in post-processing (ie sorting and
332  duplicate removal).
333  Later, tmp_tables will be adjusted to the correct number of
334  intermediate tables, @see JOIN::make_tmp_tables_info.
335  - The remaining tables (ie. tables - primary_tables - tmp_tables) are
336  input tables to materialized semi-join operations.
337  The tables are ordered as follows in the join_tab array:
338  1. const primary table
339  2. non-const primary tables
340  3. intermediate sort/group tables
341  4. possible holes in array
342  5. semi-joined tables used with materialization strategy
343  */
344  uint tables; ///< Total number of tables in query block
345  uint primary_tables; ///< Number of primary input tables in query block
346  uint const_tables; ///< Number of primary tables deemed constant
347  uint tmp_tables; ///< Number of temporary tables used by query
349  /**
350  Indicates that the data will be aggregated (typically GROUP BY),
351  _and_ that it is already processed in an order that is compatible with
352  the grouping in use (e.g. because we are scanning along an index,
353  or because an earlier step sorted the data in a group-compatible order).
354 
355  Note that this flag changes value at multiple points during optimization;
356  if it's set when a temporary table is created, this means we aggregate
357  into said temporary table (end_write_group is chosen instead of end_write),
358  but if it's set later, it means that we can aggregate as we go,
359  just before sending the data to the client (end_send_group is chosen
360  instead of end_send).
361 
362  @see make_group_fields, alloc_group_fields, JOIN::exec
363  */
365  bool seen_first_record; ///< Whether we've seen at least one row already
366  bool grouped; ///< If query contains GROUP BY clause
367  bool do_send_rows; ///< If true, send produced rows using query_result
368  table_map all_table_map; ///< Set of tables contained in query
369  table_map const_table_map; ///< Set of tables found to be const
370  /**
371  Const tables which are either:
372  - not empty
373  - empty but inner to a LEFT JOIN, thus "considered" not empty for the
374  rest of execution (a NULL-complemented row will be used).
375  */
377  /**
378  Used in some loops which scan the JOIN's tables: it is the bitmap of all
379  tables which are dependencies of lateral derived tables which the loop
380  has not yet processed.
381  */
383 
384  /* Number of records produced after join + group operation */
389  // m_select_limit is used to decide if we are likely to scan the whole table.
391  /**
392  Used to fetch no more than given amount of rows per one
393  fetch operation of server side cursor.
394  The value is checked in end_send and end_send_group in fashion, similar
395  to offset_limit_cnt:
396  - fetch_limit= HA_POS_ERROR if there is no cursor.
397  - when we open a cursor, we set fetch_limit to 0,
398  - on each fetch iteration we add num_rows to fetch to fetch_limit
399  */
401 
402  /**
403  This is the result of join optimization.
404 
405  @note This is a scratch array, not used after get_best_combination().
406  */
408 
409  /******* Join optimization state members start *******/
410 
411  /* Current join optimization state */
413 
414  /* We also maintain a stack of join optimization states in * join->positions[]
415  */
416  /******* Join optimization state members end *******/
417 
419  /**
420  The cost of best complete join plan found so far during optimization,
421  after optimization phase - cost of picked join order (not taking into
422  account the changes made by test_if_skip_sort_order()).
423  */
424  double best_read;
425  /**
426  The estimated row count of the plan with best read time (see above).
427  */
429  /// Expected cost of filesort.
430  double sort_cost;
431  /// Expected cost of windowing;
436  /**
437  Describes a temporary table.
438  Each tmp table has its own tmp_table_param.
439  The one here has two roles:
440  - is transiently used as a model by create_intermediate_table(), to build
441  the tmp table's own tmp_table_param.
442  - is also used as description of the pseudo-tmp-table of grouping
443  (REF_SLICE_ORDERED_GROUP_BY) (e.g. in end_send_group()).
444  */
447 
448  ROLLUP rollup; ///< Used with rollup
449  bool implicit_grouping; ///< True if aggregated but no GROUP BY
450 
451  /**
452  At construction time, set if SELECT DISTINCT. May be reset to false
453  later, when we set up a temporary table operation that deduplicates for us.
454  */
456 
457  /**
458  If we have the GROUP BY statement in the query,
459  but the group_list was emptied by optimizer, this
460  flag is true.
461  It happens when fields in the GROUP BY are from
462  constant table
463  */
465 
466  /*
467  simple_xxxxx is set if ORDER/GROUP BY doesn't include any references
468  to other tables than the first non-constant table in the JOIN.
469  It's also set if ORDER/GROUP BY is empty.
470  Used for deciding for or against using a temporary table to compute
471  GROUP/ORDER BY.
472  */
474 
475  /*
476  m_ordered_index_usage is set if an ordered index access
477  should be used instead of a filesort when computing
478  ORDER/GROUP BY.
479  */
480  enum {
481  ORDERED_INDEX_VOID, // No ordered index avail.
482  ORDERED_INDEX_GROUP_BY, // Use index for GROUP BY
483  ORDERED_INDEX_ORDER_BY // Use index for ORDER BY
485 
486  /**
487  Is set if we have a GROUP BY and we have ORDER BY on a constant or when
488  sorting isn't required.
489  */
491 
492  /**
493  If true we need a temporary table on the result set before any
494  windowing steps, e.g. for DISTINCT or we have a query ORDER BY.
495  See details in JOIN::optimize
496  */
498 
499  /// If JOIN has lateral derived tables (is set at start of planning)
501 
502  /// Used and updated by JOIN::make_join_plan() and optimize_keyuse()
504 
505  /// List storing all expressions used in query block
507 
508  /// List storing all expressions of select list
510 
511  /**
512  This is similar to tmp_fields_list, but it also contains necessary
513  extras: expressions added for ORDER BY, GROUP BY, window clauses,
514  underlying items of split items.
515  */
517 
518  /**
519  Array of pointers to lists of expressions.
520  Each list represents the SELECT list at a certain stage of execution.
521  This array is only used when the query makes use of tmp tables: after
522  writing to tmp table (e.g. for GROUP BY), if this write also does a
523  function's calculation (e.g. of SUM), after the write the function's value
524  is in a column of the tmp table. If a SELECT list expression is the SUM,
525  and we now want to read that materialized SUM and send it forward, a new
526  expression (Item_field type instead of Item_sum), is needed. The new
527  expressions are listed in JOIN::tmp_fields_list[x]; 'x' is a number
528  (REF_SLICE_).
529  Same is applicable to tmp_all_fields.
530  @see JOIN::make_tmp_tables_info()
531  */
533 
534  int error; ///< set in optimize(), exec(), prepare_result()
535 
536  /**
537  ORDER BY and GROUP BY lists, to transform with prepare,optimize and exec
538  */
540 
541  /**
542  Any window definitions
543  */
545 
546  /**
547  True if a window requires a certain order of rows, which implies that any
548  order of rows coming out of the pre-window join will be disturbed.
549  */
551 
552  /// If we have set up tmp tables for windowing, @see make_tmp_tables_info
554 
555  /**
556  Buffer to gather GROUP BY, ORDER BY and DISTINCT QEP details for EXPLAIN
557  */
559 
560  /**
561  JOIN::having_cond is initially equal to select_lex->having_cond, but may
562  later be changed by optimizations performed by JOIN.
563  The relationship between the JOIN::having_cond condition and the
564  associated variable select_lex->having_value is so that
565  having_value can be:
566  - COND_UNDEF if a having clause was not specified in the query or
567  if it has not been optimized yet
568  - COND_TRUE if the having clause is always true, in which case
569  JOIN::having_cond is set to NULL.
570  - COND_FALSE if the having clause is impossible, in which case
571  JOIN::having_cond is set to NULL
572  - COND_OK otherwise, meaning that the having clause needs to be
573  further evaluated
574  All of the above also applies to the where_cond/select_lex->cond_value
575  pair.
576  */
577  /**
578  Optimized WHERE clause item tree (valid for one single execution).
579  Used in JOIN execution if no tables. Otherwise, attached in pieces to
580  JOIN_TABs and then not used in JOIN execution.
581  Printed by EXPLAIN EXTENDED.
582  Initialized by SELECT_LEX::get_optimizable_conditions().
583  */
585  /**
586  Optimized HAVING clause item tree (valid for one single execution).
587  Used in JOIN execution, as last "row filtering" step. With one exception:
588  may be pushed to the JOIN_TABs of temporary tables used in DISTINCT /
589  GROUP BY (see JOIN::make_tmp_tables_info()); in that case having_cond is
590  set to NULL, but is first saved to having_for_explain so that EXPLAIN
591  EXTENDED can still print it.
592  Initialized by SELECT_LEX::get_optimizable_conditions().
593  */
595  Item *having_for_explain; ///< Saved optimized HAVING for EXPLAIN
596  /**
597  Pointer set to select_lex->get_table_list() at the start of
598  optimization. May be changed (to NULL) only if optimize_aggregated_query()
599  optimizes tables away.
600  */
603  /*
604  Join tab to return to. Points to an element of join->join_tab array, or to
605  join->join_tab[-1].
606  This is used at execution stage to shortcut join enumeration. Currently
607  shortcutting is done to handle outer joins or handle semi-joins with
608  FirstMatch strategy.
609  */
611 
612  /**
613  ref_items is an array of 5 slices, each containing an array of Item
614  pointers. ref_items is used in different phases of query execution.
615  - slice 0 is initially the same as SELECT_LEX::base_ref_items, ie it is
616  the set of items referencing fields from base tables. During optimization
617  and execution it may be temporarily overwritten by slice 1-3.
618  - slice 1 is a representation of the used items when being read from
619  the first temporary table.
620  - slice 2 is a representation of the used items when being read from
621  the second temporary table.
622  - slice 3 is a representation of the used items when used in
623  aggregation but no actual temporary table is needed.
624  - slice 4 is a copy of the original slice 0. It is created if
625  slice overwriting is necessary, and it is used to restore
626  original values in slice 0 after having been overwritten.
627  - slices 5 -> N are used by windowing:
628  first are all the window's out tmp tables,
629  the next indexes are reserved for the windows' frame buffers (in the same
630  order), if any, e.g.
631 
632  One window: 5: window 1's out table
633  6: window 1's FB
634 
635  Two windows: 5: window 1's out table
636  6: window 2's out table
637  7: window 1's FB
638  8: window 2's FB
639  and so on.
640 
641  Slice 0 is allocated for the lifetime of a statement, whereas slices 1-4
642  are associated with a single optimization. The size of slice 0 determines
643  the slice size used when allocating the other slices.
644  */
646  *ref_items; // cardinality: REF_SLICE_SAVED_BASE + 1 + #windows*2
647 
648  /**
649  If slice REF_SLICE_ORDERED_GROUP_BY has been created, this is the QEP_TAB
650  which is right before calculation of items in this slice.
651  */
653 
654  /**
655  The slice currently stored in ref_items[0].
656  Used to restore the base ref_items slice from the "save" slice after it
657  has been overwritten by another slice (1-3).
658  */
660 
661  /**
662  Used only if this query block is recursive. Contains count of
663  all executions of this recursive query block, since the last
664  this->reset().
665  */
667 
668  /**
669  <> NULL if optimization has determined that execution will produce an
670  empty result before aggregation, contains a textual explanation on why
671  result is empty. Implicitly grouped queries may still produce an
672  aggregation row.
673  @todo - suggest to set to "Preparation determined that query is empty"
674  when SELECT_LEX::is_empty_query() is true.
675  */
676  const char *zero_result_cause;
677 
678  /**
679  True if, at this stage of processing, subquery materialization is allowed
680  for children subqueries of this JOIN (those in the SELECT list, in WHERE,
681  etc). If false, and we have to evaluate a subquery at this stage, then we
682  must choose EXISTS.
683  */
685  /**
686  True if plan search is allowed to use references to expressions outer to
687  this JOIN (for example may set up a 'ref' access looking up an outer
688  expression in the index, etc).
689  */
691 
692  /* Temporary tables used to weed-out semi-join duplicates */
695  /* end of allocation caching storage */
696 
697  /** Exec time only: true <=> current group has been sent */
699  /// If true, calculate found rows for this query block
701 
702  /**
703  This will force tmp table to NOT use index + update for group
704  operation as it'll cause [de]serialization for each json aggregated
705  value and is very ineffective (times worse).
706  Server should use filesort, or tmp table + filesort to resolve GROUP BY
707  with JSON aggregate functions.
708  */
710 
711  /// True if plan is const, ie it will return zero or one rows.
712  bool plan_is_const() const { return const_tables == primary_tables; }
713 
714  /**
715  True if plan contains one non-const primary table (ie not including
716  tables taking part in semi-join materialization).
717  */
719 
720  int optimize();
721  void reset();
722  void exec();
723  bool prepare_result();
724  bool destroy();
725  bool alloc_func_list();
727  bool before_group_by, bool recompute = false);
728 
729  /**
730  Overwrites one slice of ref_items with the contents of another slice.
731  In the normal case, dst and src have the same size().
732  However: the rollup slices may have smaller size than slice_sz.
733  */
734  void copy_ref_item_slice(uint dst_slice, uint src_slice) {
735  copy_ref_item_slice(ref_items[dst_slice], ref_items[src_slice]);
736  }
738  DBUG_ASSERT(dst_arr.size() >= src_arr.size());
739  void *dest = dst_arr.array();
740  const void *src = src_arr.array();
741  if (!src_arr.is_null())
742  memcpy(dest, src, src_arr.size() * src_arr.element_size());
743  }
744 
745  /**
746  Allocate a ref_item slice, assume that slice size is in ref_items[0]
747 
748  @param thd_arg thread handler
749  @param sliceno The slice number to allocate in JOIN::ref_items
750 
751  @returns false if success, true if error
752  */
753  bool alloc_ref_item_slice(THD *thd_arg, int sliceno) {
754  DBUG_ASSERT(sliceno > 0 && ref_items[sliceno].is_null());
755  size_t count = ref_items[0].size();
756  Item **slice =
757  pointer_cast<Item **>(thd_arg->alloc(sizeof(Item *) * count));
758  if (slice == NULL) return true;
759  ref_items[sliceno] = Ref_item_array(slice, count);
760  return false;
761  }
762  /**
763  Overwrite the base slice of ref_items with the slice supplied as argument.
764 
765  @param sliceno number to overwrite the base slice with, must be 1-4 or
766  4 + windowno.
767  */
768  void set_ref_item_slice(uint sliceno) {
769  DBUG_ASSERT((int)sliceno >= 1);
770  if (current_ref_item_slice != sliceno) {
772  DBUG_PRINT("info",
773  ("ref slice %u -> %u", current_ref_item_slice, sliceno));
774  current_ref_item_slice = sliceno;
775  }
776  }
777 
778  /// @note do also consider Switch_ref_item_slice
780 
781  /**
782  Returns the clone of fields_list which is appropriate for evaluating
783  expressions at the current stage of execution; which stage is denoted by
784  the value of current_ref_item_slice.
785  */
787 
788  bool optimize_rollup();
791  Item_sum ***func);
793  List<Item> &fields);
794  bool rollup_send_data(uint idx);
797  /**
798  Release memory and, if possible, the open tables held by this execution
799  plan (and nested plans). It's used to release some tables before
800  the end of execution in order to increase concurrency and reduce
801  memory consumption.
802  */
803  void join_free();
804  /** Cleanup this JOIN. Not a full cleanup. reusable? */
805  void cleanup();
806 
807  bool clear_fields(table_map *save_nullinfo);
808  void restore_fields(table_map save_nullinfo);
809 
810  /**
811  Return whether the caller should send a row even if the join
812  produced no rows if:
813  - there is an aggregate function (sum_func_count!=0), and
814  - the query is not grouped, and
815  - a possible HAVING clause evaluates to TRUE.
816 
817  @note: if there is a having clause, it must be evaluated before
818  returning the row.
819  */
820  bool send_row_on_empty_set() const {
821  return (do_send_rows && tmp_table_param.sum_func_count != 0 &&
824  }
825 
826  bool generate_derived_keys();
827  void finalize_derived_keys();
828  bool get_best_combination();
829  bool attach_join_conditions(plan_idx last_tab);
832  bool force_stable_sort = false);
834  void refine_best_rowcount();
836  table_map plan_tables, uint idx);
838 
839  void mark_const_table(JOIN_TAB *table, Key_use *key);
840  /// State of execution plan. Currently used only for EXPLAIN
842  NO_PLAN, ///< No plan is ready yet
843  ZERO_RESULT, ///< Zero result cause is set
844  NO_TABLES, ///< Plan has no tables
845  PLAN_READY ///< Plan is ready
846  };
847  /// See enum_plan_state
849  bool is_optimized() const { return optimized; }
850  void set_optimized() { optimized = true; }
851  bool is_executed() const { return executed; }
852  void set_executed() { executed = true; }
853 
854  /**
855  Retrieve the cost model object to be used for this join.
856 
857  @return Cost model object for the join
858  */
859 
860  const Cost_model_server *cost_model() const {
861  DBUG_ASSERT(thd != NULL);
862  return thd->cost_model();
863  }
864 
865  /**
866  Check if FTS index only access is possible
867  */
868  bool fts_index_access(JOIN_TAB *tab);
869 
871  /**
872  Propagate dependencies between tables due to outer join relations.
873 
874  @returns false if success, true if error
875  */
876  bool propagate_dependencies();
877 
878  /**
879  Returns whether one should send the current row on to the output,
880  or ignore it. (In particular, this implements OFFSET handling
881  in the non-iterator executor.)
882  */
884  if (!do_send_rows) {
885  return false;
886  }
887  if (unit->offset_limit_cnt > 0) {
889  return false;
890  } else {
891  return true;
892  }
893  }
894 
895  /**
896  Handle offloading of query parts to the underlying engines, when
897  such is supported by their implementation.
898 
899  @returns 0 if success, 1 if error
900  */
901  int push_to_engines();
902 
903  RowIterator *root_iterator() const { return m_root_iterator.get(); }
905  return move(m_root_iterator);
906  }
907 
908  private:
909  bool optimized; ///< flag to avoid double optimization in EXPLAIN
910  bool executed; ///< Set by exec(), reset by reset()
911 
912  /// Final execution plan state. Currently used only for EXPLAIN
914 
915  public:
916  /*
917  When join->select_count is set, tables will not be optimized away.
918  The call to records() will be delayed until the execution phase and
919  the counting will be done on an index of Optimizer's choice.
920  The index will be decided in find_shortest_key(), called from
921  optimize_aggregated_query().
922  */
924 
925  private:
926  /**
927  Create a temporary table to be used for processing DISTINCT/ORDER
928  BY/GROUP BY.
929 
930  @note Will modify JOIN object wrt sort/group attributes
931 
932  @param tab the JOIN_TAB object to attach created table to
933  @param tmp_table_fields List of items that will be used to define
934  column types of the table.
935  @param tmp_table_group Group key to use for temporary table, NULL if none.
936  @param save_sum_fields If true, do not replace Item_sum items in
937  @c tmp_fields list with Item_field items referring
938  to fields in temporary table.
939 
940  @returns false on success, true on failure
941  */
942  bool create_intermediate_table(QEP_TAB *tab, List<Item> *tmp_table_fields,
943  ORDER_with_src &tmp_table_group,
944  bool save_sum_fields);
945 
946  /**
947  Optimize distinct when used on a subset of the tables.
948 
949  E.g.,: SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
950  In this case we can stop scanning t2 when we have found one t1.a
951  */
952  void optimize_distinct();
953 
954  /**
955  Function sets FT hints, initializes FT handlers and
956  checks if FT index can be used as covered.
957  */
958  bool optimize_fts_query();
959 
960  bool prune_table_partitions();
961  /**
962  Initialize key dependencies for join tables.
963 
964  TODO figure out necessity of this method. Current test
965  suite passed without this intialization.
966  */
968  JOIN_TAB *const tab_end = join_tab + tables;
969  for (JOIN_TAB *tab = join_tab; tab < tab_end; tab++)
970  tab->key_dependent = tab->dependent;
971  }
972 
973  private:
974  void set_prefix_tables();
975  void cleanup_item_list(List<Item> &items) const;
976  void set_semijoin_embedding();
977  bool make_join_plan();
978  bool init_planner_arrays();
979  bool extract_const_tables();
982  bool estimate_rowcount();
983  void optimize_keyuse();
984  void set_semijoin_info();
985  /**
986  An utility function - apply heuristics and optimize access methods to tables.
987  @note Side effect - this function could set 'Impossible WHERE' zero
988  result.
989  */
990  void adjust_access_methods();
991  void update_depend_map();
993  /**
994  Fill in outer join related info for the execution plan structure.
995 
996  For each outer join operation left after simplification of the
997  original query the function set up the following pointers in the linear
998  structure join->join_tab representing the selected execution plan.
999  The first inner table t0 for the operation is set to refer to the last
1000  inner table tk through the field t0->last_inner.
1001  Any inner table ti for the operation are set to refer to the first
1002  inner table ti->first_inner.
1003  The first inner table t0 for the operation is set to refer to the
1004  first inner table of the embedding outer join operation, if there is any,
1005  through the field t0->first_upper.
1006  The on expression for the outer join operation is attached to the
1007  corresponding first inner table through the field t0->on_expr_ref.
1008  Here ti are structures of the JOIN_TAB type.
1009 
1010  EXAMPLE. For the query:
1011  @code
1012  SELECT * FROM t1
1013  LEFT JOIN
1014  (t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
1015  ON (t1.a=t2.a AND t1.b=t3.b)
1016  WHERE t1.c > 5,
1017  @endcode
1018 
1019  given the execution plan with the table order t1,t2,t3,t4
1020  is selected, the following references will be set;
1021  t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
1022  t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
1023  on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
1024  *t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
1025 
1026  @note
1027  The function assumes that the simplification procedure has been
1028  already applied to the join query (see simplify_joins).
1029  This function can be called only after the execution plan
1030  has been chosen.
1031  */
1032  void make_outerjoin_info();
1033 
1034  /**
1035  Initialize ref access for all tables that use it.
1036 
1037  @return False if success, True if error
1038 
1039  @note We cannot setup fields used for ref access before we have sorted
1040  the items within multiple equalities according to the final order of
1041  the tables involved in the join operation. Currently, this occurs in
1042  @see substitute_for_best_equal_field().
1043  */
1044  bool init_ref_access();
1045  bool alloc_qep(uint n);
1046  void unplug_join_tabs();
1047  bool setup_semijoin_materialized_table(JOIN_TAB *tab, uint tableno,
1048  const POSITION *inner_pos,
1049  POSITION *sjm_pos);
1050 
1051  bool add_having_as_tmp_table_cond(uint curr_tmp_table);
1052  bool make_tmp_tables_info();
1053  void set_plan_state(enum_plan_state plan_state_arg);
1056  ORDER *remove_const(ORDER *first_order, Item *cond, bool change_list,
1057  bool *simple_order, bool group_by);
1058 
1059  /**
1060  Check whether this is a subquery that can be evaluated by index look-ups.
1061  If so, change subquery engine to subselect_indexsubquery_engine.
1062 
1063  @retval 1 engine was changed
1064  @retval 0 engine wasn't changed
1065  @retval -1 OOM
1066  */
1067  int replace_index_subquery();
1068 
1069  /**
1070  Optimize DISTINCT, GROUP BY, ORDER BY clauses
1071 
1072  @retval false ok
1073  @retval true an error occured
1074  */
1076 
1077  /**
1078  Test if an index could be used to replace filesort for ORDER BY/GROUP BY
1079 
1080  @details
1081  Investigate whether we may use an ordered index as part of either
1082  DISTINCT, GROUP BY or ORDER BY execution. An ordered index may be
1083  used for only the first of any of these terms to be executed. This
1084  is reflected in the order which we check for test_if_skip_sort_order()
1085  below. However we do not check for DISTINCT here, as it would have
1086  been transformed to a GROUP BY at this stage if it is a candidate for
1087  ordered index optimization.
1088  If a decision was made to use an ordered index, the availability
1089  if such an access path is stored in 'm_ordered_index_usage' for later
1090  use by 'execute' or 'explain'
1091  */
1092  void test_skip_sort();
1093 
1094  bool alloc_indirection_slices();
1095 
1096  /**
1097  If possible, convert the executor structures to a set of row iterators,
1098  storing the result in m_root_iterator. If not, m_root_iterator will remain
1099  nullptr.
1100  */
1101  void create_iterators();
1102 
1103  /**
1104  An iterator you can read from to get all records for this query.
1105 
1106  May be nullptr even after create_iterators() if the current query
1107  is not supported by the iterator executor.
1108  */
1110 };
1111 
1112 /**
1113  RAII class to ease the temporary switching to a different slice of
1114  the ref item array.
1115 */
1119 
1120  public:
1121  Switch_ref_item_slice(JOIN *join_arg, uint new_v)
1122  : join(join_arg), saved(join->get_ref_item_slice()) {
1123  if (!join->ref_items[new_v].is_null()) join->set_ref_item_slice(new_v);
1124  }
1126 };
1127 
1128 /**
1129  RAII class to ease the call of LEX::mark_broken() if error.
1130  Used during preparation and optimization of DML queries.
1131 */
1133  public:
1134  Prepare_error_tracker(THD *thd_arg) : thd(thd_arg) {}
1136  if (unlikely(thd->is_error())) thd->lex->mark_broken();
1137  }
1138 
1139  private:
1140  THD *const thd;
1141 };
1142 
1143 bool uses_index_fields_only(Item *item, TABLE *tbl, uint keyno,
1144  bool other_tbls_ok);
1145 bool remove_eq_conds(THD *thd, Item *cond, Item **retcond,
1146  Item::cond_result *cond_value);
1147 bool optimize_cond(THD *thd, Item **conds, COND_EQUAL **cond_equal,
1148  List<TABLE_LIST> *join_list, Item::cond_result *cond_value);
1150  COND_EQUAL *cond_equal,
1151  JOIN_TAB **table_join_idx);
1152 bool build_equal_items(THD *thd, Item *cond, Item **retcond,
1153  COND_EQUAL *inherited, bool do_inherit,
1154  List<TABLE_LIST> *join_list,
1155  COND_EQUAL **cond_equal_ref);
1158  Item_field **fields,
1159  List<Item> outer_exprs);
1160 Item_field *get_best_field(Item_field *item_field, COND_EQUAL *cond_equal);
1161 Item *make_cond_for_table(THD *thd, Item *cond, table_map tables,
1162  table_map used_table, bool exclude_expensive_cond);
1164  uint first_unused);
1165 
1166 /**
1167  Returns true if arguments are a temporal Field having no date,
1168  part and a temporal expression having a date part.
1169  @param f Field
1170  @param v Expression
1171  */
1172 inline bool field_time_cmp_date(const Field *f, const Item *v) {
1173  return f->is_temporal() && !f->is_temporal_with_date() &&
1174  v->is_temporal_with_date();
1175 }
1176 
1177 bool substitute_gc(THD *thd, SELECT_LEX *select_lex, Item *where_cond,
1178  ORDER *group_list, ORDER *order);
1179 
1180 /// RAII class to manage JOIN::deps_of_remaining_lateral_derived_tables
1184  /// All lateral tables not part of this map should be ignored
1186 
1187  public:
1188  /**
1189  Constructor.
1190  @param j the JOIN
1191  @param plan_tables_arg @see
1192  JOIN::deps_of_remaining_lateral_derived_tables
1193  */
1195  : join(j),
1196  saved(join->deps_of_remaining_lateral_derived_tables),
1197  plan_tables(plan_tables_arg) {}
1202  }
1203  void recalculate(uint next_idx) {
1204  if (join->has_lateral)
1205  /*
1206  No cur_tab given, so assume we start from a place in the plan which
1207  may be backward or forward compared to where we were before:
1208  recalculate.
1209  */
1211  next_idx);
1212  }
1213 
1214  void recalculate(JOIN_TAB *cur_tab, uint next_idx) {
1215  /*
1216  We have just added cur_tab to the plan; if it's not lateral, the map
1217  doesn't change, no need to recalculate it.
1218  */
1219  if (join->has_lateral && cur_tab->table_ref->is_derived() &&
1220  cur_tab->table_ref->derived_unit()->m_lateral_deps)
1221  recalculate(next_idx);
1222  }
1223  void init() {
1224  // Normally done once in a run of JOIN::optimize().
1225  if (join->has_lateral) {
1227  // Forget stale value:
1229  }
1230  }
1231 };
1232 
1233 /**
1234  Estimates how many times a subquery will be executed as part of a
1235  query execution. If it is a cacheable subquery, the estimate tells
1236  how many times the subquery will be executed if it is not cached.
1237 
1238  @param[in] subquery the Item that represents the subquery
1239  @param[in,out] trace optimizer trace context
1240 
1241  @return the number of times the subquery is expected to be executed
1242 */
1243 double calculate_subquery_executions(const Item_subselect *subquery,
1245 
1246 /**
1247  Class which presents a view of the current candidate table order for a JOIN.
1248 */
1250  public:
1252 
1253  /// Returns the number of tables in the candidate plan.
1254  size_t size() const { return m_join->tables; }
1255 
1256  /// Returns the table reference at the given position in the candidate plan.
1257  const TABLE_LIST *table_ref(size_t position) const {
1258  return m_join->positions[position].table->table_ref;
1259  }
1260 
1261  private:
1262  const JOIN *const m_join;
1263 };
1264 
1265 #endif /* SQL_OPTIMIZER_INCLUDED */
Definition: item.h:733
JOIN(THD *thd_arg, SELECT_LEX *select)
Definition: sql_optimizer.h:182
State
Definition: sql_optimizer.h:87
bool allow_outer_refs
True if plan search is allowed to use references to expressions outer to this JOIN (for example may s...
Definition: sql_optimizer.h:690
Definition: item.h:3287
#define INNER_TABLE_BIT
Definition: sql_const.h:113
bool make_tmp_tables_info()
Init tmp tables usage info.
Definition: sql_select.cc:4026
SQL_I_List< ORDER > group_list
GROUP BY clause.
Definition: sql_lex.h:1103
Definition: sql_optimizer.h:177
bool extract_func_dependent_tables()
Extract const tables based on functional dependencies.
Definition: sql_optimizer.cc:5175
void set_prefix_tables()
Assign set of available (prefix) tables to all tables in query block.
Definition: sql_optimizer.cc:4667
Original query has this clause.
Definition: opt_explain_format.h:439
Class which presents a view of the current candidate table order for a JOIN.
Definition: sql_optimizer.h:1249
void restore()
Definition: sql_optimizer.h:1199
void set_semijoin_embedding()
Set semi-join embedding join nest pointers.
Definition: sql_optimizer.cc:5471
Next_select_func first_select
Definition: sql_optimizer.h:418
bool is_indexed_agg_distinct(JOIN *join, List< Item_field > *out_args)
Check for the presence of AGGFN(DISTINCT a) queries that may be subject to loose index scan...
Definition: sql_optimizer.cc:7454
bool should_send_current_row()
Returns whether one should send the current row on to the output, or ignore it.
Definition: sql_optimizer.h:883
JOIN(const JOIN &rhs)
not implemented
void adjust_access_methods()
An utility function - apply heuristics and optimize access methods to tables.
Definition: sql_optimizer.cc:2501
uint tables
Before plan has been created, "tables" denote number of input tables in the query block and "primary_...
Definition: sql_optimizer.h:344
bool group_sent
Exec time only: true <=> current group has been sent.
Definition: sql_optimizer.h:698
bool clear_fields(table_map *save_nullinfo)
Clear all result fields.
Definition: sql_executor.cc:7354
bool is_error() const
true if there is an error in the error stack.
Definition: sql_class.h:2813
ulonglong table_map
Definition: my_table_map.h:32
bool init_ref_access()
Initialize ref access for all tables that use it.
Definition: sql_select.cc:1800
void reset()
Reset the state of this join object so that it is ready for a new execution.
Definition: sql_select.cc:1545
Bounds_checked_array< Item * > Ref_item_array
Definition: item.h:80
T pointer_cast(void *p)
Casts from one pointer type, to another, without using reinterpret_cast or C-style cast: foo f; bar *...
Definition: template_utils.h:70
Definition: sql_optimizer.h:482
ORDER_with_src group_list
Definition: sql_optimizer.h:539
ROLLUP rollup
Used with rollup.
Definition: sql_optimizer.h:448
List< Item > & all_fields
List storing all expressions used in query block.
Definition: sql_optimizer.h:506
void create_iterators()
If possible, convert the executor structures to a set of row iterators, storing the result in m_root_...
Definition: sql_executor.cc:1640
bool has_lateral
If JOIN has lateral derived tables (is set at start of planning)
Definition: sql_optimizer.h:500
const JOIN *const m_join
Definition: sql_optimizer.h:1262
Item ** arg_value
Definition: sql_optimizer.h:82
ssize_t count
Definition: memcached.c:386
List< Item > & fields_list
List storing all expressions of select list.
Definition: sql_optimizer.h:509
bool update_equalities_for_sjm()
Update equalities and keyuse references after semi-join materialization strategy is chosen...
Definition: sql_optimizer.cc:4603
Order clause list element.
Definition: table.h:269
~Switch_ref_item_slice()
Definition: sql_optimizer.h:1125
Deps_of_remaining_lateral_derived_tables(JOIN *j, table_map plan_tables_arg)
Constructor.
Definition: sql_optimizer.h:1194
bool is_temporal_with_date() const
Definition: item.h:2377
void cleanup()
Cleanup this JOIN.
Definition: sql_select.cc:3141
Definition: sql_optimizer.h:483
File containing constants that can be used throughout the server.
ha_rows m_select_limit
Definition: sql_optimizer.h:390
List< Item > * get_current_fields()
Returns the clone of fields_list which is appropriate for evaluating expressions at the current stage...
Definition: sql_optimizer.cc:10576
TABLE_LIST * table_ref
points to table reference
Definition: sql_select.h:622
Plan has no tables.
Definition: sql_optimizer.h:844
Prepare_error_tracker(THD *thd_arg)
Definition: sql_optimizer.h:1134
bool prune_table_partitions()
Prune partitions for all tables of a join (query block).
Definition: sql_optimizer.cc:2369
enum_plan_state get_plan_state() const
See enum_plan_state.
Definition: sql_optimizer.h:848
A context for reading through a single table using a chosen access method: index read...
Definition: row_iterator.h:59
bool switch_slice_for_rollup_fields(List< Item > &all_fields, List< Item > &fields)
Switch the ref item slice for rollup structures which need to use fields from the first temp table to...
Definition: sql_select.cc:3825
Ref_item_array * ref_items
ref_items is an array of 5 slices, each containing an array of Item pointers.
Definition: sql_optimizer.h:646
Item_field * get_best_field(Item_field *item_field, COND_EQUAL *cond_equal)
Get the best field substitution for a given field.
Definition: sql_optimizer.cc:3271
table_map found_const_table_map
Const tables which are either:
Definition: sql_optimizer.h:376
ha_rows send_records
Definition: sql_optimizer.h:385
bool m_windows_sort
True if a window requires a certain order of rows, which implies that any order of rows coming out of...
Definition: sql_optimizer.h:550
bool finalize_table_conditions()
Remove redundant predicates and cache constant expressions.
Definition: sql_optimizer.cc:8387
This class represents a query block, aka a query specification, which is a query consisting of a SELE...
Definition: sql_lex.h:922
Definition: field.h:707
enum_plan_state
State of execution plan. Currently used only for EXPLAIN.
Definition: sql_optimizer.h:841
void recalculate_deps_of_remaining_lateral_derived_tables(table_map plan_tables, uint idx)
Updates JOIN::deps_of_remaining_lateral_derived_tables.
Definition: sql_optimizer.cc:2839
JOIN_TAB * table
Definition: sql_select.h:429
bool m_windowing_steps
If we have set up tmp tables for windowing,.
Definition: sql_optimizer.h:553
enum_plan_state plan_state
Final execution plan state. Currently used only for EXPLAIN.
Definition: sql_optimizer.h:913
ha_rows fetch_limit
Used to fetch no more than given amount of rows per one fetch operation of server side cursor...
Definition: sql_optimizer.h:400
Bounds_checked_array< Item_null_result * > Item_null_array
Definition: sql_optimizer.h:71
List< Semijoin_mat_exec > sjm_exec_list
Definition: sql_optimizer.h:694
uint get_ref_item_slice() const
Definition: sql_optimizer.h:779
Represents the (explicit) window of a SQL 2003 section 7.11 <window clause>, or the implicit (inlined...
Definition: window.h:79
No plan is ready yet.
Definition: sql_optimizer.h:842
Definition: opt_explain_format.h:429
List< Cached_item > group_fields
Definition: sql_optimizer.h:434
uint current_ref_item_slice
The slice currently stored in ref_items[0].
Definition: sql_optimizer.h:659
uint saved
Definition: sql_optimizer.h:1118
Item_null_array null_items
Definition: sql_optimizer.h:89
bool select_distinct
At construction time, set if SELECT DISTINCT.
Definition: sql_optimizer.h:455
Item * make_cond_for_table(THD *thd, Item *cond, table_map tables, table_map used_table, bool exclude_expensive_cond)
Extract a condition that can be checked after reading given table.
Definition: sql_optimizer.cc:8670
Sergei Dialog Client Authentication NULL
Definition: dialog.cc:352
bool init_planner_arrays()
Initialize scratch arrays for the join order optimization.
Definition: sql_optimizer.cc:4908
bool simple_order
Definition: sql_optimizer.h:473
uint recursive_iteration_count
Used only if this query block is recursive.
Definition: sql_optimizer.h:666
bool alloc_ref_item_slice(THD *thd_arg, int sliceno)
Allocate a ref_item slice, assume that slice size is in ref_items[0].
Definition: sql_optimizer.h:753
bool grouped
If query contains GROUP BY clause.
Definition: sql_optimizer.h:366
enum_exec_method
The method chosen to execute the predicate, currently used for IN, =ANY and EXISTS predicates...
Definition: item_subselect.h:344
Definition: opt_explain_format.h:426
bool is_optimized() const
Definition: sql_optimizer.h:849
void exec()
Execute select, executor entry point.
Definition: sql_executor.cc:207
std::string join(Container cont, const std::string &delim)
join elements of an container into a string seperated by a delimiter.
Definition: string.h:125
JOIN_TAB ** best_ref
Array of plan operators representing the current (partial) best plan.
Definition: sql_optimizer.h:311
Next_select_func get_end_select_func()
Definition: sql_executor.cc:958
THD *const thd
Thread handler.
Definition: sql_optimizer.h:294
void mark_const_table(JOIN_TAB *table, Key_use *key)
Move const tables first in the position array.
Definition: sql_optimizer.cc:7890
void assert_unchanged()
Definition: sql_optimizer.h:1200
A Key_use represents an equality predicate of the form (table.column = val), where the column is inde...
Definition: sql_select.h:169
Definition: opt_explain_format.h:425
bool get_best_combination()
Set up JOIN_TAB structs according to the picked join order in best_positions.
Definition: sql_optimizer.cc:2619
bool executed
Set by exec(), reset by reset()
Definition: sql_optimizer.h:910
Key_use_array * create_keyuse_for_table(THD *thd, uint keyparts, Item_field **fields, List< Item > outer_exprs)
Create a keyuse array for a table with a primary key.
Definition: sql_optimizer.cc:7853
bool group_optimized_away
If we have the GROUP BY statement in the query, but the group_list was emptied by optimizer...
Definition: sql_optimizer.h:464
MYSQL_LOCK * lock
Definition: sql_optimizer.h:446
bool send_row_on_empty_set() const
Return whether the caller should send a row even if the join produced no rows if: ...
Definition: sql_optimizer.h:820
Definition: item_subselect.h:73
Definition: sql_optimizer.h:87
Definition: sql_optimizer.h:86
bool optimize_fts_query()
Function sets FT hints, initializes FT handlers and checks if FT index can be used as covered...
Definition: sql_optimizer.cc:9999
List< Item > * all_fields
Including hidden fields.
Definition: sql_optimizer.h:92
QEP_TAB ** map2qep_tab
mapping between table indexes and QEB_TABs
Definition: sql_optimizer.h:313
uint primary_tables
Number of primary input tables in query block.
Definition: sql_optimizer.h:345
Zero result cause is set.
Definition: sql_optimizer.h:843
table_map saved
Definition: sql_optimizer.h:1183
bool prepare_result()
Prepare join result.
Definition: sql_select.cc:1618
Common types of the Optimizer, used by optimization and execution.
Definition: table.h:1294
void restore_fields(table_map save_nullinfo)
Restore all result fields for all tables specified in save_nullinfo.
Definition: sql_executor.cc:7382
void set_plan_state(enum_plan_state plan_state_arg)
Sets the plan&#39;s state of the JOIN.
Definition: sql_optimizer.cc:954
bool seen_first_record
Whether we&#39;ve seen at least one row already.
Definition: sql_optimizer.h:365
bool is_derived() const
Return true if this represents a derived table (an unnamed view)
Definition: table.h:2613
bool remove_eq_conds(THD *thd, Item *cond, Item **retcond, Item::cond_result *cond_value)
Removes const and eq items.
Definition: sql_optimizer.cc:9573
int flags
bitmap of Explain_sort_property
Definition: sql_optimizer.h:121
bool clear_corr_derived_tmp_tables()
Empties all correlated materialized derived tables.
Definition: sql_select.cc:1524
bool add_having_as_tmp_table_cond(uint curr_tmp_table)
Add having condition as a filter condition, which is applied when reading from the temp table...
Definition: sql_select.cc:3928
cond_result
Definition: item.h:733
Explain_sort_clause src
origin of order list
Definition: sql_optimizer.h:118
int8 plan_idx
This represents the index of a JOIN_TAB/QEP_TAB in an array.
Definition: sql_opt_exec_shared.h:39
ha_rows row_limit
Definition: sql_optimizer.h:388
The slice with pointers to columns of table(s), ie., the actual Items.
Definition: sql_opt_exec_shared.h:659
#define DBUG_PRINT(keyword, arglist)
Definition: my_dbug.h:110
bool build_equal_items(THD *thd, Item *cond, Item **retcond, COND_EQUAL *inherited, bool do_inherit, List< TABLE_LIST > *join_list, COND_EQUAL **cond_equal_ref)
Build multiple equalities for a WHERE condition and all join conditions that inherit these multiple e...
Definition: sql_optimizer.cc:3948
This file includes constants used by all storage engines.
void make_outerjoin_info()
Fill in outer join related info for the execution plan structure.
Definition: sql_optimizer.cc:7919
#define DBUG_ASSERT(A)
Definition: my_dbug.h:128
void init()
Definition: sql_optimizer.h:1223
bool optimized
flag to avoid double optimization in EXPLAIN
Definition: sql_optimizer.h:909
EXPLAIN FORMAT=<format> <command>.
void optimize_distinct()
Optimize distinct when used on a subset of the tables.
Definition: sql_executor.cc:544
bool field_time_cmp_date(const Field *f, const Item *v)
Returns true if arguments are a temporal Field having no date, part and a temporal expression having ...
Definition: sql_optimizer.h:1172
bool estimate_rowcount()
Estimate the number of matched rows for each joined table.
Definition: sql_optimizer.cc:5349
bool simple_group
Definition: sql_optimizer.h:473
void test_skip_sort()
Test if an index could be used to replace filesort for ORDER BY/GROUP BY.
Definition: sql_optimizer.cc:1306
Element_type * array() const
Definition: sql_array.h:105
void unplug_join_tabs()
Definition: sql_select.cc:4665
bool substitute_gc(THD *thd, SELECT_LEX *select_lex, Item *where_cond, ORDER *group_list, ORDER *order)
Substitute all expressions in the WHERE condition and ORDER/GROUP lists that match generated columns ...
Definition: sql_optimizer.cc:873
bool select_count
Definition: sql_optimizer.h:923
bool is_temporal_with_date() const
Definition: field.h:1264
ha_rows examined_rows
Definition: sql_optimizer.h:387
ORDER * operator->() const
Definition: sql_optimizer.h:163
void recalculate(JOIN_TAB *cur_tab, uint next_idx)
Definition: sql_optimizer.h:1214
void recalculate(uint next_idx)
Definition: sql_optimizer.h:1203
ORDER_with_src & operator=(null *)
Type-safe NULL assignment.
Definition: sql_optimizer.h:136
COND_EQUAL * cond_equal
Definition: sql_optimizer.h:602
bool attach_join_conditions(plan_idx last_tab)
Attach outer join conditions to generated table conditions in an optimal way.
Definition: sql_optimizer.cc:8065
Class Item_sum is the base class used for special expressions that SQL calls &#39;set functions&#39;...
Definition: item_sum.h:385
table_map all_table_map
Set of tables contained in query.
Definition: sql_optimizer.h:368
The slice which is used during evaluation of expressions; Item_ref::ref points there.
Definition: sql_opt_exec_shared.h:597
void set_optimized()
Definition: sql_optimizer.h:850
bool rollup_make_fields(List< Item > &all_fields, List< Item > &fields, Item_sum ***func)
Fill up rollup structures with pointers to fields to use.
Definition: sql_select.cc:3683
void optimize_keyuse()
Update some values in keyuse for faster choose_table_order() loop.
Definition: sql_optimizer.cc:9959
JOIN * join
Definition: sql_optimizer.h:1182
bool unlikely(bool expr)
Definition: my_compiler.h:65
Definition: opt_explain_format.h:446
unique_ptr_destroy_only< RowIterator > m_root_iterator
An iterator you can read from to get all records for this query.
Definition: sql_optimizer.h:1109
Definition: sql_optimizer.h:481
Classes for query execution.
ORDER_with_src(null *)
Type-safe constructor from NULL.
Definition: sql_optimizer.h:146
TABLE_LIST * tables_list
Pointer set to select_lex->get_table_list() at the start of optimization.
Definition: sql_optimizer.h:601
table_map m_lateral_deps
If &#39;this&#39; is body of lateral derived table: map of tables in the same FROM clause as this derived tab...
Definition: sql_lex.h:756
Header for compiler-dependent features.
bool decide_subquery_strategy()
Decides between EXISTS and materialization; performs last steps to set up the chosen strategy...
Definition: sql_optimizer.cc:10203
ORDER_with_src(ORDER *order_arg, Explain_sort_clause src_arg)
Definition: sql_optimizer.h:126
List< Cached_item > group_fields_cache
Definition: sql_optimizer.h:434
List< Item > * fields_list
SELECT list.
Definition: sql_optimizer.h:91
JOIN_TAB ** map2table
mapping between table indexes and JOIN_TABs
Definition: sql_optimizer.h:312
bool fts_index_access(JOIN_TAB *tab)
Check if FTS index only access is possible.
Definition: sql_optimizer.cc:10055
RowIterator * root_iterator() const
Definition: sql_optimizer.h:903
void update_depend_map()
Update the dependency map for the tables.
Definition: sql_optimizer.cc:4533
SELECT_LEX_UNIT * derived_unit() const
Return the query expression of a derived table or view.
Definition: table.h:2770
const Cost_model_server * cost_model() const
Retrieve the cost model object to be used for this join.
Definition: sql_optimizer.h:860
Definition: item.h:666
double calculate_subquery_executions(const Item_subselect *subquery, Opt_trace_context *trace)
Estimates how many times a subquery will be executed as part of a query execution.
Definition: sql_optimizer.cc:10375
unsigned int uint
Definition: uca-dump.cc:29
#define true
Definition: config_static.h:44
bool make_sum_func_list(List< Item > &all_fields, List< Item > &send_fields, bool before_group_by, bool recompute=false)
Initialize &#39;sum_funcs&#39; array with all Item_sum objects.
Definition: sql_select.cc:3571
table_map const_table_map
Set of tables found to be const.
Definition: sql_optimizer.h:369
const char * zero_result_cause
<> NULL if optimization has determined that execution will produce an empty result before aggregation...
Definition: sql_optimizer.h:676
bool uses_index_fields_only(Item *item, TABLE *tbl, uint keyno, bool other_tbls_ok)
Check if given expression only uses fields covered by index keyno in the table tbl.
Definition: sql_optimizer.cc:5938
ORDER * order
ORDER expression that we are wrapping with this class.
Definition: sql_optimizer.h:117
bool skip_sort_order
Is set if we have a GROUP BY and we have ORDER BY on a constant or when sorting isn&#39;t required...
Definition: sql_optimizer.h:490
bool make_join_plan()
Calculate best possible join order and initialize the join structure.
Definition: sql_optimizer.cc:4768
uint const_tables
Number of primary tables deemed constant.
Definition: sql_optimizer.h:346
This class represents a query expression (one query block or several query blocks combined with UNION...
Definition: sql_lex.h:614
SELECT_LEX_UNIT *const unit
Query expression referring this query block.
Definition: sql_optimizer.h:292
void trace(const std::string &note)
Definition: trace.cc:57
Definition: sql_optimizer.h:87
void update_sargable_from_const(SARGABLE_PARAM *sargables)
Update info on indexes that can be used for search lookups as reading const tables may has added new ...
Definition: sql_optimizer.cc:5326
ORDER * next
Definition: table.h:270
bool plan_is_single_table()
True if plan contains one non-const primary table (ie not including tables taking part in semi-join m...
Definition: sql_optimizer.h:718
bool is_null() const
Definition: sql_array.h:97
Key_use_array keyuse_array
Used and updated by JOIN::make_join_plan() and optimize_keyuse()
Definition: sql_optimizer.h:503
uint sum_func_count
Number of fields in the query that have aggregate functions.
Definition: temp_table_param.h:118
Candidate_table_order(const JOIN *join)
Definition: sql_optimizer.h:1251
bool implicit_grouping
True if aggregated but no GROUP BY.
Definition: sql_optimizer.h:449
bool optimize_rollup()
Optimize rollup specification.
Definition: sql_optimizer.cc:10489
enum_nested_loop_state(* Next_select_func)(JOIN *, class QEP_TAB *, bool)
Definition: sql_executor.h:88
size_t element_size() const
Definition: sql_array.h:94
bool with_json_agg
This will force tmp table to NOT use index + update for group operation as it&#39;ll cause [de]serializat...
Definition: sql_optimizer.h:709
double sort_cost
Expected cost of filesort.
Definition: sql_optimizer.h:430
Plan is ready.
Definition: sql_optimizer.h:845
double best_read
The cost of best complete join plan found so far during optimization, after optimization phase - cost...
Definition: sql_optimizer.h:424
bool optimize_cond(THD *thd, Item **conds, COND_EQUAL **cond_equal, List< TABLE_LIST > *join_list, Item::cond_result *cond_value)
Optimize conditions by.
Definition: sql_optimizer.cc:9473
Definition: sql_executor.h:402
static const char * key
Definition: suite_stubs.c:14
ha_rows offset_limit_cnt
Definition: sql_lex.h:711
std::unique_ptr< T, Destroy_only< T > > unique_ptr_destroy_only
std::unique_ptr, but only destroying.
Definition: my_alloc.h:400
bool plan_is_const() const
True if plan is const, ie it will return zero or one rows.
Definition: sql_optimizer.h:712
static MEM_ROOT mem_root
Definition: client_plugin.cc:107
table_map plan_tables
All lateral tables not part of this map should be ignored.
Definition: sql_optimizer.h:1185
LEX * lex
Definition: sql_class.h:836
void copy_ref_item_slice(uint dst_slice, uint src_slice)
Overwrites one slice of ref_items with the contents of another slice.
Definition: sql_optimizer.h:734
bool propagate_dependencies()
Propagate dependencies between tables due to outer join relations.
Definition: sql_optimizer.cc:5030
bool rollup_send_data(uint idx)
Send all rollup levels higher than the current one to the client.
Definition: sql_executor.cc:449
unique_ptr_destroy_only< RowIterator > release_root_iterator()
Definition: sql_optimizer.h:904
uint num_values
Definition: sql_optimizer.h:83
Item * where_cond
JOIN::having_cond is initially equal to select_lex->having_cond, but may later be changed by optimiza...
Definition: sql_optimizer.h:584
bool setup_semijoin_materialized_table(JOIN_TAB *tab, uint tableno, const POSITION *inner_pos, POSITION *sjm_pos)
Setup the materialized table for a semi-join nest.
Definition: sql_select.cc:2480
Item::cond_result having_value
Definition: sql_lex.h:1088
Field * field
Definition: sql_optimizer.h:81
SELECT_LEX *const select_lex
Query block that is optimized and executed using this JOIN.
Definition: sql_optimizer.h:290
A per-session context which is always available at any point of execution, because in practice it&#39;s ...
Definition: opt_trace_context.h:86
A position of table within a join order.
Definition: sql_select.h:344
void set(Explain_sort_clause clause, Explain_sort_property property)
Set property bit flag for the clause.
Definition: opt_explain_format.h:458
JOIN & operator=(const JOIN &rhs)
not implemented
Query optimization plan node.
Definition: sql_select.h:585
int optimize()
Optimizes one query block into a query execution plan (QEP.)
Definition: sql_optimizer.cc:195
bool add_sorting_to_table(uint idx, ORDER_with_src *order, bool force_stable_sort=false)
Add Filesort object to the given table to sort if with filesort.
Definition: sql_select.cc:4705
void cleanup_item_list(List< Item > &items) const
Definition: sql_select.cc:1706
void init_key_dependencies()
Initialize key dependencies for join tables.
Definition: sql_optimizer.h:967
ORDER_with_src order
ORDER BY and GROUP BY lists, to transform with prepare,optimize and exec.
Definition: sql_optimizer.h:539
Wrapper for ORDER* pointer to trace origins of ORDER list.
Definition: sql_optimizer.h:102
int push_to_engines()
Handle offloading of query parts to the underlying engines, when such is supported by their implement...
Definition: sql_optimizer.cc:776
Definition: opt_explain_format.h:427
uint elements
Definition: sql_list.h:133
void copy_ref_item_slice(Ref_item_array dst_arr, Ref_item_array src_arr)
Definition: sql_optimizer.h:737
int get_flags() const
Definition: sql_optimizer.h:171
POSITION * positions
Definition: sql_optimizer.h:412
List< Item > * tmp_all_fields
This is similar to tmp_fields_list, but it also contains necessary extras: expressions added for ORDE...
Definition: sql_optimizer.h:516
Definition: item_cmpfunc.h:2162
Item_sum *** sum_funcs_end
Definition: sql_optimizer.h:435
enum_nested_loop_state sub_select(JOIN *join, QEP_TAB *const qep_tab, bool end_of_records)
Retrieve records ends with a given beginning from the result of a join.
Definition: sql_executor.cc:2313
bool do_send_rows
If true, send produced rows using query_result.
Definition: sql_optimizer.h:367
bool extract_const_tables()
Extract const tables based on row counts.
Definition: sql_optimizer.cc:5081
size_t size() const
Definition: sql_array.h:95
bool alloc_qep(uint n)
Definition: sql_optimizer.cc:984
void set_executed()
Definition: sql_optimizer.h:852
uint tmp_tables
Number of temporary tables used by query.
Definition: sql_optimizer.h:347
void refine_best_rowcount()
Refine the best_rowcount estimation based on what happens after tables have been joined: LIMIT and ty...
Definition: sql_optimizer.cc:10551
int error
set in optimize(), exec(), prepare_result()
Definition: sql_optimizer.h:534
Definition: sql_optimizer.h:80
Ref_item_array * ref_item_arrays
Definition: sql_optimizer.h:90
#define HA_POS_ERROR
Definition: my_base.h:1068
bool create_intermediate_table(QEP_TAB *tab, List< Item > *tmp_table_fields, ORDER_with_src &tmp_table_group, bool save_sum_fields)
Create a temporary table to be used for processing DISTINCT/ORDER BY/GROUP BY.
Definition: sql_executor.cc:322
uint build_bitmap_for_nested_joins(List< TABLE_LIST > *join_list, uint first_unused)
Assign each nested join structure a bit in nested_join_map.
Definition: sql_optimizer.cc:4489
RAII class to manage JOIN::deps_of_remaining_lateral_derived_tables.
Definition: sql_optimizer.h:1181
T * first
The first element in the list.
Definition: sql_list.h:49
bool rollup_write_data(uint idx, QEP_TAB *qep_tab)
Write all rollup levels higher than the current one to a temp table.
Definition: sql_executor.cc:514
bool rollup_process_const_fields()
Wrap all constant Items in GROUP BY list.
Definition: sql_select.cc:3643
List< Item > * fields
Definition: sql_optimizer.h:433
int replace_index_subquery()
Check whether this is a subquery that can be evaluated by index look-ups.
Definition: sql_optimizer.cc:1063
uint send_group_parts
Definition: sql_optimizer.h:348
ORDER_with_src()
Definition: sql_optimizer.h:124
bool alloc_func_list()
Make an array of pointers to sum_functions to speed up sum_func calculation.
Definition: sql_select.cc:3521
Item * substitute_for_best_equal_field(THD *thd, Item *cond, COND_EQUAL *cond_equal, JOIN_TAB **table_join_idx)
Substitute every field reference in a condition by the best equal field and eliminate all multiple eq...
Definition: sql_optimizer.cc:4248
void join_free()
Release memory and, if possible, the open tables held by this execution plan (and nested plans)...
Definition: sql_select.cc:3079
bool is_executed() const
Definition: sql_optimizer.h:851
const Cost_model_server * cost_model() const
Retrieve the optimizer cost model for this connection.
Definition: sql_class.h:3819
table_map deps_of_remaining_lateral_derived_tables
Used in some loops which scan the JOIN&#39;s tables: it is the bitmap of all tables which are dependencie...
Definition: sql_optimizer.h:382
void * alloc(size_t size)
Definition: sql_class.h:299
bool destroy()
Clean up and destroy join object.
Definition: sql_select.cc:1652
enum JOIN::@103 m_ordered_index_usage
bool child_subquery_can_materialize
True if, at this stage of processing, subquery materialization is allowed for children subqueries of ...
Definition: sql_optimizer.h:684
QEP_TAB * ref_slice_immediately_before_group_by
If slice REF_SLICE_ORDERED_GROUP_BY has been created, this is the QEP_TAB which is right before calcu...
Definition: sql_optimizer.h:652
bool compare_costs_of_subquery_strategies(Item_exists_subselect::enum_exec_method *method)
Tells what is the cheapest between IN->EXISTS and subquery materialization, in terms of cost...
Definition: sql_optimizer.cc:10264
List< Window > m_windows
Any window definitions.
Definition: sql_optimizer.h:544
JOIN * join
Definition: sql_optimizer.h:1117
bool is_temporal() const
Definition: field.h:1260
Definition: opt_explain_format.h:438
ha_rows end_write_records
Definition: temp_table_param.h:91
bool is_distinct() const
Definition: sql_lex.h:1365
bool calc_found_rows
If true, calculate found rows for this query block.
Definition: sql_optimizer.h:700
SQL_I_List< ORDER > order_list
ORDER BY clause.
Definition: sql_lex.h:1173
RAII class to ease the call of LEX::mark_broken() if error.
Definition: sql_optimizer.h:1132
Item * having_for_explain
Saved optimized HAVING for EXPLAIN.
Definition: sql_optimizer.h:595
~Deps_of_remaining_lateral_derived_tables()
Definition: sql_optimizer.h:1198
ORDER * remove_const(ORDER *first_order, Item *cond, bool change_list, bool *simple_order, bool group_by)
Remove all constants and check if ORDER only contains simple expressions.
Definition: sql_optimizer.cc:9320
bool need_tmp_before_win
If true we need a temporary table on the result set before any windowing steps, e.g.
Definition: sql_optimizer.h:497
Definition: opt_explain_format.h:424
void mark_broken(bool broken=true)
Certain permanent transformations (like in2exists), if they fail, may leave the LEX in an inconsisten...
Definition: sql_lex.h:3924
plan_idx return_tab
Definition: sql_optimizer.h:610
size_t size() const
Returns the number of tables in the candidate plan.
Definition: sql_optimizer.h:1254
POSITION * best_positions
This is the result of join optimization.
Definition: sql_optimizer.h:407
Explain_sort_clause
Enumeration of ORDER BY, GROUP BY and DISTINCT clauses for array indexing.
Definition: opt_explain_format.h:423
Switch_ref_item_slice(JOIN *join_arg, uint new_v)
Definition: sql_optimizer.h:1121
State state
Definition: sql_optimizer.h:88
List< Item > * tmp_fields_list
Array of pointers to lists of expressions.
Definition: sql_optimizer.h:532
JOIN_TAB * join_tab
Optimal query execution plan.
Definition: sql_optimizer.h:301
Definition: table.h:2439
List< TABLE > sj_tmp_tables
Definition: sql_optimizer.h:693
ha_rows found_records
Definition: sql_optimizer.h:386
RAII class to ease the temporary switching to a different slice of the ref item array.
Definition: sql_optimizer.h:1116
void set_ref_item_slice(uint sliceno)
Overwrite the base slice of ref_items with the slice supplied as argument.
Definition: sql_optimizer.h:768
void clean()
Definition: sql_optimizer.h:165
Definition: lock.h:38
Temp_table_param tmp_table_param
Describes a temporary table.
Definition: sql_optimizer.h:445
QEP_TAB * qep_tab
Array of QEP_TABs.
Definition: sql_optimizer.h:303
bool generate_derived_keys()
Add keys to derived tables&#39;/views&#39; result tables in a list.
Definition: sql_optimizer.cc:8464
Explain_format_flags explain_flags
Buffer to gather GROUP BY, ORDER BY and DISTINCT QEP details for EXPLAIN.
Definition: sql_optimizer.h:558
Item_sum ** sum_funcs
Definition: sql_optimizer.h:435
double windowing_cost
Expected cost of windowing;.
Definition: sql_optimizer.h:432
void set_semijoin_info()
Set the first_sj_inner_tab and last_sj_inner_tab fields for all tables inside the semijoin nests of t...
Definition: sql_select.cc:1823
Item * having_cond
Optimized HAVING clause item tree (valid for one single execution).
Definition: sql_optimizer.h:594
#define false
Definition: config_static.h:43
~Prepare_error_tracker()
Definition: sql_optimizer.h:1135
Mem_root_array< Key_use > Key_use_array
Definition: sql_optimizer.h:76
bool optimize_distinct_group_order()
Optimize DISTINCT, GROUP BY, ORDER BY clauses.
Definition: sql_optimizer.cc:1122
Definition: sql_optimizer.h:87
API for getting cost estimates for server operations that are not directly related to a table object...
Definition: opt_costmodel.h:41
ha_rows best_rowcount
The estimated row count of the plan with best read time (see above).
Definition: sql_optimizer.h:428
my_off_t ha_rows
Definition: my_base.h:1066
bool alloc_indirection_slices()
Definition: sql_optimizer.cc:139
const TABLE_LIST * table_ref(size_t position) const
Returns the table reference at the given position in the candidate plan.
Definition: sql_optimizer.h:1257
Object containing parameters used when creating and using temporary tables.
Definition: temp_table_param.h:70
Definition: items.h:34
bool streaming_aggregation
Indicates that the data will be aggregated (typically GROUP BY), and that it is already processed in ...
Definition: sql_optimizer.h:364
TABLE * sort_by_table
Definition: sql_optimizer.h:319
void finalize_derived_keys()
For each materialized derived table/view, informs every TABLE of the key it will (not) use...
Definition: sql_optimizer.cc:8485
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:776
THD *const thd
Definition: sql_optimizer.h:1140
Private empty class to implement type-safe NULL assignment.
Definition: sql_optimizer.h:114