1 #ifndef SQL_PLANNER_INCLUDED 2 #define SQL_PLANNER_INCLUDED 3 4 /* Copyright (c) 2000, 2012, 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 /** @file Join planner classes */ 27 28 #include "sql_class.h" 29 #include "sql_select.h" 30 #include "sql_test.h" 31 #include "sql_optimizer.h" 32 33 class Opt_trace_object; 34 35 /** 36 This class determines the optimal join order for tables within 37 a basic query block, ie a query specification clause, possibly extended 38 with semi-joined tables from embedded subqueries. 39 40 This class takes as prerequisite a join class where all dependencies among 41 tables have been sorted out, all possible access paths have been 42 sorted out, and all statistics information has been filled in. 43 44 The class has a sole public function that will calculate the most 45 optimal plan based on the inputs and the environment, such as prune level 46 and greedy optimizer search depth. For more information, see the 47 function headers for the private functions greedy_search(), 48 best_extension_by_limited_search() and eq_ref_extension_by_limited_search(). 49 */ 50 51 class Optimize_table_order 52 { 53 public: Optimize_table_order(THD * thd,JOIN * join,TABLE_LIST * sjm_nest)54 Optimize_table_order(THD *thd, JOIN *join, TABLE_LIST *sjm_nest) 55 : search_depth(determine_search_depth(thd->variables.optimizer_search_depth, 56 join->tables - join->const_tables)), 57 prune_level(thd->variables.optimizer_prune_level), 58 thd(thd), join(join), 59 cur_embedding_map(0), emb_sjm_nest(sjm_nest), 60 excluded_tables((sjm_nest ? 61 (join->all_table_map & ~sjm_nest->sj_inner_tables) : 0) | 62 (join->allow_outer_refs ? 0 : OUTER_REF_TABLE_BIT)) 63 {} ~Optimize_table_order()64 ~Optimize_table_order() 65 {} 66 /** 67 Entry point to table join order optimization. 68 For further description, see class header and private function headers. 69 70 @return false if successful, true if error 71 */ 72 bool choose_table_order(); 73 74 private: 75 const uint search_depth; // Maximum search depth to apply in greedy search 76 const uint prune_level; // pruning heuristics to be applied 77 // (0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS) 78 THD *const thd; // Pointer to current THD 79 JOIN *const join; // Pointer to the current plan being developed 80 /** 81 Bitmap of all join nests embedding the last table appended to the current 82 partial join. 83 */ 84 nested_join_map cur_embedding_map; 85 /** 86 If non-NULL, we are optimizing a materialized semi-join nest. 87 If NULL, we are optimizing a complete join plan. 88 */ 89 const TABLE_LIST *const emb_sjm_nest; 90 /** 91 When calculating a plan for a materialized semi-join nest, 92 best_access_path() needs to know not only the remaining tables within the 93 semi-join nest, but also all tables outside of this nest, because there may 94 be key references between the semi-join nest and the outside tables 95 that should not be considered when materializing the semi-join nest. 96 @c excluded_tables tracks these tables. 97 */ 98 const table_map excluded_tables; 99 100 void best_access_path(JOIN_TAB *s, table_map remaining_tables, uint idx, 101 bool disable_jbuf, double record_count, 102 POSITION *pos, POSITION *loose_scan_pos); 103 bool check_interleaving_with_nj(JOIN_TAB *next_tab); 104 void advance_sj_state(table_map remaining_tables, 105 const JOIN_TAB *tab, uint idx, 106 double *current_rowcount, double *current_cost, 107 POSITION *loose_scan_pos); 108 void backout_nj_state(const table_map remaining_tables, 109 const JOIN_TAB *tab); 110 void optimize_straight_join(table_map join_tables); 111 bool greedy_search(table_map remaining_tables); 112 bool best_extension_by_limited_search(table_map remaining_tables, 113 uint idx, 114 double record_count, 115 double read_time, 116 uint current_search_depth); 117 table_map eq_ref_extension_by_limited_search( 118 table_map remaining_tables, 119 uint idx, 120 double record_count, 121 double read_time, 122 uint current_search_depth); 123 void consider_plan(uint idx, double record_count, double read_time, 124 Opt_trace_object *trace_obj); 125 bool fix_semijoin_strategies(); 126 bool semijoin_firstmatch_loosescan_access_paths( 127 uint first_tab, uint last_tab, table_map remaining_tables, 128 bool loosescan, bool final, 129 double *newcount, double *newcost); 130 void semijoin_mat_scan_access_paths( 131 uint last_inner_tab, uint last_outer_tab, 132 table_map remaining_tables, TABLE_LIST *sjm_nest, bool final, 133 double *newcount, double *newcost); 134 void semijoin_mat_lookup_access_paths( 135 uint last_inner, TABLE_LIST *sjm_nest, 136 double *newcount, double *newcost); 137 void semijoin_dupsweedout_access_paths( 138 uint first_tab, uint last_tab, 139 table_map remaining_tables, 140 double *newcount, double *newcost); 141 142 static uint determine_search_depth(uint search_depth, uint table_count); 143 }; 144 145 void get_partial_join_cost(JOIN *join, uint n_tables, double *read_time_arg, 146 double *record_count_arg); 147 148 #endif /* SQL_PLANNER_INCLUDED */ 149