Understanding MySQL ORDER BY and LIMIT: Execution Principles, Sorting Algorithms, and Pagination Optimization

MySQL pagination queries rely on the interaction between the Server layer and the storage engine layer. The Server layer handles SQL parsing, optimization, and execution planning, while the InnoDB storage engine retrieves data based on B+ tree index structures. Primary indexes store complete row data, whereas secondary indexes only store primary key values, necessitating table lookups when queried fields are not fully covered.

The ORDER BY clause operates through two main mechanisms: index scan sorting and filesort. When the sorting field matches a secondary index and the query range is small, MySQL leverages the index's inherent order to avoid additional sorting. However, if the query range is large, the sorting field lacks an index, or the index cannot satisfy the ORDER BY condition, MySQL triggers filesort. Filesort utilizes a dedicated memory buffer (sort_buffer) and switches to disk-based temporary files if the data exceeds the buffer size.

Filesort employs two primary algorithms: full-field sorting and rowid sorting. Full-field sorting places all required fields into the sort buffer, minimizing disk I/O but consuming more memory. Rowid sorting stores only the sorting field and primary key ID in the buffer, reducing memory usage but requiring additional table lookups after sorting. MySQL dynamically selects the algorithm based on row size and available memory, prioritizing full-field sorting for InnoDB tables to avoid extra disk reads.

The underlying sorting algorithm adapts to data volume and query constraints. Quick sort is used when all data fits in memory, merge sort handles disk-based sorting by merging sorted chunks, and heap sort optimizes queries containing LIMIT clauses by maintaining a fixed-size priority queue.

The LIMIT clause works by fetching the first m+n rows, discarding the initial m rows, and returning the subsequent n rows. Large offset values significantly degrade performance because MySQL must still scan and sort all preceding records. Additionally, sorting by non-unique fields can cause unstable ordering across pagination pages due to heap sort's non-deterministic nature. To optimize deep pagination, developers should utilize covering index subqueries to minimize table lookups:

SELECT * FROM goods g INNER JOIN (SELECT id FROM goods ORDER BY price LIMIT 80000, 10) AS d ON g.id = d.id;

This approach first retrieves only the primary keys via a secondary index, applies pagination filtering, and then joins back to the main table, avoiding full table scans and expensive filesort operations while dramatically improving query efficiency for large datasets.