1 /* Copyright (c) 2014, 2017, Oracle and/or its affiliates. All rights reserved. 2 3 This program is free software; you can redistribute it and/or modify 4 it under the terms of the GNU General Public License, version 2.0, 5 as published by the Free Software Foundation. 6 7 This program is also distributed with certain software (including 8 but not limited to OpenSSL) that is licensed under separate terms, 9 as designated in a particular file or component or in included license 10 documentation. The authors of MySQL hereby grant you an additional 11 permission to link the program and your derivative works with the 12 separately licensed software that they have included with MySQL. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License, version 2.0, for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with this program; if not, write to the Free Software 21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ 22 23 /// @file Common types of the Optimizer, used by optimization and execution 24 25 #ifndef SQL_OPT_EXEC_SHARED_INCLUDED 26 #define SQL_OPT_EXEC_SHARED_INCLUDED 27 28 #include "my_base.h" 29 #include "item.h" // Item 30 #include "sql_alloc.h" // Sql_alloc 31 #include "sql_class.h" // Temp_table_param 32 33 class JOIN; 34 class Item_func_match; 35 class store_key; 36 class QUICK_SELECT_I; 37 38 /** 39 This represents the index of a JOIN_TAB/QEP_TAB in an array. "plan_idx": "Plan 40 Table Index". 41 It is signed, because: 42 - firstmatch_return may be PRE_FIRST_PLAN_IDX (it can happen that the first 43 table of the plan uses FirstMatch: SELECT ... WHERE literal IN (SELECT 44 ...)). 45 - it must hold the invalid value NO_PLAN_IDX (which means "no 46 JOIN_TAB/QEP_TAB", equivalent of NULL pointer); this invalid value must 47 itself be different from PRE_FIRST_PLAN_IDX, to distinguish "FirstMatch to 48 before-first-table" (firstmatch_return==PRE_FIRST_PLAN_IDX) from "No 49 FirstMatch" (firstmatch_return==NO_PLAN_IDX). 50 */ 51 typedef int8 plan_idx; 52 #define NO_PLAN_IDX (-2) ///< undefined index 53 #define PRE_FIRST_PLAN_IDX (-1) ///< right before the first (first's index is 0) 54 55 56 typedef struct st_table_ref : public Sql_alloc 57 { 58 bool key_err; 59 /** True if something was read into buffer in join_read_key. */ 60 bool has_record; 61 uint key_parts; ///< num of ... 62 uint key_length; ///< length of key_buff 63 int key; ///< key no 64 uchar *key_buff; ///< value to look for with key 65 uchar *key_buff2; ///< key_buff+key_length 66 /** 67 Used to store the value from each keypart field. These values are 68 used for ref access. If key_copy[key_part] == NULL it means that 69 the value is constant and does not need to be reevaluated 70 */ 71 store_key **key_copy; 72 Item **items; ///< val()'s for each keypart 73 /* 74 Array of pointers to trigger variables. Some/all of the pointers may be 75 NULL. The ref access can be used iff 76 77 for each used key part i, (!cond_guards[i] || *cond_guards[i]) 78 79 This array is used by subquery code. The subquery code may inject 80 triggered conditions, i.e. conditions that can be 'switched off'. A ref 81 access created from such condition is not valid when at least one of the 82 underlying conditions is switched off (see subquery code for more details). 83 If a table in a subquery has this it means that the table access 84 will switch from ref access to table scan when the outer query 85 produces a NULL value to be checked for in the subquery. This will 86 be used by NOT IN subqueries and IN subqueries for which 87 is_top_level_item() returns false. 88 */ 89 bool **cond_guards; 90 /** 91 (null_rejecting & (1<<i)) means the condition is '=' and no matching 92 rows will be produced if items[i] IS NULL (see add_not_null_conds()) 93 */ 94 key_part_map null_rejecting; 95 table_map depend_map; ///< Table depends on these tables. 96 /* null byte position in the key_buf. Used for REF_OR_NULL optimization */ 97 uchar *null_ref_key; 98 /* 99 The number of times the record associated with this key was used 100 in the join. 101 */ 102 ha_rows use_count; 103 104 /* 105 TRUE <=> disable the "cache" as doing lookup with the same key value may 106 produce different results (because of Index Condition Pushdown) 107 */ 108 bool disable_cache; 109 st_table_refst_table_ref110 st_table_ref() 111 : key_err(TRUE), 112 has_record(FALSE), 113 key_parts(0), 114 key_length(0), 115 key(-1), 116 key_buff(NULL), 117 key_buff2(NULL), 118 key_copy(NULL), 119 items(NULL), 120 cond_guards(NULL), 121 null_rejecting(0), 122 depend_map(0), 123 null_ref_key(NULL), 124 use_count(0), 125 disable_cache(FALSE) 126 { 127 } 128 129 /** 130 @returns whether the reference contains NULL values which could never give 131 a match. 132 */ impossible_null_refst_table_ref133 bool impossible_null_ref() const 134 { 135 if (null_rejecting != 0) 136 { 137 for (uint i= 0 ; i < key_parts ; i++) 138 { 139 if ((null_rejecting & 1 << i) && items[i]->is_null()) 140 return TRUE; 141 } 142 } 143 return FALSE; 144 } 145 146 147 /** 148 Check if there are triggered/guarded conditions that might be 149 'switched off' by the subquery code when executing 'Full scan on 150 NULL key' subqueries. 151 152 @return true if there are guarded conditions, false otherwise 153 */ 154 has_guarded_condsst_table_ref155 bool has_guarded_conds() const 156 { 157 DBUG_ASSERT(key_parts == 0 || cond_guards != NULL); 158 159 for (uint i = 0; i < key_parts; i++) 160 { 161 if (cond_guards[i]) 162 return true; 163 } 164 return false; 165 } 166 } TABLE_REF; 167 168 169 struct st_cache_field; 170 class QEP_operation; 171 class Filesort; 172 typedef struct st_position POSITION; 173 class Semijoin_mat_exec; 174 175 /* 176 The structs which holds the join connections and join states 177 */ 178 enum join_type { /* 179 Initial state. Access type has not yet been decided 180 for the table 181 */ 182 JT_UNKNOWN, 183 /* Table has exactly one row */ 184 JT_SYSTEM, 185 /* 186 Table has at most one matching row. Values read 187 from this row can be treated as constants. Example: 188 "WHERE table.pk = 3" 189 */ 190 JT_CONST, 191 /* 192 '=' operator is used on unique index. At most one 193 row is read for each combination of rows from 194 preceding tables 195 */ 196 JT_EQ_REF, 197 /* 198 '=' operator is used on non-unique index 199 */ 200 JT_REF, 201 /* 202 Full table scan. 203 */ 204 JT_ALL, 205 /* 206 Range scan. 207 */ 208 JT_RANGE, 209 /* 210 Like table scan, but scans index leaves instead of 211 the table 212 */ 213 JT_INDEX_SCAN, 214 /* Fulltext index is used */ 215 JT_FT, 216 /* 217 Like ref, but with extra search for NULL values. 218 E.g. used for "WHERE col = ... OR col IS NULL" 219 */ 220 JT_REF_OR_NULL, 221 /* 222 Like eq_ref for subqueries: Replaces subquery with 223 index lookup in unique index 224 */ 225 JT_UNIQUE_SUBQUERY, 226 /* 227 Like unique_subquery but for non-unique index 228 */ 229 JT_INDEX_SUBQUERY, 230 /* 231 Do multiple range scans over one table and combine 232 the results into one. The merge can be used to 233 produce unions and intersections 234 */ 235 JT_INDEX_MERGE}; 236 237 238 /// Holds members common to JOIN_TAB and QEP_TAB. 239 class QEP_shared : public Sql_alloc 240 { 241 public: QEP_shared()242 QEP_shared() : 243 m_join(NULL), 244 m_idx(NO_PLAN_IDX), 245 m_table(NULL), 246 m_position(NULL), 247 m_sj_mat_exec(NULL), 248 m_first_sj_inner(NO_PLAN_IDX), 249 m_last_sj_inner(NO_PLAN_IDX), 250 m_first_inner(NO_PLAN_IDX), 251 m_last_inner(NO_PLAN_IDX), 252 m_first_upper(NO_PLAN_IDX), 253 m_ref(), 254 m_index(0), 255 m_type(JT_UNKNOWN), 256 m_condition(NULL), 257 m_keys(), 258 m_records(0), 259 m_quick(NULL), 260 prefix_tables_map(0), 261 added_tables_map(0), 262 m_ft_func(NULL) 263 {} 264 265 /* 266 Simple getters and setters. They are public. However, this object is 267 protected in QEP_shared_owner, so only that class and its children 268 (JOIN_TAB, QEP_TAB) can access the getters and setters. 269 */ 270 join()271 JOIN *join() const { return m_join; } set_join(JOIN * j)272 void set_join(JOIN *j) { m_join= j; } idx()273 plan_idx idx() const 274 { 275 DBUG_ASSERT(m_idx >= 0); // Index must be valid 276 return m_idx; 277 } set_idx(plan_idx i)278 void set_idx(plan_idx i) 279 { 280 DBUG_ASSERT(m_idx == NO_PLAN_IDX); // Index should not change in lifetime 281 m_idx= i; 282 } table()283 TABLE *table() const { return m_table; } set_table(TABLE * t)284 void set_table(TABLE *t) { m_table= t; } position()285 POSITION *position() const { return m_position; } set_position(POSITION * p)286 void set_position(POSITION *p) { m_position= p; } sj_mat_exec()287 Semijoin_mat_exec *sj_mat_exec() const { return m_sj_mat_exec; } set_sj_mat_exec(Semijoin_mat_exec * s)288 void set_sj_mat_exec(Semijoin_mat_exec *s) { m_sj_mat_exec= s; } first_sj_inner()289 plan_idx first_sj_inner() { return m_first_sj_inner; } last_sj_inner()290 plan_idx last_sj_inner() { return m_last_sj_inner; } first_inner()291 plan_idx first_inner() { return m_first_inner; } set_first_inner(plan_idx i)292 void set_first_inner(plan_idx i) { m_first_inner= i; } set_last_inner(plan_idx i)293 void set_last_inner(plan_idx i) { m_last_inner= i; } set_first_sj_inner(plan_idx i)294 void set_first_sj_inner(plan_idx i) { m_first_sj_inner= i; } set_last_sj_inner(plan_idx i)295 void set_last_sj_inner(plan_idx i) { m_last_sj_inner= i; } set_first_upper(plan_idx i)296 void set_first_upper(plan_idx i) { m_first_upper= i; } last_inner()297 plan_idx last_inner() { return m_last_inner; } first_upper()298 plan_idx first_upper() { return m_first_upper; } ref()299 TABLE_REF &ref() { return m_ref; } index()300 uint index() const { return m_index; } set_index(uint i)301 void set_index(uint i) { m_index= i; } type()302 enum join_type type() const { return m_type; } set_type(enum join_type t)303 void set_type(enum join_type t) { m_type= t; } condition()304 Item *condition() const { return m_condition; } set_condition(Item * c)305 void set_condition(Item *c) { m_condition= c; } keys()306 key_map &keys() { return m_keys; } records()307 ha_rows records() const { return m_records; } set_records(ha_rows r)308 void set_records(ha_rows r) { m_records= r; } quick()309 QUICK_SELECT_I *quick() const { return m_quick; } set_quick(QUICK_SELECT_I * q)310 void set_quick(QUICK_SELECT_I *q) { m_quick= q; } prefix_tables()311 table_map prefix_tables() const { return prefix_tables_map; } added_tables()312 table_map added_tables() const { return added_tables_map; } ft_func()313 Item_func_match *ft_func() const { return m_ft_func; } set_ft_func(Item_func_match * f)314 void set_ft_func(Item_func_match *f) { m_ft_func= f; } 315 316 // More elaborate functions: 317 318 /** 319 Set available tables for a table in a join plan. 320 321 @param prefix_tables_arg: Set of tables available for this plan 322 @param prev_tables_arg: Set of tables available for previous table, used to 323 calculate set of tables added for this table. 324 */ set_prefix_tables(table_map prefix_tables_arg,table_map prev_tables_arg)325 void set_prefix_tables(table_map prefix_tables_arg, table_map prev_tables_arg) 326 { 327 prefix_tables_map= prefix_tables_arg; 328 added_tables_map= prefix_tables_arg & ~prev_tables_arg; 329 } 330 331 /** 332 Add an available set of tables for a table in a join plan. 333 334 @param tables: Set of tables added for this table in plan. 335 */ add_prefix_tables(table_map tables)336 void add_prefix_tables(table_map tables) 337 { prefix_tables_map|= tables; added_tables_map|= tables; } 338 is_first_inner_for_outer_join()339 bool is_first_inner_for_outer_join() const 340 { 341 return m_first_inner == m_idx; 342 } 343 is_inner_table_of_outer_join()344 bool is_inner_table_of_outer_join() const 345 { 346 return m_first_inner != NO_PLAN_IDX; 347 } is_single_inner_of_semi_join()348 bool is_single_inner_of_semi_join() const 349 { 350 return m_first_sj_inner == m_idx && m_last_sj_inner == m_idx; 351 } is_single_inner_of_outer_join()352 bool is_single_inner_of_outer_join() const 353 { 354 return m_first_inner == m_idx && m_last_inner == m_idx; 355 } 356 357 private: 358 359 JOIN *m_join; 360 361 /** 362 Index of structure in array: 363 - NO_PLAN_IDX if before get_best_combination() 364 - index of pointer to this JOIN_TAB, in JOIN::best_ref array 365 - index of this QEP_TAB, in JOIN::qep array. 366 */ 367 plan_idx m_idx; 368 369 /// Corresponding table. Might be an internal temporary one. 370 TABLE *m_table; 371 372 /// Points into best_positions array. Includes cost info. 373 POSITION *m_position; 374 375 /* 376 semijoin-related members. 377 */ 378 379 /** 380 Struct needed for materialization of semi-join. Set for a materialized 381 temporary table, and NULL for all other join_tabs (except when 382 materialization is in progress, @see join_materialize_semijoin()). 383 */ 384 Semijoin_mat_exec *m_sj_mat_exec; 385 386 /** 387 Boundaries of semijoin inner tables around this table. Valid only once 388 final QEP has been chosen. Depending on the strategy, they may define an 389 interval (all tables inside are inner of a semijoin) or 390 not. last_sj_inner is not set for Duplicates Weedout. 391 */ 392 plan_idx m_first_sj_inner, m_last_sj_inner; 393 394 /* 395 outer-join-related members. 396 */ 397 plan_idx m_first_inner; ///< first inner table for including outer join 398 plan_idx m_last_inner; ///< last table table for embedding outer join 399 plan_idx m_first_upper; ///< first inner table for embedding outer join 400 401 /** 402 Used to do index-based look up based on a key value. 403 Used when we read constant tables, in misc optimization (like 404 remove_const()), and in execution. 405 */ 406 TABLE_REF m_ref; 407 408 /// ID of index used for index scan or semijoin LooseScan 409 uint m_index; 410 411 /// Type of chosen access method (scan, etc). 412 enum join_type m_type; 413 414 /** 415 Table condition, ie condition to be evaluated for a row from this table. 416 Notice that the condition may refer to rows from previous tables in the 417 join prefix, as well as outer tables. 418 */ 419 Item *m_condition; 420 421 /** 422 All keys with can be used. 423 Used by add_key_field() (optimization time) and execution of dynamic 424 range (join_init_quick_record()), and EXPLAIN. 425 */ 426 key_map m_keys; 427 428 /** 429 Either #rows in the table or 1 for const table. 430 Used in optimization, and also in execution for FOUND_ROWS(). 431 */ 432 ha_rows m_records; 433 434 /** 435 Non-NULL if quick-select used. 436 Filled in optimization, used in execution to find rows, and in EXPLAIN. 437 */ 438 QUICK_SELECT_I *m_quick; 439 440 /* 441 Maps below are shared because of dynamic range: in execution, it needs to 442 know the prefix tables, to find the possible QUICK methods. 443 */ 444 445 /** 446 The set of all tables available in the join prefix for this table, 447 including the table handled by this JOIN_TAB. 448 */ 449 table_map prefix_tables_map; 450 /** 451 The set of tables added for this table, compared to the previous table 452 in the join prefix. 453 */ 454 table_map added_tables_map; 455 456 /** FT function */ 457 Item_func_match *m_ft_func; 458 }; 459 460 461 /// Owner of a QEP_shared; parent of JOIN_TAB and QEP_TAB. 462 class QEP_shared_owner 463 { 464 public: QEP_shared_owner()465 QEP_shared_owner() : m_qs(NULL) {} 466 467 /// Instructs to share the QEP_shared with another owner share_qs(QEP_shared_owner * other)468 void share_qs(QEP_shared_owner *other) { other->set_qs(m_qs); } set_qs(QEP_shared * q)469 void set_qs(QEP_shared *q) { DBUG_ASSERT(!m_qs); m_qs= q; } 470 471 // Getters/setters forwarding to QEP_shared: 472 join()473 JOIN *join() const { return m_qs->join(); } set_join(JOIN * j)474 void set_join(JOIN *j) { return m_qs->set_join(j); } idx()475 plan_idx idx() const { return m_qs->idx(); } set_idx(plan_idx i)476 void set_idx(plan_idx i) { return m_qs->set_idx(i); } table()477 TABLE *table() const { return m_qs->table(); } position()478 POSITION *position() const { return m_qs->position(); } set_position(POSITION * p)479 void set_position(POSITION *p) { return m_qs->set_position(p); } sj_mat_exec()480 Semijoin_mat_exec *sj_mat_exec() const { return m_qs->sj_mat_exec(); } set_sj_mat_exec(Semijoin_mat_exec * s)481 void set_sj_mat_exec(Semijoin_mat_exec *s) { return m_qs->set_sj_mat_exec(s); } first_sj_inner()482 plan_idx first_sj_inner() const { return m_qs->first_sj_inner(); } last_sj_inner()483 plan_idx last_sj_inner() const { return m_qs->last_sj_inner(); } first_inner()484 plan_idx first_inner() const { return m_qs->first_inner(); } last_inner()485 plan_idx last_inner() const { return m_qs->last_inner(); } first_upper()486 plan_idx first_upper() const { return m_qs->first_upper(); } set_first_inner(plan_idx i)487 void set_first_inner(plan_idx i) { return m_qs->set_first_inner(i); } set_last_inner(plan_idx i)488 void set_last_inner(plan_idx i) { return m_qs->set_last_inner(i); } set_first_sj_inner(plan_idx i)489 void set_first_sj_inner(plan_idx i) { return m_qs->set_first_sj_inner(i); } set_last_sj_inner(plan_idx i)490 void set_last_sj_inner(plan_idx i) { return m_qs->set_last_sj_inner(i); } set_first_upper(plan_idx i)491 void set_first_upper(plan_idx i) { return m_qs->set_first_upper(i); } ref()492 TABLE_REF &ref() const { return m_qs->ref(); } index()493 uint index() const { return m_qs->index(); } set_index(uint i)494 void set_index(uint i) { return m_qs->set_index(i); } type()495 enum join_type type() const { return m_qs->type(); } set_type(enum join_type t)496 void set_type(enum join_type t) { return m_qs->set_type(t); } condition()497 Item *condition() const { return m_qs->condition(); } set_condition(Item * to)498 void set_condition(Item *to) { return m_qs->set_condition(to); } keys()499 key_map &keys() { return m_qs->keys(); } records()500 ha_rows records() const { return m_qs->records(); } set_records(ha_rows r)501 void set_records(ha_rows r) { return m_qs->set_records(r); } quick()502 QUICK_SELECT_I *quick() const { return m_qs->quick(); } set_quick(QUICK_SELECT_I * q)503 void set_quick(QUICK_SELECT_I *q) { return m_qs->set_quick(q); } prefix_tables()504 table_map prefix_tables() const { return m_qs->prefix_tables(); } added_tables()505 table_map added_tables() const { return m_qs->added_tables(); } ft_func()506 Item_func_match *ft_func() const { return m_qs->ft_func(); } set_ft_func(Item_func_match * f)507 void set_ft_func(Item_func_match *f) { return m_qs->set_ft_func(f); } set_prefix_tables(table_map prefix_tables,table_map prev_tables)508 void set_prefix_tables(table_map prefix_tables, table_map prev_tables) 509 { return m_qs->set_prefix_tables(prefix_tables, prev_tables); } add_prefix_tables(table_map tables)510 void add_prefix_tables(table_map tables) 511 { return m_qs->add_prefix_tables(tables); } is_single_inner_of_semi_join()512 bool is_single_inner_of_semi_join() const 513 { return m_qs->is_single_inner_of_semi_join(); } is_inner_table_of_outer_join()514 bool is_inner_table_of_outer_join() const 515 { return m_qs->is_inner_table_of_outer_join(); } is_first_inner_for_outer_join()516 bool is_first_inner_for_outer_join() const 517 { return m_qs->is_first_inner_for_outer_join(); } is_single_inner_for_outer_join()518 bool is_single_inner_for_outer_join() const 519 { return m_qs->is_single_inner_of_outer_join(); } 520 has_guarded_conds()521 bool has_guarded_conds() const 522 { return ref().has_guarded_conds(); } 523 bool and_with_condition(Item *tmp_cond); 524 525 void qs_cleanup(); 526 527 protected: 528 QEP_shared *m_qs; // qs stands for Qep_Shared 529 }; 530 531 #endif // SQL_OPT_EXEC_SHARED_INCLUDED 532