> WHERE STARTTIME>=2012110900 and STARTTIME<=2012111623
> AND bts_name IN ('BTEAG0716A', 'BTEAG0716B', 'BTEAG0716C')
1. Change the datatype of STARTTIME to INT UNSIGNED so that you can PARTITION on it.
2. Add PARTITION BY RANGE(STARTTIME) ... with 20-50 partitions.
3. Have an index starting with bts_name.
Then, and only then, will that SELECT run faster. (OK, there may be other ways.)
In fact, a non-partitioned table with
INDEX(bts_name, STARTTIME)
will perform well if you have a new enough version of MySQL. (I don't know when that particular optimization (IN, then 'range') was implemented.)
> I cannot modify the table structure
That is not a viable position to be in!
> One developer tried to add index and it hanged (due to huge table's size) so he had to break the process to release the lock.
Virtually any ALTER on a huge table takes a long time. See
http://www.percona.com/doc/percona-toolkit/2.1/pt-online-schema-change.html