Why ORDER BY DESC Is Slower in MySQL: Inside InnoDB’s Page Structure and Scan Algorithms

InnoDB page structure

Singly linked list

InnoDB stores records on a page as a singly linked list. Each page contains two virtual records infimum (head) and supremum (tail). User records are linked between them:

infimum -> rec1 -> rec2 -> … -> recN -> supremum

REC_NEXT field

Each record header reserves two bytes ( REC_NEXT) that store the offset to the next record.

constexpr uint32_t REC_NEXT = 2;
constexpr uint32_t REC_NEXT_MASK = 0xFFFFUL;

Example of the infimum record in COMPACT row format shows REC_NEXT value 0x00, 0x0d pointing to the supremum.

Page directory

Because a singly linked list requires scanning, InnoDB adds a page‑directory at the end of each data page. It is an array of 2‑byte slots; each slot stores the offset of the last record managed by that slot (typically 4–8 records).

constexpr uint32_t PAGE_DIR_SLOT_SIZE = 2;
constexpr uint32_t PAGE_DIR_SLOT_MAX_N_OWNED = 8;
constexpr uint32_t PAGE_DIR_SLOT_MIN_N_OWNED = 4;

The first slot points to infimum, the last slot points to supremum.

N_OWNED field

Each record header contains a 4‑bit N_OWNED field that records how many records the owning slot contains. If the record is not the last one of its slot the value is 0.

constexpr uint32_t REC_NEW_N_OWNED = 5; /* single‑byte bit‑field */
constexpr uint32_t REC_N_OWNED_MASK = 0xFUL;

Example layout

A typical page with 24 user records (rec0‑rec23) and corresponding slots is illustrated below.

Orange arrows connect the 24 user records from rec0 to rec23.

Gray arrows point to the slot that manages the last record of each slot: slot 0 → infimum, slot 1 → rec3, …, last slot → supremum.

Scanning algorithms

Forward scan (ASC)

To find the next record after a given record (e.g., rec10) read the REC_NEXT offset, add it to the current address and align to the page size.

field_value = mach_read_from_2(rec - REC_NEXT);
return ut_align_offset(rec + field_value, UNIV_PAGE_SIZE);

Backward scan (DESC)

Because the list is singly linked, locating the previous record requires two steps.

Find the owning slot

1. Scan forward from the current record until a record with n_owned != 0 is found.

while (rec_get_n_owned_new(r) == 0) {
    r = rec_get_next_ptr_const(r, true);
}

2. Scan the page directory from the last slot toward slot 0 to locate the slot whose offset matches the current record.

while (*(uint16 *)slot != rec_offs_bytes) {
    slot += PAGE_DIR_SLOT_SIZE;
}
return ((ulint)(first_slot - slot)) / PAGE_DIR_SLOT_SIZE;

Scan the previous slot group

After the owning slot is identified, move to the previous slot and iterate through its records until the target record is reached.

slot = page_dir_get_nth_slot(page, slot_no - 1);
rec2 = page_dir_slot_get_rec(slot);
while (rec != rec2) {
    prev_rec = rec2;
    rec2 = page_rec_get_next_low(rec2, true);
}
return prev_rec;

Time complexity

Forward scans run in O(1) time. Backward scans run in O(n), where n is the number of slots in the page directory.

Benchmark

Forward scan (ASC)

mysql> select k from sbtest1 order by k asc limit 9999999,1;
+--------+
| k      |
+--------+
| 8670945 |
+--------+
1 row in set (1.41 sec)

Backward scan (DESC)

mysql> select k from sbtest1 order by k desc limit 9999999,1;
+--------+
| k      |
+--------+
| 1184614 |
+--------+
1 row in set (2.01 sec)
Extra: Backward index scan