MySQL8.0 優化器介紹（二）

来源:https://www.cnblogs.com/greatsql/archive/2023/04/17/17325300.html
-Advertisement-
Play Games

GreatSQL社區原創內容未經授權不得隨意使用，轉載請聯繫小編並註明來源。 GreatSQL是MySQL的國產分支版本，使用上與MySQL一致。 作者： 奧特曼愛小怪獸 文章來源：GreatSQL社區投稿 上一篇 MySQL8.0 優化器介紹（一）介紹了成本優化模型的三要素：表關聯順序，與每張表返 ...


  • GreatSQL社區原創內容未經授權不得隨意使用，轉載請聯繫小編並註明來源。
  • GreatSQL是MySQL的國產分支版本，使用上與MySQL一致。
  • 作者： 奧特曼愛小怪獸
  • 文章來源：GreatSQL社區投稿

上一篇 MySQL8.0 優化器介紹（一）介紹了成本優化模型的三要素：表關聯順序，與每張表返回的行數（過濾效率），查詢成本。而join演算法又是影響表關聯效率的首要因素。

join演算法（Join Algorithms）

join在MySQL 是一個如此重要的章節，毫不誇張的說，everything is a join。

截止到本文寫作時，MySQL8.0.32 GA已經發行，這裡主要介紹三大join：NL（Nested Loop），BNL（Block Nested Loop）,HASH JOIN

嵌套迴圈（Nested Loop）

MySQL5.7之前，都只有NL，它實現簡單，適合索引查找。

幾乎每個人都可以手動實現一個NL。

SELECT CountryCode, 
       country.Name AS Country,  
       city.Name AS City, 
       city.District  
  FROM world.country  
  INNER JOIN world.city  
    ON city.CountryCode = country.Code  
  WHERE Continent = 'Asia'; 
  
  ##執行計劃類似如下：
  -> Nested loop inner join
     -> Filter: (country.Continent = 'Asia')
         -> Table scan on country
     -> Index lookup on city using CountryCode
     (CountryCode=country.`Code`)
     
 ##python 代碼實現一個NL
 result = []
 for country_row in country:
     if country_row.Continent == 'Asia':
         for city_row in city.CountryCode['country_row.Code']:
             result.append(join_rows(country_row, city_row))

圖示化一個NL

image-20230417112154499

NL的限制：通常多個表join，小表在前做驅動表，被驅動表有索引檢索，效率會高一些。（官方手冊上沒有full outer join ,full join 語法，實際支持full join）

舉個例子 多表join 且關聯表不走索引：

#人為干預計劃，走性能最差的執行路徑。
SELECT /*+ NO_BNL(city) */
       CountryCode, 
       country.Name AS Country,
       city.Name AS City, 
       city.District
  FROM world.country IGNORE INDEX (Primary)
  INNER JOIN world.city IGNORE INDEX (CountryCode)
    ON city.CountryCode = country.Code
  WHERE Continent = 'Asia';
  
  SELECT rows_examined, rows_sent,
         last_statement_latency AS latency
    FROM sys.session
   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G
**************************** 1. row ****************************
rows_examined: 208268
 rows_sent: 1766
 latency: 44.83 ms
 
 ##對比一下優化器 自動優化後的
 SELECT CountryCode, 
       country.Name AS Country,
       city.Name AS City, 
       city.District
  FROM world.country 
  INNER JOIN world.city 
    ON city.CountryCode = country.Code
  WHERE Continent = 'Asia';
  
  SELECT rows_examined, rows_sent,
         last_statement_latency AS latency
    FROM sys.session
   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G
*************************** 1. row ***************************
rows_examined: 2005
 rows_sent: 1766
 latency: 4.36 ms
1 row in set (0.0539 sec)

塊嵌套迴圈（Block Nested Loop）

塊嵌套迴圈演算法是嵌套迴圈演算法的擴展。它也被稱為BNL演算法。連接緩衝區用於收集儘可能多的行，併在第二個表的一次掃描中比較所有行，而不是逐個提交第一個表中的行。這可以大大提高NL在某些查詢上的性能。

hash join是在MySQL8.0.18引進的，下麵的sql，使用了NO_HASH_JOIN(country,city) 的提示，並且兩表的join 欄位上的索引被忽略，目的是為了介紹BNL特性。

SELECT /*+ NO_HASH_JOIN(country,city) */
       CountryCode, 
       country.Name AS Country,
       city.Name AS City, 
       city.District
 FROM world.country IGNORE INDEX (Primary)
 INNER JOIN world.city IGNORE INDEX (CountryCode)
   ON city.CountryCode = country.Code
WHERE Continent = 'Asia';

##使用python偽代碼來解釋一下 BNL
result = []
join_buffer = []
for country_row in country:
     if country_row.Continent == 'Asia':
     join_buffer.append(country_row.Code)
     if is_full(join_buffer):
         for city_row in city:
             CountryCode = city_row.CountryCode
             if CountryCode in join_buffer:
                 country_row = get_row(CountryCode)
                 result.append(
                     join_rows(country_row, city_row))
             join_buffer = []
if len(join_buffer) > 0:
     for city_row in city:
     CountryCode = city_row.CountryCode
     if CountryCode in join_buffer:
         country_row = get_row(CountryCode)
         result.append(join_rows(country_row, city_row))
   join_buffer = []

圖示化一個BNL

圖片

註意圖裡的join_buffer,在MySQL5.7上使用sysbench壓測讀寫場景，壓力上不去，主要就是因為BNL 演算法下，join_buffer_size的設置為預設值。適當調整幾個buffer後，tps得到顯著提高。join buffer對查詢影響，也可以用下麵的例子做一個量化說明。

SELECT /*+ NO_HASH_JOIN(country,city) */
       CountryCode, 
       country.Name AS Country,
       city.Name AS City, 
       city.District
 FROM world.country IGNORE INDEX (Primary)
 INNER JOIN world.city IGNORE INDEX (CountryCode)
   ON city.CountryCode = country.Code
WHERE Continent = 'Asia';

 SELECT rows_examined, rows_sent,
         last_statement_latency AS latency
    FROM sys.session
   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G
*************************** 1. row ***************************
rows_examined: 4318
 rows_sent: 1766
 latency: 16.87 ms
1 row in set (0.0490 sec)

#人為干預計劃，走性能最差的執行路徑。
SELECT /*+ NO_BNL(city) */
       CountryCode, 
       country.Name AS Country,
       city.Name AS City, 
       city.District
  FROM world.country IGNORE INDEX (Primary)
  INNER JOIN world.city IGNORE INDEX (CountryCode)
    ON city.CountryCode = country.Code
  WHERE Continent = 'Asia';
  
  SELECT rows_examined, rows_sent,
         last_statement_latency AS latency
    FROM sys.session
   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G
**************************** 1. row ****************************
rows_examined: 208268
 rows_sent: 1766
 latency: 44.83 ms
 
 在兩表join，且join欄位不使用索引的前提下，BNL +join_buffer 性能遠大於 NL

使用BNL 有幾個點需要註意。（我實在懶得全文翻譯官方文檔了）

  • Only the columns required for the join are stored in the join buffer. This means that you will need less memory for the join buffer than you may at first expect. （不需要配置太高buffer)
  • The size of the join buffer is configured with the join_buffer_size variable. The value of join_buffer_size is the minimum size of the buffer! Even if less than 1 KiB of country code values will be stored in the join buffer in the discussed example, if join_buffer_size is set to 1 GiB, then 1 GiB will be allocated. For this reason, keep the value of join_buffer_size low and only increase it as needed.
  • One join buffer is allocated per join using the block nested loop algorithm.
  • Each join buffer is allocated for the entire duration of the query.
  • The block nested loop algorithm can be used for full table scans, full index scans, and range scans.(適用table access 方式）
  • The block nested loop algorithm will never be used for constant tables as well as the first nonconstant table. This means that it requires a join between two tables with more than one row after filtering by unique indexes to use the block nested loop algorithm

可以通過 optimizer switch 配置BNL() 、 NO_BNL()

BNL 特別擅長在non-indexed joins 的場景，很多時候性能優於hash join。As of version 8.0.20, block nested-loop joins are no longer used; instead, a hash join has replaced it.

哈希join （Hash Join）

圖片

Hash Join 作為大殺器在 MySQL8.0.18引入，期間有過引起記憶體和文件句柄大量消耗的線上問題，但是不妨礙它作為一個join演算法的重大突破，特別適合大表與大表的無索引join。某些場景甚至比NL+index join 更快。（當然比起oracle 上的hash join 依然弱爆了，40w * 40w 的大表查詢，MySQL優化到極致在10s左右，oracle在1s 水平，相差一個數量級。

思考：MySQL、Oracle都是hash join，為何差距如此大？MySQL hash join 可以哪些方面進行性能提高？

業界主要有兩大方向

  1. 單線程hash優化演算法和數據結構
  2. NUMA架構下，多線程Hash Join的優化主要是能夠讓讀寫數據儘量發生在當前NUMA node

參考文檔（https://zhuanlan.zhihu.com/p/589601705）

大家不妨看看 MySQL工程師的worklog， 內容很精彩（https://dev.mysql.com/worklog/task/?id=2241）

可以看出國外大廠強大的標準化的it生產能力，一個功能從需求到實現經歷了哪些關鍵步驟。

MySQL 的Hash join是一個記憶體hash+磁碟hash的混合擴展。為了不讓hash join 溢出join buffer,需要加大記憶體設置，使用磁碟hash時，需要配置更多的文件句柄數。儘管有disk hash ，但實際幹活的還是in-memory hash。

記憶體hash 有兩個階段：

  1. build phase. One of the tables in the join is chosen as the build table. The hash is calculated for the columns required for the join and loaded into memory.
  2. probe phase. The other table in the join is the probe input. For this table, rows are read one at a time, and the hash is calculated. Then a hash key lookup is performed on the hashes calculated from the build table, and the result of the join is generated from the matching rows.

當hashes of build table 不足以全部放進記憶體時，MySQL會自動切換到on-disk的擴展實現（基於 GRACE hash join algorithm）。在build phase階段，join buffer滿，就會發生 in-mem hash 向on-disk hash 轉換。

on-disk algorithm 包含3個步驟：

  1. Calculate the hashes of all rows in both the build and probe tables and store them on disk in several small files partitioned by the hash. The number of partitions is chosen to make each partition of the probe table fit into the join buffer but with a limit of at most 128 partitions.
  2. Load the first partition of the build table into memory and iterate over the hashes from the probe table in the same way as for the probe phase for the in-memory algorithm. Since the partitioning in step 1 uses the same hash function for both the build and probe tables, it is only necessary to iterate over the first partition of the probe table.
  3. Clear the in-memory buffer and continue with the rest of the partitions one by one

無論是記憶體hash還是磁碟hash，都使用xxHash64 hash function。xxHash64有足夠快，hash質量好（reducing the number of hash collisions）的特點

BNL不會被選中的時候，MySQL就會選用hash join。

在整理這篇資料時，對要使用的哈希連接演算法存在以下要求：

  • The join must be an inner join.
  • The join cannot be performed using an index, either because there is no available index or because the indexes have been disabled for the query.
  • All joins in the query must have at least one equi-join condition between the two tables in the join, and only columns from the two tables as well as constants are referenced in the condition. （查詢中的所有聯接必須在聯接中的兩個表之間至少有一個等聯接條件，並且在該條件中僅引用兩個表中的列以及常量）
  • As of 8.0.20, anti, semi, and outer joins are also supported. If you join the two tables t1 and t2, then examples of join conditions that are supported for hash join include
  • t1.t1_val = t2.t2_val
  • t1.t1_val = t2.t2_val + 2
  • t1.t1_val1 = t2.t2_val AND t1.t1_val2 > 100
  • MONTH(t1.t1_val) = MONTH(t2.t2_val)

用一個例子來說明一下hash join：

SELECT CountryCode, 
       country.Name AS Country,
       city.Name AS City, 
       city.District
 FROM world.country IGNORE INDEX (Primary)
 INNER JOIN world.city IGNORE INDEX (CountryCode)
   ON city.CountryCode = country.Code
WHERE Continent = 'Asia';

#用一段偽代碼翻譯一下
result = []
join_buffer = []
partitions = 0
on_disk = False
for country_row in country:
     if country_row.Continent == 'Asia':
         hash = xxHash64(country_row.Code)
         if not on_disk:
             join_buffer.append(hash)
             if is_full(join_buffer):
             # Create partitions on disk
               on_disk = True
               partitions = write_buffer_to_disk(join_buffer)
               join_buffer = []
         else
             write_hash_to_disk(hash)
             
if not on_disk:
     for city_row in city:
         hash = xxHash64(city_row.CountryCode)
         if hash in join_buffer:
             country_row = get_row(hash)
             city_row = get_row(hash)
             result.append(join_rows(country_row, city_row))
else:
     for city_row in city:
         hash = xxHash64(city_row.CountryCode)
         write_hash_to_disk(hash)
         
     for partition in range(partitions):
         join_buffer = load_build_from_disk(partition)
         for hash in load_hash_from_disk(partition):
         if hash in join_buffer:
             country_row = get_row(hash)
             city_row = get_row(hash)
             result.append(join_rows(country_row, city_row))
 join_buffer = []

與所使用的實際演算法相比，所描述的演算法稍微簡化了一些。
真正的演算法必須考慮哈希衝突，
而對於磁碟上的演算法，某些分區可能會變得太大而無法放入連接緩衝區，
在這種情況下，它們會被分塊處理，以避免使用比配置的記憶體更多的記憶體

圖示化一下 in-mem hash 演算法：

圖片

量化一下hash join 的成本

SELECT CountryCode, 
       country.Name AS Country,
       city.Name AS City, 
       city.District
 FROM world.country IGNORE INDEX (Primary)
 INNER JOIN world.city IGNORE INDEX (CountryCode)
   ON city.CountryCode = country.Code
WHERE Continent = 'Asia';

SELECT rows_examined, rows_sent,
         last_statement_latency AS latency
    FROM sys.session
   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G
**************************** 1. row ****************************
rows_examined: 4318
 rows_sent: 1766
 latency: 3.53 ms

從本文的例子中，rows_examined 的角度來看 index_join 下的NL（2005） 優於 無索引join條件下的BNL (4318）= 無索引join條件下的 hash join。但是當數據量發生變化，可能結果就不一樣了，現實中也沒有絕對的性能好壞規則（如果有，基於規則的成本計算就能很好處理的查詢問題，實際上更值得信賴的是成本估算），hash join與NL,BNL 的優越比較，列出幾點，當作紙上談兵 ：

Hash Join 最大的好處在於提升多表無索引關聯時的查詢性能。具體NL,BNL,HASH JOIN誰更適合用於查詢計劃，實踐才是最好的證明。

同樣可以使用HASH_JOIN() 和 NO_HASH_JOIN() 的hint 來影響查詢計劃。

MySQL8.0 關於支持的三種high-level 連接策略的討論暫時到此結束。下來可以自己去查一下 anti, semi, and outer joins。

更多細節 參考

（https://dev.mysql.com/doc/refman/8.0/en/select-optimization.html）（https://dev.mysql.com/doc/refman/8.0/en/semijoins.html）

還有一些 關於join的lower-level優化值得考慮，下篇文章分解。

Enjoy GreatSQL

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

-Advertisement-
Play Games
更多相關文章
  • 面試題百日百刷-kafka篇(四)
    **鎖屏面試題百日百刷，每個工作日堅持更新面試題。**請看到最後就能獲取你想要的, 接下來的是今日的面試題： 1.為什麼kafka可以實現高吞吐？單節點kafka的吞吐量也比其他消息隊列大，為什麼？ Kafka是分散式消息系統，需要處理海量的消息，Kafka的設計是把所有的消息都寫入速度低容量大的硬 ...
  • Redis---數據持久化之RDB與AOF
    一、數據持久化之RDB 1、RDB介紹 Redis 資料庫文件，全稱 Redis DataBase，數據持久化方式之一，數據持久化預設方式，按照指定時間間隔，將記憶體中的數據及快照寫入硬碟 定義RDB文件名 dbfilename "dump.rdb" RDB指dump.rdb文件; redis數據每次 ...
  • day03-Redis的客戶端
    Redis的Java客戶端 在Redis官網中提供了各種語言的客戶端，地址：Get started using Redis clients | Redis Redis的Java客戶端： 1.Jedis Jedis 的官方地址：redis/jedis: Redis Java client design ...
  • Redis --- 數據類型之列表 數據類型之hash
    一、數據類型之列表 列表簡介 Redis的list是一個字元隊列，先進後出，一個key可以有多個值 列表操作 lpush key values [value ...] 將一個或多個值value插入到列表key的表頭，Key不存在，則創建key 127.0.0.1:6379> FLUSHALL OK ...
  • 連接MongoDB+Docker安裝MongoDB
    一、連接MongoDB 工具：==studio 3T== 下載：https://studio3t.com/download-thank-you/?OS=win64 1、無設置密碼 最終成功頁面 2、設置了密碼 後續同1 二、安裝 MongoDB版本：5.0.5 參考： https://www.cnb ...
  • CentOS7---部署LNMP數據存儲到redis
    一、部署LNMP及redis 1、部署LNMP，需要將 tengine-2.2.0.tar.gz 拷貝到虛擬機的 /root 目錄下 步驟一：安裝nginx 源碼安裝相關軟體包 # pcre-devel做正則匹配，zlib-devel做數據壓縮 [root@template ~]# yum -y i ...
  • 袋鼠雲春季生長大會最新議程來啦！4月20日我們雲上見
    如今，數字經濟正逐步走向深化應用、規範發展、普惠共用的新階段，數字經濟與實體經濟深度融合、基礎軟體國產化替代成為數字時代主潮流。數字工具如何讓千行百業共同實現韌性生長？ 「 2023 袋鼠雲春季生長大會」乘風而起，帶來數實融合趨勢下的產品煥新升級剖析、前瞻行業視覺解讀、最佳數字實踐分享，助力各大產業 ...
  • 發現Mysql的主從資料庫沒有同步，差點涼涼了
    摘要：今天發現Mysql的主從資料庫沒有同步，瞬間整個人頭皮發麻。 本文分享自華為雲社區《糟了，生產環境數據竟然不一致，人麻了！》，作者：冰 河 。 今天發現Mysql的主從資料庫沒有同步 先上Master庫： mysql>show processlist; 查看下進程是否Sleep太多。發現很正常 ...
一周排行
    -Advertisement-
    Play Games
  • C# + WPF 音頻播放器 界面優雅，體驗良好
    前言 本文介紹一款使用 C# 與 WPF 開發的音頻播放器，其界面簡潔大方，操作體驗流暢。該播放器支持多種音頻格式（如 MP4、WMA、OGG、FLAC 等），並具備標記、實時歌詞顯示等功能。 另外，還支持換膚及多語言（中英文）切換。核心音頻處理採用 FFmpeg 組件，獲得了廣泛認可，目前 Git ...
  • OAuth2.0授權-gitee授權碼模式
    OAuth2.0授權驗證-gitee授權碼模式 本文主要介紹如何筆者自己是如何使用gitee提供的OAuth2.0協議完成授權驗證並登錄到自己的系統，完整模式如圖 1、創建應用 打開gitee個人中心->第三方應用->創建應用 創建應用後在我的應用界面，查看已創建應用的Client ID和Clien ...
  • FastReport.OpenSource .Net下開源免費報表列印組件
    解決了這個問題：《winForm下，fastReport.net 從.net framework 升級到.net5遇到的錯誤“Operation is not supported on this platform.”》 本文內容轉載自：https://www.fcnsoft.com/Home/Sho ...
  • 如何在 ASP.NET Core Web API 方法執行前後 “偷偷“ 作一些 “壞“ 事？初識 ActionFilterAttribute
    國內文章 WPF 從裸 Win 32 的 WM_Pointer 消息獲取觸摸點繪製筆跡 https://www.cnblogs.com/lindexi/p/18390983 本文將告訴大家如何在 WPF 裡面，接收裸 Win 32 的 WM_Pointer 消息，從消息裡面獲取觸摸點信息，使用觸摸點 ...
  • 在 ASP.NET Core Web API 中使用異常篩選器捕獲和統一處理異常
    前言 給大家推薦一個專為新零售快消行業打造了一套高效的進銷存管理系統。 系統不僅具備強大的庫存管理功能，還集成了高性能的輕量級 POS 解決方案，確保頁面載入速度極快，提供良好的用戶體驗。 項目介紹 Dorisoy.POS 是一款基於 .NET 7 和 Angular 4 開發的新零售快消進銷存管理 ...
  • AbpHelper CLI積累與實戰分享
    ABP CLI常用的代碼分享 一、確保環境配置正確 安裝.NET CLI： ABP CLI是基於.NET Core或.NET 5/6/7等更高版本構建的，因此首先需要在你的開發環境中安裝.NET CLI。這可以通過訪問Microsoft官網下載並安裝相應版本的.NET SDK來實現。 安裝ABP ...
  • 記一次HttpClient使用問題分析
    問題 問題是這樣的：第三方的webapi，需要先調用登陸介面獲取Cookie，訪問其它介面時攜帶Cookie信息。 但使用HttpClient類調用登陸介面，返回的Headers中沒有找到Cookie信息。 分析 首先，使用Postman測試該登陸介面，正常返回Cookie信息，說明是HttpCli ...
  • .NET周刊【9月第3期 2024-09-15】
    國內文章 關於.NET在中國為什麼工資低的分析 https://www.cnblogs.com/thinkingmore/p/18406244 .NET在中國開發者的薪資偏低，主要因市場需求、技術棧選擇和企業文化等因素所致。歷史上，.NET曾因微軟的閉源策略發展受限，儘管後來推出了跨平臺的.NET ...
  • 我的網站集成ElasticSearch初體驗
    在WPF開發應用中，動畫不僅可以引起用戶的註意與興趣，而且還使軟體更加便於使用。前面幾篇文章講解了畫筆（Brush），形狀（Shape），幾何圖形（Geometry），變換（Transform）等相關內容，今天繼續講解動畫相關內容和知識點，僅供學習分享使用，如有不足之處，還請指正。 ...
  • 第23篇 委托的概述
    什麼是委托？ 委托可以說是把一個方法代入另一個方法執行，相當於指向函數的指針；事件就相當於保存委托的數組； 1.實例化委托的方式： 方式1：通過new創建實例： public delegate void ShowDelegate(); 或者 public delegate string ShowDe ...
所有分類