Today somebody had a problem with expiring a large table (a Serendipity Blog table).
In MySQL InnoDB, tables are physically ordered by primary key (InnoDB data is a B+ tree, a balanced tree where the data pages are the leaves of the tree). If you are expiring old data from such a log table, you are deleting from the left hand side of the tree, and since it is a balanced tree, that triggers a lot of rebalancing – hence it is very slow.
If you rename the old table and INSERT … SELECT the data you want to keep back into the original table, that can be faster. But if the data you want to keep is larger than memory, the indexing of the data will still be slow.
A nice way to handle log tables are partitions. Here is an example. It’s not very cleaned up, but it works on my system.