淘寶數據庫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語法的執行順序等。

---

歡迎光臨我的網站----蝴蝶忽然的博客園----人既無名的專欄。
如果閱讀本文過程中有任何問題，請聯係作者，轉載請注明出處！