Home > Database > Mysql Tutorial > MySQL源码:JOIN顺序选择的复杂度

MySQL源码:JOIN顺序选择的复杂度

WBOY
Release: 2016-06-07 16:34:26
Original
1218 people have browsed it

在看MySQL优化器代码过程中,这应该是相对较简单/代码较清晰的部分了。MySQL优化器有两个自由度:单表访问方式,多表顺序选择。前文已经介绍过MySQL单表访问的一些考量(ref/range等),本文将介绍JOIN在顺序选择上的复杂度分析。 当有多个表需要JOIN的时候,M

在看MySQL优化器代码过程中,这应该是相对较简单/代码较清晰的部分了。MySQL优化器有两个自由度:单表访问方式,多表顺序选择。前文已经介绍过MySQL单表访问的一些考量(ref/range等),本文将介绍JOIN在顺序选择上的复杂度分析。

当有多个表需要JOIN的时候,MySQL首先会处理两类特殊情况,一个是常数表,一个是由于外连接导致顺序依赖关系。前者总是放在关联的最前面,后者会在遍历的时候考虑。本文将忽略上面两点,从较宏观角度看JOIN顺序选择时候的复杂度。

在设置了参数prune_level(默认设置)后,MySQL使用"极其"贪婪的方式获取顺序。如果未设置,则使用了有限穷举获取"最优"的执行计划。

1. 有限穷举

有限穷举只在参数prune_level关闭时才使用,默认情况prune_level时打开的。所以,MySQL一般不这么做。如果只想了解prune_level打开的时候,直接跳过本节,参考贪婪的MySQL。

在关闭参数prune_level后,MySQL基本上就是穷举了,说"有限"是指,当关联表的数量超过63时(search_depth的默认值),达到最大深度, MySQL将分多个阶段穷举。当关联表的数量较少的时候(小于search_depth),MySQL会穷举所有可能,然后计算每个JOIN顺序的成本,选择成本最低的作为其执行计划。关于这部分的算法复杂度,在代码注释中有较为详细的描述,建议阅读函数greedy_search的注释先。下面是注释部分的两段伪代码,很好的描述了整个过程:

1.1 greedy_search

 4997     procedure greedy_search
 4998     input: remaining_tables
 4999     output: pplan;
 5000     {
 5001       pplan = ;
 5002       do {
 5003         (t, a) = best_extension(pplan, remaining_tables);
 5004         pplan = concat(pplan, (t, a));
 5005         remaining_tables = remaining_tables - t;
 5006       } while (remaining_tables != {})
 5007       return pplan;
 5008     }
Copy after login

这里的(t , a)表示,每次best_extension返回下一个需要JOIN的表t,并且确定的访问方式是a。上面的代码中,执行计划的扩展由函数best_extension,初始pplan为空,do循环结束输出最终的执行计划。

1.2 best_extension

best_extension中调用函数best_extension_by_limited_search完成递归遍历,其输入是部分执行计划(pplan)和它的成本,函数目的是找到下一个关联的表。思路很简单,遍历所有剩余表,对每一个表,计算对应的"局部"最优执行计划,当然计算这个“局部”最优仍然是调用这个函数,所以这是一个深度优先的遍历。

伪代码(是不是又有人说我总贴代码了):

 5171     @code
 5172     procedure best_extension_by_limited_search(
 5173       pplan in,             // in, partial plan of tables-joined-so-far
 5174       pplan_cost,           // in, cost of pplan
 5175       remaining_tables,     // in, set of tables not referenced in pplan
 5176       best_plan_so_far,     // in/out, best plan found so far
 5177       best_plan_so_far_cost,// in/out, cost of best_plan_so_far
 5178       search_depth)         // in, maximum size of the plans being considered
 5179     {
 5180       for each table T from remaining_tables
 5181       {
 5182         // Calculate the cost of using table T as above
 5183         cost = complex-series-of-calculations;
 5184
 5185         // Add the cost to the cost so far.
 5186         pplan_cost+= cost;
 5187
 5188         if (pplan_cost >= best_plan_so_far_cost)
 5189           // pplan_cost already too great, stop search
 5190           continue;
 5191
 5192         pplan= expand pplan by best_access_method;
 5193         remaining_tables= remaining_tables - table T;
 5194         if (remaining_tables is not an empty set
 5195             and
 5196             search_depth > 1)
 5197         {
 5198           best_extension_by_limited_search(pplan, pplan_cost,
 5199                                            remaining_tables,
 5200                                            best_plan_so_far,
 5201                                            best_plan_so_far_cost,
 5202                                            search_depth - 1);
 5203         }
 5204         else
 5205         {
 5206           best_plan_so_far_cost= pplan_cost;
 5207           best_plan_so_far= pplan;
 5208         }
 5209       }
 5210     }
 5211     @endcode
Copy after login

一个说明:在每次遍历的时候,一旦发现成本大于当前的最优成本,则放弃,不再继续深入。

1.3 简单的小结

函数的输入:
	部分执行计划 partial plan
	N个剩余表
函数输出:
	当 N   search_depth,返回search_depth个表的最优执行计划,并合并到部分执行计划
		递归调用该函数,输入为:当前部分执行计划   剩余表N-depth
Copy after login

1.4 复杂度分析

join-complex

所以,复杂度可能是O(N*N^search_depth/search_depth)。如果search_depth > N 那么算法的复杂度就是O(N!)。通常MySQL优化器分析的复杂度都是O(N!)。

1.5 边界情形

有两个比较极端的情况:

– 当需要JOIN的表的数量小于search_depth时,这里就退化为一个深度优先的穷举确定最优执行计划

– 当search_depth = 1的时候,函数退化为"极其"贪婪的算法,每次从当前的剩余的表中取一个成本最小的,来扩展当前的执行计划

剩余的情况就是介于上面两者之间。

2. 贪婪的MySQL

在打开了参数prune_level(默认开启)后,MySQL不再使用穷举的方式扩展执行计划,而是在剩余表中直接选取访问最少纪录数的表。按照MySQL手册上的描述是:根据经验来看,这种”educated guess”基本不会漏掉最优的执行计划,但是却可以大大(dramatically )缩小搜索空间。要是你怀疑漏掉了某个最优的执行计划,你可以考虑关闭参数试试,当然这会导致搜索空间增大,优化器执行时间偏长。

这个参数在深度优先搜索中起作用,在进行深度探索时,根据current_record_count和current_read_time,来确定,这是不是一个好的执行计划。(原本是需要递归调用计算成本确定)

下面是一个简单的伪代码描述:

场景:
pplan 			当前部分执行计划(初始为空) short for partial plan
N remaining table 	当前剩余表(初始化时,为除了常数表之外的所有表)
	这N表记为T[0] T[1] ... T[N-1]
计算代码:
Function best_extension(pplan,N)
Foreach T in T[0...N-1]
    let P(pplan,T) := add T to pplan
    let current_record_count := #row of P(pplan,T)
    let current_read_time := #read time of P(pplan,T)
    if [
         T is Not The First Table in T[0...N-1] AND
         current_record_count >= best_record_count AND
         current_read_time >= best_read_time
       ]
        "P(pplan,T) is a bad plan! SKIP it!!!!!!!"
    END
    let best_record_count := min(best_record_count, current_record_count )
    let best_read_time := min(best_read_time,current_read_time)
    best_extension(P(pplan,T),N-1);
END
Copy after login

说明:

(1) 伪代码中未考虑依赖关系。第一个表的COST总是会计算出来。

(2) 面对pplan和T[0...N-1]时,只计算pplan与T[0],T[1]…T[N-1]的关联后各自的current_record_count,并以此为依据选择,pplan应该跟哪一个表JOIN。除了第一个表(搜索树的最左边的那各分支)会递推计算其代价,其他所有分支都只是蜻蜓点水般只计算一级,而不会深度递归计算。

(3) 这看起来这是一个非常激进的优化方式。

3. 开始前的排序

 4753   my_qsort(join->best_ref + join->const_tables,
 4754            join->tables - join->const_tables, sizeof(JOIN_TAB*),
 4755            straight_join ? join_tab_cmp_straight : join_tab_cmp);
Copy after login

MySQL在开始确定JOIN顺序之前会根据每个表可能访问的纪录数,进行一次排序。这一步看似多余,但是当穷举搜索时,可以大大的减少执行计划需要探测的深度。

当评估某个执行计划的时候,如果某一步发现当前的cost已经大于最优的执行计划时,则立即退出评估。这意味着,如果最先找到最优的执行计划,那么需要做的评估将会少很多。如果某个表需要扫描的行数越少,那么可以初步认为越先使用越好。当然,因为这里的排序评估是没有使用JOIN条件的,所以,看起来需要扫描很多的,也可能加上JOIN以后只需要扫描很少的记录。

4. 函数调用栈

#0            best_access_path

#1          best_extension_by_limited_search

#2        greedy_search

#3      choose_plan

#4    make_join_statistics

#5  JOIN::optimize

source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template