MSDB db too big?

Microsoft provides “sp_delete_backuphistory ‘6/1/2011’“.   However, this can take a very long time unless you also add indexes to the backup table.  This is what did the trick for me:

Create Nonclustered index idx_backupset_finishdate ON backupset (backup_finish_date) INCLUDE (backup_set_id, media_set_id)

What was taking 20 minutes now takes 1 minute.

Enjoy!