I have the following EXPLAIN QUERY PLAN. It looks like it is using the correct index. But my query is still slow. I have around 20000 records in...

you don't need the order by because it will be disabled anyway /* If there is both a GROUP BY and an ORDER BY clause and they are ** identical, then disable the ORDER BY clause since the GROUP BY ** will cause elements to come out in the correct order. This is ** an optimization - the correct answer should result regardless. ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER ** to disable this optimization for testing purposes. */ if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy)==0 && (db->flags & SQLITE_GroupByOrder)==0 ){ pOrderBy = 0; } can you print out the explain data for the query

Also if the between returns only a small amount of values you want the index on the between value. If it returns a large amount of values > 1/3 of the table you want it on the group by. That what i have found to be the case what is your index on