MySQL 內部最佳化器

優化器（The Optimizer）

 這篇描述MySQL查詢優化器的工作原理。 MySQL查詢優化器主要為執行的查詢決斷最有效的路線（routine，走向）。

 

一。原始碼與概念

 這部分討論優化器關鍵概念，術語，及在MySQL原始碼怎麼對應的。

 

1.定義

 狹義定義：最佳化器，就是DBMS為查詢時決斷要往哪種執行路徑的一系列路線。

 MySQL是經常調整查詢的路線，所以你得把這篇描述的邏輯和在原始碼裡的做比較。為了讓比較容易些，這裡會包含相關檔案和路徑的註解，例如原始碼/sql/sql_select.cc，optimize_cond()函數。

 當一個查詢被轉換成另一個查詢時，其結果是一樣的，就會發生語句轉換。以下這個查詢

SELECT ... WHERE 5 = a
就會被轉換變成

SELECT ... WHERE a = 5
 最明顯的語句轉換是少的，有些語句轉換，是為了更快的執行。

 

2.最佳化器原始碼

 如下偽代碼顯示了/sql/sql_select.cc中handle_select()函數的邏輯結構。 (原始碼/sql/sql_select.cc處理SQL查詢）

handle_select()
   mysql_select()
     JOIN::PRep            /* optimizer is from here ... * /
       optimize_cond()
       opt_sum_query()
            choose_plan()
           /* Find the best way to access tables */
               optimize_straight_join()
             best_access_path ()
           /* Find a (sub-)optimal plan among all or subset */
            /* controls the exhaustiveness of the search.   */
           greedy_search()
      ()
               best_access_path()
          
       make_join_select()        /* ... to here */
     JOIN::exec()
 縮顯示了哪個函數呼叫哪個函數，如handle_select()函數呼叫mysql_select()函數，mysql_select()函數會呼叫JOIN::prepare()、JOIN::optimize()、JOIN::exec()，以及類別推。 mysql_select()函數的第一部分是呼叫JOIN::prepare()，此函數用來上下文分析、元資料建立和一些語句轉換。查詢最佳化器函數JOIN::optimize()和其所有最佳化處理中的子路線。當執行完JOIN::optimize()函數後，JOIN::exec()接手並完成JOIN::optimize()函數最佳化決斷後的執行工作。

 雖然有JOIN字出現，其實查詢優化器的工作會處理所有的查詢類型，不單單JOIN聯接查詢。

 

二。首要最佳化

 這部分討論伺服器執行的最重要最佳化。

 

1.最佳化常數關係

常數等值傳遞

 如下的表達式會發生語句轉換：

lumWHERE column1 = column2 AND cocolum =B && B=C => A=C（可等值傳遞），上句表達式轉換後變成：

WHERE column1='x' AND column2='x'

 

 當且僅當，操作符為如下的任何一個，在column1 column2條件中就會發生語句轉換：

=, , =, , , LIKE

注意：等值傳遞的轉化，不適合BETWEEN。可能也不適合於LIKE，這是後話。

 

 常數等值傳遞同樣發生在循環中，前一步傳遞的輸出作為後一步傳遞的輸入。

原始碼見/sql/sql_select.cc，change_cond_ref_to_const()函數。或/sql/sql_select.cc，propagate_cond_constants()函數。

 

剔除死代碼

 總是TRUE的條件會發生語句轉化，如：

WHERE 0=0 AND column1='y'
這種情況下，第一個條件會被剔除，最後一個條件會被剔除，最後一個條件：

column1='y'
 原始碼見/sql/sql_select.cc，remove_eq_conds()。

 

 總是FLASE的條件也會發生語句轉化，如：

WHERE (0 = AND s1 = OR s1 = 7
小括號和前兩個條件總是FLASE，最後為：

= 7

 

 還有一些情況下，當WHERE語句中代表不可能的條件，查詢最佳化器可能會全部剔除語句，如下：

WHERE (0 = AND s1 = 5)
因為這條件永遠不會為TRUE，在EXPLAIN分析中會顯示Impossible WHERE。這樣

微妙的。所有的Impossible WHERE的條件，因為這方面可能性太多了。器不會剔除這種查詢的條件，即使在CREATE TABLE定義中使之成為不可能的條件。 1 + 2

最後為：

WHERE column1 = 3

 在先前說的常數等值傳遞，最佳化器很容易將此查詢語句合併在一起。和常數表

 MySQL常數值，有時不單單指在查詢的SQL語句的字面意思上，也可在常數表（constant tables）的內容裡。無記錄或一筆記錄的表

2。鍵的欄位定義為NOT NULL）

 例如，Table0表的定義包含：

... PRIMARY KEY (column1,column2)

 然後，查詢表達式：

F AND column2=7 ...
會傳回常數表（constant tables）。更簡單地，如果Table1表的定義包含：

... unique_not_null_column INT NOT NULL UNIQUE
然後，查詢表達式：

FROM Table1 ... WHERE unique_not_null_column

FROM Table1 ... WHERE unique_not_null_column tables）。

 

 這個規則指一個常數表（constant tables）至多有一筆記錄值。 MySQL就會優先評估是否為常數表（constant tables），並找出那個值。這樣，MySQL會將這值插入查詢語句。如這個例子：

SELECT Table1.unique_not_null_column, Table2.any_column
    FROM Table1, Table2

    WHERE Table1.unique_not_null_column = Table  n = 5;

MySQL評估這語句時，首先會發現，依照常數表（constant tables）的第二點定義，查詢條件為unique_not_null_column的表Table1是一個常數表（constant tables），它就會得到這個值。

如果取值失敗，也就是在表Table1裡unique_not_null_column = 沒值，EXPLAIN後結果：

Impossible WHERE noticed after reading const tablesd

Impossible WHERE noticed after reading const tablesdnot

，如果取值成功，也就是在表值一筆記錄值，MySQL會轉換為下列語句：

SELECT 5, Table2.any_column
    FROM Table1, Table2

    WHERE 5 = Table2.any_column

  事實上，這是一個很好的例子。優化器因前面提到的常數等值傳遞進行一些語句轉換。另外，為什麼要先描述常數等值傳遞，因為它在MySQL確認什麼是常數表（constant tables）前就先進行了。優化器步驟的順序，有時是有差異。

 雖然很多查詢都沒常數表（constant tables）參考。應該牢記，以後無論什麼時候，常數constant字被提及，它是指任何一個字面上的值或一個常數表（constant tables）的內容。

 

2.最佳化JOIN連結

 這部分討論最佳化JOIN連結的不同方法。注意：JOIN聯結並非單單指JOIN類型，而是所有條件查詢的類型。有些人喜歡叫access type。

 

確定JOIN聯結類型

 當評估查詢條件表達式時，MySQL會確定它是屬於哪個JOIN聯接類型。

 如下有記錄在檔的JOIN類型，從最好到最壞的排序下來：

system：常數表（constant tables）的system類型 
const：常數表（constant tables） 
eq_ref：相等關係的唯一或主鍵索引 
ref：相等關係的索引，此索引的值不能為NULL 
ref_or_null：相等關係的索引，此索引的值可能為NULL 
range：有關聯的索引，如BETWEEN，IN，>=，LIKE等 
index：順序掃描索引 
ALL：順序掃描整個表格資料

原始程式碼請參閱/sql/sql_select.h，enum join_type{}。另外，還有一小部分沒記錄在檔，為了子查詢的JOIN聯結類型。

 

 優化器利用JOIN聯接類型選擇一個驅動表達式，如下：

SELECT *
FROM Table1
WHERE indexed_column = AND unindexed_column = 60cDlumn = 6969式。對它來說，你也會遇到各種不同的例外，但對這句話描述，是第一個簡單的最佳化法則。

 

 對驅動來說，什麼是最有意義的呢？ 如下查詢時的兩條執行路徑：

最壞執行計劃：掃描讀表的所有行。這也叫Table1的順序掃描或簡單表格掃描。查詢每行，檢查indexed_column和unindexed_column兩列的值是否符合查詢的條件。

最好執行計劃： 透過索引，檢索哪些有indexed_column = 值的記錄。這也叫被索引的搜尋。查詢每行，檢查unindexed_column列的值是否符合查詢的條件。

 

 被索引的搜尋通常比順序掃描調用更少的訪問，而且如果訪問的表是巨大的，索引又是唯一的，這樣表的訪問是非常少的。這也是為什麼有好執行計劃的存取表是更好的，而且這也是為什麼常常把indexed_column做為驅動。

 

聯接和存取的方法

 在單表搜尋中，壞的JOIN連結執行選擇比壞的執行選擇造成更多的效能損害。所以MySQL開發者發了更多的時間確保查詢中的表以一種最佳順序被聯接和此最佳訪問方法（常常被稱為訪問路徑）被選擇作為檢查表資料。表聯的固定順序和對應的所有表的表訪問方法的組合，稱為查詢執行計劃（QEP）。查詢優化器的目的就是在所有可能的計劃中找出一個最佳的QEP。 JOIN聯接優先後有一些常規的概念。

 每個計劃或計劃的部分，被定義成COST成本。計劃的成本粗略地反映了計算按照計劃的查詢所需的資源，其中主要的因素是當計算查詢時所以訪問的記錄總數。一旦我們有辦法分配到不同的成本QEPs，我們有辦法對它們進行比較。這樣，優化器的目的就是在所有可能的計劃中找到一個成本最低的QEP。

 

 在MySQL中，實現了最佳QEP搜尋是自下而上的方式。優化器首先確認一張表的所有計劃，接著兩張表的所有計劃，以此類推，直到建立一個完整的最佳QEP。查詢計劃包括在查詢中只有部分錶和限定（predicates），被稱為部分計劃（partial plans）。優化器依賴一點事實：越多表被加到部分計劃（partial plans），成本就越高（註：成本高，執行效率就低）。這使得優化器可擴展更多的表只用較低成本的部分計劃（partial plans）類比目前最好的完整計劃。

 完成搜尋一條最佳QEP的關鍵路線請見sql/sql_select.cc，find_best()。它執行了所有可能計劃的詳盡搜索，從而保證它最終將找到一個最佳的一條。

 

 如下我們描述find_best()方法的偽代碼。這是遞歸的，所以一些輸入變數被標記了，以表明到目前為止，他們從前一個的迭代來的。

remaining_tables = {t1, ..., tn}; /* all tables referenced in a query */

procedure find_best(
  partial_plan in,      /* in, 目前連接的表的部分計劃*/
  partial_plan_cost,  中未引用的表集*/
   best_plan_so_far,     /* 輸入/輸出，迄今為止找到的最佳方案*/
   best_plan_so_far_cost)/* 輸入/輸出，best_plan_so  / * 計算
        最佳化器考慮的因素可能包括：
          中有許多行（不好）
       限制（好）
          長鍵（好）
          唯一或主鍵（良好）
          全文鍵（壞）
             平均/最大鍵長短
          小表檔案
          關卡很少在索引中
所有ORDER BY / GROUP 欄位都來自此表*/
     cost = complex-series-of-calculations;
     /* 將成本加到目前的成本中。 */
    partial_plan_cost+= cost;

     if (partial_plan_cost >= best_plan_so_far_cost)
   
    partial_plan=透過best_access_method擴充partial_plan;
    剩餘表=剩餘表-表T；
if (remaining_tables 不是空集)
     {
                  best_plan_so_far, best_plan_so_far_cost);

     }

    
       best_plan_so_far=partial_plan;
     }

   }

}

這裡優化器使用了一種深度優先搜尋演算法。它完成在 FROM 語句中評估所有的表。如果評估金斯目前狀況最好的評估，變得更差，將停止搜索。掃描的順序依賴於出現FROM語句中的表格的順序。


原始碼見：/sql/table.h， struct st_table。


 分析表（ANALYZE TABLE）可能會影響一些最佳化器決斷的參數。原始碼請參閱：/sql/sql_sqlect.cc，make_join_statistics()。


 find_best()和greedy_search()的直截了當（straightforward）使用將用於不會LEFT JOIN或RIGHT JOIN。例如，從MySQL 4.0.14開始，在某些這種情況下，優化器可能會將 LEFT JOIN 轉變為 STRAIHT JOIN，並交換錶的順序。另外請參閱：LEFT JOIN 和 RIGHT JOIN 優化。


 

 RANGE 連接類型

 有些條件使用索引，但是在一個可以鍵的範圍（range）或寬度內。這些稱為範圍條件，最常的是帶>，>=，

 

對最佳化器來說，如下表達式：

column1 IN (1,2,3)

和這個是一樣的：

column1 = OR columnSQL1 = ORcolumn種語句，需要對查詢條件的IN到OR或OR到IN做轉變。

 

 如下語句，最佳化器也需要使用索引（範圍查詢範圍搜尋）

column1 LIKE 'x%'

 但不行：

column1 KE的第一個字元一個是通配符那就，沒範圍查詢。

 

 同樣，如下兩個語句也是一樣的

column1 BETWEEN 5 AND 7
和

列 1 >= AND 列 1 = 7

 

 如果查詢的條件，檢索了太多的索引鍵，優化器可能轉變RANGE連接類型為ALL JOIN連接類型。像這種轉變，特別可能在條件和多層第二索引（secondary indexes）中。原始碼請參閱：/myisam/mi_range.c，mi_records_in_range()（MyISAM索引）。

收到像這種方式的索引，一般稱為覆蓋索引（COVERING INDEX）。在EXPLAIN Extra描述中，MySQL會簡單地用INDEX單字來表示覆蓋索引（COVERING INDEX）。

 語句：

SELECT column1, column2 FROM Table1; 只有當索引被定義成如下，優化器會使用JOIN聯接類型為INDEX：join type = index CREATE INDEX ... ON Table1 (column1, lum2);換句話說，被查詢的欄位（如：column1, column2）都必需被加索引的，而被加索引的多個欄位是無順序之分的。因此，更有意義的嚴格定義一個多列索引（multiple-column index）作為一個覆蓋索引（COVERING INDEX）來使用，無論搜尋的考慮。

 

 INDEX MERGE聯接類型

概述

 使用索引合併（INDEX MERGE），當表的條件可轉換成如下：

個cond_i（con​​d_1，cond_2。。。）條件可用於範圍掃描，且沒有一對條件（cond_i，cond_j）用相同的索引。如果cond_i和cond_j條件使用相同的索引，那麼cond_i或cond_j條件能結合單一範圍掃描，也就沒合併的必要了。

 

 如下查詢就用了索引合併（INDEX MERGE）：

SELECT * FROM t WHERE key1=c1 OR key2 索引合併（INDEX MERGE），是實作成一種範圍鍵（range key）並以cond_i（con​​d_1，cond_2。。。）條件建構成的容器。在做索引合併（INDEX MERGE）時，MySQL檢索每個鍵掃描（keyscans）的行，然後透過一個消除重複的過程來執行它們。目前類別Unique用於消除重複的。

 

INDEX MERGE優化器

 單一SEL_TREE物件無法建構成在OR語句中有不同成員的鍵的條件，類似這條件：

key1

sel_imerge_cond = (t_1 OR t_1 OR ... OR t_n)

 每個t_i（t_1，t_2。）代表一個SEL_TREE，沒有一對。 （t_i，t_j）不同的SEL_TREE物件能被合併成單一的SEL_TREE物件。

 目前的實現方法在建構SEL_IMERGE時，只有當沒有單一的SEL_TREE物件能被建構成被分析過的查詢的一部分；如果發現單一SEL_TREE物件能被建構，就會馬上丟棄SEL_TREE。這實際上是一個限制，並且可能導致最壞行檢索策略的使​​用。下列查詢：

SELECT * FROM t WHERE (goodkey1=c1 OR goodkey1=c2) AND badkey=c3

 在badkey的掃描會被選擇，即使在（goodkey1，goodkey1）上的索引合併（IND在badkey的掃描會被選擇，即使在（goodkey1，goodkey1）上的索引合併（INDEXEXEXEX）快。

 

 索引合併（INDEX MERGE） 最佳化器會收集索引合併（INDEX MERGE）存取資料列的所有可能的路線清單。這個SEL_IMERGE結構清單表示以下的條件：

  (t_11 OR t_12 OR ... OR t_1k) AND

  (t_21 OR t_22 OR ... OR t_2l) AND🠎 (t_21 OR t_22 OR ... OR t_2l) AND🠎 ...         AND
  (t_M1 OR t_M2 OR . .. OR t_mp)

 當t_ij是一個SEL_IMERGE且條件就是一個SEL_IMERGE物件。

 最小成本的SEL_IMERGE物件用來檢索行。

 索引合併（INDEX MERGE）建構子的詳細資訊請參閱：原始碼sql/opt_range.cc，imerge_list_and_list()，imerge_list_or_list()，和SEL_IMERGE類別的成員函數。

 

RANGE優化器

 為了範圍RANGE查詢，MySQL最佳化器建立一個SEL_TREE對象，如下這種形式：

range_cond = (cond_key_1 AND cond_key_2 都是 cond_key_2的組成部分的條件。 MySQL為每個有用的鍵建立一個cond_key_i條件。然後這種成本最便宜的條件cond_key_i用來做範圍RANGE掃描。

 單一的cond_key_i條件是用SEL_ARG物件中的一個相聯指標網（a pointer-linked network of SEL_ARG objects）來表示。每個SEL_ARG對象參考鍵的特定部分和表示如下的條件：

  sel_arg_cond= (inf_val                 AND next_key_part_sel_arg_cond                  (2)
                OR left_sel_arg_cond                            (3)
                OR right_sel_arg_cond                           (4)
 

1。實現間隔，可能沒有上下臨界，或包括或不包括臨界值。

2。實作SEL_ARG物件以下一個鍵組件作為條件（is for a SEL_ARG object with condition on next key component）。

3。實作有間隔的SEL_ARG對象，在同樣區域作為這個SEL_ARG物件（is for a SEL_ARG object with an interval on the same field as this SEL_ARG object）。在目前物件和左邊物件中的間隔，是不相交的。 left_sel_arg_cond.sup_val

4。實現有間隔的SEL_ARG對象，在同樣區域作為這個SEL_ARG對象。在目前物件和右邊物件中的間隔，是不相交的。 left_sel_arg_cond.min_val >= max_val。

 MySQL會轉換任意深度的嵌套AND-OR條件為上述相連接的形式。

 

行檢索演算法

 索引合併（INDEX MERGE）有以下兩個步驟：

準備階段：

activate 'index only';g next (key, rowid) pair from key_i)
  {
    if (no clustered PK scan ||
        row doesn't match clustered scan     row doesn't match clustered PK scan con  
deactivate 'index only';



行檢索階段：

for each rowid in Unique

{

  retrieve row and pass it to output;

}

if (clustered_pk_scan){fluf {p output;

}

原始程式碼請參閱：sql/opt_range.cc，QUICK_INDEX_MERGE_SELECT類別函數的索引合併（INDEX MERGE）行檢索程式碼。


 

3.換位（Transpositions）

 MySQL支援簡單語句表達式的換位（反轉關係運算子的運算元的順序）。換句話說：

WHERE - 5 = column1

此語句可轉換成：

WHERE column1 = -5

 

column1

而這句話不能同等對待：

WHERE column1 = -5

 

 像這形式column = constant表達式的換位是為了更好的索引檢索。如果這種形式的語句有加了索引的字段，不論表的大小，MySQL總是使用上索引的。 （例外：如果表無記錄或只有一行記錄，它就是常數表，需特別處理。請參閱常數值和常數表）。

 

 AND關係

 一個AND的查詢形式如condition1 AND condition2，如下：

WHERE column1 = 'x' AND column2 = 'y'

WHERE column1 = 'x' AND column2 = 'y'

WHERE column1 = 'x' AND column2 = 'y'

WHERE column1 = 'x' AND column2 = 'y'

375：解說如果兩個條件都沒被索引，使用順序掃描（全表掃描）。

2。除前一點之外，如果其中一個條件有更好的JOIN聯接類型，則以JOIN聯接類型選擇一個驅動器。 （請參閱確定JOIN聯接類型）

3。除前兩點之外，如果兩個條件都有加索引且平等的JOIN聯接類型（註：JON 聯接類型效果有好壞之分），則以第一個建立的索引選擇一個驅動。

 最佳化器也會根據索引交叉選擇索引合併（INDEX MERGE），請參閱 INDEX MERGE連接類型。 例子如下：

CREATE TABLE Table1 (s1 INT, s2 INT);
CREATE INDEX Index1 ON Table1 (s2);

CREATE INDEX Index2 ON Table1 (s1);

);
CREATE INDEX Index2 ON Table1 (s1);
. s2 = 5;

 當選擇一種策略來解決這個查詢，優化器會選擇s2 = 5作為驅動，由於s2上的索引首先被創建。視為一個偶然的效果，而不是一種規則，在任何時刻都有可能改變的。

 

 OR關係

 一個OR的查詢形式如condition1 OR condition2，如下：

WHERE column1 = 'x' OR column2 = 'y'
 這種查詢最佳化器的決斷是使用順序全表掃描。

 

 還有一個選擇在特定的環境下會使用索引合併（INDEX MERGE），更多資訊請參閱INDEX MERGE優化器和Index Merge Optimization。

 上述的特定情況不能用於如果兩個條件的欄位是一樣。如下：

WHERE column1 = 'x' OR column1 = 'y'
 這種情況，由於語句是RANG查詢，所以會走索引的。這個話題會在IN限定（predicate）的討論中再次看到。

 

 UNION查詢

 所有含有UNION的SELECT查詢語句會被各自最佳化。因此，這個查詢：

SELECT * FROM Table1 WHERE column1 = 'x'
UNION ALL
SELECT * FROM TABLE1 WHERE column2 = 'y'
 如果column1和column2ECT的結果集會被合併。注意：此查詢可能產生相同的結果集，如果查詢使用了順序掃描OR的範例。

 

 NOT（）關係

 一個邏輯條件如下：

column1 5
等價於：

column1 5
等價於：

進行轉化語句。如果你覺得用RANG查詢效果會更好，你必需自己手動做語句轉換。

 

 還有一個邏輯條件如下：

WHERE NOT (column1 != 5)

等價於：

WHERE column1 = 5

字

WHERE column1 = 5

句

 我們期待能針對上述兩種情況加入新的最佳化方法。

 

 ORDER BY語句

 通常，如果最佳化器發現行記錄不管怎麼樣都是有順序的，在ORDER BY語句中它也會跳過SORT過程。但是還是驗證幾個例外的情況。

 例：

SELECT column1 FROM Table1 ORDER BY 'x';

 優化器會丟掉ORDER BY語句，這也是死程式碼刪除範例。

 

 例：

SELECT column1 FROM Table1 ORDER BY column1;

 優化器會使用column1的索引，如果有的話。

 

 例：

SELECT column1 FROM Table1 ORDER BY column1+1;

 最佳化器會使用column1的索引，如果有的話。但是不要被弄混了，索引只用來找出記錄值。另外：順序掃描索引的成本比順序掃描全表的成本是更便宜的（一般索引的大小會比資料值的大小小的），這也是為什麼INDEX JOIN聯結類型會比ALL型別更優化。請參閱確定JOIN聯接類型。

 

 還有一個結果集的全部排序SORT，例如：

SELECT * FROM Table1
WHERE column1 > 'x' AND column2 > 'x'的，優化器會走在column1上的索引。在這個查詢語句，對column2值的排序不會影響驅動的選擇。

原始碼請參閱：/sql/sql_select.cc，test_if_order_by_key()和/sql/sql_select.cc，test_if_skip_sort_order()。

 

 ORDER BY Optimization，描述了SORT排序過程的內容機制，在這裡不重複解釋。但懇請你一定要閱讀，因為它描述了緩衝和快速排序機制的操作。

 

 GROUP BY和相關的條件

 這裡描述了GROUP BY和相關條件（HAVING，COUNT()，MAX()，MIN()，SUM()，AVG()，DISTINCT()）的主要主要的主要最佳化.


GROUP BY會使用索，如果一個索引存在的話。 
GROUP BY會用排序，如果沒有索引存在。優化器可能選擇使用HASH表排序。  
GROUP BY x ORDER BY x的情況，最佳化器會因為GROUP BY會以 x 的排序，而認為ORDER BY是不需要的。 
最佳化器包含了為轉移特定HAVING條件的WHERE語句中的程式碼。然而，此程式碼在編寫時是不生效的。原始碼請參閱：/sql/sql_select.cc，JOIN::optimize()，在#ifdef HAVE_REF_TO_FIELDS之後。 

如果表句柄（handler）有個有效的快速行總數（row-count），那麼這個查詢： 

SELECT COUNT(*) FROM Table1;
不必掃描所有行，就能得到行總數值。這只對MyISAM表是正確的，但不適合InnoDB表。另外這個查詢

SELECT COUNT(column1) FROM Table1;
 不會有同樣的最佳化，除非column1定義為NOT NULL。


MAX()和MIN()新的最佳化方法。例： 
SELECT MAX(column1)

  FROM Table1

  WHERE column1  如果column1被索引了，就很容易找到最大值通過查詢索引中的'a'值並且在這之前返回索引鍵。

最佳化對以下形式的查詢，進行語句轉換： 🎜SELECT DISTINCT column1 FROM Table1;🎜成：🎜

SELECT column1 FROM Table1 GROUP BY column1;
當且僅當這兩個條件都是正確：

* GROUP BY能透過索引來未完成。這暗示了只有一個表在FROM語句中且沒有WHERE語句。
* 沒有LIMIT語句。

 

 因為DISTINCT語句並不總是轉換成GROUP BY，不要期望含有DISTINCT查詢語句總是會有被排序的結果集。然而，你能依賴GROUP BY優化規則，除非查詢包括ORDER BY NULL。

 

三。其它最佳化

 這部分，討論其它更特別的最佳化方法。

 

1. ref和eq_ref的NULLs值過濾存取

 這部分討論ref和eq_ref聯接類型的NULLs值過濾最佳化方法。

 

 前期（early）NULLs值過濾

 假設我們有個聯接順序如下：

...,  tblX, ..., tblY, ...
更深入假設，表blref類型被存取：

tblY.key_column = tblX.column
或者，使用多個鍵部分的ref類型存取：

... AND tblY.key_partN = tblX.column AND ...
...AND tblY.key_partN = tblX.column AND ...

.為NULL。 ref（或eq_ref）類型存取時，前期會套用NULLs過濾。我們做如下的推論：

(tblY.key_partN = tblX.column)  =>  (tblX.column IS NOT NULL)

 原等式的檢查只有在讀了表tblX和tblY的當前行記錄後。 IS NOT NULL限定（predicate）的檢查，只有在讀了表tblX的目前行記錄後。如果表tblX和tblY的共同排序中有任何

 其它表，IS NOT NULL限定（predicate）的檢查就允許我們跳過訪問這些表。

 

 這個特性的實作代碼如下：

ref分析器（包含方法update_ref_and_keys()）透過設定KEY_FIELD::null_rejecting=TRUE檢查和標記像上述類型的等式查詢。 

選擇JOIN聯接排序以後，add_not_null_conds()會增加適當的IS NOT NULL限定（predicate）到適當表的相關條件中。

 

 對所有等式加了IS NOT NULL限定（predicate）是有可能被ref訪問類型使用（而不是那些有實際使用的）。然而，目前沒這樣做。

 

 後期（Late）NULLs過濾

 假設我們有一個表tblX查詢計劃，是透過ref存取類型被存取：

tblX.key_part1 = expr1 AND tblX.檢索前，我們確定任何expri（expr1，expr2，expr3。。）值是否為NULL。如果是，我們不會呼叫檢索，而是會馬上返回沒找到符合數組。

 這個最佳化方法重複使用了由前期（early）NULLs濾波產生的null_rejecting屬性。這個檢查的源代碼見：函數join_read_always_key()。

 

 2.分區相關的最佳化

 這部分討論MySQL分區相關的最佳化。 MySQL5.1分區相關概念與實作請參考：Partitioning。

 

 分區裁切（pruning）

 分區裁切（partition pruning）的操作，如下定義：

 「提供一個分區表的查詢，比對此分區表的DDL3查詢和任何查詢中的任何語句，並且找出這查詢存取的最小分區集。沒被加入這個分區集的其它分區，就不會被訪問的，也就是說被裁剪掉的分區。正因為這樣，查詢的執行速度變得更快。

 Non-Transactional Table Engines.??如MyISAM無事務儲存引擎，鎖會被加在整個分區表。理論上講，使用分區裁剪（partition pruning）是有可能提高並發，只把鎖加在被使用的分區上。但是目前還沒實現這功能。

 分區裁剪（partition pruning）不依賴表的儲存引擎，所以這功能是MySQL查詢優化器的一部分。接下來章節描述分區裁切（partition pruning）的細節。

 

分區裁切概述

 分區裁切（partition pruning）的實作步驟如下：

1。分析WHERE語句條件並建構區間圖interval graph，用來描述分析的結果情形。

2。透過區間圖，為每個區間找出被存取的分區集（包括子分區）。

3。建構查詢所需的分區集。

 區間圖interval graph是由下而上的方式建構成，並來表示上述步驟的描述。接著討論，我們會先定義術語區間圖interval graph，接著描述怎樣用分區區間來組成一個區間圖interval graph，最後描述區間圖interval graph的工作流程。

 

分區區間（Partitioning Intervals）

單點區間（Single-Point Intervals）

 從最簡單的情況開始，假設一個有一個有N個列的分區表，透過分區類型如下：

CREATE TABLE t (columns)
PARTITION BY p_type(p_func(col1, col2,... colN)...);
 再假設查詢的WHERE條件形式如下：

WHERE t.col1=const1 AND37. col2=const2 AND ... t.colN=constN
 我們能計算出p_func(const1, const2 ... constN)，並挖掘出哪個分區包含的記錄和WHERE條件一樣。注意：這個流程會在所有的分區類型和所有的分區函數上操作。

 

 注意：此流程只工作在，如果WHERE條件的形式像上述那樣，表的每個列必需被驗證是否等與一些任意常數（不需要相同的常數為每列）。例如，如果上述例子的WHERE語句中沒有col1=const1，那麼我們不會計算p_func分區函數的值，也不會約束實際被用的分區集。

 

 區間遊歷（Walking）

 假設一個分區表t定義成columns列集，分區型別p_type，分區函數p_func使用integer型別類

，如下：

p_type(p_func(int_col))
...
 假設我們有以下形式的WHERE條件查詢：

WHERE const1  我們能縮小此情況的條件成一系列單點間（Single-Single- Point Intervals），如下，透過轉換此WHERE語句為下列關係：

int_field=const1       OR
int_field=const1 + 1   OR         OR
int_field=const2

 

 在在原始碼裡，這種轉換被稱為區間遊歷（Walking）。遊歷短的區間成本是不貴的，這樣我們才能縮小分區數來掃描小的分區。然爾，遊歷長的區間不是那麼非常有效的，需要檢查大量的分區，這樣的話，可能所有分區都會被掃描的。

 

 區間映射（mapping）

 假設如下的分區表定義：

CREATE TABLE t (columns)

PARTITION BY RANGE|LIST(unary_ascending_function

是以下形式中的一種：

const1 t.column const1

 自分區函數是升序，看如下的關係：

const
  => p_func(const1) p_func(t.column)  用A和B表示這關係的最左和最右部分，我們能重寫關係為：


A  注意：在這個實例中，區間是關閉的且有兩個界值。但是，類似的推論可以類推到其它類型的區間。

 

 如範圍分區（RANGE partitioning），每個分區佔據一個區間於分區函數值的軸線上，每個區間是不相連的，如下：

     p1      p2
  table partitions    ----- -x------x--------x-------->

  search interval     ----x============== x----------->
                          A              B
 一個分區需要被訪問，當且僅當如果它的區間和搜索區間[A, B]沒有空的交叉點。

 

 如列舉分區（LIST partitioning），各分區包含點集於分區函數值的軸線上，各分區會產生不同的交叉點，如下：

  p2   p1   p1   p0
table partitions    - -+---+----+----+----+----+---->

search interval     ----x===================x------>
                  
 一個分區需要被訪問，至少一個交叉點在搜尋區間[A, B]裡。所使用的分區集可確定運行從A到B，並收集它們的點在這個搜尋範圍內的分區。

 

 子分區區間（subpartitioning intervals）

 在前面部分我們描述幾種從基本的WHERE條件推斷出在用分區集。一切都表明，這些分區的推斷方法都適合子分區，除範圍分區（RANGE partitioning）和列舉分區（LIST partitioning）的子分區外。

 自每個分區以相同的方式被分子分區，我們會找出在每個分區內的哪個子分區會被訪問。

 

 從WHERE語句到區間（From WHERE Clauses to Intervals）

 之前的章節講述了，從表示分區和子分區區間的WHERE語句推斷出分區集。現在我們來看看如何從任一WHERE語句抽出區間。

 

 抽取的流程使用範圍分析器（RANGE Analyzer），屬於MySQL最佳化器的一部分，它產生範圍RANGE存取的計畫。這是因為這個任務是相似的。兩種WHERE語句的形式：RANGE存取類型使用索引範圍（區間）掃描；分區裁切（partition pruning）模組使用分區區間，用來決定哪個分區被使用。

 為了分區裁剪（partition pruning），範圍分析器（RANGE Analyzer）與WHERE語句被調用，一個由分區和子分區函數使用的表的列清單：

(part_col1, part_col2, ... part_colN, part_colN, subpart_col1, subpart_col2, ... subpart_colM)
 範圍分析器（RANGE Analyzer）工作的結果稱為SEL_ARG圖。這是一個很複雜的結構，我們不打算在這裡描述它。目前這個文化討論的重點是我們能遊歷所有分區，並收集分區和子分區的區間。

 

 如下例子闡明結構和遊歷流程。假設表t依下列的分區：

CREATE TABLE t (..., pf INT, sp1 CHAR(5), sp2 INT, ... )

  PARTITION BY LIST (pf)
  SUBPARTITION BY HASH(sp1, sp2) (
    PARTITION p0 VALUES IN (1),
    PARTITION p1 VALUES IN (2),
    PARTITION p2 VALUES IN (3),]
  );
現假設對錶t的一個很複雜的WHERE語句查詢：


pf=1 AND (sp1='foo' AND sp2 IN (40,50))

OR

(pf1=3 OR pf1=4) AND sp1='bar' AND sp2=33

OR

((pf=3 OR pf=4) AND sp1=5)

OR

p=8

 

OR

p=8

 

（根）
   |               :
   |分區：           |              :
                  -----+
   ---| pf=1 |----:-----| sp1='foo' |---| sp2=40 |
       +------+    : +-----------+   +--------+
          |       :                    :                     +--------+
              | sp2=50 |
          | :                     +--------+
          |    
       +------+    :     +-----------+   +--------+
       | pf=3 |----:--+--| sp1='吧台' |---| sp2=33 |
       +--------+    :  |  +----- -------+   +--------+
          |        :  |
       +------+   +- ----+    :
          |       :
           +-----------+
       | pf=8 |----:----- | sp1='baz' |
       +------+    :     +-----------+

  上述圖表，垂直的邊界（|）代表OR，橫的（-）代表AND ，的和垂直的線也代表AND。


 

 分區修剪）代碼遊歷從圖上方到下方，從左橫到右邊，並做瞭如下的推

1。在最上和最左的再次區間，從使用分區的空集合開始遊歷：

2。

執行pf=1的區間分析，找出分區P0的對應集合，右邊到sp1='foo'
右移，到sp2=40

分析sp1='foo' AND sp2=40區間，在某SP1子分區找到行。推論一：在每個分區組成集合P0，標識子分區SP1「被使用」

下移到sp2=50 

分析sp1= 'foo'區間和sp2=50區間，在某SP2子分區找到行。推論二：在每個分區組成集合P0，標識子分區SP2「被使用」

移回pf=1，然後下稱到pf =3 

3。

執行pf=3的區間分析，找到分區P1的對應集合，右移到sp1='bar' 
再右移，到sp2=33

分析sp1='bar' AND sp2= 33區間，在某某SP3子分割區找到行。推論三：在每個分區組成集合P1，標識子分區SP3「被使用」
移回pf=3，然後下移到pf=4

4。

執行pf=4的區間分析，找到分區P2的相應集合，右移到sp2='bar'

執行移動和類似的推論已在pf=3驗證正確。這樣的效果是比較差的，因為我們將再次分析sp1='bar' AND sp2=33區間，但這個操作不會很大影響到整體效能。

移回pf=3，然後下稱到pf=8

5。

執行pf =8的區間分析，找出分區P3的對應集合，右移到sp1='baz'

現在到了sp1='baz'，發現不能再向右移動，也不能建構子分區區間。我們記錄下，並返回pf=8
從之前的過程，我們不能再限制子分區區間了，所以推論：在P3分區集裡的每個分區，假設所有的子分區都是有效在用的。

6。試著從pf=9下移，發現到尾，所以遊歷圖也就完成。

 

 注意：在特定的情況下，範圍分析器（RANGE Analyzer）的結果會有幾種的SEL_ARG圖，這圖是由OR或AND操作符組成的。出現這種情況對於WHERE語句，要么是非常複雜的要么是一個單一的區間列表建構。對這種情況，分區裁剪（partition pruning）代碼採用適當的操作，例：

SELECT * FROM t1 WHERE partition_id=10 OR subpartition_id=20
 在這個實例中，沒有單一的區間被構建，但分區（partition pruning）程式碼正確地推斷了使用的分區集是聯合：

所有在分區裡的子分區包含了partition_id=10的行，在每個分區裡一個子分區包含subpartition_id=20的行。

 

 原始程式碼中分區裁切（partition pruning）實作

 原始程式碼的簡單解說：

sql/opt_range.cc：
這程式碼包含了從WHERWHER ，方法prune_partitions()。關於分區裁切（partition pruning）的都有詳細的行行程式碼註釋，從PartitionPruningModule程式碼開始：

sql/partition_info.h：

class partition_info {
  ...
  /*
class partition_info {
  ...
  /*
. away) 部分。    on this partitioned table (used by the code in opt_range .cc)

  */

  get_partitions_in_range_iter get_part_iter_for_interval;
  get_partitions_in_range_iter get_subpart_iter_for_interval； 。

 

 分區檢索

 如果分區表被一系列索引檢索（即ref，eq_ref，ref_or_null連接存取方式）訪問，MySQL會檢查是否需要所有分區做索引檢索或限制訪問到特定的分區。例：

CREATE TABLE t1 (a INT, b INT);

INSERT INTO t1 VALUES (1,1),(2,2),(3,3);

CREATE TABLE t2 (

  keypart2 INT,

    KEY(keypart1, keypart2)

)

PARTITION BY HASH(keypart2);

INSERT INTO t2 VALUES (1,1),(2,2),(3,3);如下：

SELECT * FROM t1, t2

    WHERE  t2.keypart1=t1.a
    AND    t2.keypart2=t1.b;
利用如下算法執行：


(for each record in t1:)

{

  t2 ->index_read({current-value-of(t1.a), current-value-of(t1.b)});

  while( t2->index_next_same() )

    pass row combination to query output; 在index_read()呼叫中，分區表句柄會挖掘出被確定所有分區列的值，在這個例子中，是單一列b，接著找出一個分區存取。如果這個分區被裁剪過，就沒其它的分區可訪問。

 以上就是MySQL Internals Optimizer的內容，更多相關文章請關注PHP中文網（www.php.cn）！