緣起

StoneDB 在列式存儲(chǔ)引擎 Tianmu 的加持下，在大多數(shù)場(chǎng)景下相對(duì) MySQL 都會(huì)有大幅性能提升。當(dāng)然，這是需要工程師不斷優(yōu)化代碼才能做到的，而且，性能好也需要通過(guò)基準(zhǔn)測(cè)試才有說(shuō)服力，所以我們也會(huì)針對(duì) TPC-H 的測(cè)試語(yǔ)句進(jìn)行測(cè)試排查，爭(zhēng)取不斷提升 StoneDB 的性能。本文主要講解對(duì) TPCH_Q4 的分析優(yōu)化，在這個(gè)優(yōu)化過(guò)程中，我們涉及到了對(duì)子查詢中的 Semi-join 優(yōu)化。

首先看一下 Q4 的查詢語(yǔ)句，比較簡(jiǎn)單：

可以看到，這個(gè)語(yǔ)句中只有兩個(gè)查詢表, 4 個(gè)謂詞條件，特點(diǎn)是在子查詢中使用了外表的字段，我們也管這種叫做相關(guān)子查詢，而在驅(qū)動(dòng)表里則使用了聚合。

這里科普一下，驅(qū)動(dòng)表（Driving Table），也稱外層表（Outer Table）,顧名思義，驅(qū)動(dòng)表是用來(lái)驅(qū)動(dòng)查詢的。驅(qū)動(dòng)表僅僅用于 Nested-Loop Join 和 Hash Join，簡(jiǎn)單來(lái)說(shuō)，就是用來(lái)最先獲得數(shù)據(jù)，并以此表的數(shù)據(jù)為依據(jù)，逐步獲得其他表的數(shù)據(jù)，直至最終查詢到所有滿足條件的數(shù)據(jù)的第一個(gè)表。

介紹完簡(jiǎn)單的語(yǔ)句之后，說(shuō)下我們?cè)谶@里的優(yōu)化方案。

常見(jiàn)的子查詢優(yōu)化

子查詢合并：如果兩個(gè)查詢塊語(yǔ)義等價(jià)，則能夠?qū)⑵浜喜⒊梢粋€(gè)子查詢，這樣多次 TableScan、TableJoin 都可以消減為單表的 Scan、Join。

子查詢展開(kāi)：又稱為子查詢上拉，把子查詢的查詢謂詞和表提到上層中，變?yōu)?join 操作，這樣子查詢就不存在了，連接方法和連接順序也可以隨意調(diào)整了，如 Nested-Loop Join 可以換成 Hash Join 等等，我們的 Q4 也就是通過(guò)這種方式進(jìn)行優(yōu)化的。

針對(duì) Q4 的優(yōu)化方案

上一段也有說(shuō)到，針對(duì) Q4，我們需要是子查詢展開(kāi)優(yōu)化。就是將子查詢重寫(xiě)為同語(yǔ)義的 Semi-join(半連接), 然后執(zhí)行 Semi-join 即可。

mysql 的子查詢展開(kāi)代碼流程

resolve_subquery :對(duì)subqueryitem進(jìn)行解析，收集能夠unnesting為semi-join的所有subqueryblock，這里有很多的嚴(yán)格限制條件(mysql5.7有11個(gè)限制條件)，基本來(lái)說(shuō)就是只允許 SPJ 的 subquery 進(jìn)行 unnesting，具體條件可詳見(jiàn)函數(shù)中的代碼及注釋?？梢宰?unnesting，會(huì)把這個(gè) subquery 的 item 對(duì)象，加入到外層 select_lex::sj_candidates 中后續(xù)使用，無(wú)法做 unnesting 的，則調(diào)用 select_transformer，嘗試做 IN->EXIST 的轉(zhuǎn)換。

convert_subquery_to_semijoin:?將真正可以展開(kāi)的(內(nèi)層有 table)，建立 sj-nest 這個(gè) TABLE_LIST 對(duì)象， 基本思路就是想將 inner table 放到外層的 Join list 中， 內(nèi)層的謂詞條件都放在外層對(duì)應(yīng)的 ON/WHERE 條件上。sj-nest 是后續(xù)優(yōu)化 Semi-join 的一個(gè)重要結(jié)構(gòu)，會(huì)用子查詢 SELECT_LEX 中的內(nèi)容對(duì)其進(jìn)行填充。

我們的優(yōu)化方案

首先是 MySQL-5.7 只展開(kāi) in 子查詢，無(wú)法展開(kāi) exists 子查詢，而我們的 Q4 就是一個(gè) exists 子查詢；再者我們的 Tianmu 查詢引擎目前沒(méi)有執(zhí)行 Semi-join 流程，所以即使是 in 子查詢也無(wú)法在 tianmu 引擎中執(zhí)行。所以我們的優(yōu)化方案也就不言自明了，首先在 MySQL-5.7 增加針對(duì) exists 子查詢展開(kāi)的這個(gè) case，然后讓我們的 tianmu 引擎能夠執(zhí)行 semi-join。

優(yōu)化器改寫(xiě)

我們的 exists 語(yǔ)句改寫(xiě)參照 in 語(yǔ)句進(jìn)行的，但是跟 in 語(yǔ)句稍有不同。首先 resolve_subquery 函數(shù)中，判斷是 exists 則不進(jìn)行轉(zhuǎn)換，這里我們把他加回來(lái)；resolve_subquery只是進(jìn)行的判斷，是否能夠轉(zhuǎn)換，真正的轉(zhuǎn)換操作是在 convert_subquery_to_semijoin 函數(shù)中進(jìn)行的，在 convert_subquery_to_semijoin 中，我們把子查詢所有用到的表上提到 sj_nest，把所有的謂詞上提到 sj_cond, in 子查詢因?yàn)?in 子查詢是一個(gè)謂詞，所以需要針對(duì)謂詞進(jìn)行單獨(dú)處理，exists 則不需要，直接上提。但是這里我們還需要做一個(gè)操作，就是把子查詢中用到的外表的表達(dá)式放到 sj_outer_exprs 中，所有用到內(nèi)表的表達(dá)式放到 sj_inner_exprs 中，這個(gè) mysql 的執(zhí)行器或者 tianmu 執(zhí)行器都會(huì)用到。我們可以使用 EXPLAIN 語(yǔ)句在查詢、調(diào)試我們優(yōu)化后的語(yǔ)句：

子查詢被成功上提到外層查詢中，接下來(lái)只要能夠正確執(zhí)行 Semi-join 就大功告成了。

Semi-join 的執(zhí)行策略

MySQL 的 Semi-join 執(zhí)行策略

Semi-join 的執(zhí)行概括來(lái)看就是想辦法把內(nèi)層的查詢進(jìn)行去重。在寫(xiě)我們自己的 Semi-join 執(zhí)行前，我們先學(xué)習(xí)一下 MySQL 中執(zhí)行的方式，主要有 4 種，分別是：

1. DuplicateWeedout，使用臨時(shí)表針對(duì) join 序列中，join 內(nèi)表產(chǎn)生的重復(fù)部分，做消除處理；內(nèi)層子查詢的表通過(guò)在外層表的 rowid 上建立唯一索引來(lái)對(duì)重復(fù)生成的 country 行數(shù)據(jù)做去重。

2. FirstMatch，比較好理解，在選中內(nèi)部表的第 1 條與外表匹配的記錄后，就跳過(guò)后續(xù)的匹配過(guò)程，從外層表的下一條記錄重新開(kāi)始，從而也達(dá)到了去重的目的。

3. LooseScan，把 inner-tables 中的第一個(gè)表，其數(shù)據(jù)基于索引進(jìn)行分組，取每組第一條數(shù)據(jù)向后做匹配。

4. Materialize，這個(gè)是想法上最直觀的，通過(guò)將 inner-table 去重，并固化成臨時(shí)表，遍歷 outer-table，然后在固化表上去尋找匹配。

Tianmu 的 Semi-join 執(zhí)行策略選擇

根據(jù)我們的執(zhí)行引擎特點(diǎn)，最后決定使用實(shí)現(xiàn) DuplicateWeedout 和 Materialize 兩種執(zhí)行策略。

因?yàn)?Tianmu 是列存，內(nèi)部沒(méi)有 row by row 的執(zhí)行流程，所以放棄了 FirstMatch；而且只有主鍵，沒(méi)有索引， LooseScan 其實(shí)主要使用索引，所以也放棄這一方案了。

DuplicateWeedout

DuplicateWeedout 方式其實(shí)相對(duì)比較容易實(shí)現(xiàn)，可以復(fù)用現(xiàn)有的 inner-join 執(zhí)行流程，其實(shí) semi-join 跟 inner-join 的主要區(qū)別就內(nèi)表的去重，這個(gè)確實(shí)是我們的難點(diǎn)，因?yàn)?mysql 這里使用了，默認(rèn)主鍵(rowid)來(lái)進(jìn)行內(nèi)表的去重，而我們的此概念，所以在這里我們又增加一個(gè)限制，就是給必須外表必須包含主鍵，才能子查詢展開(kāi)。另外一個(gè)難點(diǎn)是我們的 group by 處理，因?yàn)槲覀?group by 和 distinct 是同一個(gè)算子，而且做不到先去重后聚合這種操作，所以這里我們?cè)黾恿艘粋€(gè)臨時(shí)表，專(zhuān)門(mén)用來(lái)去重，然后再分組聚合，這里又會(huì)遇到新的問(wèn)題，因?yàn)?SPJ 和 非 SPJ 語(yǔ)句用到的 Field 是不同的， 例如我們需要將 count(*), min(xxx),avg(xxx) 等 Field 中聚合去掉，保留原始 Field, 然后等去重之后，再添加聚合屬性。細(xì)節(jié)處理很多，大家可以直接看代碼。

我們來(lái)看一個(gè)具體例子：

從例子中我們可以看到，T:-2 這個(gè)臨時(shí)表是用來(lái)去重的，T:-4 這個(gè)臨時(shí)表是用來(lái)聚合的，最后物化的結(jié)果集也是 T:-4 這個(gè)臨時(shí)表。

Materialize

Materialize 方式是直接將內(nèi)表進(jìn)行物化，當(dāng)然如果內(nèi)表包含相關(guān)條件，則無(wú)法直接進(jìn)行物化，這里需要把需要相關(guān)條件提出來(lái)，變成外表的 join 條件，注意這里執(zhí)行器需要 join 的表?yè)Q成我們?yōu)閮?nèi)表創(chuàng)建的臨時(shí)表，而不是原來(lái)的物理表。這種執(zhí)行方式不是有必須包含主鍵的限制，但是他有兩個(gè)問(wèn)題，首先是他走了兩遍查詢流程，比 DuplicateWeedout 要慢，然后就是相關(guān)條件的提取非常困難，目前還是無(wú)法在所有場(chǎng)景下都支持， 所以最后的代碼中沒(méi)有包含使用 Materialize 方式的代碼，后續(xù)如果必須有主鍵這個(gè)限制很大，我們會(huì)考慮把 Materialize 的方式加回來(lái)，但是肯定是能使用 DuplicateWeedout， 優(yōu)先使用 DuplicateWeedout。

總結(jié)

通過(guò)子查詢優(yōu)化這個(gè)，發(fā)現(xiàn)Tianmu引擎中部分語(yǔ)句性能慢的原因是優(yōu)化器還不夠完美，相比其他組件，我們目前的優(yōu)化器可能沒(méi)做那么精致，雖然我們的大部分語(yǔ)句性能都不錯(cuò)，但是遇到個(gè)別復(fù)雜語(yǔ)句時(shí)性能卻不夠給力。我們后續(xù)會(huì) Tianmu 的 Join order 做優(yōu)化，敬請(qǐng)期待。

以上就是本次分享，歡迎大家批評(píng)指正，我們會(huì)持續(xù)發(fā)布 StoneDB 的研發(fā)分享文章，希望能幫助到大家學(xué)習(xí)數(shù)據(jù)庫(kù)和 StoneDB 的相關(guān)知識(shí)。

作者：段福相

編輯：宇亭