[Bellardia]

Did they say it was purely the database size?
Performance issues could also be server load (perhaps you have a bunch of inefficient mods or plugins that are hammering your server down. If this is the case consider removing some of the less important ones.

Your database size is pretty much relational to the amount of posts you have..if you're not willing to prune those then you won't see major differences. You could clear adminlog and moderator log if that data isn't of particular use to you. They can grow pretty large in size.