Why does MySQL fail to use an index effectively when LIMIT offset is large?

I do not understand when querying 5 rows from a table of 500,000 rows, the following query takes 0.00sec:

SELECT id, username FROM Users FORCE INDEX (PRIMARY) ORDER BY id LIMIT 20,5;

But querying the exact same rows in the reverse takes 2.50sec:

SELECT id, username FROM Users FORCE INDEX (PRIMARY) ORDER BY id DESC LIMIT 499975,5;

Furthermore, if I don't force index for the second query, MySQL will choose not to use it.

I note that there is a plan to introduce sort order for index, but that does not explain why MySQL cannot use the same index effectively when LIMIT offset is large since it knows the total row count.

Yes, the large offset is a problem. MySQL does early row lookups, which do not allow throwing data away as easy as one imagines. MySQL retrieves the whole records as it processes the database and each record may be of variable length. Throwing rows away afterwards becomes as cumbersome as throwing each single row away. It's not like "throw away x*y bytes".

There are tricks to force MySQL into late row lookup, which means process the index and do all operations concerning that, than retrieve the row. This offers the possibility to throw rows away much faster.

See

• this stackoverflow thread for an easy answer

• or this page for in-depth info.

StackExchange Database Administrators Q#59347, answer score: 3