MySQL Internals Manual Chapter 10 : 10.2 How MySQL Does Sorting (filesort)

悠悠 2023-01-08 04:28 152阅读 0赞

https://dev.mysql.com/doc/refman/8.0/en/order-by-optimization.html

8.2.1.16 ORDER BY Optimization

This section describes when MySQL can use an index to satisfy an ORDER BY clause, the filesort operation used when an index cannot be used, and execution plan information available from the optimizer about ORDER BY.

本节描述了当MySQL可以使用一个索引来满足ORDER BY子句时，当一个索引不能被使用时使用的filesort操作，以及关于ORDER BY的优化器提供的执行计划信息。

An ORDER BY with and without LIMIT may return rows in different orders, as discussed in Section 8.2.1.19, “LIMIT Query Optimization”.

ORDER BY with和without LIMIT可能返回不同顺序的行，如8.2.1.19节“限制查询优化”所述。

Use of Indexes to Satisfy ORDER BY
    
    Use of filesort to Satisfy ORDER BY
    
    Influencing ORDER BY Optimization
    
    ORDER BY Execution Plan Information Available

Use of Indexes to Satisfy ORDER BY

In some cases, MySQL may use an index to satisfy an ORDER BY clause and avoid the extra sorting involved in performing a filesort operation.

在某些情况下，MySQL可能会使用一个索引来满足ORDER BY子句，从而避免执行filesort操作所涉及的额外排序。

The index may also be used even if the ORDER BY does not match the index exactly, as long as all unused portions of the index and all extra ORDER BY columns are constants in the WHERE clause. If the index does not contain all columns accessed by the query, the index is used only if index access is cheaper than other access methods.  
即使ORDER BY与索引不完全匹配，也可以使用索引，只要索引的所有未使用的部分和所有额外的ORDER BY列都是WHERE子句中的常量。如果索引不包含查询访问的所有列，则只有在索引访问比其他访问方法更便宜时才使用索引。

Assuming that there is an index on (key\_part1, key\_part2), the following queries may use the index to resolve the ORDER BY part. Whether the optimizer actually does so depends on whether reading the index is more efficient than a table scan if columns not in the index must also be read.

假设在(key\_part1, key\_part2)上有一个索引，下面的查询可以使用索引来解析按部分排序。优化器是否真的这样做，取决于如果还必须读取索引中的列，那么读取索引是否比表扫描更有效。

In this query, the index on (key_part1, key_part2) enables the optimizer to avoid sorting:
    
    SELECT * FROM t1
      ORDER BY key_part1, key_part2;

However, the query uses SELECT \*, which may select more columns than key\_part1 and key\_part2. In that case, scanning an entire index and looking up table rows to find columns not in the index may be more expensive than scanning the table and sorting the results. If so, the optimizer probably does not use the index. If SELECT \* selects only the index columns, the index is used and sorting avoided.

但是，查询使用SELECT \*，它可以选择比key\_part1和key\_part2更多的列。在这种情况下，扫描整个索引并查找表行以查找不在索引中的列可能比扫描表并对结果排序花费更多。如果是这样，优化器可能不会使用索引。如果SELECT \*只选择索引列，则使用索引，避免排序。

If t1 is an InnoDB table, the table primary key is implicitly part of the index, and the index can be used to resolve the ORDER BY for this query:

SELECT pk, key\_part1, key\_part2 FROM t1  
ORDER BY key\_part1, key\_part2;

In this query, key\_part1 is constant, so all rows accessed through the index are in key\_part2 order, and an index on (key\_part1, key\_part2) avoids sorting if the WHERE clause is selective enough to make an index range scan cheaper than a table scan:

SELECT \* FROM t1  
WHERE key\_part1 = constant  
ORDER BY key\_part2;

In the next two queries, whether the index is used is similar to the same queries without DESC shown previously:

SELECT \* FROM t1  
ORDER BY key\_part1 DESC, key\_part2 DESC;

SELECT \* FROM t1  
WHERE key\_part1 = constant  
ORDER BY key\_part2 DESC;

Two columns in an ORDER BY can sort in the same direction (both ASC, or both DESC) or in opposite directions (one ASC, one DESC). A condition for index use is that the index must have the same homogeneity, but need not have the same actual direction.

If a query mixes ASC and DESC, the optimizer can use an index on the columns if the index also uses corresponding mixed ascending and descending columns:

SELECT \* FROM t1  
ORDER BY key\_part1 DESC, key\_part2 ASC;

The optimizer can use an index on (key\_part1, key\_part2) if key\_part1 is descending and key\_part2 is ascending. It can also use an index on those columns (with a backward scan) if key\_part1 is ascending and key\_part2 is descending. See Section 8.3.13, “Descending Indexes”.

In the next two queries, key\_part1 is compared to a constant. The index is used if the WHERE clause is selective enough to make an index range scan cheaper than a table scan:

SELECT \* FROM t1  
WHERE key\_part1 > constant  
ORDER BY key\_part1 ASC;

SELECT \* FROM t1  
WHERE key\_part1 < constant  
ORDER BY key\_part1 DESC;

In the next query, the ORDER BY does not name key\_part1, but all rows selected have a constant key\_part1 value, so the index can still be used:

SELECT \* FROM t1  
WHERE key\_part1 = constant1 AND key\_part2 > constant2  
ORDER BY key\_part2;

In some cases, MySQL cannot use indexes to resolve the ORDER BY, although it may still use indexes to find the rows that match the WHERE clause. Examples:

The query uses ORDER BY on different indexes:
    
    SELECT * FROM t1 ORDER BY key1, key2;

The query uses ORDER BY on nonconsecutive parts of an index:

SELECT \* FROM t1 WHERE key2=constant ORDER BY key1\_part1, key1\_part3;

The index used to fetch the rows differs from the one used in the ORDER BY:

SELECT \* FROM t1 WHERE key2=constant ORDER BY key1;

The query uses ORDER BY with an expression that includes terms other than the index column name:

SELECT \* FROM t1 ORDER BY ABS(key);  
SELECT \* FROM t1 ORDER BY -key;

The query joins many tables, and the columns in the ORDER BY are not all from the first nonconstant table that is used to retrieve rows. (This is the first table in the EXPLAIN output that does not have a const join type.)
    
    The query has different ORDER BY and GROUP BY expressions.
    
    There is an index on only a prefix of a column named in the ORDER BY clause. In this case, the index cannot be used to fully resolve the sort order. For example, if only the first 10 bytes of a CHAR(20) column are indexed, the index cannot distinguish values past the 10th byte and a filesort is needed.
    
    The index does not store rows in order. For example, this is true for a HASH index in a MEMORY table.

Availability of an index for sorting may be affected by the use of column aliases. Suppose that the column t1.a is indexed. In this statement, the name of the column in the select list is a. It refers to t1.a, as does the reference to a in the ORDER BY, so the index on t1.a can be used:

SELECT a FROM t1 ORDER BY a;

In this statement, the name of the column in the select list is also a, but it is the alias name. It refers to ABS(a), as does the reference to a in the ORDER BY, so the index on t1.a cannot be used:

SELECT ABS(a) AS a FROM t1 ORDER BY a;

In the following statement, the ORDER BY refers to a name that is not the name of a column in the select list. But there is a column in t1 named a, so the ORDER BY refers to t1.a and the index on t1.a can be used. (The resulting sort order may be completely different from the order for ABS(a), of course.)

SELECT ABS(a) AS b FROM t1 ORDER BY a;

Previously (MySQL 5.7 and lower), GROUP BY sorted implicitly under certain conditions. In MySQL 8.0, that no longer occurs, so specifying ORDER BY NULL at the end to suppress implicit sorting (as was done previously) is no longer necessary. However, query results may differ from previous MySQL versions. To produce a given sort order, provide an ORDER BY clause.  
Use of filesort to Satisfy ORDER BY

If an index cannot be used to satisfy an ORDER BY clause, MySQL performs a filesort operation that reads table rows and sorts them. A filesort constitutes an extra sorting phase in query execution.

To obtain memory for filesort operations, as of MySQL 8.0.12, the optimizer allocates memory buffers incrementally as needed, up to the size indicated by the sort\_buffer\_size system variable, rather than allocating a fixed amount of sort\_buffer\_size bytes up front, as was done prior to MySQL 8.0.12. This enables users to set sort\_buffer\_size to larger values to speed up larger sorts, without concern for excessive memory use for small sorts. (This benefit may not occur for multiple concurrent sorts on Windows, which has a weak multithreaded malloc.)

A filesort operation uses temporary disk files as necessary if the result set is too large to fit in memory. Some types of queries are particularly suited to completely in-memory filesort operations. For example, the optimizer can use filesort to efficiently handle in memory, without temporary files, the ORDER BY operation for queries (and subqueries) of the following form:

SELECT … FROM single\_table … ORDER BY non\_index\_column \[DESC\] LIMIT \[M,\]N;

Such queries are common in web applications that display only a few rows from a larger result set. Examples:

SELECT col1, … FROM t1 … ORDER BY name LIMIT 10;  
SELECT col1, … FROM t1 … ORDER BY RAND() LIMIT 15;

Influencing ORDER BY Optimization

For slow ORDER BY queries for which filesort is not used, try lowering the max\_length\_for\_sort\_data system variable to a value that is appropriate to trigger a filesort. (A symptom of setting the value of this variable too high is a combination of high disk activity and low CPU activity.) This technique applies only before MySQL 8.0.20. As of 8.0.20, max\_length\_for\_sort\_data is deprecated due to optimizer changes that make it obsolete and of no effect.

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, try the following strategies:

Increase the sort_buffer_size variable value. Ideally, the value should be large enough for the entire result set to fit in the sort buffer (to avoid writes to disk and merge passes).
    
    Take into account that the size of column values stored in the sort buffer is affected by the max_sort_length system variable value. For example, if tuples store values of long string columns and you increase the value of max_sort_length, the size of sort buffer tuples increases as well and may require you to increase sort_buffer_size.
    
    To monitor the number of merge passes (to merge temporary files), check the Sort_merge_passes status variable.
    
    Increase the read_rnd_buffer_size variable value so that more rows are read at a time.
    
    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. Separate the paths by colon characters (:) on Unix and semicolon characters (;) on Windows. The paths should name directories in file systems located on different physical disks, not different partitions on the same disk.

ORDER BY Execution Plan Information Available

With EXPLAIN (see Section 8.8.1, “Optimizing Queries with EXPLAIN”), you can check whether MySQL can use indexes to resolve an ORDER BY clause:

If the Extra column of EXPLAIN output does not contain Using filesort, the index is used and a filesort is not performed.
    
    If the Extra column of EXPLAIN output contains Using filesort, the index is not used and a filesort is performed.

In addition, if a filesort is performed, optimizer trace output includes a filesort\_summary block. For example:

“filesort\_summary”: \{  
“rows”: 100,  
“examined\_rows”: 100,  
“number\_of\_tmp\_files”: 0,  
“peak\_memory\_used”: 25192,  
“sort\_mode”: “<sort\_key, packed\_additional\_fields>”  
\}

peak\_memory\_used indicates the maximum memory used at any one time during the sort. This is a value up to but not necessarily as large as the value of the sort\_buffer\_size system variable. Prior to MySQL 8.0.12, the output shows sort\_buffer\_size instead, indicating the value of sort\_buffer\_size. (Prior to MySQL 8.0.12, the optimizer always allocates sort\_buffer\_size bytes for the sort buffer. As of 8.0.12, the optimizer allocates sort-buffer memory incrementally, beginning with a small amount and adding more as necessary, up to sort\_buffer\_size bytes.)

The sort\_mode value provides information about the contents of tuples in the sort buffer:

<sort_key, rowid>: This indicates that sort buffer tuples are pairs that contain the sort key value and row ID of the original table row. Tuples are sorted by sort key value and the row ID is used to read the row from the table.
    
    <sort_key, additional_fields>: This indicates that sort buffer tuples contain the sort key value and columns referenced by the query. Tuples are sorted by sort key value and column values are read directly from the tuple.
    
    <sort_key, packed_additional_fields>: Like the previous variant, but the additional columns are packed tightly together instead of using a fixed-length encoding.

EXPLAIN does not distinguish whether the optimizer does or does not perform a filesort in memory. Use of an in-memory filesort can be seen in optimizer trace output. Look for filesort\_priority\_queue\_optimization. For information about the optimizer trace, see MySQL Internals: Tracing the Optimizer.