1 /* 2 Copyright (c) 2000, 2010, 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 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 St, Fifth Floor, Boston, MA 02110-1335 USA */ 16 17 18 /* classes to use when handling where clause */ 19 20 #ifndef _opt_range_h 21 #define _opt_range_h 22 23 #ifdef USE_PRAGMA_INTERFACE 24 #pragma interface /* gcc class implementation */ 25 #endif 26 27 #include "records.h" /* READ_RECORD */ 28 #include "queues.h" /* QUEUE */ 29 #include "filesort.h" /* SORT_INFO */ 30 31 /* 32 It is necessary to include set_var.h instead of item.h because there 33 are dependencies on include order for set_var.h and item.h. This 34 will be resolved later. 35 */ 36 #include "sql_class.h" // set_var.h: THD 37 #include "set_var.h" /* Item */ 38 39 class JOIN; 40 class Item_sum; 41 42 struct KEY_PART { 43 uint16 key,part; 44 /* See KEY_PART_INFO for meaning of the next two: */ 45 uint16 store_length, length; 46 uint8 null_bit; 47 /* 48 Keypart flags (0 when this structure is used by partition pruning code 49 for fake partitioning index description) 50 */ 51 uint8 flag; 52 Field *field; 53 Field::imagetype image_type; 54 }; 55 56 57 class RANGE_OPT_PARAM; 58 /* 59 A construction block of the SEL_ARG-graph. 60 61 The following description only covers graphs of SEL_ARG objects with 62 sel_arg->type==KEY_RANGE: 63 64 One SEL_ARG object represents an "elementary interval" in form 65 66 min_value <=? table.keypartX <=? max_value 67 68 The interval is a non-empty interval of any kind: with[out] minimum/maximum 69 bound, [half]open/closed, single-point interval, etc. 70 71 1. SEL_ARG GRAPH STRUCTURE 72 73 SEL_ARG objects are linked together in a graph. The meaning of the graph 74 is better demostrated by an example: 75 76 tree->keys[i] 77 | 78 | $ $ 79 | part=1 $ part=2 $ part=3 80 | $ $ 81 | +-------+ $ +-------+ $ +--------+ 82 | | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 | 83 | +-------+ $ +-------+ $ +--------+ 84 | | $ $ | 85 | | $ $ +--------+ 86 | | $ $ | kp3=12 | 87 | | $ $ +--------+ 88 | +-------+ $ $ 89 \->| kp1=2 |--$--------------$-+ 90 +-------+ $ $ | +--------+ 91 | $ $ ==>| kp3=11 | 92 +-------+ $ $ | +--------+ 93 | kp1=3 |--$--------------$-+ | 94 +-------+ $ $ +--------+ 95 | $ $ | kp3=14 | 96 ... $ $ +--------+ 97 98 The entire graph is partitioned into "interval lists". 99 100 An interval list is a sequence of ordered disjoint intervals over the same 101 key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally, 102 all intervals in the list form an RB-tree, linked via left/right/parent 103 pointers. The RB-tree root SEL_ARG object will be further called "root of the 104 interval list". 105 106 In the example pic, there are 4 interval lists: 107 "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13". 108 The vertical lines represent SEL_ARG::next/prev pointers. 109 110 In an interval list, each member X may have SEL_ARG::next_key_part pointer 111 pointing to the root of another interval list Y. The pointed interval list 112 must cover a key part with greater number (i.e. Y->part > X->part). 113 114 In the example pic, the next_key_part pointers are represented by 115 horisontal lines. 116 117 2. SEL_ARG GRAPH SEMANTICS 118 119 It represents a condition in a special form (we don't have a name for it ATM) 120 The SEL_ARG::next/prev is "OR", and next_key_part is "AND". 121 122 For example, the picture represents the condition in form: 123 (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR 124 (kp1=2 AND (kp3=11 OR kp3=14)) OR 125 (kp1=3 AND (kp3=11 OR kp3=14)) 126 127 128 3. SEL_ARG GRAPH USE 129 130 Use get_mm_tree() to construct SEL_ARG graph from WHERE condition. 131 Then walk the SEL_ARG graph and get a list of dijsoint ordered key 132 intervals (i.e. intervals in form 133 134 (constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K) 135 136 Those intervals can be used to access the index. The uses are in: 137 - check_quick_select() - Walk the SEL_ARG graph and find an estimate of 138 how many table records are contained within all 139 intervals. 140 - get_quick_select() - Walk the SEL_ARG, materialize the key intervals, 141 and create QUICK_RANGE_SELECT object that will 142 read records within these intervals. 143 144 4. SPACE COMPLEXITY NOTES 145 146 SEL_ARG graph is a representation of an ordered disjoint sequence of 147 intervals over the ordered set of index tuple values. 148 149 For multi-part keys, one can construct a WHERE expression such that its 150 list of intervals will be of combinatorial size. Here is an example: 151 152 (keypart1 IN (1,2, ..., n1)) AND 153 (keypart2 IN (1,2, ..., n2)) AND 154 (keypart3 IN (1,2, ..., n3)) 155 156 For this WHERE clause the list of intervals will have n1*n2*n3 intervals 157 of form 158 159 (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i} 160 161 SEL_ARG graph structure aims to reduce the amount of required space by 162 "sharing" the elementary intervals when possible (the pic at the 163 beginning of this comment has examples of such sharing). The sharing may 164 prevent combinatorial blowup: 165 166 There are WHERE clauses that have combinatorial-size interval lists but 167 will be represented by a compact SEL_ARG graph. 168 Example: 169 (keypartN IN (1,2, ..., n1)) AND 170 ... 171 (keypart2 IN (1,2, ..., n2)) AND 172 (keypart1 IN (1,2, ..., n3)) 173 174 but not in all cases: 175 176 - There are WHERE clauses that do have a compact SEL_ARG-graph 177 representation but get_mm_tree() and its callees will construct a 178 graph of combinatorial size. 179 Example: 180 (keypart1 IN (1,2, ..., n1)) AND 181 (keypart2 IN (1,2, ..., n2)) AND 182 ... 183 (keypartN IN (1,2, ..., n3)) 184 185 - There are WHERE clauses for which the minimal possible SEL_ARG graph 186 representation will have combinatorial size. 187 Example: 188 By induction: Let's take any interval on some keypart in the middle: 189 190 kp15=c0 191 192 Then let's AND it with this interval 'structure' from preceding and 193 following keyparts: 194 195 (kp14=c1 AND kp16=c3) OR keypart14=c2) (*) 196 197 We will obtain this SEL_ARG graph: 198 199 kp14 $ kp15 $ kp16 200 $ $ 201 +---------+ $ +---------+ $ +---------+ 202 | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 | 203 +---------+ $ +---------+ $ +---------+ 204 | $ $ 205 +---------+ $ +---------+ $ 206 | kp14=c2 |--$-->| kp15=c0 | $ 207 +---------+ $ +---------+ $ 208 $ $ 209 210 Note that we had to duplicate "kp15=c0" and there was no way to avoid 211 that. 212 The induction step: AND the obtained expression with another "wrapping" 213 expression like (*). 214 When the process ends because of the limit on max. number of keyparts 215 we'll have: 216 217 WHERE clause length is O(3*#max_keyparts) 218 SEL_ARG graph size is O(2^(#max_keyparts/2)) 219 220 (it is also possible to construct a case where instead of 2 in 2^n we 221 have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31 222 nodes) 223 224 We avoid consuming too much memory by setting a limit on the number of 225 SEL_ARG object we can construct during one range analysis invocation. 226 */ 227 228 class SEL_ARG :public Sql_alloc 229 { 230 static int sel_cmp(Field *field, uchar *a, uchar *b, uint8 a_flag, 231 uint8 b_flag); 232 public: 233 uint8 min_flag,max_flag,maybe_flag; 234 uint8 part; // Which key part 235 uint8 maybe_null; 236 /* 237 The ordinal number the least significant component encountered in 238 the ranges of the SEL_ARG tree (the first component has number 1) 239 */ 240 uint16 max_part_no; 241 /* 242 Number of children of this element in the RB-tree, plus 1 for this 243 element itself. 244 */ 245 uint32 elements; 246 /* 247 Valid only for elements which are RB-tree roots: Number of times this 248 RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by 249 SEL_TREE::keys[i] or by a temporary SEL_ARG* variable) 250 */ 251 ulong use_count; 252 253 Field *field; 254 uchar *min_value,*max_value; // Pointer to range 255 256 /* 257 eq_tree() requires that left == right == 0 if the type is MAYBE_KEY. 258 */ 259 SEL_ARG *left,*right; /* R-B tree children */ 260 SEL_ARG *next,*prev; /* Links for bi-directional interval list */ 261 SEL_ARG *parent; /* R-B tree parent */ 262 SEL_ARG *next_key_part; 263 enum leaf_color { BLACK,RED } color; 264 enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type; 265 266 enum { MAX_SEL_ARGS = 16000 }; 267 SEL_ARG()268 SEL_ARG() {} 269 SEL_ARG(SEL_ARG &); 270 SEL_ARG(Field *,const uchar *, const uchar *); 271 SEL_ARG(Field *field, uint8 part, uchar *min_value, uchar *max_value, 272 uint8 min_flag, uint8 max_flag, uint8 maybe_flag); SEL_ARG(enum Type type_arg)273 SEL_ARG(enum Type type_arg) 274 :min_flag(0), max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/, 275 elements(1),use_count(1),left(0),right(0), 276 next_key_part(0), color(BLACK), type(type_arg) 277 {} 278 /** 279 returns true if a range predicate is equal. Use all_same() 280 to check for equality of all the predicates on this keypart. 281 */ is_same(const SEL_ARG * arg)282 inline bool is_same(const SEL_ARG *arg) const 283 { 284 if (type != arg->type || part != arg->part) 285 return false; 286 if (type != KEY_RANGE) 287 return true; 288 return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0; 289 } 290 /** 291 returns true if all the predicates in the keypart tree are equal 292 */ all_same(const SEL_ARG * arg)293 bool all_same(const SEL_ARG *arg) const 294 { 295 if (type != arg->type || part != arg->part) 296 return false; 297 if (type != KEY_RANGE) 298 return true; 299 if (arg == this) 300 return true; 301 const SEL_ARG *cmp_arg= arg->first(); 302 const SEL_ARG *cur_arg= first(); 303 for (; cur_arg && cmp_arg && cur_arg->is_same(cmp_arg); 304 cur_arg= cur_arg->next, cmp_arg= cmp_arg->next) ; 305 if (cur_arg || cmp_arg) 306 return false; 307 return true; 308 } merge_flags(SEL_ARG * arg)309 inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; } maybe_smaller()310 inline void maybe_smaller() { maybe_flag=1; } 311 /* Return true iff it's a single-point null interval */ is_null_interval()312 inline bool is_null_interval() { return maybe_null && max_value[0] == 1; } cmp_min_to_min(const SEL_ARG * arg)313 inline int cmp_min_to_min(const SEL_ARG* arg) const 314 { 315 return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag); 316 } cmp_min_to_max(const SEL_ARG * arg)317 inline int cmp_min_to_max(const SEL_ARG* arg) const 318 { 319 return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag); 320 } cmp_max_to_max(const SEL_ARG * arg)321 inline int cmp_max_to_max(const SEL_ARG* arg) const 322 { 323 return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag); 324 } cmp_max_to_min(const SEL_ARG * arg)325 inline int cmp_max_to_min(const SEL_ARG* arg) const 326 { 327 return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag); 328 } clone_and(THD * thd,SEL_ARG * arg)329 SEL_ARG *clone_and(THD *thd, SEL_ARG* arg) 330 { // Get overlapping range 331 uchar *new_min,*new_max; 332 uint8 flag_min,flag_max; 333 if (cmp_min_to_min(arg) >= 0) 334 { 335 new_min=min_value; flag_min=min_flag; 336 } 337 else 338 { 339 new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */ 340 } 341 if (cmp_max_to_max(arg) <= 0) 342 { 343 new_max=max_value; flag_max=max_flag; 344 } 345 else 346 { 347 new_max=arg->max_value; flag_max=arg->max_flag; 348 } 349 return new (thd->mem_root) SEL_ARG(field, part, new_min, new_max, flag_min, 350 flag_max, 351 MY_TEST(maybe_flag && arg->maybe_flag)); 352 } clone_first(SEL_ARG * arg)353 SEL_ARG *clone_first(SEL_ARG *arg) 354 { // min <= X < arg->min 355 return new SEL_ARG(field,part, min_value, arg->min_value, 356 min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX, 357 maybe_flag | arg->maybe_flag); 358 } clone_last(SEL_ARG * arg)359 SEL_ARG *clone_last(SEL_ARG *arg) 360 { // min <= X <= key_max 361 return new SEL_ARG(field, part, min_value, arg->max_value, 362 min_flag, arg->max_flag, maybe_flag | arg->maybe_flag); 363 } 364 SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next); 365 copy_min(SEL_ARG * arg)366 bool copy_min(SEL_ARG* arg) 367 { // Get overlapping range 368 if (cmp_min_to_min(arg) > 0) 369 { 370 min_value=arg->min_value; min_flag=arg->min_flag; 371 if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) == 372 (NO_MAX_RANGE | NO_MIN_RANGE)) 373 return 1; // Full range 374 } 375 maybe_flag|=arg->maybe_flag; 376 return 0; 377 } copy_max(SEL_ARG * arg)378 bool copy_max(SEL_ARG* arg) 379 { // Get overlapping range 380 if (cmp_max_to_max(arg) <= 0) 381 { 382 max_value=arg->max_value; max_flag=arg->max_flag; 383 if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) == 384 (NO_MAX_RANGE | NO_MIN_RANGE)) 385 return 1; // Full range 386 } 387 maybe_flag|=arg->maybe_flag; 388 return 0; 389 } 390 copy_min_to_min(SEL_ARG * arg)391 void copy_min_to_min(SEL_ARG *arg) 392 { 393 min_value=arg->min_value; min_flag=arg->min_flag; 394 } copy_min_to_max(SEL_ARG * arg)395 void copy_min_to_max(SEL_ARG *arg) 396 { 397 max_value=arg->min_value; 398 max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX; 399 } copy_max_to_min(SEL_ARG * arg)400 void copy_max_to_min(SEL_ARG *arg) 401 { 402 min_value=arg->max_value; 403 min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN; 404 } 405 /* returns a number of keypart values (0 or 1) appended to the key buffer */ store_min(uint length,uchar ** min_key,uint min_key_flag)406 int store_min(uint length, uchar **min_key,uint min_key_flag) 407 { 408 /* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */ 409 if ((min_flag & GEOM_FLAG) || 410 (!(min_flag & NO_MIN_RANGE) && 411 !(min_key_flag & (NO_MIN_RANGE | NEAR_MIN)))) 412 { 413 if (maybe_null && *min_value) 414 { 415 **min_key=1; 416 bzero(*min_key+1,length-1); 417 } 418 else 419 memcpy(*min_key,min_value,length); 420 (*min_key)+= length; 421 return 1; 422 } 423 return 0; 424 } 425 /* returns a number of keypart values (0 or 1) appended to the key buffer */ store_max(uint length,uchar ** max_key,uint max_key_flag)426 int store_max(uint length, uchar **max_key, uint max_key_flag) 427 { 428 if (!(max_flag & NO_MAX_RANGE) && 429 !(max_key_flag & (NO_MAX_RANGE | NEAR_MAX))) 430 { 431 if (maybe_null && *max_value) 432 { 433 **max_key=1; 434 bzero(*max_key+1,length-1); 435 } 436 else 437 memcpy(*max_key,max_value,length); 438 (*max_key)+= length; 439 return 1; 440 } 441 return 0; 442 } 443 444 /* 445 Returns a number of keypart values appended to the key buffer 446 for min key and max key. This function is used by both Range 447 Analysis and Partition pruning. For partition pruning we have 448 to ensure that we don't store also subpartition fields. Thus 449 we have to stop at the last partition part and not step into 450 the subpartition fields. For Range Analysis we set last_part 451 to MAX_KEY which we should never reach. 452 */ store_min_key(KEY_PART * key,uchar ** range_key,uint * range_key_flag,uint last_part)453 int store_min_key(KEY_PART *key, 454 uchar **range_key, 455 uint *range_key_flag, 456 uint last_part) 457 { 458 SEL_ARG *key_tree= first(); 459 uint res= key_tree->store_min(key[key_tree->part].store_length, 460 range_key, *range_key_flag); 461 *range_key_flag|= key_tree->min_flag; 462 if (key_tree->next_key_part && 463 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && 464 key_tree->part != last_part && 465 key_tree->next_key_part->part == key_tree->part+1 && 466 !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN))) 467 res+= key_tree->next_key_part->store_min_key(key, 468 range_key, 469 range_key_flag, 470 last_part); 471 return res; 472 } 473 474 /* returns a number of keypart values appended to the key buffer */ store_max_key(KEY_PART * key,uchar ** range_key,uint * range_key_flag,uint last_part)475 int store_max_key(KEY_PART *key, 476 uchar **range_key, 477 uint *range_key_flag, 478 uint last_part) 479 { 480 SEL_ARG *key_tree= last(); 481 uint res=key_tree->store_max(key[key_tree->part].store_length, 482 range_key, *range_key_flag); 483 (*range_key_flag)|= key_tree->max_flag; 484 if (key_tree->next_key_part && 485 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE && 486 key_tree->part != last_part && 487 key_tree->next_key_part->part == key_tree->part+1 && 488 !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX))) 489 res+= key_tree->next_key_part->store_max_key(key, 490 range_key, 491 range_key_flag, 492 last_part); 493 return res; 494 } 495 496 SEL_ARG *insert(SEL_ARG *key); 497 SEL_ARG *tree_delete(SEL_ARG *key); 498 SEL_ARG *find_range(SEL_ARG *key); 499 SEL_ARG *rb_insert(SEL_ARG *leaf); 500 friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par); 501 #ifdef EXTRA_DEBUG 502 friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent); 503 void test_use_count(SEL_ARG *root); 504 #endif 505 SEL_ARG *first(); 506 const SEL_ARG *first() const; 507 SEL_ARG *last(); 508 void make_root(); simple_key()509 inline bool simple_key() 510 { 511 return !next_key_part && elements == 1; 512 } increment_use_count(long count)513 void increment_use_count(long count) 514 { 515 if (next_key_part) 516 { 517 next_key_part->use_count+=count; 518 count*= (next_key_part->use_count-count); 519 for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next) 520 if (pos->next_key_part) 521 pos->increment_use_count(count); 522 } 523 } incr_refs()524 void incr_refs() 525 { 526 increment_use_count(1); 527 use_count++; 528 } incr_refs_all()529 void incr_refs_all() 530 { 531 for (SEL_ARG *pos=first(); pos ; pos=pos->next) 532 { 533 pos->increment_use_count(1); 534 } 535 use_count++; 536 } free_tree()537 void free_tree() 538 { 539 for (SEL_ARG *pos=first(); pos ; pos=pos->next) 540 if (pos->next_key_part) 541 { 542 pos->next_key_part->use_count--; 543 pos->next_key_part->free_tree(); 544 } 545 } 546 parent_ptr()547 inline SEL_ARG **parent_ptr() 548 { 549 return parent->left == this ? &parent->left : &parent->right; 550 } 551 552 553 /* 554 Check if this SEL_ARG object represents a single-point interval 555 556 SYNOPSIS 557 is_singlepoint() 558 559 DESCRIPTION 560 Check if this SEL_ARG object (not tree) represents a single-point 561 interval, i.e. if it represents a "keypart = const" or 562 "keypart IS NULL". 563 564 RETURN 565 TRUE This SEL_ARG object represents a singlepoint interval 566 FALSE Otherwise 567 */ 568 is_singlepoint()569 bool is_singlepoint() 570 { 571 /* 572 Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field) 573 flags, and the same for right edge. 574 */ 575 if (min_flag || max_flag) 576 return FALSE; 577 uchar *min_val= min_value; 578 uchar *max_val= max_value; 579 580 if (maybe_null) 581 { 582 /* First byte is a NULL value indicator */ 583 if (*min_val != *max_val) 584 return FALSE; 585 586 if (*min_val) 587 return TRUE; /* This "x IS NULL" */ 588 min_val++; 589 max_val++; 590 } 591 return !field->key_cmp(min_val, max_val); 592 } 593 SEL_ARG *clone_tree(RANGE_OPT_PARAM *param); 594 }; 595 596 597 class SEL_ARG_IMPOSSIBLE: public SEL_ARG 598 { 599 public: SEL_ARG_IMPOSSIBLE(Field * field)600 SEL_ARG_IMPOSSIBLE(Field *field) 601 :SEL_ARG(field, 0, 0) 602 { 603 type= SEL_ARG::IMPOSSIBLE; 604 } 605 }; 606 607 608 class RANGE_OPT_PARAM 609 { 610 public: 611 THD *thd; /* Current thread handle */ 612 TABLE *table; /* Table being analyzed */ 613 table_map prev_tables; 614 table_map read_tables; 615 table_map current_table; /* Bit of the table being analyzed */ 616 617 /* Array of parts of all keys for which range analysis is performed */ 618 KEY_PART *key_parts; 619 KEY_PART *key_parts_end; 620 MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */ 621 MEM_ROOT *old_root; /* Memory that will last until the query end */ 622 /* 623 Number of indexes used in range analysis (In SEL_TREE::keys only first 624 #keys elements are not empty) 625 */ 626 uint keys; 627 628 /* 629 If true, the index descriptions describe real indexes (and it is ok to 630 call field->optimize_range(real_keynr[...], ...). 631 Otherwise index description describes fake indexes. 632 */ 633 bool using_real_indexes; 634 635 /* 636 Aggressively remove "scans" that do not have conditions on first 637 keyparts. Such scans are usable when doing partition pruning but not 638 regular range optimization. 639 */ 640 bool remove_jump_scans; 641 642 /* 643 TRUE <=> Range analyzer should remove parts of condition that are found 644 to be always FALSE. 645 */ 646 bool remove_false_where_parts; 647 648 /* 649 used_key_no -> table_key_no translation table. Only makes sense if 650 using_real_indexes==TRUE 651 */ 652 uint real_keynr[MAX_KEY]; 653 654 /* 655 Used to store 'current key tuples', in both range analysis and 656 partitioning (list) analysis 657 */ 658 uchar *min_key; 659 uchar *max_key; 660 661 /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */ 662 uint alloced_sel_args; 663 664 bool force_default_mrr; 665 KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */ 666 statement_should_be_aborted()667 bool statement_should_be_aborted() const 668 { 669 return 670 thd->killed || 671 thd->is_fatal_error || 672 thd->is_error() || 673 alloced_sel_args > SEL_ARG::MAX_SEL_ARGS; 674 } 675 }; 676 677 678 class Explain_quick_select; 679 /* 680 A "MIN_TUPLE < tbl.key_tuple < MAX_TUPLE" interval. 681 682 One of endpoints may be absent. 'flags' member has flags which tell whether 683 the endpoints are '<' or '<='. 684 */ 685 class QUICK_RANGE :public Sql_alloc { 686 public: 687 uchar *min_key,*max_key; 688 uint16 min_length,max_length,flag; 689 key_part_map min_keypart_map, // bitmap of used keyparts in min_key 690 max_keypart_map; // bitmap of used keyparts in max_key 691 #ifdef HAVE_valgrind 692 uint16 dummy; /* Avoid warnings on 'flag' */ 693 #endif 694 QUICK_RANGE(); /* Full range */ QUICK_RANGE(THD * thd,const uchar * min_key_arg,uint min_length_arg,key_part_map min_keypart_map_arg,const uchar * max_key_arg,uint max_length_arg,key_part_map max_keypart_map_arg,uint flag_arg)695 QUICK_RANGE(THD *thd, const uchar *min_key_arg, uint min_length_arg, 696 key_part_map min_keypart_map_arg, 697 const uchar *max_key_arg, uint max_length_arg, 698 key_part_map max_keypart_map_arg, 699 uint flag_arg) 700 : min_key((uchar*) thd->memdup(min_key_arg, min_length_arg + 1)), 701 max_key((uchar*) thd->memdup(max_key_arg, max_length_arg + 1)), 702 min_length((uint16) min_length_arg), 703 max_length((uint16) max_length_arg), 704 flag((uint16) flag_arg), 705 min_keypart_map(min_keypart_map_arg), 706 max_keypart_map(max_keypart_map_arg) 707 { 708 #ifdef HAVE_valgrind 709 dummy=0; 710 #endif 711 } 712 713 /** 714 Initalizes a key_range object for communication with storage engine. 715 716 This function facilitates communication with the Storage Engine API by 717 translating the minimum endpoint of the interval represented by this 718 QUICK_RANGE into an index range endpoint specifier for the engine. 719 720 @param Pointer to an uninitialized key_range C struct. 721 722 @param prefix_length The length of the search key prefix to be used for 723 lookup. 724 725 @param keypart_map A set (bitmap) of keyparts to be used. 726 */ make_min_endpoint(key_range * kr,uint prefix_length,key_part_map keypart_map)727 void make_min_endpoint(key_range *kr, uint prefix_length, 728 key_part_map keypart_map) { 729 make_min_endpoint(kr); 730 kr->length= MY_MIN(kr->length, prefix_length); 731 kr->keypart_map&= keypart_map; 732 } 733 734 /** 735 Initalizes a key_range object for communication with storage engine. 736 737 This function facilitates communication with the Storage Engine API by 738 translating the minimum endpoint of the interval represented by this 739 QUICK_RANGE into an index range endpoint specifier for the engine. 740 741 @param Pointer to an uninitialized key_range C struct. 742 */ make_min_endpoint(key_range * kr)743 void make_min_endpoint(key_range *kr) { 744 kr->key= (const uchar*)min_key; 745 kr->length= min_length; 746 kr->keypart_map= min_keypart_map; 747 kr->flag= ((flag & NEAR_MIN) ? HA_READ_AFTER_KEY : 748 (flag & EQ_RANGE) ? HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT); 749 } 750 751 /** 752 Initalizes a key_range object for communication with storage engine. 753 754 This function facilitates communication with the Storage Engine API by 755 translating the maximum endpoint of the interval represented by this 756 QUICK_RANGE into an index range endpoint specifier for the engine. 757 758 @param Pointer to an uninitialized key_range C struct. 759 760 @param prefix_length The length of the search key prefix to be used for 761 lookup. 762 763 @param keypart_map A set (bitmap) of keyparts to be used. 764 */ make_max_endpoint(key_range * kr,uint prefix_length,key_part_map keypart_map)765 void make_max_endpoint(key_range *kr, uint prefix_length, 766 key_part_map keypart_map) { 767 make_max_endpoint(kr); 768 kr->length= MY_MIN(kr->length, prefix_length); 769 kr->keypart_map&= keypart_map; 770 } 771 772 /** 773 Initalizes a key_range object for communication with storage engine. 774 775 This function facilitates communication with the Storage Engine API by 776 translating the maximum endpoint of the interval represented by this 777 QUICK_RANGE into an index range endpoint specifier for the engine. 778 779 @param Pointer to an uninitialized key_range C struct. 780 */ make_max_endpoint(key_range * kr)781 void make_max_endpoint(key_range *kr) { 782 kr->key= (const uchar*)max_key; 783 kr->length= max_length; 784 kr->keypart_map= max_keypart_map; 785 /* 786 We use READ_AFTER_KEY here because if we are reading on a key 787 prefix we want to find all keys with this prefix 788 */ 789 kr->flag= (flag & NEAR_MAX ? HA_READ_BEFORE_KEY : HA_READ_AFTER_KEY); 790 } 791 }; 792 793 794 /* 795 Quick select interface. 796 This class is a parent for all QUICK_*_SELECT and FT_SELECT classes. 797 798 The usage scenario is as follows: 799 1. Create quick select 800 quick= new QUICK_XXX_SELECT(...); 801 802 2. Perform lightweight initialization. This can be done in 2 ways: 803 2.a: Regular initialization 804 if (quick->init()) 805 { 806 //the only valid action after failed init() call is delete 807 delete quick; 808 } 809 2.b: Special initialization for quick selects merged by QUICK_ROR_*_SELECT 810 if (quick->init_ror_merged_scan()) 811 delete quick; 812 813 3. Perform zero, one, or more scans. 814 while (...) 815 { 816 // initialize quick select for scan. This may allocate 817 // buffers and/or prefetch rows. 818 if (quick->reset()) 819 { 820 //the only valid action after failed reset() call is delete 821 delete quick; 822 //abort query 823 } 824 825 // perform the scan 826 do 827 { 828 res= quick->get_next(); 829 } while (res && ...) 830 } 831 832 4. Delete the select: 833 delete quick; 834 835 NOTE 836 quick select doesn't use Sql_alloc/MEM_ROOT allocation because "range 837 checked for each record" functionality may create/destroy 838 O(#records_in_some_table) quick selects during query execution. 839 */ 840 841 class QUICK_SELECT_I 842 { 843 public: 844 ha_rows records; /* estimate of # of records to be retrieved */ 845 double read_time; /* time to perform this retrieval */ 846 TABLE *head; 847 /* 848 Index this quick select uses, or MAX_KEY for quick selects 849 that use several indexes 850 */ 851 uint index; 852 853 /* 854 Total length of first used_key_parts parts of the key. 855 Applicable if index!= MAX_KEY. 856 */ 857 uint max_used_key_length; 858 859 /* 860 Max. number of (first) key parts this quick select uses for retrieval. 861 eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2. 862 Applicable if index!= MAX_KEY. 863 864 For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts. 865 */ 866 uint used_key_parts; 867 868 QUICK_SELECT_I(); ~QUICK_SELECT_I()869 virtual ~QUICK_SELECT_I(){}; 870 871 /* 872 Do post-constructor initialization. 873 SYNOPSIS 874 init() 875 876 init() performs initializations that should have been in constructor if 877 it was possible to return errors from constructors. The join optimizer may 878 create and then delete quick selects without retrieving any rows so init() 879 must not contain any IO or CPU intensive code. 880 881 If init() call fails the only valid action is to delete this quick select, 882 reset() and get_next() must not be called. 883 884 RETURN 885 0 OK 886 other Error code 887 */ 888 virtual int init() = 0; 889 890 /* 891 Initialize quick select for row retrieval. 892 SYNOPSIS 893 reset() 894 895 reset() should be called when it is certain that row retrieval will be 896 necessary. This call may do heavyweight initialization like buffering first 897 N records etc. If reset() call fails get_next() must not be called. 898 Note that reset() may be called several times if 899 * the quick select is executed in a subselect 900 * a JOIN buffer is used 901 902 RETURN 903 0 OK 904 other Error code 905 */ 906 virtual int reset(void) = 0; 907 908 virtual int get_next() = 0; /* get next record to retrieve */ 909 910 /* Range end should be called when we have looped over the whole index */ range_end()911 virtual void range_end() {} 912 913 virtual bool reverse_sorted() = 0; unique_key_range()914 virtual bool unique_key_range() { return false; } 915 916 /* 917 Request that this quick select produces sorted output. Not all quick 918 selects can do it, the caller is responsible for calling this function 919 only for those quick selects that can. 920 */ 921 virtual void need_sorted_output() = 0; 922 enum { 923 QS_TYPE_RANGE = 0, 924 QS_TYPE_INDEX_INTERSECT = 1, 925 QS_TYPE_INDEX_MERGE = 2, 926 QS_TYPE_RANGE_DESC = 3, 927 QS_TYPE_FULLTEXT = 4, 928 QS_TYPE_ROR_INTERSECT = 5, 929 QS_TYPE_ROR_UNION = 6, 930 QS_TYPE_GROUP_MIN_MAX = 7 931 }; 932 933 /* Get type of this quick select - one of the QS_TYPE_* values */ 934 virtual int get_type() = 0; 935 936 /* 937 Initialize this quick select as a merged scan inside a ROR-union or a ROR- 938 intersection scan. The caller must not additionally call init() if this 939 function is called. 940 SYNOPSIS 941 init_ror_merged_scan() 942 reuse_handler If true, the quick select may use table->handler, 943 otherwise it must create and use a separate handler 944 object. 945 RETURN 946 0 Ok 947 other Error 948 */ init_ror_merged_scan(bool reuse_handler,MEM_ROOT * alloc)949 virtual int init_ror_merged_scan(bool reuse_handler, MEM_ROOT *alloc) 950 { DBUG_ASSERT(0); return 1; } 951 952 /* 953 Save ROWID of last retrieved row in file->ref. This used in ROR-merging. 954 */ save_last_pos()955 virtual void save_last_pos(){}; 956 957 void add_key_and_length(String *key_names, 958 String *used_lengths, 959 bool *first); 960 961 /* 962 Append comma-separated list of keys this quick select uses to key_names; 963 append comma-separated list of corresponding used lengths to used_lengths. 964 This is used by select_describe. 965 */ 966 virtual void add_keys_and_lengths(String *key_names, 967 String *used_lengths)=0; 968 969 void add_key_name(String *str, bool *first); 970 971 /* Save information about quick select's query plan */ 972 virtual Explain_quick_select* get_explain(MEM_ROOT *alloc)= 0; 973 974 /* 975 Return 1 if any index used by this quick select 976 uses field which is marked in passed bitmap. 977 */ 978 virtual bool is_keys_used(const MY_BITMAP *fields); 979 980 /** 981 Simple sanity check that the quick select has been set up 982 correctly. Function is overridden by quick selects that merge 983 indices. 984 */ is_valid()985 virtual bool is_valid() { return index != MAX_KEY; }; 986 987 /* 988 rowid of last row retrieved by this quick select. This is used only when 989 doing ROR-index_merge selects 990 */ 991 uchar *last_rowid; 992 993 /* 994 Table record buffer used by this quick select. 995 */ 996 uchar *record; 997 replace_handler(handler * new_file)998 virtual void replace_handler(handler *new_file) 999 { 1000 DBUG_ASSERT(0); /* Only supported in QUICK_RANGE_SELECT */ 1001 } 1002 1003 #ifndef DBUG_OFF 1004 /* 1005 Print quick select information to DBUG_FILE. Caller is responsible 1006 for locking DBUG_FILE before this call and unlocking it afterwards. 1007 */ 1008 virtual void dbug_dump(int indent, bool verbose)= 0; 1009 #endif 1010 1011 /* 1012 Returns a QUICK_SELECT with reverse order of to the index. 1013 */ make_reverse(uint used_key_parts_arg)1014 virtual QUICK_SELECT_I *make_reverse(uint used_key_parts_arg) { return NULL; } 1015 1016 /* 1017 Add the key columns used by the quick select into table's read set. 1018 1019 This is used by an optimization in filesort. 1020 */ 1021 virtual void add_used_key_part_to_set()=0; 1022 }; 1023 1024 1025 struct st_qsel_param; 1026 class PARAM; 1027 1028 1029 /* 1030 MRR range sequence, array<QUICK_RANGE> implementation: sequence traversal 1031 context. 1032 */ 1033 typedef struct st_quick_range_seq_ctx 1034 { 1035 QUICK_RANGE **first; 1036 QUICK_RANGE **cur; 1037 QUICK_RANGE **last; 1038 } QUICK_RANGE_SEQ_CTX; 1039 1040 range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags); 1041 bool quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range); 1042 1043 1044 /* 1045 Quick select that does a range scan on a single key. The records are 1046 returned in key order. 1047 */ 1048 class QUICK_RANGE_SELECT : public QUICK_SELECT_I 1049 { 1050 protected: 1051 THD *thd; 1052 bool no_alloc; 1053 MEM_ROOT *parent_alloc; 1054 1055 /* true if we enabled key only reads */ 1056 handler *file; 1057 1058 /* Members to deal with case when this quick select is a ROR-merged scan */ 1059 bool in_ror_merged_scan; 1060 MY_BITMAP column_bitmap; 1061 bool free_file; /* TRUE <=> this->file is "owned" by this quick select */ 1062 1063 /* Range pointers to be used when not using MRR interface */ 1064 /* Members needed to use the MRR interface */ 1065 QUICK_RANGE_SEQ_CTX qr_traversal_ctx; 1066 public: 1067 uint mrr_flags; /* Flags to be used with MRR interface */ 1068 protected: 1069 uint mrr_buf_size; /* copy from thd->variables.mrr_buff_size */ 1070 HANDLER_BUFFER *mrr_buf_desc; /* the handler buffer */ 1071 1072 /* Info about index we're scanning */ 1073 1074 DYNAMIC_ARRAY ranges; /* ordered array of range ptrs */ 1075 QUICK_RANGE **cur_range; /* current element in ranges */ 1076 1077 QUICK_RANGE *last_range; 1078 1079 KEY_PART *key_parts; 1080 KEY_PART_INFO *key_part_info; 1081 1082 bool dont_free; /* Used by QUICK_SELECT_DESC */ 1083 1084 int cmp_next(QUICK_RANGE *range); 1085 int cmp_prev(QUICK_RANGE *range); 1086 bool row_in_ranges(); 1087 public: 1088 MEM_ROOT alloc; 1089 1090 QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc, 1091 MEM_ROOT *parent_alloc, bool *create_err); 1092 ~QUICK_RANGE_SELECT(); clone(bool * create_error)1093 virtual QUICK_RANGE_SELECT *clone(bool *create_error) 1094 { return new QUICK_RANGE_SELECT(thd, head, index, no_alloc, parent_alloc, 1095 create_error); } 1096 1097 void need_sorted_output(); 1098 int init(); 1099 int reset(void); 1100 int get_next(); 1101 void range_end(); 1102 int get_next_prefix(uint prefix_length, uint group_key_parts, 1103 uchar *cur_prefix); reverse_sorted()1104 bool reverse_sorted() { return 0; } 1105 bool unique_key_range(); 1106 int init_ror_merged_scan(bool reuse_handler, MEM_ROOT *alloc); save_last_pos()1107 void save_last_pos() 1108 { file->position(record); } get_type()1109 int get_type() { return QS_TYPE_RANGE; } 1110 void add_keys_and_lengths(String *key_names, String *used_lengths); 1111 Explain_quick_select *get_explain(MEM_ROOT *alloc); 1112 #ifndef DBUG_OFF 1113 void dbug_dump(int indent, bool verbose); 1114 #endif replace_handler(handler * new_file)1115 virtual void replace_handler(handler *new_file) { file= new_file; } 1116 QUICK_SELECT_I *make_reverse(uint used_key_parts_arg); 1117 1118 virtual void add_used_key_part_to_set(); 1119 1120 private: 1121 /* Default copy ctor used by QUICK_SELECT_DESC */ 1122 friend class TRP_ROR_INTERSECT; 1123 friend 1124 QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, 1125 struct st_table_ref *ref, 1126 ha_rows records); 1127 friend bool get_quick_keys(PARAM *param, QUICK_RANGE_SELECT *quick, 1128 KEY_PART *key, SEL_ARG *key_tree, 1129 uchar *min_key, uint min_key_flag, 1130 uchar *max_key, uint max_key_flag); 1131 friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx, 1132 SEL_ARG *key_tree, 1133 uint mrr_flags, 1134 uint mrr_buf_size, 1135 MEM_ROOT *alloc); 1136 friend class QUICK_SELECT_DESC; 1137 friend class QUICK_INDEX_SORT_SELECT; 1138 friend class QUICK_INDEX_MERGE_SELECT; 1139 friend class QUICK_ROR_INTERSECT_SELECT; 1140 friend class QUICK_INDEX_INTERSECT_SELECT; 1141 friend class QUICK_GROUP_MIN_MAX_SELECT; 1142 friend bool quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range); 1143 friend range_seq_t quick_range_seq_init(void *init_param, 1144 uint n_ranges, uint flags); 1145 friend 1146 int read_keys_and_merge_scans(THD *thd, TABLE *head, 1147 List<QUICK_RANGE_SELECT> quick_selects, 1148 QUICK_RANGE_SELECT *pk_quick_select, 1149 READ_RECORD *read_record, 1150 bool intersection, 1151 key_map *filtered_scans, 1152 Unique **unique_ptr); 1153 1154 }; 1155 1156 1157 class QUICK_RANGE_SELECT_GEOM: public QUICK_RANGE_SELECT 1158 { 1159 public: QUICK_RANGE_SELECT_GEOM(THD * thd,TABLE * table,uint index_arg,bool no_alloc,MEM_ROOT * parent_alloc,bool * create_err)1160 QUICK_RANGE_SELECT_GEOM(THD *thd, TABLE *table, uint index_arg, 1161 bool no_alloc, MEM_ROOT *parent_alloc, 1162 bool *create_err) 1163 :QUICK_RANGE_SELECT(thd, table, index_arg, no_alloc, parent_alloc, 1164 create_err) 1165 {}; clone(bool * create_error)1166 virtual QUICK_RANGE_SELECT *clone(bool *create_error) 1167 { 1168 DBUG_ASSERT(0); 1169 return new QUICK_RANGE_SELECT_GEOM(thd, head, index, no_alloc, 1170 parent_alloc, create_error); 1171 } 1172 virtual int get_next(); 1173 }; 1174 1175 1176 /* 1177 QUICK_INDEX_SORT_SELECT is the base class for the common functionality of: 1178 - QUICK_INDEX_MERGE_SELECT, access based on multi-index merge/union 1179 - QUICK_INDEX_INTERSECT_SELECT, access based on multi-index intersection 1180 1181 1182 QUICK_INDEX_SORT_SELECT uses 1183 * QUICK_RANGE_SELECTs to get rows 1184 * Unique class 1185 - to remove duplicate rows for QUICK_INDEX_MERGE_SELECT 1186 - to intersect rows for QUICK_INDEX_INTERSECT_SELECT 1187 1188 INDEX MERGE OPTIMIZER 1189 Current implementation doesn't detect all cases where index merge could 1190 be used, in particular: 1191 1192 * index_merge+'using index' is not supported 1193 1194 * If WHERE part contains complex nested AND and OR conditions, some ways 1195 to retrieve rows using index merge will not be considered. The choice 1196 of read plan may depend on the order of conjuncts/disjuncts in WHERE 1197 part of the query, see comments near imerge_list_or_list and 1198 SEL_IMERGE::or_sel_tree_with_checks functions for details. 1199 1200 * There is no "index_merge_ref" method (but index merge on non-first 1201 table in join is possible with 'range checked for each record'). 1202 1203 1204 ROW RETRIEVAL ALGORITHM 1205 1206 index merge/intersection uses Unique class for duplicates removal. 1207 index merge/intersection takes advantage of Clustered Primary Key (CPK) 1208 if the table has one. 1209 The index merge/intersection algorithm consists of two phases: 1210 1211 Phase 1 1212 (implemented by a QUICK_INDEX_MERGE_SELECT::read_keys_and_merge call): 1213 1214 prepare() 1215 { 1216 activate 'index only'; 1217 while(retrieve next row for non-CPK scan) 1218 { 1219 if (there is a CPK scan and row will be retrieved by it) 1220 skip this row; 1221 else 1222 put its rowid into Unique; 1223 } 1224 deactivate 'index only'; 1225 } 1226 1227 Phase 2 1228 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next calls): 1229 1230 fetch() 1231 { 1232 retrieve all rows from row pointers stored in Unique 1233 (merging/intersecting them); 1234 free Unique; 1235 if (! intersection) 1236 retrieve all rows for CPK scan; 1237 } 1238 */ 1239 1240 class QUICK_INDEX_SORT_SELECT : public QUICK_SELECT_I 1241 { 1242 protected: 1243 Unique *unique; 1244 public: 1245 QUICK_INDEX_SORT_SELECT(THD *thd, TABLE *table); 1246 ~QUICK_INDEX_SORT_SELECT(); 1247 1248 int init(); need_sorted_output()1249 void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ } 1250 int reset(void); reverse_sorted()1251 bool reverse_sorted() { return false; } unique_key_range()1252 bool unique_key_range() { return false; } 1253 bool is_keys_used(const MY_BITMAP *fields); 1254 #ifndef DBUG_OFF 1255 void dbug_dump(int indent, bool verbose); 1256 #endif 1257 Explain_quick_select *get_explain(MEM_ROOT *alloc); 1258 1259 bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range); 1260 1261 /* range quick selects this index merge/intersect consists of */ 1262 List<QUICK_RANGE_SELECT> quick_selects; 1263 1264 /* quick select that uses clustered primary key (NULL if none) */ 1265 QUICK_RANGE_SELECT* pk_quick_select; 1266 1267 MEM_ROOT alloc; 1268 THD *thd; is_valid()1269 virtual bool is_valid() 1270 { 1271 List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); 1272 QUICK_RANGE_SELECT *quick; 1273 bool valid= true; 1274 while ((quick= it++)) 1275 { 1276 if (!quick->is_valid()) 1277 { 1278 valid= false; 1279 break; 1280 } 1281 } 1282 return valid; 1283 } 1284 virtual int read_keys_and_merge()= 0; 1285 /* used to get rows collected in Unique */ 1286 READ_RECORD read_record; 1287 1288 virtual void add_used_key_part_to_set(); 1289 }; 1290 1291 1292 1293 class QUICK_INDEX_MERGE_SELECT : public QUICK_INDEX_SORT_SELECT 1294 { 1295 private: 1296 /* true if this select is currently doing a clustered PK scan */ 1297 bool doing_pk_scan; 1298 protected: 1299 int read_keys_and_merge(); 1300 1301 public: QUICK_INDEX_MERGE_SELECT(THD * thd_arg,TABLE * table)1302 QUICK_INDEX_MERGE_SELECT(THD *thd_arg, TABLE *table) 1303 :QUICK_INDEX_SORT_SELECT(thd_arg, table) {} 1304 1305 int get_next(); get_type()1306 int get_type() { return QS_TYPE_INDEX_MERGE; } 1307 void add_keys_and_lengths(String *key_names, String *used_lengths); 1308 }; 1309 1310 class QUICK_INDEX_INTERSECT_SELECT : public QUICK_INDEX_SORT_SELECT 1311 { 1312 protected: 1313 int read_keys_and_merge(); 1314 1315 public: QUICK_INDEX_INTERSECT_SELECT(THD * thd_arg,TABLE * table)1316 QUICK_INDEX_INTERSECT_SELECT(THD *thd_arg, TABLE *table) 1317 :QUICK_INDEX_SORT_SELECT(thd_arg, table) {} 1318 1319 key_map filtered_scans; 1320 int get_next(); get_type()1321 int get_type() { return QS_TYPE_INDEX_INTERSECT; } 1322 void add_keys_and_lengths(String *key_names, String *used_lengths); 1323 Explain_quick_select *get_explain(MEM_ROOT *alloc); 1324 }; 1325 1326 1327 /* 1328 Rowid-Ordered Retrieval (ROR) index intersection quick select. 1329 This quick select produces intersection of row sequences returned 1330 by several QUICK_RANGE_SELECTs it "merges". 1331 1332 All merged QUICK_RANGE_SELECTs must return rowids in rowid order. 1333 QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too. 1334 1335 All merged quick selects retrieve {rowid, covered_fields} tuples (not full 1336 table records). 1337 QUICK_ROR_INTERSECT_SELECT retrieves full records if it is not being used 1338 by QUICK_ROR_INTERSECT_SELECT and all merged quick selects together don't 1339 cover needed all fields. 1340 1341 If one of the merged quick selects is a Clustered PK range scan, it is 1342 used only to filter rowid sequence produced by other merged quick selects. 1343 */ 1344 1345 class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I 1346 { 1347 public: 1348 QUICK_ROR_INTERSECT_SELECT(THD *thd, TABLE *table, 1349 bool retrieve_full_rows, 1350 MEM_ROOT *parent_alloc); 1351 ~QUICK_ROR_INTERSECT_SELECT(); 1352 1353 int init(); need_sorted_output()1354 void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ } 1355 int reset(void); 1356 int get_next(); reverse_sorted()1357 bool reverse_sorted() { return false; } unique_key_range()1358 bool unique_key_range() { return false; } get_type()1359 int get_type() { return QS_TYPE_ROR_INTERSECT; } 1360 void add_keys_and_lengths(String *key_names, String *used_lengths); 1361 Explain_quick_select *get_explain(MEM_ROOT *alloc); 1362 bool is_keys_used(const MY_BITMAP *fields); 1363 void add_used_key_part_to_set(); 1364 #ifndef DBUG_OFF 1365 void dbug_dump(int indent, bool verbose); 1366 #endif 1367 int init_ror_merged_scan(bool reuse_handler, MEM_ROOT *alloc); 1368 bool push_quick_back(MEM_ROOT *alloc, QUICK_RANGE_SELECT *quick_sel_range); 1369 1370 class QUICK_SELECT_WITH_RECORD : public Sql_alloc 1371 { 1372 public: 1373 QUICK_RANGE_SELECT *quick; 1374 uchar *key_tuple; ~QUICK_SELECT_WITH_RECORD()1375 ~QUICK_SELECT_WITH_RECORD() { delete quick; } 1376 }; 1377 1378 /* 1379 Range quick selects this intersection consists of, not including 1380 cpk_quick. 1381 */ 1382 List<QUICK_SELECT_WITH_RECORD> quick_selects; 1383 is_valid()1384 virtual bool is_valid() 1385 { 1386 List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects); 1387 QUICK_SELECT_WITH_RECORD *quick; 1388 bool valid= true; 1389 while ((quick= it++)) 1390 { 1391 if (!quick->quick->is_valid()) 1392 { 1393 valid= false; 1394 break; 1395 } 1396 } 1397 return valid; 1398 } 1399 1400 /* 1401 Merged quick select that uses Clustered PK, if there is one. This quick 1402 select is not used for row retrieval, it is used for row retrieval. 1403 */ 1404 QUICK_RANGE_SELECT *cpk_quick; 1405 1406 MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */ 1407 THD *thd; /* current thread */ 1408 bool need_to_fetch_row; /* if true, do retrieve full table records. */ 1409 /* in top-level quick select, true if merged scans where initialized */ 1410 bool scans_inited; 1411 }; 1412 1413 1414 /* 1415 Rowid-Ordered Retrieval index union select. 1416 This quick select produces union of row sequences returned by several 1417 quick select it "merges". 1418 1419 All merged quick selects must return rowids in rowid order. 1420 QUICK_ROR_UNION_SELECT will return rows in rowid order, too. 1421 1422 All merged quick selects are set not to retrieve full table records. 1423 ROR-union quick select always retrieves full records. 1424 1425 */ 1426 1427 class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I 1428 { 1429 public: 1430 QUICK_ROR_UNION_SELECT(THD *thd, TABLE *table); 1431 ~QUICK_ROR_UNION_SELECT(); 1432 1433 int init(); need_sorted_output()1434 void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ } 1435 int reset(void); 1436 int get_next(); reverse_sorted()1437 bool reverse_sorted() { return false; } unique_key_range()1438 bool unique_key_range() { return false; } get_type()1439 int get_type() { return QS_TYPE_ROR_UNION; } 1440 void add_keys_and_lengths(String *key_names, String *used_lengths); 1441 Explain_quick_select *get_explain(MEM_ROOT *alloc); 1442 bool is_keys_used(const MY_BITMAP *fields); 1443 void add_used_key_part_to_set(); 1444 #ifndef DBUG_OFF 1445 void dbug_dump(int indent, bool verbose); 1446 #endif 1447 1448 bool push_quick_back(QUICK_SELECT_I *quick_sel_range); 1449 1450 List<QUICK_SELECT_I> quick_selects; /* Merged quick selects */ 1451 is_valid()1452 virtual bool is_valid() 1453 { 1454 List_iterator_fast<QUICK_SELECT_I> it(quick_selects); 1455 QUICK_SELECT_I *quick; 1456 bool valid= true; 1457 while ((quick= it++)) 1458 { 1459 if (!quick->is_valid()) 1460 { 1461 valid= false; 1462 break; 1463 } 1464 } 1465 return valid; 1466 } 1467 1468 QUEUE queue; /* Priority queue for merge operation */ 1469 MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */ 1470 1471 THD *thd; /* current thread */ 1472 uchar *cur_rowid; /* buffer used in get_next() */ 1473 uchar *prev_rowid; /* rowid of last row returned by get_next() */ 1474 bool have_prev_rowid; /* true if prev_rowid has valid data */ 1475 uint rowid_length; /* table rowid length */ 1476 private: 1477 bool scans_inited; 1478 }; 1479 1480 1481 /* 1482 Index scan for GROUP-BY queries with MIN/MAX aggregate functions. 1483 1484 This class provides a specialized index access method for GROUP-BY queries 1485 of the forms: 1486 1487 SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)] 1488 FROM T 1489 WHERE [RNG(A_1,...,A_p ; where p <= k)] 1490 [AND EQ(B_1,...,B_m)] 1491 [AND PC(C)] 1492 [AND PA(A_i1,...,A_iq)] 1493 GROUP BY A_1,...,A_k; 1494 1495 or 1496 1497 SELECT DISTINCT A_i1,...,A_ik 1498 FROM T 1499 WHERE [RNG(A_1,...,A_p ; where p <= k)] 1500 [AND PA(A_i1,...,A_iq)]; 1501 1502 where all selected fields are parts of the same index. 1503 The class of queries that can be processed by this quick select is fully 1504 specified in the description of get_best_trp_group_min_max() in opt_range.cc. 1505 1506 The get_next() method directly produces result tuples, thus obviating the 1507 need to call end_send_group() because all grouping is already done inside 1508 get_next(). 1509 1510 Since one of the requirements is that all select fields are part of the same 1511 index, this class produces only index keys, and not complete records. 1512 */ 1513 1514 class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I 1515 { 1516 private: 1517 handler * const file; /* The handler used to get data. */ 1518 JOIN *join; /* Descriptor of the current query */ 1519 KEY *index_info; /* The index chosen for data access */ 1520 uchar *record; /* Buffer where the next record is returned. */ 1521 uchar *tmp_record; /* Temporary storage for next_min(), next_max(). */ 1522 uchar *group_prefix; /* Key prefix consisting of the GROUP fields. */ 1523 const uint group_prefix_len; /* Length of the group prefix. */ 1524 uint group_key_parts; /* A number of keyparts in the group prefix */ 1525 uchar *last_prefix; /* Prefix of the last group for detecting EOF. */ 1526 bool have_min; /* Specify whether we are computing */ 1527 bool have_max; /* a MIN, a MAX, or both. */ 1528 bool have_agg_distinct;/* aggregate_function(DISTINCT ...). */ 1529 bool seen_first_key; /* Denotes whether the first key was retrieved.*/ 1530 bool doing_key_read; /* true if we enabled key only reads */ 1531 1532 KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */ 1533 /* of all MIN/MAX functions. */ 1534 uint min_max_arg_len; /* The length of the MIN/MAX argument field */ 1535 uchar *key_infix; /* Infix of constants from equality predicates. */ 1536 uint key_infix_len; 1537 DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */ 1538 uint real_prefix_len; /* Length of key prefix extended with key_infix. */ 1539 uint real_key_parts; /* A number of keyparts in the above value. */ 1540 List<Item_sum> *min_functions; 1541 List<Item_sum> *max_functions; 1542 List_iterator<Item_sum> *min_functions_it; 1543 List_iterator<Item_sum> *max_functions_it; 1544 /* 1545 Use index scan to get the next different key instead of jumping into it 1546 through index read 1547 */ 1548 bool is_index_scan; 1549 public: 1550 /* 1551 The following two members are public to allow easy access from 1552 TRP_GROUP_MIN_MAX::make_quick() 1553 */ 1554 MEM_ROOT alloc; /* Memory pool for this and quick_prefix_select data. */ 1555 QUICK_RANGE_SELECT *quick_prefix_select;/* For retrieval of group prefixes. */ 1556 private: 1557 int next_prefix(); 1558 int next_min_in_range(); 1559 int next_max_in_range(); 1560 int next_min(); 1561 int next_max(); 1562 void update_min_result(); 1563 void update_max_result(); 1564 int cmp_min_max_key(const uchar *key, uint16 length); 1565 public: 1566 QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min, 1567 bool have_max, bool have_agg_distinct, 1568 KEY_PART_INFO *min_max_arg_part, 1569 uint group_prefix_len, uint group_key_parts, 1570 uint used_key_parts, KEY *index_info, uint 1571 use_index, double read_cost, ha_rows records, uint 1572 key_infix_len, uchar *key_infix, MEM_ROOT 1573 *parent_alloc, bool is_index_scan); 1574 ~QUICK_GROUP_MIN_MAX_SELECT(); 1575 bool add_range(SEL_ARG *sel_range); 1576 void update_key_stat(); 1577 void adjust_prefix_ranges(); 1578 bool alloc_buffers(); 1579 int init(); need_sorted_output()1580 void need_sorted_output() { /* always do it */ } 1581 int reset(); 1582 int get_next(); reverse_sorted()1583 bool reverse_sorted() { return false; } unique_key_range()1584 bool unique_key_range() { return false; } get_type()1585 int get_type() { return QS_TYPE_GROUP_MIN_MAX; } 1586 void add_keys_and_lengths(String *key_names, String *used_lengths); 1587 void add_used_key_part_to_set(); 1588 #ifndef DBUG_OFF 1589 void dbug_dump(int indent, bool verbose); 1590 #endif is_agg_distinct()1591 bool is_agg_distinct() { return have_agg_distinct; } loose_scan_is_scanning()1592 bool loose_scan_is_scanning() { return is_index_scan; } 1593 Explain_quick_select *get_explain(MEM_ROOT *alloc); 1594 }; 1595 1596 1597 class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT 1598 { 1599 public: 1600 QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts); clone(bool * create_error)1601 virtual QUICK_RANGE_SELECT *clone(bool *create_error) 1602 { DBUG_ASSERT(0); return new QUICK_SELECT_DESC(this, used_key_parts); } 1603 int get_next(); reverse_sorted()1604 bool reverse_sorted() { return 1; } get_type()1605 int get_type() { return QS_TYPE_RANGE_DESC; } make_reverse(uint used_key_parts_arg)1606 QUICK_SELECT_I *make_reverse(uint used_key_parts_arg) 1607 { 1608 return this; // is already reverse sorted 1609 } 1610 private: 1611 bool range_reads_after_key(QUICK_RANGE *range); reset(void)1612 int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); } 1613 List<QUICK_RANGE> rev_ranges; 1614 List_iterator<QUICK_RANGE> rev_it; 1615 uint used_key_parts; 1616 }; 1617 1618 1619 class SQL_SELECT :public Sql_alloc { 1620 public: 1621 QUICK_SELECT_I *quick; // If quick-select used 1622 COND *cond; // where condition 1623 1624 /* 1625 When using Index Condition Pushdown: condition that we've had before 1626 extracting and pushing index condition. 1627 In other cases, NULL. 1628 */ 1629 Item *pre_idx_push_select_cond; 1630 TABLE *head; 1631 IO_CACHE file; // Positions to used records 1632 ha_rows records; // Records in use if read from file 1633 double read_time; // Time to read rows 1634 key_map quick_keys; // Possible quick keys 1635 key_map needed_reg; // Possible quick keys after prev tables. 1636 table_map const_tables,read_tables; 1637 /* See PARAM::possible_keys */ 1638 key_map possible_keys; 1639 bool free_cond; /* Currently not used and always FALSE */ 1640 1641 SQL_SELECT(); 1642 ~SQL_SELECT(); 1643 void cleanup(); set_quick(QUICK_SELECT_I * new_quick)1644 void set_quick(QUICK_SELECT_I *new_quick) { delete quick; quick= new_quick; } check_quick(THD * thd,bool force_quick_range,ha_rows limit)1645 bool check_quick(THD *thd, bool force_quick_range, ha_rows limit) 1646 { 1647 key_map tmp; 1648 tmp.set_all(); 1649 return test_quick_select(thd, tmp, 0, limit, force_quick_range, FALSE, FALSE) < 0; 1650 } 1651 /* 1652 RETURN 1653 0 if record must be skipped <-> (cond && cond->val_int() == 0) 1654 -1 if error 1655 1 otherwise 1656 */ skip_record(THD * thd)1657 inline int skip_record(THD *thd) 1658 { 1659 int rc= MY_TEST(!cond || cond->val_int()); 1660 if (thd->is_error()) 1661 rc= -1; 1662 return rc; 1663 } 1664 int test_quick_select(THD *thd, key_map keys, table_map prev_tables, 1665 ha_rows limit, bool force_quick_range, 1666 bool ordered_output, bool remove_false_parts_of_where); 1667 }; 1668 1669 1670 class SQL_SELECT_auto 1671 { 1672 SQL_SELECT *select; 1673 public: SQL_SELECT_auto()1674 SQL_SELECT_auto(): select(NULL) 1675 {} ~SQL_SELECT_auto()1676 ~SQL_SELECT_auto() 1677 { 1678 delete select; 1679 } 1680 SQL_SELECT_auto& 1681 operator= (SQL_SELECT *_select) 1682 { 1683 select= _select; 1684 return *this; 1685 } 1686 operator SQL_SELECT * () const 1687 { 1688 return select; 1689 } 1690 SQL_SELECT * 1691 operator-> () const 1692 { 1693 return select; 1694 } 1695 operator bool () const 1696 { 1697 return select; 1698 } 1699 }; 1700 1701 1702 class FT_SELECT: public QUICK_RANGE_SELECT 1703 { 1704 public: FT_SELECT(THD * thd,TABLE * table,uint key,bool * create_err)1705 FT_SELECT(THD *thd, TABLE *table, uint key, bool *create_err) : 1706 QUICK_RANGE_SELECT (thd, table, key, 1, NULL, create_err) 1707 { (void) init(); } ~FT_SELECT()1708 ~FT_SELECT() { file->ft_end(); } clone(bool * create_error)1709 virtual QUICK_RANGE_SELECT *clone(bool *create_error) 1710 { DBUG_ASSERT(0); return new FT_SELECT(thd, head, index, create_error); } init()1711 int init() { return file->ft_init(); } reset()1712 int reset() { return 0; } get_next()1713 int get_next() { return file->ha_ft_read(record); } get_type()1714 int get_type() { return QS_TYPE_FULLTEXT; } 1715 }; 1716 1717 FT_SELECT *get_ft_select(THD *thd, TABLE *table, uint key); 1718 QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, 1719 struct st_table_ref *ref, 1720 ha_rows records); 1721 SQL_SELECT *make_select(TABLE *head, table_map const_tables, 1722 table_map read_tables, COND *conds, 1723 SORT_INFO* filesort, 1724 bool allow_null_cond, int *error); 1725 1726 bool calculate_cond_selectivity_for_table(THD *thd, TABLE *table, Item **cond); 1727 1728 bool eq_ranges_exceeds_limit(RANGE_SEQ_IF *seq, void *seq_init_param, 1729 uint limit); 1730 1731 #ifdef WITH_PARTITION_STORAGE_ENGINE 1732 bool prune_partitions(THD *thd, TABLE *table, Item *pprune_cond); 1733 #endif 1734 void store_key_image_to_rec(Field *field, uchar *ptr, uint len); 1735 1736 extern String null_string; 1737 1738 /* check this number of rows (default value) */ 1739 #define SELECTIVITY_SAMPLING_LIMIT 100 1740 /* but no more then this part of table (10%) */ 1741 #define SELECTIVITY_SAMPLING_SHARE 0.10 1742 /* do not check if we are going check less then this number of records */ 1743 #define SELECTIVITY_SAMPLING_THRESHOLD 10 1744 1745 #endif 1746