Speeding up GROUP BY if you want aproximate results (mysqlperformanceblog.com)

or use a better dbms

Chris Jermaine has done some interesting work in giving DBMSs support for approximate query answers.

http://www.cise.ufl.edu/~cjermain/OLA