Why Does LIMIT + ORDER BY Yield Different Results in MySQL? Uncovering the Priority‑Queue Threshold

Background

The MySQL manual’s

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

shows a nondeterministic result when ORDER BY is combined with LIMIT. This behavior was observed while investigating pagination.

Reproducing the Official Example

On MySQL 8.0.22 the following table is created and populated with seven rows:

CREATE TABLE `ratings` (
  `id` int NOT NULL AUTO_INCREMENT,
  `category` int DEFAULT NULL,
  `rating` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

INSERT INTO `ratings`(`id`,`category`,`rating`) VALUES
(1,1,'4.5'),
(2,3,'5.0'),
(3,2,'3.7'),
(4,2,'3.5'),
(5,1,'3.2'),
(6,2,'3.5'),
(7,3,'2.7');

Without LIMIT the rows are returned ordered by category (IDs 1,5,3,4,6,2,7). Adding LIMIT 5 changes the order to IDs 1,5,4,3,6, matching the manual’s illustration.

Finding the Critical Row Count

When many rows share the same category value (e.g., 20 rows with category=2), the LIMIT 5 query suddenly returns IDs 1,5,16,3,4 – the row with id=16 jumps to the top. By incrementally inserting rows, the change occurs exactly when the total row count exceeds 15 (i.e., at 16 rows).

Using optimizer_trace to See the Decision

Enabling the optimizer trace reveals the filesort_priority_queue_optimization field:

SET optimizer_trace='enabled=on';
SELECT * FROM ratings ORDER BY category LIMIT 5;
SELECT * FROM information_schema.OPTIMIZER_TRACE;
SET optimizer_trace='enabled=off';

For 15 rows the field shows "chosen": false (no priority queue). For 16 rows it shows "chosen": true, indicating that MySQL switched to a priority‑queue based filesort.

Source‑Code Analysis

The relevant code lives in

https://github.com/mysql/mysql-server/blob/trunk/sql/filesort.cc

. The function check_if_pq_applicable decides whether to use a priority queue. Its key condition is:

if (param->max_rows < num_rows / PQ_slowness)
    // use priority queue
else
    // fall back to normal sort ("sort_is_cheaper")

Here max_rows is the LIMIT value (5), num_rows is the total rows matching the query, and PQ_slowness is a constant equal to 3 (MySQL’s estimate that quicksort is three times faster than heap‑sort). The inequality becomes true when num_rows > 15, exactly the observed threshold.

Sort Modes and Heap‑Sort Illustration

The manual describes three sort‑buffer modes:

<sort_key,rowid>

<sort_key,additional_fields>

<sort_key,packed_additional_fields>

When the priority‑queue path is taken, MySQL builds a min‑heap of the first LIMIT rows, inserts subsequent rows, and extracts the top elements. Because heap sort is unstable, rows with identical keys can be reordered, which explains why a later row (ID 16) appears before earlier rows with the same category.

Conclusion

The change in ORDER BY … LIMIT results is deterministic: MySQL switches to a priority‑queue based filesort when max_rows < total_rows / 3. For a LIMIT 5 query this happens at 16 rows, matching the official example and providing a concrete rule for developers to anticipate when the optimizer will change its strategy.