MySQL@Facebook recently posted an article on speeding up queries with LIMIT clauses ("LIMIT a, b is O(N*N)":
http://www.facebook.com/note.php?note_id=206034210932).
The user indicates that creating a compound index (containing both the indexed field and the pk field) and then using a specially-formed query will speed up certain queries:
"Indexing all columns from the PRIMARY index is not as horrible as you might think when using InnoDB because all secondary index entries contain the PRIMARY key columns as the row pointer."
I thought that all InnoDB secondary indexes contained the PK (per
http://dev.mysql.com/doc/refman/5.1/en/innodb-index-types.html), and so I am not really sure what this user is trying to say.
Also, I do not really understand the select query at the end of the article (what are "$last_j" and "$last_i", are they the same as "$offset"?).
I'd reply to the post, but it is a few months old and I am not sure I'd get an answer.
Thanks!