1 /* Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved. 2 3 This program is free software; you can redistribute it and/or modify 4 it under the terms of the GNU General Public License as published by 5 the Free Software Foundation; version 2 of the License. 6 7 This program is distributed in the hope that it will be useful, 8 but WITHOUT ANY WARRANTY; without even the implied warranty of 9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10 GNU General Public License for more details. 11 12 You should have received a copy of the GNU General Public License 13 along with this program; if not, write to the Free Software 14 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ 15 16 17 /* classes to use when handling where clause */ 18 19 #ifndef _opt_range_h 20 #define _opt_range_h 21 22 #ifdef USE_PRAGMA_INTERFACE 23 #pragma interface /* gcc class implementation */ 24 #endif 25 26 #include "thr_malloc.h" /* sql_memdup */ 27 #include "records.h" /* READ_RECORD */ 28 #include "queues.h" /* QUEUE */ 29 /* 30 It is necessary to include set_var.h instead of item.h because there 31 are dependencies on include order for set_var.h and item.h. This 32 will be resolved later. 33 */ 34 #include "sql_class.h" // set_var.h: THD 35 #include "set_var.h" /* Item */ 36 37 class JOIN; 38 class Item_sum; 39 40 typedef struct st_key_part { 41 uint16 key,part; 42 /* See KEY_PART_INFO for meaning of the next two: */ 43 uint16 store_length, length; 44 uint8 null_bit; 45 /* 46 Keypart flags (0 when this structure is used by partition pruning code 47 for fake partitioning index description) 48 */ 49 uint8 flag; 50 Field *field; 51 Field::imagetype image_type; 52 } KEY_PART; 53 54 55 class QUICK_RANGE :public Sql_alloc { 56 public: 57 uchar *min_key,*max_key; 58 uint16 min_length,max_length,flag; 59 key_part_map min_keypart_map, // bitmap of used keyparts in min_key 60 max_keypart_map; // bitmap of used keyparts in max_key 61 #ifdef HAVE_purify 62 uint16 dummy; /* Avoid warnings on 'flag' */ 63 #endif 64 QUICK_RANGE(); /* Full range */ QUICK_RANGE(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)65 QUICK_RANGE(const uchar *min_key_arg, uint min_length_arg, 66 key_part_map min_keypart_map_arg, 67 const uchar *max_key_arg, uint max_length_arg, 68 key_part_map max_keypart_map_arg, 69 uint flag_arg) 70 : min_key((uchar*) sql_memdup(min_key_arg,min_length_arg+1)), 71 max_key((uchar*) sql_memdup(max_key_arg,max_length_arg+1)), 72 min_length((uint16) min_length_arg), 73 max_length((uint16) max_length_arg), 74 flag((uint16) flag_arg), 75 min_keypart_map(min_keypart_map_arg), 76 max_keypart_map(max_keypart_map_arg) 77 { 78 #ifdef HAVE_purify 79 dummy=0; 80 #endif 81 } 82 83 /** 84 Initalizes a key_range object for communication with storage engine. 85 86 This function facilitates communication with the Storage Engine API by 87 translating the minimum endpoint of the interval represented by this 88 QUICK_RANGE into an index range endpoint specifier for the engine. 89 90 @param Pointer to an uninitialized key_range C struct. 91 92 @param prefix_length The length of the search key prefix to be used for 93 lookup. 94 95 @param keypart_map A set (bitmap) of keyparts to be used. 96 */ make_min_endpoint(key_range * kr,uint prefix_length,key_part_map keypart_map)97 void make_min_endpoint(key_range *kr, uint prefix_length, 98 key_part_map keypart_map) { 99 make_min_endpoint(kr); 100 kr->length= min(kr->length, prefix_length); 101 kr->keypart_map&= keypart_map; 102 } 103 104 /** 105 Initalizes a key_range object for communication with storage engine. 106 107 This function facilitates communication with the Storage Engine API by 108 translating the minimum endpoint of the interval represented by this 109 QUICK_RANGE into an index range endpoint specifier for the engine. 110 111 @param Pointer to an uninitialized key_range C struct. 112 */ make_min_endpoint(key_range * kr)113 void make_min_endpoint(key_range *kr) { 114 kr->key= (const uchar*)min_key; 115 kr->length= min_length; 116 kr->keypart_map= min_keypart_map; 117 kr->flag= ((flag & NEAR_MIN) ? HA_READ_AFTER_KEY : 118 (flag & EQ_RANGE) ? HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT); 119 } 120 121 /** 122 Initalizes a key_range object for communication with storage engine. 123 124 This function facilitates communication with the Storage Engine API by 125 translating the maximum endpoint of the interval represented by this 126 QUICK_RANGE into an index range endpoint specifier for the engine. 127 128 @param Pointer to an uninitialized key_range C struct. 129 130 @param prefix_length The length of the search key prefix to be used for 131 lookup. 132 133 @param keypart_map A set (bitmap) of keyparts to be used. 134 */ make_max_endpoint(key_range * kr,uint prefix_length,key_part_map keypart_map)135 void make_max_endpoint(key_range *kr, uint prefix_length, 136 key_part_map keypart_map) { 137 make_max_endpoint(kr); 138 kr->length= min(kr->length, prefix_length); 139 kr->keypart_map&= keypart_map; 140 } 141 142 /** 143 Initalizes a key_range object for communication with storage engine. 144 145 This function facilitates communication with the Storage Engine API by 146 translating the maximum endpoint of the interval represented by this 147 QUICK_RANGE into an index range endpoint specifier for the engine. 148 149 @param Pointer to an uninitialized key_range C struct. 150 */ make_max_endpoint(key_range * kr)151 void make_max_endpoint(key_range *kr) { 152 kr->key= (const uchar*)max_key; 153 kr->length= max_length; 154 kr->keypart_map= max_keypart_map; 155 /* 156 We use READ_AFTER_KEY here because if we are reading on a key 157 prefix we want to find all keys with this prefix 158 */ 159 kr->flag= (flag & NEAR_MAX ? HA_READ_BEFORE_KEY : HA_READ_AFTER_KEY); 160 } 161 }; 162 163 164 /* 165 Quick select interface. 166 This class is a parent for all QUICK_*_SELECT and FT_SELECT classes. 167 168 The usage scenario is as follows: 169 1. Create quick select 170 quick= new QUICK_XXX_SELECT(...); 171 172 2. Perform lightweight initialization. This can be done in 2 ways: 173 2.a: Regular initialization 174 if (quick->init()) 175 { 176 //the only valid action after failed init() call is delete 177 delete quick; 178 } 179 2.b: Special initialization for quick selects merged by QUICK_ROR_*_SELECT 180 if (quick->init_ror_merged_scan()) 181 delete quick; 182 183 3. Perform zero, one, or more scans. 184 while (...) 185 { 186 // initialize quick select for scan. This may allocate 187 // buffers and/or prefetch rows. 188 if (quick->reset()) 189 { 190 //the only valid action after failed reset() call is delete 191 delete quick; 192 //abort query 193 } 194 195 // perform the scan 196 do 197 { 198 res= quick->get_next(); 199 } while (res && ...) 200 } 201 202 4. Delete the select: 203 delete quick; 204 205 */ 206 207 class QUICK_SELECT_I 208 { 209 public: 210 bool sorted; 211 ha_rows records; /* estimate of # of records to be retrieved */ 212 double read_time; /* time to perform this retrieval */ 213 TABLE *head; 214 /* 215 Index this quick select uses, or MAX_KEY for quick selects 216 that use several indexes 217 */ 218 uint index; 219 220 /* 221 Total length of first used_key_parts parts of the key. 222 Applicable if index!= MAX_KEY. 223 */ 224 uint max_used_key_length; 225 226 /* 227 Max. number of (first) key parts this quick select uses for retrieval. 228 eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2. 229 Applicable if index!= MAX_KEY. 230 231 For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts. 232 */ 233 uint used_key_parts; 234 235 QUICK_SELECT_I(); ~QUICK_SELECT_I()236 virtual ~QUICK_SELECT_I(){}; 237 238 /* 239 Do post-constructor initialization. 240 SYNOPSIS 241 init() 242 243 init() performs initializations that should have been in constructor if 244 it was possible to return errors from constructors. The join optimizer may 245 create and then delete quick selects without retrieving any rows so init() 246 must not contain any IO or CPU intensive code. 247 248 If init() call fails the only valid action is to delete this quick select, 249 reset() and get_next() must not be called. 250 251 RETURN 252 0 OK 253 other Error code 254 */ 255 virtual int init() = 0; 256 257 /* 258 Initialize quick select for row retrieval. 259 SYNOPSIS 260 reset() 261 262 reset() should be called when it is certain that row retrieval will be 263 necessary. This call may do heavyweight initialization like buffering first 264 N records etc. If reset() call fails get_next() must not be called. 265 Note that reset() may be called several times if 266 * the quick select is executed in a subselect 267 * a JOIN buffer is used 268 269 RETURN 270 0 OK 271 other Error code 272 */ 273 virtual int reset(void) = 0; 274 275 virtual int get_next() = 0; /* get next record to retrieve */ 276 277 /* Range end should be called when we have looped over the whole index */ range_end()278 virtual void range_end() {} 279 280 virtual bool reverse_sorted() = 0; unique_key_range()281 virtual bool unique_key_range() { return false; } clustered_pk_range()282 virtual bool clustered_pk_range() { return false; } 283 284 enum { 285 QS_TYPE_RANGE = 0, 286 QS_TYPE_INDEX_MERGE = 1, 287 QS_TYPE_RANGE_DESC = 2, 288 QS_TYPE_FULLTEXT = 3, 289 QS_TYPE_ROR_INTERSECT = 4, 290 QS_TYPE_ROR_UNION = 5, 291 QS_TYPE_GROUP_MIN_MAX = 6 292 }; 293 294 /* Get type of this quick select - one of the QS_TYPE_* values */ 295 virtual int get_type() = 0; 296 297 /* 298 Initialize this quick select as a merged scan inside a ROR-union or a ROR- 299 intersection scan. The caller must not additionally call init() if this 300 function is called. 301 SYNOPSIS 302 init_ror_merged_scan() 303 reuse_handler If true, the quick select may use table->handler, 304 otherwise it must create and use a separate handler 305 object. 306 RETURN 307 0 Ok 308 other Error 309 */ init_ror_merged_scan(bool reuse_handler)310 virtual int init_ror_merged_scan(bool reuse_handler) 311 { DBUG_ASSERT(0); return 1; } 312 313 /* 314 Save ROWID of last retrieved row in file->ref. This used in ROR-merging. 315 */ save_last_pos()316 virtual void save_last_pos(){}; 317 318 /* 319 Append comma-separated list of keys this quick select uses to key_names; 320 append comma-separated list of corresponding used lengths to used_lengths. 321 This is used by select_describe. 322 */ 323 virtual void add_keys_and_lengths(String *key_names, 324 String *used_lengths)=0; 325 326 /* 327 Append text representation of quick select structure (what and how is 328 merged) to str. The result is added to "Extra" field in EXPLAIN output. 329 This function is implemented only by quick selects that merge other quick 330 selects output and/or can produce output suitable for merging. 331 */ add_info_string(String * str)332 virtual void add_info_string(String *str) {}; 333 /* 334 Return 1 if any index used by this quick select 335 uses field which is marked in passed bitmap. 336 */ 337 virtual bool is_keys_used(const MY_BITMAP *fields); 338 339 /** 340 Simple sanity check that the quick select has been set up 341 correctly. Function is overridden by quick selects that merge 342 indices. 343 */ is_valid()344 virtual bool is_valid() { return index != MAX_KEY; }; 345 346 /* 347 rowid of last row retrieved by this quick select. This is used only when 348 doing ROR-index_merge selects 349 */ 350 uchar *last_rowid; 351 352 /* 353 Table record buffer used by this quick select. 354 */ 355 uchar *record; 356 #ifndef DBUG_OFF 357 /* 358 Print quick select information to DBUG_FILE. Caller is responsible 359 for locking DBUG_FILE before this call and unlocking it afterwards. 360 */ 361 virtual void dbug_dump(int indent, bool verbose)= 0; 362 #endif 363 364 /* 365 Returns a QUICK_SELECT with reverse order of to the index. 366 */ make_reverse(uint used_key_parts_arg)367 virtual QUICK_SELECT_I *make_reverse(uint used_key_parts_arg) { return NULL; } 368 }; 369 370 371 struct st_qsel_param; 372 class PARAM; 373 class SEL_ARG; 374 375 /* 376 Quick select that does a range scan on a single key. The records are 377 returned in key order. 378 */ 379 class QUICK_RANGE_SELECT : public QUICK_SELECT_I 380 { 381 protected: 382 bool next,dont_free,in_ror_merged_scan; 383 public: 384 int error; 385 protected: 386 handler *file; 387 /* 388 If true, this quick select has its "own" handler object which should be 389 closed no later then this quick select is deleted. 390 */ 391 bool free_file; 392 bool in_range; 393 uint multi_range_count; /* copy from thd->variables.multi_range_count */ 394 uint multi_range_length; /* the allocated length for the array */ 395 uint multi_range_bufsiz; /* copy from thd->variables.read_rnd_buff_size */ 396 KEY_MULTI_RANGE *multi_range; /* the multi-range array (allocated and 397 freed by QUICK_RANGE_SELECT) */ 398 HANDLER_BUFFER *multi_range_buff; /* the handler buffer (allocated and 399 freed by QUICK_RANGE_SELECT) */ 400 MY_BITMAP column_bitmap, *save_read_set, *save_write_set; 401 402 friend class TRP_ROR_INTERSECT; 403 friend 404 QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, 405 struct st_table_ref *ref, 406 ha_rows records); 407 friend bool get_quick_keys(PARAM *param, 408 QUICK_RANGE_SELECT *quick,KEY_PART *key, 409 SEL_ARG *key_tree, 410 uchar *min_key, uint min_key_flag, 411 uchar *max_key, uint max_key_flag); 412 friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx, 413 SEL_ARG *key_tree, 414 MEM_ROOT *alloc); 415 friend class QUICK_SELECT_DESC; 416 friend class QUICK_INDEX_MERGE_SELECT; 417 friend class QUICK_ROR_INTERSECT_SELECT; 418 friend class QUICK_GROUP_MIN_MAX_SELECT; 419 420 DYNAMIC_ARRAY ranges; /* ordered array of range ptrs */ 421 QUICK_RANGE **cur_range; /* current element in ranges */ 422 423 QUICK_RANGE *last_range; 424 KEY_PART *key_parts; 425 KEY_PART_INFO *key_part_info; 426 int cmp_next(QUICK_RANGE *range); 427 int cmp_prev(QUICK_RANGE *range); 428 bool row_in_ranges(); 429 public: 430 MEM_ROOT alloc; 431 432 QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc=0, 433 MEM_ROOT *parent_alloc=NULL); 434 ~QUICK_RANGE_SELECT(); 435 436 int init(); 437 int reset(void); 438 int get_next(); 439 void range_end(); 440 int get_next_prefix(uint prefix_length, uint group_key_parts, 441 uchar *cur_prefix); reverse_sorted()442 bool reverse_sorted() { return 0; } 443 bool unique_key_range(); 444 int init_ror_merged_scan(bool reuse_handler); save_last_pos()445 void save_last_pos() 446 { file->position(record); } get_type()447 int get_type() { return QS_TYPE_RANGE; } 448 void add_keys_and_lengths(String *key_names, String *used_lengths); 449 void add_info_string(String *str); 450 #ifndef DBUG_OFF 451 void dbug_dump(int indent, bool verbose); 452 #endif 453 QUICK_SELECT_I *make_reverse(uint used_key_parts_arg); 454 private: 455 /* Default copy ctor used by QUICK_SELECT_DESC */ 456 }; 457 458 459 class QUICK_RANGE_SELECT_GEOM: public QUICK_RANGE_SELECT 460 { 461 public: QUICK_RANGE_SELECT_GEOM(THD * thd,TABLE * table,uint index_arg,bool no_alloc,MEM_ROOT * parent_alloc)462 QUICK_RANGE_SELECT_GEOM(THD *thd, TABLE *table, uint index_arg, 463 bool no_alloc, MEM_ROOT *parent_alloc) 464 :QUICK_RANGE_SELECT(thd, table, index_arg, no_alloc, parent_alloc) 465 {}; 466 virtual int get_next(); 467 }; 468 469 470 /* 471 QUICK_INDEX_MERGE_SELECT - index_merge access method quick select. 472 473 QUICK_INDEX_MERGE_SELECT uses 474 * QUICK_RANGE_SELECTs to get rows 475 * Unique class to remove duplicate rows 476 477 INDEX MERGE OPTIMIZER 478 Current implementation doesn't detect all cases where index_merge could 479 be used, in particular: 480 * index_merge will never be used if range scan is possible (even if 481 range scan is more expensive) 482 483 * index_merge+'using index' is not supported (this the consequence of 484 the above restriction) 485 486 * If WHERE part contains complex nested AND and OR conditions, some ways 487 to retrieve rows using index_merge will not be considered. The choice 488 of read plan may depend on the order of conjuncts/disjuncts in WHERE 489 part of the query, see comments near imerge_list_or_list and 490 SEL_IMERGE::or_sel_tree_with_checks functions for details. 491 492 * There is no "index_merge_ref" method (but index_merge on non-first 493 table in join is possible with 'range checked for each record'). 494 495 See comments around SEL_IMERGE class and test_quick_select for more 496 details. 497 498 ROW RETRIEVAL ALGORITHM 499 500 index_merge uses Unique class for duplicates removal. index_merge takes 501 advantage of Clustered Primary Key (CPK) if the table has one. 502 The index_merge algorithm consists of two phases: 503 504 Phase 1 (implemented in QUICK_INDEX_MERGE_SELECT::prepare_unique): 505 prepare() 506 { 507 activate 'index only'; 508 while(retrieve next row for non-CPK scan) 509 { 510 if (there is a CPK scan and row will be retrieved by it) 511 skip this row; 512 else 513 put its rowid into Unique; 514 } 515 deactivate 'index only'; 516 } 517 518 Phase 2 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next 519 calls): 520 521 fetch() 522 { 523 retrieve all rows from row pointers stored in Unique; 524 free Unique; 525 retrieve all rows for CPK scan; 526 } 527 */ 528 529 class QUICK_INDEX_MERGE_SELECT : public QUICK_SELECT_I 530 { 531 Unique *unique; 532 public: 533 QUICK_INDEX_MERGE_SELECT(THD *thd, TABLE *table); 534 ~QUICK_INDEX_MERGE_SELECT(); 535 536 int init(); 537 int reset(void); 538 int get_next(); reverse_sorted()539 bool reverse_sorted() { return false; } unique_key_range()540 bool unique_key_range() { return false; } get_type()541 int get_type() { return QS_TYPE_INDEX_MERGE; } 542 void add_keys_and_lengths(String *key_names, String *used_lengths); 543 void add_info_string(String *str); 544 bool is_keys_used(const MY_BITMAP *fields); 545 #ifndef DBUG_OFF 546 void dbug_dump(int indent, bool verbose); 547 #endif 548 549 bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range); 550 551 /* range quick selects this index_merge read consists of */ 552 List<QUICK_RANGE_SELECT> quick_selects; 553 554 /* quick select that uses clustered primary key (NULL if none) */ 555 QUICK_RANGE_SELECT* pk_quick_select; 556 557 /* true if this select is currently doing a clustered PK scan */ 558 bool doing_pk_scan; 559 560 MEM_ROOT alloc; 561 THD *thd; 562 int read_keys_and_merge(); 563 clustered_pk_range()564 bool clustered_pk_range() { return test(pk_quick_select); } 565 is_valid()566 virtual bool is_valid() 567 { 568 List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); 569 QUICK_RANGE_SELECT *quick; 570 bool valid= true; 571 while ((quick= it++)) 572 { 573 if (!quick->is_valid()) 574 { 575 valid= false; 576 break; 577 } 578 } 579 return valid; 580 } 581 582 /* used to get rows collected in Unique */ 583 READ_RECORD read_record; 584 }; 585 586 587 /* 588 Rowid-Ordered Retrieval (ROR) index intersection quick select. 589 This quick select produces intersection of row sequences returned 590 by several QUICK_RANGE_SELECTs it "merges". 591 592 All merged QUICK_RANGE_SELECTs must return rowids in rowid order. 593 QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too. 594 595 All merged quick selects retrieve {rowid, covered_fields} tuples (not full 596 table records). 597 QUICK_ROR_INTERSECT_SELECT retrieves full records if it is not being used 598 by QUICK_ROR_INTERSECT_SELECT and all merged quick selects together don't 599 cover needed all fields. 600 601 If one of the merged quick selects is a Clustered PK range scan, it is 602 used only to filter rowid sequence produced by other merged quick selects. 603 */ 604 605 class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I 606 { 607 public: 608 QUICK_ROR_INTERSECT_SELECT(THD *thd, TABLE *table, 609 bool retrieve_full_rows, 610 MEM_ROOT *parent_alloc); 611 ~QUICK_ROR_INTERSECT_SELECT(); 612 613 int init(); 614 int reset(void); 615 int get_next(); reverse_sorted()616 bool reverse_sorted() { return false; } unique_key_range()617 bool unique_key_range() { return false; } get_type()618 int get_type() { return QS_TYPE_ROR_INTERSECT; } 619 void add_keys_and_lengths(String *key_names, String *used_lengths); 620 void add_info_string(String *str); 621 bool is_keys_used(const MY_BITMAP *fields); 622 #ifndef DBUG_OFF 623 void dbug_dump(int indent, bool verbose); 624 #endif 625 int init_ror_merged_scan(bool reuse_handler); 626 bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range); 627 628 /* 629 Range quick selects this intersection consists of, not including 630 cpk_quick. 631 */ 632 List<QUICK_RANGE_SELECT> quick_selects; 633 is_valid()634 virtual bool is_valid() 635 { 636 List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects); 637 QUICK_RANGE_SELECT *quick; 638 bool valid= true; 639 while ((quick= it++)) 640 { 641 if (!quick->is_valid()) 642 { 643 valid= false; 644 break; 645 } 646 } 647 return valid; 648 } 649 650 /* 651 Merged quick select that uses Clustered PK, if there is one. This quick 652 select is not used for row retrieval, it is used for row retrieval. 653 */ 654 QUICK_RANGE_SELECT *cpk_quick; 655 656 MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */ 657 THD *thd; /* current thread */ 658 bool need_to_fetch_row; /* if true, do retrieve full table records. */ 659 /* in top-level quick select, true if merged scans where initialized */ 660 bool scans_inited; 661 }; 662 663 664 /* 665 Rowid-Ordered Retrieval index union select. 666 This quick select produces union of row sequences returned by several 667 quick select it "merges". 668 669 All merged quick selects must return rowids in rowid order. 670 QUICK_ROR_UNION_SELECT will return rows in rowid order, too. 671 672 All merged quick selects are set not to retrieve full table records. 673 ROR-union quick select always retrieves full records. 674 675 */ 676 677 class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I 678 { 679 public: 680 QUICK_ROR_UNION_SELECT(THD *thd, TABLE *table); 681 ~QUICK_ROR_UNION_SELECT(); 682 683 int init(); 684 int reset(void); 685 int get_next(); reverse_sorted()686 bool reverse_sorted() { return false; } unique_key_range()687 bool unique_key_range() { return false; } get_type()688 int get_type() { return QS_TYPE_ROR_UNION; } 689 void add_keys_and_lengths(String *key_names, String *used_lengths); 690 void add_info_string(String *str); 691 bool is_keys_used(const MY_BITMAP *fields); 692 #ifndef DBUG_OFF 693 void dbug_dump(int indent, bool verbose); 694 #endif 695 696 bool push_quick_back(QUICK_SELECT_I *quick_sel_range); 697 698 List<QUICK_SELECT_I> quick_selects; /* Merged quick selects */ 699 is_valid()700 virtual bool is_valid() 701 { 702 List_iterator_fast<QUICK_SELECT_I> it(quick_selects); 703 QUICK_SELECT_I *quick; 704 bool valid= true; 705 while ((quick= it++)) 706 { 707 if (!quick->is_valid()) 708 { 709 valid= false; 710 break; 711 } 712 } 713 return valid; 714 } 715 716 QUEUE queue; /* Priority queue for merge operation */ 717 MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */ 718 719 THD *thd; /* current thread */ 720 uchar *cur_rowid; /* buffer used in get_next() */ 721 uchar *prev_rowid; /* rowid of last row returned by get_next() */ 722 bool have_prev_rowid; /* true if prev_rowid has valid data */ 723 uint rowid_length; /* table rowid length */ 724 private: 725 bool scans_inited; 726 }; 727 728 729 /* 730 Index scan for GROUP-BY queries with MIN/MAX aggregate functions. 731 732 This class provides a specialized index access method for GROUP-BY queries 733 of the forms: 734 735 SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)] 736 FROM T 737 WHERE [RNG(A_1,...,A_p ; where p <= k)] 738 [AND EQ(B_1,...,B_m)] 739 [AND PC(C)] 740 [AND PA(A_i1,...,A_iq)] 741 GROUP BY A_1,...,A_k; 742 743 or 744 745 SELECT DISTINCT A_i1,...,A_ik 746 FROM T 747 WHERE [RNG(A_1,...,A_p ; where p <= k)] 748 [AND PA(A_i1,...,A_iq)]; 749 750 where all selected fields are parts of the same index. 751 The class of queries that can be processed by this quick select is fully 752 specified in the description of get_best_trp_group_min_max() in opt_range.cc. 753 754 The get_next() method directly produces result tuples, thus obviating the 755 need to call end_send_group() because all grouping is already done inside 756 get_next(). 757 758 Since one of the requirements is that all select fields are part of the same 759 index, this class produces only index keys, and not complete records. 760 */ 761 762 class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I 763 { 764 private: 765 handler * const file; /* The handler used to get data. */ 766 JOIN *join; /* Descriptor of the current query */ 767 KEY *index_info; /* The index chosen for data access */ 768 uchar *record; /* Buffer where the next record is returned. */ 769 uchar *tmp_record; /* Temporary storage for next_min(), next_max(). */ 770 uchar *group_prefix; /* Key prefix consisting of the GROUP fields. */ 771 const uint group_prefix_len; /* Length of the group prefix. */ 772 uint group_key_parts; /* A number of keyparts in the group prefix */ 773 uchar *last_prefix; /* Prefix of the last group for detecting EOF. */ 774 bool have_min; /* Specify whether we are computing */ 775 bool have_max; /* a MIN, a MAX, or both. */ 776 bool have_agg_distinct;/* aggregate_function(DISTINCT ...). */ 777 bool seen_first_key; /* Denotes whether the first key was retrieved.*/ 778 KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */ 779 /* of all MIN/MAX functions. */ 780 uint min_max_arg_len; /* The length of the MIN/MAX argument field */ 781 uchar *key_infix; /* Infix of constants from equality predicates. */ 782 uint key_infix_len; 783 DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */ 784 uint real_prefix_len; /* Length of key prefix extended with key_infix. */ 785 uint real_key_parts; /* A number of keyparts in the above value. */ 786 List<Item_sum> *min_functions; 787 List<Item_sum> *max_functions; 788 List_iterator<Item_sum> *min_functions_it; 789 List_iterator<Item_sum> *max_functions_it; 790 /* 791 Use index scan to get the next different key instead of jumping into it 792 through index read 793 */ 794 bool is_index_scan; 795 public: 796 /* 797 The following two members are public to allow easy access from 798 TRP_GROUP_MIN_MAX::make_quick() 799 */ 800 MEM_ROOT alloc; /* Memory pool for this and quick_prefix_select data. */ 801 QUICK_RANGE_SELECT *quick_prefix_select;/* For retrieval of group prefixes. */ 802 private: 803 int next_prefix(); 804 int next_min_in_range(); 805 int next_max_in_range(); 806 int next_min(); 807 int next_max(); 808 void update_min_result(); 809 void update_max_result(); 810 public: 811 QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min, 812 bool have_max, bool have_agg_distinct, 813 KEY_PART_INFO *min_max_arg_part, 814 uint group_prefix_len, uint group_key_parts, 815 uint used_key_parts, KEY *index_info, uint 816 use_index, double read_cost, ha_rows records, uint 817 key_infix_len, uchar *key_infix, MEM_ROOT 818 *parent_alloc, bool is_index_scan); 819 ~QUICK_GROUP_MIN_MAX_SELECT(); 820 bool add_range(SEL_ARG *sel_range); 821 void update_key_stat(); 822 void adjust_prefix_ranges(); 823 bool alloc_buffers(); 824 int init(); 825 int reset(); 826 int get_next(); reverse_sorted()827 bool reverse_sorted() { return false; } unique_key_range()828 bool unique_key_range() { return false; } get_type()829 int get_type() { return QS_TYPE_GROUP_MIN_MAX; } 830 void add_keys_and_lengths(String *key_names, String *used_lengths); 831 #ifndef DBUG_OFF 832 void dbug_dump(int indent, bool verbose); 833 #endif is_agg_distinct()834 bool is_agg_distinct() { return have_agg_distinct; } append_loose_scan_type(String * str)835 virtual void append_loose_scan_type(String *str) 836 { 837 if (is_index_scan) 838 str->append(STRING_WITH_LEN(" (scanning)")); 839 } 840 }; 841 842 843 class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT 844 { 845 public: 846 QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts); 847 int get_next(); reverse_sorted()848 bool reverse_sorted() { return 1; } get_type()849 int get_type() { return QS_TYPE_RANGE_DESC; } make_reverse(uint used_key_parts_arg)850 QUICK_SELECT_I *make_reverse(uint used_key_parts_arg) 851 { 852 return this; // is already reverse sorted 853 } 854 private: 855 bool range_reads_after_key(QUICK_RANGE *range); reset(void)856 int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); } 857 List<QUICK_RANGE> rev_ranges; 858 List_iterator<QUICK_RANGE> rev_it; 859 uint used_key_parts; 860 }; 861 862 863 class SQL_SELECT :public Sql_alloc { 864 public: 865 QUICK_SELECT_I *quick; // If quick-select used 866 COND *cond; // where condition 867 TABLE *head; 868 IO_CACHE file; // Positions to used records 869 ha_rows records; // Records in use if read from file 870 double read_time; // Time to read rows 871 key_map quick_keys; // Possible quick keys 872 key_map needed_reg; // Possible quick keys after prev tables. 873 table_map const_tables,read_tables; 874 bool free_cond; 875 876 SQL_SELECT(); 877 ~SQL_SELECT(); 878 void cleanup(); set_quick(QUICK_SELECT_I * new_quick)879 void set_quick(QUICK_SELECT_I *new_quick) { delete quick; quick= new_quick; } check_quick(THD * thd,bool force_quick_range,ha_rows limit)880 bool check_quick(THD *thd, bool force_quick_range, ha_rows limit) 881 { 882 key_map tmp; 883 tmp.set_all(); 884 return test_quick_select(thd, tmp, 0, limit, force_quick_range) < 0; 885 } skip_record(THD * thd,bool * skip_record)886 inline bool skip_record(THD *thd, bool *skip_record) 887 { 888 *skip_record= cond ? cond->val_int() == FALSE : FALSE; 889 return thd->is_error(); 890 } 891 int test_quick_select(THD *thd, key_map keys, table_map prev_tables, 892 ha_rows limit, bool force_quick_range); 893 }; 894 895 896 class FT_SELECT: public QUICK_RANGE_SELECT { 897 public: FT_SELECT(THD * thd,TABLE * table,uint key)898 FT_SELECT(THD *thd, TABLE *table, uint key) : 899 QUICK_RANGE_SELECT (thd, table, key, 1) { (void) init(); } ~FT_SELECT()900 ~FT_SELECT() { file->ft_end(); } init()901 int init() { return error=file->ft_init(); } reset()902 int reset() { return 0; } get_next()903 int get_next() { return error=file->ft_read(record); } get_type()904 int get_type() { return QS_TYPE_FULLTEXT; } 905 }; 906 907 QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table, 908 struct st_table_ref *ref, 909 ha_rows records); 910 SQL_SELECT *make_select(TABLE *head, table_map const_tables, 911 table_map read_tables, COND *conds, 912 bool allow_null_cond, int *error); 913 914 #ifdef WITH_PARTITION_STORAGE_ENGINE 915 bool prune_partitions(THD *thd, TABLE *table, Item *pprune_cond); 916 void store_key_image_to_rec(Field *field, uchar *ptr, uint len); 917 #endif 918 919 extern String null_string; 920 921 #endif 922