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