That's a bit overkill for a phone.
I recommend enabling server side search in Account Settings, much easier on resources.
It doesn't work well either in my experience. Not sure if K9 is really the one to blame, or the IMAP server (Gmail, in my case). As Thunderbird indeed does search locally, it isn't impacted by poor server side search anyway. Thanks for the suggestion, though.
If search works fast on Thunderbird is because it keeps all emails in your local hdd. To be fair you should also set the option account settings > fetching mail > local folder size to 'all' in K9.