Jeff Moden (12/31/2013)
REBUILDing indexes requires additional space in the database. A LOT of additional space if your tables are large. Typically, and across the database REBUILD of all indexes will require a bit more than 100% of the largest index size (usually, a Clustered Index because it contains ALL of the data for the table as well as a B-Tree).That bring us to a question... what is the GROWTH setup for on the database? If it's set for something small (typically somthing less than 100MB or {gasp} 1MB), then a huge amount of time will be dedicated to growing the database instead of using it.
I have a 20GB table in my database with 4 small indexes and a fairly wide covering index... it takes about 2 hours to rebuild all of the indexes on that and it's actually in pretty good shape already. Maybe you're just not being patient enough.
If anyone has a version of this updated for 2008+, please let me know, but the best document I've seen so far is http://download.microsoft.com/download/D/9/4/D948F981-926E-40FA-A026-5BFCF076D9B9/TEMPDB_Capacity_Planning_Index.doc
See page 8 of 10 for a chart, but ONLINE clustered index rebuilds take more space than the amount of space the amount the clustered index takes.
As far as time goes:
1) Check for fragmentation at a filesystem level first - Jeff's right to point out autogrowth, and the side effect of autogrowth is what can be called "Filesystem File level fragmentation".
2) Check for excessive VLFs second - autogrowth on log files often leads to this. Kimberly L. Tripp is one of the authorities here, see http://www.sqlskills.com/blogs/kimberly/transaction-log-vlfs-too-many-or-too-few/[/url]
3) If you have either space or time constraints, start small - deliberately start with the smallest indexes/tables that have fragmentation you consider significant, and work up; this will provide progressively more free space in your user database MDFs as you continue, will start providing performance benefits, and... see 4.
4) Whatever you do, if maintenance windows are a concern, start estimating! How long did it take to do a ~100k page nonclustered index? A ~100k page clustered index? It's not going to be terribly consistent, but you'll get an idea of what takes how long - rebuilding clustered and nonclustered indexes are very different (or they were in 2000). You do not want to show up monday morning and see a critical table still locked, with business users unable to get their jobs done.