role

  • AHI is for leaf nodes to reduce the cost of B-tree addressing (height + in-page addressing).

How to do

Run key(index_id+ Fileds +bytes):value(the physical address of the record) to locate the data directly. There are a couple of details

  • Fileds +bytes How to choose
  • Key (Index_id + Fileds +bytes) uniquely identifies a record and selects the leftmost or rightmost record if duplication exists.

In the following figure, if fileds is 2 and bytes is 0, create (a,a),(a,b),(a,c),(a,d) keys (not considering cross-page cases). If left_side is True, the value of key(a,b) selects (a,b,1); otherwise, the value of key(a,b) selects (a,b,3).

How to use

The whole process

In the btr_cur_search_to_nth_level function

  • If certain conditions are met, btr_search_GUess_ON_hash is used to locate the record, and btr_search_check_GUESS is used to determine the validity of the record.
  • If the AHI cannot locate or fails, search_loop searches layer by layer.
  • When the search is complete, if the layer ultimately located is a leaf node, btr_search_info_update is called to update AHI related information.

code

Btr_cur_search_to_nth_level (dict_index_t, /*! < in: index */ ulint level, /*! < in: the tree level of search */ ulint mode, /*! < in: PAGE_CUR_L, ... ; Inserts should always be made using PAGE_CUR_LE to search the position! * /...). { /* Use of AHI is disabled for intrinsic table as these tables re-use the index-id and AHI validation is based on index-id. */ if (rw_lock_get_writer(btr_get_search_latch(index)) == RW_LOCK_NOT_LOCKED && latch_mode <= BTR_MODIFY_LEAF && info->last_hash_succ && ! index->disable_ahi && ! estimate # ifdef PAGE_CUR_LE_OR_EXTENDS && mode ! = PAGE_CUR_LE_OR_EXTENDS # endif /* PAGE_CUR_LE_OR_EXTENDS */ && ! dict_index_is_spatial(index) /* If ! has_search_latch, we do a dirty read of btr_search_enabled below, and btr_search_guess_on_hash() will have to check it again. */ && UNIV_LIKELY(btr_search_enabled) && ! modify_external && btr_search_guess_on_hash(index, info, tuple, mode, latch_mode, cursor, has_search_latch, mtr)) { /* Search using the hash index succeeded */ ut_ad(cursor->up_match ! = ULINT_UNDEFINED || mode ! = PAGE_CUR_GE); ut_ad(cursor->up_match ! = ULINT_UNDEFINED || mode ! = PAGE_CUR_LE); ut_ad(cursor->low_match ! = ULINT_UNDEFINED || mode ! = PAGE_CUR_LE); btr_cur_n_sea++; DBUG_VOID_RETURN; } // Initial, get the index root (space_id, page_no) space = dict_index_get_space(index); page_no = dict_index_get_page(index); search_loop: // Loop and search layer by layer until the passed level "level" is reached. Block = buf_page_get_gen(space, zip_size, page_no, rw_latch, guess, buf_mode, file, line, mtr); For a given Tuple, a record that meets certain criteria (depending on the mode passed in, for example, PAGE_CUR_L) stores the search result in a page_cursor. The page_cursor structure is simple:  // struct page_cur_t{ // byte* rec; / *! < pointer to a record on page */ // buf_block_t* block; / *! < pointer to the block containing rec */ // }; page_cur_search_with_match(block, index, tuple, page_mode, &up_match, &up_bytes, &low_match, &low_bytes, page_cursor); if (level ! = height) {// If the number of levels is not reached, obtain the index page page_no of the lower nodes stored in the middle node // note: The Value of the intermediate node is a Pointer (page_no) that points to a child node (intermediate node or leaf node) node_ptr = page_cur_get_rec(page_cursor); /* Go to the child node */ page_no = btr_node_ptr_get_child_page_no(node_ptr, offsets); // Continue at the next level to find goto search_loop; } // The function exits if (btr_search_enabled &&! index->disable_ahi) { btr_search_info_update(index, cursor); }}Copy the code

Position and judge validity

Positioning – btr_search_guess_on_hash
  • First, the prefix index query condition provided by the user must be greater than or equal to the number of prefix index columns when AHI was built. There is a possibility: The n_fields of search_info index and the cur_n_fields of block AHI are different, but we do not know which block the query falls on. The n_fields of search_info index are used to calculate the fold. Query AHI;
  • An S lock on &btr_search_latch is required to retrieve the AHI;
  • If the AHI is not hit, btr_search_INFO ::last_hash_succ is set to false, which means that subsequent queries do not use the AHI until the next query is analyzed (btr_search_failure);
  • For the record pointer obtained from the AHI, you also need to check for the correct record location (bTR_SEARCH_CHECK_GUESS) against the current query mode.
Check record validity bTR_search_check_GUESS

Judging the validity of the record depends on the query mode, see the comments for details.

btr_search_check_guess( btr_cur_t* cursor, ibool can_only_compare_to_cursor_rec, const dtuple_t* tuple, ulint mode, mtr_t* mtr) { rec_t* rec; ulint n_unique; ulint match; int cmp; mem_heap_t* heap = NULL; ulint offsets_[REC_OFFS_NORMAL_SIZE]; ulint* offsets = offsets_; ibool success = FALSE; rec_offs_init(offsets_); n_unique = dict_index_get_n_unique_in_tree(cursor->index); rec = btr_cur_get_rec(cursor); ut_ad(page_rec_is_user_rec(rec)); match = 0; offsets = rec_get_offsets(rec, cursor->index, offsets, n_unique, &heap); cmp = cmp_dtuple_rec_with_match(tuple, rec, offsets, &match); If (mode == PAGE_CUR_GE) {// CMP >0,tuple is greater than rec, reC may be the leftmost record, such as AHI key is (a,b),tuple is (a,b,c), rec is (a,b,a), then this case does not work. if (cmp > 0) { goto exit_func; } cursor->up_match = match; if (match >= n_unique) { success = TRUE; goto exit_func; } } else if (mode == PAGE_CUR_LE) { if (cmp < 0) { goto exit_func; } cursor->low_match = match; } else if (mode == PAGE_CUR_G) { if (cmp >= 0) { goto exit_func; } } else if (mode == PAGE_CUR_L) { if (cmp <= 0) { goto exit_func; } } if (can_only_compare_to_cursor_rec) { /* Since we could not determine if our guess is right just by looking at the record under the cursor, return FALSE */ goto exit_func; } match = 0; When mode is PAGE_CUR_G and PAGE_CUR_GE, determine whether the record is the leftmost record that meets the AHI query key. Otherwise, the system determines whether the record is the right-most record that meets the AHI query key. if ((mode == PAGE_CUR_G) || (mode == PAGE_CUR_GE)) { rec_t* prev_rec; ut_ad(! page_rec_is_infimum(rec)); prev_rec = page_rec_get_prev(rec); if (page_rec_is_infimum(prev_rec)) { success = btr_page_get_prev(page_align(prev_rec), mtr) == FIL_NULL; goto exit_func; } offsets = rec_get_offsets(prev_rec, cursor->index, offsets, n_unique, &heap); cmp = cmp_dtuple_rec_with_match( tuple, prev_rec, offsets, &match); if (mode == PAGE_CUR_GE) { success = cmp > 0; } else { success = cmp >= 0; } goto exit_func; } else { rec_t* next_rec; ut_ad(! page_rec_is_supremum(rec)); next_rec = page_rec_get_next(rec); if (page_rec_is_supremum(next_rec)) { if (btr_page_get_next(page_align(next_rec), mtr) == FIL_NULL) { cursor->up_match = 0; success = TRUE; } goto exit_func; } offsets = rec_get_offsets(next_rec, cursor->index, offsets, n_unique, &heap); cmp = cmp_dtuple_rec_with_match( tuple, next_rec, offsets, &match); if (mode == PAGE_CUR_LE) { success = cmp < 0; cursor->up_match = match; } else { success = cmp <= 0; } } exit_func: if (UNIV_LIKELY_NULL(heap)) { mem_heap_free(heap); } return(success); }Copy the code

How to build AHI

fileds+bytes

The key is index_id+ Fileds +bytes.

What are the concepts of fileds and bytes

See www.jianshu.com/p/0cdd573a8…

Structure field used to determine fileds and bytes

There are three structures that play a role in determining fileds and bytes: btr_CUR_T (cursor for tree queries), bTR_search_t (query information maintained for each index), and buf_BLOCK_T (block control structure). The information in bTR_cur_t is updated in the B tree location. After the B tree location, bTR_search_T is updated according to the information in bTR_CUR_T, which records the information related to the B tree query. Then, buf_BLOCK_T is updated according to the information in bTR_search_T. Records the query information about the Block.

Index ->search_info maintained for each index object of type Btr_search_t.

/** The search info struct in an index */ struct btr_search_t{ ... ulint n_fields; / *! < recommended prefix length for hash search: number of full fields */ ulint n_fields; / *! < recommended prefix: number of bytes in an incomplete field @see BTR_PAGE_MAX_REC_SIZE */ ibool left_side; / *! < TRUE or FALSE, depending on whether the leftmost record of several records with the same prefix should be indexed in the hash index */ . };Copy the code

Block controls related variables on the structure (buf_block_T)

struct buf_block_t{ ... volatile ulint n_bytes; / *! < recommended prefix length for hash search: number of bytes in an incomplete last field */ volatile ulint n_fields; / *! < recommended prefix length for hash search: number of full fields */ volatile bool left_side; / *! < true or false, depending on whether the leftmost record of several records with the same prefix should be indexed in the hash index */ . }Copy the code

The tree cursor

struct btr_cur_t { ... ulint up_match; / *! < If the search mode was PAGE_CUR_LE, the number of matched fields to the the first user record to the right of the cursor record after btr_cur_search_to_nth_level; for the mode PAGE_CUR_GE, the matched fields to the first user record AT THE CURSOR or to the right of it; NOTE that the up_match and low_match values may exceed the correct values for comparison to the adjacent user record if that record is on a different leaf page! (See the note in row_ins_duplicate_error_in_clust.) */ ulint up_bytes; / *! < number of matched bytes to the right at the time cursor positioned; only used internally in searches: not defined after the search */ ulint low_match; / *! < if search mode was PAGE_CUR_LE, the number of matched fields to the first user record AT THE CURSOR or to the left of it after btr_cur_search_to_nth_level; NOT defined for PAGE_CUR_GE or any other search modes; see also the NOTE in up_match! */ ulint low_bytes; / *! < number of matched bytes to the left at the time cursor positioned; only used internally in searches: not defined after the search */ ulint n_fields; / *! < prefix length used in a hash search if hash_node ! = NULL */ ulint n_bytes; / *! < hash prefix bytes if hash_node ! = NULL */ ... };Copy the code
Determines the timing of fileds and bytes

Referring to the overall flow, when the search is complete, btr_search_info_update is called to update AHI information if the layer that is finally located is a leaf node.

Cursor ->{up_match, up_bytes, low_match, low_bytes} have been set.

Cursor ->{up_match, up_bytes, low_match, low_bytes} to update the search info of index.

The path is btr_search_info_update->btr_search_info_update_slow->btr_search_info_update_hash.

There are two cases where you need to update btr_search_t->{n_fields,n_bytes,left_side}.

  • Btr_search_t ->n_hash_potential is 0: search info is initialized for the first time or the last query could not determine a unique record based on the query condition.
  • Cursor ->low_match; cursor->low_bytes; info->n_fields; info->n_bytes; If the info suggestion is to build the AHI based on the leftmost record of the same prefix, it does not meet the current query requirements and needs to generate the suggestion again. (Add a picture)
	cmp = ut_pair_cmp(info->n_fields, info->n_bytes,
			  cursor->low_match, cursor->low_bytes);
	if (info->left_side ? cmp <= 0 : cmp > 0) {
		goto set_new_recomm;
	}
Copy the code

Info ->{n_fields,n_bytes,left_side} {info->n_fields, info->n_bytes, info->left_side} is selected to minimize the computation cost of the unique index without exceeding the number of columns. The value of index->info->left_side determines whether the leftmost or right-most record of the same prefix index is stored on the same data page.

See the notes for details.

set_new_recomm: /* We have to set a new recommendation; skip the hash analysis for a while to avoid unnecessary CPU time usage when there is no chance for success */ info->hash_analysis = 0; cmp = ut_pair_cmp(cursor->up_match, cursor->up_bytes, cursor->low_match, cursor->low_bytes); If (CMP ==0) {// CMP ==0 indicates that a record cannot be uniquely identified according to the query conditions. For example, if (CMP == b), low is located to A, and up is located to C. info->n_hash_potential = 0; /* For extra safety, we set some sensible values here */ info->n_fields = 1; info->n_bytes = 0; info->left_side = TRUE; } else if (cmp > 0) { //cm info->n_hash_potential = 1; If (cursor->up_match >= n_unique) {//n_unique info->n_fields = n_unique; info->n_bytes = 0; } else if (cursor->low_match < cursor->up_match) {if (cursor->low_match < cursor->up_match) {if (cursor->low_match < cursor->up_match) { For example, if the query condition is (a,b,c), low_match is (a), and up_match is (a,b,c), use (A, B is sufficient to locate up_match). Also, when low_match=0, n_fields is set to 1, which is sufficient. info->n_fields = cursor->low_match + 1; info->n_bytes = 0; } else { info->n_fields = cursor->low_match; info->n_bytes = cursor->low_bytes + 1; } info->left_side = TRUE; } else { info->n_hash_potential = 1; if (cursor->low_match >= n_unique) { info->n_fields = n_unique; info->n_bytes = 0; } else if (cursor->low_match > cursor->up_match) { info->n_fields = cursor->up_match + 1; info->n_bytes = 0; } else { info->n_fields = cursor->up_match; info->n_bytes = cursor->up_bytes + 1; } info->left_side = FALSE; }Copy the code
static void btr_search_info_update_hash( btr_search_t* info, btr_cur_t* cursor) { dict_index_t* index = cursor->index; ulint n_unique; int cmp; ut_ad(! rw_lock_own(btr_get_search_latch(index), RW_LOCK_S)); ut_ad(! rw_lock_own(btr_get_search_latch(index), RW_LOCK_X)); if (dict_index_is_ibuf(index)) { /* So many deletes are performed on an insert buffer tree that we do not consider a hash index useful on it: */ return; } n_unique = dict_index_get_n_unique_in_tree(index); if (info->n_hash_potential == 0) { goto set_new_recomm; } /* Test if the search would have succeeded using the recommended hash prefix */ if (info->n_fields >= n_unique && cursor->up_match >= n_unique) { increment_potential: info->n_hash_potential++; return; } cmp = ut_pair_cmp(info->n_fields, info->n_bytes, cursor->low_match, cursor->low_bytes); if (info->left_side ? cmp <= 0 : cmp > 0) { goto set_new_recomm; } cmp = ut_pair_cmp(info->n_fields, info->n_bytes, cursor->up_match, cursor->up_bytes); if (info->left_side ? cmp <= 0 : cmp > 0) { goto increment_potential; } set_new_recomm: /* We have to set a new recommendation; skip the hash analysis for a while to avoid unnecessary CPU time usage when there is no chance for success */ info->hash_analysis = 0; cmp = ut_pair_cmp(cursor->up_match, cursor->up_bytes, cursor->low_match, cursor->low_bytes); If (CMP ==0) {// CMP ==0 indicates that a record cannot be uniquely identified according to the query conditions. For example, if (CMP == b), low is located to A, and up is located to C. info->n_hash_potential = 0; /* For extra safety, we set some sensible values here */ info->n_fields = 1; info->n_bytes = 0; info->left_side = TRUE; } else if (cmp > 0) { info->n_hash_potential = 1; if (cursor->up_match >= n_unique) { info->n_fields = n_unique; info->n_bytes = 0; } else if (cursor->low_match < cursor->up_match) { info->n_fields = cursor->low_match + 1; info->n_bytes = 0; } else { info->n_fields = cursor->low_match; info->n_bytes = cursor->low_bytes + 1; } info->left_side = TRUE; } else { info->n_hash_potential = 1; if (cursor->low_match >= n_unique) { info->n_fields = n_unique; info->n_bytes = 0; } else if (cursor->low_match > cursor->up_match) { info->n_fields = cursor->up_match + 1; info->n_bytes = 0; } else { info->n_fields = cursor->up_match; info->n_bytes = cursor->up_bytes + 1; } info->left_side = FALSE; }}Copy the code
How to apply the n_fileds and n_bytes suggestions at the Index layer to the block layer?

The code path is btr_search_info_update->btr_search_info_update_slow->btr_search_update_block_hash_info. Although AHI generates suggestions for Index, the key:value mapping relationship is finally established on block. Block level records the query information of block. If certain conditions are met, AHI is established. Question? What innoDB does if the fields and bytes suggested by index change after a block is built.

How do I avoid frequent builds of AHI

  • Index level bTR_search_t, how to avoid frequent generation of new recommendations
  • Block level buf_block_t, how to determine whether the block is worth building

Btr_search_t has a hash_analysis variable. When a new suggestion is generated, hash_analysis is reset to 0. After reset, within the query BTR_SEARCH_HASH_ANALYSIS, They don’t even try to generate new suggestions.

At the block level, how to determine whether the block is worth building.

  • First, btr_search_t has a variable n_hash_potential, and when n_hash_potential>BTR_SEARCH_BUILD_LIMIT(100), the current recommendation for this index is feasible.
  • Then, there is the variable n_hash_HELPS on buf_block_T, and when it has more than 1/16 of the successes with the AHI on the data page block and more than 100 of the successes with the current prefix index, The AHI cache information needs to be constructed for the data page if the user record on the data page or the currently recommended prefix index information has changed with more than 2 times the potential success with the AHI.
if ((block->n_hash_helps > page_get_n_recs(block->frame) / BTR_SEARCH_PAGE_BUILD_LIMIT) && (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT)) { if ((! block->index) || (block->n_hash_helps > 2 * page_get_n_recs(block->frame)) || (block->n_fields ! = block->curr_n_fields) || (block->n_bytes ! = block->curr_n_bytes) || (block->left_side ! = block->curr_left_side)) { /* Build a new hash index on the page */ return(TRUE); }Copy the code

Incrementing logic of buf_block_t -> n_hash_HELPS. If the query mode for this block is still the same as that for index, it can be incremented; otherwise, it can be reset.

if ((block->n_hash_helps > 0) && (info->n_hash_potential > 0) && (block->n_fields == info->n_fields) && (block->n_bytes == info->n_bytes) && (block->left_side == info->left_side)) { if ((block->index) && (block->curr_n_fields == info->n_fields) && (block->curr_n_bytes == info->n_bytes) && (block->curr_left_side == info->left_side)) { /* The search  would presumably have succeeded using the hash index */ info->last_hash_succ = TRUE; } block->n_hash_helps++; } else { block->n_hash_helps = 1; block->n_fields = info->n_fields; block->n_bytes = info->n_bytes; block->left_side = info->left_side; }Copy the code

AHI Concurrency control

Juejin. Cn/post / 684490… Developer.aliyun.com/article/410… Mysql.taobao.org/monthly/201… www.jianshu.com/p/0cdd573a8…

The pit of AHI

Mp.weixin.qq.com/s/nW9FARyeq…