Hio

I agree with all the previous statements the other guys made espesially having indexes on individual columns and then a covering index on them as well. There is no real reason for that. If you want to use your covering index suffciently make sure you create the covering index in the order that you will query (left to right).

I also noticed that you do alot of converts ect in your where clause, not a good idea , this increases read IO and CPU IO and increases the cost of the query overall.

Even if this will be executed once a day you don't want batch runs that is worth 1.2 million rows to take to long ,espesially if other batch jobs are dependant on this one's success.

The partitioning comment is very valid but if you do not want to partition make sure you use a clustered index on the addrtype column , since non-clustered indexes are better for row specfic searches and high selectivity values and clusterd indexes are good for that as well but clustered indexes are good for range values.You can also if capcacity allows you to split the table into two base tables each having data with the different addrtype in it (this is where partitioing is so good) so you will work with each addrtype indvidually and this will decrease the row sizes you work with per batch

Have you tried creating the indexes specifying MAXDOP ? ..maybe using multiple threads might help you

Getting back to your question why do the index creation takes so long ...alll these index creation will take long concidering the duplication of indexes you are creating. Also look at your data types and column lenghts this is alo a good indication why indexes might take long. Have you analysed the waitstats of the engine while you create these indexes, maybe you have blocking of some sort or tempdb is under pressure ..you will need to benchmark and get baselines , try different approaches and select the best approach.