How to minimize\plan ahead the effect of running sp_delete_backuphistory? Measure the gains too!
My gripes with this proc go back a long way:


The Annals of Hilariously Bad Code, Part 1: Critique the Code
The Annals of Hilariously Bad Code, Part 2


The problem you run into when deleting large amounts of data is the crappy estimate you get from the table variables. 

I've had pretty good luck creating a new version of the proc using temp tables. You could also try just adding recompile hints, but hey, this way we get useful indexes.

As a side note: if you still run into this blocking because this is running long, you can try either removing the transaction code, or changing it to encapsulate each individual delete (though at that point the benefits are negligible).

CREATE   PROCEDURE [dbo].[sp_delete_backuphistory_pro]
   @oldest_date datetime
 AS
 BEGIN
   SET NOCOUNT ON

   CREATE TABLE #backup_set_id      (backup_set_id INT PRIMARY KEY CLUSTERED)
   CREATE TABLE #media_set_id       (media_set_id INT PRIMARY KEY CLUSTERED)
   CREATE TABLE #restore_history_id (restore_history_id INT PRIMARY KEY CLUSTERED)

   INSERT INTO #backup_set_id WITH (TABLOCKX) (backup_set_id)
   SELECT DISTINCT backup_set_id
   FROM msdb.dbo.backupset
   WHERE backup_finish_date &lt; @oldest_date

   INSERT INTO #media_set_id WITH (TABLOCKX) (media_set_id)
   SELECT DISTINCT media_set_id
   FROM msdb.dbo.backupset
   WHERE backup_finish_date &lt; @oldest_date

   INSERT INTO #restore_history_id WITH (TABLOCKX) (restore_history_id)
   SELECT DISTINCT restore_history_id
   FROM msdb.dbo.restorehistory
   WHERE backup_set_id IN (SELECT backup_set_id
                           FROM   #backup_set_id)

   BEGIN TRANSACTION

   DELETE FROM msdb.dbo.backupfile
   WHERE backup_set_id IN (SELECT backup_set_id
                           FROM   #backup_set_id)
   IF (@@error &gt; 0)
     GOTO Quit

   DELETE FROM msdb.dbo.backupfilegroup
   WHERE backup_set_id IN (SELECT backup_set_id
                           FROM   #backup_set_id)
   IF (@@error &gt; 0)
     GOTO Quit

   DELETE FROM msdb.dbo.restorefile
   WHERE restore_history_id IN (SELECT restore_history_id
                                FROM   #restore_history_id)
   IF (@@error &gt; 0)
     GOTO Quit

   DELETE FROM msdb.dbo.restorefilegroup
   WHERE restore_history_id IN (SELECT restore_history_id
                                FROM   #restore_history_id)
   IF (@@error &gt; 0)
     GOTO Quit

   DELETE FROM msdb.dbo.restorehistory
   WHERE restore_history_id IN (SELECT restore_history_id
                                FROM   #restore_history_id)
   IF (@@error &gt; 0)
     GOTO Quit

   DELETE FROM msdb.dbo.backupset
   WHERE backup_set_id IN (SELECT backup_set_id
                           FROM   #backup_set_id)
   IF (@@error &gt; 0)
     GOTO Quit

   DELETE msdb.dbo.backupmediafamily
   FROM msdb.dbo.backupmediafamily bmf
   WHERE bmf.media_set_id IN (SELECT media_set_id
                              FROM   #media_set_id)
     AND ((SELECT COUNT(*)
           FROM msdb.dbo.backupset
           WHERE media_set_id = bmf.media_set_id) = 0)
   IF (@@error &gt; 0)
     GOTO Quit

   DELETE msdb.dbo.backupmediaset
   FROM msdb.dbo.backupmediaset bms
   WHERE bms.media_set_id IN (SELECT media_set_id
                              FROM   #media_set_id)
     AND ((SELECT COUNT(*)
           FROM msdb.dbo.backupset
           WHERE media_set_id = bms.media_set_id) = 0)
   IF (@@error &gt; 0)
     GOTO Quit

   COMMIT TRANSACTION
   RETURN

 Quit:
   ROLLBACK TRANSACTION

 END