基于規則的路徑選擇 · k8s原理與實踐

[TOC] # 基于規則的路徑選擇目前 OceanBase 數據庫路徑選擇的規則體系分為前置規則（正向規則）和 Skyline 剪枝規則（反向規則）。前置規則直接決定了一個查詢使用什么樣的索引，是一個強匹配的規則體系。 Skyline 剪枝規則會比較兩個索引，如果一個索引在一些定義的維度上優于（dominate）另外一個索引，那么不優的索引會被剪掉，最后沒有被剪掉的索引會進行代價比較，從而選出最優的計劃。目前 OceanBase 數據庫的優化器會優先使用前置規則選擇索引，如果沒有匹配的索引，那么 Skyline 剪枝規則會剪掉一些不優的索引，最后代價模型會在沒有被剪掉的索引中選擇代價最低的路徑。如下例所示，OceanBase 數據庫的計劃展示中會輸出相應的路徑選擇的規則信息。 ~~~ 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 展示了具體的規則信息，它有以下兩種形式: * 如果`optimization_method=rule_based`, 那么就是命中了前置規則，同時會展示出具體命中的規則名稱，unique\_index\_with\_indexback 表示命中了前置規則的第三條規則（唯一性索引全匹配+回表+回表數量少于一定的閾值）。 * 如果`optimization_method=cost_based`, 那么就是基于代價選擇出來的，同時會展示出來 Skyline 剪枝規則剪掉了那些訪問路徑（pruned\_index\_name）以及剩下了那些訪問路徑（avaiable\_index\_name）。 ## 前置規則目前 OceanBase 數據庫的前置規則只用于簡單的單表掃描。因為前置規則是一個強匹配的規則體系，一旦命中，就直接選擇命中的索引，所以要限制它的使用場景，以防選錯計劃。目前 OceanBase 數據庫根據“查詢條件是否能覆蓋所有索引鍵”和“使用該索引是否需要回表”這兩個信息，將前置規則按照優先級劃分成如下三種匹配類型： * 匹配“唯一性索引全匹配+不需要回表（主鍵被當成唯一性索引來處理）”，則選擇該索引。如果存在多個這樣的索引，選擇索引列數最小的一個。 * 匹配“普通索引全匹配+不需要回表”，則選擇該索引。如果存在多個這樣的索引，選擇索引列數最小的一個。 * 匹配“唯一性索引全匹配+回表+回表數量少于一定的閾值”，則選擇該索引。如果存在多個這樣的索引，選擇回表數量最小的一個。這里需要注意的是，索引全匹配是指在索引鍵上都存在等值條件（對應于 get 或者 multi-get）。如下示例中，查詢 Q1 命中了索引 uk1（唯一性索引全匹配+不需要回表）；查詢 Q2 命中了索引 uk2（唯一性索引全匹配+回表+回表行數最多 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 剪枝規則 Skyline 算子是學術界在 2001 年提出的一個新的數據庫算子（它并不是標準的 SQL 算子）。自此之后，學術界對 Skyline 算子有大量的研究（包括語法、語義和執行等）。 Skyline 從字面上的理解是指天空中的一些邊際點，這些點組成搜索空間中最優解的集合。例如要尋找價格最低并且路途最短的一家旅館，想象一個二維空間，有兩個維度，橫軸表示價格，縱軸表示距離，二維空間上的每個點表示一個旅館。如下圖所示，不論最后的選擇如何，最優解肯定是在這一條天空的邊際線上。假設點 A 不在 Skyline 上，那么肯定能夠在 Skyline 上找到在兩個維度上都比 A 更優的點 B，在這個場景中就是距離更近，價格更便宜的旅館，稱為點 B dominate A。所以 Skyline 一個重要應用場景就是用戶沒辦法去衡量多個維度的比重，或者多個維度不能綜合量化（如果可以綜合量化，使用 “SQL 函數+ ORDER BY ”就可以解決了）。 ![](https://img.kancloud.cn/10/44/1044642478af9770f9ae0368fece5893_642x454.png) Skyline 操作是在給定對象集 O 中找出不被別的對象所 dominate 的對象集合。若一個對象 A 在所有維度都不被另一個對象 B 所 dominate，并且 A 至少在一個維度上 dominate B，則稱 A dominate B。所以在 Skyline 操作中比較重要的是維度的選擇以及在每個維度上的 dominate 的關系定義。假設有 N 個索引的路徑`<idx_1，idx_2，idx_3...idx_n>`可以供優化器選擇，如果對于查詢 Q，索引 idx\_x 在定義的維度上 dominate 索引 idx\_y，那就可以提前把索引 idx\_y 剪掉，不讓它參與最終代價的運算。 ## 維度的定義針對 Skyline 剪枝，對每個索引（主鍵也是一種索引）定義了如下三個維度: * 是否回表 * 是否存在 intersting order * 索引前綴能否抽取 query range 通過如下示例進行分析： ~~~ 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 的話就需要回查主表，因為索引 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; ~~~ 基于這三個維度，定義了索引之間的 dominate 關系，如果索引 A 在三個維度上都不比索引 B 差，并且其中至少有一個維度比 B 好，那么就可以直接把 B 索引剪掉，因為基于索引 B 最后生成的計劃肯定不會比索引 A 好。 * 如果索引 idx\_A 不需要回表，而索引 idx\_B 需要回表，那么在這個維度上索引 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`）, 那么在這個維度上索引 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, 那么在這個維度上索引 idx\_A dominate idx\_B。 #### **回表** 這個維度初看比較簡單，就是查詢所需列是否在索引中。其中，一些案例需要特殊考慮，例如當主表和索引表都沒有 interesting order 和抽取不了 query range 的情況下，直接走主表不一定是最優解。 ~~~ 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; ~~~ <table data-tag="table" id="table-7m6-nxd-zl3" class="table"><colgroup span="1" width="180" data-tag="col" id="col-63n-247-k42" colwidth="1*" colnum="1" colname="col1" style="width:25%" class="col"></colgroup><colgroup span="1" width="180" data-tag="col" id="col-p7s-t0z-n9s" colwidth="1*" colnum="2" colname="col2" style="width:25%" class="col"></colgroup><colgroup span="1" width="180" data-tag="col" id="col-asy-dvk-sp1" colwidth="1*" colnum="3" colname="col3" style="width:25%" class="col"></colgroup><colgroup span="1" width="180" data-tag="col" id="col-wpm-cn0-34l" colwidth="1*" colnum="4" colname="col4" style="width:25%" class="col"></colgroup><thead id="thead-xnn-wye-5pq" class="thead"><tr id="tr-ndn-k5i-3um"><th id="td-4tu-04o-2rd">索引</th><th id="td-p62-qv4-qpj">Index Back</th><th id="td-daw-891-c30">Interesting Order</th><th id="td-27u-lgy-2iy">Query Range</th></tr></thead><tbody data-tag="tbody" id="tbody-wvo-npf-dgy" class="tbody"><tr data-tag="tr" id="tr-vru-fbb-5ie" class="tr"><td data-tag="td" id="td-shr-tcs-3q3" class="td">primary</td><td data-tag="td" id="td-glp-t56-pio" class="td">no</td><td data-tag="td" id="td-7xf-mu9-ktc" class="td">no</td><td data-tag="td" id="td-9iy-zyl-cgj" class="td">no</td></tr><tr data-tag="tr" id="tr-jub-dyr-i9s" class="tr"><td data-tag="td" id="td-g4q-peu-stz" class="td">idx_a_b</td><td data-tag="td" id="td-p7h-pvi-kn6" class="td">yes</td><td data-tag="td" id="td-0rq-i97-j52" class="td">no</td><td data-tag="td" id="td-c8q-8ha-ido" class="td">no</td></tr></tbody></table> 主表很寬，而索引表很窄，雖然從維度上主表 dominate 索引 idx\_a\_b，然而，索引掃描加回表的代價不一定會比主表全表掃描來的慢。簡單來說，索引表可能只需要讀一個宏塊，而主表可能需要十個宏塊。這種情況下，需要對規則做一些放寬，考慮具體的過濾條件。 #### **Interesting Order** 優化器通過 Interesting Order 利用底層的序，就不需要對底層掃描的行做排序，還可以消除 ORDER BY，進行 MERGE GROUP BY，提高 Pipeline（不需要進行物化）等。 ~~~ 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); ~~~ ![](https://img.kancloud.cn/48/97/48973dc7a8301cb01d0f743f9c6e650d_702x395.png) 從執行計劃可以看到，ORDER BY 被消除了，同時使用了 MERGE DISTINCT，UNION 也沒有做 SORT。可以看到，從底層 TABLE SCAN 吐出來的序，可以被上層的算子使用。換句話說，保留 idx\_v1\_v3\_v5 吐出來的行的順序，可以讓后面的算子在保序的情況下執行更優的操作。優化器在識別這些序的情況下，才能生成更優的執行計劃。所以 Skyline 剪枝對 interesting order 的判斷，需要充分考慮各個索引能夠最大利用的序。例如上述最大的序其實是`v1,v3`而不僅僅是 v1，它從 MERGE JOIN 吐出來的序（v1, v3) 可以到 MERGE DISINCT 算子, 再到最后的 UNISON DISTINCT 算子。 #### **Query Range** Query range 的抽取可以方便底層直接根據抽取出來的 range 定位到具體的宏塊，而從減少存儲層的 IO。例如`SELECT * FROM t1 WHERE pk < 100 AND pk > 0`就可以直接根據一級索引的信息定位到具體的宏塊，加速查詢，越精確的 query range 能夠讓數據庫掃描更少的行。 ~~~ 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)，所以在這個維度上，索引 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; ~~~ <table data-tag="table" id="table-8be-4ac-7jb" class="table"><colgroup span="1" width="180" data-tag="col" id="col-r2z-9vv-54c" colwidth="1*" colnum="1" colname="col1" style="width:25%" class="col"></colgroup><colgroup span="1" width="180" data-tag="col" id="col-hpv-bra-smz" colwidth="1*" colnum="2" colname="col2" style="width:25%" class="col"></colgroup><colgroup span="1" width="180" data-tag="col" id="col-gio-j20-gx3" colwidth="1*" colnum="3" colname="col3" style="width:25%" class="col"></colgroup><colgroup span="1" width="180" data-tag="col" id="col-mnq-yif-vae" colwidth="1*" colnum="4" colname="col4" style="width:25%" class="col"></colgroup><thead id="thead-nnh-wsx-57g" class="thead"><tr id="tr-qfd-hv8-9fr"><th id="td-m77-ru9-us6">索引</th><th id="td-lm3-6u2-7vb">Index Back</th><th id="td-rb3-zpc-q2h">Interesting order</th><th id="td-4vk-r68-puh">Query range</th></tr></thead><tbody data-tag="tbody" id="tbody-v9h-3ql-boq" class="tbody"><tr data-tag="tr" id="tr-6p6-11w-9qo" class="tr"><td data-tag="td" id="td-ti0-brt-6j4" class="td">primary</td><td data-tag="td" id="td-lh9-qx0-0tk" class="td">Not need</td><td data-tag="td" id="td-9bl-8xl-yly" class="td">No</td><td data-tag="td" id="td-95o-q9s-aov" class="td">No</td></tr><tr data-tag="tr" id="tr-h6q-aif-diz" class="tr"><td data-tag="td" id="td-9wf-5lu-mjw" class="td">idx_v1_v3_v5</td><td data-tag="td" id="td-795-jsr-gez" class="td">Not need</td><td data-tag="td" id="td-zd6-dy5-s0u" class="td">(v1)</td><td data-tag="td" id="td-73w-bd2-m17" class="td">(v1, v3)</td></tr><tr data-tag="tr" id="tr-mgn-sg3-g65" class="tr"><td data-tag="td" id="td-q10-2a6-5ti" class="td">idx_v3_v4</td><td data-tag="td" id="td-c5d-qif-d08" class="td">Need</td><td data-tag="td" id="td-iuj-nno-e9j" class="td">No</td><td data-tag="td" id="td-nlb-ouw-4bv" class="td">(v3)</td></tr></tbody></table> 可以看到索引 idx_v1_v3_v5 在三個維度上都不比主鍵索引或索引 idx_v3_v4 差。所以在規則系統下，會直接剪掉主鍵索引和索引 idx_v3_v4。維度的合理定義，決定了 Skyline 剪枝是否合理。錯誤的維度，將會導致該索引提前被剪掉，從而導致永遠生成不了最優的計劃。