МОЙ тестовый код:
Разница 42 с и 2 мин.
mysql> UPDATE big_table SET id = INSERT(id,1,5,'');
Query OK, 2835999 rows affected (42.69 sec)
Rows matched: 2835999 Changed: 2835999 Warnings: 0
mysql> ALTER TABLE big_table ADD INDEX id(id);
Query OK, 2835999 rows affected (5.75 sec)
Records: 2835999 Duplicates: 0 Warnings: 0
mysql> UPDATE big_table SET id = INSERT(id,1,4,'');
Query OK, 2835999 rows affected, 2856 warnings (2 min 1.49 sec)
Rows matched: 2835999 Changed: 2835999 Warnings: 2856