笔记:mysql-order by 算法及优化

  • G8bao7

    2014-03-01 12:55:56
  • MySQL
  • 原创

http://dev.mysql.com/doc/refman/5.5/en/order-by-optimization.html

两种算法都是使用快排进行排序

max_length_for_sort_data 
    当排序数据集还是单行列?大小小于此值时，使用改进算法(modified method);否则使用原算法
The original method uses only the ORDER BY columns.
    sort buffer 保存结构(排序列+主键ID)。优点:占用sort buffer空间小。缺点:排序后，需要再访问一次表读取select列数据。额外产生一次访问原表的操作
The modified method uses not just the ORDER BY columns, but all the columns referenced by the query.
    sort buffer 保存结构(排序列+select包含的所有列),。优点:排序后，直接返回数据。缺点:占用sort buffer空间大，会导致产生tempfile进行排序

 sort_buffer_size 
    决定是否在磁盘文件中进行排序

read_rnd_buffer_size 
    原算法排序时，每次读取row的大小

尽量给(var)char分配合适的大小
    防止超过tmp_table_size/max_heap_table_size大小

  • Change the tmpdir system variable to point to a dedicated file system with large amounts of free space. The variable value can list several paths that are used in round-robin fashion; you can use this feature to spread the load across several directories. Paths should be separated by colon characters (“:”) on Unix and semicolon
     characters (“;”) on Windows. The paths should name directories in file systems located on different physicaldisks, not different partitions on the same disk.



算法详细介绍

MySQL has two filesort algorithms for sorting and retrieving results. The original method uses only the ORDER BY columns. The modified method uses not just the ORDER BY columns, but all the columns referenced by the query.

The optimizer selects which filesort algorithm to use. It normally uses the modified algorithm except whenBLOB or TEXT columns are involved, in which case it uses the original algorithm. For both algorithms, the sort buffer size is the sort_buffer_size system variable value.

The original filesort algorithm works as follows:

  1. Read all rows according to key or by table scanning. Skip rows that do not match the WHERE clause.

  2. For each row, store a pair of values (the sort key value and the row ID) in the sort buffer.

  3. If all pairs fit into the sort buffer, no temporary file is created. Otherwise, when the sort buffer becomes full, run a qsort (quicksort) on it in memory and write it to a temporary file. Save a pointer to the sorted block.

  4. Repeat the preceding steps until all rows have been read.

  5. Do a multi-merge of up to MERGEBUFF (7) regions to one block in another temporary file. Repeat until all blocks from the first file are in the second file.

  6. Repeat the following until there are fewer than MERGEBUFF2 (15) blocks left.

  7. On the last multi-merge, only the row ID (the last part of the value pair) is written to a result file.

  8. Read the rows in sorted order using the row IDs in the result file. To optimize this, read in a large block of row IDs, sort them, and use them to read the rows in sorted order into a row buffer. The row buffer size is theread_rnd_buffer_size system variable value. The code for this step is in the sql/records.cc source file.

One problem with this approach is that it reads rows twice: One time during WHERE clause evaluation, and again after sorting the value pairs. And even if the rows were accessed successively the first time (for example, if a table scan is done), the second time they are accessed randomly. (The sort keys are ordered, but the row positions are not.)

The modified filesort algorithm incorporates an optimization to avoid reading the rows twice: It records the sort key value, but instead of the row ID, it records the columns referenced by the query. The modified filesortalgorithm works like this:

  1. Read the rows that match the WHERE clause.

  2. For each row, record a tuple of values consisting of the sort key value and the columns referenced by the query.

  3. When the sort buffer becomes full, sort the tuples by sort key value in memory and write it to a temporary file.

  4. After merge-sorting the temporary file, retrieve the rows in sorted order, but read the required columns directly from the sorted tuples rather than by accessing the table a second time.

Using the modified filesort algorithm, the tuples are longer than the pairs used in the original method, and fewer of them fit in the sort buffer. As a result, it is possible for the extra I/O to make the modified approach slower, not faster. To avoid a slowdown, the optimizer uses the modified algorithm only if the total size of the extra columns in the sort tuple does not exceed the value of the max_length_for_sort_data system variable. (A symptom of setting the value of this variable too high is a combination of high disk activity and low CPU activity.)


For slow queries for which filesort is not used, try lowering max_length_for_sort_data to a value that is appropriate to trigger a filesort.

To increase ORDER BY speed, check whether you can get MySQL to use indexes rather than an extra sorting phase. If this is not possible, you can try the following strategies:

  • Increase the sort_buffer_size variable value.

  • Increase the read_rnd_buffer_size variable value.

  • Use less RAM per row by declaring columns only as large as they need to be to hold the values stored in them. For example, CHAR(16) is better than CHAR(200) if values never exceed 16 characters.

  • Change the tmpdir system variable to point to a dedicated file system with large amounts of free space. The variable value can list several paths that are used in round-robin fashion; you can use this feature to spread the load across several directories. Paths should be separated by colon characters (“:”) on Unix and semicolon characters (“;”) on Windows. The paths should name directories in file systems located on different physicaldisks, not different partitions on the same disk.

请使用浏览器的分享功能分享到微信等