When we tried to clean up a rather large (4.500.000 rows, 20GB) InnoDB table some days ago, we were astonished by the time MySQL took to complete the task. We had already
LIMITed the transaction size, but every single chunk still took minutes to execute. The table itself contains some number columns, including a numeric primary key, and a blob. The delete condition was mainly based on the primary key (being smaller than a predefined value) and status field. After some mails between the support crew and us an optimizer bug was identified: MySQL Bug #28554.
The problem is that in some cases the optimizer makes a bad choice concerning which index to use. It will pick a secondary index that can be used to cover a
WHERE indexed_column=<constant> condition, even though it will cause way more data to be scanned than necessary. The primary key for the second condition
pk_column<=<constant> would be a far better choice, visiting only a much smaller number of rows.
The bug has been verified in 4.1.12, 4.1.22 and 5.0.42-BK. Read the bug report for details and some example data.