關于innodb中查詢的定位方式

2024-09-07 22:12:33

字體：大中小

來源：轉載

供稿：網友

涉及源碼文件
page0cur.cc
page0page.h
page0page.cc
rem0cmp.cc
為什么談及定位方法，因為在innodb中，比如一個插入語句我們需要定位在哪里插入(PAGE_CUR_LE)，比如一個查詢語句我們需要定位到其第一個需要讀取數據的位置，因此定位方法是查詢的根本。而找到這個記錄位置后實際上是用一個叫做page_cur_t結構體進行存儲，暫且叫他cursor游標

struct page_cur_t{
    const dict_index_t* index;
    rec_t*      rec;    /*!< pointer to a record on page */
    ulint*      offsets;
    buf_block_t*    block; /*!< pointer to the block containing rec */
};
其中包含了本index的數據字典類容、實際的數據、記錄所在塊的信息等，下面我具體談一下定位方法，同時結合源碼來看它具體的實現。

我們先來明確一下概念：

記錄(rec)：通常為存儲在內存中物理記錄的完全拷貝，通常用一個unsigned char* 指針指向整個記錄
元組(dtuple)：物理記錄的邏輯體現，他就復雜得多，但是一個記錄(rec)對應一個元組(dtuple),由dtuple_t結構體表示，其中每一個field由一個dfield_t結構體表示，數據存儲在dfied_t的一個叫做void* data的指針中
可自行參考運維內參等其他書籍，這里就在簡單描述到這里，本文會出現相關術語。

一、查詢模式(search mode)
在innodb中的常用的search mode有如下幾個

/* Page cursor search modes; the values must be in this order! */
enum page_cur_mode_t {
    PAGE_CUR_UNSUPP = 0,
    PAGE_CUR_G = 1,
    PAGE_CUR_GE = 2,
    PAGE_CUR_L = 3,
    PAGE_CUR_LE = 4,
};
PAGE_CUR_G(>)
PAGE_CUR_GE(>=)
PAGE_CUR_L(<)
PAGE_CUR_LE(<=)
我們來討論一個問題考慮如下有序的數組

1,2,3,3,4,5,6,7
規律1:
如果我們查詢>=3(PAGE_CUR_GE)和<3(PAGE_CUR_L),那么自然我們需要將位置定位到2到3之間我們且用2-3表示

如果是>=3那么我們需要將記錄定位到3及[3(第一個),正無窮)
如果是<3那么我們需要將記錄定位到2及（負無窮,2]
也就是說>=3和<3定位的區間是相同的2-3
如果我們查詢<=3(PAGE_CUR_LE)和>3(PAGE_CUR_G),那么自然我們需要將位置定位到3到4之間我們且用3-4表示

如果是<=3那么我們需要將記錄定位到3及(負無窮,3(最后一個)]
如果是>3那么我們需要將記錄定位到4及[4,正無窮)
也就是說<=3和>3定位的區間是相同的3-4
那么我們將這里的區間兩個值記為low-high

規律2:
仔細分析后我們發現另外一個規律

(>) PAGE_CUR_G和(>=) PAGE_CUR_GE 都是取high
(< )PAGE_CUR_L和(<=) PAGE_CUR_LE 都是取low
為什么講這個東西，因為這兩個規律在innodb記錄定位中起到了關鍵作用，也直接影響到了innodb記錄查找的二分算法的實現方式。

二、matched_fields和matched_bytes
大家在源碼中能看到matched_fields和matched_bytes兩個值，那么他們代表什么意思呢？
以int類型為例，因為在函數cmp_dtuple_rec_with_match_bytes是逐個字段逐個字節進行比較的，關鍵代碼如下

while (cur_field < n_cmp) {
rec_byte = *rec_b_ptr++;
dtuple_byte = *dtuple_b_ptr++;}
比如int 2,int 3在innodb中內部表示為0X80000002和0X80000003,如果他們進行比較那么最終此field的比較為不相等(-1),那么matched_fields=0但是

0X 800000 02
0X 800000 03
我們能夠發現其中有3個字節是相同的及0X80 0X00 0X00 所以matched_bytes=3
簡單的說matched_fields為相同field數量,如果field不相同則會返回相同的字節數。
當然cmp_dtuple_rec_with_match_bytes對不同數據類型的比較方式也不相同如下:
switch (type->mtype) {
        case DATA_FIXBINARY:
        case DATA_BINARY:
        case DATA_INT:
        case DATA_SYS_CHILD:
        case DATA_SYS:
            break;
        case DATA_BLOB:
            if (type->prtype & DATA_BINARY_TYPE) {
                break;
            }
        default:
            ret = cmp_data(type->mtype, type->prtype,
                       dtuple_b_ptr, dtuple_f_len,
                       rec_b_ptr, rec_f_len);

            if (!ret) {
                goto next_field;
            }

            cur_bytes = 0;
            goto order_resolved;
        }
具體可以參考一下源碼，這里不再過多解釋

三、塊內二分查詢方法再析
為什么叫做再析，因為如運維內參已經對本函數進行了分析，這里主要分析查詢模式對二分法實現的影響，并且用圖進行說明你會有新的感悟！當然如果你對什么slot還不清楚請自行參考運維內參

簡單的說page_cur_search_with_match_bytes會調用cmp_dtuple_rec_with_match_bytes函數進行元組和記錄之間的比較，而塊內部比較方法就是先對所有的slot進行二分查找確定到某個slot以快速縮小范圍，然后在對slot內部使用類似二分查找的方法等到記錄，我們主要來分析一下slot內部的類二分法，因為它完全是我們查詢模式中兩個規律的完美體現，如下簡化的代碼片段以及我寫的注釋：

/* Perform linear search until the upper and lower records come to
    distance 1 of each other. */

    while (page_rec_get_next_const(low_rec) != up_rec) { //如果low_rec和up_rec相差1則結束循環，否則繼續

        mid_rec = page_rec_get_next_const(low_rec);//這里并沒有除以2作為mid_rec而是簡單的取下一行，因為rec是單鏈表這樣顯然很容易完成

        ut_pair_min(&cur_matched_fields, &cur_matched_bytes,
                low_matched_fields, low_matched_bytes,
                up_matched_fields, up_matched_bytes);

        offsets = rec_get_offsets(
            mid_rec, index, offsets_,
            dtuple_get_n_fields_cmp(tuple), &heap);//獲得記錄的各個字段的偏移數組

        cmp = cmp_dtuple_rec_with_match_bytes(
            tuple, mid_rec, index, offsets,
            &cur_matched_fields, &cur_matched_bytes);//進行比較 0為相等 1 元組大于記錄 -1記錄大于元組，并且傳出field和bytes

        if (cmp > 0) { //如果元組大于mid_rec記錄
low_rec_match://當然簡單的將mid_rec指針賦予給low_rec即可
            low_rec = mid_rec;
            low_matched_fields = cur_matched_fields;
            low_matched_bytes = cur_matched_bytes;

        } else if (cmp) { //如果元組小于mid_rec記錄
up_rec_match://當然簡單的將mid_rec指針賦予給up_rec即可，這一步可以跳過很多記錄
            up_rec = mid_rec;
            up_matched_fields = cur_matched_fields;
            up_matched_bytes = cur_matched_bytes;
        }

               //下面是相等情況的判斷非常關鍵符合我們規律1算法
               //如果元組等于mid_rec
               else if (mode == PAGE_CUR_G || mode == PAGE_CUR_LE //如果是>(PAGE_CUR_G)和<=(PAGE_CUR_LE)
               ) {
            goto low_rec_match; //執行low_rec_match
        } else //如果是>=(PAGE_CUR_GE)和<(PAGE_CUR_L)
               {
            goto up_rec_match;//執行up_rec_match
        }
    }
        //下面體現我們的規律2算法
        //如果是> PAGE_CUR_G和>= PAGE_CUR_GE 都是取high
        //如果是< PAGE_CUR_L和<= PAGE_CUR_LE 都是取low
        //因為是enum類型直接比較
    if (mode <= PAGE_CUR_GE) {
        page_cur_position(up_rec, block, cursor);
    } else {
        page_cur_position(low_rec, block, cursor);
    }
    *iup_matched_fields = up_matched_fields;
    *iup_matched_bytes   = up_matched_bytes;
    *ilow_matched_fields = low_matched_fields;
    *ilow_matched_bytes = low_matched_bytes;
注意一個slot的own記錄為最多8條如下定義:

/* The maximum and minimum number of records owned by a directory slot. The
number may drop below the minimum in the first and the last slot in the
directory. */
#define PAGE_DIR_SLOT_MAX_N_OWNED   8
#define PAGE_DIR_SLOT_MIN_N_OWNED   4
如果大于了8則進行分裂

if (n_owned == PAGE_DIR_SLOT_MAX_N_OWNED) {
            page_dir_split_slot(
                page, NULL,
                page_dir_find_owner_slot(owner_rec));
        }
下面我們畫一個slot內部定位的圖，我們以如下有序數據為例，假設每一個數字代表一個記錄(rec)

1 2 2 2 3 3 4 4
我們可以看到有大量重復的記錄，但是本算法也可以進行精確的定位，我們約定:

紅色箭頭為最后定位到的值
黃色箭頭為mid rec
黑色箭頭分別表示low rec/high rec
如果是我們要定位到>2,那么我們明顯要定位到2-3同時取high值3，我們用源碼中的代碼推導出整個過程如下：
mid為2顯然已經等于了元組的中的2，如圖
關于innodb中查詢的定位方法

但是查詢模式為PAGE_CUR_G 做low_rec_match操作、并且將mid取向下一條記錄后如圖
關于innodb中查詢的定位方法

mid為2顯然已經等于了元組的中的2，但是查詢模式為PAGE_CUR_G做low_rec_match后、并且將mid取向下一條記錄如圖
關于innodb中查詢的定位方法

mid為2顯然已經等于了元組的中的2，但是查詢模式為PAGE_CUR_G做low_rec_match后、并且將mid取向下一條記錄如圖
關于innodb中查詢的定位方法

mid為3顯然已經大于了元組中的2，做up_rec_match后我們發現記錄定位成功，為low 2-high 3。page_rec_get_next_const(low_rec) == up_rec 循環退出如圖
關于innodb中查詢的定位方法

因為我們的查詢模式是PAGE_CUR_G所以我們執行page_cur_position(up_rec, block, cursor);取high值如圖
關于innodb中查詢的定位方法

如果我們要定位到<3,那么我們明顯要定位到2-3.并且取low值2。我們用源碼中的代碼推導出整個過程如下
mid為2顯然小于元組的中的3，如圖
關于innodb中查詢的定位方法

做low_rec_match操作、并且將mid取向下一條記錄后如圖
關于innodb中查詢的定位方法

mid為2顯然小于元組的中的3，做low_rec_match操作、并且將mid取向下一條記錄后如圖
關于innodb中查詢的定位方法

mid為2顯然小于元組的中的3，做low_rec_match操作、并且將mid取向下一條記錄后如圖
關于innodb中查詢的定位方法

mid為3顯然等于元組的中的3，但是查詢模式為PAGE_CUR_L做up_rec_match后、我們發現記錄定位成功為low 2-high 3.page_rec_get_next_const(low_rec) == up_rec 循環退出如圖
關于innodb中查詢的定位方法

因為我們的查詢模式是PAGE_CUR_L所以我們執行page_cur_position(low_rec, block, cursor);取low值如圖
關于innodb中查詢的定位方法

四、總結
我們slot內部的記錄并不多最多為8條，二分算法slot內部并沒有使用二分而是使用了取下一個記錄的值的指針，非常容易實現因為記錄中本來就包含了下一條記錄的偏移量，并且通過訪問模式兩個規律將重復值過濾掉，最終找到邊界?？傊治鲋蟀l現是一種精確高效的算法。

（編輯：武林網）

上一篇：try restarting transaction參數控制

下一篇：binlog_ignore_db造成的同步復制故障