Deleting old data in MySQL becomes slower over time
I would look to the InnoDB redo log file size. 

The symptoms you describe is typical if you fill up the redo log with changes, which forces a "synchronous flush" — MySQL blocks further changes until it can free up a portion of the redo log by flushing dirty pages from the buffer pool.

RDS used to use an absurdly small redo log file size by default, 128M if I recall. For years they did not allow changing the size. But in the last couple of years they do allow changing it.

Here's how to check the size of your redo log file in megabytes:

mysql&gt; SELECT @@innodb_log_file_size / 1024 / 1024;


To change it, I think you'd use the RDS parameter groups UI, then restart your RDS instance to apply the change.



To monitor this, I'd watch the number of bytes written to the redo log:

mysql&gt; SHOW GLOBAL STATUS LIKE 'Innodb_os_log_written';


Measure that every 10 minutes or so, and plot it. The redo log files are of fixed size, and writes will eventually reach the end and wrap around to the beginning of the file. They must not overwrite changes in the log that represent dirty pages in the buffer pool, so before they get close to doing that, MySQL forces a synchronous flush.

So you can watch the rate of Innodb_os_log_written, by reading that variable periodically at even intervals. Compare this rate of log writes to the log file size (remember that you have two redo log files by default, so your redo log capacity is Innodb_log_file_size * 2).

This allows you to estimate "we overwrite the whole redo log file(s) every N minutes." This should correlate (roughly) to your 10-15 minutes time period when deletes are fast.

I think I recall there are some nuances to this calculation ... the Innodb_os_log_written might include some overwrites, i.e. some writes seek backwards to re-write a block under some circumstances. So there might be some cases where the numbers don't add up. I don't know deep details here.

In any case, InnoDB has long been known to be better able to handle heavy write workload if you increase the size of redo logs. It's tempting to increase it as large as you are allowed, but this may be overkill for most of your day-to-day workload with more modest write traffic. 

See also: 


https://www.percona.com/blog/2011/04/04/innodb-flushing-theory-and-solutions/
https://www.percona.com/blog/2008/11/21/how-to-calculate-a-good-innodb-log-file-size/
https://www.percona.com/blog/2016/05/31/what-is-a-big-innodb_log_file_size/