1 /* 2 Copyright (c) 2010, 2019, MariaDB 3 4 This program is free software; you can redistribute it and/or modify 5 it under the terms of the GNU General Public License as published by 6 the Free Software Foundation; version 2 of the License. 7 8 This program is distributed in the hope that it will be useful, 9 but WITHOUT ANY WARRANTY; without even the implied warranty of 10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 GNU General Public License for more details. 12 13 You should have received a copy of the GNU General Public License 14 along with this program; if not, write to the Free Software 15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */ 16 17 /* 18 Semi-join subquery optimization code definitions 19 */ 20 21 #ifdef USE_PRAGMA_INTERFACE 22 #pragma interface /* gcc class implementation */ 23 #endif 24 25 int check_and_do_in_subquery_rewrites(JOIN *join); 26 bool convert_join_subqueries_to_semijoins(JOIN *join); 27 int pull_out_semijoin_tables(JOIN *join); 28 bool optimize_semijoin_nests(JOIN *join, table_map all_table_map); 29 bool setup_degenerate_jtbm_semi_joins(JOIN *join, 30 List<TABLE_LIST> *join_list, 31 List<Item> &eq_list); 32 bool setup_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list, 33 List<Item> &eq_list); 34 void cleanup_empty_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list); 35 36 // used by Loose_scan_opt 37 ulonglong get_bound_sj_equalities(TABLE_LIST *sj_nest, 38 table_map remaining_tables); 39 40 /* 41 This is a class for considering possible loose index scan optimizations. 42 It's usage pattern is as follows: 43 best_access_path() 44 { 45 Loose_scan_opt opt; 46 47 opt.init() 48 for each index we can do ref access with 49 { 50 opt.next_ref_key(); 51 for each keyuse 52 opt.add_keyuse(); 53 opt.check_ref_access(); 54 } 55 56 if (some criteria for range scans) 57 opt.check_range_access(); 58 59 opt.get_best_option(); 60 } 61 */ 62 63 class Loose_scan_opt 64 { 65 /* All methods must check this before doing anything else */ 66 bool try_loosescan; 67 68 /* 69 If we consider (oe1, .. oeN) IN (SELECT ie1, .. ieN) then ieK=oeK is 70 called sj-equality. If oeK depends only on preceding tables then such 71 equality is called 'bound'. 72 */ 73 ulonglong bound_sj_equalities; 74 75 /* Accumulated properties of ref access we're now considering: */ 76 ulonglong handled_sj_equalities; 77 key_part_map loose_scan_keyparts; 78 uint max_loose_keypart; 79 bool part1_conds_met; 80 81 /* 82 Use of quick select is a special case. Some of its properties: 83 */ 84 uint quick_uses_applicable_index; 85 uint quick_max_loose_keypart; 86 87 /* Best loose scan method so far */ 88 uint best_loose_scan_key; 89 double best_loose_scan_cost; 90 double best_loose_scan_records; 91 KEYUSE *best_loose_scan_start_key; 92 93 uint best_max_loose_keypart; 94 table_map best_ref_depend_map; 95 96 public: Loose_scan_opt()97 Loose_scan_opt(): 98 try_loosescan(false), 99 bound_sj_equalities(0), 100 quick_uses_applicable_index(0), 101 quick_max_loose_keypart(0), 102 best_loose_scan_key(0), 103 best_loose_scan_cost(0), 104 best_loose_scan_records(0), 105 best_loose_scan_start_key(NULL), 106 best_max_loose_keypart(0), 107 best_ref_depend_map(0) 108 { 109 } 110 init(JOIN * join,JOIN_TAB * s,table_map remaining_tables)111 void init(JOIN *join, JOIN_TAB *s, table_map remaining_tables) 112 { 113 /* 114 Discover the bound equalities. We need to do this if 115 1. The next table is an SJ-inner table, and 116 2. It is the first table from that semijoin, and 117 3. We're not within a semi-join range (i.e. all semi-joins either have 118 all or none of their tables in join_table_map), except 119 s->emb_sj_nest (which we've just entered, see #2). 120 4. All non-IN-equality correlation references from this sj-nest are 121 bound 122 5. But some of the IN-equalities aren't (so this can't be handled by 123 FirstMatch strategy) 124 */ 125 best_loose_scan_cost= DBL_MAX; 126 if (!join->emb_sjm_nest && s->emb_sj_nest && // (1) 127 s->emb_sj_nest->sj_in_exprs < 64 && 128 ((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2) 129 s->emb_sj_nest->sj_inner_tables) && // (2) 130 join->cur_sj_inner_tables == 0 && // (3) 131 !(remaining_tables & 132 s->emb_sj_nest->nested_join->sj_corr_tables) && // (4) 133 remaining_tables & s->emb_sj_nest->nested_join->sj_depends_on &&// (5) 134 optimizer_flag(join->thd, OPTIMIZER_SWITCH_LOOSE_SCAN)) 135 { 136 /* This table is an LooseScan scan candidate */ 137 bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest, 138 remaining_tables); 139 try_loosescan= TRUE; 140 DBUG_PRINT("info", ("Will try LooseScan scan, bound_map=%llx", 141 (longlong)bound_sj_equalities)); 142 } 143 } 144 next_ref_key()145 void next_ref_key() 146 { 147 handled_sj_equalities=0; 148 loose_scan_keyparts= 0; 149 max_loose_keypart= 0; 150 part1_conds_met= FALSE; 151 } 152 add_keyuse(table_map remaining_tables,KEYUSE * keyuse)153 void add_keyuse(table_map remaining_tables, KEYUSE *keyuse) 154 { 155 if (try_loosescan && keyuse->sj_pred_no != UINT_MAX && 156 (keyuse->table->file->index_flags(keyuse->key, 0, 1 ) & HA_READ_ORDER)) 157 158 { 159 if (!(remaining_tables & keyuse->used_tables)) 160 { 161 /* 162 This allows to use equality propagation to infer that some 163 sj-equalities are bound. 164 */ 165 bound_sj_equalities |= 1ULL << keyuse->sj_pred_no; 166 } 167 else 168 { 169 handled_sj_equalities |= 1ULL << keyuse->sj_pred_no; 170 loose_scan_keyparts |= ((key_part_map)1) << keyuse->keypart; 171 set_if_bigger(max_loose_keypart, keyuse->keypart); 172 } 173 } 174 } 175 have_a_case()176 bool have_a_case() { return MY_TEST(handled_sj_equalities); } 177 check_ref_access_part1(JOIN_TAB * s,uint key,KEYUSE * start_key,table_map found_part)178 void check_ref_access_part1(JOIN_TAB *s, uint key, KEYUSE *start_key, 179 table_map found_part) 180 { 181 /* 182 Check if we can use LooseScan semi-join strategy. We can if 183 1. This is the right table at right location 184 2. All IN-equalities are either 185 - "bound", ie. the outer_expr part refers to the preceding tables 186 - "handled", ie. covered by the index we're considering 187 3. Index order allows to enumerate subquery's duplicate groups in 188 order. This happens when the index definition matches this 189 pattern: 190 191 (handled_col|bound_col)* (other_col|bound_col) 192 193 */ 194 if (try_loosescan && // (1) 195 (handled_sj_equalities | bound_sj_equalities) == // (2) 196 PREV_BITS(ulonglong, s->emb_sj_nest->sj_in_exprs) && // (2) 197 (PREV_BITS(key_part_map, max_loose_keypart+1) & // (3) 198 (found_part | loose_scan_keyparts)) == // (3) 199 PREV_BITS(key_part_map, max_loose_keypart+1) && // (3) 200 !key_uses_partial_cols(s->table->s, key)) 201 { 202 if (s->quick && s->quick->index == key && 203 s->quick->get_type() == QUICK_SELECT_I::QS_TYPE_RANGE) 204 { 205 quick_uses_applicable_index= TRUE; 206 quick_max_loose_keypart= max_loose_keypart; 207 } 208 DBUG_PRINT("info", ("Can use LooseScan scan")); 209 210 if (found_part & 1) 211 { 212 /* Can use LooseScan on ref access if the first key part is bound */ 213 part1_conds_met= TRUE; 214 } 215 216 /* 217 Check if this is a special case where there are no usable bound 218 IN-equalities, i.e. we have 219 220 outer_expr IN (SELECT innertbl.key FROM ...) 221 222 and outer_expr cannot be evaluated yet, so it's actually full 223 index scan and not a ref access. 224 We can do full index scan if it uses index-only. 225 */ 226 if (!(found_part & 1 ) && /* no usable ref access for 1st key part */ 227 s->table->covering_keys.is_set(key)) 228 { 229 part1_conds_met= TRUE; 230 DBUG_PRINT("info", ("Can use full index scan for LooseScan")); 231 232 /* Calculate the cost of complete loose index scan. */ 233 double records= rows2double(s->table->file->stats.records); 234 235 /* The cost is entire index scan cost (divided by 2) */ 236 double read_time= s->table->file->keyread_time(key, 1, 237 (ha_rows) records); 238 239 /* 240 Now find out how many different keys we will get (for now we 241 ignore the fact that we have "keypart_i=const" restriction for 242 some key components, that may make us think think that loose 243 scan will produce more distinct records than it actually will) 244 */ 245 ulong rpc; 246 if ((rpc= s->table->key_info[key].rec_per_key[max_loose_keypart])) 247 records= records / rpc; 248 249 // TODO: previous version also did /2 250 if (read_time < best_loose_scan_cost) 251 { 252 best_loose_scan_key= key; 253 best_loose_scan_cost= read_time; 254 best_loose_scan_records= records; 255 best_max_loose_keypart= max_loose_keypart; 256 best_loose_scan_start_key= start_key; 257 best_ref_depend_map= 0; 258 } 259 } 260 } 261 } 262 check_ref_access_part2(uint key,KEYUSE * start_key,double records,double read_time,table_map ref_depend_map_arg)263 void check_ref_access_part2(uint key, KEYUSE *start_key, double records, 264 double read_time, table_map ref_depend_map_arg) 265 { 266 if (part1_conds_met && read_time < best_loose_scan_cost) 267 { 268 /* TODO use rec-per-key-based fanout calculations */ 269 best_loose_scan_key= key; 270 best_loose_scan_cost= read_time; 271 best_loose_scan_records= records; 272 best_max_loose_keypart= max_loose_keypart; 273 best_loose_scan_start_key= start_key; 274 best_ref_depend_map= ref_depend_map_arg; 275 } 276 } 277 check_range_access(JOIN * join,uint idx,QUICK_SELECT_I * quick)278 void check_range_access(JOIN *join, uint idx, QUICK_SELECT_I *quick) 279 { 280 /* TODO: this the right part restriction: */ 281 if (quick_uses_applicable_index && idx == join->const_tables && 282 quick->read_time < best_loose_scan_cost) 283 { 284 best_loose_scan_key= quick->index; 285 best_loose_scan_cost= quick->read_time; 286 /* this is ok because idx == join->const_tables */ 287 best_loose_scan_records= rows2double(quick->records); 288 best_max_loose_keypart= quick_max_loose_keypart; 289 best_loose_scan_start_key= NULL; 290 best_ref_depend_map= 0; 291 } 292 } 293 save_to_position(JOIN_TAB * tab,POSITION * pos)294 void save_to_position(JOIN_TAB *tab, POSITION *pos) 295 { 296 pos->read_time= best_loose_scan_cost; 297 if (best_loose_scan_cost != DBL_MAX) 298 { 299 pos->records_read= best_loose_scan_records; 300 pos->key= best_loose_scan_start_key; 301 pos->cond_selectivity= 1.0; 302 pos->loosescan_picker.loosescan_key= best_loose_scan_key; 303 pos->loosescan_picker.loosescan_parts= best_max_loose_keypart + 1; 304 pos->use_join_buffer= FALSE; 305 pos->table= tab; 306 pos->range_rowid_filter_info= tab->range_rowid_filter_info; 307 pos->ref_depend_map= best_ref_depend_map; 308 DBUG_PRINT("info", ("Produced a LooseScan plan, key %s, %s", 309 tab->table->key_info[best_loose_scan_key].name.str, 310 best_loose_scan_start_key? "(ref access)": 311 "(range/index access)")); 312 } 313 } 314 }; 315 316 317 void advance_sj_state(JOIN *join, table_map remaining_tables, uint idx, 318 double *current_record_count, double *current_read_time, 319 POSITION *loose_scan_pos); 320 void restore_prev_sj_state(const table_map remaining_tables, 321 const JOIN_TAB *tab, uint idx); 322 323 void fix_semijoin_strategies_for_picked_join_order(JOIN *join); 324 325 bool setup_sj_materialization_part1(JOIN_TAB *sjm_tab); 326 bool setup_sj_materialization_part2(JOIN_TAB *sjm_tab); 327 328 329 /* 330 Temporary table used by semi-join DuplicateElimination strategy 331 332 This consists of the temptable itself and data needed to put records 333 into it. The table's DDL is as follows: 334 335 CREATE TABLE tmptable (col VARCHAR(n) BINARY, PRIMARY KEY(col)); 336 337 where the primary key can be replaced with unique constraint if n exceeds 338 the limit (as it is always done for query execution-time temptables). 339 340 The record value is a concatenation of rowids of tables from the join we're 341 executing. If a join table is on the inner side of the outer join, we 342 assume that its rowid can be NULL and provide means to store this rowid in 343 the tuple. 344 */ 345 346 class SJ_TMP_TABLE : public Sql_alloc 347 { 348 public: 349 /* 350 Array of pointers to tables whose rowids compose the temporary table 351 record. 352 */ 353 class TAB 354 { 355 public: 356 JOIN_TAB *join_tab; 357 uint rowid_offset; 358 ushort null_byte; 359 uchar null_bit; 360 }; 361 TAB *tabs; 362 TAB *tabs_end; 363 364 /* 365 is_degenerate==TRUE means this is a special case where the temptable record 366 has zero length (and presence of a unique key means that the temptable can 367 have either 0 or 1 records). 368 In this case we don't create the physical temptable but instead record 369 its state in SJ_TMP_TABLE::have_degenerate_row. 370 */ 371 bool is_degenerate; 372 373 /* 374 When is_degenerate==TRUE: the contents of the table (whether it has the 375 record or not). 376 */ 377 bool have_degenerate_row; 378 379 /* table record parameters */ 380 uint null_bits; 381 uint null_bytes; 382 uint rowid_len; 383 384 /* The temporary table itself (NULL means not created yet) */ 385 TABLE *tmp_table; 386 387 /* 388 These are the members we got from temptable creation code. We'll need 389 them if we'll need to convert table from HEAP to MyISAM/Maria. 390 */ 391 TMP_ENGINE_COLUMNDEF *start_recinfo; 392 TMP_ENGINE_COLUMNDEF *recinfo; 393 394 SJ_TMP_TABLE *next_flush_table; 395 396 int sj_weedout_delete_rows(); 397 int sj_weedout_check_row(THD *thd); 398 bool create_sj_weedout_tmp_table(THD *thd); 399 }; 400 401 int setup_semijoin_loosescan(JOIN *join); 402 int setup_semijoin_dups_elimination(JOIN *join, ulonglong options, 403 uint no_jbuf_after); 404 void destroy_sj_tmp_tables(JOIN *join); 405 int clear_sj_tmp_tables(JOIN *join); 406 int rewrite_to_index_subquery_engine(JOIN *join); 407 408 409 void get_delayed_table_estimates(TABLE *table, 410 ha_rows *out_rows, 411 double *scan_time, 412 double *startup_cost); 413 414 enum_nested_loop_state join_tab_execution_startup(JOIN_TAB *tab); 415 416