OceanBase是阿里巴巴集团自主研发的可扩展的关系型数据库，实现了跨行跨表的事务，支持数千亿条记录、数百TB数据上的SQL操作。在阿里巴巴集团下，OceanBase数据库支持了多个重要业务的数据存储，包括收藏夹、直通车报表、天猫评价等。截止到2013年4月份，OceanBase线上业务的数据量已经超过一千亿条。

看起来挺厉害的,今天我们来研究下它的源代码。关于OceanBase的架构描述有很多文档，这篇笔记也不打算涉及这些东西，只讨论OceanBase的SQL编译部分的代码。

OceanBase是一个开源的数据库,托管在github上,点击下载。本文讨论的源码路径对应为：oceanbase_0.3/src/sql。最新的版本为0.4，本文讨论的代码基于0.3版本的OceanBase.目前OceanBase的能解析的SQL还比较少，包括Select,Insert,Update,Delete,Show,Explain等.

选择OceanBase 0.3 版本进行学习，基于几个原因：

1.OceanBase 的高质量，高可读性

2.OceanBase 版本低，没有历史负担

3.OceanBase SQL解析相对简单，更容易窥见全貌，利于理解设计开发中要解决的主要问题。

4.与其他数据库的SQL解析部分进行对比，深入理解问题本质

该部分主要功能包括了，SQL语句解析，逻辑计划的生成，物理操作符运算等。

入口：ObSql类

本部分的入口函数在ob_sql.h中,调用函数ObSql::direct_execute可以直接执行SQL语句,并返回结果集ObResultSet。函数stmt_prepare用于解析要预编译的SQL语句,stmt_execute则用于执行Prepare过的SQL语句。

class ObSql  
   {  
     public:  
       ObSql(){}  
       ~ObSql(){}  
       int direct_execute(const common::ObString &stmt, ObResultSet &result)  
       int stmt_prepare(const common::ObString &stmt, ObStmtPrepareResult &result);  
       int stmt_execute(const uint64_t stmt_id, const common::ObArray<common::ObObj> params, ObResultSet &result);  
       int stmt_close(const uint64_t stmt_id);  
   };  

在0.4版本中，direct_execute,stmt_prepare,stmt_execute等函数都被声明为static函数,意味着调用SQL语句执行时可以直接ObSql::direct_execute可以执行SQL语句，而不必再先定义一个ObSql对象。OceanBase还有年轻，还存在不足，我们阅读源码时应该带着批判思考的精神。

直接进入direct_execute函数，可以看到整个执行的过程,函数中有很多的if,else语句，主要是因为OceanBase有一个编码规范要求：一个函数只能有一个返回出口.按单出口的规范写代码会使得写代码的思路非常清晰，不容易出现内存泄露等问题，在大型项目中还是应该尽量保持函数单出口.当然，我觉得保持一个函数功能简洁、简单易懂也是非常重要的。

在你阅读源码的过程中，遇到的大部分函数都会是这个样.刨去其他干扰信息，结合注释，可以看到，SQL执行分为5个步骤：

初始化

parse_init(&parse_res)

解析SQL语法树

parse_sql(&parse_res, stmt.ptr(), static_cast<size_t>(stmt.length()));

制定逻辑计划

resolve(&logical_plan, parse_res.result_tree_)
ObMultiPlan* multi_plan = static_cast<ObMultiPlan*>(logical_plan.plan_tree_);

生成物理计划：

trans.add_logical_plans(multi_plan);
physical_plan = trans.get_physical_plan(0)

执行物理计划：

exec_plan->open()

初始化仅仅是初始化一个缓冲区，可以略过来研究后面关键的4步。

解析SQL语法树

像PostgreSQL,MySQl等一样,OceanBase采用lex和yacc系的词法和语法解析工具生成语法树。GNU下的词法和语法工具为Flex和Bison.Flex利用正则表达式识别SQL语句中的所有词语，Bison则根据类似BNF的语法规则识别SQL语义，从而构建语法树。不熟悉Flex与Bison的同学推荐阅读《FLEX与BISON》(貌似我也没找到其他类似的书籍,^_^)，里面也有专门的一章讲述利用Flex与Bison实现一个简单的SQL分析器。

OceanBase的SQL语法树与PostgreSQL更为相似，但是设计上也有很多区别。

节点设计

语法树由一系列的节点串连而成。我选取较为简单的Update语句作为示例，下面是一个例句：

Update student set sex="M" where name="小明";

其SQL语法树可以表示为：

|--Update Stmt

语法解析的作用就是如何用数据结构来表示上面这棵语法树。不同的数据库有不同的方案。为加强对比，我选取了PostgreSQL,RedBase与OceanBase作为参照。

PostgreSQL语法树的节点设计

PostgreSQL中每一种语法都会有一个对应的结构体，比如更新语句Update对应的结构体为UpdateStmt:

typedef struct UpdateStmt  
  
  NodeTag        type;           /* 枚举类型 */  
  RangeVar   *relation;        /* 要更新的关系 */  
  List       *targetList;        /* 要更新的项 */  
  Node       *whereClause;    /* 更新条件 */  
  List       *fromClause;        /* optional from clause for more tables */  
  List       *returningList;    /* 返回的表达式列表 */  
  WithClause *withClause;        /* WITH clause */  
UpdateStmt;  

其中type是个枚举值,表示结构体的类型,在UpdateStmt中为T_UpdateStmt。其他字段分别对应UPdate语句的各个部分，该结构体可以支持更复杂的Update语句。

PostgreSQL中还有一个基础的结构体：

typedef struct Node  
{  
    NodeTag        type;  
} Node;  

用于语法解析的结构体都可以强制转换成Node * 类型。PostgreSQL中传递语法结构体是都会转化成Node *类型，只有在需要明确类型的时候根据type枚举值转换成需要的类型。Node *的作用有的类似于void * ,但是更利于调试。我们也可以简单的认为：诸如UpdateStmt的语法解析结构体们都继承自Node。

由于每个语法对应一个结构体，因此在PostgreSQL中存在很多类似的结构体，包括SelectStmt,InsertStmt,DeleteStmt等。最终这些结构体还会被统一转换成Query结构体。即Query是统一的语法树结构体。

在PostgreSQL中，示例中的SQL语法树可表示为：

|--UpdateStmt

RedBase的语法树的节点设计

RedBase是斯坦福的数据库系统实现这门课程(cs346)的一个项目。RedBase比起PostgreSQL,OceanBase这样的复杂数据库而言，十分的简单。但是其语法树的节点设计与其他数据库不同，因此提出来做对比。

typedef struct node{  
   NODEKIND kind;/*枚举类型*/  
  
   union{  
      /* SM component nodes */  
      /* create table node */  
      struct{  
         char *relname;  
         struct node *attrlist;  
      } CREATETABLE;  
  
     /*此处省略n多个结构体...*/  
  
      /* QL component nodes */  
      /* query node */  
      ...  
  
      /* update node */  
      struct{  
         char *relname;                 /* 关系名 */  
         struct node *relattr;          /* 属性 */  
         struct node *relorvalue;       /* 修改后值 */  
         struct node *conditionlist;    /* 条件列表 */  
      } UPDATE;  
  
     /*此处省略n多个结构体...*/  
   } u;  
} NODE;  

RedBase数据库的语法树结构体只有一个，就是NODE,但是这个NODE结构体的声明有150多行(^-^).NODE包括一个枚举类型,作用于PostgreSQL中的type一样。所有的语法结构如UPDATE,SELECT,CREATETABLE等构成巨大的联合体。针对Update语句的结构体包括了关系名,属性,修改后的值,条件列表等字段，显然这种设计只能支持简单的Update语句。

RedBase采用“巨型”联合体取代PostgreSQL中的多个结构体，免去了类型转换（语法结构体到Node*的转换）。如果把PostgreSQL语法树节点看成是“继承”结构，那么RedBase的语法树节点可以看成是“组合”结构。

在RedBase中，示例中的SQL语法树可表示为：

|--NODE:

OceanBase的语法树的节点设计

OceanBase 的语法树节点结构体也只有一个,该结构体包括一个枚举类型变量type_,和PostgreSQL与RedBase一样，代表该结构体对应的类型。还有两组属性，对应终止符节点,只能使用vakue_和str_value_两个字段，分别对应64位整形值和字符串值；非终止符节点使用最后两个字段,num_child_表示子节点的个数,children_指向子节点数组的首地址。

typedef struct _ParseNode  
{  
  ObItemType   type_;  
  
  /* 终止符节点的真实的值 */  
  int64_t      value_;  
  const char*  str_value_;  
  
  /* 非终止符节点的孩子节点*/  
  int32_t      num_child_; /*孩子节点的个数*/  
  struct _ParseNode** children_;   
  
  // BuildPlanFunc m_fnBuildPlan;  
} ParseNode; 

对应一个节点而言，要么是终止符节点要么是非终止符节点，它只会使用两组属性中的一组。int,long,float,double,string等都是终止符类型，可以看出int,long都是用64位整形int64表示。float,double,string则用char *字符串表示。终止符的num_child_为0,children_为null.

PostgreSQL的子节点都是有名字的子节点，可以使用名字进行访问，如在PostgreSQL中，Update语句的where条件可以通过 updatestmt.whereClause 来访问 。 但在OceanBase中不行 ， 所有的子节点都是匿名的 ， 只能通过下标来访问。

打个比方，在PostgreSQL和RedBase中，孩子是有名字的，可以叫小明、小红等，根据名字你大概可以知道这个孩子是男是女；但是在OceanBase家，他们分别叫老大，老二，老三，听名字完全听不出是男是女的。OceanBase家有点不讲究^-^。

可以在运行时查看语法树的结构，也可以在代码中可以推各个子节点代表的类型，但是不如PostgreSQL和RedBase方便。在sql_parser.y文件中，定义了SQL的语法规则，同时也规定了各种类型的子节点的结构。

update_stmt:   
    UPDATE relation_factor SET update_asgn_list opt_where  
    {  
      ParseNode* assign_list = merge_tree(result->malloc_pool_, T_ASSIGN_LIST, $4);  
      $$ = new_non_terminal_node(result->malloc_pool_, T_UPDATE, 3, $2, assign_list, $5);  
    }  
  ;  

从上述代码可以看出，Update语法结构体中有3个子节点，第一个表示表名，第二个表示要更新列表项，第三个表示更新的条件语句。

示例中的Update语句在OceanBase中可以表示为如下形式：

|--ParseNode

OceanBase中采用的这种方式缺点很明显，就是使用这些结构体时必须要仔细辨别各个子节点代表的意义，否则容易出错。优点同样也很明显，可以非常灵活的构建出语法树。

语法树的节点的设计，主要是为了解决如何表达语法结构。不同的数据库有不同的具体实现。OceanBase采用终止符和非终止符分类，使用OceanBase的设计极具灵活性，但使用时需要仔细验证，避免出错。