The SQL Backup graphical user interface (GUI) provides the option to delete the backup and restore history from the msdb database and SQL Server Compact database for each SQL Server (Tools > Server Options > File Management). For more information, see File management options.

Selecting this option can cause performance problems when running backup or restore operations, or when using the SQL Backup GUI. If this is the case, you may find it helpful to clear the option and delete backup and restore history manually or as a scheduled task. 

The following script deletes backup and restore history older than the specified number of days from the msdb database, the SQL Server Compact database and the SQL Backup GUI activity cache:

----------------------------------------------------------------------------------------------------
-- Delete backup history from SQL Backup's SQL Server Compact database
----------------------------------------------------------------------------------------------------
SET NOCOUNT ON
DECLARE @backup_id INT ,
    @command NVARCHAR(4000) ,
    @retain_date NVARCHAR(64) ,
    @IDList VARCHAR(2000)

-- number of days of history that you want to retain (currently 30 days)
SET @retain_date = GETDATE() - 30

-- temp table for ids we're deleting.
IF OBJECT_ID('tempdb..#DeleteTheseIDs') IS NOT NULL 
    DROP TABLE #DeleteTheseIDs
CREATE TABLE #DeleteTheseIDs ( id INT )

-- get total from the SQL Server Compact database (this will also show an error if its corrupted)
EXEC [master]..sqbdata N'select COUNT(*) AS TotalBackupRows from backuphistory'
EXEC [master]..sqbdata N'select COUNT(*) AS TotalRestoreRows from restorehistory '

----------------------------------------------------------------------------------------------------
-- Delete backup history from msdb database
----------------------------------------------------------------------------------------------------
-- first do a standard delete
EXEC msdb.dbo.sp_delete_backuphistory @retain_date

----------------------------------------------------------------------------------------------------
-- Delete backup history from SQL Backup GUI activity cache
----------------------------------------------------------------------------------------------------

 --get all of the ids that we want to delete
SET @command = 'select id from backuphistory where backup_end < '''
    + @retain_date + ''''
TRUNCATE TABLE #DeleteTheseIDs
INSERT  INTO #DeleteTheseIDs
        EXEC [master]..sqbdata @command
SELECT  'Deleteing # Backup ids ' = COUNT(*)
FROM    #DeleteTheseIDs

 --loop until they're all deleted
WHILE EXISTS ( SELECT   1
               FROM     #DeleteTheseIDs ) 
    BEGIN

  --get next set of ids (do not get too many at a time, otherwise the list will be truncated)
        SET @IDList = ''
        SELECT TOP 150
                @IDList = @IDList + CASE WHEN @IDList = '' THEN ''
                                         ELSE ','
                                    END + CONVERT(VARCHAR(10), id)
        FROM    #DeleteTheseIDs
        ORDER BY id

  --delete history
        SET @command = 'delete from backupfiles where backup_id IN ('
            + @IDList + ')'
        EXEC [master]..sqbdata @command
        SET @command = 'delete from backuplog where backup_id IN (' + @IDList
            + ')'
        EXEC [master]..sqbdata @command
        SET @command = 'delete from backuphistory where id IN (' + @IDList
            + ')'
        EXEC [master]..sqbdata @command

  --delete from temp file
        SET @Command = 'DELETE FROM #DeleteTheseIDs where id IN (' + @IDList
            + ')'
        EXEC (@Command)    
    END

----------------------------------------------------------------------------------------------------
-- Delete restore history from SQL Backup GUI activity cache
----------------------------------------------------------------------------------------------------
 --get all of the ids that we want to delete
SET @command = 'select id from restorehistory where restore_end < '''
    + @retain_date + ''''
TRUNCATE TABLE #DeleteTheseIDs
INSERT  INTO #DeleteTheseIDs
        EXEC [master]..sqbdata @command
SELECT  'Deleting # Restore ids ' = COUNT(*)
FROM    #DeleteTheseIDs

 --loop until they're all deleted
WHILE EXISTS ( SELECT   1
               FROM     #DeleteTheseIDs ) 
    BEGIN

 -- get next set of ids
        SET @IDList = ''
        SELECT TOP 200
                @IDList = @IDList + CASE WHEN @IDList = '' THEN ''
                                         ELSE ','
                                    END + CONVERT(VARCHAR(10), id)
        FROM    #DeleteTheseIDs
        ORDER BY id

  --delete history
        SET @command = 'delete from restorefiles where restore_id IN ('
            + @IDList + ')'
        EXEC [master]..sqbdata @command
        SET @command = 'delete from restorelog where restore_id IN ('
            + @IDList + ')'
        EXEC [master]..sqbdata @command
        SET @command = 'delete from restorehistory where id IN (' + @IDList
            + ')'
        EXEC [master]..sqbdata @command

  --delete from temp file
        SET @Command = 'DELETE FROM #DeleteTheseIDs where id IN (' + @IDList
            + ')'
        EXEC (@Command)    
    END
SELECT  'Done.'