Hmm, 10M rows is a quite few, but it's not outside the realm of MSSQL and that does seem very slow.
We had a table with a huge row size (poorly designed) and over 10M rows. When we had to modify the structure, it was def. very slow, so what we did was (to keep the table online, and this is rough from memory because it was a long time ago):
- Created new table with the suffix "C" (for Conversion) and new structure (i.e. same as old one, but with new column/index/etc)
- SELECT * INTO tableC FROM table
- sp_rename 'table' 'tableOld'
- sp_rename 'tableC' 'table'
This way it doesn't matter how long the conversion takes, as the old data is online. It might cause issues with rows being written to the table whilst the conversion takes place though (this wasn't an issue for us as the data was only written once daily, but queried thousands of times an hour) so you might want to investigate that.