After quite a bit of work on this one it appears that SP1 (and a slightly earlier hotfix) were almost coincidental in this problem rather than being the cause - and it can occur even without SP1 if you add enough dimensions to your cubes. The best resolution is a combination of the first 2 or all 3 of the following items:
1. Keep you statistics up to date! In minor cases updating the statistics on your reporting database can help - but in all cases it is required to get the full benefit. You should set up a maintenance plan or initial for testing you could use sp_updatestats on your reporting database. See Christophe's recent blog for some guidance here - database maintenance is one of the keys to better queue performance.
2. if you see a "No Join Predicate" warning in the execution plan of the large query causing the problem then apply SQL Server 2005 SP2 Cumulative Update 6 http://support.microsoft.com/kb/946608 . The SQL bug is resolved by Hotfix 942444 which is in that roll up. Please also read http://support.microsoft.com/kb/942444 carefully, particularly the details of setting Trace Flags 4101 and 4121 - which are required to be set to active this hotfix. See the remarks section at http://msdn2.microsoft.com/en-us/library/ms188396.aspx for more details of trace flag setting. Use the command line option -T4101 and -T4121, and set these in the SQL Server Configuration Manager for the instance of SQL Server 2005 used for your reporting database.
*** Update - SQL Server 2008 R2 - CU7 + setting the flag for -T4136 will get you back to good build times if you have upgraded and gone slow again - thanks to Flo ***
***Update 2 - I think this should be -T4199 for 2008 R2 to do the exact same - -T4136 is for parameter sniffing - perhaps that results in the good execution plan too ***
3. If this still isn't giving you the speed of cube build you require then it might be time to consider upgrading your server hardware. In our tests with very large cube builds you can improve the build times with more RAM - and also x64 hardware (which also allows you to support even more RAM).
If you are not sure about step 2 - then see my previous posting which will help you identify the bad query - and then paste this into a SQL Query window against you reporting database and click to see the estimated query plan. In the execution plan - which will be quite large - you are looking for something like this:
And if you hover over the warning triangle you should see a warning of "No Join Predicate". Also note the expense (74% of the cost of the query) attributed to the Table Spool. This is where tempdb is getting heavily used.
As an example of potential improvements after following these steps (without any hardware upgrades) we have seen cube builds of 20+ hours complete in 45 minutes, and a 1 hour 15 minute build come down to less than 1 minute. Your mileage may vary :).
You may still see quite heavy tempdb usage and this is to be expected with such a large query - and should not be a concern. If Your server doesn't have the space for the tempdb SQL is trying to use after following these steps then time to invest in more disk space!