записи с done = 0 - это 3% от общего числа записей в таблице. Кажется, он должен по ним хорошо работать
зачем держать полный индекс ради 3% записей? сделать create .... where done=0 и в таком случае я думаю эффект будет лучше и размер индекса гораздо меньше.