If you can afford a lock on the table to last a little longer you can go with creating the 2 indexes at once.
If not create the one by one... i'm sure some other queries will be honoured between those ALTER statements.
From MySQL 4.0 we have:
ALTER TABLE ... DISABLE KEYS and ALTER TABLE ... ENABLE KEYS Using the above when you have many inserts the missing index entries are created only once... maybe the same is with adding 2 indexes at a time instead of adding one at a time... So it is possible (although i din't found anything in the manual) that adding 2 indexes at a time will be faster ! [I'll get back if i'll find something in the Certification Study Guide... a pretty nice book !] -- Gabriel PREDA Senior Web Developer