Performance Recommendations for Large Volume of Data
It's important to know what sort of queries you are running.  Are they mostly based on the time of the record, or something other field?  That will inform what sort of approach you should take here.  Maybe your indexes should actually be multi-indexes for example.

What's your EXPLAIN statement say for your queries?  That's really one of the best ways to see where exactly things are slowing down and attack it.

Edit: Sorry, I just saw the SUBSTR query, I believe you can make indexes based on substrings of a column.  Have you done that?  That IS different from just having an index on the column itself vs. having a index on the substring(1,8) of said column.