INDEXes are (often) useful for finding a few rows out of many. You need to look at all the rows, so an index is more trouble than it is worth. Hence, the "table scan".
Solution? Often it is building and incrementally maintaining a "summary table". You have not divulged much info, so I can't be very specific.
Here are some examples:
summary -
http://forums.mysql.com/read.php?10,421092 (Large Table Architecture)
partition, summary -
http://forums.mysql.com/read.php?106,288561 (Partitioning with range(to_days) issue)
data warehouse, summary -
http://forums.mysql.com/read.php?125,252723 (Database Design for huge set of data)
summary -
http://forums.mysql.com/read.php?10,252593 (Counters)
locks, summary tables -
http://forums.mysql.com/read.php?21,247124 (Solving table locking issues)
summary -
http://forums.mysql.com/read.php?125,245133 (Design approach for summary table by 3 items)
summary table -
http://forums.mysql.com/read.php?24,428050 (To store or calculate on the spot?)
ummary -
http://forums.mysql.com/read.php?125,393184 (Storing a large, dense tensor (35gb scientific data) -- is mysql appropriate?)
summary -
http://forums.mysql.com/read.php?10,364300 (Thinking about sorting articles..)
summary -
http://forums.mysql.com/read.php?52,359476 (Slow 'sending data' phase on mySQL query, for simple query)
summary -
http://forums.mysql.com/read.php?10,298557 (UNIX_TIMESTAMP Duplicate key)
ALTER, summary -
http://forums.mysql.com/read.php?125,287739 (Large table designissue)
huge, summary tables -
http://forums.mysql.com/read.php?10,282768 (Which storage engine?)
summary -
http://forums.mysql.com/read.php?125,266570 (Best way to store/access large amounts of data?)
summary, using index -
http://forums.mysql.com/read.php?24,253221 (InnoDB CPU Spikes)
summary -
http://forums.mysql.com/read.php?10,254332 (Very long query doubt... (Monster query...))
summary -
http://forums.mysql.com/read.php?10,247779 (compressing tables)
summary -
http://forums.mysql.com/read.php?24,372008 (Index performance)
summary -
http://forums.mysql.com/read.php?20,294180 (Multiple complex queries)
left_off, myisam vs innodb, summary -
http://forums.mysql.com/read.php?10,276359 (should i go with myisam or innodb?)