It's very good. I have ~3GB of email in tens of thousands of messages, about a decade's worth, in my FastMail account. Searching through all of that takes only a second. See https://www.fastmail.com/help/receive/search.html for what the search can do.