Growing database size

I searched for an answer to this, but didn’t find one so I thought I’d post.

We have a WP site which is a year old. It has been slowing down. The hosting service we use (who is very good with WP), looked into it and responded that one database was growing quite large (500,000+ rows), with one table at 300,000+ rows. They suggested trimming it by dates.

Is there a best-practices for this? Have I missed some obvious configuration issue that would prevent this??