diff options
Diffstat (limited to 'sql/sql_select.h')
| -rw-r--r-- | sql/sql_select.h | 1373 |
1 files changed, 1 insertions, 1372 deletions
diff --git a/sql/sql_select.h b/sql/sql_select.h index ee6a58ed97e..0fdba1adb4f 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -411,1378 +411,7 @@ typedef struct st_join_table { } JOIN_TAB; -#define JOIN_CACHE_INCREMENTAL_BIT 1 -#define JOIN_CACHE_HASHED_BIT 2 -#define JOIN_CACHE_BKA_BIT 4 - -/* - Categories of data fields of variable length written into join cache buffers. - The value of any of these fields is written into cache together with the - prepended length of the value. -*/ -#define CACHE_BLOB 1 /* blob field */ -#define CACHE_STRIPPED 2 /* field stripped of trailing spaces */ -#define CACHE_VARSTR1 3 /* short string value (length takes 1 byte) */ -#define CACHE_VARSTR2 4 /* long string value (length takes 2 bytes) */ - -/* - The CACHE_FIELD structure used to describe fields of records that - are written into a join cache buffer from record buffers and backward. -*/ -typedef struct st_cache_field { - uchar *str; /**< buffer from/to where the field is to be copied */ - uint length; /**< maximal number of bytes to be copied from/to str */ - /* - Field object for the moved field - (0 - for a flag field, see JOIN_CACHE::create_flag_fields). - */ - Field *field; - uint type; /**< category of the of the copied field (CACHE_BLOB et al.) */ - /* - The number of the record offset value for the field in the sequence - of offsets placed after the last field of the record. These - offset values are used to access fields referred to from other caches. - If the value is 0 then no offset for the field is saved in the - trailing sequence of offsets. - */ - uint referenced_field_no; - /* The remaining structure fields are used as containers for temp values */ - uint blob_length; /**< length of the blob to be copied */ - uint offset; /**< field offset to be saved in cache buffer */ -} CACHE_FIELD; - - -class JOIN_TAB_SCAN; - - -/* - JOIN_CACHE is the base class to support the implementations of - - Block Nested Loop (BNL) Join Algorithm, - - Block Nested Loop Hash (BNLH) Join Algorithm, - - Batched Key Access (BKA) Join Algorithm. - The first algorithm is supported by the derived class JOIN_CACHE_BNL, - the second algorithm is supported by the derived class JOIN_CACHE_BNLH, - while the third algorithm is implemented in two variant supported by - the classes JOIN_CACHE_BKA and JOIN_CACHE_BKAH. - These three algorithms have a lot in common. Each of them first accumulates - the records of the left join operand in a join buffer and then searches for - matching rows of the second operand for all accumulated records. - For the first two algorithms this strategy saves on logical I/O operations: - the entire set of records from the join buffer requires only one look-through - of the records provided by the second operand. - For the third algorithm the accumulation of records allows to optimize - fetching rows of the second operand from disk for some engines (MyISAM, - InnoDB), or to minimize the number of round-trips between the Server and - the engine nodes (NDB Cluster). -*/ - -class JOIN_CACHE :public Sql_alloc -{ - -private: - - /* Size of the offset of a record from the cache */ - uint size_of_rec_ofs; - /* Size of the length of a record in the cache */ - uint size_of_rec_len; - /* Size of the offset of a field within a record in the cache */ - uint size_of_fld_ofs; - -protected: - - /* 3 functions below actually do not use the hidden parameter 'this' */ - - /* Calculate the number of bytes used to store an offset value */ - uint offset_size(uint len) - { return (len < 256 ? 1 : len < 256*256 ? 2 : 4); } - - /* Get the offset value that takes ofs_sz bytes at the position ptr */ - ulong get_offset(uint ofs_sz, uchar *ptr) - { - switch (ofs_sz) { - case 1: return uint(*ptr); - case 2: return uint2korr(ptr); - case 4: return uint4korr(ptr); - } - return 0; - } - - /* Set the offset value ofs that takes ofs_sz bytes at the position ptr */ - void store_offset(uint ofs_sz, uchar *ptr, ulong ofs) - { - switch (ofs_sz) { - case 1: *ptr= (uchar) ofs; return; - case 2: int2store(ptr, (uint16) ofs); return; - case 4: int4store(ptr, (uint32) ofs); return; - } - } - - /* - The maximum total length of the fields stored for a record in the cache. - For blob fields only the sizes of the blob lengths are taken into account. - */ - uint length; - - /* - Representation of the executed multi-way join through which all needed - context can be accessed. - */ - JOIN *join; - - /* - Cardinality of the range of join tables whose fields can be put into the - cache. A table from the range not necessarily contributes to the cache. - */ - uint tables; - - /* - The total number of flag and data fields that can appear in a record - written into the cache. Fields with null values are always skipped - to save space. - */ - uint fields; - - /* - The total number of flag fields in a record put into the cache. They are - used for table null bitmaps, table null row flags, and an optional match - flag. Flag fields go before other fields in a cache record with the match - flag field placed always at the very beginning of the record. - */ - uint flag_fields; - - /* The total number of blob fields that are written into the cache */ - uint blobs; - - /* - The total number of fields referenced from field descriptors for other join - caches. These fields are used to construct key values. - When BKA join algorithm is employed the constructed key values serve to - access matching rows with index lookups. - The key values are put into a hash table when the BNLH join algorithm - is employed and when BKAH is used for the join operation. - */ - uint referenced_fields; - - /* - The current number of already created data field descriptors. - This number can be useful for implementations of the init methods. - */ - uint data_field_count; - - /* - The current number of already created pointers to the data field - descriptors. This number can be useful for implementations of - the init methods. - */ - uint data_field_ptr_count; - - /* - Array of the descriptors of fields containing 'fields' elements. - These are all fields that are stored for a record in the cache. - */ - CACHE_FIELD *field_descr; - - /* - Array of pointers to the blob descriptors that contains 'blobs' elements. - */ - CACHE_FIELD **blob_ptr; - - /* - This flag indicates that records written into the join buffer contain - a match flag field. The flag must be set by the init method. - */ - bool with_match_flag; - /* - This flag indicates that any record is prepended with the length of the - record which allows us to skip the record or part of it without reading. - */ - bool with_length; - - /* - The maximal number of bytes used for a record representation in - the cache excluding the space for blob data. - For future derived classes this representation may contains some - redundant info such as a key value associated with the record. - */ - uint pack_length; - /* - The value of pack_length incremented by the total size of all - pointers of a record in the cache to the blob data. - */ - uint pack_length_with_blob_ptrs; - - /* - The total size of the record base prefix. The base prefix of record may - include the following components: - - the length of the record - - the link to a record in a previous buffer. - Each record in the buffer are supplied with the same set of the components. - */ - uint base_prefix_length; - - /* - The expected length of a record in the join buffer together with - all prefixes and postfixes - */ - ulong avg_record_length; - - /* The expected size of the space per record in the auxiliary buffer */ - ulong avg_aux_buffer_incr; - - /* Expected join buffer space used for one record */ - ulong space_per_record; - - /* Pointer to the beginning of the join buffer */ - uchar *buff; - /* - Size of the entire memory allocated for the join buffer. - Part of this memory may be reserved for the auxiliary buffer. - */ - ulong buff_size; - /* The minimal join buffer size when join buffer still makes sense to use */ - ulong min_buff_size; - /* The maximum expected size if the join buffer to be used */ - ulong max_buff_size; - /* Size of the auxiliary buffer */ - ulong aux_buff_size; - - /* The number of records put into the join buffer */ - ulong records; - /* - The number of records in the fully refilled join buffer of - the minimal size equal to min_buff_size - */ - ulong min_records; - /* - The maximum expected number of records to be put in the join buffer - at one refill - */ - ulong max_records; - - /* - Pointer to the current position in the join buffer. - This member is used both when writing to buffer and - when reading from it. - */ - uchar *pos; - /* - Pointer to the first free position in the join buffer, - right after the last record into it. - */ - uchar *end_pos; - - /* - Pointer to the beginning of the first field of the current read/write - record from the join buffer. The value is adjusted by the - get_record/put_record functions. - */ - uchar *curr_rec_pos; - /* - Pointer to the beginning of the first field of the last record - from the join buffer. - */ - uchar *last_rec_pos; - - /* - Flag is set if the blob data for the last record in the join buffer - is in record buffers rather than in the join cache. - */ - bool last_rec_blob_data_is_in_rec_buff; - - /* - Pointer to the position to the current record link. - Record links are used only with linked caches. Record links allow to set - connections between parts of one join record that are stored in different - join buffers. - In the simplest case a record link is just a pointer to the beginning of - the record stored in the buffer. - In a more general case a link could be a reference to an array of pointers - to records in the buffer. - */ - uchar *curr_rec_link; - - /* - This flag is set to TRUE if join_tab is the first inner table of an outer - join and the latest record written to the join buffer is detected to be - null complemented after checking on conditions over the outer tables for - this outer join operation - */ - bool last_written_is_null_compl; - - /* - The number of fields put in the join buffer of the join cache that are - used in building keys to access the table join_tab - */ - uint local_key_arg_fields; - /* - The total number of the fields in the previous caches that are used - in building keys to access the table join_tab - */ - uint external_key_arg_fields; - - /* - This flag indicates that the key values will be read directly from the join - buffer. It will save us building key values in the key buffer. - */ - bool use_emb_key; - /* The length of an embedded key value */ - uint emb_key_length; - - /* - This object provides the methods to iterate over records of - the joined table join_tab when looking for join matches between - records from join buffer and records from join_tab. - BNL and BNLH join algorithms retrieve all records from join_tab, - while BKA/BKAH algorithm iterates only over those records from - join_tab that can be accessed by look-ups with join keys built - from records in join buffer. - */ - JOIN_TAB_SCAN *join_tab_scan; - - void calc_record_fields(); - void collect_info_on_key_args(); - int alloc_fields(); - void create_flag_fields(); - void create_key_arg_fields(); - void create_remaining_fields(); - void set_constants(); - int alloc_buffer(); - - /* Shall reallocate the join buffer */ - virtual int realloc_buffer(); - - /* Check the possibility to read the access keys directly from join buffer */ - bool check_emb_key_usage(); - - uint get_size_of_rec_offset() { return size_of_rec_ofs; } - uint get_size_of_rec_length() { return size_of_rec_len; } - uint get_size_of_fld_offset() { return size_of_fld_ofs; } - - uchar *get_rec_ref(uchar *ptr) - { - return buff+get_offset(size_of_rec_ofs, ptr-size_of_rec_ofs); - } - ulong get_rec_length(uchar *ptr) - { - return (ulong) get_offset(size_of_rec_len, ptr); - } - ulong get_fld_offset(uchar *ptr) - { - return (ulong) get_offset(size_of_fld_ofs, ptr); - } - - void store_rec_ref(uchar *ptr, uchar* ref) - { - store_offset(size_of_rec_ofs, ptr-size_of_rec_ofs, (ulong) (ref-buff)); - } - void store_rec_length(uchar *ptr, ulong len) - { - store_offset(size_of_rec_len, ptr, len); - } - void store_fld_offset(uchar *ptr, ulong ofs) - { - store_offset(size_of_fld_ofs, ptr, ofs); - } - - /* Write record fields and their required offsets into the join buffer */ - uint write_record_data(uchar *link, bool *is_full); - - /* Get the total length of all prefixes of a record in the join buffer */ - virtual uint get_prefix_length() { return base_prefix_length; } - /* Get maximum total length of all affixes of a record in the join buffer */ - virtual uint get_record_max_affix_length(); - - /* - Shall get maximum size of the additional space per record used for - record keys - */ - virtual uint get_max_key_addon_space_per_record() { return 0; } - - /* - This method must determine for how much the auxiliary buffer should be - incremented when a new record is added to the join buffer. - If no auxiliary buffer is needed the function should return 0. - */ - virtual uint aux_buffer_incr(ulong recno); - - /* Shall calculate how much space is remaining in the join buffer */ - virtual ulong rem_space() - { - return max(buff_size-(end_pos-buff)-aux_buff_size,0); - } - - /* - Shall calculate how much space is taken by allocation of the key - for a record in the join buffer - */ - virtual uint extra_key_length() { return 0; } - - /* Read all flag and data fields of a record from the join buffer */ - uint read_all_record_fields(); - - /* Read all flag fields of a record from the join buffer */ - uint read_flag_fields(); - - /* Read a data record field from the join buffer */ - uint read_record_field(CACHE_FIELD *copy, bool last_record); - - /* Read a referenced field from the join buffer */ - bool read_referenced_field(CACHE_FIELD *copy, uchar *rec_ptr, uint *len); - - /* - Shall skip record from the join buffer if its match flag - is set to MATCH_FOUND - */ - virtual bool skip_if_matched(); - - /* - Shall skip record from the join buffer if its match flag - commands to do so - */ - virtual bool skip_if_not_needed_match(); - - /* - True if rec_ptr points to the record whose blob data stay in - record buffers - */ - bool blob_data_is_in_rec_buff(uchar *rec_ptr) - { - return rec_ptr == last_rec_pos && last_rec_blob_data_is_in_rec_buff; - } - - /* Find matches from the next table for records from the join buffer */ - virtual enum_nested_loop_state join_matching_records(bool skip_last); - - /* Shall set an auxiliary buffer up (currently used only by BKA joins) */ - virtual int setup_aux_buffer(HANDLER_BUFFER &aux_buff) - { - DBUG_ASSERT(0); - return 0; - } - - /* - Shall get the number of ranges in the cache buffer passed - to the MRR interface - */ - virtual uint get_number_of_ranges_for_mrr() { return 0; }; - - /* - Shall prepare to look for records from the join cache buffer that would - match the record of the joined table read into the record buffer - */ - virtual bool prepare_look_for_matches(bool skip_last)= 0; - /* - Shall return a pointer to the record from join buffer that is checked - as the next candidate for a match with the current record from join_tab. - Each implementation of this virtual function should bare in mind - that the record position it returns shall be exactly the position - passed as the parameter to the implementations of the virtual functions - skip_next_candidate_for_match and read_next_candidate_for_match. - */ - virtual uchar *get_next_candidate_for_match()= 0; - /* - Shall check whether the given record from the join buffer has its match - flag settings commands to skip the record in the buffer. - */ - virtual bool skip_next_candidate_for_match(uchar *rec_ptr)= 0; - /* - Shall read the given record from the join buffer into the - the corresponding record buffer - */ - virtual void read_next_candidate_for_match(uchar *rec_ptr)= 0; - - /* - Shall return the location of the association label returned by - the multi_read_range_next function for the current record loaded - into join_tab's record buffer - */ - virtual uchar **get_curr_association_ptr() { return 0; }; - - /* Add null complements for unmatched outer records from the join buffer */ - virtual enum_nested_loop_state join_null_complements(bool skip_last); - - /* Restore the fields of the last record from the join buffer */ - virtual void restore_last_record(); - - /* Set match flag for a record in join buffer if it has not been set yet */ - bool set_match_flag_if_none(JOIN_TAB *first_inner, uchar *rec_ptr); - - enum_nested_loop_state generate_full_extensions(uchar *rec_ptr); - - /* Check matching to a partial join record from the join buffer */ - bool check_match(uchar *rec_ptr); - - /* - This constructor creates an unlinked join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. - */ - JOIN_CACHE(JOIN *j, JOIN_TAB *tab) - { - join= j; - join_tab= tab; - prev_cache= next_cache= 0; - buff= 0; - } - - /* - This constructor creates a linked join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. The parameter 'prev' specifies the previous - cache object to which this cache is linked. - */ - JOIN_CACHE(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) - { - join= j; - join_tab= tab; - next_cache= 0; - prev_cache= prev; - buff= 0; - if (prev) - prev->next_cache= this; - } - -public: - - /* - The enumeration type Join_algorithm includes a mnemonic constant for - each join algorithm that employs join buffers - */ - - enum Join_algorithm - { - BNL_JOIN_ALG, /* Block Nested Loop Join algorithm */ - BNLH_JOIN_ALG, /* Block Nested Loop Hash Join algorithm */ - BKA_JOIN_ALG, /* Batched Key Access Join algorithm */ - BKAH_JOIN_ALG, /* Batched Key Access with Hash Table Join Algorithm */ - }; - - /* - The enumeration type Match_flag describes possible states of the match flag - field stored for the records of the first inner tables of outer joins and - semi-joins in the cases when the first match strategy is used for them. - When a record with match flag field is written into the join buffer the - state of the field usually is MATCH_NOT_FOUND unless this is a record of the - first inner table of the outer join for which the on precondition (the - condition from on expression over outer tables) has turned out not to be - true. In the last case the state of the match flag is MATCH_IMPOSSIBLE. - The state of the match flag field is changed to MATCH_FOUND as soon as - the first full matching combination of inner tables of the outer join or - the semi-join is discovered. - */ - enum Match_flag { MATCH_NOT_FOUND, MATCH_FOUND, MATCH_IMPOSSIBLE }; - - /* Table to be joined with the partial join records from the cache */ - JOIN_TAB *join_tab; - - /* Pointer to the previous join cache if there is any */ - JOIN_CACHE *prev_cache; - /* Pointer to the next join cache if there is any */ - JOIN_CACHE *next_cache; - - /* Shall initialize the join cache structure */ - virtual int init(); - - /* Get the current size of the cache join buffer */ - ulong get_join_buffer_size() { return buff_size; } - /* Set the size of the cache join buffer to a new value */ - void set_join_buffer_size(ulong sz) { buff_size= sz; } - - /* Get the minimum possible size of the cache join buffer */ - virtual ulong get_min_join_buffer_size(); - /* Get the maximum possible size of the cache join buffer */ - virtual ulong get_max_join_buffer_size(); - - /* Shrink the size if the cache join buffer in a given ratio */ - bool shrink_join_buffer_in_ratio(ulonglong n, ulonglong d); - - /* Shall return the type of the employed join algorithm */ - virtual enum Join_algorithm get_join_alg()= 0; - - /* - The function shall return TRUE only when there is a key access - to the join table - */ - virtual bool is_key_access()= 0; - - /* Shall reset the join buffer for reading/writing */ - virtual void reset(bool for_writing); - - /* - This function shall add a record into the join buffer and return TRUE - if it has been decided that it should be the last record in the buffer. - */ - virtual bool put_record(); - - /* - This function shall read the next record into the join buffer and return - TRUE if there is no more next records. - */ - virtual bool get_record(); - - /* - This function shall read the record at the position rec_ptr - in the join buffer - */ - virtual void get_record_by_pos(uchar *rec_ptr); - - /* Shall return the value of the match flag for the positioned record */ - virtual enum Match_flag get_match_flag_by_pos(uchar *rec_ptr); - - /* Shall return the position of the current record */ - virtual uchar *get_curr_rec() { return curr_rec_pos; } - - /* Shall set the current record link */ - virtual void set_curr_rec_link(uchar *link) { curr_rec_link= link; } - - /* Shall return the current record link */ - virtual uchar *get_curr_rec_link() - { - return (curr_rec_link ? curr_rec_link : get_curr_rec()); - } - - /* Join records from the join buffer with records from the next join table */ - enum_nested_loop_state join_records(bool skip_last); - - /* Add a comment on the join algorithm employed by the join cache */ - void print_explain_comment(String *str); - - virtual ~JOIN_CACHE() {} - void reset_join(JOIN *j) { join= j; } - void free() - { - x_free(buff); - buff= 0; - } - - JOIN_TAB *get_next_table(JOIN_TAB *tab); - - friend class JOIN_CACHE_HASHED; - friend class JOIN_CACHE_BNL; - friend class JOIN_CACHE_BKA; - friend class JOIN_TAB_SCAN; - friend class JOIN_TAB_SCAN_MRR; - -}; - - -/* - The class JOIN_CACHE_HASHED is the base class for the classes - JOIN_CACHE_HASHED_BNL and JOIN_CACHE_HASHED_BKA. The first of them supports - an implementation of Block Nested Loop Hash (BNLH) Join Algorithm, - while the second is used for a variant of the BKA Join algorithm that performs - only one lookup for any records from join buffer with the same key value. - For a join cache of this class the records from the join buffer that have - the same access key are linked into a chain attached to a key entry structure - that either itself contains the key value, or, in the case when the keys are - embedded, refers to its occurrence in one of the records from the chain. - To build the chains with the same keys a hash table is employed. It is placed - at the very end of the join buffer. The array of hash entries is allocated - first at the very bottom of the join buffer, while key entries are placed - before this array. - A hash entry contains a header of the list of the key entries with the same - hash value. - Each key entry is a structure of the following type: - struct st_join_cache_key_entry { - union { - uchar[] value; - cache_ref *value_ref; // offset from the beginning of the buffer - } hash_table_key; - key_ref next_key; // offset backward from the beginning of hash table - cache_ref *last_rec // offset from the beginning of the buffer - } - The references linking the records in a chain are always placed at the very - beginning of the record info stored in the join buffer. The records are - linked in a circular list. A new record is always added to the end of this - list. - - The following picture represents a typical layout for the info stored in the - join buffer of a join cache object of the JOIN_CACHE_HASHED class. - - buff - V - +----------------------------------------------------------------------------+ - | |[*]record_1_1| | - | ^ | | - | | +--------------------------------------------------+ | - | | |[*]record_2_1| | | - | | ^ | V | - | | | +------------------+ |[*]record_1_2| | - | | +--------------------+-+ | | - |+--+ +---------------------+ | | +-------------+ | - || | | V | | | - |||[*]record_3_1| |[*]record_1_3| |[*]record_2_2| | | - ||^ ^ ^ | | - ||+----------+ | | | | - ||^ | |<---------------------------+-------------------+ | - |++ | | ... mrr | buffer ... ... | | | - | | | | | - | +-----+--------+ | +-----|-------+ | - | V | | | V | | | - ||key_3|[/]|[*]| | | |key_2|[/]|[*]| | | - | +-+---|-----------------------+ | | - | V | | | | | - | |key_1|[*]|[*]| | | ... |[*]| ... |[*]| ... | | - +----------------------------------------------------------------------------+ - ^ ^ ^ - | i-th entry j-th entry - hash table - - i-th hash entry: - circular record chain for key_1: - record_1_1 - record_1_2 - record_1_3 (points to record_1_1) - circular record chain for key_3: - record_3_1 (points to itself) - - j-th hash entry: - circular record chain for key_2: - record_2_1 - record_2_2 (points to record_2_1) - -*/ - -class JOIN_CACHE_HASHED: public JOIN_CACHE -{ - -private: - - /* Size of the offset of a key entry in the hash table */ - uint size_of_key_ofs; - - /* - Length of the key entry in the hash table. - A key entry either contains the key value, or it contains a reference - to the key value if use_emb_key flag is set for the cache. - */ - uint key_entry_length; - - /* The beginning of the hash table in the join buffer */ - uchar *hash_table; - /* Number of hash entries in the hash table */ - uint hash_entries; - - - /* The position of the currently retrieved key entry in the hash table */ - uchar *curr_key_entry; - - /* The offset of the data fields from the beginning of the record fields */ - uint data_fields_offset; - - uint get_hash_idx(uchar* key, uint key_len); - - int init_hash_table(); - void cleanup_hash_table(); - -protected: - - /* - Length of a key value. - It is assumed that all key values have the same length. - */ - uint key_length; - /* Buffer to store key values for probing */ - uchar *key_buff; - - /* Number of key entries in the hash table (number of distinct keys) */ - uint key_entries; - - /* The position of the last key entry in the hash table */ - uchar *last_key_entry; - - /* - The offset of the record fields from the beginning of the record - representation. The record representation starts with a reference to - the next record in the key record chain followed by the length of - the trailing record data followed by a reference to the record segment - in the previous cache, if any, followed by the record fields. - */ - uint rec_fields_offset; - - uint get_size_of_key_offset() { return size_of_key_ofs; } - - /* - Get the position of the next_key_ptr field pointed to by - a linking reference stored at the position key_ref_ptr. - This reference is actually the offset backward from the - beginning of hash table. - */ - uchar *get_next_key_ref(uchar *key_ref_ptr) - { - return hash_table-get_offset(size_of_key_ofs, key_ref_ptr); - } - - /* - Store the linking reference to the next_key_ptr field at - the position key_ref_ptr. The position of the next_key_ptr - field is pointed to by ref. The stored reference is actually - the offset backward from the beginning of the hash table. - */ - void store_next_key_ref(uchar *key_ref_ptr, uchar *ref) - { - store_offset(size_of_key_ofs, key_ref_ptr, (ulong) (hash_table-ref)); - } - - /* - Check whether the reference to the next_key_ptr field at the position - key_ref_ptr contains a nil value. - */ - bool is_null_key_ref(uchar *key_ref_ptr) - { - ulong nil= 0; - return memcmp(key_ref_ptr, &nil, size_of_key_ofs ) == 0; - } - - /* - Set the reference to the next_key_ptr field at the position - key_ref_ptr equal to nil. - */ - void store_null_key_ref(uchar *key_ref_ptr) - { - ulong nil= 0; - store_offset(size_of_key_ofs, key_ref_ptr, nil); - } - - uchar *get_next_rec_ref(uchar *ref_ptr) - { - return buff+get_offset(get_size_of_rec_offset(), ref_ptr); - } - - void store_next_rec_ref(uchar *ref_ptr, uchar *ref) - { - store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); - } - - /* - Get the position of the embedded key value for the current - record pointed to by get_curr_rec(). - */ - uchar *get_curr_emb_key() - { - return get_curr_rec()+data_fields_offset; - } - - /* - Get the position of the embedded key value pointed to by a reference - stored at ref_ptr. The stored reference is actually the offset from - the beginning of the join buffer. - */ - uchar *get_emb_key(uchar *ref_ptr) - { - return buff+get_offset(get_size_of_rec_offset(), ref_ptr); - } - - /* - Store the reference to an embedded key at the position key_ref_ptr. - The position of the embedded key is pointed to by ref. The stored - reference is actually the offset from the beginning of the join buffer. - */ - void store_emb_key_ref(uchar *ref_ptr, uchar *ref) - { - store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff)); - } - - /* Get the total length of all prefixes of a record in hashed join buffer */ - uint get_prefix_length() - { - return base_prefix_length + get_size_of_rec_offset(); - } - - /* - Get maximum size of the additional space per record used for - the hash table with record keys - */ - uint get_max_key_addon_space_per_record(); - - /* - Calculate how much space in the buffer would not be occupied by - records, key entries and additional memory for the MMR buffer. - */ - ulong rem_space() - { - return max(last_key_entry-end_pos-aux_buff_size,0); - } - - /* - Calculate how much space is taken by allocation of the key - entry for a record in the join buffer - */ - uint extra_key_length() { return key_entry_length; } - - /* - Skip record from a hashed join buffer if its match flag - is set to MATCH_FOUND - */ - bool skip_if_matched(); - - /* - Skip record from a hashed join buffer if its match flag setting - commands to do so - */ - bool skip_if_not_needed_match(); - - /* Search for a key in the hash table of the join buffer */ - bool key_search(uchar *key, uint key_len, uchar **key_ref_ptr); - - /* Reallocate the join buffer of a hashed join cache */ - int realloc_buffer(); - - /* - This constructor creates an unlinked hashed join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. - */ - JOIN_CACHE_HASHED(JOIN *j, JOIN_TAB *tab) :JOIN_CACHE(j, tab) {} - - /* - This constructor creates a linked hashed join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. The parameter 'prev' specifies the previous - cache object to which this cache is linked. - */ - JOIN_CACHE_HASHED(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) - :JOIN_CACHE(j, tab, prev) {} - -public: - - /* Initialize a hashed join cache */ - int init(); - - /* Reset the buffer of a hashed join cache for reading/writing */ - void reset(bool for_writing); - - /* Add a record into the buffer of a hashed join cache */ - bool put_record(); - - /* Read the next record from the buffer of a hashed join cache */ - bool get_record(); - - /* - Shall check whether all records in a key chain have - their match flags set on - */ - virtual bool check_all_match_flags_for_key(uchar *key_chain_ptr); - - uint get_next_key(uchar **key); - - /* Get the head of the record chain attached to the current key entry */ - uchar *get_curr_key_chain() - { - return get_next_rec_ref(curr_key_entry+key_entry_length- - get_size_of_rec_offset()); - } - -}; - - -/* - The class JOIN_TAB_SCAN is a companion class for the classes JOIN_CACHE_BNL - and JOIN_CACHE_BNLH. Actually the class implements the iterator over the - table joinded by BNL/BNLH join algorithm. - The virtual functions open, next and close are called for any iteration over - the table. The function open is called to initiate the process of the - iteration. The function next shall read the next record from the joined - table. The record is read into the record buffer of the joined table. - The record is to be matched with records from the join cache buffer. - The function close shall perform the finalizing actions for the iteration. -*/ - -class JOIN_TAB_SCAN: public Sql_alloc -{ - -private: - /* TRUE if this is the first record from the joined table to iterate over */ - bool is_first_record; - -protected: - - /* The joined table to be iterated over */ - JOIN_TAB *join_tab; - /* The join cache used to join the table join_tab */ - JOIN_CACHE *cache; - /* - Representation of the executed multi-way join through which - all needed context can be accessed. - */ - JOIN *join; - -public: - - JOIN_TAB_SCAN(JOIN *j, JOIN_TAB *tab) - { - join= j; - join_tab= tab; - cache= join_tab->cache; - } - - virtual ~JOIN_TAB_SCAN() {} - - /* - Shall calculate the increment of the auxiliary buffer for a record - write if such a buffer is used by the table scan object - */ - virtual uint aux_buffer_incr(ulong recno) { return 0; } - - /* Initiate the process of iteration over the joined table */ - virtual int open(); - /* - Shall read the next candidate for matches with records from - the join buffer. - */ - virtual int next(); - /* - Perform the finalizing actions for the process of iteration - over the joined_table. - */ - virtual void close(); - -}; - -/* - The class JOIN_CACHE_BNL is used when the BNL join algorithm is - employed to perform a join operation -*/ - -class JOIN_CACHE_BNL :public JOIN_CACHE -{ -private: - /* - The number of the records in the join buffer that have to be - checked yet for a match with the current record of join_tab - read into the record buffer. - */ - uint rem_records; - -protected: - - bool prepare_look_for_matches(bool skip_last); - - uchar *get_next_candidate_for_match(); - - bool skip_next_candidate_for_match(uchar *rec_ptr); - - void read_next_candidate_for_match(uchar *rec_ptr); - -public: - - /* - This constructor creates an unlinked BNL join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. - */ - JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab) :JOIN_CACHE(j, tab) {} - - /* - This constructor creates a linked BNL join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. The parameter 'prev' specifies the previous - cache object to which this cache is linked. - */ - JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) - :JOIN_CACHE(j, tab, prev) {} - - /* Initialize the BNL cache */ - int init(); - - enum Join_algorithm get_join_alg() { return BNL_JOIN_ALG; } - - bool is_key_access() { return FALSE; } - -}; - - -/* - The class JOIN_CACHE_BNLH is used when the BNLH join algorithm is - employed to perform a join operation -*/ - -class JOIN_CACHE_BNLH :public JOIN_CACHE_HASHED -{ - -protected: - - /* - The pointer to the last record from the circular list of the records - that match the join key built out of the record in the join buffer for - the join_tab table - */ - uchar *last_matching_rec_ref_ptr; - /* - The pointer to the next current record from the circular list of the - records that match the join key built out of the record in the join buffer - for the join_tab table. This pointer is used by the class method - get_next_candidate_for_match to iterate over records from the circular - list. - */ - uchar *next_matching_rec_ref_ptr; - - /* - Get the chain of records from buffer matching the current candidate - record for join - */ - uchar *get_matching_chain_by_join_key(); - - bool prepare_look_for_matches(bool skip_last); - - uchar *get_next_candidate_for_match(); - - bool skip_next_candidate_for_match(uchar *rec_ptr); - - void read_next_candidate_for_match(uchar *rec_ptr); - -public: - - /* - This constructor creates an unlinked BNLH join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. - */ - JOIN_CACHE_BNLH(JOIN *j, JOIN_TAB *tab) : JOIN_CACHE_HASHED(j, tab) {} - - /* - This constructor creates a linked BNLH join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. The parameter 'prev' specifies the previous - cache object to which this cache is linked. - */ - JOIN_CACHE_BNLH(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev) - : JOIN_CACHE_HASHED(j, tab, prev) {} - - /* Initialize the BNLH cache */ - int init(); - - enum Join_algorithm get_join_alg() { return BNLH_JOIN_ALG; } - - bool is_key_access() { return TRUE; } - -}; - - -/* - The class JOIN_TAB_SCAN_MRR is a companion class for the classes - JOIN_CACHE_BKA and JOIN_CACHE_BKAH. Actually the class implements the - iterator over the records from join_tab selected by BKA/BKAH join - algorithm as the candidates to be joined. - The virtual functions open, next and close are called for any iteration over - join_tab record candidates. The function open is called to initiate the - process of the iteration. The function next shall read the next record from - the set of the record candidates. The record is read into the record buffer - of the joined table. The function close shall perform the finalizing actions - for the iteration. -*/ - -class JOIN_TAB_SCAN_MRR: public JOIN_TAB_SCAN -{ - /* Interface object to generate key ranges for MRR */ - RANGE_SEQ_IF range_seq_funcs; - - /* Number of ranges to be processed by the MRR interface */ - uint ranges; - - /* Flag to to be passed to the MRR interface */ - uint mrr_mode; - - /* MRR buffer assotiated with this join cache */ - HANDLER_BUFFER mrr_buff; - - /* Shall initialize the MRR buffer */ - virtual void init_mrr_buff() - { - cache->setup_aux_buffer(mrr_buff); - } - -public: - - JOIN_TAB_SCAN_MRR(JOIN *j, JOIN_TAB *tab, uint flags, RANGE_SEQ_IF rs_funcs) - :JOIN_TAB_SCAN(j, tab), range_seq_funcs(rs_funcs), mrr_mode(flags) {} - - uint aux_buffer_incr(ulong recno); - - int open(); - - int next(); - -}; - -/* - The class JOIN_CACHE_BKA is used when the BKA join algorithm is - employed to perform a join operation -*/ - -class JOIN_CACHE_BKA :public JOIN_CACHE -{ -private: - - /* Flag to to be passed to the companion JOIN_TAB_SCAN_MRR object */ - uint mrr_mode; - - /* - This value is set to 1 by the class prepare_look_for_matches method - and back to 0 by the class get_next_candidate_for_match method - */ - uint rem_records; - - /* - This field contains the current association label set by a call of - the multi_range_read_next handler function. - See the function JOIN_CACHE_BKA::get_curr_key_association() - */ - uchar *curr_association; - -protected: - - /* - Get the number of ranges in the cache buffer passed to the MRR - interface. For each record its own range is passed. - */ - uint get_number_of_ranges_for_mrr() { return records; } - - /* - Setup the MRR buffer as the space between the last record put - into the join buffer and the very end of the join buffer - */ - int setup_aux_buffer(HANDLER_BUFFER &aux_buff) - { - aux_buff.buffer= end_pos; - aux_buff.buffer_end= buff+buff_size; - return 0; - } - - bool prepare_look_for_matches(bool skip_last); - - uchar *get_next_candidate_for_match(); - - bool skip_next_candidate_for_match(uchar *rec_ptr); - - void read_next_candidate_for_match(uchar *rec_ptr); - -public: - - /* - This constructor creates an unlinked BKA join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. - The MRR mode initially is set to 'flags'. - */ - JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags) - :JOIN_CACHE(j, tab), mrr_mode(flags) {} - /* - This constructor creates a linked BKA join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. The parameter 'prev' specifies the previous - cache object to which this cache is linked. - The MRR mode initially is set to 'flags'. - */ - JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE *prev) - :JOIN_CACHE(j, tab, prev), mrr_mode(flags) {} - - uchar **get_curr_association_ptr() { return &curr_association; } - - /* Initialize the BKA cache */ - int init(); - - enum Join_algorithm get_join_alg() { return BKA_JOIN_ALG; } - - bool is_key_access() { return TRUE; } - - /* Get the key built over the next record from the join buffer */ - uint get_next_key(uchar **key); - - /* Check index condition of the joined table for a record from BKA cache */ - bool skip_index_tuple(char *range_info); - -}; - - - -/* - The class JOIN_CACHE_BKAH is used when the BKAH join algorithm is - employed to perform a join operation -*/ - -class JOIN_CACHE_BKAH :public JOIN_CACHE_BNLH -{ - -private: - /* Flag to to be passed to the companion JOIN_TAB_SCAN_MRR object */ - uint mrr_mode; - - /* - This flag is set to TRUE if the implementation of the MRR interface cannot - handle range association labels and does not return them to the caller of - the multi_range_read_next handler function. E.g. the implementation of - the MRR inteface for the Falcon engine could not return association - labels to the caller of multi_range_read_next. - The flag is set by JOIN_CACHE_BKA::init() and is not ever changed. - */ - bool no_association; - - /* - This field contains the association label returned by the - multi_range_read_next function. - See the function JOIN_CACHE_BKAH::get_curr_key_association() - */ - uchar *curr_matching_chain; - -protected: - - uint get_number_of_ranges_for_mrr() { return key_entries; } - - /* - Initialize the MRR buffer allocating some space within the join buffer. - The entire space between the last record put into the join buffer and the - last key entry added to the hash table is used for the MRR buffer. - */ - int setup_aux_buffer(HANDLER_BUFFER &aux_buff) - { - aux_buff.buffer= end_pos; - aux_buff.buffer_end= last_key_entry; - return 0; - } - - bool prepare_look_for_matches(bool skip_last); - - /* - The implementations of the methods - - get_next_candidate_for_match - - skip_recurrent_candidate_for_match - - read_next_candidate_for_match - are inherited from the JOIN_CACHE_BNLH class - */ - -public: - - /* - This constructor creates an unlinked BKAH join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. - The MRR mode initially is set to 'flags'. - */ - JOIN_CACHE_BKAH(JOIN *j, JOIN_TAB *tab, uint flags) - :JOIN_CACHE_BNLH(j, tab), mrr_mode(flags) {} - - /* - This constructor creates a linked BKAH join cache. The cache is to be - used to join table 'tab' to the result of joining the previous tables - specified by the 'j' parameter. The parameter 'prev' specifies the previous - cache object to which this cache is linked. - The MRR mode initially is set to 'flags'. - */ - JOIN_CACHE_BKAH(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE *prev) - :JOIN_CACHE_BNLH(j, tab, prev), mrr_mode(flags) {} - - uchar **get_curr_association_ptr() { return &curr_matching_chain; } - - /* Initialize the BKAH cache */ - int init(); - - enum Join_algorithm get_join_alg() { return BKAH_JOIN_ALG; } - - /* Check index condition of the joined table for a record from BKAH cache */ - bool skip_index_tuple(char *range_info); -}; - +#include "sql_join_cache.h" enum_nested_loop_state sub_select_cache(JOIN *join, JOIN_TAB *join_tab, bool end_of_records); |