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

来源:https://www.cnblogs.com/stonedb/archive/2022/12/02/16945182.html
-Advertisement-
Play Games

緣起 StoneDB 在列式存儲引擎 Tianmu 的加持下，在大多數場景下相對 MySQL 都會有大幅性能提升。當然，這是需要工程師不斷優化代碼才能做到的，而且，性能好也需要通過基準測試才有說服力，所以我們也會針對 TPC-H 的測試語句進行測試排查，爭取不斷提升 StoneDB 的性能。本文主要 ...


緣起

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 的相關知識。

作者：段福相

編輯：宇亭

參考鏈接：

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

    https://zhuanlan.zhihu.com/p/382416772

  2. 《MySQL是怎樣運行的》
    第14章　基於規則的優化

    https://book.douban.com/subject/35231266/

  3. 《資料庫查詢優化器的藝術》
    第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/


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 架構解析：Dubbo3 應用級服務發現如何應對雙11百萬集群實例
    引言 儘管 redis 是一款非常優秀的 NoSQL 資料庫，但更重要的是，作為使用者我們應該學會在不同的場景中如何更好的使用它，更大的發揮它的價值。主要可以從這四個方面進行優化：Redis鍵值設計、批處理優化、服務端優化、集群配置優化 1. Redis慢查詢日誌使用 Redis 提供了慢日誌命令的 ...
  • MybatisPlus多表連接查詢一對多分頁查詢數據
    一、序言 在日常一線開發過程中，多表連接查詢不可或缺，基於MybatisPlus多表連接查詢究竟該如何實現，本文將帶你找到答案。 在多表連接查詢中，既有查詢單條記錄的情況，又有列表查詢，還有分頁查詢，這些需求與多表連接是什麼關係，又該如何實現，這是本文討論的中心內容。 二、實戰編碼 1、兩個關聯DO ...
  • 使用python玩轉二維碼！速學速用！⛵
    本文講解二維碼的生成與解碼：使用Python工具庫qrcode『構建二維碼』，使用cv2和pyzbar兩類工具庫『解碼二維碼』。二維碼是目前最常使用的快捷信息存儲方式之一，讀完本篇即可掌握這一必備技能！ ...
  • iNeuOS工業互聯網操作系統，腳本化實現設備運行時長和效率計算與統計
    有一個煤礦項目，使用iNeuOS系統時有一個需要是：要統計設備的運行時長，進一步統計設備運行效率。主要是有效分析設備運行狀態，合理的進行節能。iNeuOS本身具備強大的腳本能力，需要現場實施人員有一定腳本編寫能力，如果不具備腳本編寫能力，那麼下麵的模板修改相應的參數即可。 ...
  • .net 溫故知新：【10】.NET ORM框架EFCore使用入門之CodeFirs、DBFirst
    前言：本系列是我自己學習.net相關知識，以便跟上.net跨平臺的步伐，目前工作原因基本在.net Framework4.7以下，所以才有了這一系列的學習總結，但是並不是從基本的C#語法和基礎知識開始的，而是圍繞.net core以後平臺的重要設計和差異進行溫故知新。目的在於通過要點的梳理最後串聯起 ...
  • Linux 基礎-新手必備命令
    Linux 基礎-新手必備命令 概述 常見執行 Linux 命令的格式是這樣的： 命令名稱 [命令參數] [命令對象] 註意，命令名稱、命令參數、命令對象之間請用空格鍵分隔。 命令對象一般是指要處理的文件、目錄、用戶等資源，而命令參數可以用長格式（完整的選項名稱），也可以用短格式（單個字母的縮寫）， ...
  • 1.1 大數據簡介-hadoop-最全最完整的保姆級的java大數據學習資料
    1 hadoop-最全最完整的保姆級的java大數據學習資料 大數據技術解決的是什麼問題？ 大數據技術解決的主要是海量數據的存儲和計算。 Hadoop的廣義和狹義之分 狹義的Hadoop:指的是一個框架，Hadoop是由三部分組成：HDFS：分散式文件系統--> 存儲； MapReduce:分散式離 ...
  • mysql 基礎知識
    學習中的思考 在 mysql 學習和使用中，我遇到了不少的難題，我覺得我應該形成一套邏輯思考體系，可以讓我在初識 mysql 的過程中加入理性思考，從一開始就探求原理，瞭解所學內容的核心和關鍵點，做到一葉知秋而不是只見樹木不見森林。 mysql 幾種數據類型的底層是如何存儲的，不同的 sql 語句對 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類