MySQL  8.0.27
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, 2021, Oracle and/or its affiliates.
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 #include <sys/types.h>
32 
33 #include <cstring>
34 #include <memory>
35 #include <utility>
36 
37 #include "field_types.h"
38 #include "my_alloc.h"
39 #include "my_base.h"
40 #include "my_dbug.h"
41 #include "my_table_map.h"
42 #include "sql/field.h"
43 #include "sql/item.h"
44 #include "sql/mem_root_array.h"
45 #include "sql/opt_explain_format.h" // Explain_sort_clause
46 #include "sql/row_iterator.h"
47 #include "sql/sql_executor.h"
48 #include "sql/sql_lex.h"
49 #include "sql/sql_list.h"
51 #include "sql/sql_select.h" // Key_use
52 #include "sql/table.h"
53 #include "sql/temp_table_param.h"
54 
55 enum class Subquery_strategy : int;
56 class COND_EQUAL;
57 class Item_subselect;
58 class Item_sum;
59 class Opt_trace_context;
60 class THD;
61 class Window;
62 struct AccessPath;
63 struct MYSQL_LOCK;
64 
65 class Item_equal;
66 template <class T>
67 class mem_root_deque;
68 
69 // Key_use has a trivial destructor, no need to run it from Mem_root_array.
70 typedef Mem_root_array<Key_use> Key_use_array;
71 
72 class Cost_model_server;
73 
74 /*
75  This structure is used to collect info on potentially sargable
76  predicates in order to check whether they become sargable after
77  reading const tables.
78  We form a bitmap of indexes that can be used for sargable predicates.
79  Only such indexes are involved in range analysis.
80 */
81 
83  Field *field; /* field against which to check sargability */
84  Item **arg_value; /* values of potential keys for lookups */
85  uint num_values; /* number of values in the above array */
86 };
87 
88 /**
89  Wrapper for ORDER* pointer to trace origins of ORDER list
90 
91  As far as ORDER is just a head object of ORDER expression
92  chain, we need some wrapper object to associate flags with
93  the whole ORDER list.
94 */
96  public:
97  ORDER *order; ///< ORDER expression that we are wrapping with this class
98  Explain_sort_clause src; ///< origin of order list
99 
100  private:
101  int flags; ///< bitmap of Explain_sort_property
102 
103  public:
105 
107  : order(order_arg),
108  src(src_arg),
109  flags(order_arg ? ESP_EXISTS : ESP_none) {}
110 
111  bool empty() const { return order == nullptr; }
112 
113  void clean() {
114  order = nullptr;
115  src = ESC_none;
116  flags = ESP_none;
117  }
118 
119  int get_flags() const {
120  assert(order);
121  return flags;
122  }
123 };
124 
125 class JOIN {
126  public:
127  JOIN(THD *thd_arg, Query_block *select);
128  JOIN(const JOIN &rhs) = delete;
129  JOIN &operator=(const JOIN &rhs) = delete;
130 
131  /// Query expression referring this query block
134  }
135 
136  /// Query block that is optimized and executed using this JOIN
138  /// Thread handler
139  THD *const thd;
140 
141  /**
142  Optimal query execution plan. Initialized with a tentative plan in
143  JOIN::make_join_plan() and later replaced with the optimal plan in
144  get_best_combination().
145  */
146  JOIN_TAB *join_tab{nullptr};
147  /// Array of QEP_TABs
148  QEP_TAB *qep_tab{nullptr};
149 
150  /**
151  Array of plan operators representing the current (partial) best
152  plan. The array is allocated in JOIN::make_join_plan() and is valid only
153  inside this function. Initially (*best_ref[i]) == join_tab[i].
154  The optimizer reorders best_ref.
155  */
156  JOIN_TAB **best_ref{nullptr};
157  /// mapping between table indexes and JOIN_TABs
158  JOIN_TAB **map2table{nullptr};
159  /*
160  The table which has an index that allows to produce the requried ordering.
161  A special value of 0x1 means that the ordering will be produced by
162  passing 1st non-const table to filesort(). NULL means no such table exists.
163  */
164  TABLE *sort_by_table{nullptr};
165 
166  // Temporary tables that need to be cleaned up after the query.
167  // Only used for the hypergraph optimizer; the non-hypergraph optimizer
168  // uses QEP_TABs to hold the list of tables (including temporary tables).
171 
172  // Allocated on the MEM_ROOT, but can hold some objects
173  // that allocate on the heap and thus need destruction.
175  };
178 
179  // Similarly, filesorts that need to be cleaned up after the query.
180  // Only used for the hypergraph optimizer, for the same reason as above.
182 
183  /**
184  Before plan has been created, "tables" denote number of input tables in the
185  query block and "primary_tables" is equal to "tables".
186  After plan has been created (after JOIN::get_best_combination()),
187  the JOIN_TAB objects are enumerated as follows:
188  - "tables" gives the total number of allocated JOIN_TAB objects
189  - "primary_tables" gives the number of input tables, including
190  materialized temporary tables from semi-join operation.
191  - "const_tables" are those tables among primary_tables that are detected
192  to be constant.
193  - "tmp_tables" is 0, 1 or 2 (more if windows) and counts the maximum
194  possible number of intermediate tables in post-processing (ie sorting and
195  duplicate removal).
196  Later, tmp_tables will be adjusted to the correct number of
197  intermediate tables, @see JOIN::make_tmp_tables_info.
198  - The remaining tables (ie. tables - primary_tables - tmp_tables) are
199  input tables to materialized semi-join operations.
200  The tables are ordered as follows in the join_tab array:
201  1. const primary table
202  2. non-const primary tables
203  3. intermediate sort/group tables
204  4. possible holes in array
205  5. semi-joined tables used with materialization strategy
206  */
207  uint tables{0}; ///< Total number of tables in query block
208  uint primary_tables{0}; ///< Number of primary input tables in query block
209  uint const_tables{0}; ///< Number of primary tables deemed constant
210  uint tmp_tables{0}; ///< Number of temporary tables used by query
212  /**
213  Indicates that the data will be aggregated (typically GROUP BY),
214  _and_ that it is already processed in an order that is compatible with
215  the grouping in use (e.g. because we are scanning along an index,
216  or because an earlier step sorted the data in a group-compatible order).
217 
218  Note that this flag changes value at multiple points during optimization;
219  if it's set when a temporary table is created, this means we aggregate
220  into said temporary table (end_write_group is chosen instead of end_write),
221  but if it's set later, it means that we can aggregate as we go,
222  just before sending the data to the client (end_send_group is chosen
223  instead of end_send).
224 
225  @see make_group_fields, alloc_group_fields, JOIN::exec
226  */
228  /// If query contains GROUP BY clause
229  bool grouped;
230  /// If true, send produced rows using query_result
231  bool do_send_rows{true};
232  /// Set of tables contained in query
234  table_map const_table_map; ///< Set of tables found to be const
235  /**
236  Const tables which are either:
237  - not empty
238  - empty but inner to a LEFT JOIN, thus "considered" not empty for the
239  rest of execution (a NULL-complemented row will be used).
240  */
242  /**
243  This is the bitmap of all tables which are dependencies of
244  lateral derived tables which are not (yet) part of the partial
245  plan. (The value is a logical 'or' of zero or more
246  TABLE_LIST.map() values.)
247 
248  When we are building the join order, there is a partial plan (an
249  ordered sequence of JOIN_TABs), and an unordered set of JOIN_TABs
250  not yet added to the plan. Due to backtracking, the partial plan
251  may both grow and shrink. When we add a new table to the plan, we
252  may wish to set up join buffering, so that rows from the preceding
253  table are buffered. If any of the remaining tables are derived
254  tables that depends on any of the predecessors of the table we
255  are adding (i.e. a lateral dependency), join buffering would be
256  inefficient. (@see setup_join_buffering() for a detailed
257  explanation of why this is so.)
258 
259  For this reason we need to maintain this table_map of lateral
260  dependencies of tables not yet in the plan. Whenever we add a new
261  table to the plan, we update the map by calling
262  Optimize_table_order::recalculate_lateral_deps_incrementally().
263  And when we remove a table, we restore the previous map value
264  using a Tabel_map_restorer object.
265 
266  As an example, assume that we join four tables, t1, t2, t3 and
267  d1, where d1 is a derived table that depends on t1:
268 
269  SELECT * FROM t1 JOIN t2 ON t1.a=t2.b JOIN t3 ON t2.c=t3.d
270  JOIN LATERAL (SELECT DISTINCT e AS x FROM t4 WHERE t4.f=t1.c)
271  AS d1 ON t3.e=d1.x;
272 
273  Now, if our partial plan is t1->t2, the map (of lateral
274  dependencies of the remaining tables) will contain t1.
275  This tells us that we should not use join buffering when joining t1
276  with t2. But if the partial plan is t1->d2->t2, the map will be
277  empty. We may thus use join buffering when joining d2 with t2.
278  */
280 
281  /* Number of records produced after join + group operation */
286  // m_select_limit is used to decide if we are likely to scan the whole table.
288  /**
289  Used to fetch no more than given amount of rows per one
290  fetch operation of server side cursor.
291  The value is checked in end_send and end_send_group in fashion, similar
292  to offset_limit_cnt:
293  - fetch_limit= HA_POS_ERROR if there is no cursor.
294  - when we open a cursor, we set fetch_limit to 0,
295  - on each fetch iteration we add num_rows to fetch to fetch_limit
296  */
298 
299  /**
300  This is the result of join optimization.
301 
302  @note This is a scratch array, not used after get_best_combination().
303  */
305 
306  /******* Join optimization state members start *******/
307 
308  /* Current join optimization state */
309  POSITION *positions{nullptr};
310 
311  /* We also maintain a stack of join optimization states in * join->positions[]
312  */
313  /******* Join optimization state members end *******/
314 
315  /// A hook that secondary storage engines can use to override the executor
316  /// completely.
317  using Override_executor_func = bool (*)(JOIN *, Query_result *);
319 
320  /**
321  The cost of best complete join plan found so far during optimization,
322  after optimization phase - cost of picked join order (not taking into
323  account the changes made by test_if_skip_sort_order()).
324  */
325  double best_read{0.0};
326  /**
327  The estimated row count of the plan with best read time (see above).
328  */
330  /// Expected cost of filesort.
331  double sort_cost{0.0};
332  /// Expected cost of windowing;
333  double windowing_cost{0.0};
337 
338  // For destroying fields otherwise owned by RemoveDuplicatesIterator.
340 
341  Item_sum **sum_funcs{nullptr};
342  /**
343  Describes a temporary table.
344  Each tmp table has its own tmp_table_param.
345  The one here is transiently used as a model by create_intermediate_table(),
346  to build the tmp table's own tmp_table_param.
347  */
350 
351  enum class RollupState { NONE, INITED, READY };
353  bool implicit_grouping; ///< True if aggregated but no GROUP BY
354 
355  /**
356  At construction time, set if SELECT DISTINCT. May be reset to false
357  later, when we set up a temporary table operation that deduplicates for us.
358  */
360 
361  /**
362  If we have the GROUP BY statement in the query,
363  but the group_list was emptied by optimizer, this
364  flag is true.
365  It happens when fields in the GROUP BY are from
366  constant table
367  */
368  bool group_optimized_away{false};
369 
370  /*
371  simple_xxxxx is set if ORDER/GROUP BY doesn't include any references
372  to other tables than the first non-constant table in the JOIN.
373  It's also set if ORDER/GROUP BY is empty.
374  Used for deciding for or against using a temporary table to compute
375  GROUP/ORDER BY.
376  */
377  bool simple_order{false};
378  bool simple_group{false};
379 
380  /*
381  m_ordered_index_usage is set if an ordered index access
382  should be used instead of a filesort when computing
383  ORDER/GROUP BY.
384  */
385  enum {
386  ORDERED_INDEX_VOID, // No ordered index avail.
387  ORDERED_INDEX_GROUP_BY, // Use index for GROUP BY
388  ORDERED_INDEX_ORDER_BY // Use index for ORDER BY
389  } m_ordered_index_usage{ORDERED_INDEX_VOID};
390 
391  /**
392  Is set if we have a GROUP BY and we have ORDER BY on a constant or when
393  sorting isn't required.
394  */
395  bool skip_sort_order{false};
396 
397  /**
398  If true we need a temporary table on the result set before any
399  windowing steps, e.g. for DISTINCT or we have a query ORDER BY.
400  See details in JOIN::optimize
401  */
402  bool need_tmp_before_win{false};
403 
404  /// If JOIN has lateral derived tables (is set at start of planning)
405  bool has_lateral{false};
406 
407  /// Used and updated by JOIN::make_join_plan() and optimize_keyuse()
409 
410  /**
411  Array of pointers to lists of expressions.
412  Each list represents the SELECT list at a certain stage of execution,
413  and also contains necessary extras: expressions added for ORDER BY,
414  GROUP BY, window clauses, underlying items of split items.
415  This array is only used when the query makes use of tmp tables: after
416  writing to tmp table (e.g. for GROUP BY), if this write also does a
417  function's calculation (e.g. of SUM), after the write the function's value
418  is in a column of the tmp table. If a SELECT list expression is the SUM,
419  and we now want to read that materialized SUM and send it forward, a new
420  expression (Item_field type instead of Item_sum), is needed. The new
421  expressions are listed in JOIN::tmp_fields_list[x]; 'x' is a number
422  (REF_SLICE_).
423  @see JOIN::make_tmp_tables_info()
424  */
426 
427  int error{0}; ///< set in optimize(), exec(), prepare_result()
428 
429  /**
430  Incremented each time clear_hash_tables() is run, signaling to
431  HashJoinIterators that they cannot keep their hash tables anymore
432  (since outer references may have changed).
433  */
435 
436  /**
437  ORDER BY and GROUP BY lists, to transform with prepare,optimize and exec
438  */
440 
441  // Used so that AggregateIterator knows which items to signal when the rollup
442  // level changes. Obviously only used in the presence of rollup.
447 
448  /**
449  Any window definitions
450  */
452 
453  /**
454  True if a window requires a certain order of rows, which implies that any
455  order of rows coming out of the pre-window join will be disturbed.
456  */
457  bool m_windows_sort{false};
458 
459  /// If we have set up tmp tables for windowing, @see make_tmp_tables_info
460  bool m_windowing_steps{false};
461 
462  /**
463  Buffer to gather GROUP BY, ORDER BY and DISTINCT QEP details for EXPLAIN
464  */
466 
467  /**
468  JOIN::having_cond is initially equal to query_block->having_cond, but may
469  later be changed by optimizations performed by JOIN.
470  The relationship between the JOIN::having_cond condition and the
471  associated variable query_block->having_value is so that
472  having_value can be:
473  - COND_UNDEF if a having clause was not specified in the query or
474  if it has not been optimized yet
475  - COND_TRUE if the having clause is always true, in which case
476  JOIN::having_cond is set to NULL.
477  - COND_FALSE if the having clause is impossible, in which case
478  JOIN::having_cond is set to NULL
479  - COND_OK otherwise, meaning that the having clause needs to be
480  further evaluated
481  All of the above also applies to the where_cond/query_block->cond_value
482  pair.
483  */
484  /**
485  Optimized WHERE clause item tree (valid for one single execution).
486  Used in JOIN execution if no tables. Otherwise, attached in pieces to
487  JOIN_TABs and then not used in JOIN execution.
488  Printed by EXPLAIN EXTENDED.
489  Initialized by Query_block::get_optimizable_conditions().
490  */
492  /**
493  Optimized HAVING clause item tree (valid for one single execution).
494  Used in JOIN execution, as last "row filtering" step. With one exception:
495  may be pushed to the JOIN_TABs of temporary tables used in DISTINCT /
496  GROUP BY (see JOIN::make_tmp_tables_info()); in that case having_cond is
497  set to NULL, but is first saved to having_for_explain so that EXPLAIN
498  EXTENDED can still print it.
499  Initialized by Query_block::get_optimizable_conditions().
500  */
502  Item *having_for_explain; ///< Saved optimized HAVING for EXPLAIN
503  /**
504  Pointer set to query_block->get_table_list() at the start of
505  optimization. May be changed (to NULL) only if optimize_aggregated_query()
506  optimizes tables away.
507  */
510  /*
511  Join tab to return to. Points to an element of join->join_tab array, or to
512  join->join_tab[-1].
513  This is used at execution stage to shortcut join enumeration. Currently
514  shortcutting is done to handle outer joins or handle semi-joins with
515  FirstMatch strategy.
516  */
518 
519  /**
520  ref_items is an array of 4+ slices, each containing an array of Item
521  pointers. ref_items is used in different phases of query execution.
522  - slice 0 is initially the same as Query_block::base_ref_items, ie it is
523  the set of items referencing fields from base tables. During optimization
524  and execution it may be temporarily overwritten by slice 1-3.
525  - slice 1 is a representation of the used items when being read from
526  the first temporary table.
527  - slice 2 is a representation of the used items when being read from
528  the second temporary table.
529  - slice 3 is a copy of the original slice 0. It is created if
530  slice overwriting is necessary, and it is used to restore
531  original values in slice 0 after having been overwritten.
532  - slices 4 -> N are used by windowing: all the window's out tmp tables,
533 
534  Two windows: 4: window 1's out table
535  5: window 2's out table
536 
537  and so on.
538 
539  Slice 0 is allocated for the lifetime of a statement, whereas slices 1-3
540  are associated with a single optimization. The size of slice 0 determines
541  the slice size used when allocating the other slices.
542  */
544  nullptr}; // cardinality: REF_SLICE_SAVED_BASE + 1 + #windows*2
545 
546  /**
547  The slice currently stored in ref_items[0].
548  Used to restore the base ref_items slice from the "save" slice after it
549  has been overwritten by another slice (1-3).
550  */
552 
553  /**
554  Used only if this query block is recursive. Contains count of
555  all executions of this recursive query block, since the last
556  this->reset().
557  */
559 
560  /**
561  <> NULL if optimization has determined that execution will produce an
562  empty result before aggregation, contains a textual explanation on why
563  result is empty. Implicitly grouped queries may still produce an
564  aggregation row.
565  @todo - suggest to set to "Preparation determined that query is empty"
566  when Query_block::is_empty_query() is true.
567  */
568  const char *zero_result_cause{nullptr};
569 
570  /**
571  True if, at this stage of processing, subquery materialization is allowed
572  for children subqueries of this JOIN (those in the SELECT list, in WHERE,
573  etc). If false, and we have to evaluate a subquery at this stage, then we
574  must choose EXISTS.
575  */
577  /**
578  True if plan search is allowed to use references to expressions outer to
579  this JOIN (for example may set up a 'ref' access looking up an outer
580  expression in the index, etc).
581  */
582  bool allow_outer_refs{false};
583 
584  /* Temporary tables used to weed-out semi-join duplicates */
587  /* end of allocation caching storage */
588 
589  /** Exec time only: true <=> current group has been sent */
590  bool group_sent{false};
591  /// If true, calculate found rows for this query block
592  bool calc_found_rows{false};
593 
594  /**
595  This will force tmp table to NOT use index + update for group
596  operation as it'll cause [de]serialization for each json aggregated
597  value and is very ineffective (times worse).
598  Server should use filesort, or tmp table + filesort to resolve GROUP BY
599  with JSON aggregate functions.
600  */
602 
603  /// True if plan is const, ie it will return zero or one rows.
604  bool plan_is_const() const { return const_tables == primary_tables; }
605 
606  /**
607  True if plan contains one non-const primary table (ie not including
608  tables taking part in semi-join materialization).
609  */
611 
612  bool optimize(bool finalize_access_paths);
613  void reset();
614  bool prepare_result();
615  void destroy();
616  bool alloc_func_list();
618  bool before_group_by, bool recompute = false);
619 
620  /**
621  Overwrites one slice of ref_items with the contents of another slice.
622  In the normal case, dst and src have the same size().
623  However: the rollup slices may have smaller size than slice_sz.
624  */
625  void copy_ref_item_slice(uint dst_slice, uint src_slice) {
626  copy_ref_item_slice(ref_items[dst_slice], ref_items[src_slice]);
627  }
629  assert(dst_arr.size() >= src_arr.size());
630  void *dest = dst_arr.array();
631  const void *src = src_arr.array();
632  if (!src_arr.is_null())
633  memcpy(dest, src, src_arr.size() * src_arr.element_size());
634  }
635 
636  /**
637  Allocate a ref_item slice, assume that slice size is in ref_items[0]
638 
639  @param thd_arg thread handler
640  @param sliceno The slice number to allocate in JOIN::ref_items
641 
642  @returns false if success, true if error
643  */
644  bool alloc_ref_item_slice(THD *thd_arg, int sliceno);
645 
646  /**
647  Overwrite the base slice of ref_items with the slice supplied as argument.
648 
649  @param sliceno number to overwrite the base slice with, must be 1-4 or
650  4 + windowno.
651  */
652  void set_ref_item_slice(uint sliceno) {
653  assert((int)sliceno >= 1);
654  if (current_ref_item_slice != sliceno) {
656  DBUG_PRINT("info", ("JOIN %p ref slice %u -> %u", this,
657  current_ref_item_slice, sliceno));
658  current_ref_item_slice = sliceno;
659  }
660  }
661 
662  /// @note do also consider Switch_ref_item_slice
664 
665  /**
666  Returns the clone of fields_list which is appropriate for evaluating
667  expressions at the current stage of execution; which stage is denoted by
668  the value of current_ref_item_slice.
669  */
671 
672  bool optimize_rollup();
674  /**
675  Release memory and, if possible, the open tables held by this execution
676  plan (and nested plans). It's used to release some tables before
677  the end of execution in order to increase concurrency and reduce
678  memory consumption.
679  */
680  void join_free();
681  /** Cleanup this JOIN. Not a full cleanup. reusable? */
682  void cleanup();
683 
684  bool clear_fields(table_map *save_nullinfo);
685  void restore_fields(table_map save_nullinfo);
686 
687  /**
688  Return whether the caller should send a row even if the join
689  produced no rows if:
690  - there is an aggregate function (sum_func_count!=0), and
691  - the query is not grouped, and
692  - a possible HAVING clause evaluates to TRUE.
693 
694  @note: if there is a having clause, it must be evaluated before
695  returning the row.
696  */
697  bool send_row_on_empty_set() const {
698  return (do_send_rows && tmp_table_param.sum_func_count != 0 &&
701  }
702 
703  bool generate_derived_keys();
704  void finalize_derived_keys();
705  bool get_best_combination();
706  bool attach_join_conditions(plan_idx last_tab);
707 
708  private:
709  bool attach_join_condition_to_nest(plan_idx first_inner, plan_idx last_tab,
710  Item *join_cond, bool is_sj_mat_cond);
711 
712  public:
715  bool sort_before_group);
717  void refine_best_rowcount();
719  table_map plan_tables, uint idx) const;
720  bool clear_sj_tmp_tables();
723 
724  void mark_const_table(JOIN_TAB *table, Key_use *key);
725  /// State of execution plan. Currently used only for EXPLAIN
727  NO_PLAN, ///< No plan is ready yet
728  ZERO_RESULT, ///< Zero result cause is set
729  NO_TABLES, ///< Plan has no tables
730  PLAN_READY ///< Plan is ready
731  };
732  /// See enum_plan_state
734  bool is_optimized() const { return optimized; }
735  void set_optimized() { optimized = true; }
736  bool is_executed() const { return executed; }
737  void set_executed() { executed = true; }
738 
739  /**
740  Retrieve the cost model object to be used for this join.
741 
742  @return Cost model object for the join
743  */
744 
745  const Cost_model_server *cost_model() const;
746 
747  /**
748  Check if FTS index only access is possible
749  */
750  bool fts_index_access(JOIN_TAB *tab);
751 
753  /**
754  Propagate dependencies between tables due to outer join relations.
755 
756  @returns false if success, true if error
757  */
758  bool propagate_dependencies();
759 
760  /**
761  Handle offloading of query parts to the underlying engines, when
762  such is supported by their implementation.
763 
764  @returns false if success, true if error
765  */
766  bool push_to_engines();
767 
769 
770  /**
771  If this query block was planned twice, once with and once without conditions
772  added by in2exists, changes the root access path to the one without
773  in2exists. If not (ie., there were never any such conditions in the first
774  place), does nothing.
775  */
777 
778  /**
779  In the case of rollup (only): After the base slice list was made, we may
780  have modified the field list to add rollup group items and sum switchers,
781  but there may be Items with refs that refer to the base slice. This function
782  refreshes the base slice (and its copy, REF_SLICE_SAVED_BASE) with a fresh
783  copy of the list from “fields”.
784 
785  When we get rid of slices entirely, we can get rid of this, too.
786  */
787  void refresh_base_slice();
788 
789  /**
790  Whether this query block needs finalization (see
791  FinalizePlanForQueryBlock()) before it can be actually used.
792  This only happens when using the hypergraph join optimizer.
793  */
794  bool needs_finalize{false};
795 
796  private:
797  bool optimized{false}; ///< flag to avoid double optimization in EXPLAIN
798 
799  /**
800  Set by exec(), reset by reset(). Note that this needs to be set
801  _during_ the query (not only when it's done executing), or the
802  dynamic range optimizer will not understand which tables have been
803  read.
804  */
805  bool executed{false};
806 
807  /// Final execution plan state. Currently used only for EXPLAIN
809 
810  public:
811  /*
812  When join->select_count is set, tables will not be optimized away.
813  The call to records() will be delayed until the execution phase and
814  the counting will be done on an index of Optimizer's choice.
815  The index will be decided in find_shortest_key(), called from
816  optimize_aggregated_query().
817  */
818  bool select_count{false};
819 
820  private:
821  /**
822  Create a temporary table to be used for processing DISTINCT/ORDER
823  BY/GROUP BY.
824 
825  @note Will modify JOIN object wrt sort/group attributes
826 
827  @param tab the JOIN_TAB object to attach created table to
828  @param tmp_table_fields List of items that will be used to define
829  column types of the table.
830  @param tmp_table_group Group key to use for temporary table, empty if none.
831  @param save_sum_fields If true, do not replace Item_sum items in
832  @c tmp_fields list with Item_field items referring
833  to fields in temporary table.
834 
835  @returns false on success, true on failure
836  */
838  const mem_root_deque<Item *> &tmp_table_fields,
839  ORDER_with_src &tmp_table_group,
840  bool save_sum_fields);
841 
842  /**
843  Optimize distinct when used on a subset of the tables.
844 
845  E.g.,: SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
846  In this case we can stop scanning t2 when we have found one t1.a
847  */
848  void optimize_distinct();
849 
850  /**
851  Function sets FT hints, initializes FT handlers and
852  checks if FT index can be used as covered.
853  */
854  bool optimize_fts_query();
855 
856  bool prune_table_partitions();
857  /**
858  Initialize key dependencies for join tables.
859 
860  TODO figure out necessity of this method. Current test
861  suite passed without this intialization.
862  */
864  JOIN_TAB *const tab_end = join_tab + tables;
865  for (JOIN_TAB *tab = join_tab; tab < tab_end; tab++)
866  tab->key_dependent = tab->dependent;
867  }
868 
869  private:
870  void set_prefix_tables();
871  void cleanup_item_list(const mem_root_deque<Item *> &items) const;
872  void set_semijoin_embedding();
873  bool make_join_plan();
874  bool init_planner_arrays();
875  bool extract_const_tables();
878  bool estimate_rowcount();
879  void optimize_keyuse();
880  void set_semijoin_info();
881  /**
882  An utility function - apply heuristics and optimize access methods to tables.
883  @note Side effect - this function could set 'Impossible WHERE' zero
884  result.
885  */
886  void adjust_access_methods();
887  void update_depend_map();
889  /**
890  Fill in outer join related info for the execution plan structure.
891 
892  For each outer join operation left after simplification of the
893  original query the function set up the following pointers in the linear
894  structure join->join_tab representing the selected execution plan.
895  The first inner table t0 for the operation is set to refer to the last
896  inner table tk through the field t0->last_inner.
897  Any inner table ti for the operation are set to refer to the first
898  inner table ti->first_inner.
899  The first inner table t0 for the operation is set to refer to the
900  first inner table of the embedding outer join operation, if there is any,
901  through the field t0->first_upper.
902  The on expression for the outer join operation is attached to the
903  corresponding first inner table through the field t0->on_expr_ref.
904  Here ti are structures of the JOIN_TAB type.
905 
906  EXAMPLE. For the query:
907  @code
908  SELECT * FROM t1
909  LEFT JOIN
910  (t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
911  ON (t1.a=t2.a AND t1.b=t3.b)
912  WHERE t1.c > 5,
913  @endcode
914 
915  given the execution plan with the table order t1,t2,t3,t4
916  is selected, the following references will be set;
917  t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
918  t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
919  on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
920  *t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
921 
922  @note
923  The function assumes that the simplification procedure has been
924  already applied to the join query (see simplify_joins).
925  This function can be called only after the execution plan
926  has been chosen.
927  */
928  void make_outerjoin_info();
929 
930  /**
931  Initialize ref access for all tables that use it.
932 
933  @return False if success, True if error
934 
935  @note We cannot setup fields used for ref access before we have sorted
936  the items within multiple equalities according to the final order of
937  the tables involved in the join operation. Currently, this occurs in
938  @see substitute_for_best_equal_field().
939  */
940  bool init_ref_access();
941  bool alloc_qep(uint n);
942  void unplug_join_tabs();
944  POSITION *inner_pos,
945  POSITION *sjm_pos);
946 
947  bool add_having_as_tmp_table_cond(uint curr_tmp_table);
948  bool make_tmp_tables_info();
949  void set_plan_state(enum_plan_state plan_state_arg);
951  ORDER *remove_const(ORDER *first_order, Item *cond, bool change_list,
952  bool *simple_order, bool group_by);
953 
954  /**
955  Check whether this is a subquery that can be evaluated by index look-ups.
956  If so, change subquery engine to subselect_indexsubquery_engine.
957 
958  @retval 1 engine was changed
959  @retval 0 engine wasn't changed
960  @retval -1 OOM or other error
961  */
963 
964  /**
965  Optimize DISTINCT, GROUP BY, ORDER BY clauses
966 
967  @retval false ok
968  @retval true an error occurred
969  */
971 
972  /**
973  Test if an index could be used to replace filesort for ORDER BY/GROUP BY
974 
975  @details
976  Investigate whether we may use an ordered index as part of either
977  DISTINCT, GROUP BY or ORDER BY execution. An ordered index may be
978  used for only the first of any of these terms to be executed. This
979  is reflected in the order which we check for test_if_skip_sort_order()
980  below. However we do not check for DISTINCT here, as it would have
981  been transformed to a GROUP BY at this stage if it is a candidate for
982  ordered index optimization.
983  If a decision was made to use an ordered index, the availability
984  if such an access path is stored in 'm_ordered_index_usage' for later
985  use by 'execute' or 'explain'
986  */
987  void test_skip_sort();
988 
990 
991  /**
992  Convert the executor structures to a set of access paths, storing
993  the result in m_root_access_path.
994  */
995  void create_access_paths();
996 
997  /**
998  Create access paths with the knowledge that there are going to be zero rows
999  coming from tables (before aggregation); typically because we know that
1000  all of them would be filtered away by WHERE (e.g. SELECT * FROM t1
1001  WHERE 1=2). This will normally yield no output rows, but if we have implicit
1002  aggregation, it might yield a single one.
1003  */
1005 
1007 
1008  /** @{ Helpers for create_access_paths. */
1011  /** @} */
1012 
1013  /**
1014  An access path you can read from to get all records for this query
1015  (after you create an iterator from it).
1016  */
1018 
1019  /**
1020  If this query block contains conditions synthesized during IN-to-EXISTS
1021  conversion: A second query plan with all such conditions removed.
1022  See comments in JOIN::optimize().
1023  */
1025 };
1026 
1027 /**
1028  Use this in a function which depends on best_ref listing tables in the
1029  final join order. If 'tables==0', one is not expected to consult best_ref
1030  cells, and best_ref may not even have been allocated.
1031 */
1032 #define ASSERT_BEST_REF_IN_JOIN_ORDER(join) \
1033  do { \
1034  assert((join)->tables == 0 || ((join)->best_ref && !(join)->join_tab)); \
1035  } while (0)
1036 
1037 /**
1038  RAII class to ease the temporary switching to a different slice of
1039  the ref item array.
1040 */
1044 
1045  public:
1046  Switch_ref_item_slice(JOIN *join_arg, uint new_v)
1047  : join(join_arg), saved(join->get_ref_item_slice()) {
1048  if (!join->ref_items[new_v].is_null()) join->set_ref_item_slice(new_v);
1049  }
1051 };
1052 
1053 bool uses_index_fields_only(Item *item, TABLE *tbl, uint keyno,
1054  bool other_tbls_ok);
1055 bool remove_eq_conds(THD *thd, Item *cond, Item **retcond,
1056  Item::cond_result *cond_value);
1057 bool optimize_cond(THD *thd, Item **conds, COND_EQUAL **cond_equal,
1058  mem_root_deque<TABLE_LIST *> *join_list,
1059  Item::cond_result *cond_value);
1061  COND_EQUAL *cond_equal,
1062  JOIN_TAB **table_join_idx);
1063 bool build_equal_items(THD *thd, Item *cond, Item **retcond,
1064  COND_EQUAL *inherited, bool do_inherit,
1065  mem_root_deque<TABLE_LIST *> *join_list,
1066  COND_EQUAL **cond_equal_ref);
1068  mem_root_deque<Item_field *> *out_args);
1070  THD *thd, uint keyparts, Item_field **fields,
1071  const mem_root_deque<Item *> &outer_exprs);
1072 Item_field *get_best_field(Item_field *item_field, COND_EQUAL *cond_equal);
1073 Item *make_cond_for_table(THD *thd, Item *cond, table_map tables,
1074  table_map used_table, bool exclude_expensive_cond);
1076  uint first_unused);
1077 
1078 /**
1079  Create an order list that consists of all non-const fields and items.
1080  This is usable for e.g. converting DISTINCT into GROUP or ORDER BY.
1081  Is ref_item_array is non-null (is_null() returns false), the items
1082  will point into the slice given by it. Otherwise, it points directly
1083  into *fields (this is the only reason why fields is not const).
1084 
1085  Try to put the items in "order_list" first, to allow one to optimize away
1086  a later ORDER BY.
1087  */
1088 ORDER *create_order_from_distinct(THD *thd, Ref_item_array ref_item_array,
1089  ORDER *order_list,
1090  mem_root_deque<Item *> *fields,
1091  bool skip_aggregates,
1092  bool convert_bit_fields_to_long,
1093  bool *all_order_by_fields_used);
1094 
1095 /**
1096  Returns true if arguments are a temporal Field having no date,
1097  part and a temporal expression having a date part.
1098  @param f Field
1099  @param v Expression
1100  */
1101 inline bool field_time_cmp_date(const Field *f, const Item *v) {
1102  const enum_field_types ft = f->type();
1103  return is_temporal_type(ft) && !is_temporal_type_with_date(ft) &&
1104  v->is_temporal_with_date();
1105 }
1106 
1107 bool substitute_gc(THD *thd, Query_block *query_block, Item *where_cond,
1108  ORDER *group_list, ORDER *order);
1109 
1110 /**
1111  This class restores a table_map object to its original value
1112  when '*this' is destroyed.
1113  */
1114 class Table_map_restorer final {
1115  /** The location to be restored.*/
1117  /** The original value to restore.*/
1119 
1120  public:
1121  /**
1122  Constructor.
1123  @param map The table map that we wish to restore.
1124  */
1126  : m_location(map), m_saved_value(*map) {}
1127 
1128  // This class is not intended to be copied.
1131 
1134  void assert_unchanged() const { assert(*m_location == m_saved_value); }
1135 };
1136 
1137 /**
1138  Estimates how many times a subquery will be executed as part of a
1139  query execution. If it is a cacheable subquery, the estimate tells
1140  how many times the subquery will be executed if it is not cached.
1141 
1142  @param[in] subquery the Item that represents the subquery
1143  @param[in,out] trace optimizer trace context
1144 
1145  @return the number of times the subquery is expected to be executed
1146 */
1147 double calculate_subquery_executions(const Item_subselect *subquery,
1148  Opt_trace_context *trace);
1149 
1150 extern const char *antijoin_null_cond;
1151 
1152 /**
1153  Checks if an Item, which is constant for execution, can be evaluated during
1154  optimization. It cannot be evaluated if it contains a subquery and the
1155  OPTION_NO_SUBQUERY_DURING_OPTIMIZATION query option is active.
1156 
1157  @param item the Item to check
1158  @param select the query block that contains the Item
1159  @return false if this Item contains a subquery and subqueries cannot be
1160  evaluated during optimization, or true otherwise
1161 */
1162 bool evaluate_during_optimization(const Item *item, const Query_block *select);
1163 
1164 /**
1165  Find the multiple equality predicate containing a field.
1166 
1167  The function retrieves the multiple equalities accessed through
1168  the cond_equal structure from current level and up looking for
1169  an equality containing a field. It stops retrieval as soon as the equality
1170  is found and set up inherited_fl to true if it's found on upper levels.
1171 
1172  @param cond_equal multiple equalities to search in
1173  @param item_field field to look for
1174  @param[out] inherited_fl set up to true if multiple equality is found
1175  on upper levels (not on current level of
1176  cond_equal)
1177 
1178  @return
1179  - Item_equal for the found multiple equality predicate if a success;
1180  - nullptr otherwise.
1181 */
1183  const Item_field *item_field, bool *inherited_fl);
1184 
1185 /**
1186  Find an artificial cap for ref access. This is mostly a crutch to mitigate
1187  that we don't estimate the cache effects of ref accesses properly
1188  (ie., normally, if we do many, they will hit cache instead of being
1189  separate seeks). Given to find_cost_for_ref().
1190  */
1191 double find_worst_seeks(const Cost_model_table *cost_model, double num_rows,
1192  double table_scan_cost);
1193 
1194 /**
1195  Whether a ref lookup of “right_item” on “field” will give an exact
1196  comparison in all cases, ie., one can remove any further checks on
1197  field = right_item. If not, there may be false positives, and one
1198  needs to keep the comparison after the ref lookup.
1199  */
1200 bool ref_lookup_subsumes_comparison(Field *field, Item *right_item);
1201 
1202 bool HasFullTextFunction(Item *item);
1203 
1204 #endif /* SQL_OPTIMIZER_INCLUDED */
bool is_null() const
Definition: sql_array.h:134
size_t size() const
Definition: sql_array.h:131
size_t element_size() const
Definition: sql_array.h:130
Element_type * array() const
Definition: sql_array.h:142
Definition: item_cmpfunc.h:2609
API for getting cost estimates for server operations that are not directly related to a table object.
Definition: opt_costmodel.h:41
API for getting cost estimates for operations on table data.
Definition: opt_costmodel.h:229
Definition: opt_explain_format.h:448
Definition: field.h:590
virtual enum_field_types type() const =0
Definition: item_cmpfunc.h:2474
Definition: item.h:4027
Definition: item_subselect.h:79
Class Item_sum is the base class used for special expressions that SQL calls 'set functions'.
Definition: item_sum.h:398
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:802
bool is_temporal_with_date() const
Definition: item.h:3002
cond_result
Definition: item.h:871
@ COND_FALSE
Definition: item.h:871
Query optimization plan node.
Definition: sql_select.h:597
Definition: sql_optimizer.h:125
const Cost_model_server * cost_model() const
Retrieve the cost model object to be used for this join.
Definition: sql_optimizer.cc:11064
bool skip_sort_order
Is set if we have a GROUP BY and we have ORDER BY on a constant or when sorting isn't required.
Definition: sql_optimizer.h:395
bool attach_join_condition_to_nest(plan_idx first_inner, plan_idx last_tab, Item *join_cond, bool is_sj_mat_cond)
Helper for JOIN::attach_join_conditions().
Definition: sql_optimizer.cc:8425
bool calc_found_rows
If true, calculate found rows for this query block.
Definition: sql_optimizer.h:592
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:610
JOIN & operator=(const JOIN &rhs)=delete
void mark_const_table(JOIN_TAB *table, Key_use *key)
Move const tables first in the position array.
Definition: sql_optimizer.cc:8256
JOIN_TAB * join_tab
Optimal query execution plan.
Definition: sql_optimizer.h:146
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:297
Item_sum ** sum_funcs
Definition: sql_optimizer.h:341
List< Cached_item > group_fields
Definition: sql_optimizer.h:335
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:457
MYSQL_LOCK * lock
Definition: sql_optimizer.h:349
bool executed
Set by exec(), reset by reset().
Definition: sql_optimizer.h:805
QEP_TAB * qep_tab
Array of QEP_TABs.
Definition: sql_optimizer.h:148
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:697
ha_rows found_records
Definition: sql_optimizer.h:283
uint recursive_iteration_count
Used only if this query block is recursive.
Definition: sql_optimizer.h:558
void copy_ref_item_slice(Ref_item_array dst_arr, Ref_item_array src_arr)
Definition: sql_optimizer.h:628
bool child_subquery_can_materialize
True if, at this stage of processing, subquery materialization is allowed for children subqueries of ...
Definition: sql_optimizer.h:576
Prealloced_array< Item_rollup_group_item *, 4 > rollup_group_items
Definition: sql_optimizer.h:443
COND_EQUAL * cond_equal
Definition: sql_optimizer.h:509
JOIN_TAB ** map2table
mapping between table indexes and JOIN_TABs
Definition: sql_optimizer.h:158
ha_rows m_select_limit
Definition: sql_optimizer.h:287
POSITION * positions
Definition: sql_optimizer.h:309
uint current_ref_item_slice
The slice currently stored in ref_items[0].
Definition: sql_optimizer.h:551
bool is_executed() const
Definition: sql_optimizer.h:736
uint tables
Before plan has been created, "tables" denote number of input tables in the query block and "primary_...
Definition: sql_optimizer.h:207
bool has_lateral
If JOIN has lateral derived tables (is set at start of planning)
Definition: sql_optimizer.h:405
bool need_tmp_before_win
If true we need a temporary table on the result set before any windowing steps, e....
Definition: sql_optimizer.h:402
Prealloced_array< Item_rollup_sum_switcher *, 4 > rollup_sums
Definition: sql_optimizer.h:445
uint tmp_tables
Number of temporary tables used by query.
Definition: sql_optimizer.h:210
int error
set in optimize(), exec(), prepare_result()
Definition: sql_optimizer.h:427
bool plan_is_const() const
True if plan is const, ie it will return zero or one rows.
Definition: sql_optimizer.h:604
table_map const_table_map
Set of tables found to be const.
Definition: sql_optimizer.h:234
Prealloced_array< TemporaryTableToCleanup, 1 > temp_tables
Definition: sql_optimizer.h:176
Query_block *const query_block
Query block that is optimized and executed using this JOIN.
Definition: sql_optimizer.h:137
bool select_distinct
At construction time, set if SELECT DISTINCT.
Definition: sql_optimizer.h:359
RollupState
Definition: sql_optimizer.h:351
List< TABLE > sj_tmp_tables
Definition: sql_optimizer.h:585
table_map found_const_table_map
Const tables which are either:
Definition: sql_optimizer.h:241
bool simple_order
Definition: sql_optimizer.h:377
void set_executed()
Definition: sql_optimizer.h:737
List< Window > m_windows
Any window definitions.
Definition: sql_optimizer.h:451
AccessPath * root_access_path() const
Definition: sql_optimizer.h:768
Explain_format_flags explain_flags
Buffer to gather GROUP BY, ORDER BY and DISTINCT QEP details for EXPLAIN.
Definition: sql_optimizer.h:465
mem_root_deque< Item * > * tmp_fields
Array of pointers to lists of expressions.
Definition: sql_optimizer.h:425
uint const_tables
Number of primary tables deemed constant.
Definition: sql_optimizer.h:209
Prealloced_array< Filesort *, 1 > filesorts_to_cleanup
Definition: sql_optimizer.h:181
ha_rows examined_rows
Definition: sql_optimizer.h:284
ha_rows row_limit
Definition: sql_optimizer.h:285
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:582
JOIN_TAB ** best_ref
Array of plan operators representing the current (partial) best plan.
Definition: sql_optimizer.h:156
Item * having_for_explain
Saved optimized HAVING for EXPLAIN.
Definition: sql_optimizer.h:502
RollupState rollup_state
Definition: sql_optimizer.h:352
ha_rows send_records
Definition: sql_optimizer.h:282
Override_executor_func override_executor_func
Definition: sql_optimizer.h:318
plan_idx return_tab
Definition: sql_optimizer.h:517
enum_plan_state plan_state
Final execution plan state. Currently used only for EXPLAIN.
Definition: sql_optimizer.h:808
Item * having_cond
Optimized HAVING clause item tree (valid for one single execution).
Definition: sql_optimizer.h:501
void make_outerjoin_info()
Fill in outer join related info for the execution plan structure.
Definition: sql_optimizer.cc:8285
TABLE_LIST * tables_list
Pointer set to query_block->get_table_list() at the start of optimization.
Definition: sql_optimizer.h:508
mem_root_deque< Item * > * fields
Definition: sql_optimizer.h:334
Temp_table_param tmp_table_param
Describes a temporary table.
Definition: sql_optimizer.h:348
bool select_count
Definition: sql_optimizer.h:818
bool m_windowing_steps
If we have set up tmp tables for windowing,.
Definition: sql_optimizer.h:460
@ ORDERED_INDEX_GROUP_BY
Definition: sql_optimizer.h:387
@ ORDERED_INDEX_VOID
Definition: sql_optimizer.h:386
@ ORDERED_INDEX_ORDER_BY
Definition: sql_optimizer.h:388
bool fts_index_access(JOIN_TAB *tab)
Check if FTS index only access is possible.
Definition: sql_optimizer.cc:10586
void optimize_keyuse()
Update some values in keyuse for faster choose_table_order() loop.
Definition: sql_optimizer.cc:10488
bool with_json_agg
This will force tmp table to NOT use index + update for group operation as it'll cause [de]serializat...
Definition: sql_optimizer.h:601
uint send_group_parts
Definition: sql_optimizer.h:211
bool finalize_table_conditions()
Remove redundant predicates and cache constant expressions.
Definition: sql_optimizer.cc:8879
AccessPath * m_root_access_path_no_in2exists
If this query block contains conditions synthesized during IN-to-EXISTS conversion: A second query pl...
Definition: sql_optimizer.h:1024
ORDER_with_src group_list
Definition: sql_optimizer.h:439
double sort_cost
Expected cost of filesort.
Definition: sql_optimizer.h:331
bool generate_derived_keys()
Add keys to derived tables'/views' result tables in a list.
Definition: sql_optimizer.cc:8956
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:10527
enum_plan_state
State of execution plan. Currently used only for EXPLAIN.
Definition: sql_optimizer.h:726
@ NO_TABLES
Plan has no tables.
Definition: sql_optimizer.h:729
@ NO_PLAN
No plan is ready yet.
Definition: sql_optimizer.h:727
@ ZERO_RESULT
Zero result cause is set.
Definition: sql_optimizer.h:728
@ PLAN_READY
Plan is ready.
Definition: sql_optimizer.h:730
Key_use_array keyuse_array
Used and updated by JOIN::make_join_plan() and optimize_keyuse()
Definition: sql_optimizer.h:408
bool group_sent
Exec time only: true <=> current group has been sent.
Definition: sql_optimizer.h:590
bool needs_finalize
Whether this query block needs finalization (see FinalizePlanForQueryBlock()) before it can be actual...
Definition: sql_optimizer.h:794
void init_key_dependencies()
Initialize key dependencies for join tables.
Definition: sql_optimizer.h:863
void set_ref_item_slice(uint sliceno)
Overwrite the base slice of ref_items with the slice supplied as argument.
Definition: sql_optimizer.h:652
List< Cached_item > group_fields_cache
Definition: sql_optimizer.h:336
bool streaming_aggregation
Indicates that the data will be aggregated (typically GROUP BY), and that it is already processed in ...
Definition: sql_optimizer.h:227
void set_optimized()
Definition: sql_optimizer.h:735
uint primary_tables
Number of primary input tables in query block.
Definition: sql_optimizer.h:208
bool optimize_rollup()
Optimize rollup specification.
Definition: sql_optimizer.cc:11021
THD *const thd
Thread handler.
Definition: sql_optimizer.h:139
table_map all_table_map
Set of tables contained in query.
Definition: sql_optimizer.h:233
bool attach_join_conditions(plan_idx last_tab)
Attach outer join conditions to generated table conditions in an optimal way.
Definition: sql_optimizer.cc:8536
bool decide_subquery_strategy()
Decides between EXISTS and materialization; performs last steps to set up the chosen strategy.
Definition: sql_optimizer.cc:10735
List< Semijoin_mat_exec > sjm_exec_list
Definition: sql_optimizer.h:586
JOIN(const JOIN &rhs)=delete
TABLE * sort_by_table
Definition: sql_optimizer.h:164
Ref_item_array * ref_items
ref_items is an array of 4+ slices, each containing an array of Item pointers.
Definition: sql_optimizer.h:543
bool do_send_rows
If true, send produced rows using query_result.
Definition: sql_optimizer.h:231
double windowing_cost
Expected cost of windowing;.
Definition: sql_optimizer.h:333
enum_plan_state get_plan_state() const
See enum_plan_state.
Definition: sql_optimizer.h:733
ORDER_with_src order
ORDER BY and GROUP BY lists, to transform with prepare,optimize and exec.
Definition: sql_optimizer.h:439
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:368
double best_read
The cost of best complete join plan found so far during optimization, after optimization phase - cost...
Definition: sql_optimizer.h:325
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:9860
bool implicit_grouping
True if aggregated but no GROUP BY.
Definition: sql_optimizer.h:353
POSITION * best_positions
This is the result of join optimization.
Definition: sql_optimizer.h:304
void finalize_derived_keys()
For each materialized derived table/view, informs every TABLE of the key it will (not) use,...
Definition: sql_optimizer.cc:8976
bool optimized
flag to avoid double optimization in EXPLAIN
Definition: sql_optimizer.h:797
bool compare_costs_of_subquery_strategies(Subquery_strategy *method)
Tells what is the cheapest between IN->EXISTS and subquery materialization, in terms of cost,...
Definition: sql_optimizer.cc:10796
bool is_optimized() const
Definition: sql_optimizer.h:734
enum JOIN::@160 ORDERED_INDEX_VOID
const char * zero_result_cause
<> NULL if optimization has determined that execution will produce an empty result before aggregation...
Definition: sql_optimizer.h:568
Query_expression * query_expression() const
Query expression referring this query block.
Definition: sql_optimizer.h:132
mem_root_deque< Item * > * get_current_fields()
Returns the clone of fields_list which is appropriate for evaluating expressions at the current stage...
Definition: sql_optimizer.cc:11058
bool(*)(JOIN *, Query_result *) Override_executor_func
A hook that secondary storage engines can use to override the executor completely.
Definition: sql_optimizer.h:317
void clear_hash_tables()
Definition: sql_optimizer.h:722
uint get_ref_item_slice() const
Definition: sql_optimizer.h:663
List< Cached_item > semijoin_deduplication_fields
Definition: sql_optimizer.h:339
bool grouped
If query contains GROUP BY clause.
Definition: sql_optimizer.h:229
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:11032
AccessPath * m_root_access_path
An access path you can read from to get all records for this query (after you create an iterator from...
Definition: sql_optimizer.h:1017
ha_rows best_rowcount
The estimated row count of the plan with best read time (see above).
Definition: sql_optimizer.h:329
Item * where_cond
JOIN::having_cond is initially equal to query_block->having_cond, but may later be changed by optimiz...
Definition: sql_optimizer.h:491
bool simple_group
Definition: sql_optimizer.h:378
uint64_t hash_table_generation
Incremented each time clear_hash_tables() is run, signaling to HashJoinIterators that they cannot kee...
Definition: sql_optimizer.h:434
table_map deps_of_remaining_lateral_derived_tables
This is the bitmap of all tables which are dependencies of lateral derived tables which are not (yet)...
Definition: sql_optimizer.h:279
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:625
A Key_use represents an equality predicate of the form (table.column = val), where the column is inde...
Definition: sql_select.h:173
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:418
Wrapper for ORDER* pointer to trace origins of ORDER list.
Definition: sql_optimizer.h:95
bool empty() const
Definition: sql_optimizer.h:111
int get_flags() const
Definition: sql_optimizer.h:119
void clean()
Definition: sql_optimizer.h:113
ORDER * order
ORDER expression that we are wrapping with this class.
Definition: sql_optimizer.h:97
ORDER_with_src()
Definition: sql_optimizer.h:104
Explain_sort_clause src
origin of order list
Definition: sql_optimizer.h:98
int flags
bitmap of Explain_sort_property
Definition: sql_optimizer.h:101
ORDER_with_src(ORDER *order_arg, Explain_sort_clause src_arg)
Definition: sql_optimizer.h:106
A per-session context which is always available at any point of execution, because in practice it's a...
Definition: opt_trace_context.h:89
A typesafe replacement for DYNAMIC_ARRAY.
Definition: prealloced_array.h:70
Definition: sql_executor.h:256
enum_op_type
Definition: sql_executor.h:403
This class represents a query block, aka a query specification, which is a query consisting of a SELE...
Definition: sql_lex.h:1123
Item::cond_result having_value
Definition: sql_lex.h:1996
Query_expression * master_query_expression() const
Definition: sql_lex.h:1199
This class represents a query expression (one query block or several query blocks combined with UNION...
Definition: sql_lex.h:629
Definition: query_result.h:55
RAII class to ease the temporary switching to a different slice of the ref item array.
Definition: sql_optimizer.h:1041
Switch_ref_item_slice(JOIN *join_arg, uint new_v)
Definition: sql_optimizer.h:1046
uint saved
Definition: sql_optimizer.h:1043
JOIN * join
Definition: sql_optimizer.h:1042
~Switch_ref_item_slice()
Definition: sql_optimizer.h:1050
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:821
This class restores a table_map object to its original value when '*this' is destroyed.
Definition: sql_optimizer.h:1114
Table_map_restorer(table_map *map)
Constructor.
Definition: sql_optimizer.h:1125
table_map *const m_location
The location to be restored.
Definition: sql_optimizer.h:1116
~Table_map_restorer()
Definition: sql_optimizer.h:1132
const table_map m_saved_value
The original value to restore.
Definition: sql_optimizer.h:1118
void restore()
Definition: sql_optimizer.h:1133
Table_map_restorer & operator=(const Table_map_restorer &)=delete
void assert_unchanged() const
Definition: sql_optimizer.h:1134
Table_map_restorer(const Table_map_restorer &)=delete
Object containing parameters used when creating and using temporary tables.
Definition: temp_table_param.h:98
uint sum_func_count
Number of fields in the query that have aggregate functions.
Definition: temp_table_param.h:135
Represents the (explicit) window of a SQL 2003 section 7.11 <window clause>, or the implicit (inlined...
Definition: window.h:94
A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT.
Definition: mem_root_deque.h:109
bool is_temporal_type(enum_field_types type)
Tests if field type is temporal, i.e.
Definition: field_common_properties.h:114
bool is_temporal_type_with_date(enum_field_types type)
Tests if field type is temporal and has date part, i.e.
Definition: field_common_properties.h:155
This file contains the field type.
enum_field_types
Column types for MySQL.
Definition: field_types.h:57
void optimize_distinct()
Optimize distinct when used on a subset of the tables.
Definition: sql_executor.cc:357
AccessPath * create_root_access_path_for_join()
Definition: sql_executor.cc:2850
void restore_fields(table_map save_nullinfo)
Restore all result fields for all tables specified in save_nullinfo.
Definition: sql_executor.cc:5208
bool create_intermediate_table(QEP_TAB *tab, const mem_root_deque< 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:185
AccessPath * attach_access_paths_for_having_and_limit(AccessPath *path)
Definition: sql_executor.cc:3180
QEP_TAB::enum_op_type get_end_select_func()
Definition: sql_executor.cc:585
void create_access_paths()
Convert the executor structures to a set of access paths, storing the result in m_root_access_path.
Definition: sql_executor.cc:2841
void create_access_paths_for_index_subquery()
Definition: sql_executor.cc:3213
bool clear_fields(table_map *save_nullinfo)
Set all column values from all input tables to NULL.
Definition: sql_executor.cc:5187
bool clear_corr_derived_tmp_tables()
Empties all correlated materialized derived tables.
Definition: sql_select.cc:1581
uint build_bitmap_for_nested_joins(mem_root_deque< TABLE_LIST * > *join_list, uint first_unused)
Assign each nested join structure a bit in nested_join_map.
Definition: sql_optimizer.cc:4832
bool alloc_func_list()
Make an array of pointers to sum_functions to speed up sum_func calculation.
Definition: sql_select.cc:3884
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:5681
bool add_sorting_to_table(uint idx, ORDER_with_src *order, bool sort_before_group)
Add Filesort object to the given table to sort if with filesort.
Definition: sql_select.cc:4795
bool clear_sj_tmp_tables()
Remove all rows from all temp tables used by NL-semijoin runtime.
Definition: sql_select.cc:1571
bool alloc_qep(uint n)
Definition: sql_optimizer.cc:1251
void change_to_access_path_without_in2exists()
If this query block was planned twice, once with and once without conditions added by in2exists,...
Definition: sql_optimizer.cc:1053
void unplug_join_tabs()
Definition: sql_select.cc:4767
bool push_to_engines()
Handle offloading of query parts to the underlying engines, when such is supported by their implement...
Definition: sql_optimizer.cc:1087
bool make_tmp_tables_info()
Init tmp tables usage info.
Definition: sql_select.cc:4167
bool make_join_plan()
Calculate best possible join order and initialize the join structure.
Definition: sql_optimizer.cc:5114
void set_semijoin_embedding()
Set semi-join embedding join nest pointers.
Definition: sql_optimizer.cc:5831
bool build_equal_items(THD *thd, Item *cond, Item **retcond, COND_EQUAL *inherited, bool do_inherit, mem_root_deque< 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:4274
bool optimize_distinct_group_order()
Optimize DISTINCT, GROUP BY, ORDER BY clauses.
Definition: sql_optimizer.cc:1398
JOIN(THD *thd_arg, Query_block *select)
Definition: sql_optimizer.cc:157
table_map calculate_deps_of_remaining_lateral_derived_tables(table_map plan_tables, uint idx) const
Finds the dependencies of the remaining lateral derived tables.
Definition: sql_optimizer.cc:3171
void set_prefix_tables()
Assign set of available (prefix) tables to all tables in query block.
Definition: sql_optimizer.cc:5007
void cleanup()
Cleanup this JOIN.
Definition: sql_select.cc:3522
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:6284
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:3585
void test_skip_sort()
Test if an index could be used to replace filesort for ORDER BY/GROUP BY.
Definition: sql_optimizer.cc:1584
void create_access_paths_for_zero_rows()
Create access paths with the knowledge that there are going to be zero rows coming from tables (befor...
Definition: sql_optimizer.cc:1059
bool HasFullTextFunction(Item *item)
Definition: sql_optimizer.cc:222
bool propagate_dependencies()
Propagate dependencies between tables due to outer join relations.
Definition: sql_optimizer.cc:5379
void adjust_access_methods()
An utility function - apply heuristics and optimize access methods to tables.
Definition: sql_optimizer.cc:2830
bool estimate_rowcount()
Estimate the number of matched rows for each joined table.
Definition: sql_optimizer.cc:5717
bool prune_table_partitions()
Prune partitions for all tables of a join (query block).
Definition: sql_optimizer.cc:2691
Item_equal * find_item_equal(COND_EQUAL *cond_equal, const Item_field *item_field, bool *inherited_fl)
Find the multiple equality predicate containing a field.
Definition: sql_optimizer.cc:3552
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:4580
void refresh_base_slice()
In the case of rollup (only): After the base slice list was made, we may have modified the field list...
Definition: sql_select.cc:4742
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.cc:197
bool setup_semijoin_materialized_table(JOIN_TAB *tab, uint tableno, POSITION *inner_pos, POSITION *sjm_pos)
Setup the materialized table for a semi-join nest.
Definition: sql_select.cc:2871
void join_free()
Release memory and, if possible, the open tables held by this execution plan (and nested plans).
Definition: sql_select.cc:3452
bool make_sum_func_list(const mem_root_deque< Item * > &fields, bool before_group_by, bool recompute=false)
Initialize 'sum_funcs' array with all Item_sum objects.
Definition: sql_select.cc:3932
bool extract_func_dependent_tables()
Extract const tables based on functional dependencies.
Definition: sql_optimizer.cc:5524
bool init_planner_arrays()
Initialize scratch arrays for the join order optimization.
Definition: sql_optimizer.cc:5252
bool substitute_gc(THD *thd, Query_block *query_block, 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:1134
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:2014
bool prepare_result()
Prepare join result.
Definition: sql_select.cc:1665
void destroy()
Clean up and destroy join object.
Definition: sql_select.cc:1683
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:4012
double find_worst_seeks(const Cost_model_table *cost_model, double num_rows, double table_scan_cost)
Find an artificial cap for ref access.
Definition: sql_optimizer.cc:5697
const char * antijoin_null_cond
Definition: sql_optimizer.cc:115
bool alloc_indirection_slices()
Definition: sql_optimizer.cc:207
void reset()
Reset the state of this join object so that it is ready for a new execution.
Definition: sql_select.cc:1602
bool optimize(bool finalize_access_paths)
Optimizes one query block into a query execution plan (QEP.)
Definition: sql_optimizer.cc:288
bool init_ref_access()
Initialize ref access for all tables that use it.
Definition: sql_select.cc:1991
bool get_best_combination()
Set up JOIN_TAB structs according to the picked join order in best_positions.
Definition: sql_optimizer.cc:2947
bool extract_const_tables()
Extract const tables based on row counts.
Definition: sql_optimizer.cc:5430
bool update_equalities_for_sjm()
Update equalities and keyuse references after semi-join materialization strategy is chosen.
Definition: sql_optimizer.cc:4943
void set_plan_state(enum_plan_state plan_state_arg)
Sets the plan's state of the JOIN.
Definition: sql_optimizer.cc:1223
void cleanup_item_list(const mem_root_deque< Item * > &items) const
Definition: sql_select.cc:1776
int replace_index_subquery()
Check whether this is a subquery that can be evaluated by index look-ups.
Definition: sql_optimizer.cc:1331
void update_depend_map()
Update the dependency map for the tables.
Definition: sql_optimizer.cc:4874
Subquery_strategy
Strategy which will be used to handle this subquery: flattening to a semi-join, conversion to a deriv...
Definition: item_subselect.h:390
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1138
#define HA_POS_ERROR
Definition: my_base.h:1140
#define DBUG_PRINT(keyword, arglist)
Definition: my_dbug.h:168
uint64_t table_map
Definition: my_table_map.h:29
static char * path
Definition: mysqldump.cc:130
std::string join(Container cont, const std::string &delim)
join elements of an container into a string separated by a delimiter.
Definition: string.h:144
EXPLAIN FORMAT=<format> <command>.
Explain_sort_clause
Enumeration of ORDER BY, GROUP BY and DISTINCT clauses for array indexing.
Definition: opt_explain_format.h:425
@ ESC_none
Definition: opt_explain_format.h:426
@ ESP_EXISTS
Original query has this clause.
Definition: opt_explain_format.h:441
@ ESP_none
Definition: opt_explain_format.h:440
required string key
Definition: replication_asynchronous_connection_failover.proto:59
Classes for query execution.
Common types of the Optimizer, used by optimization and execution.
@ REF_SLICE_ACTIVE
The slice which is used during evaluation of expressions; Item_ref::ref points there.
Definition: sql_opt_exec_shared.h:610
int8 plan_idx
This represents the index of a JOIN_TAB/QEP_TAB in an array.
Definition: sql_opt_exec_shared.h:40
ORDER * create_order_from_distinct(THD *thd, Ref_item_array ref_item_array, ORDER *order_list, mem_root_deque< Item * > *fields, bool skip_aggregates, bool convert_bit_fields_to_long, bool *all_order_by_fields_used)
Create an order list that consists of all non-const fields and items.
Definition: sql_optimizer.cc:10375
Key_use_array * create_keyuse_for_table(THD *thd, uint keyparts, Item_field **fields, const mem_root_deque< Item * > &outer_exprs)
Create a keyuse array for a table with a primary key.
Definition: sql_optimizer.cc:8219
bool evaluate_during_optimization(const Item *item, const Query_block *select)
Checks if an Item, which is constant for execution, can be evaluated during optimization.
Definition: sql_optimizer.cc:11103
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:10906
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:9182
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:1101
bool optimize_cond(THD *thd, Item **conds, COND_EQUAL **cond_equal, mem_root_deque< TABLE_LIST * > *join_list, Item::cond_result *cond_value)
Optimize conditions by.
Definition: sql_optimizer.cc:10009
bool ref_lookup_subsumes_comparison(Field *field, Item *right_item)
Whether a ref lookup of “right_item” on “field” will give an exact comparison in all cases,...
Definition: sql_optimizer.cc:8654
bool is_indexed_agg_distinct(JOIN *join, mem_root_deque< 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:7814
bool remove_eq_conds(THD *thd, Item *cond, Item **retcond, Item::cond_result *cond_value)
Removes const and eq items.
Definition: sql_optimizer.cc:10128
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:176
Definition: sql_optimizer.h:169
Temp_table_param * temp_table_param
Definition: sql_optimizer.h:174
TABLE * table
Definition: sql_optimizer.h:170
Definition: lock.h:38
Definition: table.h:279
A position of table within a join order.
Definition: sql_select.h:350
Definition: sql_optimizer.h:82
Item ** arg_value
Definition: sql_optimizer.h:84
Field * field
Definition: sql_optimizer.h:83
uint num_values
Definition: sql_optimizer.h:85
Definition: table.h:2694
Definition: table.h:1394
unsigned int uint
Definition: uca-dump.cc:29
#define PSI_NOT_INSTRUMENTED
Definition: validate_password_imp.cc:39
int n
Definition: xcom_base.cc:505