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

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;
}

四、 总结

物理查询计划的生成过程比逻辑计划和语法树解析部分更复杂。你需要了解相关的基础知识包括关系代数查询，流水线方式下的运算符构成，SQL语法的执行顺序等。


欢迎光临我的网站----蝴蝶忽然的博客园----人既无名的专栏。
如果阅读本文过程中有任何问题，请联系作者，转载请注明出处！

时间： 2024-10-27 09:23:44

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

淘宝数据库OceanBase SQL编译器部分 源码阅读--生成逻辑计划

淘宝数据库OceanBase SQL编译器部分 源码阅读--生成逻辑计划 SQL编译解析三部曲分为:构建语法树,生成逻辑计划,指定物理执行计划.第一步骤,在我的上一篇博客淘宝数据库OceanBase SQL编译器部分 源码阅读--解析SQL语法树里做了介绍,这篇博客主要研究第二步,生成逻辑计划. 一. 什么是逻辑计划? 我们已经知道,语法树就是一个树状的结构组织,每个节点代表一种类型的语法含义.如 update student set sex="M" where name ="

淘宝数据库OceanBase SQL编译器部分 源码阅读--Schema模式

淘宝数据库OceanBase SQL编译器部分 源码阅读--Schema模式 什么是Database,什么是Schema,什么是Table,什么是列,什么是行,什么是User?我们可以可以把Database看作是一个大仓库,仓库分了很多很多的房间,Schema就是其中的房间,一个Schema代表一个房间,Table可以看作是每个Schema中的柜子,行和列就是柜子中的格子.User就是房间的主人.简单来说,Schema是包括表,列,索引,视图等数据库对象的集合. OceanBase中的强Sche

淘宝数据库OceanBase SQL编译器部分 源码阅读--解析SQL语法树

OceanBase是阿里巴巴集团自主研发的可扩展的关系型数据库,实现了跨行跨表的事务,支持数千亿条记录.数百TB数据上的SQL操作.在阿里巴巴集团下,OceanBase数据库支持了多个重要业务的数据存储,包括收藏夹.直通车报表.天猫评价等.截止到2013年4月份,OceanBase线上业务的数据量已经超过一千亿条. 看起来挺厉害的,今天我们来研究下它的源代码.关于OceanBase的架构描述有很多文档,这篇笔记也不打算涉及这些东西,只讨论OceanBase的SQL编译部分的代码. OceanBa

ASP.Net C#2.0全能数据库组件 (含下载实例源码地址)

asp.net|数据|数据库|下载 /* ?--------------------------?   | Title: ASP.Net C#2.0全能数据库组件 (开源含实例源码)|   | Project: DBOperatorService.Data                    |   | Subarea: DataSet                                   |   | Author: ξ箫音ξ                           

写一个mysql数据库的sql 递归查询，我现在有个能查询三级的，谁能帮我改为查询四级或五级的

问题描述 select distinct * from (select * from news_types where news_types.id=1 union select n2.* from news_types n1,news_types n2 where n1.id=1 and n2.parentid=n1.id union select n3.* from news_types n3,( select n2.* from news_types n1,news_types n2 whe

CI框架源码阅读笔记2 一切的入口 index.php

上一节(CI框架源码阅读笔记1 - 环境准备.基本术语和框架流程)中,我们提到了CI框架的基本流程,这里再次贴出流程图,以备参考: 作为CI框架的入口文件,源码阅读,自然由此开始.在源码阅读的过程中,我们并不会逐行进行解释,而只解释核心的功能和实现. 1. 设置应用程序环境 define("ENVIRONMENT", "development"); 这里的development可以是任何你喜欢的环境名称(比如dev,再如test),相对应的,你要在下面的switch

Apache Storm源码阅读笔记&amp;OLAP在大数据时代的挑战

 <一>Apache Storm源码阅读笔记 楔子 自从建了Spark交流的QQ群之后,热情加入的同学不少,大家不仅对Spark很热衷对于Storm也是充满好奇.大家都提到一个问题就是有关storm内部实现机理的资料比较少,理解起来非常费劲. 尽管自己也陆续对storm的源码走读发表了一些博文,当时写的时候比较匆忙,有时候衔接的不是太好,此番做了一些整理,主要是针对TridentTopology部分,修改过的内容采用pdf格式发布,方便打印. 文章中有些内容的理解得益于徐明明和fxjwind两

php中get_adjacent_post函数PHP源码阅读笔记

这个函数是wordpress里的一个函数,作用是获取相邻的POST文章. 函数并不大,有效代码大概只有70行左右,但是里面包含的知识不少,所以专门用一篇文章来解释一下. get_adjacent_post函数的源码位于wp-includes/link-template.php中. 我会通过"//roc:"在引出源码阅读笔记. /**  * Retrieve adjacent post.  *  * Can either be next or previous post.  *  * @

Flume-NG源码阅读：HBaseSink

关于HBase的sink的所有内容均在org.apache.flume.sink.hbase包下. 每个sink包括自己定制的,都extends AbstractSink implements Configurable. 一.首先是configure(Context context)方法.该方法是对HBaseSink的参数初始化.主要包括以下几个: tableName:要写入的HBase数据表名,不能为空: columnFamily:数据表对应的列簇名,这个sink目前只支持一个列簇,不能为空: