前篇介绍了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_partBreakpoint 2 at 0x6009e1: file sql_select.cc, line 3668.(gdb) cContinuing.(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数组结构图如下：
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中的字段相同 <初始化keyuse对象> 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 departmentON 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,使用前面两个columnINDEX[3]->| |-> ... |-->keyuse[4] |-> }
本篇就介绍到此，后面将根据这些结构，看看MySQL如何如何根据这些结构选择执行计划。
Pingback: database SQL常见的可优化点 | 极客521