Você pode tentar usar um banco de dados baseado em colunas. Esses tipos de banco de dados são muito melhores em consultas analíticas do tipo que você está descrevendo. Existem várias opções:

http://en.wikipedia.org/wiki/Column-oriented_DBMS

Tivemos uma boa experiência com o InfiniDB:

http://infinidb.org/

e Infobright parece bom também:

http://www.infobright.com/

Tanto o InfiniDB quanto o Infobright têm edições gratuitas da comunidade de código aberto, então eu recomendaria usá-las para obter alguns benchmarks sobre os tipos de benefícios de desempenho que você pode obter.

Você também pode querer analisar o particionamento de seus dados para melhorar o desempenho.