SQL Server Index Maintenance – Do We Need to Run Auto Update Statistics After Index Rebuild?

You can grab this data with the Auto Stats Event Class with SQL Trace. One of the event's data columns is Duration. As per the referenced BOL documentation above, here is a quote:

Duration: Amount of time (in microseconds) taken by the event.

That should give you a pretty good idea when/how long auto stats is taking. If you are seeing a lot of performance-halting auto update stats (synchronously), you could consider utilizing auto update statistics async. Turning this on will tell the query optimizer to not wait for statistics to be updated in order to continue compiling the query. This is one solution in order to prevent the direct interference of stats updates, but of course you're sacrificing fresh statistics for that particular query compilation.

For more information on this, please see the MSDN reference on Statistics.

Fragmentation on its own is not necessarily the evil demon it is made out to be. If your database files are stored on a SAN, or some types of RAID array, or perhaps on SSDs, index defragmentation will make very little difference since pages will be spread all over the disks no matter if they are fragmented or not. See this answer for a discussion of that: Is there any benefit to defragmenting SQL indexes in a SAN environment?

When you rebuild indexes, you should not indiscriminately set FILL_FACTOR = 80 - that setting needs to be evaluated on a table-by-table basis. Assuming the tables were at FILL_FACTOR = 100 prior to your rebuild, you have effectively increased the storage required for each table by 20%. That may be a good part of the reason why things are slower now.

Using OPTION (MAXDOP 1) on ALL queries is a bad idea as well. You should allow the query engine to decide whether to execute a parallel query or not. Set the appropriate MAXDOP option at the server level using EXEC sp_configure 'max degree of parallelism', X where X is the maximum number of cores to use for parallel queries. See this question for a discussion on MAXDOP: What is a good, repeatable way to calculate MAXDOP on SQL Server?

Adding a non-clustered index on a field (or fields) will certainly make the query run faster if the database engine decides to use the index.

You may want to ensure the statistics on the affected tables are up to date. See http://technet.microsoft.com/en-us/library/ms187348.aspx for the Books Online description of how to do that. SQLSkills also has an excellent article on statistics, here: http://www.sqlskills.com/blogs/erin/understanding-when-statistics-will-automatically-update/