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 std::max<ulong>(buff_size-(end_pos-buff)-aux_buff_size, 0UL); 353 } 354 355 /* Shall skip record from the join buffer if its match flag is on */ 356 virtual bool skip_record_if_match(); 357 358 /* Read some flag and data fields of a record from the join buffer */ 359 int read_some_record_fields(); 360 361 /* Read some flag fields of a record from the join buffer */ 362 void read_some_flag_fields(); 363 364 /* Read all flag fields of the record which is at position rec_ptr */ 365 void read_all_flag_fields_by_pos(uchar *rec_ptr); 366 367 /* Read a data record field from the join buffer */ 368 uint read_record_field(CACHE_FIELD *copy, bool last_record); 369 370 /* Read a referenced field from the join buffer */ 371 bool read_referenced_field(CACHE_FIELD *copy, uchar *rec_ptr, uint *len); 372 373 /* 374 True if rec_ptr points to the record whose blob data stay in 375 record buffers 376 */ blob_data_is_in_rec_buff(uchar * rec_ptr)377 bool blob_data_is_in_rec_buff(uchar *rec_ptr) 378 { 379 return rec_ptr == last_rec_pos && last_rec_blob_data_is_in_rec_buff; 380 } 381 382 /* Find matches from the next table for records from the join buffer */ 383 virtual enum_nested_loop_state join_matching_records(bool skip_last)=0; 384 385 /* Add null complements for unmatched outer records from buffer */ 386 virtual enum_nested_loop_state join_null_complements(bool skip_last); 387 388 /* Restore the fields of the last record from the join buffer */ 389 virtual void restore_last_record(); 390 391 /*Set match flag for a record in join buffer if it has not been set yet */ 392 bool set_match_flag_if_none(JOIN_TAB *first_inner, uchar *rec_ptr); 393 394 enum_nested_loop_state generate_full_extensions(uchar *rec_ptr); 395 396 /* Check matching to a partial join record from the join buffer */ 397 virtual bool check_match(uchar *rec_ptr); 398 399 /** @returns whether we should check only the first match for this table */ calc_check_only_first_match(const JOIN_TAB * t)400 bool calc_check_only_first_match(const JOIN_TAB *t) const 401 { 402 return (t->last_sj_inner_tab == t && 403 t->get_sj_strategy() == SJ_OPT_FIRST_MATCH) || 404 (t->first_inner && t->first_inner->last_inner == t && 405 t->table->reginfo.not_exists_optimize); 406 } 407 408 /* 409 This function shall add a record into the join buffer and return TRUE 410 if it has been decided that it should be the last record in the buffer. 411 */ 412 virtual bool put_record_in_cache(); 413 414 public: 415 /* Pointer to the previous join cache if there is any */ 416 JOIN_CACHE *prev_cache; 417 /* Pointer to the next join cache if there is any */ 418 JOIN_CACHE *next_cache; 419 420 /* Shall initialize the join cache structure */ 421 virtual int init()=0; 422 423 /* The function shall return TRUE only for BKA caches */ is_key_access()424 virtual bool is_key_access() { return FALSE; } 425 426 /* Shall reset the join buffer for reading/writing */ 427 virtual void reset_cache(bool for_writing); 428 429 /* Add a record into join buffer and call join_records() if it's full */ put_record()430 virtual enum_nested_loop_state put_record() 431 { 432 if (put_record_in_cache()) 433 return join_records(false); 434 return NESTED_LOOP_OK; 435 } 436 /* 437 This function shall read the next record into the join buffer and return 438 TRUE if there is no more next records. 439 */ 440 virtual bool get_record(); 441 442 /* 443 This function shall read the record at the position rec_ptr 444 in the join buffer 445 */ 446 virtual void get_record_by_pos(uchar *rec_ptr); 447 448 /* Shall return the value of the match flag for the positioned record */ 449 virtual bool get_match_flag_by_pos(uchar *rec_ptr); 450 451 /* Shall return the position of the current record */ get_curr_rec()452 virtual uchar *get_curr_rec() { return curr_rec_pos; } 453 454 /* Shall set the current record link */ set_curr_rec_link(uchar * link)455 virtual void set_curr_rec_link(uchar *link) { curr_rec_link= link; } 456 457 /* Shall return the current record link */ get_curr_rec_link()458 virtual uchar *get_curr_rec_link() 459 { 460 return (curr_rec_link ? curr_rec_link : get_curr_rec()); 461 } 462 463 /* Join records from the join buffer with records from the next join table */ end_send()464 enum_nested_loop_state end_send() { return join_records(false); }; 465 enum_nested_loop_state join_records(bool skip_last); 466 type()467 enum_op_type type() { return OT_CACHE; } 468 469 /** 470 This constructor creates a join cache, linked or not. The cache is to be 471 used to join table 'tab' to the result of joining the previous tables 472 specified by the 'j' parameter. The parameter 'prev' specifies the previous 473 cache object to which this cache is linked, or NULL if this cache is not 474 linked. 475 */ JOIN_CACHE(JOIN * j,JOIN_TAB * tab,JOIN_CACHE * prev)476 JOIN_CACHE(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) 477 : QEP_operation(tab), join(j), buff(NULL), prev_cache(prev), 478 next_cache(NULL) 479 { 480 if (prev_cache) 481 prev_cache->next_cache= this; 482 } ~JOIN_CACHE()483 virtual ~JOIN_CACHE() {} free()484 void free() 485 { 486 /* 487 JOIN_CACHE doesn't support unlinking cache chain. This code is needed 488 only by set_join_cache_denial(). 489 */ 490 /* 491 If there is a previous/next cache linked to this cache through the 492 (next|prev)_cache pointer: remove the link. 493 */ 494 if (prev_cache) 495 prev_cache->next_cache= NULL; 496 if (next_cache) 497 next_cache->prev_cache= NULL; 498 499 my_free(buff); 500 buff= NULL; 501 } 502 503 /** Bits describing cache's type @sa setup_join_buffering() */ 504 enum {ALG_NONE= 0, ALG_BNL= 1, ALG_BKA= 2, ALG_BKA_UNIQUE= 4}; 505 506 friend class JOIN_CACHE_BNL; 507 friend class JOIN_CACHE_BKA; 508 friend class JOIN_CACHE_BKA_UNIQUE; 509 }; 510 511 class JOIN_CACHE_BNL :public JOIN_CACHE 512 { 513 514 protected: 515 516 /* Using BNL find matches from the next table for records from join buffer */ 517 enum_nested_loop_state join_matching_records(bool skip_last); 518 519 public: JOIN_CACHE_BNL(JOIN * j,JOIN_TAB * tab,JOIN_CACHE * prev)520 JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) 521 : JOIN_CACHE(j, tab, prev) 522 {} 523 524 /* Initialize the BNL cache */ 525 int init(); 526 527 }; 528 529 class JOIN_CACHE_BKA :public JOIN_CACHE 530 { 531 protected: 532 533 /* Flag to to be passed to the MRR interface */ 534 uint mrr_mode; 535 536 /* MRR buffer assotiated with this join cache */ 537 HANDLER_BUFFER mrr_buff; 538 539 /* Shall initialize the MRR buffer */ init_mrr_buff()540 virtual void init_mrr_buff() 541 { 542 mrr_buff.buffer= end_pos; 543 mrr_buff.buffer_end= buff+buff_size; 544 } 545 546 /* 547 The number of the cache fields that are used in building keys to access 548 the table join_tab 549 */ 550 uint local_key_arg_fields; 551 /* 552 The total number of the fields in the previous caches that are used 553 in building keys t access the table join_tab 554 */ 555 uint external_key_arg_fields; 556 557 /* 558 This flag indicates that the key values will be read directly from the join 559 buffer. It will save us building key values in the key buffer. 560 */ 561 bool use_emb_key; 562 /* The length of an embedded key value */ 563 uint emb_key_length; 564 565 /* Check the possibility to read the access keys directly from join buffer */ 566 bool check_emb_key_usage(); 567 568 /** Calculate the increment of the MRR buffer for a record write */ 569 uint aux_buffer_incr(); 570 571 /** Calculate the minimume size for the MRR buffer */ 572 uint aux_buffer_min_size() const; 573 574 /* Using BKA find matches from the next table for records from join buffer */ 575 enum_nested_loop_state join_matching_records(bool skip_last); 576 577 /* Prepare to search for records that match records from the join buffer */ 578 bool init_join_matching_records(RANGE_SEQ_IF *seq_funcs, uint ranges); 579 580 public: 581 582 /// The MRR mode initially is set to 'flags' JOIN_CACHE_BKA(JOIN * j,JOIN_TAB * tab,uint flags,JOIN_CACHE * prev)583 JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE* prev) 584 : JOIN_CACHE(j, tab, prev), mrr_mode(flags) 585 {} 586 587 /* Initialize the BKA cache */ 588 int init(); 589 is_key_access()590 bool is_key_access() { return TRUE; } 591 592 /* Shall get the key built over the next record from the join buffer */ 593 virtual uint get_next_key(uchar **key); 594 595 /* Check if the record combination matches the index condition */ 596 bool skip_index_tuple(range_seq_t rseq, char *range_info); 597 }; 598 599 /* 600 The class JOIN_CACHE_BKA_UNIQUE supports the variant of the BKA join algorithm 601 that submits only distinct keys to the MRR interface. The records in the join 602 buffer of a cache of this class that have the same access key are linked into 603 a chain attached to a key entry structure that either itself contains the key 604 value, or, in the case when the keys are embedded, refers to its occurance in 605 one of the records from the chain. 606 To build the chains with the same keys a hash table is employed. It is placed 607 at the very end of the join buffer. The array of hash entries is allocated 608 first at the very bottom of the join buffer, then go key entries. A hash entry 609 contains a header of the list of the key entries with the same hash value. 610 Each key entry is a structure of the following type: 611 struct st_join_cache_key_entry { 612 union { 613 uchar[] value; 614 cache_ref *value_ref; // offset from the beginning of the buffer 615 } hash_table_key; 616 key_ref next_key; // offset backward from the beginning of hash table 617 cache_ref *last_rec // offset from the beginning of the buffer 618 } 619 The references linking the records in a chain are always placed at the very 620 beginning of the record info stored in the join buffer. The records are 621 linked in a circular list. A new record is always added to the end of this 622 list. When a key is passed to the MRR interface it can be passed either with 623 an association link containing a reference to the header of the record chain 624 attached to the corresponding key entry in the hash table, or without any 625 association link. When the next record is returned by a call to the MRR 626 function multi_range_read_next without any association (because if was not 627 passed together with the key) then the key value is extracted from the 628 returned record and searched for it in the hash table. If there is any records 629 with such key the chain of them will be yielded as the result of this search. 630 631 The following picture represents a typical layout for the info stored in the 632 join buffer of a join cache object of the JOIN_CACHE_BKA_UNIQUE class. 633 634 buff 635 V 636 +----------------------------------------------------------------------------+ 637 | |[*]record_1_1| | 638 | ^ | | 639 | | +--------------------------------------------------+ | 640 | | |[*]record_2_1| | | 641 | | ^ | V | 642 | | | +------------------+ |[*]record_1_2| | 643 | | +--------------------+-+ | | 644 |+--+ +---------------------+ | | +-------------+ | 645 || | | V | | | 646 |||[*]record_3_1| |[*]record_1_3| |[*]record_2_2| | | 647 ||^ ^ ^ | | 648 ||+----------+ | | | | 649 ||^ | |<---------------------------+-------------------+ | 650 |++ | | ... mrr | buffer ... ... | | | 651 | | | | | 652 | +-----+--------+ | +-----|-------+ | 653 | V | | | V | | | 654 ||key_3|[/]|[*]| | | |key_2|[/]|[*]| | | 655 | +-+---|-----------------------+ | | 656 | V | | | | | 657 | |key_1|[*]|[*]| | | ... |[*]| ... |[*]| ... | | 658 +----------------------------------------------------------------------------+ 659 ^ ^ ^ 660 | i-th entry j-th entry 661 hash table 662 663 i-th hash entry: 664 circular record chain for key_1: 665 record_1_1 666 record_1_2 667 record_1_3 (points to record_1_1) 668 circular record chain for key_3: 669 record_3_1 (points to itself) 670 671 j-th hash entry: 672 circular record chain for key_2: 673 record_2_1 674 record_2_2 (points to record_2_1) 675 676 */ 677 678 class JOIN_CACHE_BKA_UNIQUE :public JOIN_CACHE_BKA 679 { 680 681 private: 682 683 /* Size of the offset of a key entry in the hash table */ 684 uint size_of_key_ofs; 685 686 /* 687 Length of a key value. 688 It is assumed that all key values have the same length. 689 */ 690 uint key_length; 691 /* 692 Length of the key entry in the hash table. 693 A key entry either contains the key value, or it contains a reference 694 to the key value if use_emb_key flag is set for the cache. 695 */ 696 uint key_entry_length; 697 698 /* The beginning of the hash table in the join buffer */ 699 uchar *hash_table; 700 /* Number of hash entries in the hash table */ 701 uint hash_entries; 702 703 /* Number of key entries in the hash table (number of distinct keys) */ 704 uint key_entries; 705 706 /* The position of the last key entry in the hash table */ 707 uchar *last_key_entry; 708 709 /* The position of the currently retrieved key entry in the hash table */ 710 uchar *curr_key_entry; 711 712 /* 713 The offset of the record fields from the beginning of the record 714 representation. The record representation starts with a reference to 715 the next record in the key record chain followed by the length of 716 the trailing record data followed by a reference to the record segment 717 in the previous cache, if any, followed by the record fields. 718 */ 719 uint rec_fields_offset; 720 /* The offset of the data fields from the beginning of the record fields */ 721 uint data_fields_offset; 722 723 uint get_hash_idx(uchar* key, uint key_len); 724 725 void cleanup_hash_table(); 726 727 protected: 728 get_size_of_key_offset()729 uint get_size_of_key_offset() { return size_of_key_ofs; } 730 731 /* 732 Get the position of the next_key_ptr field pointed to by 733 a linking reference stored at the position key_ref_ptr. 734 This reference is actually the offset backward from the 735 beginning of hash table. 736 */ get_next_key_ref(uchar * key_ref_ptr)737 uchar *get_next_key_ref(uchar *key_ref_ptr) 738 { 739 return hash_table-get_offset(size_of_key_ofs, key_ref_ptr); 740 } 741 742 /* 743 Store the linking reference to the next_key_ptr field at 744 the position key_ref_ptr. The position of the next_key_ptr 745 field is pointed to by ref. The stored reference is actually 746 the offset backward from the beginning of the hash table. 747 */ store_next_key_ref(uchar * key_ref_ptr,uchar * ref)748 void store_next_key_ref(uchar *key_ref_ptr, uchar *ref) 749 { 750 store_offset(size_of_key_ofs, key_ref_ptr, (ulong) (hash_table-ref)); 751 } 752 753 /* 754 Check whether the reference to the next_key_ptr field at the position 755 key_ref_ptr contains a nil value. 756 */ is_null_key_ref(uchar * key_ref_ptr)757 bool is_null_key_ref(uchar *key_ref_ptr) 758 { 759 ulong nil= 0; 760 return memcmp(key_ref_ptr, &nil, size_of_key_ofs ) == 0; 761 } 762 763 /* 764 Set the reference to the next_key_ptr field at the position 765 key_ref_ptr equal to nil. 766 */ store_null_key_ref(uchar * key_ref_ptr)767 void store_null_key_ref(uchar *key_ref_ptr) 768 { 769 ulong nil= 0; 770 store_offset(size_of_key_ofs, key_ref_ptr, nil); 771 } 772 get_next_rec_ref(uchar * ref_ptr)773 uchar *get_next_rec_ref(uchar *ref_ptr) 774 { 775 return buff+get_offset(get_size_of_rec_offset(), ref_ptr); 776 } 777 store_next_rec_ref(uchar * ref_ptr,uchar * ref)778 void store_next_rec_ref(uchar *ref_ptr, uchar *ref) 779 { 780 store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); 781 } 782 783 /* 784 Get the position of the embedded key value for the current 785 record pointed to by get_curr_rec(). 786 */ get_curr_emb_key()787 uchar *get_curr_emb_key() 788 { 789 return get_curr_rec()+data_fields_offset; 790 } 791 792 /* 793 Get the position of the embedded key value pointed to by a reference 794 stored at ref_ptr. The stored reference is actually the offset from 795 the beginning of the join buffer. 796 */ get_emb_key(uchar * ref_ptr)797 uchar *get_emb_key(uchar *ref_ptr) 798 { 799 return buff+get_offset(get_size_of_rec_offset(), ref_ptr); 800 } 801 802 /* 803 Store the reference to an embedded key at the position key_ref_ptr. 804 The position of the embedded key is pointed to by ref. The stored 805 reference is actually the offset from the beginning of the join buffer. 806 */ store_emb_key_ref(uchar * ref_ptr,uchar * ref)807 void store_emb_key_ref(uchar *ref_ptr, uchar *ref) 808 { 809 store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); 810 } 811 812 /* 813 Calculate how much space in the buffer would not be occupied by 814 records, key entries and additional memory for the MMR buffer. 815 */ rem_space()816 ulong rem_space() 817 { 818 return std::max<ulong>(last_key_entry-end_pos-aux_buff_size, 0UL); 819 } 820 821 /* 822 Initialize the MRR buffer allocating some space within the join buffer. 823 The entire space between the last record put into the join buffer and the 824 last key entry added to the hash table is used for the MRR buffer. 825 */ init_mrr_buff()826 void init_mrr_buff() 827 { 828 mrr_buff.buffer= end_pos; 829 mrr_buff.buffer_end= last_key_entry; 830 } 831 832 /* Skip record from JOIN_CACHE_BKA_UNIQUE buffer if its match flag is on */ 833 bool skip_record_if_match(); 834 835 /* Using BKA_UNIQUE find matches for records from join buffer */ 836 enum_nested_loop_state join_matching_records(bool skip_last); 837 838 /* Search for a key in the hash table of the join buffer */ 839 bool key_search(uchar *key, uint key_len, uchar **key_ref_ptr); 840 841 virtual bool check_match(uchar *rec_ptr); 842 843 /* Add a record into the JOIN_CACHE_BKA_UNIQUE buffer */ 844 bool put_record_in_cache(); 845 846 public: 847 JOIN_CACHE_BKA_UNIQUE(JOIN * j,JOIN_TAB * tab,uint flags,JOIN_CACHE * prev)848 JOIN_CACHE_BKA_UNIQUE(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE* prev) 849 : JOIN_CACHE_BKA(j, tab, flags, prev) 850 {} 851 852 /* Initialize the BKA_UNIQUE cache */ 853 int init(); 854 855 /* Reset the JOIN_CACHE_BKA_UNIQUE buffer for reading/writing */ 856 void reset_cache(bool for_writing); 857 858 /* Read the next record from the JOIN_CACHE_BKA_UNIQUE buffer */ 859 bool get_record(); 860 861 /* 862 Shall check whether all records in a key chain have 863 their match flags set on 864 */ 865 virtual bool check_all_match_flags_for_key(uchar *key_chain_ptr); 866 867 uint get_next_key(uchar **key); 868 869 /* Get the head of the record chain attached to the current key entry */ get_curr_key_chain()870 uchar *get_curr_key_chain() 871 { 872 return get_next_rec_ref(curr_key_entry+key_entry_length- 873 get_size_of_rec_offset()); 874 } 875 876 /* Check if the record combination matches the index condition */ 877 bool skip_index_tuple(range_seq_t rseq, char *range_info); 878 }; 879 880 881 #endif /* SQL_JOIN_CACHE_INCLUDED */ 882