注:由於查詢優化器涉及面很廣也比較複雜，作者也沒有完全領會，本文主要來自書籍<<資料庫查詢優化的藝術: 原理解析和SQL性能優化>>，如果涉及到版權，請告知作者，刪除本文。

一、查詢語句的執行過程簡介

MySQL查詢語句在資料庫中的執行分為5個階段，具體如下:

1.1 SQL輸入

資料庫接收用戶輸入的SQL語句，準備執行。

1.2 語法分析

對輸入的SQL語句進行詞法分析、語法分析，得到語法分析樹。在這個階段，輸入的是一條SQL語句，輸出的是一棵多叉樹。

1.3 語義檢查

根據語法樹和系統的元信息進行語義檢查，本階段是對語法分析樹進行邏輯判斷，樹的結構不發生變化。對語法分析樹上的各個節點進行語義分析，判斷對象是否存在、是否重名等，對不合語義的地方報告錯誤。

1.4 SQL優化

SQL優化通常包括兩項工作:一是邏輯優化、二是物理優化。這兩項工作都要對語法分析樹的形態進行修改，把語法分析樹變為查詢樹。其中，邏輯查詢優化將生成邏輯查詢執行計劃。在生成邏輯查詢執行計劃過程中，根據關係代數的原理，把語法分析樹變為關係代數語法樹的樣式，原先SQL語義中的一些謂詞變化為邏輯代數的操作符等樣式，這些樣式是一個臨時的中間狀態，經過進一步的邏輯查詢優化，如執行常量傳遞、選擇下推等(如一些節點下移，一些節點上移)，從而生成邏輯查詢執行計劃。在生成邏輯查詢計劃後，查詢優化器會進一步對查詢樹進行物理查詢優化。物理優化會對邏輯查詢進行改造，改造的內容主要是對連接的順序進行調整。SQL語句確定的連接順序經過多表連接演算法的處理，可能導致表之間的連接順序發生變化，所以樹的形態有可能調整。物理查詢優化除了進行表的連接順序調整外，還會使用代價估算模型對單個表的掃描方式、兩表連接的連接演算法進行評估，選擇每一項操作中代價最小的操作為下一步優化的基礎。物理查詢優化的最終結果是生成最終物理查詢執行計劃。

1.5 SQL執行

在SQL執行階段，依據物理查詢計劃執行查詢，逐步調用相關演算法進行執行。演算法包括一趟演算法、嵌套循環連接、基於排序的兩趟演算法、基於散列的兩趟演算法、基於索引的演算法、使用超過兩趟的演算法等。

二、 邏輯查詢優化

2.1 邏輯查詢優化思路

查詢優化器在邏輯優化階段主要解決的問題是: 如何找出SQL語句等價的變換形式，使得SQL執行更高效。一條SQL查詢語句結構複雜，包含多種類型的字句，優化操作依賴於表的一些屬性(如索引和約束等)。可用於優化的思路包括:

  • 字句局部優化: 每種類型字句都可能存在優化方式，如等價謂詞重寫、where和having條件化簡中的大部分情況，都屬於這種字句範圍內的優化。
  • 字句間關聯優化: 字句與字句之間關聯的語義存在優化的可能，如外連接消除、連接消除、子查詢優化、視圖重寫等都屬於字句間的關聯優化，因為他們的優化都需要藉助其他字句、表定義或列屬性等信息進行。
  • 局部與整體的優化: 需要協同考慮局部表達式和整體的關係，如OR重寫並集規則需要考慮UNION操作(UNION師變換後的整體的形式)的花費和OR操作(OR是局部表達式)的花費。
  • 形式變化優化: 多個字句存在嵌套，可以通過形式的變化完成優化，如嵌套連接消除。
  • 語義優化:根據完整性約束、SQL表達的含義等信息對語句進行語義優化。

2.2 查詢重寫規則

傳統的聯機事務處理(OLTP)使用基於選擇(SELECT)、投影(PROJECT)、連接(JOIN)3種基本操作相結合的查詢，這種查詢稱為SPJ查詢。資料庫在查詢優化的過程中，會對這3種基本操作進行優化。優化的方式如下:

  • 選擇操作: 對應的是限制條件(格式類似field consant，field表示列對象，op是操作符，如=，>等)，優化方式是選擇操作下推，目的是盡量減少連接操作前的遠組數，使得中間臨時關係盡量少(元組數少，連接得到的遠組數就少)，這樣可減少IO和CPU的消耗，節約內存空間。
  • 投影操作: 對應的SELECT查詢的目的列對象，優化方式是投影操作下推，目的是盡量減少連接操作前的列數，使得中間臨時關係盡量小(特別注意差別:選擇操作是使元組的個數"盡量少"，投影操作是使一條元組"盡量小")，這樣雖然不能減少IO(多數資料庫存儲方式是行存儲，元組是讀取的最基本單位，所以要想操作列則必須讀取一行數據)，但可以減少連接後中間關係的元組大小，節約內存空間)。
  • 連接關係: 對應的是連接條件(格式類似field_1, field_2，field_1和field_2表示不同表上的列對象，op是操作符，如=，>等)，表示兩個表連接的條件。這裡涉及以下兩個子問題:
    • 多表連接中每個表被連接的順序決定著效率。如果一個查詢語句只有一個表，則這樣的語句很簡單；但如果有多個表，則會涉及表之間以什麼樣的順序連接效率最高效(如A、B、C三表連接，如果ABC、ACB、BCA等連接後的結果集一樣，則計算哪種連接次序的效率最高，是需要考慮的問題)。
    • 多表連接每個表被連接的順序由用戶語義決定。查詢語句多表連接有著不同的語義(如笛卡爾積、內連接 、還是外連接中的左外連接等)，這決定著表之間的額前後連接次序是不能隨意更換的，否則結果集中數據是不同的。因此，表的前後連接次序是不能隨意交換的。

  • 根據SQL語句的形式特點，可以針對SPJ的查詢優化，如基於選擇、投影、連接3種基本操作相結合的查詢。

2.3 啟發式規則再邏輯優化階段的應用

邏輯優化階段使用的啟發式規則通常包括如下兩類:

2.3.1 一定能帶來優化效果的，主要包括:

  • 優先做選擇和投影(選擇條件在查詢樹上下推)
  • 子查詢的消除
  • 嵌套連接的消除
  • 外連接的消除
  • 連接的消除
  • 使用等價謂詞重寫，對條件化簡
  • 語義優化
  • 剪掉冗餘操作(一些剪枝優化技術)、最小化查詢塊。

2.3.2 變換未必會帶來性能的提高，需根據代價選擇，主要包括:

  • 分組的合併
  • 借用索引優化分組、排序、DISTINCT等操作
  • 對視圖的查詢變為基於表的查詢
  • 連接條件的下推
  • 分組的下推
  • 連接提取公共表達式
  • 謂詞的上拉
  • 用連接取代集合操作
  • 用UNIONALL取代OR操作

三、物理優化

查詢優化器在物理優化階段，主要解決的問題如下:

  • 從可選的單表掃描方式中，挑選什麼樣的單表掃描方式是最優的？
  • 對於兩個表連接時，如何選擇是最優的？
  • 對多個表連接，連接順序有多種組合，是否要對每種組合都探索？如果不全部探索，怎麼找到最優的一種組合？

在查詢優化器實現的早期，使用的是邏輯優化技術，即使用關係代數規則和啟發式規則對查詢進行優化後，認為生成的執行計劃就是最優的。在引入了基於代價的查詢優化方式後，對查詢執行計劃做了定量的分析，對每一個可能的執行方式進行評估，挑出代價最小的作為最優的計劃。目前資料庫的查詢優化器通常融合這兩種方式。

3.1 查詢代價估算

查詢代價估算的重點是代價估算模型，這是物理查詢優化的依據。除了代價模型外，選擇率對代價求解也起著重要作用。

3.2 單表掃描演算法

單表掃描需要從表上獲取元組，直接關聯到物理IO的讀取，所以不同的單表掃描方式，有不同的代價。

3.3 索引

索引是 建立在表上的，本質上是通過索引直接定位表的物理元組，加快數據獲取的方式，所以索引優化的手段應該歸屬到物理查詢優化階段。

3.4 兩表連接演算法

關係代數的一項重要操作是連接運算，多個表連接是建立在兩表之間連接的基礎上的。研究兩表連接的方式，對連接效率的提高有著直接的影響。

3.5 多表連接演算法

多表連接演算法實現的是在查詢路徑生成的過程中，根據代價估算，從各種可能的候選路徑中找出最優的路徑(最優路徑是代價最小的路徑)。多表連接演算法需要解決兩個問題:

  • 多表連接的順序: 表的不同連接順序，會產生許多不同的連接路徑；不同的連接路徑有不同的效率。
  • 多表連接的搜索空間:因為多表連接的順序不同，產生的連接組合會有多種，如果這個組合的數據巨大，連接次數會達到一個很高的數量級，最大可能的連接次數是N！(N的階乘)。比如N=5，連接次數是120；N=10，連接次數是362880。所有的連接可能構成一個巨大的"搜索空間"。如何將搜索空間限制在一個可接受的時間範圍內，並高效地生成查詢執行計劃將成為一個難點。

四、查詢優化器與其他模塊的關係

在資料庫內部，根據功能不同，可以劃分出多個模塊，不同模塊之間有的關係緊密，有的關係鬆散。查詢優化器是其中的一個功能模塊，是實現查詢優化技術的模塊。下面介紹資料庫中與查詢優化器相關的模塊:

4.1 查詢優化器與語法分析器

語法分析器是查詢優化器的輸入。理解查詢優化器，從語法分析器開始，將是個好的開端。因為不同對象有著不同的數據結構，數據結構成員是對象屬性的載體，而語法分析器把一個SQL分解為眾多數據結構體並給數據結構賦值，這樣才能被查詢優化器逐項獲取並用與計算，比如邏輯查詢優化有一條"常量傳遞"規則，如果沒有語法分析器分解條件，也不可能推知列值是常量，也不可能有此優化。

4.2 優化器與執行器

查詢優化器是執行器的前端輸入部分。查詢優化器計劃一條SQL的具體執行方式和步驟 ，執行器具體去完成計劃中的每一步。在實踐中，一條SQL最耗時的階段多發生在執行階段。如果查詢計劃做得不好，則執行起來非常耗時。

4.3 優化器與緩衝區

緩衝區有多種多樣，比如與數據相關的緩衝區(如從存儲設備載入數據到內存)、與實現過程相關的輔助緩衝區(如排序用到的臨時表或內存塊)，與功能模塊相關的緩衝區(如日誌緩衝區)等。優化器主要是對SQL輸入進行邏輯方式的變換，沒有涉及數據部分，只涉及對數據量的估計。當估算排序空間的時候，會涉及排序緩衝區；當估算數據IO的時候，需要考慮數據是否在數據緩存中。所以，查詢優化器與數據緩衝區有一定的關係。

4.4 優化器與統計

MySQL資料庫的查詢優化器使用了基於代價的查詢執行計劃估算，所以依賴於被查對象的各種數據，而數據是動態變化的，如表的元組數。如果實時獲取這些數據，系統計算的開銷會比較大。為了避免這樣的問題，定期或者根據需要統計這些數據，則比較切合實際。優化器在物理優化階段，需要對單表讀取開銷，兩表連接開銷，多表連接順序開銷等進行比較，比較基於的就是一些基礎數據的值，這些數據通常不會被實時更新，所以優化器有時做出的計劃未必是最合適的。

4.5 優化器與索引

優化器做物理查詢優化需要利用索引提高單表掃描效率，進而減少了多表連接時的元組數，所以確定哪些索引可用、怎麼有效利用索引等都在查詢優化器中得到體現。

五、 MySQL查詢優化器概述

MySQL 查詢優化器的主要功能是完成SELECT語句的執行，在保證SELECT語句正確執行之外，還有一個重要的功能，就是使用關係代數、啟發式規則、代價估值模型等不同種類的技術，提高SELECT語句的執行效率。

MySQL 查詢 優化 器 實現 第 2 章介紹 的 大多數查詢優化技術，這些 技術， 用於 對 SPJ 和 非 SPJ 類型 的 查詢 語句 進行 優化。

下面將從整體上介紹MySQL查詢優化器， 分別對MySQL 查詢優化器的執行過程、架構、層次、設計 思想、主要概念、代碼結構上宏觀探討MySQL查詢優化器的實現。

5.1 MySQL查詢執行過程

MySQL查詢執行過程分為4個階段，如下所示:

  • 語法分析階段: 將SQL查詢語句經詞法和語法分析後變換成為一棵查詢樹st_select_lex傳給優化器，並對SQL表達的語義進行檢查。
  • 生成邏輯查詢執行計劃階段: 優化器在查詢樹中遍歷每個關係，確定關係是否是常量表、為每個關係查找可用的索引、運用關係代數原理和啟發式規則進行邏輯上的查詢優化(如消除子查詢、消除外連接等)。
  • 生成物理查詢執行計劃階段: 優化器對各個連接的表進行排序，然後求解多表連接最優路徑，對於每個關係盡量利用索引計算其代價，找出代價最小的路徑後保存到JOIN類的bets_positions
  • 執行查詢執行計劃階段: 把查詢執行計劃傳到執行器進行執行。

MySQL查詢優化器在邏輯查詢執行計劃階段，機遇關係代數規則和啟發式規則，把用戶指定的SQL經過"等價"的代數轉換，變為一種更節省IO的執行序列，執行起來更為高效。

MySQL查詢優化器在物理查詢執行計劃階段，在解決多表連接的問題時，有兩套演算法:一是用戶指定表連接次序的演算法；二是混雜了貪婪和窮舉思想的演算法，解決的是較多表的連接和非用戶指定連接次序的多表連接，但不能保證得到最優的查詢執行計劃。

5.2 MySQL查詢優化器的架構和設計思想

MySQL查詢優化器設計精巧，但層次不夠清晰，V5.6之後的版本，混亂狀態有所改善，但MySQL查詢優化器實用而高效，在充分利用索引的基礎上，實現了很多查詢優化技術，有很多精巧之處值得學習探索。

MySQL查詢優化過程中，查詢優化器通過JOIN對象的方法，如JOIN.prepare()、JOIN.optimize()，完成優化工作。JOIN.prepare()完成的查詢優化主要包括：子查詢的冗餘子句消除、IN類型子查詢優化、將ALL/ANY等類型的子查詢轉換為MIN/MAX等操作，這是對簡單子查詢進行的優化；JOIN.optimize()函數完成的查詢優化主要包括：子查詢上拉，把外連接優>化為內連接，把嵌套連接消除，WHRER子句、JOIN/ON子句、HAVING子句條件表達式的化簡（尤其是對含有常量的表達式的化簡、等式合併），優化沒有GROUPBY子句情況下的COUNT(*)、MIN()、MAX()，裁剪分區partition（如果查詢的表是分區表），確定多表的連接路徑（單表是多表的特例，統計join的代價，兩種多表連接演算法選其一搜索最優的join順序、生成執行計劃）、優化等式謂詞、優化DISTINCT、創建臨時表存儲臨時結果優化分組排序等操作。在這樣的過程中，MySQL沒有把優化過程明顯地分為邏輯查詢優化階段和物理查詢優化階段，而是互為混雜，在物理查詢優化之後，繼續進行了部分邏輯查詢優化。這是MySQL查詢優化器的一大特點。

5.3 MySQL查詢優化器架構

MySQL查詢優化器為SQL查詢語句求解最優的執行方式。MySQL查詢優化器架構和執行過程如下圖所示。

MSQL查詢語句的執行主要歷經4個過程，分別如下:

  1. P1過程：SQL語句輸入變為語法查詢樹。
  2. P2過程：查詢預處理，優化相關的內容主要是子查詢優化。
  3. P3過程：語法樹變為邏輯關係查詢樹，進而變為物理查詢執行計劃，挑出最優計劃。
  4. P4過程：依據最優查詢執行計劃得到查詢結果。

MySQL查詢語句的執行，主要歷經以下4個模塊。

  1. M1模塊：語法分析模塊，執行過程P1的任務。
  2. M2模塊：查詢 預處理模塊，執行過程P2的任務。
  3. M3模塊：查詢優化模塊，執行過程P3的任務。
  4. M4模塊：查詢執行模塊，執行過程P4的任務。

實現MySQL查詢優化器功能的主要是M3模塊，其主要有以下兩個子階段的工作。

  • M3-S1邏輯查詢優化階段：把語法查詢樹通過關係代數原理，優化為關係代數查詢樹，關係代數的原理在這個階段運用；
  • M3-S2物理查詢優化階段：把關係代數查詢樹用於貪婪演算法，生成最優執行計劃。

5.4 MySQL查詢優化器的層次

MySQL整個查詢優化器從代碼層面看，邏輯結構不是很清晰，但是從技術層面看，還是能夠分為兩個階段，一是邏輯查詢優化階段，二是物理查詢優化階段。

  • 邏輯查詢優化階段主要依據關係代數可以推知的規則和啟發式規則，對SQL語句進行等價變換。MySQL淋漓盡致地使用了關係代數中可推定的各項規則，對投影、選擇等操作進行句式的優化；對條件表達式進行了謂詞的優化、條件化簡；對連接語義進行了外連接、嵌套連接的優化；對集合、GROUPBY等盡量利用索引、排序演算法進行優化。另外還利用子查詢優化、視圖重寫、語義優化等技術對查詢語句進行了優化。
  • 在物理查詢優化階段，通過貪婪演算法，並依據代價估算模型，在求解多表連接順序的過程中，對多個連接的表進行排序並探索連接方式，找出花費最小的路徑，據此生成查詢執行計劃。在這個階段，對於單表掃描和兩表連接的操作，高效地使用了索引，提高了查詢語句的執行速度。

六 、 從功能角度看MySQL查詢優化

MySQL的查詢優化技術的實現，基本也可以分為邏輯優化和物理優化兩個階段，只是和PostgreSQL相比，界線沒有那麼清晰。MySQL的查詢優化過程概述如下:

  1. 優先處理集合操作，把集合操作分解為普通的SPJ和非SPJ操作。
  2. 應用子查詢優化技術，去除子查詢中冗餘部分，轉換為半連接、用物化操作優化子查詢、執行In向EXISTS轉換、優化ALL/ANY等類型的子查詢向MIN/MAX轉換等。
  3. 消除外連接、消除嵌套連接。
  4. 利用等價謂詞重寫優化技術，優化WHERE、JOIN/ON、 HAVING等條件中的表達式，尤其是常量表達式和多重等式。
  5. 利用索引優化count(*)，MIN()，MAX()。
  6. 進行多表連接的順序確定。
  • 找出常量表，求解多表連接的過程中不使用常量表作為連接的表(減少搜索空間)。
  • 盡量利用索引優化GROUP BY、DISTINCT結合的操作
  • 利用代價估算模型，評估連接的花費，找出最優連接。
  • 用物化優化半連接嵌套的形式。
  • 從兩種多表連接的演算法中任選其一: 一是用戶指定連接順序 ，二是使用貪婪和窮盡結合的方式。
  • "選擇"、"投影"操作下推
  • 利用索引對ORDER BY進行優化
  • 對GROUP BY/DISTINCT的組合情況進行優化
  • 確定半連接優化策略，從5種備選策略選擇其中之一。
  • 對沒有GROUP BY和ORDER BY字句的IN子查詢進行優化。

七、 參考文獻

書籍: <<資料庫查詢優化的藝術: 原理解析和SQL性能優化>>


推薦閱讀：
相關文章