1、Mysql Innodb 查询优化实现分析 以下文字由808影视收集提供于影视网 何登成目录1目的22测试准备23单表查询33.1单表range查询33.1.1records_in_range函数分析53.1.2best_access_path函数(单表)63.1.3单表range查询总结83.2单表unique查询93.2.1单表Unique查询总结94多表查询104.1多表简单join104.2best_access_path函数分析124.2.1总流程分析124.2.2代价估计分析124.2.3best_access_path函数流程134.3optimizer_search_depth
2、参数154.4多表join查询总结155统计信息165.1统计信息收集165.2统计信息更新175.3统计信息收集总结186查询优化总结187参考文献18附录一19附录二20附录三21附录四221 目的分析mysql+innodb如何实现查询优化？实现查询优化，存储引擎需要做哪些方面的配合？2 测试准备mysqlselect version();5.1.49-debug-loginnodb-表定义-+-+-| Table | Create Table+-+-| nkeys | CREATE TABLE nkeys ( c1 int(11) NOT NULL, c2 int(11) DEFAUL
3、T NULL, c3 int(11) DEFAULT NULL, c4 int(11) DEFAULT NULL, c5 int(11) DEFAULT NULL, PRIMARY KEY (c1), UNIQUE KEY c2 (c2), UNIQUE KEY c3 (c3), UNIQUE KEY c4 (c4), KEY nkey1 (c3,c5) ENGINE=InnoDB DEFAULT CHARSET=gbk |+-+-数据-insert into nkeys values (1,1,1,1,1);insert into nkeys values (2,2,2,2,2);inser
4、t into nkeys values (3,3,3,3,3);insert into nkeys values (4,4,4,4,4);insert into nkeys values (5,5,5,5,5);3 单表查询3.1 单表range查询1) select * from nkeys where c3 3;不能进行索引覆盖扫描index range scan2) select c3 from nkeys where c3 3; 可以进行索引覆盖扫描index only range scan调用流程：msyql_select - JOIN:optimize - make_join_st
5、atistics -0. sql_select.cc:get_quick_record_count -opt_range.cc:SQL_SELECT:test_quick_select ha_innobase:scan_time -get_key_scans_params -check_quick_selectOpt_range.cc:check_quick_keys -ha_innobase:records_in_range- get_index_only_read_time - ha_innobase:read_time -get_best_ror_intersect -get_best_
6、covering_ror_intersect -a) ha_innobase:scan_time函数，给出全表扫描read_timei. scan_time = (double) records / TIME_FOR_COMPARE + 1; 1. mysql层面，返回一个record需要的时间(CPU时间)2. TIME_FOR_COMPARE = 5ii. return (double) (prebuilt-table-stat_clustered_index_size(聚簇索引叶页面数);1. innodb层面，全表扫描时间，用读取的page数计算(IO时间)2. 由于innodb是索引
7、组织表，用不到page的预读，因此一次读取一个pageiii. table_read_time = ha_innobase:scan_time() + scan_time + 1;1. 全表扫描总时间 = innodb读取数据块时间 + mysql比较记录时间 + 12. 测试中：table_read_time = 4.3000000000000007b) check_quick_select函数，判断索引扫描的代价c) ha_innobase:records_in_range函数，判断给定range的索引扫描，将返回多少记录i. 给定range的min_key，max_key，根据min_k
8、ey，max_key构造查询条件，分别进行btr_cur_search_to_nth_levelii. 传入的level是0，search到叶页面iii. 根据返回的两个页面的关系，计算range中的数据量iv. 详细的records_in_range函数实现，请见3.1.1章节。d) get_index_only_read_time函数，当前scan为index only scan，调用此函数计算read_timei. cpu_cost = (double) found_records / TIME_FOR_COMPARE;1. range中的记录数，除以比较时间(CPU时间)ii. get
9、_index_only_read_time，mysql上层提供函数，用于计算index only scan的代价1. keys_per_block = (table-file-stats.block_size/2)(a) / (table-key_infokeynr.key_length + table-file-ref_length + 1)(b)a) (a) 估计索引页面的利用率为1/2b) (b) 索引中，每个索引占用的空间；keynr为索引的编号，哪个索引？c) 测试中：keys_per_block = 9112. io_time = (double) (records + keys_
10、per_block - 1) / keys_per_block;a) 需要进行多少次index叶页面的IO (index only scan，不需要回表)b) 测试中：io_time = 1.0021953896816684 (records = 3)3. index_only_read_time = cpu_cost + io_time + 0.01 = 1.6121953896816683a) index_only_read_time table_read_timeb) 测试中：index only scan要好于table scan，针对第二条语句c) 对于语句(2)，mysql选择索引
11、覆盖扫描i. 索引c1，而非nkey1，虽然nkey1索引也可以做覆盖性扫描，但是nkey1的key_length要大于c1，导致io_time略微大于c1。e) ha_innobase:read_time函数，非index only scan时，调用此函数计算read_timei. cpu_cost = (double) found_records / TIME_FOR_COMPARE; 1. range中的记录数，除以比较时间(CPU时间)ii. ha_innobase:read_time Innodb层面读取的页面，IO时间1. 聚簇索引a) rows a) 针对join查询b)2. c
12、hoose_plan -a) 执行计划选择主函数，读取分析用户定义属性3. greedy_search -a) 从join_tables中逐个选取最优的表，加入当前已选择的pplancode procedure greedy_search input: remaining_tables output: pplan; pplan = ; do (t, a) = best_extension(pplan, remaining_tables); pplan = concat(pplan, (t, a); remaining_tables = remaining_tables - t; while (
13、remaining_tables != ) return pplan;4. best_extension_by_limited_search -a) 从join_tables的remain_tables中选择一个table加入pplan，目标使得整体pplan的开销最小5. best_access_path -a) 若为单表，计算单表的全表扫描代价。b) 若为多表，计算当前选择表的扫描代价。6. make_join_readinfo - pick_table_access_method - tab-index = find_shortest_key(table, & table-coverin
14、g_keys) - tab-read_first_record = join_read_first - tab-type = JT_NEXT -a) 索引覆盖扫描路径优化。若当前为全表扫描，同时存在一个或多个可以进行索引覆盖扫描的查询，那么优先选择索引覆盖扫描。i. 原理：针对Innodb引擎，索引覆盖扫描一定要优于全表扫描ii.b) 对于单表扫描，步骤0确定是否可以选择索引。步骤5返回全表扫描开销。步骤6主要处理index coverage scan的部分优化。c) 在函数find_shortest_key中，选择合适的索引，for index coverage scan。i. 索引必须包含
15、scan键值？ii. 索引列的key_length最小？iii.7.3.1.1 records_in_range函数分析records_in_range -btr_estimage_n_rows_in_range -tuple1 = min value in range scan，range scan的范围起始值btr_cur_search_to_nth_level(index, tuple1, &cursor) -tuple2 = max value in range scan，range scan的范围终止值btr_cur_search_to_nth_level(index, tuple2
16、, &cursor) -根据起始值与终止值，做两次search path，确定index path，存储在cursor中我们有了起始值与终止值的两个path，起始值与终止值所对应的索引叶节点如何根据两个叶节点计算叶节点范围内的数据量(records in range)，想法如下：1. 计算出两个叶节点间，包含多少个索引页，记为n (n leaf pages in range)2. 计算索引页平均包含多少个索引项，记为r (records per leaf page)3. 那么，records in range = n * rInnodb采用相同的计算方法，innodb计算n，r的算法如下:计算
17、n，采用自顶向下的方式计算。(1) 根页面只有一个，可以计算出根页面内，两个range间相差多少索引项n1(2) 第二层页面的n2 = n1 * r2(第二层页面平均记录数)(3) 索引叶节点一层，nn = records in range = nn-1 * rn(叶节点评价记录数)计算r，采用水平采样的方式计算。r的算法相对简单，但是却会产生IO，其核心思想是，对于索引的每一层，从tuple1确定的路径页面开始，沿着页面中的水平链表，向后遍历页面，遍历结束的条件是：1) 遇到了tuple2确定的页面; 2) 或者读取了N_PAGES_READ_LIMIT个页面(10个)。假设读取了N_PAG
18、ES_READ_LIMIT个页面，一共有M个索引记录，那么 r = M / N_PAGES_READ_LIMIT.records_in_range函数总结分析：l 总的来说，records_in_range函数是一个较为费时的函数，两次search path开销，索引层数次的计算索引每一层的records in range开销。如果表数据量较大，索引层数较多，同时查询的range也较大，那么records_in_range函数会产生多次IO，甚至是物理IO，这个是难以接受的。当然，如果查询的range较小，两次search path得到相同的路径，那么records in range pere
19、very level的开销可以忽略不计。l 解决records_in_range函数开销的办法之一，就是在Innodb内部收集更为详尽的统计信息，包括unique key counts，以及histogram(柱状图)。通过统计信息的计算来近似估计records_in_range，从而避免两次search path以及records in range per every level的开销。3.1.2 best_access_path函数(单表)在前面，我们分析到，best_access_path函数针对单表，仅仅计算全表扫描的开销。其实这个说法不是完全正确。在部分情况下，best_access
20、_path函数针对单表range查询，也会计算索引开销。也就是说函数中，s-keyuse != NULL。那么s-keyuse参数是何时设置的呢？通过跟踪两个不同的查询，可以找出设置规律。sql 1：select c3 from nkeys where c3 ID) AND (UserId = 129329421) AND (DeleteState = 0) ORDER BY ID DESC LIMIT 100;通过测试发现，执行sql 1时，s-keyuse = NULL；而执行sql2时，s-keyuse != NULL。s-keyuse设置流程：sql_select.cc:make_jo
21、in_statistics -update_ref_and_keys -sql_select.cc:add_key_fields -重点在于函数sql_select.cc:add_key_fields：此函数会被递归调用，遍历当前sql中的所有查询条件，为每一个查询条件，寻找合适的索引。简单来说，也就是设置每个表的s-keyuse，在best_access_path函数中可以估算这些索引的代价。那么哪些查询条件，才会使用索引呢？sql 1的查询条件是 = =结果是sql 2的s-keyuse被设置。就我测试跟踪的代码看来，若是等值条件，则设置s-keyuse，否则不设置。代码如下：针对sql
22、1与sql 2的第一个查询条件(2601629 ID)，函数add_key_fields判断如下：caseItem_func:OPTIMIZE_OP: boolequal_func=(cond_func-functype() = Item_func:EQ_FUNC |cond_func-functype() = Item_func:EQUAL_FUNC);add_key_equal_fields(,equal_func,);add_key_field(, equal_func, );if (!eq_func)return;cond_func-functype() = LE_FUNC(GT_FU
23、NC)，因此equal_func = false，导致add_key_field直接返回，因此s-keyuse不设置针对sql 2的第二个查询条件(UserId = 129329421)，函数add_key_fields判断如下：caseItem_func:OPTIMIZE_EQUAL:add_key_field(,TRUE,);/ 此处增加possible_keys/ 根据field-table-keys_in_use_for_query，与当前表上的index做一次比较，/ 就得出possible_keys = 6 = 21 + 22， 1号与2号索引可以用，分别是/ IDX_UID_PH
24、OTOID，IDX_UID_ID。都是以UserId字段打头的索引。possible_keys.intersect(field-table-keys_in_use_for_query);stat0.keys.merge(possible_keys);if (!eq_func)return;(*key_fields)-field=field;(*key_fields)-eq_func=eq_func;(*key_fields)-val=*value;(*key_fields)-level=and_level; equal_func直接设置为TRUE，因此UserId对应的索引将会被添加到s-ke
25、yuse中。为什么单表range查询，在range query optimization之后，还需要调用best_access_path函数进行二次执行计划的选择？我的理解是，这是针对等值查询条件的一种二次优化。mysql range query optimization更倾向于选择聚簇索引扫描(二级索引回表代价过大)，而对于等值查询，我们可以在best_access_path函数中再次计算使用二级索引的代价。若此时计算的代价小于range query optimization选择的执行计划，则替换新的执行计划。mysql range query optimization选择的执行计划，如果不
26、是全表扫描，那么一定要优于全表扫描的代价。3.1.3 单表range查询总结 每一条执行路径，其cost = CPU cost + IO cost 单表range scan的执行计划选择，记住几个关键数据的计算即可n table read time，以上步骤0)下面的a)步骤n index only read time，以上步骤0)下面的d)步骤n index read time，以上步骤0)下面的e)步骤 为了计算以上关键数据，innodb存储引擎提供了ha_innobase:records_in_keys方法，该方法根据scan的min_key，max_key进行两次索引上的search
27、path(一直读取到叶页面)，可能产生IO，然后根据两个叶页面，进行records_in_range的预估。 根据where查询条件，mysql首先会选择哪些索引可能适合做查询，这些潜在的索引，就是explain中的possible_keys一列中所列出来的索引。而possible_keys的选择，就是由where条件中涉及到的列打头的所有索引。附录一证实了这个估计。 由于mysql会对每一个possible_keys调用records_in_range进行预估，同时该函数需要两次search path，多次索引页面水平扫描，可能产生两次或以上的IO，因此我的建议是，同一个键值打头的索引，越少
28、越好，在mysql中 explain不会真正执行scan，而是只会执行上面的流程，然后将预估出来的各值返回给用户 mysql的查询优化，用的是CBO，而非RBO。 mysql的查询优化，对于unique scan，会特殊处理，不会这么复杂的路径，因此unique scan的查询优化效率很高。 根据索引覆盖扫描与全表扫描的理论代价可得，索引覆盖扫描一定要优于全表扫描。innodb的全表扫描也就是聚簇索引的覆盖扫描，由于聚簇索引包含记录的所有属性，因此其单行记录的长度一定大于二级索引，n 二级索引的页面数一定小于聚簇索引页面数二级索引的代价一定小于聚簇索引若有索引覆盖扫描，哪怕覆盖扫描的估算代价大
29、于全表扫描，最终还是会补偿选择索引覆盖扫描，在以上测试的第6步骤可得。n 附录二证实了此分析。3.2 单表unique查询select * from nkeys where c3 = 3;调用流程：mysql_execute_command - handle_select - mysql_select - JOIN_optimize - make_join_statistics -if (table-key_infokey.flags & (HA_NOSAME | HA_END_SPACE_KEY) = HA_NOSAME) -1. 若当前索引为unique索引，同时if (const_ref
30、 = eq_part) -2. 指定的等值条件与当前索引的unique key一致s-type = JT_CONST -3. 当前表上的查询，返回的数据量是一个常量join_read_const_table - -row0sel.c:row_search_for_mysql -4. 调用底层函数，做一次unique scan，主要功能是保证explain的正确性。有这个必要吗？看下面的explain截图，就可以发现此函数的功能：if (s-type = JT_SYSTEM | s-type = JT_CONST) -s-found_records = s-records = s-read_ti
31、me = 1; s-worst_seeks = 1.0;5. JT_CONST情况下，查询一定只返回1条数据，不需要调用ha_innobase:records_in_range函数进行判断。if (join-const_tables != join_tables)choose_plan();6. 若当前不全是TL_CONST查询，还需要调用choose_plan函数，判断非const表的最优执行路径。单表情况下，只需要计算全表扫描代价；多表join条件下，需要计算各非const表的join顺序以及单表的最优路径。TL_CONST情况下，不需要调用choose_plan(单表查询情况下)。3.2
32、.1 单表Unique查询总结1. mysql查询优化，对于unique查询做了路径优化，并不需要调用底层提供的records_in_range函数判断查询的代价；同时也不需要调用choose_plan函数，确定此查询全表扫描代价(单表情况下)。2. 只要指定了unique key上的等值查询，那么无论后面还有多少其他查询条件，mysql查询优化一定会选择unique key索引，做unique查询，如下：查询优化仍旧选择c3 unique索引，而非选择nkey1索引，虽然nkey1上有c3，c5两列。3.4 多表查询4.1 多表简单joinselect * from nkeys, aaa w
33、here nkeys.c3 = aaa.a3 and aaa.a2 = 2;具体nkeys，aaa表的表定义，在附录一：aaa表；附录四：nkeys表中给出。调用主流程：1. mysql_select -JOIN:optimize - make_join_statistics -SQL_SELECT:test_quick_select -get_key_scans_params -根据查询条件，aaa表指定了查询条件：aaa.a2 = 2，对于指定查询条件的表，可以通过第3章节单表查询的流程找到针对查询条件的最优路径。当然，若aaa.a2列为unique列，那么就通过第3章节单表unique查
34、询来判断。2. if (join-const_tables != join_tables) -此处判断join查询中，指定了unique key查询条件的表的数量，与join中表的数量是否一致？所有指定了unique key查询条件的表，执行计划已经确定，必定是走unique key索引，因此不需要进行查询优化，代价评估。此处不一致，因此需要调用下面的choose_plan函数，确定整个join操作的最优路径。整个join操作的最优路径，包含两层含义：(一)join操作，涉及到的表的join顺序是最优的；(二) 每张表的执行路径同样也是最优的；最终的目标，是保证选择出整个join代价最小的路径
35、。3. choose_plan -4.1 optimize_straight_join - best_access_path - returnstraight_join，join顺序确定，只需要确定每个table的最优路径。如果是straight_join，也就是说不对查询给定的table顺序进行调整，而仅仅是根据table的顺序，为每一个table找到最优的执行路径，选择4.1的代码路径。此路径相对简单，顺序遍历join结构中的每一张表，找到表的best_access_path，估算代价。一般情况下，不会选择此方案。4.2 greedy_search -greedy_search函数的功能，
36、是用贪心法找到局部最优的join执行计划，与optimize_straight_join函数不同，greedy_search函数会改变表的join顺序。关于greedy_search函数的详细说明，可见sql_select.cc:greedy_search函数功能说明。简单来说，给定剩余join表集合，每次调用best_extension_by_limited_search函数，从剩余表集合中选择一个代价最小的表，加入到当前执行计划中来，直到剩余join表集合耗尽为止。给定N张表的join，需要经过O(N!)次(N的阶层，card(5) = 120)的计算，才能找到最优的执行计划，cpu开销较
37、大。Mysql的优化措施为，设置search_depth，控制最优路径的查找限制，search_depth参数在下面提到的best_extension_by_limited_search函数中使用。若N = search_depth，则一定能找到最优计划；否则只能找到局部最优计划greedy_search函数的伪代码如下：code procedure greedy_search input: remaining_tables output: pplan; pplan = ;/ 当前已经选择的表的最优执行计划 do (t, a) = best_extension(pplan, remaining
38、_tables); pplan = concat(pplan, (t, a); remaining_tables = remaining_tables - t; while (remaining_tables != ) return pplan; 5. best_extension_by_limited_search -greedy_search函数传入的search_depth参数，在best_extension_by_limited_search函数中使用。best_extension_by_limited_search函数是一个深度优先的递归调用。调用的深度即为search_depth。
39、若search_depth=N(number of remaining tables)，则能够完成所有路径的遍历，找到对于remaining tables的一个最优执行计划。返回greedy_search的QEP，已经是针对于remaining tables则最优执行计划，greedy_search函数直接将此计划返回即可。若search_depth N，那么best_extension_by_limited_search函数不能在remaining tables中找到最优的执行计划，而只能找到一个局部最优的计划。此时，函数返回greedy_search，greedy_search会提取出当前
40、局部最优计划的第一张表，作为下一个已经确定的join表。于此同时，greedy_search函数会将选中的table从remaining tables中删除，然后再次调用best_extension_by_limited_search函数，直到N(number of remaining tables) = search_depth，余下的所有table，一次best_extension_by_limited_search函数调用，就能够找到最优的执行计划。极端情况下，search_depth = 1，则best_extension_by_limited_search函数退化为宽度优先的策略，每
41、次从remaining tables中提取能够与已经选出的最后一个table做join，并且扫描代价最小的table，然后立即返回greedy_search函数，greedy_search函数提取此表作为当前partial QEP的最后一张表。best_extension_by_limited_search函数的伪代码实现，可参见附录三。根据以上的分析，可以总结出greedy_search+best_extension_by_limited_search两个函数的复杂度。若N search_depth，则复杂度为O(N*Nsearch_depth/search_depth)，greedy_se
42、arch不能找到join的最优执行路径。6. best_access_path -对于指定的表s，找到其最优的执行路径。可选的路径，必须是join查询中，可以完成nestloop join的路径，对于4.1章节给定的查询，aaa表，可选的路径有两条：aaa.a2索引(针对于aaa.a2 = 2)；aaa.a3索引(针对于aaa.a3 = nkeys.c3条件)。Best_access_path函数，其对每条路径的代价算法较为复杂，目前暂时不准备详尽分析其过程。4.2 best_access_path函数分析同样是使用4.1章节中的测试语句：select * from nkeys, aaa where nkeys.c3 = aaa.a3 and aaa.a2 = 2;4.2.1 总流程分析根据4.1章节的分析，join涉及到两张表，同时search_depth参数设置为62. N best_access_path(table
