淘宝数据库OceanBase SQL编译器部分源码阅读--生成物理查询计划

浏览数：69 / 时间：2015年06月12日

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继承自该类。
ObNoRowsPhyOperator:无返回列的运算符,如插入运算符ObInsert继承自该类

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

运算符类名	父类	作用
ObFilter	ObSingleChildPhyOperator	选择运算符
ObProject	ObSingleChildPhyOperator	投影运算符
ObGroupBy	ObSingleChildPhyOperator	分组运算符
ObHashGroupBy	ObGroupBy	hash分组运算符
ObInsert	ObSingleChildPhyOperator,ObNoRowsPhyOperator	插入运算符
ObJoin	ObDoubleChildrenPhyOperator	连接运算符
ObLimit	ObSingleChildPhyOperator	限制行数的运算符
ObMergeDistinct	ObSingleChildPhyOperator	归并去重运算符
ObSort	ObSingleChildPhyOperator	排序运算符
ObRpcScan	ObPhyOperator	MS全表扫描
ObSstableScan	ObRowkeyPhyOperator	用于CS从磁盘或缓冲区扫描一个tablet
ObTableScan	ObSingleChildPhyOperator	全表扫描符

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

2.2 物理查询计划的定义

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

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

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

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

转换步骤很简单，添加逻辑计划，生存物理查询计划，示例代码如下：
trans.add_logical_plans(multi_plan);
physical_plan = trans.get_physical_plan(0);

trans是转换类ObTransformer类,该类的功能就是将逻辑计划转换为物理查询计划。

3.1 SQL的语法执行顺序

SQL作为一种声明式语言，它并不关心如何取数这个过程，而是通过SQL语句它声明它所需要的数据，有系统为其挑出符合要求的数据。
之前在讨论逻辑计划时，没有讨论到这一点，但是SQL的语法执行顺序直接影响了计划的生成过程。
SQL的语法顺序和执行顺序并不一致。以下面这条SQL为例：

select student.name,math.score, from student,math where student.sex=‘M‘ order by student.id;

其语法声明顺序为：

SELECT
FROM
WHERE
ORDER BY

但其执行顺序为：

FROM
WHERE
SELECT
ORDER BY

而物理查询计划，显然是以SQL执行顺序为准的。

3.2 OceanBase中生成物理查询计划的系列函数

逻辑计划生成物理查询计划或物理操作符的操作由下面一系列函数完成.

//物理查询计划生成函数
ObPhysicalPlan* ObTransformer::generate_physical_plan(ObLogicalPlan *logical_plan)

//select 语句-->物理查询计划
int64_t ObTransformer::gen_phy_mono_select
//order by -->排序运算符
ObPhyOperator* ObTransformer::gen_phy_order_by
//distinct-->去重运算符
ObPhyOperator* ObTransformer::gen_phy_distinct
//group by-->分组运算符
ObPhyOperator* ObTransformer::gen_phy_group_by
//聚集函数-->聚集运算符
ObPhyOperator* ObTransformer::gen_phy_scalar_aggregate
//表连接运算
int ObTransformer::gen_phy_joins
//from-->多表连接
int ObTransformer::gen_phy_tables
//表-->表扫描查询计划
ObPhyOperator* ObTransformer::gen_phy_table
//select语句-->物理查询计划,调用gen_phy_mono_select完成
ObPhysicalPlan* ObTransformer::gen_physical_select
//delete语句-->物理查询计划
ObPhysicalPlan* ObTransformer::gen_physical_delete
//insert语句-->物理查询计划
ObPhysicalPlan* ObTransformer::gen_physical_insert
//update语句-->物理查询计划
ObPhysicalPlan* ObTransformer::gen_physical_update

0.3中仅支持SELECT语句，其他语句还不支持。其生成逻辑在gen_phy_mono_select中，与SQL的执行顺序一致.

int64_t ObTransformer::gen_phy_mono_select(
    ObLogicalPlan *logical_plan,
    ObPhysicalPlan *physical_plan,
    uint64_t query_id)
{
  //int err = OB_SUCCESS;
  int64_t idx = OB_INVALID_INDEX;
  ObSelectStmt *select_stmt = NULL;
  if (query_id == OB_INVALID_ID)
    select_stmt = dynamic_cast<ObSelectStmt*>(logical_plan->get_main_stmt());
  else
    select_stmt = dynamic_cast<ObSelectStmt*>(logical_plan->get_query(query_id));
  if (!select_stmt)
    return OB_INVALID_INDEX;

  ObSelectStmt::SetOperator set_type = select_stmt->get_set_op();
  if (set_type != ObSelectStmt::NONE)
  {
    //带set 的SELECT语句的物理查询计划生成
  }
  else
  {
    /* 普通Select语句*/

    ObPhyOperator *result_op = NULL;

    // 1. generate physical plan for base-table/outer-join-table/temporary table
    ObList<ObPhyOperator*> phy_table_list;
    ObList<ObBitSet> bitset_list;
    ObList<ObSqlRawExpr*> remainder_cnd_list;
    gen_phy_tables(
        logical_plan,
        select_stmt,
        physical_plan,
        phy_table_list,
        bitset_list,
        remainder_cnd_list);

    // 2. Join all tables
    if (phy_table_list.size() > 1)
      gen_phy_joins(
          logical_plan,
          select_stmt,
          physical_plan,
          phy_table_list,
          bitset_list,
          remainder_cnd_list);
    phy_table_list.pop_front(result_op);

    // 3. add filter(s) to the join-op/table-scan-op result
    if (remainder_cnd_list.size() >= 1)
    {
      ObFilter *filter_op = NULL;
      CREATE_PHY_OPERRATOR(filter_op, ObFilter, physical_plan);
      filter_op->set_child(0, *result_op);
      oceanbase::common::ObList<ObSqlRawExpr*>::iterator cnd_it;
      for (cnd_it = remainder_cnd_list.begin(); cnd_it != remainder_cnd_list.end(); cnd_it++)
      {
        ObSqlExpression filter;
        (*cnd_it)->fill_sql_expression(filter, this, logical_plan, physical_plan);
        filter_op->add_filter(filter);
      }
      result_op = filter_op;
    }

    // 4. generate physical plan for group by/aggregate
    if (select_stmt->get_group_expr_size() > 0)
      result_op = gen_phy_group_by(logical_plan, select_stmt, physical_plan, result_op);
    else if (select_stmt->get_agg_fun_size() > 0)
      result_op = gen_phy_scalar_aggregate(logical_plan, select_stmt, physical_plan, result_op);

    // 5. generate physical plan for having
    if (select_stmt->get_having_expr_size() > 0)
    {
      ObFilter *having_op = NULL;
      CREATE_PHY_OPERRATOR(having_op, ObFilter, physical_plan);
      ObSqlRawExpr *having_expr;
      int32_t num = select_stmt->get_having_expr_size();
      for (int32_t i = 0; i < num; i++)
      {
        having_expr = logical_plan->get_expr(select_stmt->get_having_expr_id(i));
        ObSqlExpression having_filter;
        having_expr->fill_sql_expression(having_filter, this, logical_plan, physical_plan);
        having_op->add_filter(having_filter);
      }
      having_op->set_child(0, *result_op);
      result_op = having_op;
    }

    // 6. generate physical plan for distinct
    if (select_stmt->is_distinct())
      result_op = gen_phy_distinct(logical_plan, select_stmt, physical_plan, result_op);

    // 7. generate physical plan for order by
    if (select_stmt->get_order_item_size() > 0)
      result_op = gen_phy_order_by(logical_plan, select_stmt, physical_plan, result_op);

    // 8. generate physical plan for limit
    if (select_stmt->get_limit() != -1 || select_stmt->get_offset() != 0)
    {
      ObLimit *limit_op = NULL;
      CREATE_PHY_OPERRATOR(limit_op, ObLimit, physical_plan);
      limit_op->set_limit(select_stmt->get_limit(), select_stmt->get_offset());
      limit_op->set_child(0, *result_op);
      result_op = limit_op;
    }

    // 8. generate physical plan for select clause
    if (select_stmt->get_select_item_size() > 0)
    {
      ObProject *project_op = NULL;
      CREATE_PHY_OPERRATOR(project_op, ObProject, physical_plan);
      project_op->set_child(0, *result_op);

      ObSqlRawExpr *select_expr;
      int32_t num = select_stmt->get_select_item_size();
      for (int32_t i = 0; i < num; i++)
      {
        const SelectItem& select_item = select_stmt->get_select_item(i);
        select_expr = logical_plan->get_expr(select_item.expr_id_);
        if (select_item.is_real_alias_)
        {
          ObBinaryRefRawExpr col_raw(OB_INVALID_ID, select_expr->get_column_id(), T_REF_COLUMN);
          ObSqlRawExpr col_sql_raw(*select_expr);
          col_sql_raw.set_expr(&col_raw);
          ObSqlExpression  col_expr;
          col_sql_raw.fill_sql_expression(col_expr);
          project_op ->add_output_column(col_expr);
        }
        else
        {
          ObSqlExpression  col_expr;
          select_expr->fill_sql_expression(col_expr, this, logical_plan, physical_plan);
          project_op ->add_output_column(col_expr);
        }
      }
      result_op = project_op;
    }

    physical_plan->add_phy_query(result_op, idx);
  }

  return idx;
}