I have all my email going back to then too. Many GB. I always download all of it locally. The global search bar (which searches all of it) appears instantaneous. It must be well under under 200ms. Every time I've verified the result with grep the results are accurate. I have no idea how they get it so fast.

Searching within a folder is different. It does a linear scan. If you don't search the body it's fast enough - a few seconds I guess on a big folder. If you search the body of the email in a big file, then yes it can take a while.