小蚂蚁说：6月1日-2日，GIAC全球互联网架构大会在深圳华侨城洲际大酒店盛大召开。OceanBase团队资深技术专家柏泽受邀在“金融级核心构架设计专场”发表了《深入解析OceanBase的SQL优化器和分布式并行执行原理》的精彩演讲。本文将带你一起深入了解OceanBase SQL团队在优化器和执行引擎上所做的工作。

本文作者：柏泽

现任蚂蚁金服OceanBase团队资深技术专家，负责OceanBase的并行查询和新一代OLAP引擎。曾就职于美国Oracle公司，负责Oracle数据库并行查询研发工作并有多项专利申请。

//////////

以下为演讲实录：

OceanBase是阿里巴巴蚂蚁金服自研的一个通用分布式关系数据库，它在分布式架构下能够保证金融级的数据一致性和高可用，并且有非常灵活的水平扩展能力和弹性部署能力。它一般是多地、多活、多副本的方案去部署，它现在已经支持了蚂蚁金服百分之百的核心交易系统。去年双十一支持了25.6万笔/秒的交易，4200万条SQL/秒。

OceanBase团队资深技术专家柏泽

今天有个很流行的说法叫做金融级数据库，什么叫做金融级数据库？我们认为所有的金融客户使用的各种金融场景，都能够在这个数据库里得到很好的支持和执行，这就是一个金融级数据库。

对于金融客户的需求场景来说，从最基础的来讲，是要求数据的一致性，可靠性，数据不能出错，数据不能丢失；从进阶的角度来讲，系统要有强大的事务处理能力，具有高并发，高可用，可以方便的进行系统扩展和容灾能力。然而，除了这些以外，还有个很重要的点是OLAP（OnLine Analytic Processing在线分析型查询）的查询支持能力。

不管是从蚂蚁内部的业务场景来看，还是从外部金融客户的行业需求来看，OLAP查询是在金融场景中不可或缺的。从风险防范，模式识别，业务报表，月度结算等等，都需要数据库有能够做OLAP查询的能力。

OLAP查询的概念最早由Ed. Codd在1993年提出来，至今也有20多年的历史，学术界和工业界围绕OLAP查询的场景，也提出了很多的思路和实现方法。大体来看，OLAP查询是对数据库的SQL查询优化器和SQL执行引擎有比较高的要求的，目前在使用的数据库系统中，能够将OLTP事务型查询和OLAP分析型查询都同时支持的比较好的屈指可数。

OceanBase从金融客户的实际需求场景出发，以SQL优化器的代价模型，统计信息收集和查询改写以及SQL执行引擎的并行执行能力为突破口，围绕着OLAP场景的实际需求，做了大量的工作。

OceanBase的SQL引擎架构图

SQL引擎的基本工作就是将每一条用户输入的SQL查询语句通过一系列的语法解析，查询改写，计划代价选择，最终生成一个可以执行的语法树，再经由一定的策略通过SQL引擎执行器执行并最终返回结果给用户的过程。SQL引擎追求的优化目标就是最小化查询计划生成时间和执行时间。OceanBase实现了经典SQL引擎的全部模块，并且在其中创造性的提出了很多新的实现，比如Faster Parser这个快速命中计划缓存的机制等。

OceanBase优化器代价模型基本的经典理论还是基于System R的模型，它会结合OceanBase的数据存储引擎的特点，去考虑代价上的一些特殊性。优化器会做两阶段的优化。

第一阶段是假设所有的关系都是本地的去做一个最优计划，在各种可替代计划当中找出CPU和IO总和开销最小的计划。第二步会进行分布式并行执行优化，并行执行优化除了要考虑CPU和IO，还要考虑网络的开销，考虑采用多线程执行带来的Overhead的开销。

1. 紧密结合LSM-TREE存储的代价模型和统计信息收集

在代价模型对扫描进行代价估计时，不同于单一数据源的存储引擎，OceanBase需要考虑到一行的数据可能同时来自于静态的SSTable和动态的MemTable，每个表每个分区随着动态数据的不同，可能扫描的代价会有差异，我们可以通过一些动态采样的方式来计算不同的扫描代价。在索引回表时，因为是IOT（Index Organized Table）的形式而不是传统常见的堆表，且数据会由负载均衡模块进行动态的迁移，OceanBase的索引中保存的是每行数据的逻辑Rowkey，而不是物理的rowid，这就使得OceanBase的索引回表操作代价会比较高。

对于统计信息的收集，除了传统的平均行长，行数，每列的NDV（Number of Distinct Value），直方图等等之外，OceanBase的存储层会保存SSTable每个block的一些统计信息以及MemTable关于数据修改的一些统计信息，可以方便的给优化器提供一些统计信息的输入。此外，OceanBase还有动态采样的框架，可以对于比如没有统计信息的表，或者较为复杂的有关联性的多列的一些统计信息采集，预估，使用动态采样的方法来获取较好的统计信息预估。

2. 复杂查询的查询改写

查询改写是指通过一定的方式，将SQL语句改换成语法不同但是语意一样的一种SQL查询优化技术，目前OceanBase已经构建了一个完备的基于代价的SQL查询改写框架，可以进行丰富的基于规则的查询改写和部分的基于代价的改写。 OceanBase的查询改写框架如下图所示：

OceanBase的查询改写框架

目前，OceanBase支持的基于规则和基于代价的查询改写列表如下：

基于规则的改写

视图合并

子查询展开

Anti/Semi Join

过滤条件下推， 连接条件下推，等价条件推导

外连接消除

distinct消除

sort/order by 消除

sort方法选择等

基于代价的改写

OR-expansion

Window function

Group by placement（开发中）

连接条件下推(JPPDto view/table) (开发中)

下面各举一例说明查询改写。

例1：规则改写——子查询展开：

如上例所示，如果不做查询改写，则执行计划只能是一个filter计划，对于customer中拿出的每一行，执行子查询，如果有匹配行，则不返回，否则返回，可以看到，子查询会被执行非常多次，计划执行很不高效。在执行查询改写后，通过anti join的方式，不用多次执行orders表的子查询，并且为计划引入了新的优化可能。

 例2：代价改写——OR Expansion：

以上图的两个例子来说，第一个查询，在不采用改写之前，唯一的执行方法就是对t1表做全表扫描并且带上t1.a=1 or t1.b=1这个过滤条件。但是在改写之后，如果在a列或者a，b列上有索引，union all的两个分支可能分别可以采用索引的方式去查询，代价可能会比做全表扫描要好。对于第二个查询，在没做改写之前只能采用nested-loop join的方式去做连接，而改写之后，可以采用hash join，或者merge join等等。

查询改写是一种非常有用的对于复杂SQL提供高效的执行方案的手段，以TPC-H Q17为例，1G schema无并行执行的情况，在OceanBase采用了window function的改写之后，查询时间从原先的3个小时以上跑不出结果到4.9秒出结果。

正是因为OceanBase有一套自主研发的完备的基于代价的SQL优化器，我们才能拥有执行复杂查询，大查询的能力，为金融业务的很多复杂查询场景提供强有力的支撑。

OceanBase是一个分布式的关系数据库系统，在OLAP查询场景下，并行执行的能力对于查询的响应时间（RT）影响很大。OceanBase的SQL引擎实现了一套基于分布式架构的并行执行框架。

1. 并行执行的基本概念

并行执行是一个Divide and Conquer的概念，也就是分治。对于SQL的执行计划来说，我们将整个的计划拆分成为一个个可以独立执行的子计划，通过调度的手段，让有相互依赖的子计划同时采用不同的线程组执行，采用生产者消费者模型，形成局部流水线，充分利用系统的IO和CPU能力，达到降低查询RT快速响应的目的。

同时，在水平层面，在每一个进行基表扫描的子计划中，会通过切分扫描任务的方式，从基表扫描开始，将所有的SQL查询算子都能够并行执行。

以下图的并行执行计划为例，一个两表连接的Hash Join计划被分成了三个子计划，分别做并行左表的扫描，右表的扫描和并行的Hash Join。为此我们需要能支持数据的重分布。

并行执行计划

OceanBase能够提供多种丰富的数据重分布方法，比如Hash, Broadcast, Round Robin, PKEY, Merge SORT等等，会由优化器来决定最好的计划和数据重分布方式。数据在不同线程组之间通过数据传输层（Data Transfer Layer）DTL传输数据，生产者线程在流水线执行中根据不同的数据重分布方法流式的向DTL层写入数据，消费者线程会不停的从DTL层读取数据并进行对应子计划的执行。

2. OceanBase的两级调度

OceanBase采用了一个两级调度的机制，整体的调度模型如下所示：

OceanBase调度模型

主线程负责生成整体的执行计划，并且获得整体的并行度，随后将子计划发送到各个节点执行，同时按照优化器的指示给定每个节点的并行度，各节点的控制线程会负责本节点执行资源的获取和控制调度，各节点独立决定本节点的扫描任务的粒度，保证并发执行的均匀和高效。

以一个30G的分区表分布在3个节点为例，每个节点上的数据都为10G左右，但是第一个节点只有1个分区，其余两个节点均有20个分区，总的执行并行度假定为15，优化器给每个节点的指定并行度很显然为5。

对于有20个分区的节点，扫描粒度可以以分区为单位进行，但是只有一个分区的节点，如果以分区为单位，则5个线程会有4个处于空闲状态，显然不是最优，此时该节点的并行扫描粒度可以以数据块的范围为粒度，将5个线程同时扫描这一个大的分区。

OceanBase的并行执行引擎可以支持所有主要算子的并行执行操作，包括nested loop join, merge join, hash join, aggregation, distinct,group by, window function, count, limit等等。她能够支持丰富的数据重分区方法，从而为优化器的选优提供了更多的可能。

OceanBase的SQL团队通过4年的时间，以关系数据库成熟的理论基础为基石，结合分布式系统架构和LSM-Tree的动静态数据结合的存储引擎特点，从零开始一步一步搭建起了整个的SQL优化器和处理引擎。

我们相信，一个自主研发完全可控的完备的SQL优化器和执行引擎，才可以有能力满足金融客户的复杂查询场景需求，做到真正的具有HTAP的能力，体现出SQL语言的强大查询表达能力，而不再将关系数据库仅仅作为一个分布式的KV系统使用。

OceanBase官网链接：

https://oceanbase.alipay.com/

请将以上网址复制至浏览器中打开即可查看

最后，我们给对 OceanBase 数据库感兴趣的同学准备了微信交流群，你除了在上文的链接中查看OceanBase官网外，你还可以扫描下方二维码联系加群小助手加入OceanBase的技术交流群，来和蚂蚁金服一线OceanBase技术人员还有其他小伙伴们一起讨论交流~！

关注 OceanBase 公众号

蚂蚁金服和阿里巴巴完全自主研发的

金融级分布式关系型数据库

提供最纯粹的数据库知识分享

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。