I designed and built high-end web analytics software for years.

Sampling your data by visitor/cookie (not by page view) is the number one thing to do that that no one does. Just sample your data down by a factor of 10 or 100. The costs drop by a factor of 10 or 100, query speeds improve, and the business value of the data drops by very, very little.

The only unfortunate prerequisite for this approach is that you need a company/boss that understands that sampled numbers are OK even if they are not exact. (So, explain, if you must, that your industry insider source tells you that the notion of 'exact' in web analytics world is very loose indeed.)