緣起

StoneDB 在列式存盤引擎 Tianmu 的加持下，在大多數場景下相對 MySQL 都會有大幅性能提升，當然，這是需要工程師不斷優化代碼才能做到的，而且，性能好也需要通過基準測驗才有說服力，所以我們也會針對 TPC-H 的測驗陳述句進行測驗排查，爭取不斷提升 StoneDB 的性能，本文主要講解對 TPCH_Q4 的分析優化，在這個優化程序中，我們涉及到了對子查詢中的 Semi-join 優化，

首先看一下 Q4 的查詢陳述句，比較簡單：

explain
select o_orderpriority,
       count(*) as order_count
from orders
where o_orderdate >= date'1993-07-01'
  and o_orderdate < date'1993-07-01' + interval'3'month
  andexists(
        select *
        from lineitem
        where l_orderkey = o_orderkey
          and l_commitdate < l_receiptdate
    )
groupby o_orderpriority
orderby o_orderpriority;

可以看到，這個陳述句中只有兩個查詢表, 4 個謂詞條件，特點是在子查詢中使用了外表的欄位，我們也管這種叫做相關子查詢，而在驅動表里則使用了聚合，

這里科普一下，驅動表（Driving Table），也稱外層表（Outer Table）,顧名思義，驅動表是用來驅動查詢的，驅動表僅僅用于 Nested-Loop Join 和 Hash Join，簡單來說，就是用來最先獲得資料，并以此表的資料為依據，逐步獲得其他表的資料，直至最終查詢到所有滿足條件的資料的第一個表，

介紹完簡單的陳述句之后，說下我們在這里的優化方案，

常見的子查詢優化

子查詢合并：如果兩個查詢塊語意等價，則能夠將其合并成一個子查詢，這樣多次 TableScan、TableJoin 都可以消減為單表的 Scan、Join，

子查詢展開：又稱為子查詢上拉，把子查詢的查詢謂詞和表提到上層中，變為 join 操作，這樣子查詢就不存在了，連接方法和連接順序也可以隨意調整了，如 Nested-Loop Join 可以換成 Hash Join 等等，我們的 Q4 也就是通過這種方式進行優化的，

針對 Q4 的優化方案

上一段也有說到，針對 Q4，我們需要是子查詢展開優化，就是將子查詢重寫為同語意的 Semi-join(半連接), 然后執行 Semi-join 即可，

mysql 的子查詢展開代碼流程

resolve_subquery :對subqueryitem進行決議，收集能夠unnesting為semi-join的所有subqueryblock，這里有很多的嚴格限制條件(mysql5.7有11個限制條件)，基本來說就是只允許 SPJ 的 subquery 進行 unnesting，具體條件可詳見函式中的代碼及注釋，可以做 unnesting，會把這個 subquery 的 item 物件，加入到外層 select_lex::sj_candidates 中后續使用，無法做 unnesting 的，則呼叫 select_transformer，嘗試做 IN->EXIST 的轉換，

convert_subquery_to_semijoin: 將真正可以展開的(內層有 table)，建立 sj-nest 這個 TABLE_LIST 物件，基本思路就是想將 inner table 放到外層的 Join list 中，內層的謂詞條件都放在外層對應的 ON/WHERE 條件上，sj-nest 是后續優化 Semi-join 的一個重要結構，會用子查詢 SELECT_LEX 中的內容對其進行填充，

我們的優化方案

首先是 MySQL-5.7 只展開 in 子查詢，無法展開 exists 子查詢，而我們的 Q4 就是一個 exists 子查詢；再者我們的 Tianmu 查詢引擎目前沒有執行 Semi-join 流程，所以即使是 in 子查詢也無法在 tianmu 引擎中執行，所以我們的優化方案也就不言自明了，首先在 MySQL-5.7 增加針對 exists 子查詢展開的這個 case，然后讓我們的 tianmu 引擎能夠執行 semi-join，

優化器改寫

我們的 exists 陳述句改寫參照 in 陳述句進行的，但是跟 in 陳述句稍有不同，首先 resolve_subquery 函式中，判斷是 exists 則不進行轉換，這里我們把他加回來；resolve_subquery只是進行的判斷，是否能夠轉換，真正的轉換操作是在 convert_subquery_to_semijoin 函式中進行的，在 convert_subquery_to_semijoin 中，我們把子查詢所有用到的表上提到 sj_nest，把所有的謂詞上提到 sj_cond, in 子查詢因為 in 子查詢是一個謂詞，所以需要針對謂詞進行單獨處理，exists 則不需要，直接上提，但是這里我們還需要做一個操作，就是把子查詢中用到的外表的運算式放到 sj_outer_exprs 中，所有用到內表的運算式放到 sj_inner_exprs 中，這個 mysql 的執行器或者 tianmu 執行器都會用到，我們可以使用 EXPLAIN 陳述句在查詢、除錯我們優化后的陳述句：

select`tpch_db`.`orders`.`o_orderpriority`AS`o_orderpriority`, count(0) AS`order_count`
from`tpch_db`.`orders`semi
         join (`tpch_db`.`lineitem`)
where ((`tpch_db`.`lineitem`.`l_orderkey` = `tpch_db`.`orders`.`o_orderkey`) and
       (`tpch_db`.`orders`.`o_orderdate` >= DATE'1993-07-01') and
       (`tpch_db`.`orders`.`o_orderdate` < < cache > ((DATE'1993-07-01' + interval'3'month))) and
       (`tpch_db`.`lineitem`.`l_commitdate` < `tpch_db`.`lineitem`.`l_receiptdate`))
groupby`tpch_db`.`orders`.`o_orderpriority`
orderby`tpch_db`.`orders`.`o_orderpriority`limit100;
子查詢被成功上提到外層查詢中，接下來只要能夠正確執行 Semi-join 就大功告成了，

Semi-join 的執行策略

MySQL 的 Semi-join 執行策略

Semi-join 的執行概括來看就是想辦法把內層的查詢進行去重，在寫我們自己的 Semi-join 執行前，我們先學習一下 MySQL 中執行的方式，主要有 4 種，分別是：

DuplicateWeedout，使用臨時表針對 join 序列中，join 內表產生的重復部分，做消除處理；內層子查詢的表通過在外層表的 rowid 上建立唯一索引來對重復生成的 country 行資料做去重，

FirstMatch，比較好理解，在選中內部表的第 1 條與外表匹配的記錄后，就跳過后續的匹配程序，從外層表的下一條記錄重新開始，從而也達到了去重的目的，

LooseScan，把 inner-tables 中的第一個表，其資料基于索引進行分組，取每組第一條資料向后做匹配，

Materialize，這個是想法上最直觀的，通過將 inner-table 去重，并固化成臨時表，遍歷 outer-table，然后在固化表上去尋找匹配，

Tianmu 的 Semi-join 執行策略選擇

根據我們的執行引擎特點，最后決定使用實作 DuplicateWeedout 和 Materialize 兩種執行策略，

因為 Tianmu 是列存，內部沒有 row by row 的執行流程，所以放棄了 FirstMatch；而且只有主鍵，沒有索引， LooseScan 其實主要使用索引，所以也放棄這一方案了，

DuplicateWeedout

DuplicateWeedout 方式其實相對比較容易實作，可以復用現有的 inner-join 執行流程，其實 semi-join 跟 inner-join 的主要區別就內表的去重，這個確實是我們的難點，因為 mysql 這里使用了，默認主鍵(rowid)來進行內表的去重，而我們的此概念，所以在這里我們又增加一個限制，就是給必須外表必須包含主鍵，才能子查詢展開，另外一個難點是我們的 group by 處理，因為我們 group by 和 distinct 是同一個算子，而且做不到先去重后聚合這種操作，所以這里我們增加了一個臨時表，專門用來去重，然后再分組聚合，這里又會遇到新的問題，因為 SPJ 和非 SPJ 陳述句用到的 Field 是不同的，例如我們需要將 count(*), min(xxx),avg(xxx) 等 Field 中聚合去掉，保留原始 Field, 然后等去重之后，再添加聚合屬性，細節處理很多，大家可以直接看代碼，

我們來看一個具體例子：

add query table: ./test_db/orders
add query table: ./test_db/lineitem
T:-1 = TABLE_ALIAS(T:1,"lineitem")
T:-2 = TMP_TABLE(T:-1,T:4294967293)                              // -> for distinct tmp table
T:-3 = TABLE_ALIAS(T:0,"orders")
VC:-2.0 = CREATE_VC(T:-2,PHYS_COL(T:-3,A:5))
A:-1 = T:-2.ADD_COLUMN(VC:-2.0,LIST,"o_orderpriority","ALL")
VC:-2.1 = CREATE_VC(T:-2,PHYS_COL(T:-3,A:0))
A:-2 = T:-2.ADD_COLUMN(VC:-2.1,LIST,"o_orderkey","ALL")
VC:-2.2 = CREATE_VC(T:-2,PHYS_COL(T:-3,A:4))
VC:-2.3 = CREATE_VC(T:-2,EXPR("date_literal"))
C:0 = CREATE_CONDS(T:-2,VC:-2.2,>=,VC:-2.3,<null>)
VC:-2.4 = CREATE_VC(T:-2,EXPR("date_add_interval"))
C:0.AND(VC:-2.2,<,VC:-2.4,<null>)
VC:-2.5 = CREATE_VC(T:-2,EXPR("1"))
VC:-2.6 = CREATE_VC(T:-2,EXPR("0"))
C:0.AND(VC:-2.5,<>,VC:-2.6,<null>)
VC:-2.7 = CREATE_VC(T:-2,PHYS_COL(T:-1,A:11))
VC:-2.8 = CREATE_VC(T:-2,PHYS_COL(T:-1,A:12))
C:0.AND(VC:-2.7,<,VC:-2.8,<null>)
VC:-2.9 = CREATE_VC(T:-2,PHYS_COL(T:-1,A:0))
C:1 = CREATE_CONDS(T:-2,VC:-2.1,=,VC:-2.9,<null>)
C:0.AND(C:1)
T:-2.ADD_CONDS(C:0,WHERE)
T:-2.APPLY_CONDS()
T:-2.MODE(DISTINCT,0,0)
T:-4 = TMP_TABLE(T:4294967294)                                   // -> for group by tmp table
VC:-4.0 = CREATE_VC(T:-4,PHYS_COL(T:-2,A:-1))
A:-1 = T:-4.ADD_COLUMN(VC:-4.0,LIST,"o_orderpriority","ALL")
A:-2 = T:-4.ADD_COLUMN(<null>,COUNT,"order_count","ALL")
VC:-4.1 = CREATE_VC(T:-4,PHYS_COL(T:-2,A:-1))
A:-3 = T:-4.ADD_COLUMN(VC:-4.1,GROUP_BY,"null","ALL")
VC:-4.2 = CREATE_VC(T:-4,PHYS_COL(T:-2,A:-1))
A:-4 = T:-4.ADD_COLUMN(VC:-4.2,LIST,"null","ALL")
VC:-4.3 = CREATE_VC(T:-4,PHYS_COL(T:-4,A:-4))
T:-4.ADD_ORDER(VC:-4.3,ASC)
RESULT(T:-4)

從例子中我們可以看到，T:-2 這個臨時表是用來去重的，T:-4 這個臨時表是用來聚合的，最后物化的結果集也是 T:-4 這個臨時表，

Materialize

Materialize 方式是直接將內表進行物化，當然如果內表包含相關條件，則無法直接進行物化，這里需要把需要相關條件提出來，變成外表的 join 條件，注意這里執行器需要 join 的表換成我們為內表創建的臨時表，而不是原來的物理表，這種執行方式不是有必須包含主鍵的限制，但是他有兩個問題，首先是他走了兩遍查詢流程，比 DuplicateWeedout 要慢，然后就是相關條件的提取非常困難，目前還是無法在所有場景下都支持，所以最后的代碼中沒有包含使用 Materialize 方式的代碼，后續如果必須有主鍵這個限制很大，我們會考慮把 Materialize 的方式加回來，但是肯定是能使用 DuplicateWeedout，優先使用 DuplicateWeedout，

總結

通過子查詢優化這個，發現Tianmu引擎中部分陳述句性能慢的原因是優化器還不夠完美，相比其他組件，我們目前的優化器可能沒做那么精致，雖然我們的大部分陳述句性能都不錯，但是遇到個別復雜陳述句時性能卻不夠給力，我們后續會 Tianmu 的 Join order 做優化，敬請期待，

以上就是本次分享，歡迎大家批評指正，我們會持續發布 StoneDB 的研發分享文章，希望能幫助到大家學習資料庫和 StoneDB 的相關知識，

作者：段福相

編輯：宇亭

參考鏈接：

《Semi-join優化執行代碼分析》

https://zhuanlan.zhihu.com/p/382416772
《MySQL是怎樣運行的》
第14章　基于規則的優化

https://book.douban.com/subject/35231266/
《資料庫查詢優化器的藝術》
第11章 MySQL查詢優化器概述

第12章 MySQL查詢優化器相關資料結構
https://book.douban.com/subject/25815707/
StoneDB 2.0 云原生分布式實時 HTAP 架構詳細設計以 RFC 形式持續進行，歡迎大家關注我們最新進展，更歡迎給我們開源協作的模式和方法提出改進意見，一起通過開源的方式共建 StoneDB ~

https://github.com/stoneatom/stonedb/issues/436

StoneDB 代碼已完全在 Github 開源：

https://github.com/stoneatom/stonedb

StoneDB 官網：

https://stonedb.io/

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/539085.html

標籤：其他

上一篇：MySQL弊端凸顯，PostgreSQL將取而代之？

下一篇：mysql 基礎知識

子查詢優化之 Semi-join 優化 | StoneDB 研發分享 #2

緣起