规则优化与代价优化

查询优化器是数据库管理系统的“大脑”，决定了用户查询的执行路径（Path）。OceanBase 的查询优化是一个规则优化和代价优化相结合的过程，其主体是基于代价（Cost-Based）进行查询优化，并在查询优化过程中通过规则进行启发和剪枝。和某一些商业和开源数据库把规则优化和代价优化分成两个独立的过程不同，OceanBase 的规则优化和代价优化是交织在一起的，在代价优化的各个过程中，都会有一些启发式规则进行辅助，从而大幅提升优化的效率和效果。

代价优化方法是 OceanBase 查询优化器的核心算法。OceanBase 实现了一个分布式数据库系统的代价模型，采用动态规划算法生成搜索空间，为搜索空间的每一条路径估算代价，并最终选取一条代价最低的路径作为执行计划。搜索空间直接决定了查询优化的效果，太大的搜索空间会在查询优化阶段耗费过多的时间，而太小的搜索空间容易丢失最优计划，所以需要在代价优化过程中通过规则进行剪枝。

OceanBase 的规则体系分为前置规则（正向规则）和 Skyline 剪枝规则(反向规则)。前置规则直接决定了一个查询选取什么样的路径，是一个强匹配的规则体系。Skyline剪枝规则会两两比较两个索引，如果一个索引在一些定义的维度上优于(dominate)另外一个索引，那么被dominated的那个索引会被剪掉，最后没有被剪掉的路径会进行代价比较，选出最优的路径。优化器会优先使用前置规则，如果前置规则不能得到一个确定最优的路径，那么优化器会进一步通过 Skyline 剪枝规则剪掉一些路径，最后代价模型会在没有被剪掉的索引中选择代价最低的路径。这一过程生成的计划叫做逻辑计划（LogicalPlan），Logical Plan 也是一个树状结构，描述的查询的执行路径。

并行优化

为了充分利用 OceanBase 的分布式架构和多核计算资源的优势，OceanBase 实现了基于分区的并行查询，而优化器的并行优化能力是并行查询的基础。OceanBase 的查询优化器在生成串行执行计划后会进入并行优化阶段，根据计划树上各个节点的数据分布，对串行执行计划自底向上的分析，进行算子下推、数据重分布、智能连接等，并在计划树嵌入并行化算子，把串行的逻辑执行计划改造成一个可以并行执行的逻辑计划。

并行优化最重要的参考信息是数据的分布信息（Location），即查询所需访问的每个分区的各个副本在集群中的存储位置，这一信息由RS维护，为了提升访问效率 Optimizer 做了缓存机制。

OceanBase 的并行优化过程同样是一个规则和代价相结合的过程，除了明确的并行化规则，还会考虑 CPU、IO 开销，以及网络通讯的开销。

统计信息

统计信息是代价模型准确高效工作的基础，OceanBase 为每个分区维护列级别的统计信息，包括行数、不同值的个数、最大值、最小值等。

OceanBase 在合并的时候收集统计信息，统计信息以普通数据的形式存储在内部表中，通过全局 Schema 对外提供访问。各个节点会在本地维护一个的统计信息缓存，以提高优化器对统计信息的访问速度。