Perhaps the data you need to search is not the same as the data you might want to encrypt? For instance name, address, ssn (or similar), billing info, etc. could all be encrypted and you could still look for e.g. 50yo women in the Northeast USA who haven't had a checkup in the last three years.

Of course many DBs need to search by name, but maybe it can be set up to search by a hash of name? Hashes seem a bit simpler than homomorphic search.