MySQL Join原理分析（緩衝塊嵌套與索引嵌套迴圈）

場景假設

A表（1000條數據）left join B表（1000條數據）。

嵌套迴圈（Nested-Loop Join）

• 極簡概括：顧名思義多層迴圈疊加，由於MySQL條數數量有限，所用for迴圈而不用while，在MySQL中就是多層for迴圈。
• 性能問題：MySQL使用這種作為join方式最簡單，A表joinB表每次join查詢都需要一百萬次內部關聯，每次關聯都需要取一條數據，進行一次IO，若要再關聯C表的1000條，得10億次內部查詢，每個表的數量不過1k，因此需要優化演算法。
• 附加概念
  • 外層迴圈：從外表中選擇一行。
  • 內層迴圈：對於一行外表的一次迴圈，MySQL會在內表中逐行搜索匹配的行。

緩衝塊

• 極簡概括：緩衝塊指的是記憶體中的數據塊，當資料庫進行讀取或寫入操作時，通常會將數據載入到緩衝塊中進行處理，以減少對磁碟的訪問頻率，類比開發中的Redis的作用。

緩衝款嵌套迴圈（Block Nested-Loop Join）

• 極簡概括：取出一批數據放入記憶體中，再對這一批數據進行匹配操作，分批處理（若放不下）+記憶體的性能優勢，能減少io操作。
• 補充：這塊記憶體有個專業的名詞，叫做join buffer，使用show variables like 'join_buffer%'便可查看大小（預設256KB）。可以隨便找一個或者兩個表試一試，將無索引的列作為join on的關係關聯起來，用explain 查看Extra列，就會顯示Using join buffer (Block Nested Loop)。

索引嵌套迴圈（Index Nested-Loop Join）

• 前提：所被關聯的列，必須有索引。
• 原理：利用B+tree的非線性多路查找思路快速定位目標數據，定位到的數據作為主動關聯（A表）或者被關聯（B表）的成員，這意味著不用逐行遍歷，從而提升性能。
• 舉例：A 關聯 B，假設通過id欄位關聯，原先需要百萬次的內部關聯，受where條件影響（實際開發大概率會用），只查詢出了50條結果。
• 逐步剖析（包含主觀推理，實際情況有待考證）：
  1. 通過下文，知道SQL執行的順序是from->join->on->where->group by->having->select->order by->limit，因此會生成一個百萬級的臨時表（此時還沒有走到過濾或篩選操作的逐行對比流程）。
     但是也不一定，MySQL優化器會根據當前的索引和數據情況，也可能先把A或B表where後內部產生的臨時表（50條），再與另一張表join，從而優化性能，（MySQL優化器為了性能，可以不按照SQL國際標準來運行，這種概率較大）。
  2. 篩選出來50條數據作為臨時表，進行下游環節的處理。
  3. 分析第1步的內部行為：從下文知道1000條數據，MySQL B+tree大概率為2層，也就是50*2 = 100次IO（在樹上查找），然後根據這50條數據join另一張表，由於關聯欄位都是加索引的id欄位，所以另一張表的演算法一致，另一張表也經歷了100次內部IO，所以加起來是200次內部IO，也可以近似的理解為200次內部關聯。

SQL執行順序的邏輯

1. from用於確定操作對象，放第一位毋庸置疑。
2. join和on用於關聯，後面的各種處理邏輯依附於關聯後內部創建的臨時表，先生成數據集，才能為後續處理做基礎。
3. where用於篩選，可以減少後續操作的數據量，提高查詢性能。
4. group by用於對數據進行分類彙總，不放where前面，是為了避免分組後的數據被where過濾掉（分組分了個寂寞），造成算力浪費和記憶體資源（數據量大還是很消耗算力和記憶體的）的問題。
5. having用於對分組結果進行過濾，所以要在group by之後。
6. select用於決定迭代顯示那些列，而不是限制只有這些列才可以參與處理，上游的各種操作（如複雜的where條件）不能受7. select欄位的影響，這也是where後面跟的欄位，不必在select出現的原因。select的本意是處理數據後僅僅返回這些欄位，而不是決定只有這些欄位進行數據處理，所以必定要放偏後的位置。
7. order by用於結果進行排序，肯定是結果處理後才排序的，理由和group by相似。
8. limit用於限制返回結果的行數和偏移量，必須是等篩選完分組完拍完序之後再限制，否則可能導致結果有誤。

根據表行數量評估B+tree層數演算法

先排除一些元數據的存儲：數據存儲在頁上，每頁大小16KB，每頁需要開闢一些新的空間來存儲元數據（例如指向上一頁下一頁的指針），頁頭存儲文件頭38位元組，頁面頭56位元組，最小記錄和最大記錄26個位元組，為了保證不出錯，出現了校驗和的機制，這塊功能的存儲被放到了頁尾，占8個位元組。頁里的數據呢，為了方便查找每行的數據，所以包含頁目錄（採用二分法，把查詢複雜度從O(n)優化為O(log n)），這也占空間，這些可以粗略的估計為占用了1KB。

聲明代數：假設非葉子節點指向葉子節點的指針數量為X，葉子節點能夠容納的行數為Y，B+tree層數為Z，那麼能存儲的總行數就是Xz-1 * Y。

計算X：主鍵假設用bigint，占8個位元組，頁號這個元數據占4個位元組，非葉子節點一條數據占12個位元組，15KB / 12B = 1280。
計算Y：假設一個行數據為1KB，也就是說可以放15條數據。

若Z為1：12800 * 15 = 15行
若Z為2：12801 * 15 = 19200行
若Z為3：12802 * 15 = 24576000行
若Z為3：12803 * 15 = 31457280000行

但是這是理想情況，很多主鍵id都用無符號int，能節省4個位元組，行數大小也不確定，所以這是個理論值，究竟是多少，需要根據實際情況討論。

推薦閱讀：

SQL語句執行順序相關問題

MySQL索引底層原理相關問題自總結（難度對標18K-25K薪資，已總結80+，持續更新中）