OceanBase 基于規(guī)則的路徑選擇

目前 OceanBase 數(shù)據(jù)庫路徑選擇的規(guī)則體系分為前置規(guī)則（正向規(guī)則）和 Skyline 剪枝規(guī)則（反向規(guī)則）。前置規(guī)則直接決定了一個(gè)查詢使用什么樣的索引，是一個(gè)強(qiáng)匹配的規(guī)則體系。

Skyline 剪枝規(guī)則會(huì)比較兩個(gè)索引，如果一個(gè)索引在一些定義的維度上優(yōu)于（dominate）另外一個(gè)索引，那么不優(yōu)的索引會(huì)被剪掉，最后沒有被剪掉的索引會(huì)進(jìn)行代價(jià)比較，從而選出最優(yōu)的計(jì)劃。

目前 OceanBase 數(shù)據(jù)庫的優(yōu)化器會(huì)優(yōu)先使用前置規(guī)則選擇索引，如果沒有匹配的索引，那么 Skyline 剪枝規(guī)則會(huì)剪掉一些不優(yōu)的索引，最后代價(jià)模型會(huì)在沒有被剪掉的索引中選擇代價(jià)最低的路徑。

如下例所示，OceanBase 數(shù)據(jù)庫的計(jì)劃展示中會(huì)輸出相應(yīng)的路徑選擇的規(guī)則信息。

obclient>CREATE TABLE t1(a INT PRIMARY KEY, b INT, c INT, d INT, e INT, 
            UNIQUE INDEX k1(b), INDEX k2(b,c), INDEX k3(c,d));
Query OK, 0 rows affected (0.38 sec)

obclient> EXPLAIN EXTENDED SELECT * FROM t1 WHERE b = 1;
+-----------------------------------------------------------------+
| Query Plan                                                                              |
+-----------------------------------------------------------------+
| =====================================
|ID|OPERATOR  |NAME  |EST. ROWS|COST|
-------------------------------------
|0 |TABLE SCAN|t1(k1)|2        |94  |
=====================================

Outputs & filters:
-------------------------------------
  0 - output([t1.a(0x7f3178058bf0)], [t1.b(0x7f3178058860)], [t1.c(0x7f3178058f80)], [t1.d(0x7f3178059310)], [t1.e(0x7f31780596a0)]), filter(nil),
      access([t1.b(0x7f3178058860)], [t1.a(0x7f3178058bf0)], [t1.c(0x7f3178058f80)], [t1.d(0x7f3178059310)], [t1.e(0x7f31780596a0)]), partitions(p0),
      is_index_back=true,
      range_key([t1.b(0x7f3178058860)], [t1.shadow_pk_0(0x7f31780784b8)]), range(1,MIN ; 1,MAX),
      range_cond([t1.b(0x7f3178058860) = 1(0x7f31780581d8)])
Optimization Info:
-------------------------------------
t1:optimization_method=rule_based, heuristic_rule=unique_index_with_indexback


obclient> EXPLAIN EXTENDED SELECT * FROM t1 WHERE c < 5 ORDER BY c;
+-----------------------------------------------------------------+
| Query Plan                                                                              |
+-----------------------------------------------------------------+
| ====================================
|ID|OPERATOR   |NAME|EST. ROWS|COST|
------------------------------------
|0 |SORT       |    |200      |1054|
|1 | TABLE SCAN|t1  |200      |666 |
====================================

Outputs & filters:
-------------------------------------
  0 - output([t1.a(0x7f3178059220)], [t1.b(0x7f31780595b0)], [t1.c(0x7f3178058e90)], [t1.d(0x7f3178059940)], [t1.e(0x7f3178059cd0)]), filter(nil), sort_keys([t1.c(0x7f3178058e90), ASC])
  1 - output([t1.c(0x7f3178058e90)], [t1.a(0x7f3178059220)], [t1.b(0x7f31780595b0)], [t1.d(0x7f3178059940)], [t1.e(0x7f3178059cd0)]), filter([t1.c(0x7f3178058e90) < 5(0x7f3178058808)]),
      access([t1.c(0x7f3178058e90)], [t1.a(0x7f3178059220)], [t1.b(0x7f31780595b0)], [t1.d(0x7f3178059940)], [t1.e(0x7f3178059cd0)]), partitions(p0),
      is_index_back=false, filter_before_indexback[false],
      range_key([t1.a(0x7f3178059220)]), range(MIN ; MAX)always true
t1:optimization_method=cost_based, avaiable_index_name[t1,k3], pruned_index_name[k1,k2]

其中 optimization_method 展示了具體的規(guī)則信息，它有以下兩種形式:

• 如果 optimization_method=rule_based, 那么就是命中了前置規(guī)則，同時(shí)會(huì)展示出具體命中的規(guī)則名稱，unique_index_with_indexback 表示命中了前置規(guī)則的第三條規(guī)則（唯一性索引全匹配+回表+回表數(shù)量少于一定的閾值）。

• 如果 optimization_method=cost_based, 那么就是基于代價(jià)選擇出來的，同時(shí)會(huì)展示出來 Skyline 剪枝規(guī)則剪掉了那些訪問路徑（pruned_index_name）以及剩下了那些訪問路徑（avaiable_index_name）。

前置規(guī)則

目前 OceanBase 數(shù)據(jù)庫的前置規(guī)則只用于簡單的單表掃描。因?yàn)榍爸靡?guī)則是一個(gè)強(qiáng)匹配的規(guī)則體系，一旦命中，就直接選擇命中的索引，所以要限制它的使用場景，以防選錯(cuò)計(jì)劃。

目前 OceanBase 數(shù)據(jù)庫根據(jù)“查詢條件是否能覆蓋所有索引鍵”和“使用該索引是否需要回表”這兩個(gè)信息，將前置規(guī)則按照優(yōu)先級(jí)劃分成如下三種匹配類型：

• 匹配“唯一性索引全匹配+不需要回表（主鍵被當(dāng)成唯一性索引來處理）”，則選擇該索引。如果存在多個(gè)這樣的索引，選擇索引列數(shù)最小的一個(gè)。

• 匹配“普通索引全匹配+不需要回表”，則選擇該索引。如果存在多個(gè)這樣的索引，選擇索引列數(shù)最小的一個(gè)。

• 匹配“唯一性索引全匹配+回表+回表數(shù)量少于一定的閾值”，則選擇該索引。如果存在多個(gè)這樣的索引，選擇回表數(shù)量最小的一個(gè)。

這里需要注意的是，索引全匹配是指在索引鍵上都存在等值條件（對應(yīng)于 get 或者 multi-get）。

如下示例中，查詢 Q1 命中了索引 uk1（唯一性索引全匹配+不需要回表）；查詢 Q2 命中了索引 uk2（唯一性索引全匹配+回表+回表行數(shù)最多 4 行）。

obclient>CREATE TABLE  test(a INT PRIMARY KEY, b INT, c INT, d INT, e INT, 
              UNIQUE KEY UK1(b,c), UNIQUE KEY UK2(c,d) );
Query OK, 0 rows affected (0.38 sec)

Q1: 
obclient>SELECT b,c FROM test WHERE (b = 1 OR b = 2) AND (c = 1 OR c =2);

Q2: 
obclient>SELECT * FROM test WHERE (c = 1 OR c =2) OR (d = 1 OR d = 2);

Skyline 剪枝規(guī)則

Skyline 算子是學(xué)術(shù)界在 2001 年提出的一個(gè)新的數(shù)據(jù)庫算子（它并不是標(biāo)準(zhǔn)的 SQL 算子）。自此之后，學(xué)術(shù)界對 Skyline 算子有大量的研究（包括語法、語義和執(zhí)行等）。

Skyline 從字面上的理解是指天空中的一些邊際點(diǎn)，這些點(diǎn)組成搜索空間中最優(yōu)解的集合。例如要尋找價(jià)格最低并且路途最短的一家旅館，想象一個(gè)二維空間，有兩個(gè)維度，橫軸表示價(jià)格，縱軸表示距離，二維空間上的每個(gè)點(diǎn)表示一個(gè)旅館。

如下圖所示，不論最后的選擇如何，最優(yōu)解肯定是在這一條天空的邊際線上。假設(shè)點(diǎn) A 不在 Skyline 上，那么肯定能夠在 Skyline 上找到在兩個(gè)維度上都比 A 更優(yōu)的點(diǎn) B，在這個(gè)場景中就是距離更近，價(jià)格更便宜的旅館，稱為點(diǎn) B dominate A。所以 Skyline 一個(gè)重要應(yīng)用場景就是用戶沒辦法去衡量多個(gè)維度的比重，或者多個(gè)維度不能綜合量化（如果可以綜合量化，使用 “SQL 函數(shù)+ ORDER BY ”就可以解決了）。

Skyline 操作是在給定對象集 O 中找出不被別的對象所 dominate 的對象集合。若一個(gè)對象 A 在所有維度都不被另一個(gè)對象 B 所 dominate，并且 A 至少在一個(gè)維度上 dominate B，則稱 A dominate B。所以在 Skyline 操作中比較重要的是維度的選擇以及在每個(gè)維度上的 dominate 的關(guān)系定義。假設(shè)有 N 個(gè)索引的路徑 <idx_1，idx_2，idx_3...idx_n> 可以供優(yōu)化器選擇，如果對于查詢 Q，索引 idx_x 在定義的維度上 dominate 索引 idx_y，那就可以提前把索引 idx_y 剪掉，不讓它參與最終代價(jià)的運(yùn)算。

維度的定義

針對 Skyline 剪枝，對每個(gè)索引（主鍵也是一種索引）定義了如下三個(gè)維度:

• 是否回表

• 是否存在 intersting order

• 索引前綴能否抽取 query range

通過如下示例進(jìn)行分析：

 obclient> CREATE TABLE skyline(
        pk INT PRIMARY KEY, a INT, b INT, c INT,
        KEY idx_a_b(a, b),
        KEY idx_b_c(b, c),
        KEY idx_c_a(c, a));
Query OK, 0 rows affected (0.09 sec)

• 回表：該查詢是否需要需要回查主表。

  /* 走索引 idx_a_b 的話就需要回查主表，因?yàn)樗饕?idx_a_b 沒有 c 列*/ 
  obclient>SELECT /*+INDEX(skyline idx_a_b)*/ * FROM skyline;

• interesting order: 考慮是否有合適的序可以利用。

  /* 索引 idx_b_c 可以把 ORDER BY 語句消除*/ 
  obclient>SELECT pk, b FROM skyline ORDER BY b;

• 索引前綴能否抽取 query range。

  /*可以看到走索引 idx_c_a 就可以快速定位到需要的行的范圍，不用全表掃描*/
  obclient>SELECT pk, b FROM skyline WHERE c > 100 AND c < 2000;

基于這三個(gè)維度，定義了索引之間的 dominate 關(guān)系，如果索引 A 在三個(gè)維度上都不比索引 B 差，并且其中至少有一個(gè)維度比 B 好，那么就可以直接把 B 索引剪掉，因?yàn)榛谒饕?B 最后生成的計(jì)劃肯定不會(huì)比索引 A 好。

• 如果索引 idx_A 不需要回表，而索引 idx_B 需要回表，那么在這個(gè)維度上索引 idx_A dominate idx_B。

• 如果在索引 idx_A上抽取出來的 intersting order 是向量 Va<a1, a2, a3 ...an>， 在索引 idx_B 上抽出來的interesting order 是向量 Vb<b1, b2, b3...bm>, 如果 n > m , 并且對于ai = bi （i=1..m）, 那么在這個(gè)維度上索引 idx_A dominate idx_B。

• 如果在索引 idx_A 能用來抽取的 query range 的列集合是 Sa<a1, a2, a3 ...an>，在索引 idx_B 上能用來抽取 query range 的列集合是 Sb <b1, b2, b3...bm>, 如果 Sa 是 Sb 的 super set, 那么在這個(gè)維度上索引 idx_A dominate idx_B。

回表

這個(gè)維度初看比較簡單，就是查詢所需列是否在索引中。其中，一些案例需要特殊考慮，例如當(dāng)主表和索引表都沒有 interesting order 和抽取不了 query range 的情況下，直接走主表不一定是最優(yōu)解。

obclient>CREATE TABLE t1(
         pk INT PRIMARY KEY, a INT, b INT, c INT, v1 VARCHAR(1000), 
         v2 VARCHAR(1000), v3 VARCHAR(1000), v4 VARCHAR(1000),INDEX idx_a_b(a, b));
Query OK, 0 rows affected (0.09 sec)

obclient>SELECT a, b,c FROM t1 WHERE b = 100;

主表很寬，而索引表很窄，雖然從維度上主表 dominate 索引 idx_a_b，然而，索引掃描加回表的代價(jià)不一定會(huì)比主表全表掃描來的慢。簡單來說，索引表可能只需要讀一個(gè)宏塊，而主表可能需要十個(gè)宏塊。這種情況下，需要對規(guī)則做一些放寬，考慮具體的過濾條件。

Interesting Order

優(yōu)化器通過 Interesting Order 利用底層的序，就不需要對底層掃描的行做排序，還可以消除 ORDER BY，進(jìn)行 MERGE GROUP BY，提高 Pipeline（不需要進(jìn)行物化）等。

obclient>CREATE TABLE skyline(
        pk INT PRIMARY KEY, v1 INT, v2 INT, v3 INT, v4 INT, v5 INT,
        KEY idx_v1_v3_v5(v1, v3, v5),
        KEY idx_v3_v4(v3, v4));
Query OK, 0 rows affected (0.10 sec)

obclient>CREATE TABLE tmp (c1 INT PRIMARY KEY, c2 INT, c3 INT);
Query OK, 0 rows affected (0.06 sec)

obclient>(SELECT DISTINCT v1, v3 FROM skyline JOIN tmp WHERE skyline.v1 = tmp.c1 
          ORDER BY v1, v3) UNION (SELECT c1, c2 FROM tmp);

從執(zhí)行計(jì)劃可以看到，ORDER BY 被消除了，同時(shí)使用了 MERGE DISTINCT，UNION 也沒有做 SORT。可以看到，從底層 TABLE SCAN 吐出來的序，可以被上層的算子使用。換句話說，保留 idx_v1_v3_v5 吐出來的行的順序，可以讓后面的算子在保序的情況下執(zhí)行更優(yōu)的操作。優(yōu)化器在識(shí)別這些序的情況下，才能生成更優(yōu)的執(zhí)行計(jì)劃。

所以 Skyline 剪枝對 interesting order 的判斷，需要充分考慮各個(gè)索引能夠最大利用的序。例如上述最大的序其實(shí)是 v1,v3 而不僅僅是 v1，它從 MERGE JOIN 吐出來的序（v1, v3) 可以到 MERGE DISINCT 算子, 再到最后的 UNISON DISTINCT 算子。

Query Range

Query range 的抽取可以方便底層直接根據(jù)抽取出來的 range 定位到具體的宏塊，而從減少存儲(chǔ)層的 IO。

例如 SELECT * FROM t1 WHERE pk < 100 AND pk > 0 就可以直接根據(jù)一級(jí)索引的信息定位到具體的宏塊，加速查詢，越精確的 query range 能夠讓數(shù)據(jù)庫掃描更少的行。

obclient> CREATE TABLE t1 (
       pk INT PRIMARY KEY, a INT, b INT,c INT,
        KEY idx_b_c(b, c),
        KEY idx_a_b(a, b));
Query OK, 0 rows affected (0.12 sec)

obclient>SELECT b FROM t1 WHERE a = 100 AND b > 2000;

對于索引 idx_b_c 它能抽出 query range 的索引前綴是 (b)，對于索引 idx_a_b 它能抽出 query range 的索引前綴是 (a, b)，所以在這個(gè)維度上，索引 idx_a_b dominate idx_b_c。

綜合舉例

obclient>CREATE TABLE skyline(
        pk INT PRIMARY KEY, v1 INT, v2 INT, v3 INT, v4 INT, v5 INT,
        KEY idx_v1_v3_v5(v1, v3, v5),
        KEY idx_v3_v4(v3, v4));
Query OK, 0 rows affected (0.10 sec)

obclient>CREATE TABLE tmp (c1 INT PRIMARY KEY, c2 INT, c3 INT);
Query OK, 0 rows affected (0.06 sec)

obclient>SELECT MAX(v5) FROM skyline WHERE v1 = 100 AND v3 > 200 GROUP BY v1;

可以看到索引 idx_v1_v3_v5 在三個(gè)維度上都不比主鍵索引或索引 idx_v3_v4 差。所以在規(guī)則系統(tǒng)下，會(huì)直接剪掉主鍵索引和索引 idx_v3_v4。維度的合理定義，決定了 Skyline 剪枝是否合理。錯(cuò)誤的維度，將會(huì)導(dǎo)致該索引提前被剪掉，從而導(dǎo)致永遠(yuǎn)生成不了最優(yōu)的計(jì)劃。