OceanBase查询优化器
摘要：本文整理自OceanBase团队高级技术专家王国平，在深入浅出 OceanBase线上技术沙龙第二期的分享。
本篇内容主要分为四个部分：
1.查询优化器简介
2.查询改写
3.查询优化
4.统计信息和代价模型
一、查询优化器简介
查询优化器是关系数据库系统的核心模块，是数据库内核开发的重点和难点，也是衡量整个数据库系统成熟度的“试金石”。查询优化理论诞生距今已有四十来年，学术界和工业界其实已经形成了一套比较完善的查询优化框架。
查询优化器从诞生以来一共出现了两大框架。第一个是Volcano/Cascade Style框架，第二个是System-R Style框架。
查询优化器的整个框架以规则的形式展示给用户。主要分为两大类，即逻辑规则和物理规则。
其中，逻辑规则本质是关系代数，把一个逻辑计划转化成为另一个等价的逻辑执行计划；物理规则会涉及到物理实现。
在这个框架里，Volcano/Cascade Style有两个优点：
第一，扩展性。数据库里的任何优化都可以通过上述规则实现；
第二，Top-down DP算法。它会提前生成一些计划，作为后续计划的解释。
Volcano/Cascade Style的缺点在于复杂的规则体系管理，导致大量重复计划生成。除此之外，它很难找到一个最小规则集合。
上图是OceanBase查询优化器总体框架。左边包括查询改写和计划生成。其中，计划生成主要包含基表访问路径选择；连接顺序和连接算法和其它算子分配。
右边包括计划缓存，自适应计划匹配，计划演进，主要属于计划管理范畴。
接下来，看看OceanBase的查询优化器是如何执行的？首先，外部进入一条SQL语句，经过Parser/Resolver，转化成为内部结构Statement。其本质是用来描述原始查询的数据结构，主要包括SELECT LIST，FROM LIST，WHERE LIST等具体内容。
改写查询主要在数据结构上实现。查询改写会输出另一个Statement结构。在计划生成时，优化器会用这个Statement，生成一个总体的逻辑执行计划。然后，将其翻译成物理执行计划，从而输出最终计划。
如上图所示，左边的查询列表里有三张表的连接，即t1,t2,t3。查询优化器识别执行计划。执行计划最终会转换成对应的物理执行计划，从而输出最终计划。
二、查询改写
优化器里面比较重要的模块是查询改写模块。查询改写模块也是优化器的难点和重点。因为SQL是一种描述性的语言，所以为了获取同一个查询结果，不同的用户会写出不同的SQL。查询改写的目的是把“用户的好SQL”转化成为，更加易于优化的SQL。
如果改写的SQL不等价，意味着返回结果可能不准确。在OceanBase里，工作人员每次做改写规则时，必须确定其语义上是等价的。有时需要从关系代数的角度，证明改写规则是正确的。其次，设计的改写规则，必须能够识别出用户写的每一个SQL。
查询改写在模式匹配方面，必须保证其完整性；在等价变化方面，必须保证其正确性。只有基于规则和代价，才能判断查询改写是否有效。
OceanBase基于规则的改写，总是把SQL往好的方向改写。其主要特点是触发这类改写总能生成更好的执行计划，这类改写算法总是有效的。这类算法的整体流程是匹配模式，执行改写。
基于代价的改写，其主要特点是某些场景下改写后能生成更好的执行计划，有些场景下不能。是否可以触发这类改写，需要根据实际的数据分布、是否有合适的索引等因素来判断。
查询改写本质是Statement。在改写模块，有很多基于规则的改写。OceanBase有一个改写迭代策略的迭代器，通过不断迭代改写规则直至收敛。综上所述，OceanBase的查询改写框架，是基于代价跟规则的改写框架。
近年来，OceanBase不断从业务中，提炼并积累了各式各样的查询改写规则。有基于规则的常量折叠，SPJ和非SPJ的视图合并，连接消除等。也有基于代价的Or-expansion，Group by replacement，窗口函数改写等。
在OceanBase里，如果想要扩展一个改写规则，只需要继承一个类，实现一个Class里的虚函数接口。同时，利用改写的基础算法，很容易实现改写扩展。业务的复杂SQL，是查询改写的试金石跟原动力。目前，在OceanBase4.0中，已经有四十个改写规则框架。
三、查询优化
接下来，讲一下OceanBase的物理优化器。主包含两大部分，即计划枚举和代价计算。计划枚举包括计划形状的Deep Tree,Bushy Tree；以及枚举算法的DP，Greedy Algorithm。代价计算包括统计信息，选择率计算和中间结果估计，以及代价模型。
计划枚举是一个有确定性的算法。如果有三种连接方式，就会出现六个执行计划。每个执行计划都会计算代价，最终选择代价最小的执行计划。
在新型查询下，如果超过25张表，没有数据能枚举出来。其逻辑执行计划已经到了2亿级别。从另一个角度看，查询优化器从来都不是选择最优计划，而是避免最差计划。
在OceanBase里，如果基表个数小于十张，会使用动态规划算法。首先，枚举所有一张表的执行计划；然后，枚举两张表的执行计划；接着，枚举三张表的执行计划，以此类推。如果超过十张基表，在开源版本会有启发式的算法，快速收敛执行计划。
当OceanBase在执行计划枚举时，主要维护代价最小的计划和interesting order计划。如上图所示，总共有三个索引路径：p1,p2,p3。
索引a的执行时间是十秒；索引b的执行时间也是十秒；主表的执行计划时间是五秒。此时，由于主表代价最小的，p1是有序索引。故保留p1和p3。
如上图所示，做完S跟T，计划连接枚举之后，得出两个计划。分配Group By之后，有四个执行计划。最终，保留代价最小的以及interesting order的计划。所以计划分配的过程是比较有逻辑的。
OceanBase是分布式数据库，其分布式的计划优化没有特别的地方。在分布式场景下，有Partition Wise Join，Partial Partition Wise Join，Hash-Hash Distribution Join，Broadcast Distribution Join等。
如今的分布式场景，不再是给每个算子选择单机算法，而是给每个算子选择分布式算法。所以分布式的计划优化，本质是选择分布式的算子算法。
分布式计划优化的第一阶段，是基于所有表都是本地的假设生成一个最优计划。第二阶段是并行优化, 基于代价来选择算子的分布式算法。
如上图所示，左边是单机算法。在并行优化的过程中，OceanBase把单机算法变成分布式算法，通过分配和选择算子的分布式算法。
二阶段分布式计划优化的优点在于，计划优化复杂性降低。其缺点在于搜索空间变小，计划次优。所以在OceanBase4.0的版本里，两阶段分布式计划变成了一阶段，提升了整个计划的质量。
四、统计信息和代价模型
OceanBase的统计信息包括表级别统计信息，列级别统计信息。目前，开源版本没有直方图统计信息。动态采样，执行反馈会在4.0版本出现，现在正在开发当中。
目前，开源版本的统计信息收集只能通过每日合并。由于它是增量收集，无法改制删除。索引统计信息会随着数据的删除，越来越不准。
在3.2以上的版本，支持自动/手动触发。除了收集统计信息，还有统计信息的管理功能，包括统计信息锁定、导入、导出。
存储层的估行接口实时性很好，通过给定一个索引键值的范围，存储层会返回相对应的行数信息。基线数据按照索引rowkey顺序组织，增的数据是按照索引rowkey以B+树形式组织。
假设基线数据里面有10万行，但在增量数据里，删除了5万行。此时，如果优化器用传统的方式估算，只能得出数据剩下5万行。
为了解决此类问题，OceanBase引入了物理行跟逻辑行。物理行是基线和增量中需要访问的行数，用来计算索引顺序扫描代价。逻辑行是合并之后的行数，用来计算回表代价。
物理行与逻辑行在OceanBase里是如何计算的？增量修改在内存中，通过动态采样进行计算。基线数据在固态盘中，利用元数据计算基线行数。相比传统的代价模型，实时的统计信息通过基线+增量的方式，解决了索引列上谓词依赖关系。
计算一个计划的代价，是通过计算每一个算子的代价，以及每一个算子的输出行长，输出行数。通过础统计信息或直方图，进行动态采样，执行反馈，最终通过选择率计算，估计中间结果行数。
