Every now and again I'll come across a SQL Server 2000 install which hasn't been touched in forever and has no maintenance scheduled, and I have to clear up the backup history tables manually.

Normally this just requires a call to msdb.dbo.sp_delete_backuphistory but in some cases when you have a few hundred thousand (or a million!) records this can literally hang up for days. So I put a little something together to help me do it quickly.

Obviously this would be prettier if we could use SQL 2005 syntax but it also doesn't have this kind of deletion problem either.

Declare	@ToDate Datetime = '20151001'

-- Part 1

Delete From msdb.dbo.restorefile
Delete From msdb.dbo.restorefilegroup
Delete From msdb.dbo.restorehistory

-- Part 2

Set Nocount On
Set Rowcount 1000
Declare @Rows Int

Set 	@Rows = 1
While 	@Rows <> 0
Begin
	Delete	bf
	From	msdb.dbo.backupset bs
	Join	msdb.dbo.backupfile bf
	On	bs.backup_set_id = bf.backup_set_id
	Where	bs.backup_start_date < @ToDate

	Set	@Rows = @@Rowcount
	Print	'.'
End

-- Part 3

Set 	@Rows = 1
While 	@Rows <> 0
Begin
	Delete	bs
	From	msdb.dbo.backupset bs
	Where	bs.backup_start_date < @ToDate
    
	Set	@Rows = @@Rowcount
	Print 	'.'
End

-- Part 4

Exec	msdb.dbo.sp_delete_backuphistory @ToDate

-- Clean up

Set Nocount Off
Set Rowcount 0

If this doesn't work for your situation I've also seen people describe dropping the foreign keys so you can truncate the tables involved and then recreating them. That seemed a little drastic to me.