[源代码分析]关于排序操作的代码分析

justlooks

前几天读了下MySQL关于排序操作的代码，颇有心得，这里和大家分享下，并做记录便于以后查阅

对于排序MySQL会采用两种方法，一种是参与排序的是order by之后的列以及指向行数据的指针，而另一种方法是通过采用将select到的field和排序信息相结合，那么排序时相当与将field同时处理了，好处就是不需要再次通过指针读记录进行处理，坏处就是需要额外读取对应的select field域到辅助结构，这两者有个平衡点，下面来具体看代码

先来看结构

这个结构用来保存对应的select fields信息

1. 
   
2. 40 typedef struct st_sort_addon_field {  
   
3. 41   Field *field;          存放select的结果域
   
4. 42   uint   offset;         存放该域开始的位置（注意NULL列位图是放在最前面的）
   
5. 43   uint   null_offset;    如果该列可能为null,那么则记录到的是在null位图的具体位置
   
6. 44   uint   length;         计算对应field参与排序的长度
   
7. 45   uint8  null_bit;       如果该列可能为null,那么则记录到的是在null位图的具体位置
   
8. 46 } SORT_ADDON_FIELD;
   

复制代码

另外对于有序记录的merge,MySQL采用的是2级merge，即先将小块有序记录合并成大块，将大块有序记录合并成整块，那么在期间会用到一个结构来保存有序块在临时文件或者内存中的信息，下面就是这个结构的内容

1. 
   
2. 48 typedef struct st_buffpek {   
   
3. 49   my_off_t file_pos;           有序块在排序临时文件中的开始位置
   
4. 50   uchar *base,*key;         指向放有序数据的缓冲区
   
5. 51   ha_rows count;            表中记录数
   
6. 52   ulong mem_count;         在内存中的记录数
   
7. 53   ulong max_keys;          在buffer中的最大key数
   
8. 54 } BUFFPEK;
   

复制代码

一级merge最多使用7个有序块，二级merge最多用到15个有序块

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

复制代码

另外一个关键结构就是记录排序信息的结构，以及用于整个处理流程的param结构(太长，这里不具体列出)

1. 
   
2. 844 typedef struct st_sort_field {
   
3. 2845   Field *field;                         需要排序的表列
   
4. 2846   Item  *item;                         排序的非表列（表达式等）
   
5. 2847   uint   length;                        排序表列或者表达式返回值长度
   
6. 2848   uint   suffix_length;                 排序的前缀长度
   
7. 2849   Item_result result_type;              结果类型
   
8. 2850   bool reverse;                        是否是降序标识
   
9. 2851   bool need_strxnfrm;                   用于字符格式化
   
10. 2852 } SORT_FIELD;
    

复制代码

具体的调用处理在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)
   

复制代码

当执行的时候，执行计划被调整为FILESORT

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

复制代码

而当排序不是在内存中时，执行计划被调整为QPLAN_FILESORT_DISK

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

复制代码

那么以上两者对应的就是percona slow log 中的　Filesort　注解，以及  Filesort_on_disk　注解

那么关于内存分配，分配的内存是来自variable sort_buff_size的定义值，代码中规定了最小的内存下限为32K,或者做level 2 merge所需内存的最大者

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

复制代码

当然这里的32K是要打折扣的，除去管理数据的损耗

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

复制代码

那么当sort_buff_size规定值太小，自然就会有问题

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   }
   

复制代码

MySQL根据sort_buff_size的值来确定能够取到的排序记录条数，并比较之前估计的记录数，取小者，这里的char是用来放指向记录的指针

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

复制代码

并根据这个记录数来分配内存

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;
   

复制代码

当内存比较紧张的时候，MySQL试图减小取到的sort_buff_size值，重新计算记录数，来减小内存的消耗

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;
   

复制代码

在顺利分配内存后，MySQL调用find_all_keys将记录放到缓冲区，并返回记录总数

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;
   

复制代码

在find_all_keys调用中，MySQL将找到的记录每隔param->keys条记录进行排序，并把排序结果写到tempfile,将排序块位置信息写到每个buffpek结构中并将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缓冲
    

复制代码

那么根据这些个有序块个数，能够判断是否是内存中排序和利用临时文件进行排序

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

复制代码

如果是内存中排序，save_index调用Radixsort或者quicksort算法来进行排序（这个是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   }
   

复制代码

那么有人说了为什么find_all_keys调用中已经排过序了，为什么save_index调用还要再排一次？其实是这样的，当记录能够全部容纳在内存中时那么write_keys调用不会被执行，那么其实返回的内存中记录是未经排序的，所以这里需要调用save_index来处理排序
如果不幸使用磁盘上的临时文件排序的话，MySQL会从buffpek_pointers中将所有有序块的信息读到 table_sort.buffpek　这个缓冲区

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;
   

复制代码

那么接下来会调用merge_many_buff来进行level 1的merge动作，merge的结果会被写入tempfile,注意到这里有序块数目是传指针进去的，也就是说在level 1的merge过后maxbuffer的数目是不大于level 2的merge规定块数(15)

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

复制代码

接下来调用merge_index来进行level 2的merge,最终结果写入outfile,(如果跳入这个调用会发现和上一个merge_many_buff的调用，都是调用同一个函数(merge_buffers)

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

复制代码

其中filesort_merge_passes(sort_merge_passes)参数显示了merge_buffers调用的次数

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

复制代码

另外就是本文开头提到过的两种排序方法选择的依据，如果总的排序列长度超过max_length_for_sort_data则使用记录指针和排序列信息进行排序，否则创建addonf结构，那么排序是依据排序信息和addonf信息，并不读取记录(因为需要获取的结果集已经在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;
   

复制代码

值得注意的是这里有一个例外，在生成addonf结构的调用代码里有一个判定，当最终结果集中包含blob类型的列时，不会使用addonf结构来做排序。另外，就是结果集包含可以是null列情况下，addonf排序结构是要记录NULL位图信息的，也就是说NULL列对排序性能会有副作用，尽管这个影响并不是很大

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

复制代码

而对于有序记录块的merge,MySQL是采用priority Queues的算法,而read_to_buffer调用是将有序块内容加载到buffpek->key指向的缓冲区位置，最终内容插入到priority Queues进行排序处理

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   }
    

复制代码

另外最后需要提到的是关于sort abort错误，这个错误是在filesort调用末尾的错误处理阶段被抛出

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,　　　　　#否则增加状态参数sort_rows值
   
9. 330           (ulong) records, &LOCK_status);
   

复制代码

因为之前调用开始时参数error被初始化为1,所以导致整个处理过程中途跳出都会触发这个错误，具体的错误原因可以查阅goto err处代码信息

1. 
   
2. 145   error= 1;
   

复制代码

分析完毕

RogerZhuo

:wink:,学习了，顶一个

上海浪客

分析的真好，看源码一头雾水，看了你的分析，明白了好多，原来sort buffer是在需要排序的时候才分配的，并不是我想的跟随thread一直存在的。谢谢！

action08

岁数大了，看这些头晕