基于規則的查詢改寫 · k8s原理與實踐

[TOC] # 基于規則的查詢改寫基于規則的查詢改寫方式主要包括子查詢相關改寫、外聯接消除、簡化條件改寫和非 SPJ（SELECT PROJECT JOIN）的改寫等。 ## 子查詢相關改寫優化器對于子查詢一般使用嵌套執行的方式，也就是父查詢每生成一行數據后，都需要執行一次子查詢。使用這種方式需要多次執行子查詢，執行效率很低。對于子查詢的優化方式，一般會將其改寫為聯接操作，可大大提高執行效率，主要優點如下： * 可避免子查詢多次執行。 * 優化器可根據統計信息選擇更優的聯接順序和聯接方法。 * 子查詢的聯接條件、過濾條件改寫為父查詢的條件后，優化器可以進行進一步優化，比如條件下壓等。子查詢改寫的方式主要包括視圖合并、子查詢展開和將 ANY/ALL 使用 MAX/MIN 改寫等。 #### **視圖合并** 視圖合并是指將代表一個視圖的子查詢合并到包含該視圖的查詢中，視圖合并后，有助于優化器增加聯接順序的選擇、訪問路徑的選擇以及進一步做其他改寫操作，從而選擇更優的執行計劃。 OceanBase 數據庫支持對 SPJ 視圖進行合并。如下示例為 Q1 改寫為 Q2： ~~~ obclient>CREATE TABLE t1 (c1 INT, c2 INT); Query OK, 0 rows affected (0.00 sec) obclient>CREATE TABLE t2 (c1 INT PRIMARY KEY, c2 INT); Query OK, 0 rows affected (0.00 sec) obclient>CREATE TABLE t3 (c1 INT PRIMARY KEY, c2 INT); Query OK, 0 rows affected (0.00 sec) Q1: obclient>SELECT t1.c1, v.c1 FROM t1, (SELECT t2.c1, t3.c2 FROM t2, t3 WHERE t2.c1 = t3.c1) v WHERE t1.c2 = v.c2; <==> Q2: obclient>SELECT t1.c1, t2.c1 FROM t1, t2, t3 WHERE t2.c1 = t3.c1 AND t1.c2 = t3.c2; ~~~ 如果 Q1 不進行改寫，則其聯接順序有以下幾種： * t1, v(t2,t3) * t1, v(t3,t2) * v(t2,t3), t1 * v(t3,t2), t1 進行視圖合并改寫后，可選擇的聯接順序有： * t1, t2, t3 * t1, t3, t2 * t2, t1, t3 * t2, t3, t1 * t3, t1, t2 * t3, t2, t1 可以看出，進行視圖合并后，聯接順序可選擇空間增加。對于復雜查詢，視圖合并后，對路徑的選擇和可改寫的空間均會增大，從而使得優化器可生成更優的計劃。 #### **子查詢展開** 子查詢展開是指將 WHERE 條件中子查詢提升到父查詢中，并作為聯接條件與父查詢并列進行展開。轉換后子查詢將不存在，外層父查詢中會變成多表聯接。這樣改寫的好處是優化器在進行路徑選擇、聯接方法和聯接排序時都會考慮到子查詢中的表，從而可以獲得更優的執行計劃。涉及的子查詢表達式一般有 NOT IN、IN、NOT EXIST、EXIST、ANY、ALL。子查詢展開的方式如下： * 改寫條件使生成的聯接語句能夠返回與原始語句相同的行。 * 展開為半聯接（SEMI JOIN / ANTI JOIN）如下例所示，t2.c2 不具有唯一性，改為 SEMI JOIN，該語句改寫后執行計劃為： ~~~ obclient>CREATE TABLE t1 (c1 INT, c2 INT); Query OK, 0 rows affected (0.17 sec) obclient>CREATE TABLE t2 (c1 INT PRIMARY KEY, c2 INT); Query OK, 0 rows affected (0.01 sec) obclient>EXPLAIN SELECT * FROM t1 WHERE t1.c1 IN (SELECT t2.c2 FROM t2)\G; *************************** 1. row *************************** Query Plan: ======================================= |ID|OPERATOR |NAME|EST. ROWS|COST| --------------------------------------- |0 |HASH SEMI JOIN| |495 |3931| |1 | TABLE SCAN |t1 |1000 |499 | |2 | TABLE SCAN |t2 |1000 |433 | ======================================= Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t1.c2]), filter(nil), equal_conds([t1.c1 = t2.c2]), other_conds(nil) 1 - output([t1.c1], [t1.c2]), filter(nil), access([t1.c1], [t1.c2]), partitions(p0) 2 - output([t2.c2]), filter(nil), access([t2.c2]), partitions(p0) ~~~ 將查詢前面操作符改為 NOT IN 后，可改寫為 ANTI JOIN，具體計劃如下例所示： ~~~ obclient>EXPLAIN SELECT * FROM t1 WHERE t1.c1 NOT IN (SELECT t2.c2 FROM t2)\G; *************************** 1. row *************************** Query Plan: ================================================ |ID|OPERATOR |NAME|EST. ROWS|COST | ------------------------------------------------ |0 |NESTED-LOOP ANTI JOIN| |0 |520245| |1 | TABLE SCAN |t1 |1000 |499 | |2 | TABLE SCAN |t2 |22 |517 | ================================================ Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t1.c2]), filter(nil), conds(nil), nl_params_([t1.c1], [(T_OP_IS, t1.c1, NULL, 0)]) 1 - output([t1.c1], [t1.c2], [(T_OP_IS, t1.c1, NULL, 0)]), filter(nil), access([t1.c1], [t1.c2]), partitions(p0) 2 - output([t2.c2]), filter([(T_OP_OR, ? = t2.c2, ?, (T_OP_IS, t2.c2, NULL, 0))]), access([t2.c2]), partitions(p0) ~~~ * 子查詢展開為內聯接上面示例的 Q1 中如果將 t2.c2 改為 t2.c1，由于 t2.c1 為主鍵，子查詢輸出具有唯一性，此時可以直接轉換為內聯接，如下例所示： ~~~ Q1: obclient>SELECT * FROM t1 WHERE t1.c1 IN (SELECT t2.c1 FROM t2)\G; <==> Q2: obclient>SELECT t1.* FROM t1, t2 WHERE t1.c1 = t2.c1; ~~~ Q1 改寫后的計劃如下例所示： ~~~ obclient>EXPLAIN SELECT * FROM t1 WHERE t1.c1 IN (SELECT t2.c1 FROM t2)\G; *************************** 1. row *************************** Query Plan: ==================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ------------------------------------ |0 |HASH JOIN | |1980 |3725| |1 | TABLE SCAN|t2 |1000 |411 | |2 | TABLE SCAN|t1 |1000 |499 | ==================================== Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t1.c2]), filter(nil), equal_conds([t1.c1 = t2.c1]), other_conds(nil) 1 - output([t2.c1]), filter(nil), access([t2.c1]), partitions(p0) 2 - output([t1.c1], [t1.c2]), filter(nil), access([t1.c1], [t1.c2]), partitions(p0) ~~~ 對于 NOT IN、IN、NOT EXIST、EXIST、ANY、ALL 子查詢表達式都可以對應做類似的改寫操作。 #### **ANY/ALL 使用 MAX/MIN 改寫** 對于 ANY/ALL 的子查詢，如果子查詢中沒有 GROUP BY 子句、聚集函數以及 HAVING 時，以下表達式可以使用聚集函數 MIN/MAX 進行等價轉換，其中`col_item`為單獨列且有非 NULL 屬性： ~~~ val > ALL(SELECT col_item ...) <==> val > ALL(SELECT MAX(col_item) ...); val >= ALL(SELECT col_item ...) <==> val >= ALL(SELECT MAX(col_item) ...); val < ALL(SELECT col_item ...) <==> val < ALL(SELECT MIN(col_item) ...); val <= ALL(SELECT col_item ...) <==> val <= ALL(SELECT MIN(col_item) ...); val > ANY(SELECT col_item ...) <==> val > ANY(SELECT MIN(col_item) ...); val >= ANY(SELECT col_item ...) <==> val >= ANY(SELECT MIN(col_item) ...); val < ANY(SELECT col_item ...) <==> val < ANY(SELECT MAX(col_item) ...); val <= ANY(SELECT col_item ...) <==> val <= ANY(SELECT MAX(col_item) ...); ~~~ 將子查詢更改為含有 MAX/MIN 的子查詢后，再結合使用 MAX/MIN 的改寫，可減少改寫前對內表的多次掃描，如下例所示： ~~~ obclient>SELECT c1 FROM t1 WHERE c1 > ANY(SELECT c1 FROM t2); <==> obclient>SELECT c1 FROM t1 WHERE c1 > ANY(SELECT MIN(c1) FROM t2); ~~~ 結合 MAX/MIN 的改寫后，可利用 t2.c1 的主鍵序將 LIMIT 1 直接下壓到 TABLE SCAN，將 MIN 值輸出，執行計劃如下： ~~~ obclient>EXPLAIN SELECT c1 FROM t1 WHERE c1 > ANY(SELECT c1 FROM t2)\G; *************************** 1. row *************************** Query Plan: =================================================== |ID|OPERATOR |NAME |EST. ROWS|COST| --------------------------------------------------- |0 |SUBPLAN FILTER | |1 |73 | |1 | TABLE SCAN |t1 |1 |37 | |2 | SCALAR GROUP BY| |1 |37 | |3 | SUBPLAN SCAN |subquery_table|1 |37 | |4 | TABLE SCAN |t2 |1 |36 | =================================================== Outputs & filters: ------------------------------------- 0 - output([t1.c1]), filter([t1.c1 > ANY(subquery(1))]), exec_params_(nil), onetime_exprs_(nil), init_plan_idxs_([1]) 1 - output([t1.c1]), filter(nil), access([t1.c1]), partitions(p0) 2 - output([T_FUN_MIN(subquery_table.c1)]), filter(nil), group(nil), agg_func([T_FUN_MIN(subquery_table.c1)]) 3 - output([subquery_table.c1]), filter(nil), access([subquery_table.c1]) 4 - output([t2.c1]), filter(nil), access([t2.c1]), partitions(p0), limit(1), offset(nil) ~~~ ## 外聯接消除外聯接操作可分為左外聯接、右外聯接和全外聯接。在聯接過程中，由于外聯接左右順序不能變換，優化器對聯接順序的選擇會受到限制。外聯接消除是指將外聯接轉換成內聯接，從而可以提供更多可選擇的聯接路徑，供優化器考慮。如果進行外聯接消除，需要存在“空值拒絕條件”，即在 WHERE 條件中存在，當內表生成的值為 NULL 時，輸出為 FALSE 的條件。如下例所示： ~~~ obclient>SELECT t1.c1, t2.c2 FROM t1 LEFT JOIN t2 ON t1.c2 = t2.c2; ~~~ 這是一個外聯接，在其輸出行中 t2.c2 可能為 NULL。如果加上一個條件`t2.c2 > 5`，則通過該條件過濾后，t2.c1 輸出不可能為 NULL，從而可以將外聯接轉換為內聯接。 ~~~ obclient>SELECT t1.c1, t2.c2 FROM t1 LEFT JOIN t2 ON t1.c2 = t2.c2 WHERE t2.c2 > 5; <==> obclient>SELECT t1.c1, t2.c2 FROM t1 LEFT INNER JOIN t2 ON t1.c2 = t2.c2 WHERE t2.c2 > 5; ~~~ ## 簡化條件改寫 #### HAVING 條件消除如果查詢中沒有聚集操作及 GROUP BY，則 HAVING 可以合并到 WHERE 條件中，并將 HAVING 條件刪除，從而可以將 HAVING 條件在 WHERE 條件中統一管理，并進行進一步相關優化。 ~~~ obclient>SELECT * FROM t1, t2 WHERE t1.c1 = t2.c1 HAVING t1.c2 > 1; <==> obclient>SELECT * FROM t1, t2 WHERE t1.c1 = t2.c1 AND t1.c2 > 1; ~~~ 改寫后計劃如下例所示,`t1.c2 > 1`條件被下壓到了 TABLE SCAN 層。 ~~~ obclient>EXPLAIN SELECT * FROM t1, t2 WHERE t1.c1 = t2.c1 HAVING t1.c2 > 1\G; *************************** 1. row *************************** Query Plan: ========================================= |ID|OPERATOR |NAME|EST. ROWS|COST| ----------------------------------------- |0 |NESTED-LOOP JOIN| |1 |59 | |1 | TABLE SCAN |t1 |1 |37 | |2 | TABLE GET |t2 |1 |36 | ========================================= Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t1.c2], [t2.c1], [t2.c2]), filter(nil), conds(nil), nl_params_([t1.c1]) 1 - output([t1.c1], [t1.c2]), filter([t1.c2 > 1]), access([t1.c1], [t1.c2]), partitions(p0) 2 - output([t2.c1], [t2.c2]), filter(nil), access([t2.c1], [t2.c2]), partitions(p0) ~~~ #### **等價關系推導** 等價關系推導是指利用比較操作符的傳遞性，推倒出新的條件表達式，從而減少需要處理的行數或者選擇到更有效的索引。 OceanBase 數據庫可對等值聯接進行推導，比如`a ＝ b AND a > 1`可以推導出`a ＝ b AND a > 1 AND b > 1`，如果 b 上有索引，且`b > 1`在該索引選擇率很低，則可以大大提升訪問 b 列所在表的性能。如下例所示，條件`t1.c1 = t2.c2 AND t1.c1 > 2`，等價推導后為`t1.c1 = t2.c2 AND t1.c1 > 2 AND t2.c2 > 2`，從計劃中可以看到 t2.c2 已下壓到 TABLE SCAN，并且使用 t2.c2 對應的索引。 ~~~ obclient>CREATE TABLE t1(c1 INT PRIMARY KEY, c2 INT); Query OK, 0 rows affected (0.15 sec) obclient>CREATE TABLE t2(c1 INT PRIMARY KEY, c2 INT, c3 INT, KEY IDX_c2(c2)); Query OK, 0 rows affected (0.10 sec) /*此命令需運行于 MySQL 模式下*/ obclient>EXPLAIN EXTENDED_NOADDR SELECT t1.c1, t2.c2 FROM t1, t2 WHERE t1.c1 = t2.c2 AND t1.c1 > 2\G; *************************** 1. row *************************** Query Plan: ========================================== |ID|OPERATOR |NAME |EST. ROWS|COST| ------------------------------------------ |0 |MERGE JOIN | |5 |78 | |1 | TABLE SCAN|t2(IDX_c2)|5 |37 | |2 | TABLE SCAN|t1 |3 |37 | ========================================== Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t2.c2]), filter(nil), equal_conds([t1.c1 = t2.c2]), other_conds(nil) 1 - output([t2.c2]), filter(nil), access([t2.c2]), partitions(p0), is_index_back=false, range_key([t2.c2], [t2.c1]), range(2,MAX ; MAX,MAX), range_cond([t2.c2 > 2]) 2 - output([t1.c1]), filter(nil), access([t1.c1]), partitions(p0), is_index_back=false, range_key([t1.c1]), range(2 ; MAX), range_cond([t1.c1 > 2]) ~~~ #### **恒真/假消除** 對于如下恒真恒假條件可以進行消除： * false and expr ＝恒 false * true or expr = 恒 true 如下例所示，對于`WHERE 0 > 1 AND c1 ＝ 3`，由于`0 > 1`使得 AND 恒假，所以該 SQL 不用執行，可直接返回，從而加快查詢的執行。 ~~~ obclient>EXPLAIN EXTENDED_NOADDR SELECT * FROM t1 WHERE 0 > 1 AND c1 = 3\G; *************************** 1. row *************************** Query Plan: =================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ----------------------------------- |0 |TABLE SCAN|t1 |0 |38 | =================================== Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t1.c2]), filter([0], [t1.c1 = 3]), startup_filter([0]), access([t1.c1], [t1.c2]), partitions(p0), is_index_back=false, filter_before_indexback[false,false], range_key([t1.__pk_increment], [t1.__pk_cluster_id], [t1.__pk_partition_id]), range(MAX,MAX,MAX ; MIN,MIN,MIN)always false ~~~ ## 非 SPJ 的改寫 #### **冗余排序消除** 冗余排序消除是指刪除 order item 中不需要的項，減少排序開銷。以下三種情況可進行排序消除： * ORDER BY 表達式列表中有重復列，可進行去重后排序。 ~~~ obclient>SELECT * FROM t1 WHERE c2 = 5 ORDER BY c1, c1, c2, c3 ; <==> obclient>SELECT * FROM t1 WHERE c2 = 5 ORDER BY c1, c2, c3; ~~~ * ORDER BY 列中存在 where 中有單值條件的列，該列排序可刪除。 ~~~ obclient>SELECT * FROM t1 WHERE c2 = 5 ORDER BY c1, c2, c3; <==> obclient>SELECT * FROM t1 WHERE c2 = 5 ORDER BY c1, c3; ~~~ * 如果本層查詢有 ORDER BY 但是沒有 LIMIT，且本層查詢位于父查詢的集合操作中，則 ORDER BY 可消除。因為對兩個有序的集合做 UNION 操作，其結果是亂序的。但是如果 ORDER BY 中有 LIMIT，則語義是取最大/最小的 N 個，此時不能消除 ORDER BY，否則有語義錯誤。 ~~~ obclient>(SELECT c1,c2 FROM t1 ORDER BY c1) UNION (SELECT c3,c4 FROM t2 ORDER BY c3)； <==> obclient>(SELECT c1,c2 FROM t1) UNION (SELECT c3,c4 FROM t2)； ~~~ #### **LIMIT 下壓** LIMIT 下壓改寫是指將 LIMIT 下降到子查詢中，OceanBase 數據庫現在支持在不改變語義的情況下，將 LIMIT 下壓到視圖（示例 1）及 UNION 對應子查詢（示例 2）中。示例 1： ~~~ obclient>SELECT * FROM (SELECT * FROM t1 ORDER BY c1) a LIMIT 1; <==> obclient>SELECT * FROM (SELECT * FROM t1 ORDER BY c1 LIMIT 1) a LIMIT 1; ~~~ 示例 2： ~~~ obclient>(SELECT c1,c2 FROM t1) UNION ALL (SELECT c3,c4 FROM t2) LIMIT 5; <==> obclient>(SELECT c1,c2 FROM t1 LIMIT 5) UNION ALL (SELECT c3,c4 FROM t2 limit 5) LIMIT 5; ~~~ #### **DISTINCT 消除** * 如果 select item 中只包含常量，則可以消除 DISTINCT，并加上 LIMIT 1。 ~~~ obclient>SELECT DISTINCT 1,2 FROM t1 ; <==> obclient>SELECT DISTINCT 1,2 FROM t1 LIMIT 1; obclient>CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT); Query OK, 0 rows affected (0.17 sec) obclient>EXPLAIN EXTENDED_NOADDR SELECT DISTINCT 1,2 FROM t1\G; *************************** 1. row *************************** Query Plan: =================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ----------------------------------- |0 |TABLE SCAN|t1 |1 |36 | =================================== Outputs & filters: ------------------------------------- 0 - output([1], [2]), filter(nil), access([t1.c1]), partitions(p0), limit(1), offset(nil), is_index_back=false, range_key([t1.c1]), range(MIN ; MAX)always true ~~~ * 如果 select item 中包含確保唯一性約束的列，則 DISTINCT 能夠消除，如下示例中 (c1, c2)為主鍵，可確保 c1、c2 和 c3 唯一性，從而 DISTINCT 可消除。 ~~~ obclient>CREATE TABLE t2(c1 INT, c2 INT, c3 INT, PRIMARY KEY(c1, c2)); Query OK, 0 rows affected (0.17 sec) obclient>SELECT DISTINCT c1, c2, c3 FROM t2; <==> obclient>SELECT c1, c2 c3 FROM t2; obclient>EXPLAIN SELECT DISTINCT c1, c2, c3 FROM t2\G; *************************** 1. row *************************** Query Plan: =================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ----------------------------------- |0 |TABLE SCAN|t2 |1000 |455 | =================================== Outputs & filters: ------------------------------------- 0 - output([t2.c1], [t2.c2], [t2.c3]), filter(nil), access([t2.c1], [t2.c2], [t2.c3]), partitions(p0) ~~~ #### **MIN/MAX 改寫** * 當 MIN/MAX 函數中參數為索引前綴列，且不含 GROUP BY 時，可將該 scalar aggregate 轉換為走索引掃描 1 行的情況，如下例所示： ~~~ obclient>CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT, c3 INT, KEY IDX_c2_c3(c2,c3)); Query OK, 0 rows affected (0.17 sec) obclient>SELECT MIN(c2) FROM t1; <==> obclient>SELECT MIN(c2) FROM (SELECT c2 FROM t2 ORDER BY c2 LIMIT 1) AS t; obclient>EXPLAIN SELECT MIN(c2) FROM t1\G; *************************** 1. row *************************** Query Plan: ================================================== |ID|OPERATOR |NAME |EST. ROWS|COST| -------------------------------------------------- |0 |SCALAR GROUP BY| |1 |37 | |1 | SUBPLAN SCAN |subquery_table|1 |37 | |2 | TABLE SCAN |t1(idx_c2_c3) |1 |36 | ================================================== Outputs & filters: ------------------------------------- 0 - output([T_FUN_MIN(subquery_table.c2)]), filter(nil), group(nil), agg_func([T_FUN_MIN(subquery_table.c2)]) 1 - output([subquery_table.c2]), filter(nil), access([subquery_table.c2]) 2 - output([t1.c2]), filter([(T_OP_IS_NOT, t1.c2, NULL, 0)]), access([t1.c2]), partitions(p0), limit(1), offset(nil) ~~~ * 如果`SELECT MIN/MAX`的參數為常量，而且包含 GROUP BY，可以將 MIN/MAX 改為常量，從而減少 MIN/MAX 的計算開銷。 ~~~ obclient>SELECT MAX(1) FROM t1 GROUP BY c1; <==> obclient>SELECT 1 FROM t1 GROUP BY c1; obclient>EXPLAIN EXTENDED_NOADDR SELECT MAX(1) FROM t1 GROUP BY c1\G; *************************** 1. row *************************** Query Plan: =================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ----------------------------------- |0 |TABLE SCAN|t1 |1000 |411 | =================================== Outputs & filters: ------------------------------------- 0 - output([1]), filter(nil), access([t1.c1]), partitions(p0), is_index_back=false, range_key([t1.c1]), range(MIN ; MAX)always true ~~~ * 如果`SELECT MIN/MAX`的參數為常量，而且不含 GROUP BY，可以按照如下示例進行改寫，從而走索引只需掃描 1 行。 ~~~ obclient>SELECT MAX(1) FROM t1; <==> obclient>SELECT MAX(t.a) FROM (SELECT 1 AS a FROM t1 LIMIT 1) t; obclient>EXPLAIN EXTENDED_NOADDR SELECT MAX(1) FROM t1\G; *************************** 1. row *************************** Query Plan: ================================================== |ID|OPERATOR |NAME |EST. ROWS|COST| -------------------------------------------------- |0 |SCALAR GROUP BY| |1 |37 | |1 | SUBPLAN SCAN |subquery_table|1 |37 | |2 | TABLE SCAN |t1 |1 |36 | ================================================== Outputs & filters: ------------------------------------- 0 - output([T_FUN_MAX(subquery_table.subquery_col_alias)]), filter(nil), group(nil), agg_func([T_FUN_MAX(subquery_table.subquery_col_alias)]) 1 - output([subquery_table.subquery_col_alias]), filter(nil), access([subquery_table.subquery_col_alias]) 2 - output([1]), filter(nil), access([t1.c1]), partitions(p0), limit(1), offset(nil), is_index_back=false, range_key([t1.c1]), range(MIN ; MAX)always true ~~~