I recently has cause to cleanup the backup history on a SQL 2000 box. Not an issue, standard DBA fare really. SQL 2000 never had history cleanup options in the maintainence plans. Therefore we have to create TSQL jobs to remove backup history.
Given there was several years of backup history I started to clear backup history using a nibble delete approach. This proved to be slower than I anticipated so I started investigating further.
The quickest option would have been to directly modify the system tables, truncating them. Whilst constraints prevent this, there are solutions out there that tell you in which order to clear down the underlying tables. Pradeep Adiga is one of many to blog on pruning backup history and the fact that only 4 indexes exist on the 8 backup tables in MSDB.
Of all the scripts for additional MSDB indexes, Geoff Hiten provides the most complete solution in his post MSDB Performance Tuning. A script for MSDB indexes is located there which greatly improves the time to perform housekeeping on the backup tables.
I should include it in my build scripts really, and roll the indexes out as standard.