淘寶數據庫OceanBase SQL編譯器部分 源碼閱讀--生成邏輯計劃

SQL編譯解析三部曲分為：構建語法樹，生成邏輯計劃，指定物理執行計劃。第一步驟，在我的上一篇博客淘寶數據庫OceanBase SQL編譯器部分 源碼閱讀--解析SQL語法樹裏做了介紹，這篇博客主要研究第二步，生成邏輯計劃。

一、 什麼是邏輯計劃？

我們已經知道，語法樹就是一個樹狀的結構組織，每個節點代表一種類型的語法含義。如
update student set sex="M" where name ="小明";
這條SQL的語法樹形狀為：

|Update Stmt
|----Table:student
|----TargeList:
|--------sex = "M"
|----Qualifications:
|--------name="小明"

但是僅僅語法樹並不能知道數據庫中是否存在student這張表，這張表是否有sex,name這兩個字段，我們是否有權限修改這條記錄等。語法樹隻能判斷這條SQL的寫法是否正確，不能確定這條SQL是否可以執行。

邏輯計劃需要明確SQL語句中所涉及到的表，字段，表達式等是否有效。這個的邏輯計劃與在《數據庫係統實現》等書中描述的邏輯查詢計劃不同。邏輯查詢計劃將SQL語句直接轉為可運算的關係表達式。在OceanBase中，邏輯計劃則隻是查找或生成涉及到的表的ID，涉及字段的ID，涉及表達式的ID等，邏輯計劃是不可運算的。

二、邏輯計劃包含哪些內容？

簡單來說，邏輯計劃要弄清楚，這條SQL可以分解為幾條stmt,每條stmt包含了哪些表，字段和表達式。在此基礎上，如果是insert的Stmt，要加上設置哪些值;如果是update的stmt,要加上需要更新的列和對應的值，等等。

在一個邏輯計劃中，每一個查詢有一個唯一標識qid,每一張表有一個唯一的標識tid,每一個列有一個唯一的標識cid,每一個表達式有一個唯一的標識eid。

來看OceanBase中的邏輯計劃的結構（省略無關方法和變量).

class ObLogicalPlan
    {
      //...  
      oceanbase::common::ObVector<ObStmt*> stmts_; //存儲該邏輯計劃的所有stmt
      oceanbase::common::ObVector<ObSqlRawExpr*> exprs_; //邏輯計劃的所有表達式
      oceanbase::common::ObVector<ObRawExpr*> raw_exprs_store_;//存儲邏輯計劃的所有表達式
      uint64_t  new_gen_tid_;//用於生成新的tid
      uint64_t  new_gen_cid_;//用於生成新的cid
      uint64_t  new_gen_qid_;//用於生成新的qid
      uint64_t  new_gen_eid_;//用於生成新的eid
    };

oceanbase::common::ObVector是OceanBase中自己實現的泛型容器之一，作用與STL的vector相同。
stmts_存儲該邏輯計劃的所有stmt;
raw_exprs_store_僅僅用於存儲表達式，exprs_則引用raw_exprs_store_中的內容。
new_gen_tid_等4個變量是用來生成新的標識時使用，一個邏輯是可以用多個tid,多個cid,多個eid，多個qid的。這些標識分布於存儲的stmt和表達式中。

注：stmt實在不知道中文該怎麼稱唿，就不改中文名了。

2.1 邏輯計劃中表的定義

struct TableItem
{
    uint64_t    table_id_;
    common::ObString    table_name_;
    common::ObString    alias_name_;
    TableType   type_;

    uint64_t     ref_id_;
};

table_id_唯一標識一個關係表，其類型分為基本表，引用表和子查詢關係。
對同一個實體表,ref_id_與table_id_相同; 如果是一個引用別名的表，則table_id_是新生成的，ref_id_與這個表真正的table_id_相同;如果是一個子查詢，則table_id_是新生成的,ref_id_是對子查詢的引用。

對同一個實體表，它在所有線程使用的table_id_都是相同的；如果是生成的標識，則僅在該線程會話期間是唯一的。

2.2 邏輯計劃中列的定義

struct ColumnItem
{
    uint64_t    column_id_;
    common::ObString    column_name_;
    uint64_t    table_id_;
    uint64_t    query_id_;

    bool        is_name_unique_;
    bool        is_group_based_;

    common::ObObjType     data_type_;
};

column_id_唯一標識一個列，table_id_和query_id_為該列所屬的關係表和stmt。is_name_unique_僅用在解析邏輯計劃期間，標記該列的名稱是否在所有表的字段中都是唯一的。is_group_based_標記該列是否用於分組。data_type_標識該列的數據類型。

2.3 邏輯計劃中的表達式的定義

邏輯計劃的中表達式有多種類型，其基類為ObRawExpr.包括兩個成員變量，type_表示表達式的類型，result_type_表示表達式值的類型。

class ObRawExpr
 {
 //省略其他方法
 private:
    ObItemType  type_;
    common::ObObjType result_type_;
 }

表達式分為常量表達式, 一元引用表達式，二元引用表達式，一元操作符表達式，二元操作符表達式，三元操作符表達式，多元操作符表達式，case操作符表達式，聚集函數表達式，係統函數表達式，SQL原生表達式等。繼承關係如下。

namespace sql
{
     //原生表達式基類
    class ObRawExpr
    //常量表達式
    class ObConstRawExpr        : public ObRawExpr
    //一元引用表達式
    class ObUnaryRefRawExpr     : public ObRawExpr
    //二元引用表達式
    class ObBinaryRefRawExpr    : public ObRawExpr
    //一元操作符表達式
    class ObUnaryOpRawExpr      : public ObRawExpr
    //二元操作符表達式
    class ObBinaryOpRawExpr     : public ObRawExpr
     //三元操作符表達式
    class ObTripleOpRawExpr     : public ObRawExpr
    //多元操作符表達式
    class ObMultiOpRawExpr      : public ObRawExpr
    //case操作符表達式
    class ObCaseOpRawExpr       : public ObRawExpr
    //聚集函數表達式
    class ObAggFunRawExpr       : public ObRawExpr
    //係統函數表達式
    class ObSysFunRawExpr       : public ObRawExpr
    //SQL原生表達式
    class ObSqlRawExpr          : public ObRawExpr
 };

 class ObRawExpr
 {

 };

在ObLogicalPlan中，存儲使用的是vector<ObRawExpr *>,使用時轉為vector<ObSqlRawExpr *>.

2.4 邏輯計劃中的Stmt的定義

Stmt表示一個單獨的查詢所包含的內容，一個邏輯計劃可以包含多個Stmt.

 class ObStmt
    {
    /*省略部分內容...*/
    protected:
      common::ObVector<TableItem>    table_items_;
      common::ObVector<ColumnItem>   column_items_;

    private:
      StmtType  type_;
      uint64_t  query_id_;
      //uint64_t  where_expr_id_;
      common::ObVector<uint64_t>     where_expr_ids_;

    };

Stmt包括了一個查詢所有的表table_items_,列column_items_,表達式where_expr_ids_和一個唯一的查詢標識query_id_。注意這裏存儲的隻有表達式的id,而不是表達式的實際內容。

從上述的定義總結來看，一個邏輯計劃擁有多條查詢實例Stmt和多個表達式，一個查詢實例Stmt包含了多個表和多個列及所需表達式的引用。表，列，表達式，查詢實例都有唯一的標識符進行標記。

ObLogicalPlan
----ObStmt : 1...n
--------TableItem : 0...n
--------ColnumItem : 0...n
--------expr_id_ref : 0...n
----ObRawExpr : 0...n

三、 如何製定邏輯計劃？

3.1 reslove係列解析函數

製定邏輯計劃的源碼在build_plan.h和build_plan.cpp中，在OceanBase0.4中，則增加了dml_build_plan.h和dml_build_plan.cpp。製定邏輯對外提供的接口隻有兩個,解析函數resolove和銷毀函數destroy_plan,其他的為自用，可以瀏覽下其函數聲明及用途，基本的結構就是這樣，因為目前OceanBase中支持的SQL語句不多，相應的解析函數也比較少，還有一些沒有完成，可以想見未來還會添加更多的函數。

//解析多重查詢
int resolve_multi_stmt(ResultPlan* result_plan, ParseNode* node)
//解析獨立表達式
int resolve_independ_expr()
//解析and表達式
int resolve_and_exprs()
//解析表達式
int resolve_expr()
//解析聚集函數
int resolve_agg_func()
//解析join表連接
int resolve_joined_table()
//解析表
int resolve_table()
//解析from子句
int resolve_from_clause()
//解析列
int resolve_table_columns()
//解析*
int resolve_star()
//解析select的投影列表
int resolve_select_clause()
//解析where子句
int resolve_where_clause()
//解析group by子句
int resolve_group_clause()
//解析having子句
int resolve_having_clause()
//解析order子句
int resolve_order_clause()
//解析limit子句
int resolve_limit_clause()
//解析select查詢
int resolve_select_stmt()
//解析delete查詢
int resolve_delete_stmt()
//解析insert的插入列
int resolve_insert_columns()
//解析intsert查詢的插入值
int resolve_insert_values()
//解析insert查詢
int resolve_insert_stmt()
//解析update查詢
int resolve_update_stmt()
//解析函數。對外提供
int resolve(ResultPlan* result_plan, ParseNode* node)
//銷毀函數，對外提供
extern void destroy_plan(ResultPlan* result_plan)

resolve函數根據語法樹node的類型調用不同的查詢解析實例。以下是部分代碼摘抄：

int resolve(ResultPlan* result_plan, ParseNode* node)
{
   /*...*/

  uint64_t query_id = OB_INVALID_ID;
  if (ret == OB_SUCCESS && node != NULL)
  {
    switch (node->type_)
    {
      case T_STMT_LIST:
      {
        ret = resolve_multi_stmt(result_plan, node);
        break;
      }
      case T_SELECT:
      {
        ret = resolve_select_stmt(result_plan, node, query_id);
        break;
      }
      case T_DELETE:
      {
        ret = resolve_delete_stmt(result_plan, node, query_id);
        break;
      }
      case T_INSERT:
      {
        ret = resolve_insert_stmt(result_plan, node, query_id);
        break;
      }
      case T_UPDATE:
      {
        ret = resolve_update_stmt(result_plan, node, query_id);
        break;
      }
      default:
        ret = OB_ERROR;
        break;
    };
  }
  return ret;
}
int resolve_update_stmt(ResultPlan* result_plan, ParseNode* node, uint64_t& query_id)
{
  int& ret = result_plan->err_stat_.err_code_ = OB_SUCCESS;
  uint64_t table_id = OB_INVALID_ID;

  query_id = OB_INVALID_ID;

  ObLogicalPlan* logical_plan  logical_plan = new(logical_plan) ObLogicalPlan(name_pool);

  result_plan->plan_tree_ = logical_plan;


  update_stmt = new(update_stmt) ObUpdateStmt(name_pool);

  query_id = logical_plan->generate_query_id();
  //為update_stmt設置新的標識qid
  update_stmt->set_query_id(query_id);

  logical_plan->add_query(update_stmt);

  ParseNode* table_node = node->children_[0];
  //解析表  
  ret = resolve_table(result_plan, update_stmt, table_node, table_id);

  update_stmt->set_update_table(table_id);

  ParseNode* assign_list = node->children_[1];

  uint64_t ref_id;
  ColumnItem *column_item = NULL;
  //解析要更新的列表，如:update student set sex="M",grade="2" where name = "xiaoming";
  for (int32_t i = 0; ret == OB_SUCCESS && i < assign_list->num_child_; i++)
  {
      ParseNode* assgin_node = assign_list->children_[i];

      /* resolve target column */
      ParseNode* column_node = assgin_node->children_[0];

      ObString column_name;
            column_name.assign_ptr(
                (char*)(column_node->str_value_), 
                static_cast<int32_t>(strlen(column_node->str_value_))
                );
      //1 根據列名獲取列
      column_item = update_stmt->get_column_item(NULL, column_name);
      //2 解析列到vector<ColumnItem *>
      ret = update_stmt->add_column_item(*result_plan, column_name, NULL, &column_item);
      //3 增加列引用到update_stmt  
      ret = update_stmt->add_update_column(column_item->column_id_);

            /* resolve new value expression */
      //4 解析值表達式
      ParseNode* expr = assgin_node->children_[1];
      ret = resolve_independ_expr(result_plan, update_stmt, expr, ref_id, T_UPDATE_LIMIT);
      //5 添加值表達式引用到update_stmt
      ret = update_stmt->add_update_expr(ref_id)
  }
  //解析where子句
  ret = resolve_where_clause(result_plan, update_stmt, node->children_[2]);

  return ret;
}

我們仍舊以update語句為例。上麵是根據源代碼整理的邏輯，不是源碼，主要是為了理清思路。

1. 首先是創建一個新的查詢update_stmt，並為其生成一個獨立的查詢標識qid
2. 解析語句中的表，並將表的標識tid添加到update_stmt的引用列表
3. 利用for循環逐個解析要更新的列-值對：
   (1). 根據列名獲取列;
   (2). 將該列存儲到update_stmt的vector<ColumnItem *>中,並將列引用id添加到update_stmt的更新列列表ObArray<uint64_t> update_columns_中;
   (3). 解析值表達式;
   (4). 將值表達式引用id添加到更新值列表ObArray<uint64_t> update_exprs_中去;
4. 解析where子句.

3.2 如何解析表和列？

通過上麵我們知道，邏輯計劃的解析的一個重要內容就是要確定查詢stmt,表，列，表達式的標識.查詢和表達式的標識id都可以在解析的時候生成。因為這兩項不是線程共有的，但是表和列是持久的數據，可以跨線程使用同樣的id。這些表和列的信息由誰來管理？

3.2.1 使用Schema

追根溯源，你會發現實體表和列的id是在ob_schema.cpp中獲取的。什麼是schema？schema就是數據庫對象的一個集合。網上有一個很形象的比喻,我稍微做了點改動：

什麼是Database，什麼是Schema，什麼是Table，什麼是列，什麼是行，什麼是User？我們可以可以把Database看作是一個大倉庫，倉庫分了很多很多的房間，Schema就是其中的房間，一個Schema代表一個房間，Table可以看作是每個Schema中的櫃子，行和列就是櫃子中的格子。User就是房間的主人。

OceanBase要求schema強類型約束，也就是要預先定義好schema。這樣可以方便的進行各種online ddl操作。

OceanBase的表和列信息存儲在Schema的一個hash_map中。關於Schema 以後再深入了解。

四、總結

製定邏輯計劃，最關鍵的是要理解邏輯計劃的設計目標，其中最主要的內容就是確定邏輯計劃中使用到的查詢Stmt,表，列，表達式，並為它們生成或設置唯一標識，確保在同一個邏輯計劃中是不相同的。製定邏輯計劃的函數隻要是reslove係列函數。而表和列的信息存儲在Schema中一個hash_map中。

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