Creating SQL Indexes on Large Tables I currently have a table with about 29 million records. The table currently has no indexes.  However, I would like to build a clustered composite index built on three columns.  

When I attempt to add the NON NULL constraint, my logs fill up. So my approach is to create three new columns with NON NULL, fill them up with data from the original three columns, and create my index on the three new columns.

In order to do this, I first loop through the table in batches to populate the column. This is because I was running out of transaction log space. This was based on the lock escalation page on Microsoft's site. The threshold is 5000 locks. If rows are being locked, I wanted to come in under that limit. So 4000 rows at a time.

I didn't create a new table, insert into it, then drop &amp; rename because I thought it would be more efficient to just change some data than move everything - I might be wrong about this. When I did try it, I ran out of log space again.

This is the SQL I am using to update my new columns looks like this:

DECLARE @Rows INT,
        @BatchSize INT;      -- keep this below 5k

SET @BatchSize = 4000;

SET @Rows = @BatchSize;     

BEGIN TRY
    WHILE (@Rows = @BatchSize)
    BEGIN
        UPDATE Top(@BatchSize) Master.VOUCHER_LINE
        SET tempBusinessUnit = BUSINESS_UNIT
        FROM Master.VOUCHER_LINE
        WHERE tempBusinessUnit = 'xxxxx'; /* This is a default value for the column. 
        It identifies columns that have not been updated. */

        SET @Rows = @@ROWCOUNT;

        /* This prints the time that each loop is completed.
        I use it to estimate how much time this script will take. */
        DECLARE @Time nvarchar(100)
        SET @Time = CAST(CURRENT_TIMESTAMP as nvarchar)
        RAISERROR(@Time, 0, 1) WITH NOWAIT

    END
END TRY

BEGIN CATCH
    DECLARE @ErrorMessage NVARCHAR(4000);
    DECLARE @ErrorSeverity INT;
    DECLARE @ErrorState INT;

    SELECT @ErrorMessage = ERROR_MESSAGE(), @ErrorSeverity = ERROR_SEVERITY(), @ErrorState = ERROR_STATE();

    RAISERROR(@ErrorMessage, @ErrorSeverity, @ErrorState);
END CATCH;


With 29 million records (and about 100 columns), I expect this operation to take a while. After running for the first hour, the performance is 4,000 records about every 2 minutes.  At that rate this single column will be done in approximately 10 days.

Is there something I can do to improve performance?
Community wiki because the root of the answer (use an MLT to copy the data) was already in the comments. Shoutout to dnoeth and Der Kommissar for already explaining most of this in the comments.

Kendra Little has a great article on this topic. In general, the ALTER TABLE statement can't be assumed to be minimally logged, in particular if it is a size-of-data operation, meaning that

each record in the table must be updated

When something is a size-of-data operation is a little outside the scope of this question, and you can find good resources for it online, but in general, if changing the column metadata also requires updating the table itself (which making a column NOT NULL is) then you're going to hit this bucket. As Kendra mentions, this can be really bad:

Once you get to the point where you can alter the data, you run into a different problem:

Altering the column uses a huge amount of transaction log space
It’s reaaaalllll slow

This is because changing from INT to BIGINT is a “size-of-data” operation.
SQL Server has to go through and update Every. Single. Row.
And log it.
And SQL Server has to reserve extra space in the log in case it needs to roll back (because that will require additional logging).
If you get this far without thinking about how much log file you’re going to need and you run out, then things get extra slow, because most of that rollback’s going to be done by just one thread.

The solution is, not surprisingly, also called out in that article. You're likely going to need to take a downtime, and you're likely going to need to create a new table, copy all the data, and then swizzle everything to be pointing in the right direction.
The most important feature that this relies on is Minimal Logging (required reading). If/when you achieve Minimal Logging, you're likely going to be able to eliminate your batching (or at least get rid of a lot of it). Additionally, you can likely do it without too much of a downtime if you use Snapshot Isolation (also required reading). In that scenario, you just start dumping data into a copy of the table to get most of it in, then take a downtime, clean up any discrepancies that happened during that time, swap the tables, fix any foreign keys, etc etc, then come away from downtime.
If you find yourself still in need of batching, you're going to be better off first getting a list of keys to process, and looping over that instead of using TOP or other techniques (likely gets you better table access and will avoid any sorts).
You'll also want to keep your recovery model in mind; if you have a FULL recovery model then you will need a manual full-backup, then switch to SIMPLE, do the work, switch back, and backup again. This is because minimal logging requires SIMPLE recovery mode.