MySQL源码:索引相关的数据结构(后篇)_MySQL, Oracle及数据库讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  MySQL, Oracle及数据库讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 1874 | 回复: 0   主题: MySQL源码:索引相关的数据结构(后篇)        下一篇 
oraclexie
注册用户
等级:新兵
经验:36
发帖:67
精华:0
注册:2011-8-21
状态:离线
发送短消息息给oraclexie 加好友    发送短消息息给oraclexie 发消息
发表于: IP:您无权察看 2015-1-7 14:52:55 | [全部帖] [楼主帖] 楼主

前篇介绍了MySQL存储索引信息的基本数据结构。本篇将延续下去,介绍MySQL如何找到可以使用的索引,以及期间需要使用的主要数据结构。

   谁适合阅读: 本文不打算从High Level来介绍MySQL索引及其使用,相反是从MySQL源码对应的数据结构开始介绍。如果你了解MySQL索引的基本原理,还打算继续从源码的角度解决一些索引使用的问题,那么你适合参考本文,否则,打住,真的很枯燥:(。在可见的未来,作者还将介绍Range优化相关的数据结构等。

0. 概述

   本文介绍MySQL如何发现WHERE条件中的等值表达式,并通过分析这些等值表达式,找到可以使用的索引。在这个过程中,MySQL将递归的访问所有WHERE条件"谓词",并将等值表达式都存储到KEY_FIELD对象的数组中。

   然后遍历该KEY_FIELD数组,并同时对比所有索引列,找到哪些字段是在索引列中出现,这些字段则可能可以使用索引,MySQL将所有这些字段都存储在对象KEYUSE数组中。

   最后,对KEYUSE进行处理,包括排序、删除无法使用的索引列。这时KEYUSE数组就是所有可以使用REF的索引列了。
1. KEY_FIELD
1.1 概述

   在函数JOIN::optimize/make_join_statistics/update_ref_and_keys中,对所有WHERE条件中的等值表达式,都认为可能会走上索引,所以都暂时存放到KEY_FIELD数组中。例如有表达式:"seller_id = 631389273",那么KEY_FIELD数组中就有对应的对象。结构如下:

(gdb) b add_key_part

Breakpoint 2 at 0x6009e1: file sql_select.cc, line 3668.
(gdb) c
Continuing.
(gdb) p key_field[0]
$44 = {
      field = 0x7f6514011728, # 对应seller_id字段
      val = 0x7f6514005ae0, # 指向值为631389273的Item
      level = 0,
      optimize = 0,
      eq_func = true,
      null_rejecting = false,
      cond_guard = 0x0
}


   MySQL在后面的处理中,会遍历所有的KEY_FIELD,如果发现恰好有对应的索引在这个字段上,就会将该索引标记为可以使用。选择执行计划的时候,就会考虑使用这个索引。
1.2 定义

3065 typedef struct key_field_t {
      3066 Field *field;
      3067 Item *val; ///< May be empty if diff constant
      ......
3077 } KEY_FIELD;


   KEY_FIELD的Field和Item字段分表存储了字段和对应的值。
1.3 KEY_FIELD数组

   假设有更复杂一点的WHERE条件:

WHERE
seller_id =631389273 AND
gmt_modified = \'2012-02-12 09\' and
PARENT_ID=119985497951753 and
AUCTION_ID= 8932244966


   上面每个条件都会生成一个对应的KEY_FIELD对象来存储,对应的KEY_FIELD数组结构图如下:

indexofkeyfield


2. MySQL如何生成KEY_FIELD数组(概述)

   在函数update_ref_and_keys中,先根据WHERE条件生成KEY_FIELD数组,再进一步处理,最后找到所有REF可以使用的索引。
2.1 update_ref_and_keys函数的主流程

(1) 函数通过add_key_fields将所有的可能用到的索引字段,全部都放到key_fields数组中
    (1.1) 遍历WHERE树,递归调用add_key_fields。对每一个Item_func,调用一次add_key_fields
    (1.2) 对每一个Item_func(有两个Item),调用add_key_equal_fields
          (1.2.1) 一般来说Item_func(如col > 10),有两个Item
    (1.3) add_key_equal_fields函数
          (1.3.1)将调用add_key_field
                 该函数将等值比较放到KEY_FIELD数组中
                 不等值,如果可能用上索引,则存放到key_map对象join_tab->const_keys中。
                 详细的:

 {


                 输入:WHERE中的一个子表达式,例如col > 10
                 处理:
                     (1) field->key_start 全都加入possible keys;
                         即所有以col开头的索引,都是可能的索引
                     (2) 如果Field op constant则将,直接放到possible keys?
                 结果:
                     (1) key1 > 10 会直接存放到possible keys然存放存放到join_tab->const_keys
                     (2) key1 = 10 and key2 > 10,会放到possible keys,
                         再存放到join_tab->const_keys。key1会存放到key_field数组中

 }


(2) 调用add_key_part将所有的KEY_FIELD存放到数组KEYUSE
(3) 移除KEYUSE数组中无法使用part,例如之使用了索引的第二个字段; 对KEYUSE排序,
    相同的KEY的字段放一起
    (3.1) 先使用my_sort进行排序:根据table/index/keypart对所有的KEYUSE对象进行排序

 3986     my_qsort(keyuse->buffer,keyuse->elements,sizeof(KEYUSE),
3987           (qsort_cmp) sort_keyuse);


   (这里的(2),(3)步骤,在本篇文章后部分将详细解释)

   这个函数会对所有=比较表达式相关的谓词都放入key_fields当中,然后,MySQL会根据各个索引字段信息生成对应的KEYUSE数组。

WHERE seller_id =631389273 AND   gmt_modified > \'2012-02-12 09\'\\G


   这样的WHERE条件之后,我们看到,key_field里面只存储了一个对象,里面存储的是field是SELLER_ID。
2.2 函数的调用栈

#0 add_key_field
#1 add_key_fields
#2 update_ref_and_keys
#3  make_join_statistics
#4  JOIN::optimize


3. KEY_FIELD数组转化成KEYUSE对象
3.1 KEYUSE对象

   KEY_FIELD数组中包含了所有等值表达式对应字段,但并不是所有这些字段都有对应的索引。KEYUSE对象就是用来存储所有,有索引的KEY_FIELD,并将更多索引信息存储到KEYUSE中,以便后续使用。这个过程分两步:筛选;排序;再筛选。
3.1.0 定义

(gdb) p s->keyuse[4]
$90 = {
      table = 0x7f5bb800e980,
      val = 0x7f5bb8001570, # 存储对应的值,这里是\'2012-02-12 09\'
      used_tables = 0,
      key = 6, # 使用第6个索引
      keypart = 1, # 从零开始,keypart=1表示使用的第二个column
      optimize = 0,
      keypart_map = 2, # 二进制11,使用前面两个column
      ref_table_rows = 18446744073709551615,
      null_rejecting = false,
      cond_guard = 0x0
}


3.1.1 筛选

for ( ; field != end ; field++) #遍历key_field数组@update_ref_and_keys
{
      for (uint key=0 ; key < table->keys ; key++){ #遍历所有索引@add_key_part
            for (uint part=0 ; part < key_parts ; part++) #遍历索引所有字段@add_key_part
            {
                  if field->eq(table->key_info[key].key_part[part].field){
                        #如果索引字段跟key_field中的字段相同
                        insert_dynamic(keyuse_array,(uchar*) &keyuse);
                  }
            }
      }
}


3.1.2 排序

   这一步较简单,MySQL会根据table/index/key part对所有的KEYUSE对象进行排序:

3986     my_qsort(keyuse->buffer,keyuse->elements,sizeof(KEYUSE),
3987           (qsort_cmp) sort_keyuse);


   这里,my_qsort是一个通用快排函数,排序顺序安装函数sort_keyuse给出:tablenr越大,值越大;索引编号越大,值越大;索引列越靠前,值越大。
3.1.3 再筛选

   前面筛选,会将所有在索引中的字段都放到KEYUSE数组中,这里将继续移除以下的KEYUSE对象:

   (1) 某个列虽然是索引列,但是KEYUSE中没有前导列。例如有key(a,b,c)但条件只有b < 5,则移除。

   (2) 如果有等值和等值引用,则移除后面的等值引用,如有key(a,b)和条件a=3 and b=7 and b=t2.d,那么就会移除条件b=t2.d。

   条件(1)很好理解,B-Tree索引不能简单的使用这样的字段做索引。这里解释一下条件(2)。看如下场景:

CREATE TABLE `employee` (
`LastName` varchar(20) DEFAULT NULL,
`DepartmentID` int(11) DEFAULT NULL,


  KEY `从` (`LastName`,`DepartmentID`)

);
CREATE TABLE `department` (
`DepartmentID` int(11) DEFAULT NULL,
`DepartmentName` varchar(20) DEFAULT NULL,
KEY `IND_D` (`DepartmentID`)
)


做如下查询:

SELECT
*
FROM
employee right outer JOIN department
ON
employee.DepartmentID = department.DepartmentID and
employee.DepartmentID=33 and
employee.lastname = \'Zhou\'


   因为right join,所以department顺序总是在前。MySQL在考察employee表可以走哪些索引的时候,先收集到三个KEY_FIELD等值表达式,因为索引IND_L_D包含了这两个字段,所以这三个等值表达式都会存储到KEYUSE数组中。而三个KEYUSE在数组的中的顺序如下:

KEYUSE(lastname,\'Zhou\'),KEYUSE(DepartmentID,33),KEYUSE(DepartmentID,department.DepartmentID)


   这里的第三个等式,是一个引用,但是employee是连接的外部表,所以在扫描employee时,将忽略第三个条件,对应的KEYUSE将删除这个条件。

   更多解释和疑问:(1) KEYUSE排序会将常数放在前面 (2) 一个疑问,ON条件中的employee.lastname = \'Zhou\',放在ON里面和放在WHERE里面有什么区别?
3.2 完整的KEYUSE数组

|-> p s->keyuse[1]
|-->keyuse[0] [KEYUSE] |-> { table = 0x7f5bb800e980,
      INDEX[1]->|-->keyuse[1] ----------> |-> ...
      |-->keyuse[2] |-> key = 1, #使用第一个索引
      |-> keypart = 1, #从零开始,1表示使用的第二个column
      |-->keyuse[3] |-> keypart_map = 2, #二进制11,使用前面两个column
      INDEX[3]->| |-> ...
|-->keyuse[4] |-> }


--转自 北京联动北方科技有限公司




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论