Sql-server – Large insert/update in table causes timeout while SQL Server re-arrange indexes

No way to estimate how long it will take - so many different things would have an impact. Similar to what Paul writes about the length of a CHECKDB, very similar things would come into play with indexing and more. The best answer would be how long has it taken in the past? If you can't determine that, next best option would probably be to try it on a similar non-production environment, but even that won't necessarily match (i.e. concurrency concerns, etc. would be different).

As a side note, you may want to look into ONLINE INDEX OPERATIONS in Sql 2005 and above...I can't add a second hyperlink, but google "online index operations sql server" and click the top link.

I will assume you have good reasons to use guids as ids.

Fragmentation is mostly an issue for scans, less so for seeks. Fragmentation has a big impact on read-aheads, and seeks don't use nor need read aheads. An unfragmented index with poor column choice will perform always worse than a 99% fragment index with good, usable, columns. If you'd had described DW reporting style queries that scan the tables then I would had recommend focusing on eliminating fragmentation, but for the load you describe it makes more sense to focus on efficient (covering) seeks and (small) range scans.

Given that youre access pattern is always driven by @userId, this must be the leftmost column in the clustered index. I would also add setOn as the second column in the clustered index because it adds some marginal value on most queries (I say marginal because the @userId is so selective, at worst is 90 records from 90 mil., that the extra filtering added by @setOn is not critical). I woudldn't add any non clustered index, from the queries you describe there is no need for any.

The only problem is the deletion of old records (the 30 days retention). I would recommend against using a secondary NC index to satisfy this. I would rather deploy a weekly partitioning scheme with sliding window, see How to Implement an Automatic Sliding Window in a Partitioned Table on SQL Server 2005. With this solution, the old records are removed by a partition switch, which is just the most efficient way possible. A daily partitioning scheme would satisfy the 30 days retention requirement more exactly and perhaps is worth trying and testing. I hesitate to recommend 30 partitions directly because you describe some queries that have potential to seek a particular @userId records in each partition, and 31 partitions may create performance problems under heavy load. Test and measure both better.