I recently ran into a situation where a Delete across a large time period was taking an extensive amount of time to run when replicated to the Slave, although the query ran very quickly when running on the Master. On the Master, the query took
After much head scratching and verifying that indexes existed on both Master and Slave, we took a few minutes to compare the query execution plan using EXPLAIN. It was quickly obvious that the Slave was using a different index than the Master when executing the query. We quickly update the table statistics using Analyze Table, and re-ran EXPLAIN. After the Analyze Table, the problem was solved, and after restarting replication using Start Slave, the offending query quickly executed in 2 minutes.
Moral of the Story: Running Analyze Table on larger tables every couple days is probably a good idea.