[lnanek2]

No clue how it actually works, but just as a software engineer I can think of plenty of ways to do it. So base case you have is just the equivalent of a table scan - go through each row and decrypt it and check if it matches. But then after that you can do a lot to speed it up. Like you could keep an accessed timestamp on the records and then search most recent ones first so after the first search for a patient on a day they have an appointment everything else will be fast that day. Lots of other speed ups possible, like checking who is searching and checking only their patients first, which may be possible to store as an unencrypted relationship that tells you which encrypted records to check.

Or heck, if you have enough memory, keep your indexes in memory where they aren't required to be encrypted. Or if you don't have enough then cache according to some algorithm that works good for the use cases.