淘宝数据库OceanBaseSQL编译器部分源码阅读--生成物理查询计划(一)

SQL编译解析三部曲分为：构建语法树，制定逻辑计划，生成物理执行计划。前两个步骤请参见我的博客<<淘宝数据库OceanBase SQL编译器部分 源码阅读--解析SQL语法树>>和<<淘宝数据库OceanBase SQL编译器部分 源码阅读--生成逻辑计划>>.这篇博客主要研究第三步，生成物理查询计划。

一、 什么是物理查询计划

与之前的阅读方法一致，这篇博客的两个主要问题是what 和how。那么什么是物理查询计划？物理查询计划能够直接执行并返回数据结果数据。它包含了一系列的基本操作，比如选择，投影，聚集，排序等。因此，本质上，物理查询计划是一系列数据操作的有序集合。为了更好的研究关系数据的操作，有人提出了关系代数模型。而物理查询计划的基本原理就来自于关系代数模型。

1.1 关系代数

在《数据库系统原理及应用》等很多数据库相关书籍中都提到了关系代数。关系代数是SQL查询的理论支撑。
关系代数有六个原始元算符：“选择”、“投影”、笛卡尔积（也叫做“叉积”或“交叉连接”）、并集、差集和“重命名”。这些运算符作用于一个或多个关系上来生成一个新的关系。

• 选择(Selection) :在关系R中选择满足给定条件的诸元组。SQL 语句中的where子句就是该运算的最佳代表。
• 投影(Projection):从R中选择出若干属性列组成新的关系。SQL中Select 的列表时该运算的代表
• 连接(Join):连接也称为θ连接。它是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。连接运算中有两种最为重要也最为常用的连接，一种是等值连接（equi-join），另一种是自然连接（Natural join）。 自然连接（Natural join）是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。
• 重命名：它被简单的用来重命名关系的属性或关系自身。如SQL语句中的alias。
• 并集：是两个关系所有元组的集合
• 差集: A-B表示属于A但不属于B的元组集合
• 并集和差集的定义在数学中的定义基本相同。

1.2 流水线

如下面这条SQL：

select id,name,sex from student where sex='M' order by id;

执行这条SQL会用到多个操作符，如选择、投影、排序等。一种方法是以一定的顺序每次执行一个操作，每次计算的结果被实体化到一个临时关系中以备后用。实体化计算的代价包括所有运算的代价和把中间结果写回磁盘的代价。其中磁盘I/O的代价很高。
另一种方法是在流水线上同时执行多个运算，一个运算结果传递给下一个，而不必保存到临时关系中。在实现中，每个运算符有3个迭代函数：open,close,get_next。
open和close分别为打开一个运算符，关闭一个运算符。get_next函数用于获取一行元组。

二、 OceanBase中的物理查询计划

2.1 物理操作符

在0.3版本OceanBase中，物理上运算符接口为 ObPhyOperator。其定义如下：

/// 物理运算符接口
    class ObPhyOperator
    {
      public:
        /// 打开物理运算符。申请资源，打开子运算符等。构造row description
        virtual int open() = 0;

        /// 关闭物理运算符。释放资源，关闭子运算符等。
        virtual int close() = 0;

        /// 获得下一行的引用
        virtual int get_next_row(const common::ObRow *&row) = 0;
    };

ObPhyOperator定义了open,close,get_next_row 3个函数用于实现运算符的流水化操作。并根据子节点的个数定义了几种类型的运算符，它们都继承自ObPhyOperator.

• ObNoChildrenPhyOperator:无子节点的运算符
• ObSingleChildPhyOperator:只有一个子节点的运算符
• ObDoubleChildrenPhyOperator：有两个子节点的运算符
• ObMultiChildrenPhyOperator:有多个子节点的运算符（0.4版本才出现的）
  此外还有:
• ObRowkeyPhyOperator:(不是很清楚,自我觉得是)带返回RowKey的运算符,也就是返回的时候不是返回Row，而是返回RowKey。 磁盘表扫描运算符ObSstableScan继承自该类。

以上几个运算符依然是接口部分，真正使用时的运算符如同在关系代数中所说的一般，但SQL语句并不是完全的关系代数运算，为了方便实现时都会定义更多的运算符。
以下是0.3版本时的部分运算符及继承关系摘录：

实际上还有很多运算符，这里没有一一列举，而且在后来的版本里还会有更多的运算符会被添加进来。
这些运算符是物理查询计划的主要构成。

2.2 物理查询计划的定义

物理查询计划由一系列运算符构成。OceanBase中物理查询计划ObPhysicalPlan定义如下：

class ObPhysicalPlan
    {
        /*省略其他方法*/
      private:
        oceanbase::common::ObArray phy_querys_;
        oceanbase::common::ObArray operators_store_;
    };

与逻辑计划类似,operators_store_用于存储查询计划中使用到的所有运算符。在逻辑计划中我们已经知道，一个查询计划会有多个查询实例，在物理查询计划ObPhysicalPlan中与之对应的是 phy_querys_ 保存每个查询实例的第一个运算符。

三、 从逻辑计划如何生成物理查询计划

转换步骤很简单，添加逻辑计划，生存物理查询计划，示例代码如下：
trans.add_logical_pla