深入解析：從源碼窺探MySQL優(yōu)化器

（注:此圖出自李海翔）

上圖展示了優(yōu)化器的大致執(zhí)行過程，可以簡單描述為：

1 根據(jù)語法樹及統(tǒng)計統(tǒng)計，構(gòu)建初始表訪問數(shù)組（init_plan_arrays）

2 根據(jù)表訪問數(shù)組，計算每個表的最佳訪問路徑(find_best_ref)，同時保存當(dāng)前最優(yōu)執(zhí)行計劃（COST最?。?/span>

3 如果找到更優(yōu)的執(zhí)行計劃則更新最優(yōu)執(zhí)行計劃，否則優(yōu)化結(jié)束。

從上述流程可以看出，執(zhí)行計劃的生成是一個“動態(tài)規(guī)劃/貪心算法”的過程，動態(tài)規(guī)劃公式可以表示為：Min(Cost(Tn+1)) = Min(Cost(T1))+Min(Cost(T2))+...Min(Cost(Tn-1))+Min(Cost(Tn)),其中Cost(Tn)表示訪問表T1 T2一直到Tn的代價。如果優(yōu)化器沒有任何先驗知識，則需要進(jìn)行 A(n,n) 次循環(huán)，是一個全排列過程，很顯然優(yōu)化器是有先驗知識的，如表大小，外連接，子查詢等都會使得表的訪問是部分有序的，可以理解為一個“被裁減”的動態(tài)規(guī)劃，動態(tài)規(guī)則的核心函數(shù)為：Join::Best_extention_limited_search，在源碼中有如下代碼結(jié)構(gòu)：

bool Optimize_table_order::best_extension_by_limited_search(
         table_map remaining_tables,
         uint      idx,
         uint      current_search_depth)
{
      for (JOIN_TAB **pos= join->best_ref + idx; *pos; pos++)
    {
      ......
         best_access_path(s, remaining_tables, idx, false,
                       idx ? (position-1)->prefix_rowcount : 1.0,
                       position);
......
  if (best_extension_by_limited_search(remaining_tables_after,
                                             idx + 1,
                                             current_search_depth - 1))
          ......
          backout_nj_state(remaining_tables, s);
......
}
}

以上代碼是在一個for循環(huán)中遞歸搜索，這是一個典型的全排列的算法。

MySQL的優(yōu)化器對于Oracle來說還顯得比較幼稚。Oracle有著各種豐富的統(tǒng)計信息，比如系統(tǒng)統(tǒng)計信息，表統(tǒng)計信息，索引統(tǒng)計信息等，而MySQL則需要更多的常量，其中MySQL5.7提供了表mysql.server_cost和表mysql.engine_cost，可以供用戶配置，使得用戶能夠調(diào)整優(yōu)化器模型，下面就幾個常見而又非常重要的參數(shù)進(jìn)行介紹：

1 #define ROW_EVALUATE_COST 0.2f

  計算符合條件的行的代價，行數(shù)越多，代價越大

2 #define IO_BLOCK_READ_COST 1.0f

  從磁盤讀取一個Page的代價

3 #define MEMORY_BLOCK_READ_COST 1.0f

 從內(nèi)存讀取一個Page的代價，對于Innodb來說，表示從一個Buffer Pool讀取一個Page的代價，因此讀取內(nèi)存頁和磁盤頁的默認(rèn)代價是一樣的

4 #define COND_FILTER_EQUALITY 0.1f

等值過濾條件默認(rèn)值為0.1，例如name = ‘lily’, 表大小為100，則返回10行數(shù)據(jù)

5 #define COND_FILTER_INEQUALITY 0.3333f

非等值過濾條件的默認(rèn)值是0.3333,例如col1>col2

6 #define COND_FILTER_BETWEEN 0.1111f

 Between過濾的默認(rèn)值是0.1111f，例如:col1 between a and b

......

這樣的常量很多，涉及到過濾條件、JOIN緩存、臨時表等等各種代價，理解這些常量后，看到執(zhí)行計劃的Cost后，你會有種豁然開朗的感覺！

在MySQL中，執(zhí)行select @@optimizer_trace, 得到如下參數(shù)：

index_merge=on,index_merge_union=off,index_merge_sort_union=off, index_merge_intersection=on, engine_condition_pushdown=on, index_condition_pushdown=on, mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,subquery_materialization_cost_based=on, use_index_extensions=on, condition_fanout_filter=on

在流程圖中的函數(shù)中，存在大量如下代碼：

Opt_trace_object trace_ls(trace, "searching_loose_scan_index");

因此，在優(yōu)化器運行過程中，優(yōu)化器的執(zhí)行路徑也被保存在Opt_trace_object中，進(jìn)而保存在information_schema.optimizer_trace中，方便用戶查詢和跟蹤。

5.1 全表掃描

select * from sakila.actor;

表actor統(tǒng)計信息如下：

主鍵actor_id統(tǒng)計信息如下：

執(zhí)行計劃：  

{                                                                                           
  "query_block": {                                                                                        
    "select_id": 1,                                                                       
    "cost_info": {                                                                                            
      "query_cost": "41.00"                                                                                    
    },                                                       
    "table": {                                                            
      "table_name": "actor",                                                                                    
      "access_type": "ALL",                                                                      
      "rows_examined_per_scan": 200,                                                                 
      "rows_produced_per_join": 200,                              
      "filtered": "100.00",                                                                  
      "cost_info": {                                                          
        "read_cost": "1.00",                                                                    
        "eval_cost": "40.00",                                                              
        "prefix_cost": "41.00",                                                               
        "data_read_per_join": "56K"  
      },                                                       
      "used_columns": [                                                                 
        "actor_id",                                                      
        "first_name",                                                            
        "last_name",                                                             
        "last_update",                                                            
        "id"                                                          
      ]                                                         
    }                                                                 
  }                                                                
}
IO_COST = CLUSTER_INDEX_SIZE * PAGE_READ_TIME = 1 * 1 =1;
EVAL_COST = TABLE_ROWS*EVALUATE_COST = 200 * 0.2 =40;
PREFIX_COST = IO_COST + EVAL_COST;

注意以上過程忽略了內(nèi)存頁和磁盤頁的訪問代價差異。

 5.2 表連接時使用全表掃描

SELECT
  *
FROM
  sakila.actor a,
  sakila.film_actor b
WHERE a.actor_id = b.actor_id

表film_actor中索引(actor_id,film_id)統(tǒng)計信息如下：

{                                      
  "query_block": {                   
    "select_id": 1,                    
    "cost_info": {                   
      "query_cost": "1338.07"             
    },                                
    "nested_loop": [                
      {                              
        "table": {       
          "table_name": "a",  
          "access_type": "ALL", 
          "possible_keys": [   
            "PRIMARY"            
          ],                  
          "rows_examined_per_scan": 200, 
          "rows_produced_per_join": 200, 
          "filtered": "100.00", 
          "cost_info": {       
            "read_cost": "1.00", 
            "eval_cost": "40.00", 
            "prefix_cost": "41.00",  
            "data_read_per_join": "54K"  
          },                     
          "used_columns": [     
            "actor_id",      
            "first_name",    
            "last_name",      
            "last_update"          
          ]                          
        }                              
      },                              
      {                            
        "table": {               
          "table_name": "b",     
          "access_type": "ref",  
          "possible_keys": [  
            "PRIMARY"               
          ],                     
          "key": "PRIMARY",       
          "used_key_parts": [     
            "actor_id"              
          ],                    
          "key_length": "2",     
          "ref": [            
            "sakila.a.actor_id"    
          ],                 
          "rows_examined_per_scan": 27,  
          "rows_produced_per_join": 5461, 
          "filtered": "100.00",     
          "cost_info": {          
            "read_cost": "204.67", 
            "eval_cost": "1092.40", 
            "prefix_cost": "1338.07", 
            "data_read_per_join": "85K" 
          }, 
          "used_columns": [  
            "actor_id",            
            "film_id",        
            "last_update"           
          ]                              
        }                               
      }                                 
    ]                                     
  }                                          
}

第一張表actor的全表掃代價為41，可以參考示例1。

        第二個表就是NET LOOP 代價：

read_cost(204.67) =prefix_rowcount * (1 + keys_per_value/table_rows*cluster_index_size =

200 * (1+27/13863*12)*1

注意：27 相當(dāng)于對于每個actor_id，film_actor的索引估計，對于每個actor_id,平均有27條記錄=5462/200

Table_rows是如何計算的呢？

Film_actor表的實際記錄數(shù)是5462，一共12個page，11個葉子頁，總大小為11*16K(默認(rèn)頁大小)=180224Byte, 最小記錄長度為26(通過計算字段長度可得),13863 = 180224/26*2, 2是安全因子，做最差的代價估計。

表連接返回行數(shù)=200*5462/200，因此行估算代價為5462*0.2=1902.4

5.3 IN查詢

表film_actor中索引idx_id(film_id)統(tǒng)計信息如下：

EXPLAIN SELECT * FROM ACTOR WHERE actor_id IN (SELECT film_id FROM film_actor)
{                                  
  "query_block": {              
    "select_id": 1,             
    "cost_info": {                  
      "query_cost": "460.79"    
    },                            
    "nested_loop": [               
      {                      
        "table": {        
          "table_name": "ACTOR", 
          "access_type": "ALL", 
          "possible_keys": [ 
            "PRIMARY"          
          ],               
          "rows_examined_per_scan": 200, 
          "rows_produced_per_join": 200, 
          "filtered": "100.00", 
          "cost_info": { 
            "read_cost": "1.00", 
            "eval_cost": "40.00", 
            "prefix_cost": "41.00", 
            "data_read_per_join": "56K" 
          },                 
          "used_columns": [ 
            "actor_id",  
            "first_name",   
            "last_name", 
            "last_update",   
            "id"                 
          ]                    
        }                         
      },                         
      {                        
        "table": {     
          "table_name": "film_actor",     
          "access_type": "ref", 
          "possible_keys": [ 
            "idx_id"            
          ],                
          "key": "idx_id", 
          "used_key_parts": [ 
            "film_id"           
          ],               
          "key_length": "2",   
          "ref": [      
            "sakila.ACTOR.actor_id" 
          ],           
          "rows_examined_per_scan": 5, 
          "rows_produced_per_join": 200, 
          "filtered": "100.00", 
          "using_index": true, 
          "first_match": "ACTOR", 
          "cost_info": { 
            "read_cost": "200.66", 
            "eval_cost": "40.00", 
            "prefix_cost": "460.79", 
            "data_read_per_join": "3K" 
          },                      
          "used_columns": [  
            "film_id"            
          ],                      
          "attached_condition": "(`sakila`.`actor`.`actor_id` = `sakila`.`film_actor`.`film_id`)"                                                                        
        }                            
      }                                
    ]                                     
  }                                       
}
id  select_type  table       partitions  type    possible_keys  key     key_len  ref                      rows  filtered  Extra                                        
------  -----------  ----------  ----------  ------  -------------  ------  -------  ---------------------  ------  --------  ---------------------------------------------
     1  SIMPLE       ACTOR       (NULL)      ALL     PRIMARY        (NULL)  (NULL)   (NULL)                    200    100.00  (NULL)                                       
     1  SIMPLE       film_actor  (NULL)      ref     idx_id         idx_id  2 
sakila.ACTOR.actor_id       5    100.00  Using where; Using index; FirstMatch(ACTOR)

從執(zhí)行計劃中可以看出，MySQL采用FirstMatch方式。在MySQL中，半鏈接優(yōu)化方式為：Materialization Strategy，LooseScan，F(xiàn)irstMatch，DuplicateWeedout，默認(rèn)情況下四種優(yōu)化方式都是存在的，選取方式基于最小COST?，F(xiàn)在我們以FirstMatch為例，講解優(yōu)化器的執(zhí)行流程。

 SQL如下：

  select * from Country
where Country.code IN (select City.Country
                       from City
                       where City.Population > 1*1000*1000)
      and Country.continent='Europe'

從上圖可以看出，F(xiàn)irstMatch是通過判斷記錄是否已經(jīng)在結(jié)果集中存在來減少查詢和匹配流程。

表actor的訪問代價可以參考示例1.

表film_actor表的訪問代價200.66是如何計算的呢？

訪問表film_actor中索引字段film_id,MySQL會走覆蓋索引掃，即IDEX_ONLY_SCAN,一次索引訪問的代價是如何計算的呢？

參考函數(shù)double handler::index_only_read_time(uint keynr, double records)

索引塊大小為16K,并且MySQL假設(shè)塊都是半滿的，則一個塊能夠存放的索引記錄數(shù)為：

16K/2/(索引長度+主鍵長度(注：二級索引存儲的是主鍵的引用))=16K/2/(2+4)+1=1366,

其中主鍵為(actor_id,film_id),兩個字段都是smallint,占用4個字節(jié)，而索引idx_id(film_id)是2個字節(jié)，因此每次訪問索引的代價為：（5.47+1366-1）/1366 = 1.0032, 訪問film_actor表一共需要200次，總訪問代價為：200*1.0032=200.66

總代價460.79 = 表actor的訪問代價+表film_actor訪問代價+行估算代價=

41+200.66+200*1*5.47*1*02,其中兩個1分別表示過濾因子，由于兩個表均沒有過濾條件因此過濾因子都是1。