Large rolling update on huge table: Getting slower and slower
It probably would have been better to create the index as filter (i.e. with a WHERE clause) as that would get smaller as you updated more records that would then get filtered out of it:

CREATE NONCLUSTERED INDEX RECORD_DELETED_INDEX
  ON [dbo].[huge-table] ( [deleted] ASC, [deletedDate] ASC )
  WHERE deleted is null
  OR    deletedDate is null;


However, you are still going to run into the issue of scanning that index every time that loop runs. With 100 million rows in the table and updating 4000 per iteration, that is 25,000 times you are scanning the table (or index) looking for rows to update. It would be best if you reduced the number of times you queried the table.

Please see my answer to one of your other questions regarding this project for a setup that should make this process go much faster:

sql server: updating fields on huge table in small chunks: how to get progress/status?

In that answer, I show how to query the large table only 100 times. Each time it grabs the Clustered Index Key Field(s) and uses them for all of the UPDATE queries so that the updates are fast. And that setup also allows for getting the current progress of the operation quickly (and without having to query the table!) and cleanly cancelling the process.



It should be noted that this question relates to the following questions (listed in chronological order):


sql server: updating fields on huge table in small chunks: how to get progress/status? (noted above)
Are explicit transactions needed in this while loop?
SQL Server lock_escalation flag on ALTER TABLE -- can I really restructure without a table lock?