Search has been faster than it used to be. I've noticed this in Mail on iOS as well. I use airmail, which i don't think it downloads all emails locally.