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