淘寶數據庫OceanBase SQL編譯器部分 源碼閱讀--解析SQL語法樹

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 版本進行學習，基於幾個原因：

• OceanBase 的高質量，高可讀性
• OceanBase 版本低，沒有曆史負擔
• OceanBase SQL解析相對簡單，更容易窺見全貌，利於理解設計開發中要解決的主要問題。
• 與其他數據庫的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個步驟：

1. 初始化
   parse_init(&parse_res)
2. 解析SQL語法樹
   parse_sql(&parse_res, stmt.ptr(), static_cast<size_t>(stmt.length()));
3. 製定邏輯計劃
   resolve(&logical_plan, parse_res.result_tree_)
ObMultiPlan* multi_plan = static_cast<ObMultiPlan*>(logical_plan.plan_tree_);
4. 生成物理計劃：
   trans.add_logical_plans(multi_plan);
physical_plan = trans.get_physical_plan(0)
5. 執行物理計劃：
   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
|--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的設計極具靈活性，但使用時需要仔細驗證，避免出錯。

構建語法樹

SQL的語法規則很多 ， SELECT , INSERT , UPDATE , DELETE , CREATE TABLE 等 dml , ddl 等語句都有對應的語法樹。在上一節節中我們已經看到了UPDATE語句在內存中的語法樹形狀。本節需要些Flex和Bison的基礎知識，如果之前沒有接觸過Flex與Bison的話，可以閱讀《Flex與Bison中文版》或者GNU Bison 2.1 中文手冊。
SQL全稱為結構化查詢語言，有獨立於各數據庫廠家的SQL標準，各數據庫基本上都會大體上遵循該標準。像PostgreSQL數據庫兼容某些版本的SQL標準，同時也有些自己獨有的語句。每個數據庫都有自己的擅長之處，這些細微的區別有時候就體現在查詢語言的細微區別上。OceanBase在0.3版本僅支持有限的幾條SQL語句，按照其官方的介紹，其目標之一是兼容MySQL的語法，讓我們拭目以待。

詞法分析

利用Flex進行詞法分析是構建語法樹的第一個。Flex源文件包含3部分:選項定義、詞法規則、代碼部分。選項定義部分定義了該詞法分析器使用的特性和一些自定義的函數。詞法規則部分為匹配語法+匹配動作。匹配語法為正則表達式，flex從上往下按順序對每個規則進行匹配，一旦匹配成功則執行該項後麵大括號內對應的動作代碼;代碼部分則是C語言代碼。

OceanBase的詞法文件為sql_parser.l。其中定義了一些函數，選取部分來看。

下麵這兩個函數可以使得OceanBase支持轉義字符，包括：\b,\f,\n,\r,\t.

inline unsigned char escaped_char(unsigned char c);

/* quote_type: 0 - single quotes; 1 - double quotation marks */
int64_t parse_string(const char* src, char* dest, int64_t len, int quote_type);

OceanBase中的字符串用雙引號括起來的表示，而且需要進行轉義處理。

\"(\\.|\"\"|[^"\\\n])*\" {
  ParseNode* node = NULL;
  malloc_new_node(node, ((ParseResult*)yyextra)->malloc_pool_, T_IDENT, 0);
  yylval->node = node;
  char* src = yytext+1;
  int len = strlen(src) - 1; //remove last quote charactor
  char* dest = (char*) parse_malloc(len + 1, ((ParseResult*)yyextra)->malloc_pool_);
  check_value(dest);
  node->str_value_ = dest;
  node->value_ = parse_string(src, dest, len, 1);/*字符串轉義處理*/
  return NAME;
}

當匹配到NULL時，返回的值類型不能為NULL，因為NULL是c語言的保留字，所以需要換成其他名字，此處將NULL的類型定義為NULLX。

NULL   {
  /* yylval->node = new_node(((ParseResult*)yyextra)->malloc_pool_, T_NULL, 0); */
  malloc_new_node(yylval->node, ((ParseResult*)yyextra)->malloc_pool_, T_NULL, 0);
  return NULLX;
}

再來看關係符號的規則代碼，每個符號分別返回一個值。

"||" {return CNNOP;}
"=" {return COMP_EQ;}
">=" {return COMP_GE;}
">" {return COMP_GT;}
"<=" {return COMP_LE;}
"<" {return COMP_LT;}
"!="|"<>" {return COMP_NE;}

在《Flex與Bison》一書中，作者讓所有關係符號返回同一個值，通過yylval的成員值來標記不同符號。代碼類型如下這段。

"=" { yylval.subtok = EXPR_EQ; return COMPARISON; }
"<=>"   { yylval.subtok = EXPR_COMP; return COMPARISON; }
">="    { yylval.subtok = EXPR_GE; return COMPARISON; }
">" { yylval.subtok = EXPR_GT; return COMPARISON; }
"<="    { yylval.subtok = EXPR_LE; return COMPARISON; }
"<" { yylval.subtok = EXPR_LT; return COMPARISON; }
"!="    |
"<>"    { yylval.subtok = EXPR_NE; return COMPARISON; }

雖然都能完成相同的功能，但是從個人喜好來講，我更喜歡OceanBase這種做法，因為夠直接。

整數的值保留在node->value_中返回，為long long 類型 （ 64位 ） 。 而浮點數的值字麵值則保存在node->str_value_ 中。

接下來，看日期時間的提取。

Date{whitespace}?'[0-9]{4}(-[0-9]{2}){2}' {
  int year, month, day;
  struct  tm time;
  int ret = 0;

  /* ParseNode* node = new_node(((ParseResult*)yyextra)->malloc_pool_, T_DATE, 0); */
  ParseNode* node = NULL;
  malloc_new_node(node, ((ParseResult*)yyextra)->malloc_pool_, T_DATE, 0);
  char* dest = strchr(yytext, '\'');
  dest =  parse_strdup(dest + 1, ((ParseResult*)yyextra)->malloc_pool_); // skip left quote
  check_value(dest);
  size_t len = strlen(dest);
  dest[len - 1] = '\0'; //remove final '

  node->str_value_ = dest;//字麵值

  ret = sscanf(dest, "%4d-%2d-%2d", &year, &month, &day);
  assert(ret == 3);

  memset(&time, 0, sizeof(struct tm));
  time.tm_year = year - 1900;
  time.tm_mon = month - 1;
  time.tm_mday = day;
  time.tm_hour = 0;
  time.tm_min = 0;
  time.tm_sec = 0;
  time.tm_isdst = -1;

  node->value_ = mktime(&time) * 1000000L;//轉成微秒
  yylval->node = node;
  return DATE_VALUE;
}

從表達式中可以看到，OceanBase支持直接傳入日期時間，OceanBase也支持Time和Timestamp類型。具體如下表：

如下是一個使用日期的示例：

select id,name from student where createtime <= date '2014-09-12';

語法樹中存在日期類型的節點,其str_value_存儲時間的字麵值，value_存儲該時間與基準時間（1970年1月1日0時0分0秒）之差的毫秒值。

OceanBase通過拓展標準的SQL語法支持直接在SQL語句中寫入時間 ,在詞法分析階段就識別到時間類型，而 PostgreSQL 是在語法分析階段才會識別時間 。 相比而言 ， OceanBase 這種方式更直觀，方便。

在0.4版本的OceanBase中，增加了預編譯的功能，需要識別占位符"?",係統變量和用戶變量。對應性質如下：

語法分析

OceanBase的SQL語法文件為sql_parser.y。.y語法文件最終由Bison轉為可編譯的.c文件。其結構與Flex的.l文件類似，分為選項部分，規則部分和代碼部分。下麵的代碼都是去掉了關聯的動作代碼的規則語法，這樣有助於更專注的理解語法的實現。

select語法

在SQL的語句語法中，最複雜的語法莫過於Select語句。我們先來看其在OceanBase中的語法。一個select語句可以使帶括號的select語句，也可以使不帶括號的select語句：

select_stmt: 
    select_no_parens    %prec UMINUS    /* 不到括號的select語句 */
  | select_with_parens    %prec UMINUS  /* 帶括號的select語句 */
  ;

%prec用於交換左右兩個標記的優先級和結合性。即select_no_parens與UMINUS互換優先級和結核性，select_with_parens 與UMINUS互換優先級和結核性。UMINUS的定義為%right UMINUS。所有上麵兩句的結果是select_no_parens和select_with_parens都變成了右結合。

帶括號的select語句可以是隻帶一個括號，也可以帶多對括號：

select_with_parens:
    '(' select_no_parens ')'      /*隻帶一個括號*/
  | '(' select_with_parens ')'    /*帶多對括號*/
  ;

不帶括號的select語句包括簡單的select，帶order by排序，帶order by排序和limit限製的select語句3種：

select_no_parens:
    simple_select              
  | select_clause order_by
  | select_clause opt_order_by select_limit
  ;

select子句包括簡單slect和帶括號的select：

select_clause:
    simple_select                 
  | select_with_parens           
  ;

為什麼不包括不帶括號的select,暫時沒想通。

簡單select語句包括我們常見的select 語句，但沒有order by和limit選項;同時還包括UNION,INTERSECT,EXCEPT三種運算：

simple_select: 
    SELECT opt_distinct select_expr_list 
    FROM from_list
    opt_where opt_groupby opt_having
  | select_clause UNION opt_distinct select_clause
  | select_clause INTERSECT opt_distinct select_clause
  | select_clause EXCEPT opt_distinct select_clause
  ;

select語句的定義相對其他語句很複雜，而且上麵這段代碼還沒有包括無表的select和for update的select。(這兩項在0.4版本的OceanBase中已經實現)。

下麵這段是從PostgreSQL9.2.3中截取的Select語法：

SelectStmt: select_no_parens      %prec UMINUS
      | select_with_parens    %prec UMINUS
    ;

select_with_parens:
      '(' select_no_parens ')'       
      | '(' select_with_parens ')'   
    ;
select_no_parens:
      simple_select           
      | select_clause sort_clause
      | select_clause opt_sort_clause for_locking_clause opt_select_limit
      | select_clause opt_sort_clause select_limit opt_for_locking_clause
      | with_clause select_clause
      | with_clause select_clause sort_clause
      | with_clause select_clause opt_sort_clause for_locking_clause opt_select_limit
      | with_clause select_clause opt_sort_clause select_limit opt_for_locking_clause
    ;

select_clause:
      simple_select             
      | select_with_parens      
    ;
simple_select:
      SELECT opt_distinct target_list
      into_clause from_clause where_clause
      group_clause having_clause window_clause
      | values_clause             
      | TABLE relation_expr
      | select_clause UNION opt_all select_clause
      | select_clause INTERSECT opt_all select_clause
      | select_clause EXCEPT opt_all select_clause
    ;

不知道你是不是有種似曾相識的感覺。沒錯，在這裏，OceanBase借鑒了PostgreSQL的語法分析方式。PostgreSQL號稱世界上最優秀的開源數據庫，絕非浪得虛名。

update語法

為保證示例的完整性，我們在來分析下update的語法。

/*0.3版本的OceanBase*/
update_stmt: 
    UPDATE relation_factor SET update_asgn_list opt_where
  ;

update_asgn_list: 
    update_asgn_factor
  | update_asgn_list ',' update_asgn_factor
  ;

update_asgn_factor:
    NAME COMP_EQ expr
  ;

上麵為0.3版本中的update的語法，支持常見的update的SQL語句，如果將它和0.4版本的update的語法相比，就會發現：0.4版本的update在set時可以使用保留關鍵字作為列名，支持hint語法,支持when子句。隨著OceanBase逐漸完善，其解析的語法也必然會越來越複雜。在學習的時候，從一個簡單的版本開始，由易到難，就顯得很重要。

/*0.4版本的OceanBase*/
update_stmt:
    UPDATE opt_hint relation_factor SET update_asgn_list opt_where opt_when
  ;
update_asgn_factor:
    column_name COMP_EQ expr
  ;
column_name:
    NAME
  | unreserved_keyword
  ;
opt_when:
    /* EMPTY */
  | WHEN expr
  ;

除了select，比較複雜還有create table,alter table,expr等。本節最後隻討論表達式的語法問題。其他的不再討論。

表達式語法

expression 是指表達列名或者是一個能夠給出真假的布爾表達式。如
a+3 > b
a is not null
等等。表達式最常出現在where子句中，用於過濾數據行。

表達式的語法之所以複雜，是因為表達式可以嵌套多個子表達式，多個子表達式出現後可能會出現語法上的歧義。BETWEEN ... AND 用於測試給的表達式是否在給定的範圍內，這個操作符中的AND 與邏輯與的AND有歧義。需要使用%prec來改變其優先級和結合性，該方法能奏效，但是PostgreSQL和OceanBase都選擇從語法樹規則上完全消除該歧義。

OceanBase中表達式有3種類型，分別為expr , arith_expr , simple_expr。其中

• expr :expr為表達式的核心，是不受約束的表達式，可以直接用於where，having等子句中。
• arith_expr :arith_expr是可以用於between ... and之間的表達式，是受約束的表達式。因此arith_expr是expr的一個真子集。
• simple_expr :simple_expr是簡單表達式，不能直接進行自我遞歸的表達式。是expr和aritharith_expr的共有的部分。

expr_const:
    STRING 
  | DATE_VALUE 
  | INTNUM 
  | APPROXNUM 
  | BOOL 
  | NULLX 
  | QUESTIONMARK 
  | TEMP_VARIABLE 
  | SYSTEM_VARIABLE 
  | SESSION_ALIAS '.' column_name 
  ;

simple_expr:
    column_ref
  | expr_const
  | '(' expr ')'
  | '(' expr_list ',' expr ')'
  | case_expr
  | func_expr
  | when_func
  | select_with_parens        %prec UMINUS
  | EXISTS select_with_parens
  ;

/* used by the expression that use range value, e.g. between and */
arith_expr:
    simple_expr   
  | '+' arith_expr %prec UMINUS
  | '-' arith_expr %prec UMINUS
  | arith_expr '+' arith_expr 
  | arith_expr '-' arith_expr 
  | arith_expr '*' arith_expr 
  | arith_expr '/' arith_expr 
  | arith_expr '%' arith_expr 
  | arith_expr '^' arith_expr 
  | arith_expr MOD arith_expr 

expr:
    simple_expr   
  | '+' expr %prec UMINUS
  | '-' expr %prec UMINUS
  | expr '+' expr 
  | expr '-' expr 
  | expr '*' expr 
  | expr '/' expr 
  | expr '%' expr 
  | expr '^' expr 
  | expr MOD expr 
  | expr COMP_LE expr 
  | expr COMP_LT expr 
  | expr COMP_EQ expr 
  | expr COMP_GE expr 
  | expr COMP_GT expr 
  | expr COMP_NE expr 
  | expr LIKE expr 
  | expr NOT LIKE expr 
  | expr AND expr %prec AND
  | expr OR expr %prec OR
  | NOT expr
  | expr IS NULLX
  | expr IS NOT NULLX
  | expr IS BOOL
  | expr IS NOT BOOL
  | expr IS UNKNOWN
  | expr IS NOT UNKNOWN
  | expr BETWEEN arith_expr AND arith_expr        %prec BETWEEN
  | expr NOT BETWEEN arith_expr AND arith_expr      %prec BETWEEN
  | expr IN in_expr
  | expr NOT IN in_expr
  | expr CNNOP expr
  ;

simple_expr為簡單表達式，並不是說它很簡單，因為simple_expr也包含了select_with_parens(帶括號的select語句)等語句，隻能說simple_expr不能像arith_expr和expr等一樣遞歸調用。

expr:expr BETWEEN arith_expr AND arith_expr        %prec BETWEEN
  | expr NOT BETWEEN arith_expr AND arith_expr      %prec BETWEEN
  ;

arith_expr用於between ... and 之間，隻包含了算術表達式，沒有is,like 以及比較關係表達式。

expr,arith_expr,simple_expr實際上等同於PostgreSQL中的a_expr,b_expr,c_expr。

總之，在語法樹規則和詞法分析方麵，OceanBase大量的借鑒了PostgreSQL。

節點的創建

確定了節點的結構和語法樹的形狀，就到了實際創建語法樹的過程。通常,1條SQL語句的語法樹存在多個節點，數據庫中要高效的執行多條語句，就會遇到大量的節點創建問題。如果每次創建都調用new/malloc等係統函數必然會浪費大量的時，而且還會造成內存碎片。這種問題常常會出現在現實中，各個數據庫都有自己不同的解決辦法，但基本原理是一次性向係統申請較大的內存，然後在需要的時候自行分配。
接下來我將對比PostgreSQL，RedBase，OceanBase 3個數據庫是各自如何解決這一問題的。

PostgreSQL創建語法樹節點

PostgreSQL使用兩個宏完成節點的創建，即makeNode和newNode.

#define makeNode(_type_)  ((_type_ *) newNode(sizeof(_type_),T_##_type_))

/* 針對gcc版本的newNode */#define newNode(size, tag) \
({    Node *_result; \
    AssertMacro((size) >= sizeof(Node));/* 檢測申請的內存大小，>>=sizeof(Node) */ \
    _result = (Node *) palloc0fast(size); /* 申請內存 */ \
    _result->type = (tag); /*設置TypeTag */ \
    _result; /*返回值*/\
})

#define palloc0fast(sz) \
    ( MemSetTest(0, sz) ? \
        MemoryContextAllocZeroAligned(CurrentMemoryContext, sz) : \
        MemoryContextAllocZero(CurrentMemoryContext, sz) )

注意：要避免直接使用newNode來創建節點，因為節點的大小在不同的環境下可能是不同的。使用makeNode即可，如：
Stmt *s = makeNode(Stmt);

我們知道,PostgreSQL中繼承自NODE*的結構體們各自大小不一，都大於等於NODE 的大小。newNode中使用palloc0fast申請內存，它仍然是個宏，最終調用的是PostgreSQL中的MemoryContextAllocZeroAligned或者MemoryContextAllocZero函數，這兩個函數來自PostgreSQL中內存管理模塊--內存上下文，該模塊能夠很好的應對內存碎片，向數據庫進程提供緩衝區管理。

RedBase創建語法樹節點

RedBase沒有提供向PostgreSQL一樣複雜的內存管理機製，而是采用簡單的方法來解決頻繁創建節點的問題。因為RedBase中語法樹的節點都是NODE類型的，所有RedBase使用一個NODE的數組來作為緩衝區，默認最大值為100,超過這個值就會創建出錯，並最終退出程序。如果你的SQL語句需要的節點超過100,需要在編譯之前修改最大節點數目MAXNODE以適應需求。

#define MAXNODE        100 //最大節點數目

static NODE nodepool[MAXNODE];
static int nodeptr = 0;

/*
 * newnode: allocates a new node of the specified kind and returns a pointer
 * to it on success.  Returns NULL on error.
 */
NODE *newnode(NODEKIND kind)
{
    NODE *n;

    /* if we've used up all of the nodes then error */
    if(nodeptr == MAXNODE){
    fprintf(stderr, "out of memory\n");
    exit(1);
    }

    /* get the next node */
    n = nodepool + nodeptr;
    ++nodeptr;

    /* initialize the `kind' field */
    n -> kind = kind;
    return n;
}

OceanBase創建語法樹節點

OceanBase創建語法樹節點的方式與PostgreSQL類似，上層調用，底層有負責內存池管理的模塊來負責真正的創建，不過不是內存上下文，而是一個類ObStringBuf.

OceanBase的new_node函數申請內存時調用的是parse_malloc函數，該函數專用於語法樹結構體的創建,從obStringBuf中獲取內存，直到obStringBuf線程退出時才會真正釋放這些內存。

大型的數據庫都會有專門的內存管理模塊來負責語法程序運行過程中的內存申請和釋放，小型的數據庫則結合自身特點，量身定製輕量的內存管理機製。目的都隻有一個：降低頻繁創建和銷毀語法樹節點的開銷。

總結

SQL的執行包括了解析語法樹，製定邏輯查詢計劃，執行物理查詢計劃等步驟。通過對比3個不同的數據庫的源代碼，得出在解析語法樹中遇到的一些共性問題：

• 如何表示一個語法樹的節點
• 利用Bison定義語法樹的結構時的一些難點，如select,expr等
• 如何降低頻繁創建和銷毀語法樹節點的開銷

如果你要自己來寫一個SQL解析程序的話，這些問題同樣難以避免。

歡迎光臨我的網站----我的博客園----我的CSDN。
如果閱讀本文過程中有任何問題，請聯係作者，轉載請注明出處！