浅析MySQLJoinReorder算法

干就是了

浅析MySQL Join Reorder算法 田镜祺 MySQL代码研究 MySQL代码研究 发布MySQL代码以及核心技术相关的文章。 18篇内容 2024年09月09日 14:07 北京 引言在《浅析MySQL代价估计器》中，对JOIN::estimate_rowcount()进行了浅析。在这个函数中，主要是针对各种单表的Access Path的代价估计算法。当不存在多表Join时，上篇文章所写的内容基本就是完整的代价估计。 但如果存在多表Join，就需要决定多个表进行Join的顺序，不同的Join顺序还可能会影响表的Access Path。生成最终物理执行计划的过程也就是决定各个表Access Path的过程。还是先举个例子，创建两个最简单的表，执行一条两个表的Join语句：CREATETABLEt1(idINTPRIMARYKEY,col1INT,col2INT,KEYindex_col1(col1))ENGINE=INNODB;CREATETABLEt2(idINTPRIMARYKEY,col1INT,col2INT,KEYindex_col1(col1))ENGINE=INNODB;SELECTt1.*,t2.*FROMt1,t2WHEREt1.col1=t2.col2ANDt2.col2;//部分查询计划do{//得到下一个参与Join的表t以及位置n(t,n)=best_extension(pplan,remaining_tables);//将t与部分查询计划拼接，即t就是第n个参与Join的表pplan=concat(pplan,(t,n));//维护还剩下哪些表没参加Joinremaining_tables=remaining_tables-t;}while(remaining_tables!={})returnpplan;}现在，来计算一下算法复杂度，第一次搜索，需要从10个表里选出3个表全排列，有种选取方式，第二次搜索有种选取方式，...，最后一次搜索，有种搜索方式。因此，求和后：所以，如果有N个表参与Join，并给定optimizer_search_depth=d，则算法复杂度为。当时，算法复杂度为直接枚举所有左深树，复杂度为。MySQL官方代码中给出的算法复杂度估计为，暂不清楚官方的复杂度计算方法，如果大家有任何想法，欢迎讨论。源码解读决定JoinOrder的代码都在函数choose_table_order()中。代码结构和注释也都相对清楚，大家感兴趣地可以直接看源码，在这里，做一个简单的介绍。预排序在MySQL中，optimizer_search_depth的默认值是62，意味着，大多数情况下，其实算法复杂度都会是。因此，很多时候，剪枝承担了更多降低算法耗时的功能(剪枝算法在后面绍)。 而想要减枝更好发挥作用，就必须尽早搜索到较优的JoinOrder。我们在引言中的例子发现，一般而言都是先读行数较少的表，然后再读行数较多表，这样得到的JoinOrder可能会更好，如果我们先枚举的JoinOrder都是先读小表，就有可能尽早找到较优的JoinOrder。因此，在选择order之前一个重要操作就是预排序，这个函数会按照有无OuterJoin/StraightJoin的依赖关系、有无key的引用、estimate_rowcount()中对表记录数的估计进行排序：1. Outer Join和Straight会强制要求Join的顺序，因此先判断表之间有无Outer Join或者Straight Join的依赖关系2. 判断两个表之间有无key的依赖关系，假如t1和t2的join cond中，有t1.no_key = t2.key，那么先读t13. 如果上述都不满足，那么就比较在estimate_count()函数中得到的行数估计，小表在前。boolJoin_tab_compare_default:perator()(constJOIN_TAB*jt1,constJOIN_TAB*jt2)const{//Sortingdistincttables,soatableshouldnotbecomparedwithitselfassert(jt1!=jt2);//OuterJoin和Straight会强制要求Join的顺序，因此先判断表之间有无OuterJoin或者StraightJoin的依赖关系if(jt1->dependent&jt2->table_ref->map())returnfalse;if(jt2->dependent&jt1->table_ref->map())returntrue;//判断两个表之间有无key的依赖关系，假如t1和t2的joincond中，有t1.no_key=t2.key，那么先读t1constbooljt1_keydep_jt2=jt1->key_dependent&jt2->table_ref->map();constbooljt2_keydep_jt1=jt2->key_dependent&jt1->table_ref->map();if(jt1_keydep_jt2&!jt2_keydep_jt1)returnfalse;if(jt2_keydep_jt1&!jt1_keydep_jt2)returntrue;//如果上述都不满足，那么就比较在estimate_count()函数中得到的行数估计，小表在前。if(jt1->found_records>jt2->found_records)returnfalse;if(jt1->found_recordsfound_records)returntrue;returnjt1const_tables;//indexinto'join->best_ref'//当前搜索到的best_idxuintbest_idxOSITIONbest_pos;JOIN_TAB*best_table;//thenextplannodetobeaddedtothecurrQEPDBUG_TRACE;/*Numberoftablesthatweareoptimizing*///remaining_tables是个bitmap，在这里计算还有多少表待优化constuintn_tables=my_count_bits(remaining_tables);/*Numberoftablesremainingtobeoptimized*/uintsize_remain=n_tables;...//循环开始，开始执行JoinReorder的搜索算法中提及的搜索流程do{/*FindtheextensionofthecurrentQEPwiththelowestcost*///当前最好的完整查询计划的cost估计join->best_read=DBL_MAX;//当前最好的完整查询计划的rowcountjoin->best_rowcount=HA_POS_ERROR;found_plan_with_allowed_sj=false;//开始第一次搜索，由于0～idx-1个表都是const_table，因此不参与搜索，直接从第idx个表开始搜索，//搜索深度为search_depthif(best_extension_by_limited_search(remaining_tables,idx,search_depth))returntrue;/*'best_readbest_readbest_positions'containsacompleteoptimalextensionofthecurrentpartialQEP.*/DBUG_EXECUTE("opt",print_plan(join,n_tables,idxjoin->best_positions[idx-1].prefix_rowcount:1.0,idxjoin->best_positions[idx-1].prefix_cost:0.0,idxjoin->best_positions[idx-1].prefix_cost:0.0,"optimal"););returnfalse;}/*selectthefirsttableintheoptimalextensionasmostpromising*///join->best_positions[idx]记录当前搜索到的cost最低的部分查询计划中的第一个表，这个表其实就是我们想要的表best_pos=join->best_positions[idx];best_table=best_pos.table;/*Eachsubsequentloopof'best_extension_by_limited_search'uses'join->positions'forcostestimates,thereforewehavetoupdateitsvalue.*///join->positions维护了当前的搜索状态join->positions[idx]=best_pos;.../*findthepositionof'best_table'in'join->best_ref'*///维护best_ref，best_ref是当前的最优的查询计划best_idx=idx;JOIN_TAB*pos=join->best_ref[best_idx];while(pos&best_table!=pos)pos=join->best_ref[++best_idx];memmove(join->best_ref+idx+1,join->best_ref+idx,sizeof(JOIN_TAB*)*(best_idx-idx));join->best_ref[idx]=best_table;//维护remaining_tablesremaining_tables&=~(best_table->table_ref->map());...//剩余待优化的表数量减一--size_remain;//下次需要确定的参与Join的表的idx加一++idx;}while(true);}best_extension函数greedy_search()函数会调用best_extension_by_limited_search()函数，每次都执行深度为optimizer_search_depth的搜索来确定下一个参与Join的表。这个函数原理上其实也很简单，就是进行从剩余表中选optimizer_search_depth个表进行排列并且计算cost这个过程。best_extension()函数的源码和伪代码结构相似，因此，这里只展示伪代码。伪代码如下：procedurebest_extension_by_limited_search(pplanin,//in,partialplanoftables-joined-so-far已经参与join了的表组成部分planpplan_cost,//in,costofpplanpplan的costremaining_tables,//in,setoftablesnotreferencedinpplan还没在pplan中的tablesbest_plan_so_far,//in/out,bestplanfoundsofar至今发现的最好planbest_plan_so_far_cost,//in/out,costofbest_plan_so_far至今发现的最好plan的costsearch_depth)//in,maximumsizeoftheplansbeingconsidered当前要被搜索的plans的最大size{foreachtableTfromremaining_tables{//CalculatethecostofusingtableTasabove//对于每个待优化的表，进行一系列的复杂的cost计算cost=complex-series-of-calculations;//Addthecosttothecostsofar.//将cost加到pplan_costpplan_cost+=cost;//剪枝prune_by_costpruned_by_heuristic//将当前pplan用上面得到best_access_method进行拓展pplan=expandpplanbybest_access_method;remaining_tables=remaining_tables-tableT;//如果还有没参与Join的表并且search_depth还大于1if(remaining_tablesisnotanemptysetandsearch_depth>1){//如果tableT是通过EQ_REF-joined优化的，用eq_ref_eq_ref_extension_by_limited_search进行拓展//否则用best_extension_by_limited_search进行拓展if(tableTisEQ_REF-joined)eq_ref_eq_ref_extension_by_limited_search(pplan,pplan_cost,remaining_tables,best_plan_so_far,best_plan_so_far_cost,search_depth-1);elsebest_extension_by_limited_search(pplan,pplan_cost,remaining_tables,best_plan_so_far,best_plan_so_far_cost,search_depth-1);}else{//维护当前找到的最优plan的costbest_plan_so_far_cost=pplan_cost;best_plan_so_far=pplan;}}}该函数中的cost计算方式和剪枝方法会在之后章节中详细介绍。在这个函数中有个特殊的优化，当前参与Join的表如果是通过eq_ref的方式进行Join的（eq_ref是指在被驱动表上通过检索一个唯一键进行Join），那么此时会将其他能够使用EQ_REF进行Join的表也加入到查询计划中。这个优化只在第一次遇到用eq_ref进行Join的表才会进行。cost 计算在本节中，我们将看一下一个完整的多表Join的执行计划的代价计算。在MySQL源码中，对AccessPath有一个分类access_type：ref，eq_ref，range，scan等。在JoinReorder中的cost计算中，会将这些access_type进一步分为两类处理： ref，eq_ref：当被驱动表采用这种AccessPath时，对应的Join算法为IndexNestedLoopJoin range，scan等：当被驱动表采用这种AccessPath时，对应的Join算法为HashJoinref，eq_ref在讲ref,eq_ref的cost之前，先介绍一个概念：fanout。fanout可以理解为对于驱动表的每一条记录，能够在被驱动表中找出多少条与之能够成功Join的数据。就eq_ref而言，对于驱动表上的每一条数据，肯定在被驱动表上只有一条数据与之满足Join条件，因此fanout是1。而对于ref，驱动表上数据满足Join条件的数据其实不止一条，那么如何估计这个值呢？相信看过之前文章的同学很快能够想到，这其实又是records_per_key这个统计信息，也就是我们常说的Cardinality。这样，对于ref和eq_ref我们就都获得了fanout。有了fanout，其实IOcost计算也就很简单了，无非就是多次读索引，每次读fanout行。而读索引的次数，也就是驱动表的行数（记为prefix_rowcount）。在join的过程中，需要处理条数据，因此CPUcost 为:prefix_rowcount*fanout*row_evaluate_cost小结总costprefix_rowcount*single_io_cost+prefix_rowcount*fanout*row_evaluate_costscan，range等我们之前在boolJOIN::estimate_rowcount()函数中计算了多种类型AccessPath的cost，现在我们就是从中选择cost最小的AccessPath在这里使用。对于IOcost，其实就是要计算读几次被驱动表。在8.0中，虽然join算法从BlockNestedLoopJoin算法升级到了HashJoin，但cost的计算方式却没有改变，还是沿用BlockNestedLoopJoin算法的cost计算方式。因此，读被驱动表的次数其实就是驱动表的数据量除以JoinBuffer的大小。总的IOcost就是。接下来看CPUcost，要计算CPUcost就要计算fanout值，从被驱动表中读出的数据并不是都会直接进行join，还可能会被谓词过滤一部分，这部分的影响用calculate_condition_filter()函数计算，在这里不多展开，假设在过滤后获得rows_after_filtering行数据。那么，其实只有rows_after_filtering行会参与join，会在判断predicate时就被过滤而不会参与join计算，cpucost也就分为两部分：join_buffer_cnt*(total_records-rows_after_filtering)*row_evalute_cost+prefix_rowcount*rows_after_filtering*row_evalute_cost说一点题外话，在阅读代码的时候，我发现当被驱动表的AccessPath是range时，IOcost计算是直接，没有考虑Joinbuffer，非常疑惑，然后看到MySQL代码中这样的一行注释：TODO:We take into account possible use of join cache for ALL/indexaccess (see first else-branch below), but we don't take it intoaccount here for range/index\_merge access. Find out why this is so.大意是，我们在计算全表扫描/覆盖索引扫描的cost的时候，考虑到JoinBuffer的影响，但在计算索引范围扫描的cost的时，却没有考虑到JoinBuffer的影响，现在我们也不知道为什么，所以记了个TODO。小结总costJoin_buffer_cnt*single_io_cost+join_buffer_cnt*(total_records-rows_after_filtering)*row_evalute_cost+prefix_rowcount*rows_after_filtering*row_evalute_costrowcount计算最后，来看Join之后的行数，对于scan/range方式的AccessPath，由于已经提前估计了predicate的影响，因此行数就是，而对于ref/eq_ref，还没有考虑其他predicate的影响，因此利用calculate_condition_filter()函数又计算了filter_effect，所以行数是。AccessPath选择在计算完ref/eq_ref和scan/range的cost之后，选择cost最小的一种作为当前表最后的AccessPath。剪枝算法pruned_by_costif(position->prefix_cost>=join->best_read&found_plan_with_allowed_sj){DBUG_EXECUTE("opt",print_plan(join,idx+1,position->prefix_rowcount,position->read_cost,position->prefix_cost,"prune_by_cost"););trace_one_table.add("pruned_by_cost",true);backout_nj_state(remaining_tables,s);continue;}基于Cost的剪枝最简单，当前的cost已经大于之前找到最小cost，直接剪枝。pruned_by_heuristicif(prune_level==1){if(best_rowcount>position->prefix_rowcount||best_cost>position->prefix_cost||(idx==join->const_tables&//'s'isthefirsttableintheQEPs->table()==join->sort_by_table)){if(best_rowcount>=position->prefix_rowcount&best_cost>=position->prefix_cost&/*TODO:Whatisthereasoningbehindthiscondition*/(!(s->key_dependent&remaining_tables)||position->rows_fetchedprefix_rowcount;best_cost=position->prefix_cost;}}elseif(found_plan_with_allowed_sj){DBUG_EXECUTE("opt",print_plan(join,idx+1,position->prefix_rowcount,position->read_cost,position->prefix_cost,"pruned_by_heuristic"););trace_one_table.add("pruned_by_heuristic",true);backout_nj_state(remaining_tables,s);continue;}}启发式剪枝可以通过控制参数optimizer_prune_level来决定是否开启。 这个剪枝影响非常大，只要在当前searchdepth发现过比现在好的部分查询计划（rowcount和cost都要更低），那么就停止这条分支的继续搜索。事实上，绝大多数的查询计划都会被这条规则剪去，当不开启这条剪枝规则时，在optimizer_search_depth默认62的条件，MySQL会近似穷举，但开启这条规则后，大多数查询计划都会被提前剪枝。计算最佳AccessPath的剪枝这部分剪枝主要是当找到一种ref/eq_ref的AccessPath时，会有一些启发式规则来使得MySQL不去计算range/scan的cost。这部分规则很多，详细内容可以看MySQL给出的注释。Wedonotconsiderindex/tablescanorrangeaccessif:1a)Thebest'ref'accessproducesfewerrecordsthanatablescan(orindexscan,orrangeaccess),and1b)Thebest'ref'executedforallpartialrowcombinations,ischeaperthanasinglescan.TherationaleforcomparingCOST(ref_per_partial_row)*E(#partial_rows)vsCOST(single_scan)isthatifjoinbufferingisusedforthescan,thenscanwillnotbeperformedE(#partial_rows)times,butE(#partial_rows)/E(#partial_rows_fit_in_buffer).Atthispointinbest_access_path()wedon'tknowthisratio,butitissomewherebetween1andE(#partial_rows).Toavoidoverestimatingthetotalcostofscanning,theheuristicusedherehastoassumethattheratiois1.Amorefine-grainedcostcomparisonwillbedonelaterinthisfunction.(2)Thebestwaytoperformtableorindexscanistouse'range'accessusingindexIDX.Ifitisa'tightrange'scan(i.enotalooseindexscan'or'indexmerge'),thenrefaccessonthesameindexwillperformequalorbetterifrefaccesscanusethesameormorenumberofkeyparts.(3)SeeabovenoteaboutInnoDB.(4)NOT("FORCEINDEX(...)"isusedfortableandthereis'ref'accesspath,butthereisnoquickselect)Iftheconditionintheabovebracketsholds,thentheonlypossible"tablescan"accessmethodisALL/index(thereisnoquickselect).Sincewehavea'ref'accesspath,andFORCEINDEXinstructsustochooseitoverALL/index,thereisnoneedtoconsiderafulltablescan.总结本文浅析了MySQLJoinReorder算法的流程，cost计算，剪枝算法等，希望通过本文能帮助大家了解MySQL优化器生成执行计划的具体流程。在阅读MySQL优化器代码的过程中，也确实感觉到很多地方做的还是相对简陋，很多cost计算都很近似，我也只能根据自己的理解进行分析，如果有错误之处，欢迎大家指出。作者简介田镜祺，AliSQL内核研发人员。当前主要从事SQL优化执行、DDL相关的研发和RDS运维工作。