关于innodb中查询的定位方法

发布时间:2020-08-10 22:31:02 作者:gaopengtttt
来源:ITPUB博客 阅读:226

原创转载请注明出处

源码版本 5.7.14

涉及源码文件

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的数据字典类容、实际的数据、记录所在块的信息等,下面我具体谈一下定位方法,同时结合源码来看它具体的实现。

我们先来明确一下概念:

  1. 记录(rec):通常为存储在内存中物理记录的完全拷贝,通常用一个unsigned char* 指针指向整个记录
  2. 元组(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,
}; 
  1. PAGE_CUR_G(>)
  2. PAGE_CUR_GE(>=)
  3. PAGE_CUR_L(<)
  4. 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(PAGE_CUR_LE)和>3(PAGE_CUR_G),那么自然我们需要将位置定位到3到4之间我们且用3-4表示

那么我们将这里的区间两个值记为low-high

规律2:

仔细分析后我们发现另外一个规律

为什么讲这个东西,因为这两个规律在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但是

 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 

我们可以看到有大量重复的记录,但是本算法也可以进行精确的定位,我们约定:

如果是我们要定位到>2,那么我们明显要定位到2-3同时取high值3,我们用源码中的代码推导出整个过程如下:

  1. mid为2显然已经等于了元组的中的2,如图


    关于innodb中查询的定位方法

  2. 但是查询模式为PAGE_CUR_G 做low_rec_match操作、并且将mid取向下一条记录后如图


    关于innodb中查询的定位方法

  3. mid为2显然已经等于了元组的中的2,但是查询模式为PAGE_CUR_G做low_rec_match后、并且将mid取向下一条记录如图


    关于innodb中查询的定位方法

  4. mid为2显然已经等于了元组的中的2,但是查询模式为PAGE_CUR_G做low_rec_match后、并且将mid取向下一条记录如图


    关于innodb中查询的定位方法

  5. mid为3显然已经大于了元组中的2,做up_rec_match后我们发现记录定位成功,为low 2-high 3。page_rec_get_next_const(low_rec) == up_rec 循环退出如图


    关于innodb中查询的定位方法

  6. 因为我们的查询模式是PAGE_CUR_G所以我们执行page_cur_position(up_rec, block, cursor);取high值如图


    关于innodb中查询的定位方法

如果我们要定位到<3,那么我们明显要定位到2-3.并且取low值2。我们用源码中的代码推导出整个过程如下

  1. mid为2显然小于元组的中的3,如图


    关于innodb中查询的定位方法

  2. 做low_rec_match操作、并且将mid取向下一条记录后如图


    关于innodb中查询的定位方法

  3. mid为2显然小于元组的中的3,做low_rec_match操作、并且将mid取向下一条记录后如图


    关于innodb中查询的定位方法

  4. mid为2显然小于元组的中的3,做low_rec_match操作、并且将mid取向下一条记录后如图


    关于innodb中查询的定位方法

  5. mid为3显然等于元组的中的3,但是查询模式为PAGE_CUR_L做up_rec_match后、我们发现记录定位成功为low 2-high 3.page_rec_get_next_const(low_rec) == up_rec 循环退出如图


    关于innodb中查询的定位方法

  6. 因为我们的查询模式是PAGE_CUR_L所以我们执行page_cur_position(low_rec, block, cursor);取low值如图


    关于innodb中查询的定位方法

四、总结

我们slot内部的记录并不多最多为8条,二分算法slot内部并没有使用二分而是使用了取下一个记录的值的指针,非常容易实现因为记录中本来就包含了下一条记录的偏移量,并且通过访问模式两个规律将重复值过滤掉,最终找到边界。总之分析之后发现是一种精确高效的算法。

关于innodb中查询的定位方法
推荐阅读:
  1. InnoDB--------查询IOT B+ Tree的高度
  2. python如何实现numpy和list查询其中某个数的个数及定位方法

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

innodb 关于 定位

上一篇:Oracle同义词

下一篇:设计模式之工厂模式一简单工厂模式

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》