Query 'optimizing' state is taking too long
SELECT min(updated_date) as oldest, max(updated_date) AS newest FROM `order`;


is well optimized if you have INDEX(updated_date) (which you do).  It will do two probes.  No need for two queries, etc.

The EXPLAIN said 'optimized away' because it could see that it did not need to do any work.

I checked with a similar table, then checked the Handler% STATUS values -- Handler_read_first and Handler_read_last incremented by 1 each.  This is indicative of optimizing MIN and MAX.

Do not use OPTIMIZE TABLE it is (usually) a long wast of time.

It is a huge table.

DELETEing a million rows will queue up a lot of stuff, especially because of 10 secondary indexes.  I'll bet that when you asked for MAX and MIN, it had to finish up all the pending index updates.

If that is the case, none of the suggestions will really solve the problem.  Chunking the deletes (which is a good idea anyway) might have "hidden" the problem by slowing down the delete task.  As @eroomydna says, the undo logs must have been huge.

On what basis are you DELETEing?  If it is "purge all records older than X", then this is a cure:  PARTITION BY RANGE(...) on the date (to use for purging) and DROP PARTITION to jetison old rows.  This is also much cleaner (in the sense of OPTIMIZEing to defragment) than DELETEing.

Rolando, ANALYZE TABLE will recalc the stats "instantly".  OPTIMIZE TABLE rebuilds (and ANALYZEs) the table but takes forever on this sized table.

Potentially valid is to copy over the useful rows, a la Rolando's #4.  But only if you are jettisoning "most" of the table.  I suggest that is not the case here -- "deleting a few million rows" out of 618M.

10 secondary keys is a lot.  Would you care to show them; we may have suggestions on pruning the list.  For this sized table, it is costly to maintain that many.

Edit -- "Change buffering"

I believe what I have described is called change buffering for DELETEs.  More discussion:
http://dev.mysql.com/doc/innodb-plugin/1.0/en/innodb-performance-change_buffering.html
http://dev.mysql.com/doc/refman/5.6/en/innodb-performance-change_buffering.html

You could try innodb_change_buffering = none.