开发者学堂课程【从0到1数据库内核实战教程：OceanBase 查询优化】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1083/detail/17317
OceanBase 查询优化器
内容介绍：
一、查询优化器简介
二、查询改写
三、查询优化
本节课讲解的是 OceanBase 查询优化，了解优化器在数据库中的作用以及 OceanBase 中优化器是如何工作的，本节课分为三个部分，这三部分分别讲解查询优化器的作用和 OceanBase 中查询改写、查询优化框架的细节。
一、查询优化器简介
1.查询优化器简介
SQL 是一种描述性的语言，用户通过 sql 向数据库说明所需的结果，但是不会向数据库表名如何去做，决定如何做是优化器所决定的。优化器会举出所有可以完成 sql 请求的执行计划，并且结合统计信息和代价模型估算每一个执行计划的代价，代价通常使用执行时间表示，不同的执行计划的性能存在几十倍、上百倍甚至上千倍的差距，因此一个好的执行计划对 sql 的执行是至关重要的，优化器是数据性能非常重要的组件。
2. 查询优化器两大框架
目前业界最常见的优化器框架有两个，分别是 System - R Style 和 Volcano / Cascade Style 。System - R Style 是一个比较古老的数据优化器框架，目前 OceanBase 也使用的此框架。在框架中，当数据库互输到一条 sql ，它会通过 Parser 和 Resolver 将这条 sql 转换成形式化的数据结构，称之为 statement ， statement 描述了原始化形式化的数据，接下来优化器会以 statement 做为输入对 sql 进行查询改写，改写的是 statement 的数据结构，得到的 statement 供物理优化器生成执行计划，最终 statement 会经过一个基于动态规划的计划生成器，得到最终的物理执行计划。 Volcano / Cascade Style 这个框架中， Parser 和 Resolver 结束之后直接就得到了逻辑计划数，接着通过一系列的改写规则应用到逻辑计划数上不断的迭代得到最终的计划数，改写规则包含很多，既包含了改写规则又包含了计划生成的优化规则，不断的迭代直到收链或是通过规则的控制来保证迭代不会无限的循环。
3. OceanBase 查询优化器总体框架
OceanBase 查询优化器使用的是 System - R 框架，总体框架如下图所示，
查询改写是基于规则改写和基于代价改写，这一部分会在第二节展开讲解；在计划生成部分，会通过动态规划生成执行计划，包含基表访问路径选择、连接顺序和连接算法以及其他算子分配，除此之外，优化器还存在一些代价模型和统计信息来辅助计划生成，代价模型和统计信息也是优化器的重要组成部分，无论是任何数据库都会依赖这两部分。
二、查询改写
首先明确为什么要进行查询改写，如下图，
左侧的 sql 是业务真实的 sql ，将表名和列名做了简化， id 是表的主键，这条 sql 对 T 表做了更新操作，更新的行是满足 id 列的值在子查询的结果中，子查询查出 T 表中 type =10并且按照 K 表前三行的 id ，这条 sql 非常的直观，对于数据库来说并不是一个好的 sql ， UPDATE 中出现了多个表而且还存在子查询，如果完全不做改写直接用这条 sql 生成执行计划则将计划生成变得复杂，因为还有连接顺序、子查询需要考虑。在 OceanBase 中，经过一系列的改写，左侧的 sql 会被改写成右侧的 sql 的形式，而右侧的 sql 只涉及到单表并且不存在子查询，计划生成就会更加简单，对于数据库来说就是好的 sql 。查询改写的目的就是为了将用户输入的 sql 改写成更易于优化的形式，易于优化包含多层的含义，直观来讲，比如可以将连接中的表中无效的条件消除掉，就可以使 sql 变得更容易优化；另一个方面，如果一个改写可以使优化器考虑更多的连接算法，也能够使 sql 变得更加优化
查询改写模块是 OceanBase 优化器中投入最多的模块，查询改写比较复杂，其中最复杂的是正确性问题和完备性问题，正确性问题指无论怎样改写都需要保证改写后的 sql 与改写前的 sql 结果是等价的，完备性指无论哪一种写法写出 sql 都需要将其识别出并且做对应的改写。查询改写的本质是模式匹配的过程，在匹配过程中保证改写的完整性，如下图例子，
sql 有三个条件， PK > 0、T 1. C 1<10、1=1，最后一个是恒正的条件，在优化时不需要考虑，将此条件直接删除，得到下面 statement 的形式，完备性要求除了考虑 WHERE 中的条件，还需要考虑到此条件会出现在其它地方，都要将其识别并消除掉。正确性需要保证所有的改写是等价的变化，要求改写后的 sql 与改写前的 sql 语义是等价的，不等价就会出现正确性问题。查询改写的有效性判断，在 OceanBase 中，将改写分为基于规则和基于代价的改写，这两类改写的有效性判断是有所区别的，基于规则的改写总是把 sql 往好的方向改写，如下图实例，条件如图所示，子查询是一个相关子查询，因为子查询的结果依赖 t 1. c 3这一列的值，如不做改写，首先会查出 t 1表中送有的数据然后对于 t 1表中的每一行使用算子驱动来做子查询，会把 t 1. c 3 的值代入子查询中，查出所有满足 t 2. c 2的值，判断 t 1. c 2是否在子查询的结果中，如在就将其返回。
基于代价的改写需要计算代价才能决定是否把 SQL 往好的方向改写，举例说明，尝试查出 t 1表中 a 1=1或 b 1=1的 sql ，将其改成如下图的形式，
UNION ALL 的上方查出了所有 a 1=1的数据，下方查出了所有 b 1=1 的数据，多出的条件为了防止出现两次，保证数据只会返回一次。UNION ALL 上方的 sql 用来快速定位数据，UNION ALL 下方的 sql 可以利用 b 1 上的索引定位数据，这种情况下下图 sql 比上图 sql 好，假设 t 1上没有 a 1或 b 1上的索引，此种情况下并不能让 sql 往好的方向改，对于第一个表来讲只需要扫描就可以拿到所需的数据，对于第二个表是将第一个表扫描两次才能拿到所需的数据。这种改写叫做代价改写，估算改写前、后 sql 的代价，改写后 sql 的代价低时才会选择改写它，此种改写比基于规则的改写复杂，因为首先需要计算代价来确定是否需要改写，需要在改写的过程中保留两份 statement ，一份是改写前的，一份是改写后的，当改写后的 statement 代价更高，sql 回退成改写前的格式，代价计算是要完整进行一遍，查询优化的流程导致基于代价的改写要比基于规则的改写复杂很多，在实践中发现基于代价的改写未必是完全准确的，若 sql 出现了多表连接时，优化器的选择率的计算以及代价的计算都是不能够计算准确的，这个问题在所有的数据库中都会存在，目前还没有很好的解决方案，所以在代价改写中也加了基于规则的判断，判断改写之后计划的形状，如果满足了特定的规则是会强制做改写的。
OceanBase 在改写过程中是不断迭代基于规则和基于代价的改写，这两类改写的迭代是同时进行的，按照自身定义的顺序去依次尝试每一个改写规则，直到结束。
目前在 OceanBase 中已经支持了很多改写规则，如下图是其中一部分，
基本上学术界和工业界中的改写在 OceanBase 中已经做了，此外， OceanBase 还存在一些独有的改写规则，这些改写规则是开发者根据业务的实际场景中抽象提炼中的。
三、查询优化
目前， OceanBase 支持 Left / Right Deep Tree , Deep Tree , Bushy Tree ，Bushy Tree 指允许连接的两侧都是异步连接，而 Left Deep Tree 允许连接的右侧只能是一个基表，对应的 Right Deep Tree 要求所有连接的左侧是一个基表， Deep Tree 相当于条件放高的 Left / Right Deep Tree ，连接的任意一侧是基表，大部分数据库都是不支持 Bushy Tree 或是默认不生成 Bushy Tree 的计划的，因为一旦打开了 Bushy Tree ，计划之间成指数级增长会导致计划代价过高， OceanBase 也是默认不生成 Bushy Tree 的计划的，但是允许用户指定优化器使优化器生成 Bushy Tree 的计划， OceanBase 默认生成 Deep Tree 的计划。在枚举算法中， OceanBase 支持的是动态规划算法和线性算法，因为动态规划算法开销是非常大的，当连接的表非常多时，计划的枚举空间就非常大，此时会将其回退成线性的算法，线性算法可以使计划快速结束。线性的枚举算法在一些情况下生成的计划不是很好，在后续的版本中也相应做了优化，使用贪心算法代替线性算法，在计算枚举后有一个计算的流程去计算每一个计划的代价，继续统计信息，选择率计算和中间结果估计和代价模型去评估不同代价的计划。
如下图的例子是两个表连接，
假设在不考虑索引的情况下，会生成哈希状的计划等，交化左右表的顺序在生成一次这三种连接的计划，这一个简单的两表连接会有六种计划。以上可以得到计划枚举是一个比较难的问题，难点在于它的计划空间非常大。
询中间有一个事实表，此表会与多个维度表连接，在这种情况下，当连接表的个数到达25个时候，在不考虑物理算子实现，不考率基于代价的改写，不考虑分布式优化的情况下，逻辑计划的数量就有两亿多个，这个量级非常大，如都考虑，以 TPCH 为例， Q 2有两亿个逻辑计划， Q 8有7.51亿个逻辑计划，如何在海量的计划空间中高效的枚举计划就是一个复杂的问题。
在 OceanBase 中，小于10的场景下采用的是动态规划算法，动态规划是一个按照 size 去做迭代的算法， size 表示的是表的数量，在实现上首先会枚举所有 size 唯一的表的执行计划，枚举的是单表的最优执行计划，单表的最优执行计划实际是做基表访问路径选择，在决定访问一个基表时走主表还是走索引。
OceanBase 的基本表访问路径的选择是存在前置规则和 skyline 剪枝的优化策略的，前置规则是一种确定性的规则，当某个索引满足规则时，则直接选中此索引，不考虑其它索引，当唯一索引全覆盖不需要回表时就会直接选择这个唯一索引，若前置规则无法命中，就会使用 skyline 剪枝来减少基表访问路径的速度和空间， skyline 最初是由学术界提出的一个优化器的算子，从字面意思上理解是天气线，这些点会组成搜索空间的集合。在上图中，最优的解一定是靠在坐标轴的边界线上，如果一点 a 不在边界线上，总能找到一点 b 在两个维度上都不会比点 a 差，所以可以提前裁剪掉不在最优解集合中的索引，减少基表路径搜索空间。
OceanBase 中的 skyline 剪枝包含了三个维度，第一个维度是索引是否回表，如果一个查询中一个表上所有的列都能从索引中拿到，那么这个索引是需要回查主表就可以拿到所有的列；第二个维度是索引是否存在 interesting order ，在 OceanBase 中，主表按照主键有序，如果有一个索引的序在后序的算子执行中被使用到，此时就表明索引中存在 interesting order ，上图中右方的查询第一个索引在 a 列上有序，而 a 这个序可以用来消除后面的 ORDER BY ，所以就说第一个列存在 interesting order ，而第二个索引在 b 点上有序，这个序无法被后面的算子用到，所以就说索引 b 不存在 interesting order ；第三个维度是索引前缀能否抽取 query range ，简单的理解是索引的前缀是否可以快速的定位数据，比如存在一个 ab 列上的索引，在 a 存在一个简单的过滤条件，则索引的前缀 a 就可以用来快速的定位数据。
如下图是 Skyline 剪枝的例子，
此处存在一个是 Skyline ，它的主键是 pk ，还有五列 c 1、c 2、c 3、c 4、c 5，存在两个索引，第一个索引是在 c 1、c 3、c 5上的索引，第二个是在 c 3、c 4上的索引。主表本质上可以看作按照主键有序的索引，主表不需要回表， pk 这个序是不可以让后面的 group by 用到，所以没有 interesting order ，由于 pk 上没有简单过滤条件，所以也不能抽取 query range ；第二个索引，查询需要用到 Skyline 上的 c 1、c 3、c 5列，其中 c 1做 group by ，c 3做过滤， c 5用来最终的聚合，发现 c 1、c 3、c 5都在索引中，所以不需要回表，索引按照 c 1、c 3、c 5有序，存在 interesting order ，由于存在 c 1、c 3上简单的过滤条件，所以索引前缀是可以用来抽取 query range ；最后一个索引，刚提到查询需要用到 Skyline 上的 c 1、c 3、c 5列，索引上只存在 c 3这个列，所以 c 1和 c 5 一定要做回表才可以拿到， c 3和 c 5也不可以被后面的算子用到，所以不存在 interesting order ， c 3上存在简单过滤条件，所以可以在索引前缀 c 3上抽取 query range ，可以得出结论，第二个索引在维度上都不比另外两个差，会将第一个和第三个裁剪掉，第二个索引去生成 Skyline 。
接下来讲解动态规划算法，当基表访问路径生成完成后， size 唯一的表生成完成后，就会继续生成 size 2的计划，依次生成图中第二行，
比如生成{ R 1, R 2} 时，会枚举所有连接算法的 { R 1, R 2} 计划，会交换两表顺序生成所有连接顺序 { R 1, R 2} 的计划，然后保留最优的执行计划集合，接下来会依次生成 size 3、 size 4 的执行计划，当 size 4执行计划生成后就得到了所有表的最优计划集合，最有计划集合包含代价最小的计划和有 interesting order 的计划，如下图的例子，
索引 a 有 interesting order ，执行索引 a 需要花费10秒，索引 b 的代价是8秒但是它没有 interesting order ，主表的代价是5秒也没有 interesting order ，此时会保留代价最小的则是主表，也会保留索引 a 存在 interesting order 的，因为本身就是按照 a 有序的，不需要排序直接取前十行，找到所有满足要求的数据，如执行主表或索引 b 是要将它们的数据按照 a 排序，随后才可以取前十行，多了一个排序的操作。
接下来按照 sql 的逻辑去分配其它的算子，
比如会执行 Group By 窗口函数、 Order By 、 Limit 等，最优计划集合有两个，一个是 mer 状的计划，另一个是哈希状的计划，哈希计划是代价最小的计划， mer 计划是由 interesting order 的计划，此时需要分配 Group By 算子， Group By 算子有两种实现，一种是 mer Group By ，另一种是哈希状 Group By ，对于每一个计划都会对其分配哈希状 Group By 和 mer Group By ，这样就会得到四种计划，依然会从四个计划中保留代价最小的以及含有 interesting order 的计划，后面的所有算子都是这种逻辑，都是在最优计划集合里分配出所有的算子实现，去保留代价最小的以及含有 interesting order 的计划，当所有算子分配完成后，就得到了整个计划的最优计划集合，从里面取出就得到了所需要的计划，以上就是 OceanBase 中基于动态规划去生成计划的全部流程。 OceanBase 是一个分布式的数据库，计划生成过程中必然会涉及分布式计划的优化。
