[源代碼分析]關(guān)于排序操作的代碼分析

justlooks

前幾天讀了下MySQL關(guān)于排序操作的代碼，頗有心得，這里和大家分享下，并做記錄便于以后查閱

對于排序MySQL會采用兩種方法，一種是參與排序的是order by之后的列以及指向行數(shù)據(jù)的指針，而另一種方法是通過采用將select到的field和排序信息相結(jié)合，那么排序時相當(dāng)與將field同時處理了，好處就是不需要再次通過指針讀記錄進(jìn)行處理，壞處就是需要額外讀取對應(yīng)的select field域到輔助結(jié)構(gòu)，這兩者有個平衡點，下面來具體看代碼

先來看結(jié)構(gòu)

這個結(jié)構(gòu)用來保存對應(yīng)的select fields信息

1. 
   
2. 40 typedef struct st_sort_addon_field {  
   
3. 41   Field *field;          存放select的結(jié)果域
   
4. 42   uint   offset;         存放該域開始的位置（注意NULL列位圖是放在最前面的）
   
5. 43   uint   null_offset;    如果該列可能為null,那么則記錄到的是在null位圖的具體位置
   
6. 44   uint   length;         計算對應(yīng)field參與排序的長度
   
7. 45   uint8  null_bit;       如果該列可能為null,那么則記錄到的是在null位圖的具體位置
   
8. 46 } SORT_ADDON_FIELD;
   

復(fù)制代碼

另外對于有序記錄的merge,MySQL采用的是2級merge，即先將小塊有序記錄合并成大塊，將大塊有序記錄合并成整塊，那么在期間會用到一個結(jié)構(gòu)來保存有序塊在臨時文件或者內(nèi)存中的信息，下面就是這個結(jié)構(gòu)的內(nèi)容

1. 
   
2. 48 typedef struct st_buffpek {   
   
3. 49   my_off_t file_pos;           有序塊在排序臨時文件中的開始位置
   
4. 50   uchar *base,*key;         指向放有序數(shù)據(jù)的緩沖區(qū)
   
5. 51   ha_rows count;            表中記錄數(shù)
   
6. 52   ulong mem_count;         在內(nèi)存中的記錄數(shù)
   
7. 53   ulong max_keys;          在buffer中的最大key數(shù)
   
8. 54 } BUFFPEK;
   

復(fù)制代碼

一級merge最多使用7個有序塊，二級merge最多用到15個有序塊

1. 
   
2. 21 #define MERGEBUFF       7
   
3. 22 #define MERGEBUFF2      15
   

復(fù)制代碼

另外一個關(guān)鍵結(jié)構(gòu)就是記錄排序信息的結(jié)構(gòu)，以及用于整個處理流程的param結(jié)構(gòu)(太長，這里不具體列出)

1. 
   
2. 844 typedef struct st_sort_field {
   
3. 2845   Field *field;                         需要排序的表列
   
4. 2846   Item  *item;                         排序的非表列（表達(dá)式等）
   
5. 2847   uint   length;                        排序表列或者表達(dá)式返回值長度
   
6. 2848   uint   suffix_length;                 排序的前綴長度
   
7. 2849   Item_result result_type;              結(jié)果類型
   
8. 2850   bool reverse;                        是否是降序標(biāo)識
   
9. 2851   bool need_strxnfrm;                   用于字符格式化
   
10. 2852 } SORT_FIELD;
    

復(fù)制代碼

具體的調(diào)用處理在sql/filesort.cc有定義

1. 
   
2. 104 ha_rows filesort(THD *thd, TABLE *table, SORT_FIELD *sortorder, uint s_length,
   
3. 105          SQL_SELECT *select, ha_rows max_rows,
   
4. 106                  bool sort_positions, ha_rows *examined_rows)
   

復(fù)制代碼

當(dāng)執(zhí)行的時候，執(zhí)行計劃被調(diào)整為FILESORT

1. 
   
2. 196   thd->query_plan_flags|= QPLAN_FILESORT;
   

復(fù)制代碼

而當(dāng)排序不是在內(nèi)存中時，執(zhí)行計劃被調(diào)整為QPLAN_FILESORT_DISK

1. 
   
2. 265     thd->query_plan_flags|= QPLAN_FILESORT_DISK;
   

復(fù)制代碼

那么以上兩者對應(yīng)的就是percona slow log 中的　Filesort　注解，以及  Filesort_on_disk　注解

那么關(guān)于內(nèi)存分配，分配的內(nèi)存是來自variable sort_buff_size的定義值，代碼中規(guī)定了最小的內(nèi)存下限為32K,或者做level 2 merge所需內(nèi)存的最大者

1. 
   
2. 221   memavl= thd->variables.sortbuff_size;
   
3. 222   min_sort_memory= max(MIN_SORT_MEMORY, param.sort_length*MERGEBUFF2);
   

復(fù)制代碼

當(dāng)然這里的32K是要打折扣的，除去管理數(shù)據(jù)的損耗

1. 
   
2. 97 #define MIN_SORT_MEMORY (32*1024-MALLOC_OVERHEAD)
   

復(fù)制代碼

那么當(dāng)sort_buff_size規(guī)定值太小，自然就會有問題

1. 
   
2. 237   if (memavl < min_sort_memory)
   
3. 238   {
   
4. 239     my_error(ER_OUT_OF_SORTMEMORY,MYF(ME_ERROR+ME_WAITTANG));
   
5. 240     goto err;
   
6. 241   }
   

復(fù)制代碼

MySQL根據(jù)sort_buff_size的值來確定能夠取到的排序記錄條數(shù)，并比較之前估計的記錄數(shù)，取小者，這里的char是用來放指向記錄的指針

1. 
   
2. 226     ulong keys= memavl/(param.rec_length+sizeof(char*));
   
3. 227     param.keys=(uint) min(records+1, keys);
   

復(fù)制代碼

并根據(jù)這個記錄數(shù)來分配內(nèi)存

1. 
   
2. 228     if ((table_sort.sort_keys=
   
3. 229      (uchar **) make_char_array((char **) table_sort.sort_keys,
   
4. 230                                     param.keys, param.rec_length, MYF(0))))
   
5. 231       break;
   

復(fù)制代碼

當(dāng)內(nèi)存比較緊張的時候，MySQL試圖減小取到的sort_buff_size值，重新計算記錄數(shù)，來減小內(nèi)存的消耗

1. 
   
2. 232     old_memavl=memavl;
   
3. 233     if ((memavl=memavl/4*3) < min_sort_memory && old_memavl > min_sort_memory)
   
4. 234       memavl= min_sort_memory;
   

復(fù)制代碼

在順利分配內(nèi)存后，MySQL調(diào)用find_all_keys將記錄放到緩沖區(qū)，并返回記錄總數(shù)

1. 
   
2. 249   if ((records=find_all_keys(&param,select,sort_keys, &buffpek_pointers,
   
3. 250                  &tempfile, selected_records_file)) ==
   
4. 251       HA_POS_ERROR)
   
5. 252     goto err;
   

復(fù)制代碼

在find_all_keys調(diào)用中，MySQL將找到的記錄每隔param->keys條記錄進(jìn)行排序，并把排序結(jié)果寫到tempfile,將排序塊位置信息寫到每個buffpek結(jié)構(gòu)中并將buffpek_pointers指向這些buffpek

1. 
   
2. 613       if (idx == param->keys)
   
3. 614       {
   
4. 615     if (write_keys(param,sort_keys,idx,buffpek_pointers,tempfile))
   
5. 616       DBUG_RETURN(HA_POS_ERROR);
   
6. 617     idx=0;　　　　　　　　　　
   
7. 618     indexpos++;　　　　　　　　
   
8. 619       }
   
9. 
   
10. 620       make_sortkey(param,sort_keys[idx++],ref_pos);　　# make_sortkey將讀到的記錄放入sort_keys緩沖
    

復(fù)制代碼

那么根據(jù)這些個有序塊個數(shù)，能夠判斷是否是內(nèi)存中排序和利用臨時文件進(jìn)行排序

1. 
   
2. 253   maxbuffer= (uint) (my_b_tell(&buffpek_pointers)/sizeof(*buffpek));
   

復(fù)制代碼

如果是內(nèi)存中排序，save_index調(diào)用Radixsort或者quicksort算法來進(jìn)行排序（這個是MySQL的核心排序算法)

1. 
   
2. 255   if (maxbuffer == 0)           
   
3. 256   {
   
4. 257     if (save_index(&param,sort_keys,(uint) records, &table_sort))
   
5. 258       goto err;
   
6. 259   }
   

復(fù)制代碼

那么有人說了為什么find_all_keys調(diào)用中已經(jīng)排過序了，為什么save_index調(diào)用還要再排一次？其實是這樣的，當(dāng)記錄能夠全部容納在內(nèi)存中時那么write_keys調(diào)用不會被執(zhí)行，那么其實返回的內(nèi)存中記錄是未經(jīng)排序的，所以這里需要調(diào)用save_index來處理排序
如果不幸使用磁盤上的臨時文件排序的話，MySQL會從buffpek_pointers中將所有有序塊的信息讀到 table_sort.buffpek　這個緩沖區(qū)

1. 
   
2. 271     if (!(table_sort.buffpek=
   
3. 272           (uchar *) read_buffpek_from_file(&buffpek_pointers, maxbuffer,
   
4. 273                                  table_sort.buffpek)))
   
5. 274       goto err;
   

復(fù)制代碼

那么接下來會調(diào)用merge_many_buff來進(jìn)行l(wèi)evel 1的merge動作，merge的結(jié)果會被寫入tempfile,注意到這里有序塊數(shù)目是傳指針進(jìn)去的，也就是說在level 1的merge過后maxbuffer的數(shù)目是不大于level 2的merge規(guī)定塊數(shù)(15)

1. 
   
2. 293     if (merge_many_buff(&param,(uchar*) sort_keys,buffpek,&maxbuffer,
   
3. 294             &tempfile))
   
4. 295       goto err;
   

復(fù)制代碼

接下來調(diào)用merge_index來進(jìn)行l(wèi)evel 2的merge,最終結(jié)果寫入outfile,(如果跳入這個調(diào)用會發(fā)現(xiàn)和上一個merge_many_buff的調(diào)用，都是調(diào)用同一個函數(shù)(merge_buffers)

1. 
   
2. 299     if (merge_index(&param,(uchar*) sort_keys,buffpek,maxbuffer,&tempfile,
   
3. 300             outfile))
   
4. 301       goto err;
   

復(fù)制代碼

其中filesort_merge_passes(sort_merge_passes)參數(shù)顯示了merge_buffers調(diào)用的次數(shù)

1. 
   
2. 1205   status_var_increment(current_thd->status_var.filesort_merge_passes);
   

復(fù)制代碼

另外就是本文開頭提到過的兩種排序方法選擇的依據(jù)，如果總的排序列長度超過max_length_for_sort_data則使用記錄指針和排序列信息進(jìn)行排序，否則創(chuàng)建addonf結(jié)構(gòu)，那么排序是依據(jù)排序信息和addonf信息，并不讀取記錄(因為需要獲取的結(jié)果集已經(jīng)在addonf中了)

1. 
   
2. 1583   if (length+sortlength > thd->variables.max_length_for_sort_data ||      
   
3. 1584       !(addonf= (SORT_ADDON_FIELD *) my_malloc(sizeof(SORT_ADDON_FIELD)*
   
4. 1585                                                (fields+1), MYF(MY_WME))))
   
5. 1586     return 0;
   

復(fù)制代碼

值得注意的是這里有一個例外，在生成addonf結(jié)構(gòu)的調(diào)用代碼里有一個判定，當(dāng)最終結(jié)果集中包含blob類型的列時，不會使用addonf結(jié)構(gòu)來做排序。另外，就是結(jié)果集包含可以是null列情況下，addonf排序結(jié)構(gòu)是要記錄NULL位圖信息的，也就是說NULL列對排序性能會有副作用，盡管這個影響并不是很大

1. 
   
2. 1572     if (field->flags & BLOB_FLAG)            
   
3. 1573       return 0;
   

復(fù)制代碼

而對于有序記錄塊的merge,MySQL是采用priority Queues的算法,而read_to_buffer調(diào)用是將有序塊內(nèi)容加載到buffpek->key指向的緩沖區(qū)位置，最終內(nèi)容插入到priority Queues進(jìn)行排序處理

1. 
   
2. 1247   for (buffpek= Fb ; buffpek <= Tb ; buffpek++)
   
3. 1248   {
   
4. 1249     buffpek->base= strpos;
   
5. 1250     buffpek->max_keys= maxcount;
   
6. 1251     strpos+= (uint) (error= (int) read_to_buffer(from_file, buffpek,
   
7. 1252                                                                          rec_length));
   
8. 1253     if (error == -1)
   
9. 1254       goto err;               
   
10. 1255     buffpek->max_keys= buffpek->mem_count;  // If less data in buffers than expected
    
11. 1256     queue_insert(&queue, (uchar*) buffpek);
    
12. 1257   }
    

復(fù)制代碼

另外最后需要提到的是關(guān)于sort abort錯誤，這個錯誤是在filesort調(diào)用末尾的錯誤處理階段被拋出

1. 
   
2. 300  err:
   
3. 
   
4. 325   if (error)　　　　　　　　　　　　　　　　　　　　　　　#如果錯誤則返回sort abort信息
   
5. 326     my_message(ER_FILSORT_ABORT, ER(ER_FILSORT_ABORT),
   
6. 327                MYF(ME_ERROR+ME_WAITTANG));
   
7. 328   else
   
8. 329     statistic_add(thd->status_var.filesort_rows,　　　　　#否則增加狀態(tài)參數(shù)sort_rows值
   
9. 330           (ulong) records, &LOCK_status);
   

復(fù)制代碼

因為之前調(diào)用開始時參數(shù)error被初始化為1,所以導(dǎo)致整個處理過程中途跳出都會觸發(fā)這個錯誤，具體的錯誤原因可以查閱goto err處代碼信息

1. 
   
2. 145   error= 1;
   

復(fù)制代碼

分析完畢

RogerZhuo

:wink:,學(xué)習(xí)了，頂一個

上海浪客

分析的真好，看源碼一頭霧水，看了你的分析，明白了好多，原來sort buffer是在需要排序的時候才分配的，并不是我想的跟隨thread一直存在的。謝謝！

action08

歲數(shù)大了，看這些頭暈