Fun MySQL fact of the day: descending means ascending

If you'd believe it, I told you only a partial truth again yesterday and Tuesday. While it's true that records are sorted in key-order in an InnoDB index, there's some yet more interesting finesse to it. In fact, would you believe me if I told you that records are actually written to disk in an unordered fashion? Well, they are. Or, well, kind of.

Ignoring yet more complexity we'll get to tomorrow, records are stored on an InnoDB page. By default, a page is a 16KB block and is allocated all up-front. All pages in an index form a doubly-linked list in key order, allowing for ascending or descending traversal. Within a page, however, records are stored in order of insert in a heap, not in key order at all! So, if records are stored unordered, how are they sorted in ascending key order? Simply: each record has a pointer to the "next" record forming a singly-linked list in ascending key order.

Now, does this really matter? Well, yea: until MySQL 8.0.0, all InnoDB indices records are sorted in ascending order, even if they were declared as CREATE INDEX ... DESC ("parsed but ignored" bug #13375). And what does that mean? Well, it means queries that ORDER BY ... DESC are going to run a heck of a lot slower than their ASC counterparts will. Isn't that fun?