PolarDB-X 1.0接收到一條SQL后的執(zhí)行過程大致如下：

1. 語法解析器（Parser）將SQL文本解析成抽象語法樹（AST）。
2. 語法樹被轉(zhuǎn)化成基于關(guān)系代數(shù)的邏輯計劃。
3. 優(yōu)化器（Optimizer）對邏輯計劃進行優(yōu)化得到物理計劃。
4. 執(zhí)行器（Executor）執(zhí)行該計劃，得到查詢結(jié)果并返回給客戶端。

本文將會介紹查詢優(yōu)化器的基本原理，包含如下幾個方面：

• 關(guān)系代數(shù)算子。
• 查詢改寫（RBO階段）。
• 查詢計劃枚舉（CBO階段）。

關(guān)系代數(shù)算子

一條SQL查詢在數(shù)據(jù)庫系統(tǒng)中通常被表示為一棵關(guān)系代數(shù)算子組成的樹，有如下場景的算子：

• Project：用于描述SQL中的SELECT列，包括函數(shù)計算。
• Filter：用于描述SQL中的WHERE條件。
• JOIN：用于描述SQL中的JOIN，其對應(yīng)的物理算子有HashJoin、 BKAJoin、Nested-Loop Join、SortMergeJoin。
• Agg：用于描述SQL中的Group By及聚合函數(shù)，其對應(yīng)的物理算子有HashAgg、SortAgg。
• Sort：用于描述SQL中的Order By及Limit，其對應(yīng)的物理算子有TopN、MemSort。
• LogicalView：用于描述PolarDB-X 1.0下發(fā)至存儲層MySQL的SQL，其內(nèi)部可能包含一個或多個邏輯算子。
• Gather：代表從多個數(shù)據(jù)流匯集數(shù)據(jù)的操作，通常出現(xiàn)在LogicalView之上（若開啟并行執(zhí)行，則并行優(yōu)化步驟會將其上拉）。

例如，對于如下查詢SQL（修改自TPC-H Query 3）：

SELECT l_orderkey, sum(l_extendedprice *(1 - l_discount)) AS revenue
FROM CUSTOMER, ORDERS, LINEITEM
WHERE c_mktsegment = 'AUTOMOBILE'
  and c_custkey = o_custkey
  and l_orderkey = o_orderkey
  and o_orderdate < '1995-03-13'
  and l_shipdate > '1995-03-13'
GROUP BY l_orderkey;

通過如下EXPLAIN命令看到PolarDB-X 1.0的執(zhí)行計劃：

HashAgg(group="l_orderkey", revenue="SUM(*)")
  HashJoin(condition="o_custkey = c_custkey", type="inner")
    Gather(concurrent=true)
      LogicalView(tables="ORDERS_[0-7],LINEITEM_[0-7]", shardCount=8, sql="SELECT `ORDERS`.`o_custkey`, `LINEITEM`.`l_orderkey`, (`LINEITEM`.`l_extendedprice` * (? - `LINEITEM`.`l_discount`)) AS `x` FROM `ORDERS` AS `ORDERS` INNER JOIN `LINEITEM` AS `LINEITEM` ON (((`ORDERS`.`o_orderkey` = `LINEITEM`.`l_orderkey`) AND (`ORDERS`.`o_orderdate` < ?)) AND (`LINEITEM`.`l_shipdate` > ?))")
    Gather(concurrent=true)
      LogicalView(tables="CUSTOMER_[0-7]", shardCount=8, sql="SELECT `c_custkey` FROM `CUSTOMER` AS `CUSTOMER` WHERE (`c_mktsegment` = ?)")

用樹狀圖表示如下：

查詢改寫（RBO）

查詢改寫（SQL Rewrite）階段輸入為邏輯執(zhí)行計劃，輸出為邏輯執(zhí)行計劃。這一步主要應(yīng)用一些啟發(fā)式規(guī)則，是基于規(guī)則的優(yōu)化器（Rule-Based Optimizer，簡稱RBO），所以也常被稱為RBO階段。

查詢改寫這一步的主要有如下功能：

• 子查詢?nèi)リP(guān)聯(lián)化（Subquery Unnesting）

  子查詢?nèi)リP(guān)聯(lián)化是將含有關(guān)聯(lián)項的子查詢（關(guān)聯(lián)子查詢）表示為SemiJoin或類似的算子，便于后續(xù)的各種優(yōu)化，例如下推到存儲層MySQL或在PolarDB-X 1.0層選擇某種算法執(zhí)行。在如下例子中IN子查詢轉(zhuǎn)化為SemiJoin算子，并最終轉(zhuǎn)化成SemiHashJoin物理算子由PolarDB-X 1.0執(zhí)行：

  > explain  select id from t1 where id in (select id from t2 where t2.name = 'hello');
  SemiHashJoin(condition="id = id", type="semi")
    Gather(concurrent=true)
      LogicalView(tables="t1", shardCount=2, sql="SELECT `id` FROM `t1` AS `t1`")
    Gather(concurrent=true)
      LogicalView(tables="t2_[0-3]", shardCount=4, sql="SELECT `id` FROM `t2` AS `t2` WHERE (`name` = ?)")

• 算子下推

  算子下推是非常關(guān)鍵的一步，PolarDB-X 1.0內(nèi)置了如下算子的下推優(yōu)化規(guī)則：

  優(yōu)化規(guī)則	描述
  謂詞下推或列裁剪	將Filter及Project算子下推至存儲層MySQL執(zhí)行，過濾掉不需要的行和列。
  JOIN Clustering	將JOIN按照拆分方式及拆分鍵的等值條件進行重排和聚簇，方便下一步的JOIN下推。
  JOIN下推	對于符合條件的JOIN，將其下推至存儲層MySQL執(zhí)行。
  Agg下推	將聚合（Agg）拆分為FinalAgg和LocalAgg兩個階段，并將LocalAgg下推至存儲層MySQL。
  Sort下推	將排序（Sort）拆分為MergeSort和LocalSort兩個階段，并將LocalSort下推至存儲層MySQL。

  更多關(guān)于查詢下推的信息，請參見查詢改寫與下推。

查詢計劃枚舉（CBO）

查詢改寫階段輸出的邏輯執(zhí)行計劃會被輸入到查詢計劃枚舉（Plan Enumerator）中，并輸出一個最終的物理執(zhí)行計劃。查詢計劃枚舉在多個可行的查詢計劃中，根據(jù)預(yù)先定義的代價模型，選擇出代價最低的一個。與查詢改寫階段不同，在查詢計劃枚舉中，規(guī)則可能產(chǎn)生更好的執(zhí)行計劃，也可能產(chǎn)生更差的執(zhí)行計劃，可以根據(jù)算子經(jīng)過規(guī)則優(yōu)化后的前后代價對比選出較優(yōu)的那個，因此這也被稱為基于代價的優(yōu)化（Cost-based Optimizer，簡稱CBO）。

其核心組件有以下幾個部分：

• 統(tǒng)計信息（Statistics）
• 基數(shù)估計（Cardinality Estimation）
• 轉(zhuǎn)化規(guī)則（Transform Rules）
• 代價模型（Cost Model）
• 計劃空間搜索引擎（Plan Space Search Engine）

邏輯上，CBO的過程包括如下幾個步驟：

1. 搜索引擎利用轉(zhuǎn)化規(guī)則，對輸入的邏輯執(zhí)行計劃進行變換，構(gòu)造出物理執(zhí)行計劃的搜索空間。
2. 利用代價模型對搜索空間中的每一個執(zhí)行計劃進行代價估計，選出代價最低的物理執(zhí)行計劃。
3. 代價估計的過程離不開基數(shù)估計，它利用各個表、列的統(tǒng)計信息，估算出各算子的輸入行數(shù)、選擇率等信息，提供給算子的代價模型，從而估算出查詢計劃的代價。