GaussDB技术解读高性能——物理优化CBO

GaussDB技术解读高性能——物理优化CBO

在优化器处理完RBO的优化以后，路径的选择往往不能通过实现制定好的规则进行变换，而是需要根据数据的分布（统计信息）情况来对查询执行路径进行评估，从可选的路径中选择一个执行代价最小的路劲进行执行，例如是否选择索引SeqScan vs. IndexScan、选择哪个索引，两表关联选择什么样的连接顺序，选择怎样的具体算法等，因此，可以将物理优化总结为对多个可行的物理执行代价进行评估，选择最优的计划输出到执行器进行执行，例如有以下查询：

select * from t1 join t2 on t1.a=t2.b;

可选择的计划有：

如上图所示，根据T1、T2可访问的执行路径：IndexScan vs. SeqScan，关联算法：HashJoin、MergeJoin、NestLoop；关联内表外表等多个维度的选择，就会生成多达数十种不同的执行计划，由于考虑到T1、T2的表大小，谓词的选择率、是否有索引等因素很难从一个固定的规则里选出一个合理的执行计划，此时需要对T1、T2表的数据特征进行建模，构建代价模型从而选出最优的计划，这个过程按照处理的顺序大体上可以分为：统计信息、行数估算、代价估算、路径搜索、计划生成五个处理步骤：

（1）统计信息，物理优化的依据来源于表信息的统计, 描述基表数据的特征包括唯一值、MCV值等，用于行数估算。

（2）行数估算，代价估算的基础，来源于基表统计信息的推算，估算基表baserel、Join中间结果集joinrel、Aggregation中结果集大小，为代价估算做准备。

（3）代价估算，根据关系的行数，推算出当前算子的执行代价，根据数据量估算不同算子执行代价，各算子代价之和即为计划总代价。

（4）路径搜索，依据若干算子的执行代价对最优路径进行路径搜索，通过求解路径最优算法（e.g. 动态规划、遗传算法）处理连接路径搜索过程，以最小搜索空间找到最优连接路径。

（5）计划生成，将查询的执行路径转换成PlanTree能够输出给执行器做查询执行，在分布式场景下根据数据分布的属性决定Data-Shuffling数据迁移总体方案。