程式師世界 >> 數據庫知識 >> MYSQL數據庫 >> 關於MYSQL數據庫 >> MySQL 查詢優化器

MySQL 查詢優化器

編輯：關於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::prepare()
       setup_fIElds()
     JOIN::optimize()            /* optimizer is from here ... */
       optimize_cond()
       opt_sum_query()
       make_join_statistics()
         get_quick_record_count()
         choose_plan()
           /* Find the best way to Access tables */
           /* as specifIEd by the user.          */
           optimize_straight_join()
             best_Access_path()
           /* Find a (sub-)optimal plan among all or subset */
           /* of all possible query plans where the user    */
           /* controls the exhaustiveness of the search.   */
           greedy_search()
             best_extension_by_limited_search()
               best_Access_path()
           /* Perform an exhaustive search for an optimal plan */
           find_best()
       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.優化常數關系

常數等值傳遞

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

WHERE column1 = column2 AND column2 = 'x'

這種表達式，眾所周知，如果A=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，最後為：

WHERE s1 = 7

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

WHERE (0 = AND s1 = 5)

因為這條件永遠不為TRUE，在EXPLAIN分析中會顯示Impossible WHERE。簡單地說，MySQL會說WHERE條件被優化過。

如果一個字段不能為NULL，優化器會剔除所有不相關的IS NULL的條件，這樣

WHERE not_null_column IS NULL

這種條件總為FLASE情況；且

WHERE not_null_column IS NOT NULL

這種條件總為TRUE情況，所以這種字段查詢的條件也被剔除。這種判斷是很微妙的。舉個例：在一個OUT JOIN外聯接，被定義成NOT NULL字段仍然含有NULL值，優化器就會單獨排除IS NULL條件在這種特殊情況中。

優化器不會檢查所有的Impossible WHERE的條件，因為這方面可能性太多了。例如：

CREATE TABLE Table1 (column1 CHAR(1));
...
SELECT * FROM Table1 WHERE column1 = 'Popgo';

優化器不會剔除這種查詢的條件，即使在CREATE TABLE定義中使之成為不可能的條件。

可合並的常數值

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

WHERE column1 = 1 + 2

最後為：

WHERE column1 = 3

在之前說的常數等值傳遞 ，優化器很容易將這種查詢語句合並在一起。這操作就簡化了結果。

常數值和常數表

MySQL常數值，有時不單單指在查詢的SQL語句的字面意思上，也可在常數表（constant tables）的內容裡。常數表（constant tables）被定義為：

1。無記錄或一條記錄的表

2。表的表達式被WHERE條件約束，而且包含的表達式形式column = "constant"，或者表的主鍵的所有字段，或者任何唯一鍵的所有字段（唯一鍵的字段定義為NOT NULL）

例如，Table0表的定義包含：

... PRIMARY KEY (column1,column2)

然後，查詢表達式：

FROM Table0 ... WHERE column1=5 AND column2=7 ...

會返回常數表（constant tables）。更多簡單地，如果Table1表的定義包含：

... unique_not_null_column INT NOT NULL UNIQUE

然後，查詢表達式：

FROM Table1 ... WHERE unique_not_null_column=5

也會返回常數表（constant 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 = Table2.any_column
    AND Table1.unique_not_null_column = 5;

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

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

Impossible WHERE noticed after reading const tables

相反，如果取值成功，也就是在表Table1裡unique_not_null_column = 為一條記錄值，MySQL會轉化為如下語句：

SELECT 5, Table2.any_column
    FROM Table1, Table2
    WHERE 5 = Table2.any_column
    AND 5 = 5;

事實上，這是一個很好的例子。優化器因前面提到的常數等值傳遞進行一些語句轉化。另外，為什麼要先描述常數等值傳遞，因為它在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 = 6

如果indexed_column有比較好的JOIN聯接類型，它更可能成為驅動表達式。對它來說，你也會遇到各種不同的例外，但對這句描述，是第一個簡單的優化法則。

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

最壞執行計劃：掃描讀表的所有行。這也叫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 of tables-joined-so-far */
   partial_plan_cost,    /* in, cost of partial_plan */
   remaining_tables,     /* in, set of tables not referenced in partial_plan */
   best_plan_so_far,     /* in/out, best plan found so far */
   best_plan_so_far_cost)/* in/out, cost of best_plan_so_far */
{
   for each table T from remaining_tables
   {
     /* Calculate the cost of using table T. Factors that the
        optimizer takes into account may include:
          Many rows in table (bad)
          Many key parts in common with tables so far (very good)
          Restriction mentioned in the WHERE clause (good)
          Long key (good)
          Unique or primary key (good)
          Full-text key (bad)
        Other factors that may at some time be worth considering:
          Many columns in key
          Short average/maximum key length
          Small table file
          Few levels in index
          All ORDER BY / GROUP columns come from this table */
     cost = complex-serIEs-of-calculations;
     /* Add the cost to the cost so far. */
     partial_plan_cost+= cost;

     if (partial_plan_cost >= best_plan_so_far_cost)
       /* partial_plan_cost already too great, stop search */
       continue;

     partial_plan= expand partial_plan by best_Access_method;
     remaining_tables= remaining_tables - table T;
     if (remaining_tables is not an empty set)
     {
       find_best(partial_plan, partial_plan_cost,
                 remaining_tables,
                 best_plan_so_far, best_plan_so_far_cost);
     }
     else
     {
       best_plan_so_far_cost= partial_plan_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 and RIGHT JOIN Optimization。

RANGE聯接類型

有些條件可以使用索引，但是在一個鍵的范圍（range）或寬度內。這些稱為范圍條件，最常看到的是帶>，>=，<，<=，IN，LIKE，BETWEEN的查詢表達式。

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

column1 IN (1,2,3)

和這個是一樣的：

column1 = OR column1 = OR column1 = 3

MySQL同樣對待這種語句，無需對查詢條件的IN到OR或OR到IN做轉變。

如下語句，優化器也會用到索引（范圍查詢range search）

column1 LIKE 'x%'

但這種就不行：

column1 LIKE '%x%'

也就是說，如果匹配條件的第一個字符是通配符，那就沒范圍查詢。

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

column1 BETWEEN 5 AND 7

和

column1 >= AND column1 <= 7

如果查詢的條件，檢索了太多的索引鍵，優化器可能轉變RANGE聯接類型為ALL JOIN聯接類型。像這種轉變，特別可能在<和>條件和多級第二索引（secondary indexes）中。源代碼見：/myisam/mi_range.c，mi_records_in_range()（MyISAM索引）。

INDEX聯接類型

考慮這個查詢

SELECT column1 FROM Table1;

如果column1有加索引，那優化器可能選擇從加的索引取值，而不是從表（全表掃描）。像這種方式的索引，一般稱為覆蓋索引（COVERING INDEX）。在EXPLAIN Extra描述中，MySQL會簡單用INDEX單詞來表示覆蓋索引（COVERING INDEX）。

語句：

SELECT column1, column2 FROM Table1;

只有當索引被定義成如下，優化器會使用JOIN聯接類型為INDEX：join type = index

CREATE INDEX ... ON Table1 (column1, column2);

換句話說，被查詢的字段（如：column1, column2）都必需被加索引的，被加索引的多個字段是無順序之分的。因此，更有意義的嚴格定義一個多列索引（multiple-column index）作為一個覆蓋索引（COVERING INDEX）來使用，無論搜索的考慮。

INDEX MERGE聯接類型

概述

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

cond_1 OR cond_2 ... OR cond_N

轉化的條件是：每個cond_i（cond_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<c2 OR key3 IN (c3,c4);

SELECT * FROM t WHERE (key1=c1 OR key2<c2) AND nonkey=c3;

索引合並（INDEX MERGE），是實現成一種范圍鍵（range key）並以cond_i（cond_1，cond_2。。。）條件構造成的容器。在做索引合並（INDEX MERGE）時，MySQL檢索每個鍵掃描（keyscans）的行，然後通過一個消除重復的過程來運行它們。目前類Unique用於消除重復的。

INDEX MERGE優化器

單一SEL_TREE對象不能被構造成在OR語句中有不同成員的鍵的條件，類似這條件：

key1 < c1 OR key2 < c2

從MySQL5.0開始，這些條件被索引合並（INDEX MERGE）方法，和范圍優化器（range optimizer）結構的類SEL_IMERGE處理。SEL_IMERGE代表了若干SEL_TREE對象的析取，這種被表示為：

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）上的索引合並（INDEX MERGE）會更快。

索引合並（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
   ...                          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 AND ... AND cond_key_N)

每一個cond_key_i都是一個鍵的組成部分的條件。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 < key_part_n AND key_part_n < sup_val) (1)
                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 <= inf_val。

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

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

行檢索算法

索引合並（INDEX MERGE）有如下兩個步驟：

准備階段：

activate 'index only';
foreach key_i in (key_scans \ clustered_pk_scan)
{
  while (retrIEve next (key, rowid) pair from key_i)
  {
    if (no clustered PK scan ||
        row doesn't match clustered PK scan condition)
      put rowid into Unique;
  }
}
deactivate 'index only';

行檢索階段：

for each rowid in Unique
{
  retrIEve row and pass it to output;
}
if (clustered_pk_scan)
{
  while (retrIEve next row for clustered_pk_scan)
   pass row to output;
}

源代碼見：sql/opt_range.cc，QUICK_INDEX_MERGE_SELECT類函數的索引合並（INDEX MERGE）行檢索代碼。

3.換位（Transpositions）

MySQL支持簡單語句表達式的換位（反轉關系操作符的操作數的順序）。換句話說：

WHERE - 5 = column1

此語句可轉化成：

WHERE column1 = -5

然而，MySQL不支持有運算存在的換位，如：

WHERE 5 = -column1

而這句不能同等對待：

WHERE column1 = -5

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

AND關系

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

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

這步驟描述了優化器決斷的過程：

1。如果兩個條件都沒被索引，使用順序掃描（全表掃描）。
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);
...
SELECT * FROM Table1 WHERE s1 = AND 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和column2都有索引的，每個SELECT都會使用索引掃描，各自的結果集會被合並。注意：此查詢可能產生相同的結果集，如果查詢使用了順序掃描OR的例子。

NOT（<>）關系

一個邏輯條件如下：

column1 <> 5

等價於：

column1 < 5 OR column1 > 5

然而，MySQL不會對這種條件進行轉化語句。如果你覺得用RANG查詢效果會更好，你必需自己手動做語句轉化。

還有一個邏輯條件如下：

WHERE NOT (column1 != 5)

等價於：

WHERE column1 = 5

對這種情況，MySQL也不會做語句轉化的。

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

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'
ORDER BY column2;

如果column1和column2都有索引的，優化器會走在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 < 'a';

如果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, ...

更深入假設，表tblY通過ref或eq_ref 聯合類型被訪問：

tblY.key_column = tblX.column

或者，使用多個鍵部分的ref類型訪問：

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

tblX.column可以為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.key_part2 = expr2 AND ...

在調用索引檢索前，我們確定任何expri（expr1，expr2，expr3。。。）值是否為NULL。如果是，我們不會調用檢索，而是會馬上返回沒找到匹配數組。

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

2.分區相關的優化

這部分討論MySQL分區相關的優化。MySQL5.1分區相關概念和實現見：Partitioning。

分區裁剪（pruning）

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

“提供一個分區表的查詢，比對此分區表的DDL語句和查詢中的任何WHERE或ON語句，且找出這查詢訪問的最小分區集。”

這樣得到的分區集會比表所有分區的集合小很多，這個分區集也是之後查詢語句要用到的。沒被加入這個分區集的其它分區，就不會被訪問的，也就是說被裁剪掉的分區。正因為這樣，查詢的執行速度變得更快。

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個列的分區表，通過分區類型p_type和分區函數p_func，表示如下：

CREATE TABLE t (columns)
PARTITION BY p_type(p_func(col1, col2,... colN)...);

再假設查詢的WHERE條件形式如下：

WHERE t.col1=const1 AND t.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類型字段int_col，如下：

CREATE TABLE t (columns)
PARTITION BY
p_type(p_func(int_col))
...

假設我們有如下形式的WHERE條件查詢：

WHERE const1 <= int_col <= const2

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

int_fIEld=const1       OR
int_fIEld=const1 + 1   OR
int_fIEld=const1 + 2   OR
...                    OR
int_fIEld=const2

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

如下參數決定區間游歷（Walking）的值：

#define MAX_RANGE_TO_WALK=10

注意：如下條件關系也會利用上述區間游歷（Walking）的邏輯：

const1 >= int_col >= const2

區間映射（mapping）

假設如下的分區表定義：

CREATE TABLE t (columns)
PARTITION BY RANGE|LIST(unary_ascending_function(column))

假設我們對表t的查詢的WHERE語句，是如下形式中的一種：

const1 <= t.column <= const2
t.column <= const2
const1 <= t.column

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

const1 <= t.col <= const2

=> p_func(const1) <=

p_func(t.column) <= p_func(const2)

用A和B表示這關系的最左和最右部分，我們能重寫關系為：

A <= p_func(t.column) <= B

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

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

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

  search interval     ----x==============x----------->
                          A              B

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

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

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

search interval     ----x===================x------>
                        A                   B

一個分區需要被訪問，至少一個交叉點在搜索區間[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,
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),
    PARTITION p3 VALUES IN (4),
    PARTITION p4 VALUES IN (5),
  );

現假設對表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

SEL_ARG圖如下：

(root)
   |               :
   | Partitioning  :         Sub-partitioning
   |               :
   |               :
   |               :
   |   +------+    :     +-----------+   +--------+
   \---| pf=1 |----:-----| sp1='foo' |---| sp2=40 |
       +------+    :     +-----------+   +--------+
          |        :                         |
          |        :                     +--------+
          |        :                     | sp2=50 |
          |        :                     +--------+
          |        :
          |        :
       +------+    :     +-----------+   +--------+
       | pf=3 |----:--+--| sp1='bar' |---| sp2=33 |
       +------+    :  |  +-----------+   +--------+
          |        :  |
       +------+    :  |
       | pf=4 |----:--+
       +------+    :
          |        :
          |        :
       +------+    :     +-----------+
       | pf=8 |----:-----| sp1='baz' |
       +------+    :     +-----------+

上述圖表，豎的邊界（|）代表OR，橫的（-）代表AND，橫的和豎的線也代表AND。
分區裁剪（partition pruning）代碼游歷從圖上方到下方，從左邊到右邊，並做了如下的推論

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：

這代碼包含了從WHERE語句到區間（From WHERE Clauses to Intervals）的實現，方法prune_partitions()。關於分區裁剪（partition pruning）的都有詳細的行行代碼注釋，從PartitionPruningModule代碼開始：

sql/partition_info.h：

class partition_info {
  ...
  /*
    Bitmap of used (i.e. not pruned away) partitions. This is where result
    of partition pruning is stored.
  */
  MY_BITMAP used_partitions;

  /*
    "virtual function" pointers to functions that perform interval analysis
    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;

};

sql/sql_partition.cc：

這代碼包含了實現所有分區區間分析類型的方法。

分區檢索

如果分區表被一系列索引檢索（即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 (
    keypart1 INT,
    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，接著找出一個分區訪問。如果這個分區被裁剪過，就沒其它的分區可訪問。

-EOF-