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

标签: MySQL源码分析 join | 发表时间:2012-12-25 17:24 | 作者:OurMySQL
出处:http://ourmysql.com

   在看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     }

   这里的(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,返回search_depth个表的最优执行计划,并合并到部分执行计划
		递归调用该函数,输入为:当前部分执行计划   剩余表N-depth

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

   说明:

   (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(  ->best_ref +   ->const_tables,
 4754              ->tables -   ->const_tables, sizeof(  _TAB*),
 4755            straight_   ?   _tab_cmp_straight :   _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

相关文章

标签: ,

相关 [mysql 源码 join] 推荐:

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

- - OurMySQL
   在看MySQL优化器代码过程中,这应该是相对较简单/代码较清晰的部分了. MySQL优化器有两个自由度:单表访问方式,多表顺序选择. 前文已经介绍过MySQL单表访问的一些考量(ref/range等),本文将介绍JOIN在顺序选择上的复杂度分析.    当有多个表需要JOIN的时候,MySQL首先会处理两类特殊情况,一个是常数表,一个是由于外连接导致顺序依赖关系.

MySQL 內 JOIN 的應用…

- - Gea-Suan Lin's BLOG
「 Common use cases for the MySQL Join statement」這篇給的範例與把 MySQL 上常用到的幾種 JOIN 提出來分析,包括 index 與 explain. 另外在「 Managing hierarchical data with MySQL」也提到了要怎麼處理階層式資料.

从一个MySQL left join优化的例子加深对查询计划的理解

- - SQL - 编程语言 - ITeye博客
   今天遇到一个left join优化的问题,搞了一下午,中间查了不少资料,对MySQL的查询计划还有查询优化有了更进一步的了解,做一个简单的记录:.    这个sql是用来查询出c表中有h表中无的记录,所以想到了用left join的特性(返回左边全部记录,右表不满足匹配条件的记录对应行返回null)来满足需求,不料这个查询非常慢.

Hive中的join

- - CSDN博客云计算推荐文章
select a.* from a join b on a.id = b.id select a.* from a join b on (a.id = b.id and a.department = b.department). 在使用join写查询的时候有一个原则:应该将条目少的表或者子查询放在join操作符的左边.

mapreduce实例-Join连接 (reduce Side Join)

- - CSDN博客云计算推荐文章
//根据连接类型做不同处理. //设置不同map处理不同输入. 外键作为map输出的key,相同的外键值必然落在一个reduce中,在reduce端根据需要做不同形式的连接. 作者:liuzhoulong 发表于2013-9-5 21:35:16 原文链接. 阅读:83 评论:0 查看评论.

hive join 优化 --小表join大表

- - CSDN博客云计算推荐文章
在小表和大表进行join时,将 小表放在前边,效率会高,hive会将小表进行缓存. 使用mapjoin将小表放入内存,在map端和大表逐一匹配,从而省去reduce. 在0.7版本后,也可以用配置来自动优化. 作者:smile0198 发表于2014-10-25 21:49:25 原文链接. 阅读:62 评论:0 查看评论.

Ubuntu下源码安装MySQL-5.5.25a

- - ITeye博客
                       Ubuntu下源码安装MySQL-5.5.25a.    最近感觉各种事想做,做IT的没有休息的时候. 今天在Linux下本来玩玩Android的源码看下的. 那小的怎看根目录的空间已然不多. 所以想把MySQL卸掉然后装到自己想要装的地方,所以又开始弄起MySQL来了(好像违背了我的初衷啊^_^),在加上我的导师是高数据库的,下学期还要想跟着导师写个小型数据库呢,所以干脆换了今天的目的.

Linux安装mysql——源码安装

- - Linux - 操作系统 - ITeye博客
1.假设已经有mysql-5.5.10.tar.gz以及cmake-2.8.4.tar.gz两个源文件. (1)先安装cmake(mysql5.5以后是通过cmake来编译的). (2)创建mysql的安装目录及数据库存放目录. //安装mysql [root@ rhel5~]#mkdir -p /usr/local/mysql/data.

Hive Join 优化 翻译

- - 数据库 - ITeye博客
翻译自  https://cwiki.apache.org/confluence/display/Hive/LanguageManual+JoinOptimization#LanguageManualJoinOptimization-AutoConversiontoSMBMapJoin. Join Optimization ----Join 调优.

Hive JOIN使用详解

- - 数据库 - ITeye博客
Hive是基于Hadoop平台的,它提供了类似SQL一样的查询语言HQL. 有了Hive,如果使用过SQL语言,并且不理解Hadoop MapReduce运行原理,也就无法通过编程来实现MR,但是你仍然可以很容易地编写出特定查询分析的HQL语句,通过使用类似SQL的语法,将HQL查询语句提交Hive系统执行查询分析,最终Hive会帮你转换成底层Hadoop能够理解的MR Job.