1 /* 2 Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved. 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 "sql_priv.h" 26 #include "sql_select.h" 27 #include "sql_optimizer.h" 28 #include "abstract_query_plan.h" 29 #include "sql_join_buffer.h" 30 31 namespace AQP 32 { 33 34 /** 35 @param join_tab Array of access methods constituting the nested loop join. 36 @param access_count Length of array. 37 */ Join_plan(const JOIN * join)38 Join_plan::Join_plan(const JOIN* join) 39 : m_join_tabs(join->join_tab), 40 m_access_count(join->primary_tables), 41 m_table_accesses(NULL) 42 { 43 /* 44 This combination is assumed not to appear. If it does, code must 45 be written to handle it. 46 */ 47 DBUG_ASSERT((m_join_tabs[0].use_quick != 2) 48 || (m_join_tabs[0].type == JT_ALL) 49 || (m_join_tabs[0].select == NULL) 50 || (m_join_tabs[0].select->quick == NULL)); 51 52 m_table_accesses= new Table_access[m_access_count]; 53 for(uint i= 0; i < m_access_count; i++) 54 { 55 m_table_accesses[i].m_join_plan= this; 56 m_table_accesses[i].m_tab_no= i; 57 } 58 } 59 ~Join_plan()60 Join_plan::~Join_plan() 61 { 62 delete[] m_table_accesses; 63 m_table_accesses= NULL; 64 } 65 66 /** Get the JOIN_TAB of the n'th table access operation.*/ get_join_tab(uint join_tab_no) const67 const JOIN_TAB* Join_plan::get_join_tab(uint join_tab_no) const 68 { 69 DBUG_ASSERT(join_tab_no < m_access_count); 70 return m_join_tabs + join_tab_no; 71 } 72 73 /** 74 Determine join type between this table access and some other table 75 access that preceeds it in the join plan.. 76 */ 77 enum_join_type get_join_type(const Table_access * predecessor) const78 Table_access::get_join_type(const Table_access* predecessor) const 79 { 80 DBUG_ENTER("get_join_type"); 81 DBUG_ASSERT(get_access_no() > predecessor->get_access_no()); 82 83 const JOIN_TAB* const first_inner= get_join_tab()->first_inner; 84 if (first_inner == NULL) 85 { 86 // 'this' is not outer joined with any table. 87 DBUG_PRINT("info", ("JT_INNER_JOIN'ed table %s", 88 get_join_tab()->table->alias)); 89 DBUG_RETURN(JT_INNER_JOIN); 90 } 91 92 /** 93 * Fall Through: 'this' is a member in an outer join, 94 * but 'predecessor' may still be embedded in the same 95 * inner join as 'this'. 96 */ 97 const JOIN_TAB* const last_inner= first_inner->last_inner; 98 if (predecessor->get_join_tab() >= first_inner && 99 predecessor->get_join_tab() <= last_inner) 100 { 101 DBUG_PRINT("info", ("JT_INNER_JOIN between %s and %s", 102 predecessor->get_join_tab()->table->alias, 103 get_join_tab()->table->alias)); 104 DBUG_RETURN(JT_INNER_JOIN); 105 } 106 else 107 { 108 DBUG_PRINT("info", ("JT_OUTER_JOIN between %s and %s", 109 predecessor->get_join_tab()->table->alias, 110 get_join_tab()->table->alias)); 111 DBUG_RETURN(JT_OUTER_JOIN); 112 } 113 } //Table_access::get_join_type 114 115 /** 116 Get the number of key values for this operation. It is an error 117 to call this method on an operation that is not an index lookup 118 operation. 119 */ get_no_of_key_fields() const120 uint Table_access::get_no_of_key_fields() const 121 { 122 DBUG_ASSERT(m_access_type == AT_PRIMARY_KEY || 123 m_access_type == AT_UNIQUE_KEY || 124 m_access_type == AT_MULTI_PRIMARY_KEY || 125 m_access_type == AT_MULTI_UNIQUE_KEY || 126 m_access_type == AT_ORDERED_INDEX_SCAN); // Used as 'range scan' 127 return get_join_tab()->ref.key_parts; 128 } 129 130 /** 131 Get the field_no'th key values for this operation. It is an error 132 to call this method on an operation that is not an index lookup 133 operation. 134 */ get_key_field(uint field_no) const135 const Item* Table_access::get_key_field(uint field_no) const 136 { 137 DBUG_ASSERT(field_no < get_no_of_key_fields()); 138 return get_join_tab()->ref.items[field_no]; 139 } 140 141 /** 142 Get the field_no'th KEY_PART_INFO for this operation. It is an error 143 to call this method on an operation that is not an index lookup 144 operation. 145 */ get_key_part_info(uint field_no) const146 const KEY_PART_INFO* Table_access::get_key_part_info(uint field_no) const 147 { 148 DBUG_ASSERT(field_no < get_no_of_key_fields()); 149 const KEY* key= &get_join_tab()->table->key_info[get_join_tab()->ref.key]; 150 return &key->key_part[field_no]; 151 } 152 153 /** 154 Get the table that this operation accesses. 155 */ get_table() const156 TABLE* Table_access::get_table() const 157 { 158 return get_join_tab()->table; 159 } 160 get_fanout() const161 double Table_access::get_fanout() const 162 { 163 switch (get_access_type()) 164 { 165 case AT_PRIMARY_KEY: 166 case AT_UNIQUE_KEY: 167 return 1.0; 168 169 case AT_ORDERED_INDEX_SCAN: 170 DBUG_ASSERT(get_join_tab()->position); 171 DBUG_ASSERT(get_join_tab()->position->records_read>0.0); 172 return get_join_tab()->position->records_read; 173 174 case AT_MULTI_PRIMARY_KEY: 175 case AT_MULTI_UNIQUE_KEY: 176 case AT_MULTI_MIXED: 177 DBUG_ASSERT(get_join_tab()->position); 178 DBUG_ASSERT(get_join_tab()->position->records_read>0.0); 179 return get_join_tab()->position->records_read; 180 181 case AT_TABLE_SCAN: 182 DBUG_ASSERT(get_join_tab()->table->file->stats.records>0.0); 183 return static_cast<double>(get_join_tab()->table->file->stats.records); 184 185 default: 186 return 99999999.0; 187 } 188 } 189 190 /** Get the JOIN_TAB object that corresponds to this operation.*/ get_join_tab() const191 const JOIN_TAB* Table_access::get_join_tab() const 192 { 193 return m_join_plan->get_join_tab(m_tab_no); 194 } 195 196 /** Get the Item_equal's set relevant for the specified 'Item_field' */ 197 Item_equal* get_item_equal(const Item_field * field_item) const198 Table_access::get_item_equal(const Item_field* field_item) const 199 { 200 DBUG_ASSERT(field_item->type() == Item::FIELD_ITEM); 201 202 COND_EQUAL* const cond_equal = get_join_tab()->join->cond_equal; 203 if (cond_equal!=NULL) 204 { 205 return (field_item->item_equal != NULL) 206 ? field_item->item_equal 207 : const_cast<Item_field*>(field_item)->find_item_equal(cond_equal); 208 } 209 return NULL; 210 } 211 212 /** 213 Write an entry in the trace file about the contents of this object. 214 */ dbug_print() const215 void Table_access::dbug_print() const 216 { 217 DBUG_PRINT("info", ("type:%d", get_join_tab()->type)); 218 DBUG_PRINT("info", ("ref.key:%d", get_join_tab()->ref.key)); 219 DBUG_PRINT("info", ("ref.key_parts:%d", get_join_tab()->ref.key_parts)); 220 DBUG_PRINT("info", ("ref.key_length:%d", get_join_tab()->ref.key_length)); 221 222 DBUG_PRINT("info", ("order:%p", get_join_tab()->join->order.order)); 223 DBUG_PRINT("info", ("skip_sort_order:%d", 224 get_join_tab()->join->skip_sort_order)); 225 DBUG_PRINT("info", ("no_order:%d", get_join_tab()->join->no_order)); 226 DBUG_PRINT("info", ("simple_order:%d", get_join_tab()->join->simple_order)); 227 228 DBUG_PRINT("info", ("group:%d", get_join_tab()->join->group)); 229 DBUG_PRINT("info", ("group_list:%p", get_join_tab()->join->group_list.order)); 230 DBUG_PRINT("info", ("simple_group:%d", get_join_tab()->join->simple_group)); 231 DBUG_PRINT("info", ("group_optimized_away:%d", 232 get_join_tab()->join->group_optimized_away)); 233 234 DBUG_PRINT("info", ("full_join:%d", get_join_tab()->join->full_join)); 235 DBUG_PRINT("info", ("need_tmp:%d", get_join_tab()->join->need_tmp)); 236 DBUG_PRINT("info", ("select_distinct:%d", 237 get_join_tab()->join->select_distinct)); 238 239 DBUG_PRINT("info", ("use_quick:%d", get_join_tab()->use_quick)); 240 DBUG_PRINT("info", ("index:%d", get_join_tab()->index)); 241 DBUG_PRINT("info", ("quick:%p", get_join_tab()->quick)); 242 DBUG_PRINT("info", ("select:%p", get_join_tab()->select)); 243 if (get_join_tab()->select && get_join_tab()->select->quick) 244 { 245 DBUG_PRINT("info", ("select->quick->get_type():%d", 246 get_join_tab()->select->quick->get_type())); 247 } 248 } 249 250 251 /** 252 Compute the access type and index (if apliccable) of this operation . 253 */ compute_type_and_index() const254 void Table_access::compute_type_and_index() const 255 { 256 DBUG_ENTER("Table_access::compute_type_and_index"); 257 const JOIN_TAB* const join_tab= get_join_tab(); 258 JOIN* const join= join_tab->join; 259 260 /** 261 * OLEJA: I think this restriction can be removed 262 * now as WL5558 and other changes has cleaned up the 263 * ORDER/GROUP BY optimize + execute path. 264 */ 265 if (join->group_list && !join->tmp_table_param.quick_group) 266 { 267 m_access_type= AT_OTHER; 268 m_other_access_reason = 269 "GROUP BY cannot be done using index on grouped columns."; 270 DBUG_VOID_RETURN; 271 } 272 273 /* Tables below 'const_tables' has been const'ified, or entirely 274 * optimized away due to 'impossible WHERE/ON' 275 */ 276 if (join_tab < join->join_tab+join->const_tables) 277 { 278 DBUG_PRINT("info", ("Operation %d is const-optimized.", m_tab_no)); 279 m_access_type= AT_FIXED; 280 DBUG_VOID_RETURN; 281 } 282 283 /* 284 Identify the type of access operation and the index to use (if any). 285 */ 286 switch (join_tab->type) 287 { 288 case JT_EQ_REF: 289 m_index_no= join_tab->ref.key; 290 291 if (m_index_no == static_cast<int>(join_tab->table->s->primary_key)) 292 { 293 DBUG_PRINT("info", ("Operation %d is a primary key lookup.", m_tab_no)); 294 m_access_type= AT_PRIMARY_KEY; 295 } 296 else 297 { 298 DBUG_PRINT("info", ("Operation %d is a unique index lookup.", 299 m_tab_no)); 300 m_access_type= AT_UNIQUE_KEY; 301 } 302 break; 303 304 case JT_REF: 305 { 306 DBUG_ASSERT(join_tab->ref.key >= 0); 307 DBUG_ASSERT((uint)join_tab->ref.key < MAX_KEY); 308 m_index_no= join_tab->ref.key; 309 310 /* 311 All parts of a key are specified for an unique index -> access is a key lookup. 312 */ 313 const KEY *key_info= join_tab->table->s->key_info; 314 if (key_info[m_index_no].user_defined_key_parts == 315 join_tab->ref.key_parts && 316 key_info[m_index_no].flags & HA_NOSAME) 317 { 318 m_access_type= 319 (m_index_no == static_cast<int32>(join_tab->table->s->primary_key)) 320 ? AT_PRIMARY_KEY 321 : AT_UNIQUE_KEY; 322 DBUG_PRINT("info", ("Operation %d is an unique key referrence.", m_tab_no)); 323 } 324 else 325 { 326 DBUG_ASSERT(join_tab->ref.key_parts > 0); 327 DBUG_ASSERT(join_tab->ref.key_parts <= 328 key_info[m_index_no].user_defined_key_parts); 329 m_access_type= AT_ORDERED_INDEX_SCAN; 330 DBUG_PRINT("info", ("Operation %d is an ordered index scan.", m_tab_no)); 331 } 332 break; 333 } 334 case JT_INDEX_SCAN: 335 DBUG_ASSERT(join_tab->index < MAX_KEY); 336 m_index_no= join_tab->index; 337 m_access_type= AT_ORDERED_INDEX_SCAN; 338 DBUG_PRINT("info", ("Operation %d is an ordered index scan.", m_tab_no)); 339 break; 340 341 case JT_ALL: 342 if (join_tab->use_quick == 2) 343 { 344 /* 345 use_quick == 2 means that the decision on which access method to use 346 will be taken late (as rows from the preceeding operation arrive). 347 This operation is therefor not pushable. 348 */ 349 DBUG_PRINT("info", 350 ("Operation %d has 'use_quick == 2' -> not pushable", 351 m_tab_no)); 352 m_access_type= AT_UNDECIDED; 353 m_index_no= -1; 354 } 355 else 356 { 357 if (join_tab->select != NULL && 358 join_tab->select->quick != NULL) 359 { 360 QUICK_SELECT_I *quick= join_tab->select->quick; 361 362 /** QUICK_SELECT results in execution of MRR (Multi Range Read). 363 * Depending on each range, it may require execution of 364 * either a PK-lookup or a range scan. To cover both of 365 * these we may need to prepare both a pushed lookup join 366 * and a pushed range scan. Currently we handle it as 367 * a range scan and convert e PK lookup to a (closed-) range 368 * whenever required. 369 **/ 370 371 const KEY *key_info= join_tab->table->s->key_info; 372 DBUG_EXECUTE("info", quick->dbug_dump(0, TRUE);); 373 374 // Temporary assert as we are still investigation the relation between 375 // 'quick->index == MAX_KEY' and the different quick_types 376 DBUG_ASSERT ((quick->index == MAX_KEY) == 377 ((quick->get_type() == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) || 378 (quick->get_type() == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) || 379 (quick->get_type() == QUICK_SELECT_I::QS_TYPE_ROR_UNION))); 380 381 // JT_INDEX_MERGE: We have a set of qualifying PKs as root of pushed joins 382 if (quick->index == MAX_KEY) 383 { 384 m_index_no= join_tab->table->s->primary_key; 385 m_access_type= AT_MULTI_PRIMARY_KEY; // Multiple PKs are produced by merge 386 } 387 388 // Else JT_RANGE: May be both exact PK and/or index scans when sorted index available 389 else if (quick->index == join_tab->table->s->primary_key) 390 { 391 m_index_no= quick->index; 392 if (key_info[m_index_no].algorithm == HA_KEY_ALG_HASH) 393 m_access_type= AT_MULTI_PRIMARY_KEY; // MRR w/ multiple PK's 394 else 395 m_access_type= AT_MULTI_MIXED; // MRR w/ both range and PKs 396 } 397 else 398 { 399 m_index_no= quick->index; 400 if (key_info[m_index_no].algorithm == HA_KEY_ALG_HASH) 401 m_access_type= AT_MULTI_UNIQUE_KEY; // MRR with multiple unique keys 402 else 403 m_access_type= AT_MULTI_MIXED; // MRR w/ both range and unique keys 404 } 405 } 406 else 407 { 408 DBUG_PRINT("info", ("Operation %d is a table scan.", m_tab_no)); 409 m_access_type= AT_TABLE_SCAN; 410 } 411 } 412 break; 413 414 case JT_CONST: 415 case JT_SYSTEM: 416 default: 417 /* 418 Other join_types either cannot be pushed or the code analyze them is 419 not yet in place. 420 */ 421 DBUG_PRINT("info", 422 ("Operation %d has join_type %d. -> Not pushable.", 423 m_tab_no, join_tab->type)); 424 m_access_type= AT_OTHER; 425 m_index_no= -1; 426 m_other_access_reason = "This table access method can not be pushed."; 427 break; 428 } 429 DBUG_VOID_RETURN; 430 } 431 // Table_access::compute_type_and_index() 432 433 Table_access()434 Table_access::Table_access() 435 :m_join_plan(NULL), 436 m_tab_no(0), 437 m_access_type(AT_VOID), 438 m_other_access_reason(NULL), 439 m_index_no(-1) 440 {} 441 442 /** 443 Check if the results from this operation will joined with results 444 from the next operation using a join buffer (instead of plain nested loop). 445 @return True if using a join buffer. 446 */ uses_join_cache() const447 bool Table_access::uses_join_cache() const 448 { 449 return get_join_tab()->use_join_cache != JOIN_CACHE::ALG_NONE; 450 } 451 452 /** 453 Check if this table will be presorted to an intermediate record storage 454 before it is joined with its siblings. 455 */ filesort_before_join() const456 bool Table_access::filesort_before_join() const 457 { 458 if (m_access_type == AT_PRIMARY_KEY || 459 m_access_type == AT_UNIQUE_KEY) 460 { 461 return false; 462 } 463 464 const JOIN_TAB* const join_tab= get_join_tab(); 465 JOIN* const join= join_tab->join; 466 467 /** 468 Table will be presorted before joining with child tables, if: 469 1) This is the first non-const table 470 2) There are more tables to be joined 471 3) It is not already decide to write entire join result to temp. 472 4a) The GROUP BY is 'simple' and does not match an orderd index 473 4b) The ORDER BY is 'simple' and does not match an orderd index 474 475 A 'simple' order/group by contain only column references to 476 the first non-const table 477 */ 478 if (join_tab == join->join_tab+join->const_tables &&// First non-const table 479 !join->plan_is_const()) // There are more tables 480 { 481 if (join->need_tmp) 482 return false; 483 else if (join->group_list && join->simple_group) 484 return (join->ordered_index_usage!=JOIN::ordered_index_group_by); 485 else if (join->order && join->simple_order) 486 return (join->ordered_index_usage!=JOIN::ordered_index_order_by); 487 else 488 return false; 489 } 490 return false; 491 } 492 493 }; 494 // namespace AQP 495