With 'none' the delete operations become too slow. It takes over 25s to delete a 1k chunk. I couldn't even delete enough rows to check if the min() delay becomes noticeable. I'm now experimenting with 'purges', which buffers only the physical deletion and doesn't compromise delete performance, and I'll check If the min() isn't slower after removing a few million rows.

I'm creating a new RDS instance to repeat the tests with a fresh snapshot. I'll let you know if it works.

That seems to be working, the query for min(updated_date) no longer takes several minutes to complete after a long data archiving session, but it still takes an average 3s while initially it would return in a few ms, like the max(updated_date) query. Any idea on what else might be wrong?

The rows are deleted by primary key. Unfortunately, partitioning is not an option. You say it probably had to finish up all the pending index updates, but if that is the case, subsequent queries should be faster, right? I just noticed even an explain takes a long time to run, so it looks like you're right. Is there any way for me to force the index update immediately after deleting the chunk?

#1 is an interesting idea, but it took the same amount of time for the min value. Then I noticed it returned almost instantly for the max value. Since I'm deleting rows from the beginning of the index, it looks like something wrong with the index after the deletion. I'd prefer to avoid an optimize table because a copy of a table this size will take hours or days. Unfortunately, #4 is not an option.

Thanks for the tip, but that's not the issue.

@JehadKeriaki yes, InnoDB. Check my updated question.

@jynus but the first blog post implies any random insertion would have the same impact, PK or not.