MySQL Order By index optimization method

Although the ORDER BY does not exactly match the order of the index, the index can still be used, as long as the unused index portion and all additional ORDER BY fields are included in the WHERE clause.

MySQL Order By using index
The following queries will use indexes to solve ORDER BY or GROUP BY part:

SELECT * FROM t1 ORDER BY key_part1,key_part2,... ; 
SELECT * FROM t1 WHERE key_part1=constant ORDER BY key_part2; 
SELECT * FROM t1 WHERE key_part1=constant GROUP BY key_part2; 
SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 DESC; 
SELECT * FROM t1 WHERE key_part1=1 ORDER BY key_part1 DESC, key_part2 DESC;

MySQL Order By without using index
In other cases, MySQL cannot use index to satisfy ORDER BY, although it will use an index to find records to match the WHERE clause. These situations are as follows:
* Do ORDER BY on different index keys:
SELECT * FROM t1 ORDER BY key1, key2;
* Do ORDER BY on non-consecutive index key parts:
SELECT * FROM t1 WHERE key2=constant ORDER BY key_part2;
* using both ASC and DESC:
SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;
* The index key used to search for records is not the same as the one used for ORDER BY:
SELECT * FROM t1 WHERE key2=constant ORDER BY key1;
* There are many tables being joined together, and the fields in the ORDER BY in the records read are not all from the first non-constant table (that is, in EXPLAIN The join type of the first table in the analyzed results is not const).
* Different ORDER BY and GROUP BY expressions used.
* Records in table indexes are not stored sequentially. This is the case for HASH and HEAP tables, for example.

By executing EXPLAIN SELECT ... ORDER BY, you will know whether MySQL uses the index in the query. If the value of the Extra field is Using filesort, MySQL cannot use the index. For details, please see "7.2.1 EXPLAIN Syntax (Get Information About a SELECT)". When results had to be sorted, prior to MySQL 4.1 it used the following filesort algorithm:

1. 根据索引键读取记录，或者扫描数据表。那些无法匹配 WHERE 分句的记录都会被略过。 
2. 在缓冲中每条记录都用一个‘对'存储了2个值（索引键及记录指针）。缓冲的大小依据系统变量 sort_buffer_size 的值而定。 
3. 当缓冲慢了时，就运行 qsort（快速排序）并将结果存储在临时文件中。将存储的块指针保存起来（如果所有的‘对'值都能保存在缓冲中，就无需创建临时文件了）。 
4. 执行上面的操作，直到所有的记录都读取出来了。 
5. 做一次多重合并，将多达 MERGEBUFF（7）个区域的块保存在另一个临时文件中。重复这个操作，直到所有在第一个文件的块都放到第二个文件了。 
6. 重复以上操作，直到剩余的块数量小于 MERGEBUFF2 (15)。 
7. 在最后一次多重合并时，只有记录的指针（排序索引键的最后部分）写到结果文件中去。 
8. 通过读取结果文件中的记录指针来按序读取记录。想要优化这个操作，MySQL将记录指针读取放到一个大的块里，并且使用它来按序读取记录，将记录放到缓冲中。
缓冲的大小由系统变量 read_rnd_buffer_size 的值而定。这个步骤的代码在源文件 `sql/records.cc' 中。

A problem with this approximation algorithm is that the database reads records twice: once to estimate WHERE When splitting sentences, the second time is when sorting. Although the records were read successfully the first time (for example, a full table scan was performed), the second time was read randomly (the index keys were sorted, but the records were not). In MySQL 4.1 In and newer versions, the filesort optimization algorithm is used to record not only the index key value and record position, but also the fields required in the query. This avoids the need to read the record twice. improved filesort The algorithm is roughly as follows:
1. As before, read the records matching the WHERE clause.
2. For each record, a corresponding 'tuple' of information is recorded, including the index key value, record location, and all fields required in the query.
3. Sort ‘tuple’ information according to index key.
4. Reading records in order is just reading records from the sorted list of 'tuples' instead of reading them again from the data table.

Use improved filesort Compared with the original algorithm, 'tuples' take up longer space than 'pairs', and they rarely fit exactly in the sort buffer (the size of the buffer is determined by sort_buffer_size determined by the value). Therefore, this may require more I/O operations, making the improved algorithm slower. To avoid making it slower, this optimization is only used for sorting 'tuples' where the sum of the sizes of the extra fields exceeds the system variable The situation of max_length_for_sort_data (one symptom of setting the value of this variable too high is high disk load and low CPU load). Want to improve ORDER BY The speed depends first on whether MySQL can use indexes instead of additional sorting processes. If you can't use indexes, you can try following the following strategies:
* Increase the value of sort_buffer_size.
* Increase the value of read_rnd_buffer_size.
* Modify tmpdir so that it points to a dedicated file system with lots of free space.
If using MySQL 4.1 or newer, this option allows multiple paths in a loop format. Each path is separated by a colon (':') on Unix. Windows, NetWare and OS/2 Use a semicolon (';'). You can use this feature to evenly distribute the load among several directories. Note: These paths must be directories distributed on different physical disks, not different directories on the same physical disk.