Индексация не имеет никакого отношения к проблеме здесь. Подумайте о том, что вы делаете - вы изменяете все строки в своей таблице, поэтому независимо от того, как вы их выбираете, и если у вас есть индекс по t или нет, вы все равно сканируете всю таблицу.
Операция UPDATE == IO - это ваше узкое место. Получите более быстрые диски.
Если вы используете InnoDB, мой единственный совет будет посмотреть, если настройка innodb_flush_log_at_trx_commit и установка его в 2 помогает вашей производительности, но я сомневаюсь, что это всего лишь 1 запрос. Отключение ключей и их повторное включение после UPDATE не будет работать в InnoDB.