How big are these tables?? I've never had an optimize take more than 10 minutes, even on 5 million rows of 20+ columns each with several multi-column indices. Also, are they InnoDB or MyISAM? That's going to make a difference (especially in the time for DELETEs if you have a lot of FK's ...)