When n is sufficiently small, the optimizer will use a priority queue for sorting. Before the optimization's porting to , the alternative was, roughly speaking, to sort the entire output and then pick only first n rows.
NOTE: The problem of choosing which index to use for query with ORDER BY ... LIMIT is a different problem, see optimizer_join_limit_pref_ratio-optimization.
There are two ways to check whether filesort has used a priority queue.
The first way is to check the status variable. It shows the number of times that sorting was done through a priority queue. (The total number of times sorting was done is a sum and ).
The second way is to check the slow query log. When one uses and specifies , entries look like this
Note the "Priority_queue: Yes" on the last comment line. (pt-query-digest is able to parse slow query logs with the Priority_queue field)
As for EXPLAIN, it will give no indication whether filesort uses priority queue or the generic quicksort and merge algorithm. Using filesort will be shown in both cases, by both MariaDB and MySQL.
page in the MySQL 5.6 manual (search for "priority queue").
MySQL WorkLog entry,
,
This page is licensed: CC BY-SA / Gnu FDL
# Time: 140714 18:30:39
# User@Host: root[root] @ localhost []
# Thread_id: 3 Schema: test QC_hit: No
# Query_time: 0.053857 Lock_time: 0.000188 Rows_sent: 11 Rows_examined: 100011
# Full_scan: Yes Full_join: No Tmp_table: No Tmp_table_on_disk: No
# Filesort: Yes Filesort_on_disk: No Merge_passes: 0 Priority_queue: Yes
SET TIMESTAMP=1405348239;SET TIMESTAMP=1405348239;
SELECT * FROM t1 WHERE col1 BETWEEN 10 AND 20 ORDER BY col2 LIMIT 100;