Egy táblából vagy törölheted a régi rekordokat (lassú), vagy elláthatod egy (minden indexkulcsba felvett!) saját törlésjelző flaggel (ez se gyors nagy tételnél), vagy partícionált táblát használsz egy okosan kitalált partícionáló kulccsal, amellyel egyetlen alter table paranccsal lecsatolhatod a feleslegessé vált rekordhalmazt.
Ha jól látom (most kerestem rá, mert csak távolról ugatom a motort), a mysql támogatja az utóbbi megközelítést.