Sql-server – is it safe to compress backups for databases with TDE enabled

_{Community Wiki answer generated from comments on the question by QueueMann and Aaron Bertrand♦}

Database backup files throws away any unused space in your data files in the backup process.

TDE doesn't have to encrypt empty pages, and the backup process doesn't have to include the space in the backup, but they are still empty pages contributing to data file size.

Since the additional trace flags allowed you to narrow the delay down to the stage where the process tries to write to msdb, I'm willing to bet one or both of these returns high numbers:

SELECT MAX(row_count), SUM(in_row_reserved_page_count)
  FROM msdb.sys.dm_db_partition_stats 
  WHERE [object_id] = OBJECT_ID('msdb.dbo.backupset');

SELECT database_name, [type], c = COUNT(*)
  FROM msdb.dbo.backupset
  GROUP BY database_name, [type]
  ORDER BY c DESC;

You can consider whittling away at some of the data in that table. Of course, only you can know if you have reasons to keep backup history that otherwise should probably be cleaned up in most cases (for example, the first rule I declare to identify junk history data is for databases that no longer exist - but what if you have renamed a database recently?). So please think about each of these rules and only delete backups where the rules make sense to you based on these scenarios. For example:

CREATE TABLE #bs(id INT, ms INT);

-- Databases that no longer exist on this server:
INSERT #bs(id,ms) SELECT backup_set_id, media_set_id
FROM msdb.dbo.backupset 
WHERE database_name NOT IN (SELECT name FROM sys.databases);

-- All copy_only backups (because who cares?):
INSERT #bs(id,ms) SELECT backup_set_id, media_set_id
FROM msdb.dbo.backupset 
WHERE is_copy_only = 1;

-- All diffs except the most recent:
;WITH x AS 
(
  SELECT backup_set_id, media_set_id, 
    rn = ROW_NUMBER() OVER (PARTITION BY database_name 
      ORDER BY backup_set_id DESC)
  FROM msdb.dbo.backupset
  WHERE [type] = 'I'
  AND backup_finish_date IS NOT NULL
)
INSERT #bs(id,ms) SELECT backup_set_id, media_set_id
FROM x WHERE rn > 1;

...

-- All log backups prior to the most recent full:
INSERT #bs(id,ms) SELECT backup_set_id, media_set_id
FROM msdb.dbo.backupset AS l
WHERE [type] = 'L' AND EXISTS
(
  SELECT 1 
    FROM msdb.dbo.backupset AS bs2
    WHERE database_name = l.database_name
    AND [type] = 'D' 
    AND backup_finish_date > l.backup_finish_date
);

-- All fulls except the most recent successful non-copy-only full backup:
;WITH x AS 
(
  SELECT backup_set_id, media_set_id, 
    rn = ROW_NUMBER() OVER (PARTITION BY database_name 
      ORDER BY backup_set_id DESC)
  FROM msdb.dbo.backupset
  WHERE [type] = 'D'
  AND is_copy_only = 0
  AND backup_finish_date IS NOT NULL
)
INSERT #bs(id,ms) SELECT backup_set_id, media_set_id
FROM x WHERE rn > 1;

Need to also delete some file and filegroup information:

DELETE msdb.dbo.backupfile
WHERE backup_set_id IN (SELECT id FROM #bs);

DELETE msdb.dbo.backupfilegroup
WHERE backup_set_id IN (SELECT id FROM #bs);

DELETE mf
FROM msdb.dbo.backupmediafamily AS mf
WHERE media_set_id IN (SELECT ms FROM #bs)
AND NOT EXISTS (SELECT 1 FROM msdb.dbo.backupset
  WHERE media_set_id = mf.media_set_id);

DELETE ms
FROM msdb.dbo.backupmediaset AS ms
WHERE media_set_id IN (SELECT ms FROM #bs)
AND NOT EXISTS (SELECT 1 FROM msdb.dbo.backupset
  WHERE media_set_id = ms.media_set_id);

You also need to delete associated restore history:

DELETE msdb.dbo.restorefilegroup WHERE restore_history_id IN
(SELECT restore_history_id FROM msdb.dbo.restorehistory
  WHERE backup_set_id IN (SELECT id FROM #bs));

DELETE msdb.dbo.restorefile WHERE restore_history_id IN
(SELECT restore_history_id FROM msdb.dbo.restorehistory
  WHERE backup_set_id IN (SELECT id FROM #bs));

DELETE msdb.dbo.restorehistory
  WHERE backup_set_id IN (SELECT id FROM #bs);

And then finally the main rows can be deleted without violating any constraints:

DELETE msdb.dbo.backupset 
WHERE backup_set_id IN (SELECT id FROM #bs);

DROP TABLE #bs;

This whole process will not likely be fast - I highly recommend doing it during a maintenance window or slow period, and most certainly suspend all backup jobs while doing this.

On Standard Edition there's no real clean way to do this as an online operation, but after you've deleted all those rows, you'll likely benefit most from a full rebuild:

ALTER INDEX ALL ON msdb.dbo.backupset REBUILD;

The above was based partially on the logic included in the system procedure dbo.sp_delete_backuphistory, which leaves out some of the above criteria, has a reputation for locking up the entire set of backup- and restore-related msdb tables, and only allows a singular filter on date (which may not be very helpful depending on a variety of factors, including the percentage of bloat attributed to log backups prior to their most recent fulls, never mind the fact that different databases may be on completely different schedules). You can see where most of my logic came from, though, by looking at the definition for yourself:

EXEC msdb.sys.sp_helptext @objname = N'dbo.sp_delete_backuphistory';