關(guān)于innodb中查詢的定位方法

原創(chuàng)轉(zhuǎn)載請(qǐng)注明出處

源碼版本 5.7.14

涉及源碼文件

page0cur.cc
page0page.h
page0page.cc
rem0cmp.cc 

為什么談及定位方法，因?yàn)樵趇nnodb中，比如一個(gè)插入語(yǔ)句我們需要定位在哪里插入(PAGE_CUR_LE)，比如一個(gè)查詢語(yǔ)句我們需要定位到其第一個(gè)需要讀取數(shù)據(jù)的位置，因此定位方法是查詢的根本。而找到這個(gè)記錄位置后實(shí)際上是用一個(gè)叫做page_cur_t結(jié)構(gòu)體進(jìn)行存儲(chǔ)，暫且叫他cursor游標(biāo)

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的數(shù)據(jù)字典類容、實(shí)際的數(shù)據(jù)、記錄所在塊的信息等，下面我具體談一下定位方法，同時(shí)結(jié)合源碼來(lái)看它具體的實(shí)現(xiàn)。

我們先來(lái)明確一下概念：

1. 記錄(rec)：通常為存儲(chǔ)在內(nèi)存中物理記錄的完全拷貝，通常用一個(gè)unsigned char* 指針指向整個(gè)記錄
2. 元組(dtuple)：物理記錄的邏輯體現(xiàn)，他就復(fù)雜得多，但是一個(gè)記錄(rec)對(duì)應(yīng)一個(gè)元組(dtuple),由dtuple_t結(jié)構(gòu)體表示，其中每一個(gè)field由一個(gè)dfield_t結(jié)構(gòu)體表示，數(shù)據(jù)存儲(chǔ)在dfied_t的一個(gè)叫做void* data的指針中

可自行參考運(yùn)維內(nèi)參等其他書(shū)籍，這里就在簡(jiǎn)單描述到這里，本文會(huì)出現(xiàn)相關(guān)術(shù)語(yǔ)。

一、查詢模式(search mode)

在innodb中的常用的search mode有如下幾個(gè)

/* 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,
}; 

1. PAGE_CUR_G(>)
2. PAGE_CUR_GE(>=)
3. PAGE_CUR_L(<)
4. PAGE_CUR_LE(<=)

我們來(lái)討論一個(gè)問(wèn)題考慮如下有序的數(shù)組

1,2,3,3,4,5,6,7 

規(guī)律1:

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

• 如果是>=3那么我們需要將記錄定位到3及[3(第一個(gè)),正無(wú)窮)
• 如果是<3那么我們需要將記錄定位到2及（負(fù)無(wú)窮,2]
  也就是說(shuō)>=3和<3定位的區(qū)間是相同的2-3

如果我們查詢<=3(PAGE_CUR_LE)和>3(PAGE_CUR_G),那么自然我們需要將位置定位到3到4之間我們且用3-4表示

• 如果是<=3那么我們需要將記錄定位到3及(負(fù)無(wú)窮,3(最后一個(gè))]
• 如果是>3那么我們需要將記錄定位到4及[4,正無(wú)窮)
  也就是說(shuō)<=3和>3定位的區(qū)間是相同的3-4

那么我們將這里的區(qū)間兩個(gè)值記為low-high

規(guī)律2:

仔細(xì)分析后我們發(fā)現(xiàn)另外一個(gè)規(guī)律

• (>) PAGE_CUR_G和(>=) PAGE_CUR_GE 都是取high
• (< )PAGE_CUR_L和(<=) PAGE_CUR_LE 都是取low

為什么講這個(gè)東西，因?yàn)檫@兩個(gè)規(guī)律在innodb記錄定位中起到了關(guān)鍵作用，也直接影響到了innodb記錄查找的二分算法的實(shí)現(xiàn)方式。

二、matched_fields和matched_bytes

大家在源碼中能看到matched_fields和matched_bytes兩個(gè)值，那么他們代表什么意思呢？
以int類型為例，因?yàn)樵诤瘮?shù)cmp_dtuple_rec_with_match_bytes是逐個(gè)字段逐個(gè)字節(jié)進(jìn)行比較的，關(guān)鍵代碼如下

while (cur_field < n_cmp) {
rec_byte = *rec_b_ptr++;
dtuple_byte = *dtuple_b_ptr++;} 

比如int 2,int 3在innodb中內(nèi)部表示為0X80000002和0X80000003,如果他們進(jìn)行比較那么最終此field的比較為不相等(-1),那么matched_fields=0但是

• 0X 800000 02
• 0X 800000 03
  我們能夠發(fā)現(xiàn)其中有3個(gè)字節(jié)是相同的及0X80 0X00 0X00 所以matched_bytes=3
  簡(jiǎn)單的說(shuō)matched_fields為相同field數(shù)量,如果field不相同則會(huì)返回相同的字節(jié)數(shù)。
  當(dāng)然cmp_dtuple_rec_with_match_bytes對(duì)不同數(shù)據(jù)類型的比較方式也不相同如下:

 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;
        } 

具體可以參考一下源碼，這里不再過(guò)多解釋

三、塊內(nèi)二分查詢方法再析

為什么叫做再析，因?yàn)槿邕\(yùn)維內(nèi)參已經(jīng)對(duì)本函數(shù)進(jìn)行了分析，這里主要分析查詢模式對(duì)二分法實(shí)現(xiàn)的影響，并且用圖進(jìn)行說(shuō)明你會(huì)有新的感悟！當(dāng)然如果你對(duì)什么slot還不清楚請(qǐng)自行參考運(yùn)維內(nèi)參

簡(jiǎn)單的說(shuō)page_cur_search_with_match_bytes會(huì)調(diào)用cmp_dtuple_rec_with_match_bytes函數(shù)進(jìn)行元組和記錄之間的比較，而塊內(nèi)部比較方法就是先對(duì)所有的slot進(jìn)行二分查找確定到某個(gè)slot以快速縮小范圍，然后在對(duì)slot內(nèi)部使用類似二分查找的方法等到記錄，我們主要來(lái)分析一下slot內(nèi)部的類二分法，因?yàn)樗耆俏覀儾樵兡Ｊ街袃蓚€(gè)規(guī)律的完美體現(xiàn)，如下簡(jiǎn)化的代碼片段以及我寫(xiě)的注釋：

/* 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則結(jié)束循環(huán)，否則繼續(xù)

        mid_rec = page_rec_get_next_const(low_rec);//這里并沒(méi)有除以2作為mid_rec而是簡(jiǎn)單的取下一行，因?yàn)閞ec是單鏈表這樣顯然很容易完成

        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);//獲得記錄的各個(gè)字段的偏移數(shù)組

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

        if (cmp > 0) { //如果元組大于mid_rec記錄
low_rec_match://當(dāng)然簡(jiǎn)單的將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://當(dāng)然簡(jiǎn)單的將mid_rec指針賦予給up_rec即可，這一步可以跳過(guò)很多記錄
            up_rec = mid_rec;
            up_matched_fields = cur_matched_fields;
            up_matched_bytes = cur_matched_bytes;
        } 

               //下面是相等情況的判斷非常關(guān)鍵符合我們規(guī)律1算法
               //如果元組等于mid_rec
               else if (mode == PAGE_CUR_G || mode == PAGE_CUR_LE //如果是>(PAGE_CUR_G)和<=(PAGE_CUR_LE)
               ) {
            goto low_rec_match; //執(zhí)行l(wèi)ow_rec_match
        } else //如果是>=(PAGE_CUR_GE)和<(PAGE_CUR_L)
               {
            goto up_rec_match;//執(zhí)行up_rec_match
        }
    }
        //下面體現(xiàn)我們的規(guī)律2算法
        //如果是> PAGE_CUR_G和>= PAGE_CUR_GE 都是取high
        //如果是< PAGE_CUR_L和<= PAGE_CUR_LE 都是取low
        //因?yàn)槭莈num類型直接比較
    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; 

注意一個(gè)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則進(jìn)行分裂

 if (n_owned == PAGE_DIR_SLOT_MAX_N_OWNED) {
            page_dir_split_slot(
                page, NULL,
                page_dir_find_owner_slot(owner_rec));
        } 

下面我們畫(huà)一個(gè)slot內(nèi)部定位的圖，我們以如下有序數(shù)據(jù)為例，假設(shè)每一個(gè)數(shù)字代表一個(gè)記錄(rec)

1 2 2 2 3 3 4 4 

我們可以看到有大量重復(fù)的記錄，但是本算法也可以進(jìn)行精確的定位，我們約定:

• 紅色箭頭為最后定位到的值
• 黃色箭頭為mid rec
• 黑色箭頭分別表示low rec\high rec

如果是我們要定位到>2,那么我們明顯要定位到2-3同時(shí)取high值3，我們用源碼中的代碼推導(dǎo)出整個(gè)過(guò)程如下：

1. mid為2顯然已經(jīng)等于了元組的中的2，如圖

   
   
   
   
   

2. 但是查詢模式為PAGE_CUR_G 做low_rec_match操作、并且將mid取向下一條記錄后如圖

   
   
   
   
   

3. mid為2顯然已經(jīng)等于了元組的中的2，但是查詢模式為PAGE_CUR_G做low_rec_match后、并且將mid取向下一條記錄如圖

   
   
   
   
   

4. mid為2顯然已經(jīng)等于了元組的中的2，但是查詢模式為PAGE_CUR_G做low_rec_match后、并且將mid取向下一條記錄如圖

   
   
   
   
   

5. mid為3顯然已經(jīng)大于了元組中的2，做up_rec_match后我們發(fā)現(xiàn)記錄定位成功，為low 2-high 3。page_rec_get_next_const(low_rec) == up_rec 循環(huán)退出如圖

   
   
   
   
   

6. 因?yàn)槲覀兊牟樵兡Ｊ绞荘AGE_CUR_G所以我們執(zhí)行page_cur_position(up_rec, block, cursor);取high值如圖

   
   
   
   
   

如果我們要定位到<3,那么我們明顯要定位到2-3.并且取low值2。我們用源碼中的代碼推導(dǎo)出整個(gè)過(guò)程如下

1. mid為2顯然小于元組的中的3，如圖

   
   
   
   
   

2. 做low_rec_match操作、并且將mid取向下一條記錄后如圖

   
   
   
   
   

3. mid為2顯然小于元組的中的3，做low_rec_match操作、并且將mid取向下一條記錄后如圖

   
   
   
   
   

4. mid為2顯然小于元組的中的3，做low_rec_match操作、并且將mid取向下一條記錄后如圖

   
   
   
   
   

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

   
   
   
   
   

6. 因?yàn)槲覀兊牟樵兡Ｊ绞荘AGE_CUR_L所以我們執(zhí)行page_cur_position(low_rec, block, cursor);取low值如圖

   
   
   
   
   

四、總結(jié)

我們slot內(nèi)部的記錄并不多最多為8條，二分算法slot內(nèi)部并沒(méi)有使用二分而是使用了取下一個(gè)記錄的值的指針，非常容易實(shí)現(xiàn)因?yàn)橛涗浿斜緛?lái)就包含了下一條記錄的偏移量，并且通過(guò)訪問(wèn)模式兩個(gè)規(guī)律將重復(fù)值過(guò)濾掉，最終找到邊界?？傊治鲋蟀l(fā)現(xiàn)是一種精確高效的算法。