Recover the disk space after deleting rows from table

You will have to take the table offline to prevent any reads or writes that would get locked and probably have to roll back. If the table is called mydb.mytable, here is what you must do:

USE mydb
DROP TABLE IF EXISTS mytablenew;
CREATE TABLE mytablenew LIKE mytable;
ALTER TABLE mytable RENAME mytableold;
INSERT INTO mytablenew SELECT * FROM mytableold;
ANALYZE TABLE mytablenew;
ALTER TABLE mytablenew RENAME mytable;
DROP TABLE mytableold;

Any queries attempting to read from or write to mytable will fail immediately rather than hang on a lock from OPTIMIZE TABLE.

Give it a Try !!!

UPDATE 2013-08-26 15:24 EDT

Look back at the code I suggested. Please note the line

ALTER TABLE mytable RENAME mytableold;

That line takes the table offline with respect to the application.

To get a good idea how long it should take to optimize run the following:

USE mydb
CREATE TABLE mytablenew LIKE mytable;
INSERT INTO mytablenew SELECT * FROM mytable;

However long this takes, is how long it will actually take to run.

Could you use partitions?

If your data is deleted by time like a time series rolling off, it is worth considering range partitions by such time (ex: by month). Then deletion would be a simple matter of dropping a partition.

If instead a partition was based on a 'deleted' flag, you would truncate partition containing all rows with this deleted flag. But if you are deleting in batches (setting thousands of 'deleted' flags), it's not going to be more performant because the row would have to me be moved from a partition to the other, only to be truncated. Meanwhile, the space in the truncated or dropped partition might be reclaimed, but the original space in the partition prior deletion is probably not reclaimed better than with a regular delete.

So what I mean is that if your data is doomed to be deleted by some attribute you know at insert time, then this is a very good opportunity to use time range partitions.

pt-osc was mentioned in a comment as a way to handle foreign-key issues. Be careful if you intend to use pt-osc (pt-online-schema-change) because if it chooses to use the drop_swap foreign key handling mode (whether it's on "auto" or because you asked), it has a bug (in 3.2.1 at least) that won't restores the triggers. See https://jira.percona.com/browse/PT-1919