TiDB源码阅读: 物理计划的生成

亦凉 2023-10-03 10:26 13阅读 0赞

### 前言 ###

距离上一次的源码学习笔记已经不知过去了多少时日，大家可能会以为本人已经从入门到入土了，但是并没有！我还在坚强的学习！

中间这段时间处理的事情比较多，虽然大多还是和TiDB相关，但却很难有时间静下心来完成一篇学习笔记。刚好最近时间稍微轻松点，又有同学对于前面的笔记提出一些问题，于是决定继续记录自己的源码阅读笔记，在前面TiDB源码阅读系列文章中，都只是简单的讲解了SQL处理的流程等，对于中间的具体一些模块很少有深入的。

在前面，我们将SQL执行引擎大概分为了四个模块：SQL解析 - 制定计划 - 优化计划 - 执行计划。在制定和优化计划的过程中 ，会生成两种计划，一个是逻辑计划，一个是物理计划，当SQL解析为抽象语法树后，会先转为逻辑计划并进行一定的优化（RBO），然后将逻辑计划基于代价优化（CBO）为一个物理计划。这整个过程在前面的文章有简单的介绍，大家可以先阅读对这一块有一定的了解后，在来阅读本篇文章。

[TiDB源码学习笔记：制定计划][TiDB]

这篇文章的主题是物理计划的生成，这是在前面文章中没有深入讲解的。物理计划生成的核心就是基于代价的优化，在生成的过程就是将逻辑计划中的每一个子节点（称为逻辑算子）进行转换，转换成相应的物理算子，最后构成一颗物理计划树，这个过程中，每一个逻辑算子其实是可以转换为多个物理算子的，那么就会存在一个问题，怎么判断一个逻辑算子转换为那一个物理算子，凭借什么条件来选择，此时就需要进行代价评估，执行不同的物理算子其代价是不同的，这里的代价我们可以简单的理解为资源的消耗和时间的消耗，那么在选择的时候我们肯定就是选择代价最小的算子来生成一个最优的物理计划，执行起来速度最快！数据库嘛，要的就是快！

TiDB官方有一篇文章，对这一块有过介绍，讲解还是很清晰的，但是其代码版本比较老了，现在新版本已经很难找到其文中的方法。本文会参考该文章进行讲解，同时本文的TiDB代码版本为： 4.0.11。

[TiDB 源码阅读系列文章（八）基于代价的优化][TiDB 1]

### **逻辑算子&物理算子** ###

首先介绍一下构成计划树的节点，又称之为算子，逻辑计划由逻辑算子构成，物理计划由物理算子构成。逻辑算子比较常见的有 Projection，Aggregation，Join 和 DataSource，分别是投影（例如：Select \* ），聚合（例如：Sum，Count），连表（例如：Left Join）和扫表（例如：From table）。对应的。每一种逻辑算子在真正去执行的时候，执行的方法是不一样的，也就会转换成不同的物理算子。

举一个最为简单的例子，同样的逻辑算子 DataSource，扫表操作，在不同的情况下可以有不同的策略，例如如果可以使用索引的情况下，我们可以使用索引进行扫表（IndexReader），也可以正常的通过 row ID 扫描表（TableReader）。在选择的时候，我们就需要估算两种扫表方式，哪一种更好，通过该表的元信息来计算两种扫表方式的代价，选择代价更小的算子。这里可以拿官方文档的一个图供大家参考，列出了常用的三种逻辑算子和其能转换的物理算子：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw_size_16_color_FFFFFF_t_70][]

最后给大家一个问题：在扫表操作的时候，是不是使用索引进行扫表一定比全表扫描要更快？代价更小？

### **Hints & Physical Property** ###

在实际物理代价的生成中还需要考虑更多的问题，比如 Hints 和 Physical Property，大家都知道，数据库虽然会选择最快最优的计划去执行，但是数据库毕竟只是一个存储数据的系统，且要求一定的性能和速度（强调速度），没有强大的AI撑场，也没有时间提供复杂的算法去计算，所以并不是每一次执行SQL都能够做出最优的抉择，生成最好的执行计划。

有些时候进行数据库调优的场景会使用到 Hints，也就是提示，在物理计划的生成过程需要考虑到用户是否使用过Hints，比如在从逻辑算子 Join 转换成物理算子的时候，用户在指定了使用 HashJoin ，那么在转换的时候会优先（强制）选择 HashJoin 作为物理算子，那么此时就不需要考虑代价问题了。

除了Hints会作为选择物理计划中的一个额外条件外，还有一个是 Physical Property，也就是父节点对于子节点的数据要求（Prop），在一个物理计划的构建中，父节点的物理算子对于子节点的物理算子返回的数据会有一定的要求，所以在子节点进行选择转换成某一个物理算子的时候就需要考虑该物理算子是否满足其父节点的要求。

举一个列子：参照上图，现在有一个父节点是Join算子，转换为物理算子的时候为 SortMergeJoin，那么其要求则是 Join 的两个表都按照Join Key 有序，每个表都要通过 IndexReader 读取数据进行匹配，那么此时的该要求就会存到 Prop 中传到子节点 DataSource ，子节点 DataSource 在考虑转换成 IndexReader，TableReader 和 IndexLoopUpReader 的时候就需要加上 Prop中的条件，最终选择 IndexReader 这个物理算子，在这个时候同样不会在考虑其代价了。

### **Physical Property** ###

// PhysicalProperty stands for the required physical property by parents.
    // It contains the orders and the task types.
    type PhysicalProperty struct {
     Items []Item
     
     // TaskTp means the type of task that an operator requires.
     //
     // It needs to be specified because two different tasks can't be compared
     // with cost directly. e.g. If a copTask takes less cost than a rootTask,
     // we can't sure that we must choose the former one. Because the copTask
     // must be finished and increase its cost in sometime, but we can't make
     // sure the finishing time. So the best way to let the comparison fair is
     // to add TaskType to required property.
     TaskTp TaskType
     
     // ExpectedCnt means this operator may be closed after fetching ExpectedCnt
     // records.
     ExpectedCnt float64
     
     // hashcode stores the hash code of a PhysicalProperty, will be lazily
     // calculated when function "HashCode()" being called.
     hashcode []byte
     
     // whether need to enforce property.
     Enforced bool
    }

TiDB 中使用 PhysicalProperty 结构体来存储父节点对子节点的要求，主要属性为 Items 存储要求列表，TaskTp 存储任务类型，包括 rootTask （TiDB执行）和 copTash（TiKV执行），ExpectedCnt 表示期望读到的记录行数。

### **Task & Cost** ###

Task是一个物理计划的新版本，主要存储的是计划的成本信息，一个Task可能是 RootTask，CopTask，MPPTask或者ParellelTask，那么实际上TiDB源码中对于Task的接口实现只有 RootTask 和CopTask的实现，那么后面几种可能就是者两种Task的衍生，可以从结构简单的了解到，一个Task存储着计划和代价这两个最基本的属性，在RootTask的实现中只有这两个属性，而在CopTask的实现中属性更多，因为其需要到TiKV中去执行，所以需要参数更多。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw_size_16_color_FFFFFF_t_70 1][]

Cost为代价，在物理计划的生成中，每一个物理算子都会计算其代价，然后选择代价最小的物理算计进行转换，代价的计算上要在于 IO 开销，CPU开销，内存开销和网络开销，在代码中我们可以仔细的看一下是如何计算的。

由于一个物理计划是由多个物理算子组成，所以最后比较时是所有物理算子代价之合取最小，即为最优物理计划。

这个地方可以了解一下，在一个复杂的计划中，可能会存在重复的物理算子进行计算，如果每一次都算一次，性能就会非常差，那么在TiDB中采用记忆化搜索算法，将计算过的值进行保存，下一次就可以不用再进行计算，用于提升性能。

### **源码** ###

上面介绍了物理计划中涉及到的一系列概念，下面我们深入到源码中具体看一下整个物理计划生成的过程。

从逻辑计划转为物理计划的过程为TiDB源码 planner/core/optimizer.go 中的 DoOptimize, 该方法注释非常直接：将逻辑计划优化为一个物理计划。

**DoOptimize**

// DoOptimize optimizes a logical plan to a physical plan.
    func DoOptimize(ctx context.Context, sctx sessionctx.Context, flag uint64, logic LogicalPlan) (PhysicalPlan, float64, error) {
     // 基于规则优化逻辑计划
     logic, err := logicalOptimize(ctx, flag, logic)
     
     // 基于代价计算将逻辑计划优化为物理计划
     physical, cost, err := physicalOptimize(logic)
     
     
     // 对物理计划进行后期优化
     finalPlan := postOptimize(sctx, physical)
     return finalPlan, cost, nil
    }

该方法中主要包括三个步骤： 逻辑计划优化（基于规则的优化），将逻辑计划优化为物理计划（基于代价的优化）和 最后的一些处理。这里主要关注第二个方法 physicalOptimize。

**physcialOptimize**

func physicalOptimize(logic LogicalPlan) (PhysicalPlan, float64, error) {
     // 初始化一个空的Prop
     prop := &property.PhysicalProperty{
     TaskTp:      property.RootTaskType,
     ExpectedCnt: math.MaxFloat64,
     }
     // 寻找最优的Task 
     t, err := logic.findBestTask(prop)
     
     return t.plan(), t.cost(), err
    }

PhysicalOptimize方法会初始化一个 Prop，也就是前面提到PhysicalProperty结构体，一开始是一个空的，不断遍历子节点时，这个Prop就会不断的填充数据。

下面的 findBestTask 方法是物理计划转换的一个关键方法，其作用是将逻辑计划转换为最优物理计划，可以看到该接口有7种实现，针对于不同的逻辑计划实现不同。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw_size_16_color_FFFFFF_t_70 2][]

下面可以选择其中一个的实现中，了解实现过程，这里选择 baseLogicalPlan。

#### baseLogicalPlan.FindBestTask ####

// findBestTask implements LogicalPlan interface.
    func (p *baseLogicalPlan) findBestTask(prop *property.PhysicalProperty) (bestTask task, err error) {
     
       // Look up the task with this prop in the task map.
       // It's used to reduce double counting.
       bestTask = p.getTask(prop)
     
       var plansFitsProp, plansNeedEnforce []PhysicalPlan
       // Maybe the plan can satisfy the required property,
       // so we try to get the task without the enforced sort first.
       plansFitsProp, hintWorksWithProp = p.self.exhaustPhysicalPlans(newProp)
       if !hintWorksWithProp && !newProp.IsEmpty() {
          // If there is a hint in the plan and the hint cannot satisfy the property,
          // we enforce this property and try to generate the PhysicalPlan again to
          // make sure the hint can work.
          newProp.Enforced = true
       }
     
       if newProp.Enforced {
     
     
          plansNeedEnforce, hintCanWork = p.self.exhaustPhysicalPlans(newProp)
     
          if hintCanWork && !hintWorksWithProp {
             plansFitsProp = nil
          }
     
          if !hintCanWork && !hintWorksWithProp && !prop.Enforced {
             plansNeedEnforce = nil
          }
       }
     
       newProp.Enforced = false
       if bestTask, err = p.enumeratePhysicalPlans4Task(plansFitsProp, newProp); err != nil {
          return nil, err
       }
       newProp.Enforced = true
       curTask, err := p.enumeratePhysicalPlans4Task(plansNeedEnforce, newProp)
     
       if curTask.cost() < bestTask.cost() || (bestTask.invalid() && !curTask.invalid()) {
          bestTask = curTask
       }
     
       p.storeTask(prop, bestTask)
       return bestTask, nil
    }

方法实现比较长，文中省去了部分代码，只保留重要的代码和注释，通过参数名和注释对于代码逻辑有基本了解。可以看到，在代码中出现了我们前面讲到的Hints个Prop，一个是提示，一个是父节点要求， 在生成物理计划的时候要一直考虑这两个的因素，从代码中也可以读到。

这段代码中有两个关键的方法，exhaustPhysicalPlans() 和 enumeratePhysicalPlans4Task()，加上该方法本身 findBestTask()，三个方法共同构成了物理计划生成的整个过程。

exhaustPhysicalPlans() 方法会穷尽讨论一个逻辑计划可转换的所有物理计划，例如如果是一个 Join 的逻辑算子，那么他会讨论所有Join能转换的物理算子，例如 HashJoin，IndexJoin和MergeJoin 等。

可以从源码中看下该接口的注释和实现。该接口会返回两个值，一个是所有满足Prop的物理计划，一个是Hint是否起作用。那么在前面 findBestTask 方法过程中可以知道，当存在 Hints 没有起作用，也就是不满足 Prop 的时候，会修改 Prop 的 EnForced 属性为True，进行强制该 Prop 来重新生成一次物理算子，保证 Hints 能够起作用，如果最后Prop 和 Hint 两者无法确实同时满足，那么就不存在满足要求的物理算子来转换。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw_size_16_color_FFFFFF_t_70 3][]

可以看到该接口的实现多达16种，包含各种逻辑计划，这里我们选择上述的 LogicalJoin 算子实现，进去学一下，是否讨论了所有的 Join 物理算子。

**LogicalJoin.exhaustPhysicalPlans**

// LogicalJoin can generates hash join, index join and sort merge join.
    // Firstly we check the hint, if hint is figured by user, we force to choose the corresponding physical plan.
    // If the hint is not matched, it will get other candidates.
    // If the hint is not figured, we will pick all candidates.
    func (p *LogicalJoin) exhaustPhysicalPlans(prop *property.PhysicalProperty) ([]PhysicalPlan, bool) {
     
       joins := make([]PhysicalPlan, 0, 8)
       if p.ctx.GetSessionVars().AllowBCJ {
          broadCastJoins := p.tryToGetBroadCastJoin(prop)
          if (p.preferJoinType & preferBCJoin) > 0 {
             return broadCastJoins, true
          }
          joins = append(joins, broadCastJoins...)
       }
       if prop.IsFlashOnlyProp() {
          return joins, true
       }
       // 讨论 MergeJoin，如果preferJoinType指定该物理算子，则直接返回MergeJoin
       mergeJoins := p.GetMergeJoin(prop, p.schema, p.Stats(), p.children[0].statsInfo(), p.children[1].statsInfo())
       if (p.preferJoinType&preferMergeJoin) > 0 && len(mergeJoins) > 0 {
          return mergeJoins, true
       }
       joins = append(joins, mergeJoins...)
     
       // 讨论 IndexJoin，如果preferJoinType指定该物理算子，则直接返回IndexJoin
       indexJoins, forced := p.tryToGetIndexJoin(prop)
       if forced {
          return indexJoins, true
       }
       joins = append(joins, indexJoins..
     
       // 讨论 HashJoins ，如果preferJoinType指定该物理算子，则直接返回HashJoins
       hashJoins := p.getHashJoins(prop)
       if (p.preferJoinType&preferHashJoin) > 0 && len(hashJoins) > 0 {
          return hashJoins, true
       }
       joins = append(joins, hashJoins...)
     
       if p.preferJoinType > 0 {
          // If we reach here, it means we have a hint that doesn't work.
          // It might be affected by the required property, so we enforce
          // this property and try the hint again.
          return joins, false
       }
       return joins, true
    }

可以很清楚的看到，源码种讨论了四种可转换的物理算子：boradCastJoins，MergeJoins，IndexJoins 和 HashJoins，并且在每一次讨论后都会添加到 joins 数组中返回，当然如果 Hint 指定了某种物理算子（p.preferJoinType），则在讨论完成后直接返回该物理算子。

最后一个关键的方法为 enumeratePhysicalPlans4Task()，用于枚举所有物理计划的Task，也就是通过枚举计算物理计划的代价，输入的参数便是 exhaustPhysicalPlans() 方法生成的所有符合要求物理算子。

**enumeratePhysicalPlans4Task**

func (p *baseLogicalPlan) enumeratePhysicalPlans4Task(physicalPlans []PhysicalPlan, prop *property.PhysicalProperty) (task, error) {
       var bestTask task = invalidTask
       childTasks := make([]task, 0, len(p.children))
       // 遍历子节点并调用子节点findBestTask方法
       for _, pp := range physicalPlans {
          // find best child tasks firstly.
          childTasks = childTasks[:0]
          for i, child := range p.children {
             childTask, err := child.findBestTask(pp.GetChildReqProps(i))
             ......
             childTasks = append(childTasks, childTask)
          }
     
          // combine best child tasks with parent physical plan.
          curTask := pp.attach2Task(childTasks...)
     
          // Enforce curTask property
          if prop.Enforced {
             curTask = enforceProperty(prop, curTask, p.basePlan.ctx)
          }
     
          // optimize by shuffle executor to running in parallel manner.
          if prop.IsEmpty() {
             curTask = optimizeByShuffle(pp, curTask, p.basePlan.ctx)
          }
     
          // get the most efficient one.
          if curTask.cost() < bestTask.cost() || (bestTask.invalid() && !curTask.invalid()) {
             bestTask = curTask
          }
       }
       return bestTask, nil
    }

代码逻辑非常的清晰，并且在这个方法中我们能看到一个非常重要的信息，就是在该方法中，会遍历当前节点的所有子节点，并调用其子节点的 findBestTask 方法，获取子节点可转换的最优物理算子。

这里有一点需要注意，当到了叶子节点时，是不需要继续遍历其子节点，因为没有已经子节点，在逻辑计划中，一般最后的叶子节点是逻辑算子 DataSouce 扫表，所以在 DataSource 的 findBestTask 方法实现中是不会调用 enumeratePhysicalPlans4Task 这个方法的，而是直接讨论 DataSource 可转换的物理算子并计算代价了。

那么看到这里大家头脑应该有一个基本的流程，整个逻辑计划树是如何转换成为一个物理计划树的：

1.  从根节点开始，调用 findBestTask 寻找根节点所有可转换的物理算子通过exhaustPhysicalPlans 方法
2.  在 enumeratePhysicalPlans4Task 中遍历其所有子节点，在每一个子节点上再调用 findBestTask 方法寻找当前子节点所有可转换的物理算子。
3.  直到最后叶子节点（一般为DataSource），再从叶子节点开始计算物理算子的代价
4.  向上递归计算父节点的总代价（包括子节点），选择代价最小的路径。
5.  最终回到根节点，并获取到最小代价的物理计划。

整体上其实可以理解为一个树的深度优先遍历和递归计算代价。

文章写到这里内容已经太多了，所以更加深入的代码也不再继续跟下去了，其实了解关键的三个方法 findBestTask()，exhaustPhysicalPlans() 和 enumeratePhysicalPlans4Task()后，基本对于物理计划的生成也是有了比较深的理解，至于每个物理算子生成和代价计算的详细过程就需要大家自己进入代码之中研读了。

本文并没有最后提供流程图供大家参考，因为物理计划生成的流程根据逻辑计划的复杂度会有不同的流程，简单的流程图并不能兼顾所有，完整的流程图太过复杂，不仅无法帮助大家快速理解，甚至会看了之后失去看源码的理智。

[TiDB]: https://zhuanlan.zhihu.com/p/334986433
[TiDB 1]: https://pingcap.com/blog-cn/tidb-source-code-reading-8/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210709152527252.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210709152610863.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210709152635478.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210709152708422.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NCR0NhbXB1cw==,size_16,color_FFFFFF,t_70