1 /* 2 Copyright (c) 2011, 2012, Monty Program Ab 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 Street, Fifth Floor, Boston, MA 02110-1335 USA */ 16 17 /* 18 This file contains declarations for implementations 19 of block based join algorithms 20 */ 21 22 #define JOIN_CACHE_INCREMENTAL_BIT 1 23 #define JOIN_CACHE_HASHED_BIT 2 24 #define JOIN_CACHE_BKA_BIT 4 25 26 /* 27 Categories of data fields of variable length written into join cache buffers. 28 The value of any of these fields is written into cache together with the 29 prepended length of the value. 30 */ 31 #define CACHE_BLOB 1 /* blob field */ 32 #define CACHE_STRIPPED 2 /* field stripped of trailing spaces */ 33 #define CACHE_VARSTR1 3 /* short string value (length takes 1 byte) */ 34 #define CACHE_VARSTR2 4 /* long string value (length takes 2 bytes) */ 35 #define CACHE_ROWID 5 /* ROWID field */ 36 37 /* 38 The CACHE_FIELD structure used to describe fields of records that 39 are written into a join cache buffer from record buffers and backward. 40 */ 41 typedef struct st_cache_field { 42 uchar *str; /**< buffer from/to where the field is to be copied */ 43 uint length; /**< maximal number of bytes to be copied from/to str */ 44 /* 45 Field object for the moved field 46 (0 - for a flag field, see JOIN_CACHE::create_flag_fields). 47 */ 48 Field *field; 49 uint type; /**< category of the of the copied field (CACHE_BLOB et al.) */ 50 /* 51 The number of the record offset value for the field in the sequence 52 of offsets placed after the last field of the record. These 53 offset values are used to access fields referred to from other caches. 54 If the value is 0 then no offset for the field is saved in the 55 trailing sequence of offsets. 56 */ 57 uint referenced_field_no; 58 /* The remaining structure fields are used as containers for temp values */ 59 uint blob_length; /**< length of the blob to be copied */ 60 uint offset; /**< field offset to be saved in cache buffer */ 61 } CACHE_FIELD; 62 63 64 class JOIN_TAB_SCAN; 65 66 class EXPLAIN_BKA_TYPE; 67 68 /* 69 JOIN_CACHE is the base class to support the implementations of 70 - Block Nested Loop (BNL) Join Algorithm, 71 - Block Nested Loop Hash (BNLH) Join Algorithm, 72 - Batched Key Access (BKA) Join Algorithm. 73 74 The first algorithm is supported by the derived class JOIN_CACHE_BNL, 75 the second algorithm is supported by the derived class JOIN_CACHE_BNLH, 76 while the third algorithm is implemented in two variant supported by 77 the classes JOIN_CACHE_BKA and JOIN_CACHE_BKAH. 78 These three algorithms have a lot in common. Each of them first accumulates 79 the records of the left join operand in a join buffer and then searches for 80 matching rows of the second operand for all accumulated records. 81 For the first two algorithms this strategy saves on logical I/O operations: 82 the entire set of records from the join buffer requires only one look-through 83 of the records provided by the second operand. 84 For the third algorithm the accumulation of records allows to optimize 85 fetching rows of the second operand from disk for some engines (MyISAM, 86 InnoDB), or to minimize the number of round-trips between the Server and 87 the engine nodes. 88 */ 89 90 class JOIN_CACHE :public Sql_alloc 91 { 92 93 private: 94 95 /* Size of the offset of a record from the cache */ 96 uint size_of_rec_ofs; 97 /* Size of the length of a record in the cache */ 98 uint size_of_rec_len; 99 /* Size of the offset of a field within a record in the cache */ 100 uint size_of_fld_ofs; 101 102 /* This structure is used only for explain, not for execution */ 103 bool for_explain_only; 104 105 protected: 106 107 /* 3 functions below actually do not use the hidden parameter 'this' */ 108 109 /* Calculate the number of bytes used to store an offset value */ offset_size(size_t len)110 uint offset_size(size_t len) 111 { return (len < 256 ? 1 : len < 256*256 ? 2 : 4); } 112 113 /* Get the offset value that takes ofs_sz bytes at the position ptr */ get_offset(uint ofs_sz,uchar * ptr)114 ulong get_offset(uint ofs_sz, uchar *ptr) 115 { 116 switch (ofs_sz) { 117 case 1: return uint(*ptr); 118 case 2: return uint2korr(ptr); 119 case 4: return uint4korr(ptr); 120 } 121 return 0; 122 } 123 124 /* Set the offset value ofs that takes ofs_sz bytes at the position ptr */ store_offset(uint ofs_sz,uchar * ptr,ulong ofs)125 void store_offset(uint ofs_sz, uchar *ptr, ulong ofs) 126 { 127 switch (ofs_sz) { 128 case 1: *ptr= (uchar) ofs; return; 129 case 2: int2store(ptr, (uint16) ofs); return; 130 case 4: int4store(ptr, (uint32) ofs); return; 131 } 132 } 133 134 /* 135 The maximum total length of the fields stored for a record in the cache. 136 For blob fields only the sizes of the blob lengths are taken into account. 137 */ 138 uint length; 139 140 /* 141 Representation of the executed multi-way join through which all needed 142 context can be accessed. 143 */ 144 JOIN *join; 145 146 /* 147 JOIN_TAB of the first table that can have it's fields in the join cache. 148 That is, tables in the [start_tab, tab) range can have their fields in the 149 join cache. 150 If a join tab in the range represents an SJM-nest, then all tables from the 151 nest can have their fields in the join cache, too. 152 */ 153 JOIN_TAB *start_tab; 154 155 /* 156 The total number of flag and data fields that can appear in a record 157 written into the cache. Fields with null values are always skipped 158 to save space. 159 */ 160 uint fields; 161 162 /* 163 The total number of flag fields in a record put into the cache. They are 164 used for table null bitmaps, table null row flags, and an optional match 165 flag. Flag fields go before other fields in a cache record with the match 166 flag field placed always at the very beginning of the record. 167 */ 168 uint flag_fields; 169 170 /* The total number of blob fields that are written into the cache */ 171 uint blobs; 172 173 /* 174 The total number of fields referenced from field descriptors for other join 175 caches. These fields are used to construct key values. 176 When BKA join algorithm is employed the constructed key values serve to 177 access matching rows with index lookups. 178 The key values are put into a hash table when the BNLH join algorithm 179 is employed and when BKAH is used for the join operation. 180 */ 181 uint referenced_fields; 182 183 /* 184 The current number of already created data field descriptors. 185 This number can be useful for implementations of the init methods. 186 */ 187 uint data_field_count; 188 189 /* 190 The current number of already created pointers to the data field 191 descriptors. This number can be useful for implementations of 192 the init methods. 193 */ 194 uint data_field_ptr_count; 195 196 /* 197 Array of the descriptors of fields containing 'fields' elements. 198 These are all fields that are stored for a record in the cache. 199 */ 200 CACHE_FIELD *field_descr; 201 202 /* 203 Array of pointers to the blob descriptors that contains 'blobs' elements. 204 */ 205 CACHE_FIELD **blob_ptr; 206 207 /* 208 This flag indicates that records written into the join buffer contain 209 a match flag field. The flag must be set by the init method. 210 Currently any implementation of the virtial init method calls 211 the function JOIN_CACHE::calc_record_fields() to set this flag. 212 */ 213 bool with_match_flag; 214 /* 215 This flag indicates that any record is prepended with the length of the 216 record which allows us to skip the record or part of it without reading. 217 */ 218 bool with_length; 219 220 /* 221 The maximal number of bytes used for a record representation in 222 the cache excluding the space for blob data. 223 For future derived classes this representation may contains some 224 redundant info such as a key value associated with the record. 225 */ 226 uint pack_length; 227 /* 228 The value of pack_length incremented by the total size of all 229 pointers of a record in the cache to the blob data. 230 */ 231 uint pack_length_with_blob_ptrs; 232 233 /* 234 The total size of the record base prefix. The base prefix of record may 235 include the following components: 236 - the length of the record 237 - the link to a record in a previous buffer. 238 Each record in the buffer are supplied with the same set of the components. 239 */ 240 uint base_prefix_length; 241 242 /* 243 The expected length of a record in the join buffer together with 244 all prefixes and postfixes 245 */ 246 size_t avg_record_length; 247 248 /* The expected size of the space per record in the auxiliary buffer */ 249 size_t avg_aux_buffer_incr; 250 251 /* Expected join buffer space used for one record */ 252 size_t space_per_record; 253 254 /* Pointer to the beginning of the join buffer */ 255 uchar *buff; 256 /* 257 Size of the entire memory allocated for the join buffer. 258 Part of this memory may be reserved for the auxiliary buffer. 259 */ 260 size_t buff_size; 261 /* The minimal join buffer size when join buffer still makes sense to use */ 262 size_t min_buff_size; 263 /* The maximum expected size if the join buffer to be used */ 264 size_t max_buff_size; 265 /* Size of the auxiliary buffer */ 266 size_t aux_buff_size; 267 268 /* The number of records put into the join buffer */ 269 size_t records; 270 /* 271 The number of records in the fully refilled join buffer of 272 the minimal size equal to min_buff_size 273 */ 274 size_t min_records; 275 /* 276 The maximum expected number of records to be put in the join buffer 277 at one refill 278 */ 279 size_t max_records; 280 281 /* 282 Pointer to the current position in the join buffer. 283 This member is used both when writing to buffer and 284 when reading from it. 285 */ 286 uchar *pos; 287 /* 288 Pointer to the first free position in the join buffer, 289 right after the last record into it. 290 */ 291 uchar *end_pos; 292 293 /* 294 Pointer to the beginning of the first field of the current read/write 295 record from the join buffer. The value is adjusted by the 296 get_record/put_record functions. 297 */ 298 uchar *curr_rec_pos; 299 /* 300 Pointer to the beginning of the first field of the last record 301 from the join buffer. 302 */ 303 uchar *last_rec_pos; 304 305 /* 306 Flag is set if the blob data for the last record in the join buffer 307 is in record buffers rather than in the join cache. 308 */ 309 bool last_rec_blob_data_is_in_rec_buff; 310 311 /* 312 Pointer to the position to the current record link. 313 Record links are used only with linked caches. Record links allow to set 314 connections between parts of one join record that are stored in different 315 join buffers. 316 In the simplest case a record link is just a pointer to the beginning of 317 the record stored in the buffer. 318 In a more general case a link could be a reference to an array of pointers 319 to records in the buffer. 320 */ 321 uchar *curr_rec_link; 322 323 /* 324 This flag is set to TRUE if join_tab is the first inner table of an outer 325 join and the latest record written to the join buffer is detected to be 326 null complemented after checking on conditions over the outer tables for 327 this outer join operation 328 */ 329 bool last_written_is_null_compl; 330 331 /* 332 The number of fields put in the join buffer of the join cache that are 333 used in building keys to access the table join_tab 334 */ 335 uint local_key_arg_fields; 336 /* 337 The total number of the fields in the previous caches that are used 338 in building keys to access the table join_tab 339 */ 340 uint external_key_arg_fields; 341 342 /* 343 This flag indicates that the key values will be read directly from the join 344 buffer. It will save us building key values in the key buffer. 345 */ 346 bool use_emb_key; 347 /* The length of an embedded key value */ 348 uint emb_key_length; 349 350 /* 351 This object provides the methods to iterate over records of 352 the joined table join_tab when looking for join matches between 353 records from join buffer and records from join_tab. 354 BNL and BNLH join algorithms retrieve all records from join_tab, 355 while BKA/BKAH algorithm iterates only over those records from 356 join_tab that can be accessed by look-ups with join keys built 357 from records in join buffer. 358 */ 359 JOIN_TAB_SCAN *join_tab_scan; 360 361 void calc_record_fields(); 362 void collect_info_on_key_args(); 363 int alloc_fields(); 364 void create_flag_fields(); 365 void create_key_arg_fields(); 366 void create_remaining_fields(); 367 void set_constants(); 368 int alloc_buffer(); 369 370 /* Shall reallocate the join buffer */ 371 virtual int realloc_buffer(); 372 373 /* Check the possibility to read the access keys directly from join buffer */ 374 bool check_emb_key_usage(); 375 get_size_of_rec_offset()376 uint get_size_of_rec_offset() { return size_of_rec_ofs; } get_size_of_rec_length()377 uint get_size_of_rec_length() { return size_of_rec_len; } get_size_of_fld_offset()378 uint get_size_of_fld_offset() { return size_of_fld_ofs; } 379 get_rec_ref(uchar * ptr)380 uchar *get_rec_ref(uchar *ptr) 381 { 382 return buff+get_offset(size_of_rec_ofs, ptr-size_of_rec_ofs); 383 } get_rec_length(uchar * ptr)384 ulong get_rec_length(uchar *ptr) 385 { 386 return (ulong) get_offset(size_of_rec_len, ptr); 387 } get_fld_offset(uchar * ptr)388 ulong get_fld_offset(uchar *ptr) 389 { 390 return (ulong) get_offset(size_of_fld_ofs, ptr); 391 } 392 store_rec_ref(uchar * ptr,uchar * ref)393 void store_rec_ref(uchar *ptr, uchar* ref) 394 { 395 store_offset(size_of_rec_ofs, ptr-size_of_rec_ofs, (ulong) (ref-buff)); 396 } store_rec_length(uchar * ptr,ulong len)397 void store_rec_length(uchar *ptr, ulong len) 398 { 399 store_offset(size_of_rec_len, ptr, len); 400 } store_fld_offset(uchar * ptr,ulong ofs)401 void store_fld_offset(uchar *ptr, ulong ofs) 402 { 403 store_offset(size_of_fld_ofs, ptr, ofs); 404 } 405 406 /* Write record fields and their required offsets into the join buffer */ 407 uint write_record_data(uchar *link, bool *is_full); 408 409 /* Get the total length of all prefixes of a record in the join buffer */ get_prefix_length()410 virtual uint get_prefix_length() { return base_prefix_length; } 411 /* Get maximum total length of all affixes of a record in the join buffer */ 412 virtual uint get_record_max_affix_length(); 413 414 /* 415 Shall get maximum size of the additional space per record used for 416 record keys 417 */ get_max_key_addon_space_per_record()418 virtual uint get_max_key_addon_space_per_record() { return 0; } 419 420 /* 421 This method must determine for how much the auxiliary buffer should be 422 incremented when a new record is added to the join buffer. 423 If no auxiliary buffer is needed the function should return 0. 424 */ 425 virtual uint aux_buffer_incr(size_t recno); 426 427 /* Shall calculate how much space is remaining in the join buffer */ rem_space()428 virtual size_t rem_space() 429 { 430 return MY_MAX(buff_size-(end_pos-buff)-aux_buff_size,0); 431 } 432 433 /* 434 Shall calculate how much space is taken by allocation of the key 435 for a record in the join buffer 436 */ extra_key_length()437 virtual uint extra_key_length() { return 0; } 438 439 /* Read all flag and data fields of a record from the join buffer */ 440 uint read_all_record_fields(); 441 442 /* Read all flag fields of a record from the join buffer */ 443 uint read_flag_fields(); 444 445 /* Read a data record field from the join buffer */ 446 uint read_record_field(CACHE_FIELD *copy, bool last_record); 447 448 /* Read a referenced field from the join buffer */ 449 bool read_referenced_field(CACHE_FIELD *copy, uchar *rec_ptr, uint *len); 450 451 /* 452 Shall skip record from the join buffer if its match flag 453 is set to MATCH_FOUND 454 */ 455 virtual bool skip_if_matched(); 456 457 /* 458 Shall skip record from the join buffer if its match flag 459 commands to do so 460 */ 461 virtual bool skip_if_not_needed_match(); 462 463 /* 464 True if rec_ptr points to the record whose blob data stay in 465 record buffers 466 */ blob_data_is_in_rec_buff(uchar * rec_ptr)467 bool blob_data_is_in_rec_buff(uchar *rec_ptr) 468 { 469 return rec_ptr == last_rec_pos && last_rec_blob_data_is_in_rec_buff; 470 } 471 472 /* Find matches from the next table for records from the join buffer */ 473 virtual enum_nested_loop_state join_matching_records(bool skip_last); 474 475 /* Shall set an auxiliary buffer up (currently used only by BKA joins) */ setup_aux_buffer(HANDLER_BUFFER & aux_buff)476 virtual int setup_aux_buffer(HANDLER_BUFFER &aux_buff) 477 { 478 DBUG_ASSERT(0); 479 return 0; 480 } 481 482 /* 483 Shall get the number of ranges in the cache buffer passed 484 to the MRR interface 485 */ get_number_of_ranges_for_mrr()486 virtual uint get_number_of_ranges_for_mrr() { return 0; }; 487 488 /* 489 Shall prepare to look for records from the join cache buffer that would 490 match the record of the joined table read into the record buffer 491 */ 492 virtual bool prepare_look_for_matches(bool skip_last)= 0; 493 /* 494 Shall return a pointer to the record from join buffer that is checked 495 as the next candidate for a match with the current record from join_tab. 496 Each implementation of this virtual function should bare in mind 497 that the record position it returns shall be exactly the position 498 passed as the parameter to the implementations of the virtual functions 499 skip_next_candidate_for_match and read_next_candidate_for_match. 500 */ 501 virtual uchar *get_next_candidate_for_match()= 0; 502 /* 503 Shall check whether the given record from the join buffer has its match 504 flag settings commands to skip the record in the buffer. 505 */ 506 virtual bool skip_next_candidate_for_match(uchar *rec_ptr)= 0; 507 /* 508 Shall read the given record from the join buffer into the 509 the corresponding record buffer 510 */ 511 virtual void read_next_candidate_for_match(uchar *rec_ptr)= 0; 512 513 /* 514 Shall return the location of the association label returned by 515 the multi_read_range_next function for the current record loaded 516 into join_tab's record buffer 517 */ get_curr_association_ptr()518 virtual uchar **get_curr_association_ptr() { return 0; }; 519 520 /* Add null complements for unmatched outer records from the join buffer */ 521 virtual enum_nested_loop_state join_null_complements(bool skip_last); 522 523 /* Restore the fields of the last record from the join buffer */ 524 virtual void restore_last_record(); 525 526 /* Set match flag for a record in join buffer if it has not been set yet */ 527 bool set_match_flag_if_none(JOIN_TAB *first_inner, uchar *rec_ptr); 528 529 enum_nested_loop_state generate_full_extensions(uchar *rec_ptr); 530 531 /* Check matching to a partial join record from the join buffer */ 532 bool check_match(uchar *rec_ptr); 533 534 /* 535 This constructor creates an unlinked join cache. The cache is to be 536 used to join table 'tab' to the result of joining the previous tables 537 specified by the 'j' parameter. 538 */ JOIN_CACHE(JOIN * j,JOIN_TAB * tab)539 JOIN_CACHE(JOIN *j, JOIN_TAB *tab) 540 { 541 join= j; 542 join_tab= tab; 543 prev_cache= next_cache= 0; 544 buff= 0; 545 } 546 547 /* 548 This constructor creates a linked join cache. The cache is to be 549 used to join table 'tab' to the result of joining the previous tables 550 specified by the 'j' parameter. The parameter 'prev' specifies the previous 551 cache object to which this cache is linked. 552 */ JOIN_CACHE(JOIN * j,JOIN_TAB * tab,JOIN_CACHE * prev)553 JOIN_CACHE(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) 554 { 555 join= j; 556 join_tab= tab; 557 next_cache= 0; 558 prev_cache= prev; 559 buff= 0; 560 if (prev) 561 prev->next_cache= this; 562 } 563 564 public: 565 566 /* 567 The enumeration type Join_algorithm includes a mnemonic constant for 568 each join algorithm that employs join buffers 569 */ 570 571 enum Join_algorithm 572 { 573 BNL_JOIN_ALG, /* Block Nested Loop Join algorithm */ 574 BNLH_JOIN_ALG, /* Block Nested Loop Hash Join algorithm */ 575 BKA_JOIN_ALG, /* Batched Key Access Join algorithm */ 576 BKAH_JOIN_ALG /* Batched Key Access with Hash Table Join Algorithm */ 577 }; 578 579 /* 580 The enumeration type Match_flag describes possible states of the match flag 581 field stored for the records of the first inner tables of outer joins and 582 semi-joins in the cases when the first match strategy is used for them. 583 When a record with match flag field is written into the join buffer the 584 state of the field usually is MATCH_NOT_FOUND unless this is a record of the 585 first inner table of the outer join for which the on precondition (the 586 condition from on expression over outer tables) has turned out not to be 587 true. In the last case the state of the match flag is MATCH_IMPOSSIBLE. 588 The state of the match flag field is changed to MATCH_FOUND as soon as 589 the first full matching combination of inner tables of the outer join or 590 the semi-join is discovered. 591 */ 592 enum Match_flag { MATCH_NOT_FOUND, MATCH_FOUND, MATCH_IMPOSSIBLE }; 593 594 /* Table to be joined with the partial join records from the cache */ 595 JOIN_TAB *join_tab; 596 597 /* Pointer to the previous join cache if there is any */ 598 JOIN_CACHE *prev_cache; 599 /* Pointer to the next join cache if there is any */ 600 JOIN_CACHE *next_cache; 601 602 /* Shall initialize the join cache structure */ 603 virtual int init(bool for_explain); 604 605 /* Get the current size of the cache join buffer */ get_join_buffer_size()606 size_t get_join_buffer_size() { return buff_size; } 607 /* Set the size of the cache join buffer to a new value */ set_join_buffer_size(size_t sz)608 void set_join_buffer_size(size_t sz) { buff_size= sz; } 609 610 /* Get the minimum possible size of the cache join buffer */ 611 virtual size_t get_min_join_buffer_size(); 612 /* Get the maximum possible size of the cache join buffer */ 613 virtual size_t get_max_join_buffer_size(bool optimize_buff_size); 614 615 /* Shrink the size if the cache join buffer in a given ratio */ 616 bool shrink_join_buffer_in_ratio(ulonglong n, ulonglong d); 617 618 /* Shall return the type of the employed join algorithm */ 619 virtual enum Join_algorithm get_join_alg()= 0; 620 621 /* 622 The function shall return TRUE only when there is a key access 623 to the join table 624 */ 625 virtual bool is_key_access()= 0; 626 627 /* Shall reset the join buffer for reading/writing */ 628 virtual void reset(bool for_writing); 629 630 /* 631 This function shall add a record into the join buffer and return TRUE 632 if it has been decided that it should be the last record in the buffer. 633 */ 634 virtual bool put_record(); 635 636 /* 637 This function shall read the next record into the join buffer and return 638 TRUE if there is no more next records. 639 */ 640 virtual bool get_record(); 641 642 /* 643 This function shall read the record at the position rec_ptr 644 in the join buffer 645 */ 646 virtual void get_record_by_pos(uchar *rec_ptr); 647 648 /* Shall return the value of the match flag for the positioned record */ 649 virtual enum Match_flag get_match_flag_by_pos(uchar *rec_ptr); 650 651 /* 652 Shall return the value of the match flag for the positioned record 653 from the join buffer attached to the specified table 654 */ 655 virtual enum Match_flag 656 get_match_flag_by_pos_from_join_buffer(uchar *rec_ptr, JOIN_TAB *tab); 657 658 /* Shall return the position of the current record */ get_curr_rec()659 virtual uchar *get_curr_rec() { return curr_rec_pos; } 660 661 /* Shall set the current record link */ set_curr_rec_link(uchar * link)662 virtual void set_curr_rec_link(uchar *link) { curr_rec_link= link; } 663 664 /* Shall return the current record link */ get_curr_rec_link()665 virtual uchar *get_curr_rec_link() 666 { 667 return (curr_rec_link ? curr_rec_link : get_curr_rec()); 668 } 669 670 /* Join records from the join buffer with records from the next join table */ 671 enum_nested_loop_state join_records(bool skip_last); 672 673 /* Add a comment on the join algorithm employed by the join cache */ 674 virtual bool save_explain_data(EXPLAIN_BKA_TYPE *explain); 675 676 THD *thd(); 677 ~JOIN_CACHE()678 virtual ~JOIN_CACHE() {} reset_join(JOIN * j)679 void reset_join(JOIN *j) { join= j; } free()680 void free() 681 { 682 my_free(buff); 683 buff= 0; 684 } 685 686 friend class JOIN_CACHE_HASHED; 687 friend class JOIN_CACHE_BNL; 688 friend class JOIN_CACHE_BKA; 689 friend class JOIN_TAB_SCAN; 690 friend class JOIN_TAB_SCAN_MRR; 691 692 }; 693 694 695 /* 696 The class JOIN_CACHE_HASHED is the base class for the classes 697 JOIN_CACHE_HASHED_BNL and JOIN_CACHE_HASHED_BKA. The first of them supports 698 an implementation of Block Nested Loop Hash (BNLH) Join Algorithm, 699 while the second is used for a variant of the BKA Join algorithm that performs 700 only one lookup for any records from join buffer with the same key value. 701 For a join cache of this class the records from the join buffer that have 702 the same access key are linked into a chain attached to a key entry structure 703 that either itself contains the key value, or, in the case when the keys are 704 embedded, refers to its occurrence in one of the records from the chain. 705 To build the chains with the same keys a hash table is employed. It is placed 706 at the very end of the join buffer. The array of hash entries is allocated 707 first at the very bottom of the join buffer, while key entries are placed 708 before this array. 709 A hash entry contains a header of the list of the key entries with the same 710 hash value. 711 Each key entry is a structure of the following type: 712 struct st_join_cache_key_entry { 713 union { 714 uchar[] value; 715 cache_ref *value_ref; // offset from the beginning of the buffer 716 } hash_table_key; 717 key_ref next_key; // offset backward from the beginning of hash table 718 cache_ref *last_rec // offset from the beginning of the buffer 719 } 720 The references linking the records in a chain are always placed at the very 721 beginning of the record info stored in the join buffer. The records are 722 linked in a circular list. A new record is always added to the end of this 723 list. 724 725 The following picture represents a typical layout for the info stored in the 726 join buffer of a join cache object of the JOIN_CACHE_HASHED class. 727 728 buff 729 V 730 +----------------------------------------------------------------------------+ 731 | |[*]record_1_1| | 732 | ^ | | 733 | | +--------------------------------------------------+ | 734 | | |[*]record_2_1| | | 735 | | ^ | V | 736 | | | +------------------+ |[*]record_1_2| | 737 | | +--------------------+-+ | | 738 |+--+ +---------------------+ | | +-------------+ | 739 || | | V | | | 740 |||[*]record_3_1| |[*]record_1_3| |[*]record_2_2| | | 741 ||^ ^ ^ | | 742 ||+----------+ | | | | 743 ||^ | |<---------------------------+-------------------+ | 744 |++ | | ... mrr | buffer ... ... | | | 745 | | | | | 746 | +-----+--------+ | +-----|-------+ | 747 | V | | | V | | | 748 ||key_3|[/]|[*]| | | |key_2|[/]|[*]| | | 749 | +-+---|-----------------------+ | | 750 | V | | | | | 751 | |key_1|[*]|[*]| | | ... |[*]| ... |[*]| ... | | 752 +----------------------------------------------------------------------------+ 753 ^ ^ ^ 754 | i-th entry j-th entry 755 hash table 756 757 i-th hash entry: 758 circular record chain for key_1: 759 record_1_1 760 record_1_2 761 record_1_3 (points to record_1_1) 762 circular record chain for key_3: 763 record_3_1 (points to itself) 764 765 j-th hash entry: 766 circular record chain for key_2: 767 record_2_1 768 record_2_2 (points to record_2_1) 769 770 */ 771 772 class JOIN_CACHE_HASHED: public JOIN_CACHE 773 { 774 775 typedef uint (JOIN_CACHE_HASHED::*Hash_func) (uchar *key, uint key_len); 776 typedef bool (JOIN_CACHE_HASHED::*Hash_cmp_func) (uchar *key1, uchar *key2, 777 uint key_len); 778 779 private: 780 781 /* Size of the offset of a key entry in the hash table */ 782 uint size_of_key_ofs; 783 784 /* 785 Length of the key entry in the hash table. 786 A key entry either contains the key value, or it contains a reference 787 to the key value if use_emb_key flag is set for the cache. 788 */ 789 uint key_entry_length; 790 791 /* The beginning of the hash table in the join buffer */ 792 uchar *hash_table; 793 /* Number of hash entries in the hash table */ 794 uint hash_entries; 795 796 797 /* The position of the currently retrieved key entry in the hash table */ 798 uchar *curr_key_entry; 799 800 /* The offset of the data fields from the beginning of the record fields */ 801 uint data_fields_offset; 802 803 inline uint get_hash_idx_simple(uchar *key, uint key_len); 804 inline uint get_hash_idx_complex(uchar *key, uint key_len); 805 806 inline bool equal_keys_simple(uchar *key1, uchar *key2, uint key_len); 807 inline bool equal_keys_complex(uchar *key1, uchar *key2, uint key_len); 808 809 int init_hash_table(); 810 void cleanup_hash_table(); 811 812 protected: 813 814 /* 815 Index info on the TABLE_REF object used by the hash join 816 to look for matching records 817 */ 818 KEY *ref_key_info; 819 /* 820 Number of the key parts the TABLE_REF object used by the hash join 821 to look for matching records 822 */ 823 uint ref_used_key_parts; 824 825 /* 826 The hash function used in the hash table, 827 usually set by the init() method 828 */ 829 Hash_func hash_func; 830 /* 831 The function to check whether two key entries in the hash table 832 are equal or not, usually set by the init() method 833 */ 834 Hash_cmp_func hash_cmp_func; 835 836 /* 837 Length of a key value. 838 It is assumed that all key values have the same length. 839 */ 840 uint key_length; 841 /* Buffer to store key values for probing */ 842 uchar *key_buff; 843 844 /* Number of key entries in the hash table (number of distinct keys) */ 845 uint key_entries; 846 847 /* The position of the last key entry in the hash table */ 848 uchar *last_key_entry; 849 850 /* 851 The offset of the record fields from the beginning of the record 852 representation. The record representation starts with a reference to 853 the next record in the key record chain followed by the length of 854 the trailing record data followed by a reference to the record segment 855 in the previous cache, if any, followed by the record fields. 856 */ 857 uint rec_fields_offset; 858 get_size_of_key_offset()859 uint get_size_of_key_offset() { return size_of_key_ofs; } 860 861 /* 862 Get the position of the next_key_ptr field pointed to by 863 a linking reference stored at the position key_ref_ptr. 864 This reference is actually the offset backward from the 865 beginning of hash table. 866 */ get_next_key_ref(uchar * key_ref_ptr)867 uchar *get_next_key_ref(uchar *key_ref_ptr) 868 { 869 return hash_table-get_offset(size_of_key_ofs, key_ref_ptr); 870 } 871 872 /* 873 Store the linking reference to the next_key_ptr field at 874 the position key_ref_ptr. The position of the next_key_ptr 875 field is pointed to by ref. The stored reference is actually 876 the offset backward from the beginning of the hash table. 877 */ store_next_key_ref(uchar * key_ref_ptr,uchar * ref)878 void store_next_key_ref(uchar *key_ref_ptr, uchar *ref) 879 { 880 store_offset(size_of_key_ofs, key_ref_ptr, (ulong) (hash_table-ref)); 881 } 882 883 /* 884 Check whether the reference to the next_key_ptr field at the position 885 key_ref_ptr contains a nil value. 886 */ is_null_key_ref(uchar * key_ref_ptr)887 bool is_null_key_ref(uchar *key_ref_ptr) 888 { 889 ulong nil= 0; 890 return memcmp(key_ref_ptr, &nil, size_of_key_ofs ) == 0; 891 } 892 893 /* 894 Set the reference to the next_key_ptr field at the position 895 key_ref_ptr equal to nil. 896 */ store_null_key_ref(uchar * key_ref_ptr)897 void store_null_key_ref(uchar *key_ref_ptr) 898 { 899 ulong nil= 0; 900 store_offset(size_of_key_ofs, key_ref_ptr, nil); 901 } 902 get_next_rec_ref(uchar * ref_ptr)903 uchar *get_next_rec_ref(uchar *ref_ptr) 904 { 905 return buff+get_offset(get_size_of_rec_offset(), ref_ptr); 906 } 907 store_next_rec_ref(uchar * ref_ptr,uchar * ref)908 void store_next_rec_ref(uchar *ref_ptr, uchar *ref) 909 { 910 store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); 911 } 912 913 /* 914 Get the position of the embedded key value for the current 915 record pointed to by get_curr_rec(). 916 */ get_curr_emb_key()917 uchar *get_curr_emb_key() 918 { 919 return get_curr_rec()+data_fields_offset; 920 } 921 922 /* 923 Get the position of the embedded key value pointed to by a reference 924 stored at ref_ptr. The stored reference is actually the offset from 925 the beginning of the join buffer. 926 */ get_emb_key(uchar * ref_ptr)927 uchar *get_emb_key(uchar *ref_ptr) 928 { 929 return buff+get_offset(get_size_of_rec_offset(), ref_ptr); 930 } 931 932 /* 933 Store the reference to an embedded key at the position key_ref_ptr. 934 The position of the embedded key is pointed to by ref. The stored 935 reference is actually the offset from the beginning of the join buffer. 936 */ store_emb_key_ref(uchar * ref_ptr,uchar * ref)937 void store_emb_key_ref(uchar *ref_ptr, uchar *ref) 938 { 939 store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); 940 } 941 942 /* Get the total length of all prefixes of a record in hashed join buffer */ get_prefix_length()943 uint get_prefix_length() 944 { 945 return base_prefix_length + get_size_of_rec_offset(); 946 } 947 948 /* 949 Get maximum size of the additional space per record used for 950 the hash table with record keys 951 */ 952 uint get_max_key_addon_space_per_record(); 953 954 /* 955 Calculate how much space in the buffer would not be occupied by 956 records, key entries and additional memory for the MMR buffer. 957 */ rem_space()958 size_t rem_space() 959 { 960 return MY_MAX(last_key_entry-end_pos-aux_buff_size,0); 961 } 962 963 /* 964 Calculate how much space is taken by allocation of the key 965 entry for a record in the join buffer 966 */ extra_key_length()967 uint extra_key_length() { return key_entry_length; } 968 969 /* 970 Skip record from a hashed join buffer if its match flag 971 is set to MATCH_FOUND 972 */ 973 bool skip_if_matched(); 974 975 /* 976 Skip record from a hashed join buffer if its match flag setting 977 commands to do so 978 */ 979 bool skip_if_not_needed_match(); 980 981 /* Search for a key in the hash table of the join buffer */ 982 bool key_search(uchar *key, uint key_len, uchar **key_ref_ptr); 983 984 /* Reallocate the join buffer of a hashed join cache */ 985 int realloc_buffer(); 986 987 /* 988 This constructor creates an unlinked hashed join cache. The cache is to be 989 used to join table 'tab' to the result of joining the previous tables 990 specified by the 'j' parameter. 991 */ JOIN_CACHE_HASHED(JOIN * j,JOIN_TAB * tab)992 JOIN_CACHE_HASHED(JOIN *j, JOIN_TAB *tab) :JOIN_CACHE(j, tab) {} 993 994 /* 995 This constructor creates a linked hashed join cache. The cache is to be 996 used to join table 'tab' to the result of joining the previous tables 997 specified by the 'j' parameter. The parameter 'prev' specifies the previous 998 cache object to which this cache is linked. 999 */ JOIN_CACHE_HASHED(JOIN * j,JOIN_TAB * tab,JOIN_CACHE * prev)1000 JOIN_CACHE_HASHED(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) 1001 :JOIN_CACHE(j, tab, prev) {} 1002 1003 public: 1004 1005 /* Initialize a hashed join cache */ 1006 int init(bool for_explain); 1007 1008 /* Reset the buffer of a hashed join cache for reading/writing */ 1009 void reset(bool for_writing); 1010 1011 /* Add a record into the buffer of a hashed join cache */ 1012 bool put_record(); 1013 1014 /* Read the next record from the buffer of a hashed join cache */ 1015 bool get_record(); 1016 1017 /* 1018 Shall check whether all records in a key chain have 1019 their match flags set on 1020 */ 1021 virtual bool check_all_match_flags_for_key(uchar *key_chain_ptr); 1022 1023 uint get_next_key(uchar **key); 1024 1025 /* Get the head of the record chain attached to the current key entry */ get_curr_key_chain()1026 uchar *get_curr_key_chain() 1027 { 1028 return get_next_rec_ref(curr_key_entry+key_entry_length- 1029 get_size_of_rec_offset()); 1030 } 1031 1032 }; 1033 1034 1035 /* 1036 The class JOIN_TAB_SCAN is a companion class for the classes JOIN_CACHE_BNL 1037 and JOIN_CACHE_BNLH. Actually the class implements the iterator over the 1038 table joinded by BNL/BNLH join algorithm. 1039 The virtual functions open, next and close are called for any iteration over 1040 the table. The function open is called to initiate the process of the 1041 iteration. The function next shall read the next record from the joined 1042 table. The record is read into the record buffer of the joined table. 1043 The record is to be matched with records from the join cache buffer. 1044 The function close shall perform the finalizing actions for the iteration. 1045 */ 1046 1047 class JOIN_TAB_SCAN: public Sql_alloc 1048 { 1049 1050 private: 1051 /* TRUE if this is the first record from the joined table to iterate over */ 1052 bool is_first_record; 1053 1054 protected: 1055 1056 /* The joined table to be iterated over */ 1057 JOIN_TAB *join_tab; 1058 /* The join cache used to join the table join_tab */ 1059 JOIN_CACHE *cache; 1060 /* 1061 Representation of the executed multi-way join through which 1062 all needed context can be accessed. 1063 */ 1064 JOIN *join; 1065 1066 public: 1067 JOIN_TAB_SCAN(JOIN * j,JOIN_TAB * tab)1068 JOIN_TAB_SCAN(JOIN *j, JOIN_TAB *tab) 1069 { 1070 join= j; 1071 join_tab= tab; 1072 cache= join_tab->cache; 1073 } 1074 ~JOIN_TAB_SCAN()1075 virtual ~JOIN_TAB_SCAN() {} 1076 1077 /* 1078 Shall calculate the increment of the auxiliary buffer for a record 1079 write if such a buffer is used by the table scan object 1080 */ aux_buffer_incr(size_t recno)1081 virtual uint aux_buffer_incr(size_t recno) { return 0; } 1082 1083 /* Initiate the process of iteration over the joined table */ 1084 virtual int open(); 1085 /* 1086 Shall read the next candidate for matches with records from 1087 the join buffer. 1088 */ 1089 virtual int next(); 1090 /* 1091 Perform the finalizing actions for the process of iteration 1092 over the joined_table. 1093 */ 1094 virtual void close(); 1095 1096 }; 1097 1098 /* 1099 The class JOIN_CACHE_BNL is used when the BNL join algorithm is 1100 employed to perform a join operation 1101 */ 1102 1103 class JOIN_CACHE_BNL :public JOIN_CACHE 1104 { 1105 private: 1106 /* 1107 The number of the records in the join buffer that have to be 1108 checked yet for a match with the current record of join_tab 1109 read into the record buffer. 1110 */ 1111 uint rem_records; 1112 1113 protected: 1114 1115 bool prepare_look_for_matches(bool skip_last); 1116 1117 uchar *get_next_candidate_for_match(); 1118 1119 bool skip_next_candidate_for_match(uchar *rec_ptr); 1120 1121 void read_next_candidate_for_match(uchar *rec_ptr); 1122 1123 public: 1124 1125 /* 1126 This constructor creates an unlinked BNL join cache. The cache is to be 1127 used to join table 'tab' to the result of joining the previous tables 1128 specified by the 'j' parameter. 1129 */ JOIN_CACHE_BNL(JOIN * j,JOIN_TAB * tab)1130 JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab) :JOIN_CACHE(j, tab) {} 1131 1132 /* 1133 This constructor creates a linked BNL join cache. The cache is to be 1134 used to join table 'tab' to the result of joining the previous tables 1135 specified by the 'j' parameter. The parameter 'prev' specifies the previous 1136 cache object to which this cache is linked. 1137 */ JOIN_CACHE_BNL(JOIN * j,JOIN_TAB * tab,JOIN_CACHE * prev)1138 JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) 1139 :JOIN_CACHE(j, tab, prev) {} 1140 1141 /* Initialize the BNL cache */ 1142 int init(bool for_explain); 1143 get_join_alg()1144 enum Join_algorithm get_join_alg() { return BNL_JOIN_ALG; } 1145 is_key_access()1146 bool is_key_access() { return FALSE; } 1147 1148 }; 1149 1150 1151 /* 1152 The class JOIN_CACHE_BNLH is used when the BNLH join algorithm is 1153 employed to perform a join operation 1154 */ 1155 1156 class JOIN_CACHE_BNLH :public JOIN_CACHE_HASHED 1157 { 1158 1159 protected: 1160 1161 /* 1162 The pointer to the last record from the circular list of the records 1163 that match the join key built out of the record in the join buffer for 1164 the join_tab table 1165 */ 1166 uchar *last_matching_rec_ref_ptr; 1167 /* 1168 The pointer to the next current record from the circular list of the 1169 records that match the join key built out of the record in the join buffer 1170 for the join_tab table. This pointer is used by the class method 1171 get_next_candidate_for_match to iterate over records from the circular 1172 list. 1173 */ 1174 uchar *next_matching_rec_ref_ptr; 1175 1176 /* 1177 Get the chain of records from buffer matching the current candidate 1178 record for join 1179 */ 1180 uchar *get_matching_chain_by_join_key(); 1181 1182 bool prepare_look_for_matches(bool skip_last); 1183 1184 uchar *get_next_candidate_for_match(); 1185 1186 bool skip_next_candidate_for_match(uchar *rec_ptr); 1187 1188 void read_next_candidate_for_match(uchar *rec_ptr); 1189 1190 public: 1191 1192 /* 1193 This constructor creates an unlinked BNLH join cache. The cache is to be 1194 used to join table 'tab' to the result of joining the previous tables 1195 specified by the 'j' parameter. 1196 */ JOIN_CACHE_BNLH(JOIN * j,JOIN_TAB * tab)1197 JOIN_CACHE_BNLH(JOIN *j, JOIN_TAB *tab) : JOIN_CACHE_HASHED(j, tab) {} 1198 1199 /* 1200 This constructor creates a linked BNLH join cache. The cache is to be 1201 used to join table 'tab' to the result of joining the previous tables 1202 specified by the 'j' parameter. The parameter 'prev' specifies the previous 1203 cache object to which this cache is linked. 1204 */ JOIN_CACHE_BNLH(JOIN * j,JOIN_TAB * tab,JOIN_CACHE * prev)1205 JOIN_CACHE_BNLH(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) 1206 : JOIN_CACHE_HASHED(j, tab, prev) {} 1207 1208 /* Initialize the BNLH cache */ 1209 int init(bool for_explain); 1210 get_join_alg()1211 enum Join_algorithm get_join_alg() { return BNLH_JOIN_ALG; } 1212 is_key_access()1213 bool is_key_access() { return TRUE; } 1214 1215 }; 1216 1217 1218 /* 1219 The class JOIN_TAB_SCAN_MRR is a companion class for the classes 1220 JOIN_CACHE_BKA and JOIN_CACHE_BKAH. Actually the class implements the 1221 iterator over the records from join_tab selected by BKA/BKAH join 1222 algorithm as the candidates to be joined. 1223 The virtual functions open, next and close are called for any iteration over 1224 join_tab record candidates. The function open is called to initiate the 1225 process of the iteration. The function next shall read the next record from 1226 the set of the record candidates. The record is read into the record buffer 1227 of the joined table. The function close shall perform the finalizing actions 1228 for the iteration. 1229 */ 1230 1231 class JOIN_TAB_SCAN_MRR: public JOIN_TAB_SCAN 1232 { 1233 /* Interface object to generate key ranges for MRR */ 1234 RANGE_SEQ_IF range_seq_funcs; 1235 1236 /* Number of ranges to be processed by the MRR interface */ 1237 uint ranges; 1238 1239 /* Flag to to be passed to the MRR interface */ 1240 uint mrr_mode; 1241 1242 /* MRR buffer assotiated with this join cache */ 1243 HANDLER_BUFFER mrr_buff; 1244 1245 /* Shall initialize the MRR buffer */ init_mrr_buff()1246 virtual void init_mrr_buff() 1247 { 1248 cache->setup_aux_buffer(mrr_buff); 1249 } 1250 1251 public: 1252 JOIN_TAB_SCAN_MRR(JOIN * j,JOIN_TAB * tab,uint flags,RANGE_SEQ_IF rs_funcs)1253 JOIN_TAB_SCAN_MRR(JOIN *j, JOIN_TAB *tab, uint flags, RANGE_SEQ_IF rs_funcs) 1254 :JOIN_TAB_SCAN(j, tab), range_seq_funcs(rs_funcs), mrr_mode(flags) {} 1255 1256 uint aux_buffer_incr(size_t recno); 1257 1258 int open(); 1259 1260 int next(); 1261 1262 friend class JOIN_CACHE_BKA; /* it needs to add an mrr_mode flag after JOIN_CACHE::init() call */ 1263 }; 1264 1265 /* 1266 The class JOIN_CACHE_BKA is used when the BKA join algorithm is 1267 employed to perform a join operation 1268 */ 1269 1270 class JOIN_CACHE_BKA :public JOIN_CACHE 1271 { 1272 private: 1273 1274 /* Flag to to be passed to the companion JOIN_TAB_SCAN_MRR object */ 1275 uint mrr_mode; 1276 1277 /* 1278 This value is set to 1 by the class prepare_look_for_matches method 1279 and back to 0 by the class get_next_candidate_for_match method 1280 */ 1281 uint rem_records; 1282 1283 /* 1284 This field contains the current association label set by a call of 1285 the multi_range_read_next handler function. 1286 See the function JOIN_CACHE_BKA::get_curr_key_association() 1287 */ 1288 uchar *curr_association; 1289 1290 protected: 1291 1292 /* 1293 Get the number of ranges in the cache buffer passed to the MRR 1294 interface. For each record its own range is passed. 1295 */ get_number_of_ranges_for_mrr()1296 uint get_number_of_ranges_for_mrr() { return (uint)records; } 1297 1298 /* 1299 Setup the MRR buffer as the space between the last record put 1300 into the join buffer and the very end of the join buffer 1301 */ setup_aux_buffer(HANDLER_BUFFER & aux_buff)1302 int setup_aux_buffer(HANDLER_BUFFER &aux_buff) 1303 { 1304 aux_buff.buffer= end_pos; 1305 aux_buff.buffer_end= buff+buff_size; 1306 return 0; 1307 } 1308 1309 bool prepare_look_for_matches(bool skip_last); 1310 1311 uchar *get_next_candidate_for_match(); 1312 1313 bool skip_next_candidate_for_match(uchar *rec_ptr); 1314 1315 void read_next_candidate_for_match(uchar *rec_ptr); 1316 1317 public: 1318 1319 /* 1320 This constructor creates an unlinked BKA join cache. The cache is to be 1321 used to join table 'tab' to the result of joining the previous tables 1322 specified by the 'j' parameter. 1323 The MRR mode initially is set to 'flags'. 1324 */ JOIN_CACHE_BKA(JOIN * j,JOIN_TAB * tab,uint flags)1325 JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags) 1326 :JOIN_CACHE(j, tab), mrr_mode(flags) {} 1327 /* 1328 This constructor creates a linked BKA join cache. The cache is to be 1329 used to join table 'tab' to the result of joining the previous tables 1330 specified by the 'j' parameter. The parameter 'prev' specifies the previous 1331 cache object to which this cache is linked. 1332 The MRR mode initially is set to 'flags'. 1333 */ JOIN_CACHE_BKA(JOIN * j,JOIN_TAB * tab,uint flags,JOIN_CACHE * prev)1334 JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE *prev) 1335 :JOIN_CACHE(j, tab, prev), mrr_mode(flags) {} 1336 JOIN_CACHE_BKA(JOIN_CACHE_BKA * bka)1337 JOIN_CACHE_BKA(JOIN_CACHE_BKA *bka) 1338 :JOIN_CACHE(bka->join, bka->join_tab, bka->prev_cache), 1339 mrr_mode(bka->mrr_mode) {} 1340 get_curr_association_ptr()1341 uchar **get_curr_association_ptr() { return &curr_association; } 1342 1343 /* Initialize the BKA cache */ 1344 int init(bool for_explain); 1345 get_join_alg()1346 enum Join_algorithm get_join_alg() { return BKA_JOIN_ALG; } 1347 is_key_access()1348 bool is_key_access() { return TRUE; } 1349 1350 /* Get the key built over the next record from the join buffer */ 1351 uint get_next_key(uchar **key); 1352 1353 /* Check index condition of the joined table for a record from BKA cache */ 1354 bool skip_index_tuple(range_id_t range_info); 1355 1356 bool save_explain_data(EXPLAIN_BKA_TYPE *explain); 1357 }; 1358 1359 1360 1361 /* 1362 The class JOIN_CACHE_BKAH is used when the BKAH join algorithm is 1363 employed to perform a join operation 1364 */ 1365 1366 class JOIN_CACHE_BKAH :public JOIN_CACHE_BNLH 1367 { 1368 1369 private: 1370 /* Flag to to be passed to the companion JOIN_TAB_SCAN_MRR object */ 1371 uint mrr_mode; 1372 1373 /* 1374 This flag is set to TRUE if the implementation of the MRR interface cannot 1375 handle range association labels and does not return them to the caller of 1376 the multi_range_read_next handler function. E.g. the implementation of 1377 the MRR inteface for the Falcon engine could not return association 1378 labels to the caller of multi_range_read_next. 1379 The flag is set by JOIN_CACHE_BKA::init() and is not ever changed. 1380 */ 1381 bool no_association; 1382 1383 /* 1384 This field contains the association label returned by the 1385 multi_range_read_next function. 1386 See the function JOIN_CACHE_BKAH::get_curr_key_association() 1387 */ 1388 uchar *curr_matching_chain; 1389 1390 protected: 1391 get_number_of_ranges_for_mrr()1392 uint get_number_of_ranges_for_mrr() { return key_entries; } 1393 1394 /* 1395 Initialize the MRR buffer allocating some space within the join buffer. 1396 The entire space between the last record put into the join buffer and the 1397 last key entry added to the hash table is used for the MRR buffer. 1398 */ setup_aux_buffer(HANDLER_BUFFER & aux_buff)1399 int setup_aux_buffer(HANDLER_BUFFER &aux_buff) 1400 { 1401 aux_buff.buffer= end_pos; 1402 aux_buff.buffer_end= last_key_entry; 1403 return 0; 1404 } 1405 1406 bool prepare_look_for_matches(bool skip_last); 1407 1408 /* 1409 The implementations of the methods 1410 - get_next_candidate_for_match 1411 - skip_recurrent_candidate_for_match 1412 - read_next_candidate_for_match 1413 are inherited from the JOIN_CACHE_BNLH class 1414 */ 1415 1416 public: 1417 1418 /* 1419 This constructor creates an unlinked BKAH join cache. The cache is to be 1420 used to join table 'tab' to the result of joining the previous tables 1421 specified by the 'j' parameter. 1422 The MRR mode initially is set to 'flags'. 1423 */ JOIN_CACHE_BKAH(JOIN * j,JOIN_TAB * tab,uint flags)1424 JOIN_CACHE_BKAH(JOIN *j, JOIN_TAB *tab, uint flags) 1425 :JOIN_CACHE_BNLH(j, tab), mrr_mode(flags) {} 1426 1427 /* 1428 This constructor creates a linked BKAH join cache. The cache is to be 1429 used to join table 'tab' to the result of joining the previous tables 1430 specified by the 'j' parameter. The parameter 'prev' specifies the previous 1431 cache object to which this cache is linked. 1432 The MRR mode initially is set to 'flags'. 1433 */ JOIN_CACHE_BKAH(JOIN * j,JOIN_TAB * tab,uint flags,JOIN_CACHE * prev)1434 JOIN_CACHE_BKAH(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE *prev) 1435 :JOIN_CACHE_BNLH(j, tab, prev), mrr_mode(flags) {} 1436 JOIN_CACHE_BKAH(JOIN_CACHE_BKAH * bkah)1437 JOIN_CACHE_BKAH(JOIN_CACHE_BKAH *bkah) 1438 :JOIN_CACHE_BNLH(bkah->join, bkah->join_tab, bkah->prev_cache), 1439 mrr_mode(bkah->mrr_mode) {} 1440 get_curr_association_ptr()1441 uchar **get_curr_association_ptr() { return &curr_matching_chain; } 1442 1443 /* Initialize the BKAH cache */ 1444 int init(bool for_explain); 1445 get_join_alg()1446 enum Join_algorithm get_join_alg() { return BKAH_JOIN_ALG; } 1447 1448 /* Check index condition of the joined table for a record from BKAH cache */ 1449 bool skip_index_tuple(range_id_t range_info); 1450 1451 bool save_explain_data(EXPLAIN_BKA_TYPE *explain); 1452 }; 1453