Miljoenen rijen verwijderen in MySQL

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

Wassen, spoelen, herhalen totdat er geen rijen zijn aangetast. Misschien in een script dat een seconde of drie slaapt tussen iteraties.