We have an established web application, which is supported by a mysql database. We add data incrementally to various tables on a monthly basis. After recent updates, the database performance has degraded significantly and we had to back out the updates. So far I have identified the queries involved in the web service logic - there are no updates, just reads. I've established that all the queries are using efficient table indexes.
I know this is a difficult problem to diagnose, and I'm not expecting a definitive answer here, I just need some advice on further diagnostics, and hints for areas to investigate which will pin down what's causing the problem.