Database Deletion Taking a long time

This is caused because there are missing indexes on the backupset table within the system database msdb:

After using the Display Estimated Query Plan Wizard a few times for the system stored procedure

exec dbo.sp_delete_database_backuphistory @database_name =  N'DBName'

I found the follwoing indexes needed to be added to the backupset table:

USE [msdb]
GO

CREATE NONCLUSTERED INDEX [idx_backupset_database_name_backup_set_id] ON [dbo].[backupset]
(
    [database_name] ASC
)
INCLUDE ( [backup_set_id]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
GO

CREATE NONCLUSTERED INDEX [idx_backupset_database_name_media_set_id] ON [dbo].[backupset]
(
    [database_name] ASC
)
INCLUDE ( [media_set_id]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
GO

CREATE NONCLUSTERED INDEX [idx_backupset_media_set_id] ON [dbo].[backupset]
(
    [media_set_id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
GO