Remove Backup History for databases no longer on the server

USE [msdb]
;
DECLARE @DBName NVARCHAR(128)
DECLARE @Delete nvarchar(max)

CREATE TABLE #DatabaseList
    (
    databasename nvarchar(128),
    deletestatus bit
    );
   
INSERT INTO #DatabaseList
SELECT DISTINCT database_name,
                0
FROM msdb.dbo.backupset
WHERE database_name NOT IN(
    SELECT name
    FROM sys.databases)
   
WHILE (SELECT COUNT(*) FROM #databaseList WHERE deleteStatus = 0) > 0
    BEGIN

        SELECT TOP 1 @DBName = databasename
        FROM #databaseList
        WHERE DeleteStatus = 0;

            SET @Delete = 'EXEC [msdb].[dbo].[sp_delete_database_backuphistory] @database_name = N''' +@DBName + ''''
   
            EXEC (@Delete)
   
            IF @@ERROR<>0 PRINT @Delete
   
        UPDATE #databaseList
        SET deletestatus = 1
        WHERE databaseName = @DBName;

    END

DROP TABLE #databaseList;

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