|
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个步骤：
初始化
解析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) |
执行物理计划：
初始化仅仅是初始化一个缓冲区，可以略过来研究后面关键的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
|--Table:student
|--TargeList:
|--sex = "M"
|--Qualifications:
|--name="小明" |
语法解析的作用就是如何用数据结构来表示上面这棵语法树。不同的数据库有不同的方案。为加强对比，我选取了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
|--type: T_UpdateStmt
|--relation: student
|--targetList:
|--targest[0]:
|--name: sex
|--val: "M"
|--whereClause：
|--expr: =
|--left: name
|--right: "小明" |
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:
|--kind: N_UPDATE
|--u:UPDATE
|--relname: student
|--relattr:
|--kind: N_RELATTR
|--u:RELATTR
|--relname: (null)
|--attrname: sex
|--relorvalue:
|--kind: N_RELATTR_OR_VALUE
|--u:RELATTR_OR_VALUE
|--relattr: (null)
|--value:
|--kind:N_VALUE
|--u:VALUE
|--sval = "M"
|--conditionlist:
|--kind:N_LIST
|--u: LIST
|--next: (null)
|--curr:
|--kind: N_CONDITION
|--u: CONDITION
|--lhsRelattr:
|--kind: N_RELATTR
|--u:RELATTR
|--relname: (null)
|--attrname: name
|--op:
|--kind: N_EQ
|--rhsRelattr:(null)
|--rhsValue:
|--kind:N_VALUE
|--u:VALUE
|--sval = "M"
|
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
|--type: T_UPDATE
|--num_child: 3
|--children[0]:
|--type: T_IDENT
|--str_value: student
|--children[1]:
|--type: T_ASSIGN_LIST
|--num_child:1
|--children[0]:
|--type: T_ASSIGN_ITEM
|--children[0]:
|--type: T_IDENT
|--str_value: sex
|children[1]:
|--type: T_EXPR
|--children[0]:
|--type: T_STRING
|--str_value: "M"
|--children[2]:
|--type: T_OP_EQ
|--num_child: 2
|--children[0]:
|--type: T_IDENT
|--str_value: name
|--children[1]:
|--type: T_IDENT
|--str_value: "小明" |
OceanBase中采用的这种方式缺点很明显，就是使用这些结构体时必须要仔细辨别各个子节点代表的意义，否则容易出错。优点同样也很明显，可以非常灵活的构建出语法树。
语法树的节点的设计，主要是为了解决如何表达语法结构。不同的数据库有不同的具体实现。OceanBase采用终止符和非终止符分类，使用OceanBase的设计极具灵活性，但使用时需要仔细验证，避免出错。
|
