Menghapus jutaan baris di MySQL

DELETE FROM `table`
WHERE (whatever criteria)
ORDER BY `id`
LIMIT 1000

Cuci, bilas, ulangi sampai nol baris terpengaruh. Mungkin dalam skrip yang tidur selama satu atau tiga detik di antara iterasi.