What did you switch to? Because I switched to Thunderbird and now find my search is even worse than it was with Gmail.
Full-text search and indexing is done client-side via Orama, and search is on the order of single digit ms.
Thunderbird? Search like its 1999.
I've found no client that offers search expressions like Gmail.
Except Fastmail, whose results are wholly untrustworthy.
Granted, once in a few years I backup old emails into a different mbox. I guess this helps.