I use a smart mailbox in Apple Mail to filter out some of my messages automatically. Up until recently, it was instantaneous but something happened (I'm not sure what) to where now if I click on the smart mailbox, it takes about 30 seconds to generate what it apparently already found & I notice that Apple Mail's CPU usage spikes while it's looking. I'm not sure where to begin troubleshooting this.
** Edit **
I tried vacuuming the envelope, which didn't fix the problem. However, it did slightly change what was happening. Before, I would click on the smart mailbox & the count of messages would disappear & it would be 30 seconds of high CPU activity by Mail before I'd see the messages. Now, the count doesn't disappear, but it's still 30 seconds of high CPU activity by Mail before I see the messages.
I tried deleting the envelope so Mail would recreate it, which apparently re-imports your inboxes & re-indexes everything in Spotlight, but that didn't help either.
I'm considering renaming ~/Library/Mail & just starting from scratch.