We run a pretty big Magento store. Some stats:

- 31 GB in DB size
- Over 700,000 orders
- Over 4,000,000 quotes
- Over 1,000,000 registered customers
- Over 25,000 products

The store runs fine, but we've been experiencing trouble in altering table structures (principally installing new modules that create lots of database structures).
By cleaning all the log tables, we can reduce the DB size to 20GB, but we still have quite a lot of trouble installing third-party modules (even in our staging environment, installations may timeout or either run for several hours). Creating these new DB structures is really exhausting.

Sessions are stored with Memcache.
We use varnish but we're switching to FPC as son as we find a workaround for all the 6 servers. **All the infrastructure is hosted in AWS**.
We're running Magento CE 1.6.2.0 (updating is in our plans but running the update isn't the fastest thing on this DB and and we're afraid it won't be possible in production without a big disruption of service).

**I need alternatives or ideas for optimizing this Magento DB**. I've read a few things about Mongogento (magento catalog + mongodb), but our problem isn't really the catalog.

Most topics on the internet talk about cleaning log tables, which improves the usability but doesn't solve all of our problems.