Mysql 排序原理

参考 http://s.petrunia.net/blog/?p=24

外联排序策略

3张表外联，然后根据第一张的表的某个索引字段排序。 在这种情况下是根据索引进行排序然后进行外联。

3张表外联，然后根据第一张表的某些字段进行排序。此时会使用filesort对第一张表进行排序，然后再进行外联。

3张表外联，根据后两张表中的字段进行排序。此情况下，先生成关联后的临时表，然后对临时表进行filesort。

filesort

filesort有两种排序算法，single-pass和two-pass。

• single-pass，单次传输排序，读取查询所需要的所有列，然后进行排序，最后直接返回结果。
• two-pass，两次传输排序，首先只读取需要排序的字段和行指针(sort_key, rowid)，对其进行排序，然后根据排序结果读取所需要的行。缺点：第二次查询会导致大量的随机IO。 若order by的列的总大小超过max_length_for_sort_data字节，或者order by列是BLOB或TEXT，则采用此算法。其他时候都用single-pass。

filesort总体上来说，如果数据量小就直接在内存进行quicksort。如果数据量大，mysql会先将数据进行分块，每个独立的块进行quicksort，结果放在磁盘上，最后用mergesort 进行合并。

The amount of memory available to filesort() is controlled by @@sort_buffer_size variable