How do I manage a database with millions of mail recipient records when searching on opens or click throughs?

We are working with a group that sends tens of thousands of mailings on a weekly basis so the civicrm_mailing_recipient (and related tables) have millions of records.

They also want to track opens and click throughs. The problem is that it takes eons (like over 5 minutes) to search these tables.

I think the answer is to purge this old data.

But just in case, I’m wondering if:

• There are optimizing tips to make these searches go faster?
• There are any extensions to help automate the purging of old recipient data? It seems that archiving email doesn’t touch this data
• Any other tips?

Thanks!