You put mail into buckets (using some hashes), and hands out the bloom filter for each bucket.
It is better than downloading all mail, but it is nowhere near the speed I want my email search to be.