For me at least, this would be completely unacceptable as a search replacement, as I frequently search old message bodies. ... However, based on the experience of desktop search, I think pure client side search would probably have reasonable initialization time and space overhead, and would certainly make searches faster, at least compared to my current Gmail experience.
Just install Mozilla Thunderbird and use IMAP. Client side search, all your devices sync via IMAP, no ads, and free software.