1 /* 2 Copyright (c) 2010, 2021, Oracle and/or its affiliates. 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, version 2.0, 6 as published by the Free Software Foundation. 7 8 This program is also distributed with certain software (including 9 but not limited to OpenSSL) that is licensed under separate terms, 10 as designated in a particular file or component or in included license 11 documentation. The authors of MySQL hereby grant you an additional 12 permission to link the program and your derivative works with the 13 separately licensed software that they have included with MySQL. 14 15 This program is distributed in the hope that it will be useful, 16 but WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 GNU General Public License, version 2.0, for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with this program; if not, write to the Free Software 22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 23 */ 24 25 #include "abstract_query_plan.h" 26 27 #include "sql_optimizer.h" // JOIN 28 29 namespace AQP 30 { 31 32 /** 33 @param join_tab Array of access methods constituting the nested loop join. 34 @param access_count Length of array. 35 */ Join_plan(const JOIN * join)36 Join_plan::Join_plan(const JOIN* join) 37 : m_qep_tabs(join->qep_tab), 38 m_access_count(join->primary_tables), 39 m_table_accesses(NULL) 40 { 41 /* 42 This combination is assumed not to appear. If it does, code must 43 be written to handle it. 44 */ 45 assert(!m_qep_tabs[0].dynamic_range() 46 || (m_qep_tabs[0].type() == JT_ALL) 47 || (m_qep_tabs[0].quick() == NULL)); 48 49 m_table_accesses= new Table_access[m_access_count]; 50 for(uint i= 0; i < m_access_count; i++) 51 { 52 m_table_accesses[i].m_join_plan= this; 53 m_table_accesses[i].m_tab_no= i; 54 } 55 } 56 ~Join_plan()57 Join_plan::~Join_plan() 58 { 59 delete[] m_table_accesses; 60 m_table_accesses= NULL; 61 } 62 63 /** Get the QEP_TAB of the n'th table access operation.*/ get_qep_tab(uint qep_tab_no) const64 const QEP_TAB* Join_plan::get_qep_tab(uint qep_tab_no) const 65 { 66 assert(qep_tab_no < m_access_count); 67 return m_qep_tabs + qep_tab_no; 68 } 69 70 /** 71 Determine join type between this table access and some other table 72 access that preceeds it in the join plan.. 73 */ 74 enum_join_type get_join_type(const Table_access * predecessor) const75 Table_access::get_join_type(const Table_access* predecessor) const 76 { 77 DBUG_ENTER("get_join_type"); 78 assert(get_access_no() > predecessor->get_access_no()); 79 80 const QEP_TAB* const me= get_qep_tab(); 81 const plan_idx first_inner= me->first_inner(); 82 if (first_inner == NO_PLAN_IDX) 83 { 84 // 'this' is not outer joined with any table. 85 DBUG_PRINT("info", ("JT_INNER_JOIN'ed table %s", 86 me->table()->alias)); 87 DBUG_RETURN(JT_INNER_JOIN); 88 } 89 90 /** 91 * Fall Through: 'this' is a member in an outer join, 92 * but 'predecessor' may still be embedded in the same 93 * inner join as 'this'. 94 */ 95 const plan_idx last_inner= me->join()->qep_tab[first_inner].last_inner(); 96 if (predecessor->get_access_no() >= static_cast<uint>(first_inner) && 97 predecessor->get_access_no() <= static_cast<uint>(last_inner)) 98 { 99 DBUG_PRINT("info", ("JT_INNER_JOIN between %s and %s", 100 predecessor->get_qep_tab()->table()->alias, 101 me->table()->alias)); 102 DBUG_RETURN(JT_INNER_JOIN); 103 } 104 else 105 { 106 DBUG_PRINT("info", ("JT_OUTER_JOIN between %s and %s", 107 predecessor->get_qep_tab()->table()->alias, 108 me->table()->alias)); 109 DBUG_RETURN(JT_OUTER_JOIN); 110 } 111 } //Table_access::get_join_type 112 113 /** 114 Get the number of key values for this operation. It is an error 115 to call this method on an operation that is not an index lookup 116 operation. 117 */ get_no_of_key_fields() const118 uint Table_access::get_no_of_key_fields() const 119 { 120 assert(m_access_type == AT_PRIMARY_KEY || 121 m_access_type == AT_UNIQUE_KEY || 122 m_access_type == AT_MULTI_PRIMARY_KEY || 123 m_access_type == AT_MULTI_UNIQUE_KEY || 124 m_access_type == AT_ORDERED_INDEX_SCAN); // Used as 'range scan' 125 return get_qep_tab()->ref().key_parts; 126 } 127 128 /** 129 Get the field_no'th key values for this operation. It is an error 130 to call this method on an operation that is not an index lookup 131 operation. 132 */ get_key_field(uint field_no) const133 const Item* Table_access::get_key_field(uint field_no) const 134 { 135 assert(field_no < get_no_of_key_fields()); 136 return get_qep_tab()->ref().items[field_no]; 137 } 138 139 /** 140 Get the field_no'th KEY_PART_INFO for this operation. It is an error 141 to call this method on an operation that is not an index lookup 142 operation. 143 */ get_key_part_info(uint field_no) const144 const KEY_PART_INFO* Table_access::get_key_part_info(uint field_no) const 145 { 146 assert(field_no < get_no_of_key_fields()); 147 const KEY* key= &get_qep_tab()->table()->key_info[get_qep_tab()->ref().key]; 148 return &key->key_part[field_no]; 149 } 150 151 /** 152 Get the table that this operation accesses. 153 */ get_table() const154 TABLE* Table_access::get_table() const 155 { 156 return get_qep_tab()->table(); 157 } 158 get_fanout() const159 double Table_access::get_fanout() const 160 { 161 switch (get_access_type()) 162 { 163 case AT_PRIMARY_KEY: 164 case AT_UNIQUE_KEY: 165 return 1.0; 166 167 case AT_ORDERED_INDEX_SCAN: 168 assert(get_qep_tab()->position()); 169 assert(get_qep_tab()->position()->rows_fetched > 0.0); 170 return get_qep_tab()->position()->rows_fetched; 171 172 case AT_MULTI_PRIMARY_KEY: 173 case AT_MULTI_UNIQUE_KEY: 174 case AT_MULTI_MIXED: 175 assert(get_qep_tab()->position()); 176 assert(get_qep_tab()->position()->rows_fetched > 0.0); 177 return get_qep_tab()->position()->rows_fetched; 178 179 case AT_TABLE_SCAN: 180 assert(get_qep_tab()->table()->file->stats.records > 0.0); 181 return static_cast<double>(get_qep_tab()->table()->file->stats.records); 182 183 default: 184 return 99999999.0; 185 } 186 } 187 188 /** Get the QEP_TAB object that corresponds to this operation.*/ get_qep_tab() const189 const QEP_TAB* Table_access::get_qep_tab() const 190 { 191 return m_join_plan->get_qep_tab(m_tab_no); 192 } 193 194 /** Get the Item_equal's set relevant for the specified 'Item_field' */ 195 Item_equal* get_item_equal(const Item_field * field_item) const196 Table_access::get_item_equal(const Item_field* field_item) const 197 { 198 assert(field_item->type() == Item::FIELD_ITEM); 199 200 COND_EQUAL* const cond_equal = get_qep_tab()->join()->cond_equal; 201 if (cond_equal!=NULL) 202 { 203 return (field_item->item_equal != NULL) 204 ? field_item->item_equal 205 : const_cast<Item_field*>(field_item)->find_item_equal(cond_equal); 206 } 207 return NULL; 208 } 209 210 /** 211 Write an entry in the trace file about the contents of this object. 212 */ dbug_print() const213 void Table_access::dbug_print() const 214 { 215 DBUG_PRINT("info", ("type:%d", get_qep_tab()->type())); 216 DBUG_PRINT("info", ("ref().key:%d", get_qep_tab()->ref().key)); 217 DBUG_PRINT("info", ("ref().key_parts:%d", get_qep_tab()->ref().key_parts)); 218 DBUG_PRINT("info", ("ref().key_length:%d", get_qep_tab()->ref().key_length)); 219 220 DBUG_PRINT("info", ("order:%p", get_qep_tab()->join()->order.order)); 221 DBUG_PRINT("info", ("skip_sort_order:%d", 222 get_qep_tab()->join()->skip_sort_order)); 223 DBUG_PRINT("info", ("no_order:%d", get_qep_tab()->join()->no_order)); 224 DBUG_PRINT("info", ("simple_order:%d", get_qep_tab()->join()->simple_order)); 225 226 DBUG_PRINT("info", ("group:%d", get_qep_tab()->join()->grouped)); 227 DBUG_PRINT("info", ("group_list:%p", get_qep_tab()->join()->group_list.order)); 228 DBUG_PRINT("info", ("simple_group:%d", get_qep_tab()->join()->simple_group)); 229 DBUG_PRINT("info", ("group_optimized_away:%d", 230 get_qep_tab()->join()->group_optimized_away)); 231 232 DBUG_PRINT("info", ("need_tmp:%d", get_qep_tab()->join()->need_tmp)); 233 DBUG_PRINT("info", ("select_distinct:%d", 234 get_qep_tab()->join()->select_distinct)); 235 236 DBUG_PRINT("info", ("dynamic_range:%d", (int)get_qep_tab()->dynamic_range())); 237 DBUG_PRINT("info", ("index:%d", get_qep_tab()->index())); 238 DBUG_PRINT("info", ("quick:%p", get_qep_tab()->quick())); 239 if (get_qep_tab()->quick()) 240 { 241 DBUG_PRINT("info", ("quick->get_type():%d", 242 get_qep_tab()->quick()->get_type())); 243 } 244 } 245 246 247 /** 248 Compute the access type and index (if apliccable) of this operation . 249 */ compute_type_and_index() const250 void Table_access::compute_type_and_index() const 251 { 252 DBUG_ENTER("Table_access::compute_type_and_index"); 253 const QEP_TAB* const qep_tab= get_qep_tab(); 254 JOIN* const join= qep_tab->join(); 255 256 /** 257 * OLEJA: I think this restriction can be removed 258 * now as WL5558 and other changes has cleaned up the 259 * ORDER/GROUP BY optimize + execute path. 260 */ 261 if (join->group_list && !join->tmp_table_param.quick_group) 262 { 263 m_access_type= AT_OTHER; 264 m_other_access_reason = 265 "GROUP BY cannot be done using index on grouped columns."; 266 DBUG_VOID_RETURN; 267 } 268 269 /* Tables below 'const_tables' has been const'ified, or entirely 270 * optimized away due to 'impossible WHERE/ON' 271 */ 272 if (qep_tab < join->qep_tab + join->const_tables) 273 { 274 DBUG_PRINT("info", ("Operation %d is const-optimized.", m_tab_no)); 275 m_access_type= AT_FIXED; 276 DBUG_VOID_RETURN; 277 } 278 279 /* 280 Identify the type of access operation and the index to use (if any). 281 */ 282 switch (qep_tab->type()) 283 { 284 case JT_EQ_REF: 285 m_index_no= qep_tab->ref().key; 286 287 if (m_index_no == static_cast<int>(qep_tab->table()->s->primary_key)) 288 { 289 DBUG_PRINT("info", ("Operation %d is a primary key lookup.", m_tab_no)); 290 m_access_type= AT_PRIMARY_KEY; 291 } 292 else 293 { 294 DBUG_PRINT("info", ("Operation %d is a unique index lookup.", 295 m_tab_no)); 296 m_access_type= AT_UNIQUE_KEY; 297 } 298 break; 299 300 case JT_REF: 301 { 302 assert(qep_tab->ref().key >= 0); 303 assert((uint)qep_tab->ref().key < MAX_KEY); 304 m_index_no= qep_tab->ref().key; 305 306 /* 307 All parts of a key are specified for an unique index -> access is a key lookup. 308 */ 309 const KEY *key_info= qep_tab->table()->s->key_info; 310 if (key_info[m_index_no].user_defined_key_parts == 311 qep_tab->ref().key_parts && 312 key_info[m_index_no].flags & HA_NOSAME) 313 { 314 m_access_type= 315 (m_index_no == static_cast<int32>(qep_tab->table()->s->primary_key)) 316 ? AT_PRIMARY_KEY 317 : AT_UNIQUE_KEY; 318 DBUG_PRINT("info", ("Operation %d is an unique key referrence.", m_tab_no)); 319 } 320 else 321 { 322 assert(qep_tab->ref().key_parts > 0); 323 assert(qep_tab->ref().key_parts <= 324 key_info[m_index_no].user_defined_key_parts); 325 m_access_type= AT_ORDERED_INDEX_SCAN; 326 DBUG_PRINT("info", ("Operation %d is an ordered index scan.", m_tab_no)); 327 } 328 break; 329 } 330 case JT_INDEX_SCAN: 331 assert(qep_tab->index() < MAX_KEY); 332 m_index_no= qep_tab->index(); 333 m_access_type= AT_ORDERED_INDEX_SCAN; 334 DBUG_PRINT("info", ("Operation %d is an ordered index scan.", m_tab_no)); 335 break; 336 337 case JT_ALL: 338 case JT_RANGE: 339 case JT_INDEX_MERGE: 340 if (qep_tab->dynamic_range()) 341 { 342 /* 343 It means that the decision on which access method to use 344 will be taken late (as rows from the preceding operation arrive). 345 This operation is therefor not pushable. 346 */ 347 DBUG_PRINT("info", 348 ("Operation %d has 'dynamic range' -> not pushable", 349 m_tab_no)); 350 m_access_type= AT_UNDECIDED; 351 m_index_no= -1; 352 } 353 else 354 { 355 if (qep_tab->quick() != NULL) 356 { 357 QUICK_SELECT_I *quick= qep_tab->quick(); 358 359 /** QUICK_SELECT results in execution of MRR (Multi Range Read). 360 * Depending on each range, it may require execution of 361 * either a PK-lookup or a range scan. To cover both of 362 * these we may need to prepare both a pushed lookup join 363 * and a pushed range scan. Currently we handle it as 364 * a range scan and convert e PK lookup to a (closed-) range 365 * whenever required. 366 **/ 367 368 const KEY *key_info= qep_tab->table()->s->key_info; 369 DBUG_EXECUTE("info", quick->dbug_dump(0, TRUE);); 370 371 // Temporary assert as we are still investigation the relation between 372 // 'quick->index == MAX_KEY' and the different quick_types 373 assert ((quick->index == MAX_KEY) == 374 ((quick->get_type() == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) || 375 (quick->get_type() == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) || 376 (quick->get_type() == QUICK_SELECT_I::QS_TYPE_ROR_UNION))); 377 378 // JT_INDEX_MERGE: We have a set of qualifying PKs as root of pushed joins 379 if (quick->index == MAX_KEY) 380 { 381 m_index_no= qep_tab->table()->s->primary_key; 382 m_access_type= AT_MULTI_PRIMARY_KEY; // Multiple PKs are produced by merge 383 } 384 385 // Else JT_RANGE: May be both exact PK and/or index scans when sorted index available 386 else if (quick->index == qep_tab->table()->s->primary_key) 387 { 388 m_index_no= quick->index; 389 if (key_info[m_index_no].algorithm == HA_KEY_ALG_HASH) 390 m_access_type= AT_MULTI_PRIMARY_KEY; // MRR w/ multiple PK's 391 else 392 m_access_type= AT_MULTI_MIXED; // MRR w/ both range and PKs 393 } 394 else 395 { 396 m_index_no= quick->index; 397 if (key_info[m_index_no].algorithm == HA_KEY_ALG_HASH) 398 m_access_type= AT_MULTI_UNIQUE_KEY; // MRR with multiple unique keys 399 else 400 m_access_type= AT_MULTI_MIXED; // MRR w/ both range and unique keys 401 } 402 } 403 else 404 { 405 DBUG_PRINT("info", ("Operation %d is a table scan.", m_tab_no)); 406 m_access_type= AT_TABLE_SCAN; 407 } 408 } 409 break; 410 411 case JT_CONST: 412 case JT_SYSTEM: 413 default: 414 /* 415 Other join_types either cannot be pushed or the code analyze them is 416 not yet in place. 417 */ 418 DBUG_PRINT("info", 419 ("Operation %d has join_type %d. -> Not pushable.", 420 m_tab_no, qep_tab->type())); 421 m_access_type= AT_OTHER; 422 m_index_no= -1; 423 m_other_access_reason = "This table access method can not be pushed."; 424 break; 425 } 426 DBUG_VOID_RETURN; 427 } 428 // Table_access::compute_type_and_index() 429 430 Table_access()431 Table_access::Table_access() 432 :m_join_plan(NULL), 433 m_tab_no(0), 434 m_access_type(AT_VOID), 435 m_other_access_reason(NULL), 436 m_index_no(-1) 437 {} 438 439 /** 440 Check if the results from this operation will joined with results 441 from the next operation using a join buffer (instead of plain nested loop). 442 @return True if using a join buffer. 443 */ uses_join_cache() const444 bool Table_access::uses_join_cache() const 445 { 446 return get_qep_tab()->op && 447 get_qep_tab()->op->type() == QEP_operation::OT_CACHE; 448 } 449 450 /** 451 Check if 'FirstMatch' strategy is used for this table and return 452 the last table 'firstmatch' will skip over. 453 The tables ['last_skipped'..'this'] will form a range of tables 454 which we skipped when a 'firstmatch' is found 455 */ get_firstmatch_last_skipped() const456 const Table_access* Table_access::get_firstmatch_last_skipped() const 457 { 458 const QEP_TAB* const qep_tab= get_qep_tab(); 459 if (qep_tab->do_firstmatch()) 460 { 461 assert(qep_tab->firstmatch_return < qep_tab->idx()); 462 const uint firstmatch_last_skipped= 463 qep_tab->firstmatch_return + 1; 464 465 return m_join_plan->get_table_access(firstmatch_last_skipped); 466 } 467 return NULL; 468 } 469 470 /** 471 Check if this table will be presorted to an intermediate record storage 472 before it is joined with its siblings. 473 */ filesort_before_join() const474 bool Table_access::filesort_before_join() const 475 { 476 if (m_access_type == AT_PRIMARY_KEY || 477 m_access_type == AT_UNIQUE_KEY) 478 { 479 return false; 480 } 481 482 const QEP_TAB* const qep_tab= get_qep_tab(); 483 JOIN* const join= qep_tab->join(); 484 485 /** 486 Table will be presorted before joining with child tables, if: 487 1) This is the first non-const table 488 2) There are more tables to be joined 489 3) It is not already decide to write entire join result to temp. 490 4a) The GROUP BY is 'simple' and does not match an orderd index 491 4b) The ORDER BY is 'simple' and does not match an orderd index 492 493 A 'simple' order/group by contain only column references to 494 the first non-const table 495 */ 496 if (qep_tab == join->qep_tab + join->const_tables && // First non-const table 497 !join->plan_is_const()) // There are more tables 498 { 499 if (join->need_tmp) 500 return false; 501 else if (join->group_list && join->simple_group) 502 return (join->ordered_index_usage!=JOIN::ordered_index_group_by); 503 else if (join->order && join->simple_order) 504 return (join->ordered_index_usage!=JOIN::ordered_index_order_by); 505 else 506 return false; 507 } 508 return false; 509 } 510 set_pushed_table_access_method() const511 void Table_access::set_pushed_table_access_method() const 512 { 513 // Remove the QEP_TABs constness allowing the QEP_TAB 514 // instance for this part ot the join to be modified 515 QEP_TAB* const qep_tab= const_cast<QEP_TAB*>(get_qep_tab()); 516 qep_tab->set_pushed_table_access_method(); 517 } 518 519 }; 520 // namespace AQP 521