#SUGGESTION #1
Perhaps you can retrieve the min and max date as separate queries
SELECT updated_date INTO @oldest_updated_date
FROM `order` ORDER BY updated_date LIMIT 1;
SELECT updated_date INTO @newest_updated_date
FROM `order` ORDER BY updated_date DESC LIMIT 1;
This will traverse the index one one key per query
#SUGGESTION #2
You should shrink the table after mass deletes.
OPTIMIZE TABLE `order`;
#SUGGESTION #3
After performing the mass delete, the index statistics need to be recalculated. OPTIMIZE TABLE does it for youm but you can do a as a separate step, like this:
ANALYZE TABLE `order`;
#SUGGESTION #4
Perhaps recreate the table from a start date. For example, to keep the last 30 days, do this:
SET @TimeGapToKeep = NOW() - INTERVAL 30 DAY;
ALTER TABLE `order` RENAME `old_order`;
CREATE TABLE `new_order` LIKE `old_order`;
INSERT INTO `new_order` SELECT * FROM `old_order`
WHERE updated_date >= @TimeGapToKeep;
ALTER TABLE `new_order` RENAME `order`;
ANALYZE TABLE `order`;