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

2012-12-11  |  16:00分类:MySQL  |  标签:  |  

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

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

在设置了参数prune_level(默认设置)后,MySQL会使用"较为启发式"的方式忽略一些执行计划。如果未设置,则使用了穷举获取"最优"的执行计划。

1. 有限穷举

在MySQL打开参数prune_level(默认打开)时,会通过一个"偷懒"技巧来跳过某些看似消耗较大执行计划,可以参考偷懒的MySQL

虽然会"偷懒"的跳过某些执行计划,但是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 }

这里的(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

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

1.3 简单的小结

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

1.4 复杂度分析

假设需要关联的表一共有N个,搜索深度最大为depth,那么穷举的复杂度为(这是一个粗略的计算):

当 N < depth 时,为:

\[O(N!)\]

当 N >= depth时,为(近似):\[O(\frac{N*N^{depth}}{depth})\]

第一种情况,是简单,就是一个完全的穷举。

第二种情况说明: 每次优化深度是\(depth\),所以,需要进行\(\frac{N}{depth}次优化\);每次的复杂度为:\((N-1)*(N-2)...(N-depth)\);总的复杂度为:\[O(\frac{N}{depth}*N^{depth}) = O(\frac{N*N^{depth}}{depth})\]

所以,复杂度可能是\(O(\frac{N}{depth}*N^{depth}) = O(\frac{N*N^{depth}}{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

说明:

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

(2) 面对pplan和T[0...N-1]时,只计算pplan与T[0],T[1]...T[N-1]的关联后各自的current_record_count/current_read_time,会依此值忽略一些执行计划,只有优于"当前最优"best_record_count/best_read_time的时候,才会递推下去,否则直接忽略当前的执行计划。案例说明:

(**) 当前剩余三个表A、B、C,MySQL先将三个表按照found_records进行排序,假设排序后为B、A、C;

(**) MySQL先尝试把B加入当前执行计划(pplan+B),先计算访问B的最优方式,同时计算出current_record_count/current_read_time,并将其记录为best_record_count/best_read_time(以后再尝试把A、C加入时,如果更优,则更新该值;即该值总是为"当前最优");

(**) pplan+B继续向后扩展;

(**) MySQL再尝试把A加入当前执行计划(pplan+A),先计算访问A的最优方式,如果其current_record_count/current_read_time小于当前最优,则忽略当前执行计划(如果prune_level=1),否则,pplan+A继续向后扩展

(**) MySQL再尝试把C加入当前执行计划(pplan+C)...

(**) 穷举完成

(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);

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
喜欢本文,那就收藏到:

6条评论 关于 “MySQL源码:JOIN顺序选择的复杂度”

  1. crycran 发表于: 十二月 16th, 2012 19:43

    完全看不懂 怎么办。。。。

  2. 藏章博客 发表于: 一月 23rd, 2013 17:39

    好久没来博主博客了,就来看看!~大家 相互访问

  3. 案例:MySQL优化器如何选择索引和JOIN顺序 | Multiprocess 发表于: 十一月 16th, 2013 12:28

    […] 当表的数量较少(少于search_depth,默认是63)的时候,这里直接蜕化为一个穷举搜索,优化器将穷举所有的left-deep树找到最优的执行计划。另外,优化器为了减少因为搜索空间庞大带来巨大的穷举消耗,所以使用了一个”偷懒”的参数prune_level(默认打开),具体如何”偷懒”,可以参考JOIN顺序选择的复杂度。不过至少需要有三个表以上的关联才会有”偷懒”,所以本案例不适用。 […]

  4. 泥浆泵 发表于: 十二月 23rd, 2013 13:35

    好复杂哦,看得好凌乱

  5. 匿名 发表于: 九月 2nd, 2015 15:45

    “如果其current_record_count/current_read_time小于当前最优,则忽略当前执行计划(如果prune_level=1),否则,pplan+A继续向后扩展”

    小于应该是大于吧

  6. tq 发表于: 九月 2nd, 2015 15:47

    真正的best_access_path代价计算部分,只能看个大概。太复杂了。
    甚至代码中还有注释问道为啥有那个条件哈哈。。


发表您的评论