MySQL · 源码分析 · btr_cur_search_to_nth_level 函数分析

本文基于MySQL Community 8.0.25 Version

概述

btr_cur_search_to_nth_level 函数实现innodb中btree cursor的定位，从btree顶层的root到具体的位置，同时在该函数实现了btree的并发访问控制。

btr_cur_search_to_nth_level函数有1000多行的代码，阅读起来不太直观方便，本文对该函数的分析是基于mysql-8.0.25 源码，通过给关键函数模块框架加注释，同时删除一些非核心的代码来进行分析，目的是让阅读本文后，能对该函数有快速直观的了解，方便后续更深入的理解。

源码分析

  1. void btr_cur_search_to_nth_level(
  2.     dict_index_t *index,   /*!< in: index */
  3.     ulint level,           /*!< in: the tree level of search */
  4.     const dtuple_t *tuple, /*!< in: data tuple; NOTE: n_fields_cmp in
  5.                            tuple must be set so that it cannot get
  6.                            compared to the node ptr page number field! */
  7.     page_cur_mode_t mode,  /*!< in: PAGE_CUR_L, ...;
  8.                            Inserts should always be made using
  9.                            PAGE_CUR_LE to search the position! */
  10.     ...)
  11. {
  12.     // 变量定义及一些基本的assertion
  13.   page_t *page = nullptr; /* remove warning */
  14.   buf_block_t *block;
  15.     ...
  17.   // 使用ahi查询，查询成功返回
  18.   if (btr_search_guess_on_hash(index, info, tuple, mode, latch_mode, cursor,
  19.                                has_search_latch, mtr)) {
  20.     /* Search using the hash index succeeded */
  21.     return;
  22.   }
  24.   // 给index 加latch
  25.   switch (latch_mode) {
  26.     case BTR_MODIFY_TREE:
  27.       if (...) {
  28.         mtr_x_lock(dict_index_get_lock(index), mtr);
  29.       } else {
  30.         mtr_sx_lock(dict_index_get_lock(index), mtr);
  31.       }
  32.       upper_rw_latch = RW_X_LATCH;
  33.       break;
  34.     case BTR_CONT_MODIFY_TREE:
  35.     case BTR_CONT_SEARCH_TREE:
  36.       if (...) {
  37.         upper_rw_latch = RW_X_LATCH;
  38.       } else {
  39.         upper_rw_latch = RW_NO_LATCH;
  40.       }
  41.       break;
  42.     default:
  43.       if (!srv_read_only_mode) {
  44.         if (...) {
  45.           mtr_s_lock(dict_index_get_lock(index), mtr);
  46.         } else {
  47.           /* BTR_MODIFY_EXTERNAL needs to be excluded */
  48.           mtr_sx_lock(dict_index_get_lock(index), mtr);
  49.         }
  50.         upper_rw_latch = RW_S_LATCH;
  51.       } else {
  52.         upper_rw_latch = RW_NO_LATCH;
  53.       }
  54.   }
  56.     // 初始化root page_id
  57.   const space_id_t space = dict_index_get_space(index);
  58.   const page_size_t page_size(dict_table_page_size(index->table));
  60.   /* Start with the root page. */
  61.   page_id_t page_id(space, dict_index_get_page(index)); // root page id
  63.   // 非叶子节点调整search mode
  64.   switch (mode) {
  65.     case PAGE_CUR_GE:
  66.       page_mode = PAGE_CUR_L;
  67.       break;
  68.     case PAGE_CUR_G:
  69.       page_mode = PAGE_CUR_LE;
  70.       break;
  71.     default:
  72.       page_mode = mode;
  73.       break;
  74.   }
  76. // 循环、逐层的查找，直至达到传入的层数 level，一般是0（即叶子节点）
  77. // 此处的分析忽略Spatial index的部分
  78. // 从Buffer Pool或磁盘中得到索引页
  79. search_loop:
  80.   // 更新rw_latch for page latch mode
  81.   if (height != 0) {
  82.     if ((latch_mode != BTR_MODIFY_TREE || height == level) &&
  83.         !retrying_for_search_prev) {
  84.         rw_latch = RW_SX_LATCH;
  85.       } else {
  86.         rw_latch = upper_rw_latch;
  87.       }
  88.     }
  89.   } else if (latch_mode <= BTR_MODIFY_LEAF) {
  90.     rw_latch = latch_mode;
  92.         // 如果判断应该操作change buffer，则更新fetch mode为从buffer pool中获取
  93.     if (btr_op != BTR_NO_OP &&
  94.         ibuf_should_try(index, btr_op != BTR_INSERT_OP)) {
  95.       /* Try to buffer the operation if the leaf
  96.       page is not in the buffer pool. */
  98.       fetch = btr_op == BTR_DELETE_OP ? Page_fetch::IF_IN_POOL_OR_WATCH
  99.                                       : Page_fetch::IF_IN_POOL;
  100.     }
  101.   }
  103. // 获取page
  104. retry_page_get:
  105.   block = buf_page_get_gen(page_id, page_size, rw_latch, guess, fetch, file, line, mtr);
  107.   // 当block为null时，尝试change buffer操作
  108.   if (block == nullptr) {
  109.     switch (btr_op) {
  110.       case BTR_INSERT_OP:
  111.       case BTR_INSERT_IGNORE_UNIQUE_OP:
  112.         if (ibuf_insert(IBUF_OP_INSERT, tuple, index, page_id, page_size,
  113.                         cursor->thr)) {
  114.           cursor->flag = BTR_CUR_INSERT_TO_IBUF;
  115.           goto func_exit;
  116.         }
  117.         break;
  119.       case BTR_DELMARK_OP:
  120.         if (ibuf_insert(IBUF_OP_DELETE_MARK, tuple, index, page_id, page_size,
  121.                         cursor->thr)) {
  122.           cursor->flag = BTR_CUR_DEL_MARK_IBUF;
  124.           goto func_exit;
  125.         }
  126.         break;
  128.       case BTR_DELETE_OP:
  129.         if (!row_purge_poss_sec(cursor->purge_node, index, tuple)) {
  130.           /* The record cannot be purged yet. */
  131.           cursor->flag = BTR_CUR_DELETE_REF;
  132.         } else if (ibuf_insert(IBUF_OP_DELETE, tuple, index, page_id, page_size,
  133.                                cursor->thr)) {
  134.           /* The purge was buffered. */
  135.           cursor->flag = BTR_CUR_DELETE_IBUF;
  136.         } else {
  137.           /* The purge could not be buffered. */
  138.           buf_pool_watch_unset(page_id);
  139.           break;
  140.         }
  141.         buf_pool_watch_unset(page_id);
  142.         goto func_exit;
  144.       default:
  145.         ut_error;
  146.     }
  147.         // 操作change buffer没有成功，则更新fetch mode为从disk中获取该page，然后再次获取该page
  148.     fetch = cursor->m_fetch_mode;
  149.     goto retry_page_get;
  150.   }
  152.   // 如果search prev, 读取及latch 左节点
  153.   if (retrying_for_search_prev && height != 0) {
  154.       //获取左节点page_no
  155.     left_page_no = btr_page_get_prev(buf_block_get_frame(block), mtr);
  157.     if (left_page_no != FIL_NULL) {
  158.       get_block = buf_page_get_gen(page_id_t(page_id.space(), left_page_no), page_size,
  159.                            rw_latch, nullptr, fetch, file, line, mtr);
  160.     }
  162.     // 重新获取该page，并给该page加latch，因为之前该page是no latch，所以需要重新获取并加latch
  163.     block = buf_page_get_gen(page_id, page_size, rw_latch, nullptr, fetch, file, line, mtr);
  164.   }
  166.   page = buf_block_get_frame(block);
  168.     // 当root page同时为Leaf page，latch不符合预期时，则重新循环获取page
  169.   if (height == ULINT_UNDEFINED && page_is_leaf(page) &&
  170.       rw_latch != RW_NO_LATCH && rw_latch != root_leaf_rw_latch) {
  171.     goto search_loop;
  172.   }
  174.   // root page时，更新信息
  175.   if (UNIV_UNLIKELY(height == ULINT_UNDEFINED)) {
  176.     /* We are in the root node */
  178.     height = btr_page_get_level(page, mtr);
  179.     root_height = height;
  180.     cursor->tree_height = root_height + 1;
  182.     info->root_guess = block;
  183.   }
  185.     // 当达到leaf层时
  186.   if (height == 0) {
  187.     // 给叶子节点加latch
  188.     if (rw_latch == RW_NO_LATCH) {
  189.       latch_leaves = btr_cur_latch_leaves(block, page_id, page_size, latch_mode,
  190.                                           cursor, mtr);
  191.     }
  192.     // 释放mtr中index latch和和上层blocks
  193.     switch (latch_mode) {
  194.       case BTR_MODIFY_TREE:
  195.       case BTR_CONT_MODIFY_TREE:
  196.       case BTR_CONT_SEARCH_TREE:
  197.         break;
  198.       default:
  199.           // 释放index latch
  200.         if (!s_latch_by_caller && !srv_read_only_mode && !modify_external) {
  201.           mtr_release_s_latch_at_savepoint(mtr, savepoint,
  202.                                            dict_index_get_lock(index));
  203.         }
  204.                 // 释放各层blocks
  205.         for (; n_releases < n_blocks; n_releases++) {
  206.           if (n_releases == 0 && modify_external) {
  207.             /* keep latch of root page */
  208.             continue;
  209.           }
  210.           mtr_release_block_at_savepoint(mtr, tree_savepoints[n_releases],
  211.                                          tree_blocks[n_releases]);
  212.         }
  213.     }
  215.     page_mode = mode;
  216.   }
  218.   // index是spatial index，进行一些page search mode调整
  219.   if (dict_index_is_spatial(index)) {
  220.     if (page_mode == PAGE_CUR_RTREE_LOCATE && level == height) {
  221.       if (level == 0) {
  222.         page_mode = PAGE_CUR_LE;
  223.       } else {
  224.         page_mode = PAGE_CUR_RTREE_GET_FATHER;
  225.       }
  226.     }
  228.     if (page_mode == PAGE_CUR_RTREE_INSERT) {
  229.       page_mode = (level == height) ? PAGE_CUR_LE : PAGE_CUR_RTREE_INSERT;
  230.     }
  231.   }
  233.   // 在page中找到rec并保存到page_cursor中
  234.   page_cur_search_with_match_bytes(block, index, tuple, page_mode, &up_match,
  235.                                      &up_bytes, &low_match, &low_bytes,
  236.                                      page_cursor);
  238.   /* If this is the desired level, leave the loop */
  240.   // 没有达到目的level
  241.   if (level != height) {
  242.     // 往下层推进
  243.     height--;
  245.     /* If the rec is the first or last in the page for
  246.     pessimistic delete intention, it might cause node_ptr insert
  247.     for the upper level. We should change the intention and retry.
  248.     */
  249.     // 可能导致SMO，重置index root page为search page，重新开始循环
  250.     if (latch_mode == BTR_MODIFY_TREE &&
  251.         btr_cur_need_opposite_intention(page, lock_intention, node_ptr)) {
  252.       page_id.reset(space, dict_index_get_page(index));
  254.       goto search_loop;
  255.     }
  257.     // spatial index
  258.     if (dict_index_is_spatial(index)) {
  259.       ...
  260.     }
  262.     /* If the first or the last record of the page
  263.     or the same key value to the first record or last record,
  264.     the another page might be choosen when BTR_CONT_MODIFY_TREE.
  265.     So, the parent page should not released to avoiding deadlock
  266.     with blocking the another search with the same key value. */
  267.     // 判断是否是第一个或者最后一个rec，或者和他们match，设置变量detected_same_key_root
  268.     if (!detected_same_key_root && lock_intention == BTR_INTENTION_BOTH &&
  269.         !dict_index_is_unique(index) && latch_mode == BTR_MODIFY_TREE &&
  270.         (up_match >= rec_offs_n_fields(offsets) - 1 ||
  271.          low_match >= rec_offs_n_fields(offsets) - 1)) {
  272.        // 为第一个或者最后一个
  273.       if (node_ptr == first_rec || page_rec_is_last(node_ptr, page)) {
  274.         detected_same_key_root = true;
  275.       } else {
  276.            // 比较是否和第一个或者最后一个rec match
  277.         detected_same_key_root = true;
  278.       }
  279.     }
  281.     /* If the page might cause modify_tree,
  282.     we should not release the parent page's lock. */
  283.     if (!detected_same_key_root && latch_mode == BTR_MODIFY_TREE &&
  284.         !btr_cur_will_modify_tree(index, page, lock_intention, node_ptr,
  285.                                   node_ptr_max_size, page_size, mtr) &&
  286.         !rtree_parent_modified) {
  287.       /* we can release upper blocks */
  288.       for (; n_releases < n_blocks; n_releases++) {
  289.         if (n_releases == 0) {
  290.           /* we should not release root page
  291.           to pin to same block. */
  292.           continue;
  293.         }
  295.         /* release unused blocks to unpin */
  296.         mtr_release_block_at_savepoint(mtr, tree_savepoints[n_releases],
  297.                                        tree_blocks[n_releases]);
  298.       }
  299.     }
  301.     // 为BTR_MODIFY_TREE时给root page加 sx latch，给他其他page加x latch
  302.     if (height == level && latch_mode == BTR_MODIFY_TREE) {
  303.       ut_ad(upper_rw_latch == RW_X_LATCH);
  304.       /* we should sx-latch root page, if released already.
  305.       It contains seg_header. */
  306.       if (n_releases > 0) {
  307.         mtr_block_sx_latch_at_savepoint(mtr, tree_savepoints[0],
  308.                                         tree_blocks[0]);
  309.       }
  311.       /* x-latch the branch blocks not released yet. */
  312.       for (ulint i = n_releases; i <= n_blocks; i++) {
  313.         mtr_block_x_latch_at_savepoint(mtr, tree_savepoints[i], tree_blocks[i]);
  314.       }
  315.     }
  317.     /* We should consider prev_page of parent page, if the node_ptr
  318.     is the leftmost of the page. because BTR_SEARCH_PREV and
  319.     BTR_MODIFY_PREV latches prev_page of the leaf page. */
  320.     if ((latch_mode == BTR_SEARCH_PREV || latch_mode == BTR_MODIFY_PREV) &&
  321.         !retrying_for_search_prev) {
  322.       if (btr_page_get_prev(page, mtr) != FIL_NULL &&
  323.           page_rec_is_first(node_ptr, page)) {
  324.         if (leftmost_from_level == 0) {
  325.           leftmost_from_level = height + 1;
  326.         }
  327.       } else {
  328.         leftmost_from_level = 0;
  329.       }
  331.       if (height == 0 && leftmost_from_level > 0) {
  332.         /* should retry to get also prev_page
  333.         from level==leftmost_from_level. */
  334.         retrying_for_search_prev = true;
  336.         page_id.reset(space, tree_blocks[idx]->page.id.page_no());
  338.         for (ulint i = n_blocks - (leftmost_from_level - 1); i <= n_blocks;
  339.              i++) {
  340.           mtr_release_block_at_savepoint(mtr, tree_savepoints[i],
  341.                                          tree_blocks[i]);
  342.         }
  344.         n_blocks -= (leftmost_from_level - 1);
  345.         height = leftmost_from_level;
  347.         /* replay up_match, low_match */
  348.         for (ulint i = 0; i < n_blocks; i++) {
  349.           page_cur_search_with_match(tree_blocks[i], index, tuple, page_mode,
  350.                                      &up_match, &low_match, page_cursor,
  351.                                      rtr_info);
  352.         }
  354.         goto search_loop;
  355.       }
  356.     }
  358.     //重置page_id为下层子节点page，然后进入下层查找
  359.     page_id.reset(space, btr_node_ptr_get_child_page_no(node_ptr, offsets));
  361.     n_blocks++;
  363.     if (UNIV_UNLIKELY(height == 0 && dict_index_is_ibuf(index))) {
  364.       /* We're doing a search on an ibuf tree and we're one
  365.       level above the leaf page. */
  367.       ut_ad(level == 0);
  369.       fetch = cursor->m_fetch_mode;
  370.       rw_latch = RW_NO_LATCH;
  371.       goto retry_page_get;
  372.     }
  374.     // 循环到下层
  375.     goto search_loop;
  376.   }
  378.   // 找到对应rec位置，更新cursor的low_match up_match字段
  379.   if (level != 0) {
  380.       // assert page not corrupt
  381.     btr_assert_not_corrupted(block, index);
  383.     if (page_mode <= PAGE_CUR_LE) {
  384.       cursor->low_match = low_match;
  385.       cursor->up_match = up_match;
  386.     }
  387.   } else {
  388.     cursor->low_match = low_match;
  389.     cursor->low_bytes = low_bytes;
  390.     cursor->up_match = up_match;
  391.     cursor->up_bytes = up_bytes;
  393.     // 根据查询的结果，更新该index的ahi信息
  394.     if (btr_search_enabled && !index->disable_ahi) {
  395.       btr_search_info_update(index, cursor);
  396.     }
  397.   }
  399. // 函数退出
  400. // 释放相关堆内存等
  401. func_exit:
  402.   if (UNIV_LIKELY_NULL(heap)) {
  403.     mem_heap_free(heap);
  404.   }
  406.   if (retrying_for_search_prev) {
  407.     ut_free(prev_tree_blocks);
  408.     ut_free(prev_tree_savepoints);
  409.   }
  411.     ... 
  412. }