Summary

For large tables, it is nearly always preferable to move the data instead of altering the table. To get maximum speed, use one of the following patterns. Let us call the table you want to change S (for source).

1. Create an empty copy of S. Let us call that T
2. ALTER TABLE on T. This is very fast because T has no rows
3. If T has a cluster index, remove all other indexes but the cluster
4. If T is a heap, remove all indexes
5. Put the database in SIMPLE recovery mode (if you can, but be aware of the backup implications)
6. Use one of the two options provided in the Copy Data section below
7. Rebuild the indexes on T
8. Drop S and rename to T

Copy Data

In step 6 above, you will need to move data from S to T at highest possible speed. The following are two options:

1. Use INSERT ... SELECT
2. Use SSIS

Of these two, SSIS is the fastest. With INSERT ... SELECT you are restricted to a single thread. However, INSERT ... SELECT is much easier. See below for more details.

Option 1: INSERT ... SELECT

If T is a heap, do this:

INSERT INTO T WITH (TABLOCK) SELECT ... FROM S

This is minimally logged.

If T has a clustered index, do this:

DBCC TRACEON (610)
INSERT INTO T SELECT ... FROM S

This is also be minimally logged. The problem with this option is that you can only run one INSERT statement in parallel. Because SQL Server does not do parallel INSERT ... SELECT, this restricts you to around 40-80MB/sec - which is quite slow.

Option 2: Use SSIS

This option is a lot more trouble, but also faster. The idea is this:

1. Drop all indexes on T
2. Create an SSIS package that takes a parameter that selects a subset of the rows in S (using some filter that is supported by an index). The SSIS package then moves the rows to T using the TABLOCK hint in bulk mode
3. Execute multiple copies of the SSIS package, each operating on their own, distinct subset of S (so you don't duplicate rows in T)

This is MUCH faster because the packages can run in parallel. With this technique, I can typically move tables at GB/sec.

I would also add that not only data pages will be moved when creating a clustered index - also all the non-clustered indexes will have to be rebuilt since each row in non-clustered index contains clustered key value. All these data movements need to be logged and sorting process will heavily use tempDb since you probably don't have 500 GBs of memory available, right? ;)

You'll find plenty of debates and different opinions about using heaps and I'm of course speculating here but most likely there's a reason why such a big table doesn't already have a clustered index defined on top of it. It's not exactly the best practise but sometimes it does make sense to define a table without clustered index (quick, minimally logged inserts) with a few narrow non-clustered indexes that cover frequent queries.

Decision about adding any kind of index (primary, clustered, non-clustered, XML, spatial, ...) depends of course on the problem you're trying to solve. In OLTP system you typically optimise your indexes to improve write performance while in reporting systems like OLAP you usually need to work on read types of workloads.

And few suggestions to wrap this up: - primary key doesn't have to be clustered - if the table is not partitioned you should definitely consider partition it - if your goal is to make certain types of queries faster (and not trying to enforce uniqueness of your bigint column) you should consider creating additional (or modifying existing) non-clustered (possibly filtered) index or indexed view (perfect for aggregate queries)

Hope it helps, good luck!