新规实施：申请手机号码将全面实行人脸比对
06-18
概述 本文是 TiDB 源码阅读系列文章的第八篇。正文将首先简单介绍查询计划的制定和优化过程，然后用较大的篇幅详细介绍在获得逻辑计划后如何根据统计信息和不同的属性选择生成各种不同成本的物理计划。
通过比较物理计划的成本，最终选择成本最小的物理计划，这就是基于成本的优化（CBO）的过程。优化器框架一般分两个阶段进行优化，即基于规则的优化（Rule-Based-Opimization，简称RBO）和基于成本的优化（CBO）。
TiDB 主要分为两个模块来优化计划：逻辑优化，主要根据关系代数的等价交换规则进行一些逻辑变换。物理优化主要优化查询数据读取、表连接方式、表连接顺序、排序等技术。
与RBO相比，CBO依赖于统计信息的准确性和及时性，执行计划会根据数据变换及时调整。优化器流程 TiDB 一条查询语句的简单流程：一条语句解析后，会得到一棵抽象语法树（AST）。
首先，在合法性检查后使用 AST 生成逻辑计划，然后进行解除关联和谓词下推。 、聚合下推等正则化优化，然后通过统计数据计算成本来选择最优的物理计划，最后执行。
其流程如图1所示。 图1 物理运算符简介 通过前面物理层优化的介绍，我们可以知道同一个逻辑运算符由于数据读取和计算方式的不同，可能会生成多个不同的物理运算符，例如逻辑运算符加入。
要将运算符转换为物理运算符，您可以选择 HashJoin、SortMergeJoin 或 IndexLookupJoin。这里我们将简要介绍一些逻辑运算符可选的物理运算符。
例如： select sum(*) from t join s on t.c = s.c group by a。该语句中的逻辑运算符包括DataSource、Aggregation、Join 和Projection。
接下来，我们对几种典型逻辑运算符对应的物理运算符进行简单介绍，如下表所示： 基于成本优化的CBO流程的主要思想是计算所有可能的执行计划的成本，并选择执行计划成本最低的路径。那么就可以向后推导。
首先，我们需要收集对应表的统计信息，可以用来计算每个算子的执行成本。最后，将每条路径上算子的成本按照路径进行累加，得到成本最小的路径。
。具体代码在plan/optimizer.go中的dagPhysicalOptimize函数中实现。
本文介绍的流程基本就是通过这个函数完成的。代码如下： 代码语言： javascript copy func dagPhysicalOptimize(logic LogicalPlan) (PhysicalPlan, error) {logic.preparePossibleProperties ()logic.deriveStats() t, err :=logic.convert2PhysicalPlan(&requiredProp{taskTp: rootTaskType, ExpectedCnt: math.MaxFloat64}) if err != nil { return nil, error.Trace(err) } p := t. plan() p.ResolveIndices() return p, nil} 为了可读性，下面按照代码调用的顺序不再介绍。
下面几段对应上面代码的函数如下： prune prop 对应函数preparePossibleProperties。获取统计信息对应的函数deriveStats。
其余章节介绍函数convert2PhysicalPlan。总体流程 这里我们首先描述一下整个CBO的流程。
这部分逻辑的主要框架在文件plan/physical_plan_builder.go中，具体函数为convert2PhysicalPlan。示例为了方便理解CBO的整个流程，这里举一个例子。
在扩展之前，引入所需的属性很重要。这个概念非常重要。
必需属性是对运算符返回值数据的要求。例如，如果你希望某些算子按照某些列有序地返回数据，那么就会传递相应的列信息。
如果某些运算符不需要它，您可以传递一个空属性。 。
那么，现在我们举个例子，SQL如下： select sum(s.a),count(t.b) from s join t on s.a = t.a and s.c < and t.c > 10 group bys.a (其中a是索引， b也是索引）该语句根据该语句的on条件连接表s和表t，然后聚合连接结果。它以图形方式表示，如图 2 所示（为了与图 3 进行比较，此处省略了投影运算符）。
图2 得到逻辑运算符后，我们如何选择最优的物理运算符？ TiDB 使用记忆搜索进行处理。从下到上搜索和从上到下搜索没有太大区别。
考虑到后者更容易理解，将父级需要的道具传递给子级，因此可以减少一些可能性（这个稍后会详细介绍）。我们选择了自上而下的方法。
接下来我们详细介绍一下本例中算子的生成和选择过程。一开始的 prop 是空的，对 Agg 操作符没有要求。
接下来，根据当前逻辑算子所有可能的props构造对应的物理算子，Agg可以生成Stream Agg和Hash Agg（这个逻辑在下面代码片段的genPhysPlansByReqProp中实现）。前者需要按group bykey排序，即按a列排序，所以他的child的prop里面会有a列。
如果不需要后者， prop 将为空。该逻辑代码片段位于 plan/physical_plan_builder.go 中： 代码语言：javascript Copy for _, pp := range p.self.genPhysPlansByReqProp(prop) { t, err = p.getBestTask(t, pp) if err != nil { return nil,Errors.Trace(err) }} 那么Stream Agg的孩子是Join，Join对应三个物理运算符，SortMerge Join（SMJ）、Hash Join（HJ）和Index Join（IdxJ）。
SMJ算子要求按join key排序，因此在构建DS（DataSource）时，表s需要按s.a排序，表t需要按t.a排序。因此，在将 DS 构造为物理算子时，虽然有 IdxScan(a)、IdxScan(b) 和 TableScan(TS)，但这些算子中只有 IdxScan(a) 满足 prop(s.a)。
在本例中，只有IdxScan(a)满足要求并返回给SMJ。如果还有其他符合要求的运营商，则按成本选择。
这部分内容将在“成本评估”中详细介绍。使用记忆搜索计算每个算子的prop的哈希值并将其存储在哈希表中。
因此，当HJ计算DS(s)（黄色箭头的路径）时，你会发现SMJ以下的DS(s)都已经计算出来了。 ，则直接得到该值，无需进行不必要的计算。
由于篇幅有限，这里只描述左边的路径。本例中的最后一级比较是 HA + HJ + idx(c) 和 SA + MJ + idx(a) 之间的比较。
具体来说，通过统计信息计算成本并选择最优方案。图3（图中，黑色字体算子为逻辑算子，蓝色字体算子为物理算子，黄色箭头为已计算成本的算子，将得到已缓存在哈希表中的结果，红色箭头为算子）虚线箭头不是符合 prop 的 Operator。
）成本评估成本评估的调用逻辑在plan/physical_plan_builder.go中。代码如下： 代码语言： javascript copy func (p *baseLogicalPlan) getBestTask(bestTask task, pp PhysicalPlan) (task, error) {tasks := make([ ]task, 0, len(p.children)) for i, child := range p.children { childTask, err := child.convert2PhysicalPlan(pp.getChildReqProps(i)) if err != nil { return nil, 错误。
Trace(err) }tasks = append(tasks, childTask) } resultTask := pp.attach2Task(tasks...) if resultTask.cost() < bestTask.cost() { bestTask = resultTask } return bestTask, nil} 统计这里将详细描述 CBO 过程中统计信息的使用。收集统计信息的具体方法和过程本文不再赘述。
我们将在后续文章中详细介绍。 statesInfo 结构体有两个字段： 代码语言：javascript copy // statsInfo 存储计划输出的统计基本信息。
用于成本估算。 type statsInfo struct { count float64 cardinality []float64} 其中 count 字段表示该表中的数据行数，每个表一个值。
基数字段用于表示每一列中不同数据行的数量，每一列一个。基数一般是通过统计数据得到的，即统计信息中对应表中对应列的DNV（不同值的数量）值。
具体获取这个数据的方法有两种： 方法一，使用真实的统计数据，具体公式如下： statsTable.count/ histogram.count * hist.NDV （statsTable.count会根据statslease定期更新，histogram .count only users 仅在手动分析后更新）方法2，使用估计值。由于某些情况下尚未收集统计数据，目前尚无统计数据。
具体公式如下： statsTable.count*distinctFactor 接下来我们通过两个例子来介绍通过统计数据获取运营商的statsInfo。 DataSource，首先通过前面介绍的两个公式得到count和cardinality，然后使用下推表达式计算选择性的值，选择性=filter后的行数/filter前的行数，最后用计算出的选择性来调整原来的计数和基数值。
LogicalJoin（内连接），获取该算子计数的公式：N(join(s,t)) = N(s) * N(t) / (V(s.key) * V(t.key) ) *Min(V(s.key), V(t.key)) （其中N为表的行数，V为key的基数值）可以理解为唯一值的平均行数表s和表t中的乘积乘以小表中唯一值的行数。这里介绍的逻辑在stats.go文件中的plan/deriveStats函数中。
预期计数 预期计数指示该运算符期望在整个 SQL 结束之前读取的行数。例如 SQL： select* from swhere s.c1 < 5 order by id limit 3 （其中 c1 是索引列，id 是主键列）。
我们可以简单地认为得到两种可能的规划路径图，如图4所示。前者在使用PhysicalLimit时按顺序选择id，那么它的期望计数为3。
因为有c1 < 5的过滤条件，所以TableScan 中的预期计数值为 min(n(s), 3 / f (σ(c1<5) )) 。虽然后者知道在 TopN 时需要读取 3 行，但它是按 id 列排序的，因此它的预期计数为 Max。
当在 IndexScan 中时，预期计数为 count * f (σ(c1<5))。图 4Task 在成本评估期间将物理操作员与任务对象结构相关联。
任务分为三种类型，分别是cop single、cop double和root。前两种类型可以下推到协处理器执行。
原因有二：一是它可以区分对应的算子是在 TiDB 中处理还是下推到 TiKV 的协处理器；另一个更重要的原因是为了让成本评估更加准确。这里我们举个例子，SQL如下。
：select *from t where c < 1 and b < 1 and a = 1 (其中(a,b)是索引，(b,a,c)是索引，表t有三列a、b和c)那么就可以得到以下两条路径： doubleread (即 IndexLookUpReader): IndexScan( a = 1 and b < 1 ) -> TableScan-> Selection(c < 1) singleread (即 IndexReader): IndexScan( b < 1 ) - > Selection( a = 1 and c < 1) 当不区分cop single和cop double时，会搜索底层，这会导致case 2被提前丢弃。但实际上，对于这两条路径，第一条路径被认为读取到 TiKV 两次。
从数据情况来看，成本很可能超过第二条路径。因此，我们将区分copsingle和cop double。
我们不会比较IndexScan期间的成本，而是比较Selection结束时的成本。那么很可能会选择第二条规划路径。
这样比较符合实际情况。我们计算成本的通用公式：Cost(p) = N(p)*FN+M(p)*FM+C(p)*FC（其中N表示网络开销，M表示内存开销，C表示CPU开销， F 代表将计划与任务关联起来并添加计划成本的因子）。
任务处理的代码主要在plan/task.go文件中。 pruneproperties之所以引入预处理属性函数，是为了减少一些不需要考虑的属性，以便尽早将其切分成物理计划搜索路径上的分支，例如：select *from t join s对 t.A = s.A 且 t.B = s.B 其性质可以是 {A, B}, {B, A}。
如果我们有 n 个相等条件，那么我们就有 n！可能的属性。通过此操作，我们只能使用 t 和 s 表本身拥有的属性。
属性是在DataSource的逻辑运算符中获取的，因为在该运算符中可以获取对应的主键和索引信息。这里的逻辑由文件 plan/property_cols_prune.go 中的preparePossibleProperties 函数处理。
版权声明：本文内容由互联网用户自发贡献，本站不拥有所有权，不承担相关法律责任。如果发现本站有涉嫌抄袭的内容，欢迎发送邮件 举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
标签：
相关文章
06-18
06-17
06-17
06-18
最新文章
【玩转GPU】ControlNet初学者生存指南
【实战】获取小程序中用户的城市信息（附源码）
包雪雪简单介绍Vue.js：开学
Go进阶：使用Gin框架简单实现服务端渲染
线程池介绍及实际案例分享
JMeter 注释 18 - JMeter 常用配置组件介绍
基于Sentry的大数据权限解决方案
【云+社区年度征文集】GPE监控介绍及使用