Brief has a built-in sqlite vacuuming function: when you right-click on its Trash and choose "Empty Trash" it will ask if you want to compact the database. If you haven't done so for a long time it can take a few minutes. You might try using this function and seeing how long it takes, to compare with CCleaner's performance at the same task.
I should add: on my system (WinXP, FF 3.5.5), CCleaner does pause for a minute or so on the brief.sqlite database, but it also take Brief about the same amount of time to do its work.