1 #ifndef SQL_JOIN_CACHE_INCLUDED 2 #define SQL_JOIN_CACHE_INCLUDED 3 4 #include "sql_executor.h" 5 6 /* Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved. 7 8 This program is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License, version 2.0, 10 as published by the Free Software Foundation. 11 12 This program is also distributed with certain software (including 13 but not limited to OpenSSL) that is licensed under separate terms, 14 as designated in a particular file or component or in included license 15 documentation. The authors of MySQL hereby grant you an additional 16 permission to link the program and your derivative works with the 17 separately licensed software that they have included with MySQL. 18 19 This program is distributed in the hope that it will be useful, 20 but WITHOUT ANY WARRANTY; without even the implied warranty of 21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 22 GNU General Public License, version 2.0, for more details. 23 24 You should have received a copy of the GNU General Public License 25 along with this program; if not, write to the Free Software 26 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ 27 28 /** @file Join buffer classes */ 29 30 /* 31 Categories of data fields of variable length written into join cache buffers. 32 The value of any of these fields is written into cache together with the 33 prepended length of the value. 34 */ 35 #define CACHE_BLOB 1 /* blob field */ 36 #define CACHE_STRIPPED 2 /* field stripped of trailing spaces */ 37 #define CACHE_VARSTR1 3 /* short string value (length takes 1 byte) */ 38 #define CACHE_VARSTR2 4 /* long string value (length takes 2 bytes) */ 39 40 /* 41 The CACHE_FIELD structure used to describe fields of records that 42 are written into a join cache buffer from record buffers and backward. 43 */ 44 typedef struct st_cache_field { 45 uchar *str; /**< buffer from/to where the field is to be copied */ 46 uint length; /**< maximal number of bytes to be copied from/to str */ 47 /* 48 Field object for the moved field 49 (0 - for a flag field, see JOIN_CACHE::create_flag_fields). 50 */ 51 Field *field; 52 uint type; /**< category of the of the copied field (CACHE_BLOB et al.) */ 53 /* 54 The number of the record offset value for the field in the sequence 55 of offsets placed after the last field of the record. These 56 offset values are used to access fields referred to from other caches. 57 If the value is 0 then no offset for the field is saved in the 58 trailing sequence of offsets. 59 */ 60 uint referenced_field_no; 61 /// Used to chain rowid copy objects belonging to one join_tab 62 st_cache_field *next_copy_rowid; 63 /* The remaining structure fields are used as containers for temp values */ 64 uint blob_length; /**< length of the blob to be copied */ 65 uint offset; /**< field offset to be saved in cache buffer */ 66 bind_bufferst_cache_field67 void bind_buffer(uchar *buffer) 68 { 69 if (next_copy_rowid != NULL) 70 next_copy_rowid->bind_buffer(buffer); 71 str= buffer; 72 } buffer_is_boundst_cache_field73 bool buffer_is_bound() const { return str != NULL; } 74 } CACHE_FIELD; 75 76 77 /* 78 JOIN_CACHE is the base class to support the implementations of both 79 Blocked-Based Nested Loops (BNL) Join Algorithm and Batched Key Access (BKA) 80 Join Algorithm. The first algorithm is supported by the derived class 81 JOIN_CACHE_BNL, while the second algorithm is supported by the derived 82 class JOIN_CACHE_BKA. 83 These two algorithms have a lot in common. Both algorithms first 84 accumulate the records of the left join operand in a join buffer and 85 then search for matching rows of the second operand for all accumulated 86 records. 87 For the first algorithm this strategy saves on logical I/O operations: 88 the entire set of records from the join buffer requires only one look-through 89 the records provided by the second operand. 90 For the second algorithm the accumulation of records allows to optimize 91 fetching rows of the second operand from disk for some engines (MyISAM, 92 InnoDB), or to minimize the number of round-trips between the Server and 93 the engine nodes (NDB Cluster). 94 */ 95 96 class JOIN_CACHE :public QEP_operation 97 { 98 99 private: 100 101 /* Size of the offset of a record from the cache */ 102 uint size_of_rec_ofs; 103 /* Size of the length of a record in the cache */ 104 uint size_of_rec_len; 105 /* Size of the offset of a field within a record in the cache */ 106 uint size_of_fld_ofs; 107 108 protected: 109 110 /* 3 functions below actually do not use the hidden parameter 'this' */ 111 112 /* Calculate the number of bytes used to store an offset value */ offset_size(ulong len)113 uint offset_size(ulong len) 114 { 115 if (len <= 0xFFUL) 116 return 1; 117 if (len <= 0xFFFFUL) 118 return 2; 119 if (len <= 0xFFFFFFFFUL) 120 return 4; 121 return 8; 122 } 123 124 /* Get the offset value that takes ofs_sz bytes at the position ptr */ get_offset(uint ofs_sz,uchar * ptr)125 ulong get_offset(uint ofs_sz, uchar *ptr) 126 { 127 switch (ofs_sz) { 128 case 1: return uint(*ptr); 129 case 2: return uint2korr(ptr); 130 case 4: return uint4korr(ptr); 131 case 8: return uint8korr(ptr); 132 } 133 return 0; 134 } 135 136 /* Set the offset value ofs that takes ofs_sz bytes at the position ptr */ store_offset(uint ofs_sz,uchar * ptr,ulong ofs)137 void store_offset(uint ofs_sz, uchar *ptr, ulong ofs) 138 { 139 switch (ofs_sz) { 140 case 1: *ptr= (uchar) ofs; return; 141 case 2: int2store(ptr, (uint16) ofs); return; 142 case 4: int4store(ptr, (uint32) ofs); return; 143 case 8: int8store(ptr, (uint64) ofs); return; 144 } 145 } 146 147 /* 148 The total maximal length of the fields stored for a record in the cache. 149 For blob fields only the sizes of the blob lengths are taken into account. 150 */ 151 uint length; 152 153 /* 154 Representation of the executed multi-way join through which all needed 155 context can be accessed. 156 */ 157 JOIN *join; 158 159 /* 160 Cardinality of the range of join tables whose fields can be put into the 161 cache. (A table from the range not necessarily contributes to the cache.) 162 */ 163 uint tables; 164 165 /* 166 The total number of flag and data fields that can appear in a record 167 written into the cache. Fields with null values are always skipped 168 to save space. 169 */ 170 uint fields; 171 172 /* 173 The total number of flag fields in a record put into the cache. They are 174 used for table null bitmaps, table null row flags, and an optional match 175 flag. Flag fields go before other fields in a cache record with the match 176 flag field placed always at the very beginning of the record. 177 */ 178 uint flag_fields; 179 180 /* The total number of blob fields that are written into the cache */ 181 uint blobs; 182 183 /* 184 The total number of fields referenced from field descriptors for other join 185 caches. These fields are used to construct key values to access matching 186 rows with index lookups. Currently the fields can be referenced only from 187 descriptors for bka caches. However they may belong to a cache of any type. 188 */ 189 uint referenced_fields; 190 191 /* 192 The current number of already created data field descriptors. 193 This number can be useful for implementations of the init methods. 194 */ 195 uint data_field_count; 196 197 /* 198 The current number of already created pointers to the data field 199 descriptors. This number can be useful for implementations of 200 the init methods. 201 */ 202 uint data_field_ptr_count; 203 /* 204 Array of the descriptors of fields containing 'fields' elements. 205 These are all fields that are stored for a record in the cache. 206 */ 207 CACHE_FIELD *field_descr; 208 209 /* 210 Array of pointers to the blob descriptors that contains 'blobs' elements. 211 */ 212 CACHE_FIELD **blob_ptr; 213 214 /* 215 This flag indicates that records written into the join buffer contain 216 a match flag field. The flag must be set by the init method. 217 */ 218 bool with_match_flag; 219 /* 220 This flag indicates that any record is prepended with the length of the 221 record which allows us to skip the record or part of it without reading. 222 */ 223 bool with_length; 224 225 /* 226 The maximal number of bytes used for a record representation in 227 the cache excluding the space for blob data. 228 For future derived classes this representation may contains some 229 redundant info such as a key value associated with the record. 230 */ 231 uint pack_length; 232 /* 233 The value of pack_length incremented by the total size of all 234 pointers of a record in the cache to the blob data. 235 */ 236 uint pack_length_with_blob_ptrs; 237 238 /* Pointer to the beginning of the join buffer */ 239 uchar *buff; 240 /* 241 Size of the entire memory allocated for the join buffer. 242 Part of this memory may be reserved for the auxiliary buffer. 243 */ 244 ulong buff_size; 245 /* Size of the auxiliary buffer. */ 246 ulong aux_buff_size; 247 248 /* The number of records put into the join buffer */ 249 uint records; 250 251 /* 252 Pointer to the current position in the join buffer. 253 This member is used both when writing to buffer and 254 when reading from it. 255 */ 256 uchar *pos; 257 /* 258 Pointer to the first free position in the join buffer, 259 right after the last record into it. 260 */ 261 uchar *end_pos; 262 263 /* 264 Pointer to the beginning of first field of the current read/write record 265 from the join buffer. The value is adjusted by the get_record/put_record 266 functions. 267 */ 268 uchar *curr_rec_pos; 269 /* 270 Pointer to the beginning of first field of the last record 271 from the join buffer. 272 */ 273 uchar *last_rec_pos; 274 275 /* 276 Flag is set if the blob data for the last record in the join buffer 277 is in record buffers rather than in the join cache. 278 */ 279 bool last_rec_blob_data_is_in_rec_buff; 280 281 /* 282 Pointer to the position to the current record link. 283 Record links are used only with linked caches. Record links allow to set 284 connections between parts of one join record that are stored in different 285 join buffers. 286 In the simplest case a record link is just a pointer to the beginning of 287 the record stored in the buffer. 288 In a more general case a link could be a reference to an array of pointers 289 to records in the buffer. */ 290 uchar *curr_rec_link; 291 292 /** Cached value of calc_check_only_first_match(join_tab) */ 293 bool check_only_first_match; 294 295 void calc_record_fields(); 296 int alloc_fields(uint external_fields); 297 void create_flag_fields(); 298 void create_remaining_fields(bool all_read_fields); 299 void set_constants(); 300 bool alloc_buffer(); 301 get_size_of_rec_offset()302 uint get_size_of_rec_offset() { return size_of_rec_ofs; } get_size_of_rec_length()303 uint get_size_of_rec_length() { return size_of_rec_len; } get_size_of_fld_offset()304 uint get_size_of_fld_offset() { return size_of_fld_ofs; } 305 get_rec_ref(uchar * ptr)306 uchar *get_rec_ref(uchar *ptr) 307 { 308 return buff+get_offset(size_of_rec_ofs, ptr-size_of_rec_ofs); 309 } get_rec_length(uchar * ptr)310 ulong get_rec_length(uchar *ptr) 311 { 312 return get_offset(size_of_rec_len, ptr); 313 } get_fld_offset(uchar * ptr)314 ulong get_fld_offset(uchar *ptr) 315 { 316 return get_offset(size_of_fld_ofs, ptr); 317 } 318 store_rec_ref(uchar * ptr,uchar * ref)319 void store_rec_ref(uchar *ptr, uchar* ref) 320 { 321 store_offset(size_of_rec_ofs, ptr-size_of_rec_ofs, (ulong) (ref-buff)); 322 } 323 store_rec_length(uchar * ptr,ulong len)324 void store_rec_length(uchar *ptr, ulong len) 325 { 326 store_offset(size_of_rec_len, ptr, len); 327 } store_fld_offset(uchar * ptr,ulong ofs)328 void store_fld_offset(uchar *ptr, ulong ofs) 329 { 330 store_offset(size_of_fld_ofs, ptr, ofs); 331 } 332 333 /* Write record fields and their required offsets into the join buffer */ 334 uint write_record_data(uchar *link, bool *is_full); 335 336 /* 337 This method must determine for how much the auxiliary buffer should be 338 incremented when a new record is added to the join buffer. 339 If no auxiliary buffer is needed the function should return 0. 340 */ aux_buffer_incr()341 virtual uint aux_buffer_incr() { return 0; } 342 343 /** 344 This method must determine the minimum size for the auxiliary buffer. 345 If no auxiliary buffer is needed the function should return 0. 346 */ aux_buffer_min_size()347 virtual uint aux_buffer_min_size() const { return 0; } 348 349 /* Shall calculate how much space is remaining in the join buffer */ rem_space()350 virtual ulong rem_space() 351 { 352 return static_cast<ulong>( 353 std::max<long>(buff_size-(end_pos-buff)-aux_buff_size, 0L) 354 ); 355 } 356 357 /* Shall skip record from the join buffer if its match flag is on */ 358 virtual bool skip_record_if_match(); 359 360 /* Read some flag and data fields of a record from the join buffer */ 361 int read_some_record_fields(); 362 363 /* Read some flag fields of a record from the join buffer */ 364 void read_some_flag_fields(); 365 366 /* Read all flag fields of the record which is at position rec_ptr */ 367 void read_all_flag_fields_by_pos(uchar *rec_ptr); 368 369 /* Read a data record field from the join buffer */ 370 uint read_record_field(CACHE_FIELD *copy, bool last_record); 371 372 /* Read a referenced field from the join buffer */ 373 bool read_referenced_field(CACHE_FIELD *copy, uchar *rec_ptr, uint *len); 374 375 /* 376 True if rec_ptr points to the record whose blob data stay in 377 record buffers 378 */ blob_data_is_in_rec_buff(uchar * rec_ptr)379 bool blob_data_is_in_rec_buff(uchar *rec_ptr) 380 { 381 return rec_ptr == last_rec_pos && last_rec_blob_data_is_in_rec_buff; 382 } 383 384 /* Find matches from the next table for records from the join buffer */ 385 virtual enum_nested_loop_state join_matching_records(bool skip_last)=0; 386 387 /* Add null complements for unmatched outer records from buffer */ 388 virtual enum_nested_loop_state join_null_complements(bool skip_last); 389 390 /* Restore the fields of the last record from the join buffer */ 391 virtual void restore_last_record(); 392 393 /*Set match flag for a record in join buffer if it has not been set yet */ 394 bool set_match_flag_if_none(JOIN_TAB *first_inner, uchar *rec_ptr); 395 396 enum_nested_loop_state generate_full_extensions(uchar *rec_ptr); 397 398 /* Check matching to a partial join record from the join buffer */ 399 virtual bool check_match(uchar *rec_ptr); 400 401 /** @returns whether we should check only the first match for this table */ calc_check_only_first_match(const JOIN_TAB * t)402 bool calc_check_only_first_match(const JOIN_TAB *t) const 403 { 404 return (t->last_sj_inner_tab == t && 405 t->get_sj_strategy() == SJ_OPT_FIRST_MATCH) || 406 (t->first_inner && t->first_inner->last_inner == t && 407 t->table->reginfo.not_exists_optimize); 408 } 409 410 /* 411 This function shall add a record into the join buffer and return TRUE 412 if it has been decided that it should be the last record in the buffer. 413 */ 414 virtual bool put_record_in_cache(); 415 416 public: 417 /* Pointer to the previous join cache if there is any */ 418 JOIN_CACHE *prev_cache; 419 /* Pointer to the next join cache if there is any */ 420 JOIN_CACHE *next_cache; 421 422 /* Shall initialize the join cache structure */ 423 virtual int init()=0; 424 425 /* The function shall return TRUE only for BKA caches */ is_key_access()426 virtual bool is_key_access() { return FALSE; } 427 428 /* Shall reset the join buffer for reading/writing */ 429 virtual void reset_cache(bool for_writing); 430 431 /* Add a record into join buffer and call join_records() if it's full */ put_record()432 virtual enum_nested_loop_state put_record() 433 { 434 if (put_record_in_cache()) 435 return join_records(false); 436 return NESTED_LOOP_OK; 437 } 438 /* 439 This function shall read the next record into the join buffer and return 440 TRUE if there is no more next records. 441 */ 442 virtual bool get_record(); 443 444 /* 445 This function shall read the record at the position rec_ptr 446 in the join buffer 447 */ 448 virtual void get_record_by_pos(uchar *rec_ptr); 449 450 /* Shall return the value of the match flag for the positioned record */ 451 virtual bool get_match_flag_by_pos(uchar *rec_ptr); 452 453 /* Shall return the position of the current record */ get_curr_rec()454 virtual uchar *get_curr_rec() { return curr_rec_pos; } 455 456 /* Shall set the current record link */ set_curr_rec_link(uchar * link)457 virtual void set_curr_rec_link(uchar *link) { curr_rec_link= link; } 458 459 /* Shall return the current record link */ get_curr_rec_link()460 virtual uchar *get_curr_rec_link() 461 { 462 return (curr_rec_link ? curr_rec_link : get_curr_rec()); 463 } 464 465 /* Join records from the join buffer with records from the next join table */ end_send()466 enum_nested_loop_state end_send() { return join_records(false); }; 467 enum_nested_loop_state join_records(bool skip_last); 468 type()469 enum_op_type type() { return OT_CACHE; } 470 471 /** 472 This constructor creates a join cache, linked or not. The cache is to be 473 used to join table 'tab' to the result of joining the previous tables 474 specified by the 'j' parameter. The parameter 'prev' specifies the previous 475 cache object to which this cache is linked, or NULL if this cache is not 476 linked. 477 */ JOIN_CACHE(JOIN * j,JOIN_TAB * tab,JOIN_CACHE * prev)478 JOIN_CACHE(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) 479 : QEP_operation(tab), join(j), buff(NULL), prev_cache(prev), 480 next_cache(NULL) 481 { 482 if (prev_cache) 483 prev_cache->next_cache= this; 484 } ~JOIN_CACHE()485 virtual ~JOIN_CACHE() {} free()486 void free() 487 { 488 /* 489 JOIN_CACHE doesn't support unlinking cache chain. This code is needed 490 only by set_join_cache_denial(). 491 */ 492 /* 493 If there is a previous/next cache linked to this cache through the 494 (next|prev)_cache pointer: remove the link. 495 */ 496 if (prev_cache) 497 prev_cache->next_cache= NULL; 498 if (next_cache) 499 next_cache->prev_cache= NULL; 500 501 my_free(buff); 502 buff= NULL; 503 } 504 505 /** Bits describing cache's type @sa setup_join_buffering() */ 506 enum {ALG_NONE= 0, ALG_BNL= 1, ALG_BKA= 2, ALG_BKA_UNIQUE= 4}; 507 508 friend class JOIN_CACHE_BNL; 509 friend class JOIN_CACHE_BKA; 510 friend class JOIN_CACHE_BKA_UNIQUE; 511 }; 512 513 class JOIN_CACHE_BNL :public JOIN_CACHE 514 { 515 516 protected: 517 518 /* Using BNL find matches from the next table for records from join buffer */ 519 enum_nested_loop_state join_matching_records(bool skip_last); 520 521 public: JOIN_CACHE_BNL(JOIN * j,JOIN_TAB * tab,JOIN_CACHE * prev)522 JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) 523 : JOIN_CACHE(j, tab, prev) 524 {} 525 526 /* Initialize the BNL cache */ 527 int init(); 528 529 }; 530 531 class JOIN_CACHE_BKA :public JOIN_CACHE 532 { 533 protected: 534 535 /* Flag to to be passed to the MRR interface */ 536 uint mrr_mode; 537 538 /* MRR buffer assotiated with this join cache */ 539 HANDLER_BUFFER mrr_buff; 540 541 /* Shall initialize the MRR buffer */ init_mrr_buff()542 virtual void init_mrr_buff() 543 { 544 mrr_buff.buffer= end_pos; 545 mrr_buff.buffer_end= buff+buff_size; 546 } 547 548 /* 549 The number of the cache fields that are used in building keys to access 550 the table join_tab 551 */ 552 uint local_key_arg_fields; 553 /* 554 The total number of the fields in the previous caches that are used 555 in building keys t access the table join_tab 556 */ 557 uint external_key_arg_fields; 558 559 /* 560 This flag indicates that the key values will be read directly from the join 561 buffer. It will save us building key values in the key buffer. 562 */ 563 bool use_emb_key; 564 /* The length of an embedded key value */ 565 uint emb_key_length; 566 567 /* Check the possibility to read the access keys directly from join buffer */ 568 bool check_emb_key_usage(); 569 570 /** Calculate the increment of the MRR buffer for a record write */ 571 uint aux_buffer_incr(); 572 573 /** Calculate the minimume size for the MRR buffer */ 574 uint aux_buffer_min_size() const; 575 576 /* Using BKA find matches from the next table for records from join buffer */ 577 enum_nested_loop_state join_matching_records(bool skip_last); 578 579 /* Prepare to search for records that match records from the join buffer */ 580 bool init_join_matching_records(RANGE_SEQ_IF *seq_funcs, uint ranges); 581 582 public: 583 584 /// The MRR mode initially is set to 'flags' JOIN_CACHE_BKA(JOIN * j,JOIN_TAB * tab,uint flags,JOIN_CACHE * prev)585 JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE* prev) 586 : JOIN_CACHE(j, tab, prev), mrr_mode(flags) 587 {} 588 589 /* Initialize the BKA cache */ 590 int init(); 591 is_key_access()592 bool is_key_access() { return TRUE; } 593 594 /* Shall get the key built over the next record from the join buffer */ 595 virtual uint get_next_key(uchar **key); 596 597 /* Check if the record combination matches the index condition */ 598 bool skip_index_tuple(range_seq_t rseq, char *range_info); 599 }; 600 601 /* 602 The class JOIN_CACHE_BKA_UNIQUE supports the variant of the BKA join algorithm 603 that submits only distinct keys to the MRR interface. The records in the join 604 buffer of a cache of this class that have the same access key are linked into 605 a chain attached to a key entry structure that either itself contains the key 606 value, or, in the case when the keys are embedded, refers to its occurance in 607 one of the records from the chain. 608 To build the chains with the same keys a hash table is employed. It is placed 609 at the very end of the join buffer. The array of hash entries is allocated 610 first at the very bottom of the join buffer, then go key entries. A hash entry 611 contains a header of the list of the key entries with the same hash value. 612 Each key entry is a structure of the following type: 613 struct st_join_cache_key_entry { 614 union { 615 uchar[] value; 616 cache_ref *value_ref; // offset from the beginning of the buffer 617 } hash_table_key; 618 key_ref next_key; // offset backward from the beginning of hash table 619 cache_ref *last_rec // offset from the beginning of the buffer 620 } 621 The references linking the records in a chain are always placed at the very 622 beginning of the record info stored in the join buffer. The records are 623 linked in a circular list. A new record is always added to the end of this 624 list. When a key is passed to the MRR interface it can be passed either with 625 an association link containing a reference to the header of the record chain 626 attached to the corresponding key entry in the hash table, or without any 627 association link. When the next record is returned by a call to the MRR 628 function multi_range_read_next without any association (because if was not 629 passed together with the key) then the key value is extracted from the 630 returned record and searched for it in the hash table. If there is any records 631 with such key the chain of them will be yielded as the result of this search. 632 633 The following picture represents a typical layout for the info stored in the 634 join buffer of a join cache object of the JOIN_CACHE_BKA_UNIQUE class. 635 636 buff 637 V 638 +----------------------------------------------------------------------------+ 639 | |[*]record_1_1| | 640 | ^ | | 641 | | +--------------------------------------------------+ | 642 | | |[*]record_2_1| | | 643 | | ^ | V | 644 | | | +------------------+ |[*]record_1_2| | 645 | | +--------------------+-+ | | 646 |+--+ +---------------------+ | | +-------------+ | 647 || | | V | | | 648 |||[*]record_3_1| |[*]record_1_3| |[*]record_2_2| | | 649 ||^ ^ ^ | | 650 ||+----------+ | | | | 651 ||^ | |<---------------------------+-------------------+ | 652 |++ | | ... mrr | buffer ... ... | | | 653 | | | | | 654 | +-----+--------+ | +-----|-------+ | 655 | V | | | V | | | 656 ||key_3|[/]|[*]| | | |key_2|[/]|[*]| | | 657 | +-+---|-----------------------+ | | 658 | V | | | | | 659 | |key_1|[*]|[*]| | | ... |[*]| ... |[*]| ... | | 660 +----------------------------------------------------------------------------+ 661 ^ ^ ^ 662 | i-th entry j-th entry 663 hash table 664 665 i-th hash entry: 666 circular record chain for key_1: 667 record_1_1 668 record_1_2 669 record_1_3 (points to record_1_1) 670 circular record chain for key_3: 671 record_3_1 (points to itself) 672 673 j-th hash entry: 674 circular record chain for key_2: 675 record_2_1 676 record_2_2 (points to record_2_1) 677 678 */ 679 680 class JOIN_CACHE_BKA_UNIQUE :public JOIN_CACHE_BKA 681 { 682 683 private: 684 685 /* Size of the offset of a key entry in the hash table */ 686 uint size_of_key_ofs; 687 688 /* 689 Length of a key value. 690 It is assumed that all key values have the same length. 691 */ 692 uint key_length; 693 /* 694 Length of the key entry in the hash table. 695 A key entry either contains the key value, or it contains a reference 696 to the key value if use_emb_key flag is set for the cache. 697 */ 698 uint key_entry_length; 699 700 /* The beginning of the hash table in the join buffer */ 701 uchar *hash_table; 702 /* Number of hash entries in the hash table */ 703 uint hash_entries; 704 705 /* Number of key entries in the hash table (number of distinct keys) */ 706 uint key_entries; 707 708 /* The position of the last key entry in the hash table */ 709 uchar *last_key_entry; 710 711 /* The position of the currently retrieved key entry in the hash table */ 712 uchar *curr_key_entry; 713 714 /* 715 The offset of the record fields from the beginning of the record 716 representation. The record representation starts with a reference to 717 the next record in the key record chain followed by the length of 718 the trailing record data followed by a reference to the record segment 719 in the previous cache, if any, followed by the record fields. 720 */ 721 uint rec_fields_offset; 722 /* The offset of the data fields from the beginning of the record fields */ 723 uint data_fields_offset; 724 725 uint get_hash_idx(uchar* key, uint key_len); 726 727 void cleanup_hash_table(); 728 729 protected: 730 get_size_of_key_offset()731 uint get_size_of_key_offset() { return size_of_key_ofs; } 732 733 /* 734 Get the position of the next_key_ptr field pointed to by 735 a linking reference stored at the position key_ref_ptr. 736 This reference is actually the offset backward from the 737 beginning of hash table. 738 */ get_next_key_ref(uchar * key_ref_ptr)739 uchar *get_next_key_ref(uchar *key_ref_ptr) 740 { 741 return hash_table-get_offset(size_of_key_ofs, key_ref_ptr); 742 } 743 744 /* 745 Store the linking reference to the next_key_ptr field at 746 the position key_ref_ptr. The position of the next_key_ptr 747 field is pointed to by ref. The stored reference is actually 748 the offset backward from the beginning of the hash table. 749 */ store_next_key_ref(uchar * key_ref_ptr,uchar * ref)750 void store_next_key_ref(uchar *key_ref_ptr, uchar *ref) 751 { 752 store_offset(size_of_key_ofs, key_ref_ptr, (ulong) (hash_table-ref)); 753 } 754 755 /* 756 Check whether the reference to the next_key_ptr field at the position 757 key_ref_ptr contains a nil value. 758 */ is_null_key_ref(uchar * key_ref_ptr)759 bool is_null_key_ref(uchar *key_ref_ptr) 760 { 761 ulong nil= 0; 762 return memcmp(key_ref_ptr, &nil, size_of_key_ofs ) == 0; 763 } 764 765 /* 766 Set the reference to the next_key_ptr field at the position 767 key_ref_ptr equal to nil. 768 */ store_null_key_ref(uchar * key_ref_ptr)769 void store_null_key_ref(uchar *key_ref_ptr) 770 { 771 ulong nil= 0; 772 store_offset(size_of_key_ofs, key_ref_ptr, nil); 773 } 774 get_next_rec_ref(uchar * ref_ptr)775 uchar *get_next_rec_ref(uchar *ref_ptr) 776 { 777 return buff+get_offset(get_size_of_rec_offset(), ref_ptr); 778 } 779 store_next_rec_ref(uchar * ref_ptr,uchar * ref)780 void store_next_rec_ref(uchar *ref_ptr, uchar *ref) 781 { 782 store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); 783 } 784 785 /* 786 Get the position of the embedded key value for the current 787 record pointed to by get_curr_rec(). 788 */ get_curr_emb_key()789 uchar *get_curr_emb_key() 790 { 791 return get_curr_rec()+data_fields_offset; 792 } 793 794 /* 795 Get the position of the embedded key value pointed to by a reference 796 stored at ref_ptr. The stored reference is actually the offset from 797 the beginning of the join buffer. 798 */ get_emb_key(uchar * ref_ptr)799 uchar *get_emb_key(uchar *ref_ptr) 800 { 801 return buff+get_offset(get_size_of_rec_offset(), ref_ptr); 802 } 803 804 /* 805 Store the reference to an embedded key at the position key_ref_ptr. 806 The position of the embedded key is pointed to by ref. The stored 807 reference is actually the offset from the beginning of the join buffer. 808 */ store_emb_key_ref(uchar * ref_ptr,uchar * ref)809 void store_emb_key_ref(uchar *ref_ptr, uchar *ref) 810 { 811 store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); 812 } 813 814 /* 815 Calculate how much space in the buffer would not be occupied by 816 records, key entries and additional memory for the MMR buffer. 817 */ rem_space()818 ulong rem_space() 819 { 820 return static_cast<ulong>( 821 std::max<long>(last_key_entry-end_pos-aux_buff_size, 0L) 822 ); 823 } 824 825 /* 826 Initialize the MRR buffer allocating some space within the join buffer. 827 The entire space between the last record put into the join buffer and the 828 last key entry added to the hash table is used for the MRR buffer. 829 */ init_mrr_buff()830 void init_mrr_buff() 831 { 832 mrr_buff.buffer= end_pos; 833 mrr_buff.buffer_end= last_key_entry; 834 } 835 836 /* Skip record from JOIN_CACHE_BKA_UNIQUE buffer if its match flag is on */ 837 bool skip_record_if_match(); 838 839 /* Using BKA_UNIQUE find matches for records from join buffer */ 840 enum_nested_loop_state join_matching_records(bool skip_last); 841 842 /* Search for a key in the hash table of the join buffer */ 843 bool key_search(uchar *key, uint key_len, uchar **key_ref_ptr); 844 845 virtual bool check_match(uchar *rec_ptr); 846 847 /* Add a record into the JOIN_CACHE_BKA_UNIQUE buffer */ 848 bool put_record_in_cache(); 849 850 public: 851 JOIN_CACHE_BKA_UNIQUE(JOIN * j,JOIN_TAB * tab,uint flags,JOIN_CACHE * prev)852 JOIN_CACHE_BKA_UNIQUE(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE* prev) 853 : JOIN_CACHE_BKA(j, tab, flags, prev) 854 {} 855 856 /* Initialize the BKA_UNIQUE cache */ 857 int init(); 858 859 /* Reset the JOIN_CACHE_BKA_UNIQUE buffer for reading/writing */ 860 void reset_cache(bool for_writing); 861 862 /* Read the next record from the JOIN_CACHE_BKA_UNIQUE buffer */ 863 bool get_record(); 864 865 /* 866 Shall check whether all records in a key chain have 867 their match flags set on 868 */ 869 virtual bool check_all_match_flags_for_key(uchar *key_chain_ptr); 870 871 uint get_next_key(uchar **key); 872 873 /* Get the head of the record chain attached to the current key entry */ get_curr_key_chain()874 uchar *get_curr_key_chain() 875 { 876 return get_next_rec_ref(curr_key_entry+key_entry_length- 877 get_size_of_rec_offset()); 878 } 879 880 /* Check if the record combination matches the index condition */ 881 bool skip_index_tuple(range_seq_t rseq, char *range_info); 882 }; 883 884 885 #endif /* SQL_JOIN_CACHE_INCLUDED */ 886